高廣尚

GAO Guangshang1，2

1.桂林理工大學 現(xiàn)代企業(yè)管理研究中心，廣西 桂林 541004

2.桂林理工大學 商學院，廣西 桂林 541004

1.Research Center for Modern Enterprise Management,Guilin University of Technology,Guilin,Guangxi 541004,China

2.School of Management,Guilin University of Technology,Guilin,Guangxi 541004,China

1　引言

大數(shù)據(jù)環(huán)境下，數(shù)據(jù)既有多樣性（variety）[1]，又有演化性[2]。具體到數(shù)據(jù)集而言，多樣性體現(xiàn)在，若干不同形式的記錄（或稱為數(shù)據(jù)對象）描述現(xiàn)實世界同一實體。由于這些記錄的某些對應(yīng)屬性的值之間存在細微差別，因而它們被稱為近似重復(fù)記錄（approximate duplicate record）[3-4]。而演化性體現(xiàn)在，屬性值會以相對較快的速度產(chǎn)生細微變化。從聚類角度來看，實體解析（Entity Resolution，ER）定義為：通過合適的相似性函數(shù)以盡可能快地將描述現(xiàn)實世界同一實體的所有近似重復(fù)記錄聚類到同一個聚簇中（或劃分到同一個組中），使得每個聚簇表示不同的實體[5-9]。目前從整體上來看，實體解析分為兩大類：成對實體解析（Pairwise ER）和基于聚類的實體解析（Clustering-based ER）[8]。其中，成對實體解析需要對數(shù)據(jù)集中所有記錄進行兩兩比較，涉及的時間復(fù)雜度為Ο(n2)，而基于聚類的實體解析則無需進行兩兩比較，因此涉及的時間復(fù)雜度可能會遠小于Ο(n2)。

然而在實際應(yīng)用中，聚類又分為監(jiān)督聚類和無監(jiān)督聚類兩種[10-12]，前者需要訓(xùn)練數(shù)據(jù)，后者卻不需要訓(xùn)練數(shù)據(jù)，并且不依賴領(lǐng)域知識，不需要事先設(shè)定聚簇的數(shù)量。無監(jiān)督聚類本質(zhì)上就是將根據(jù)某些標準被判定為彼此相似的記錄聚類到同一個聚簇的過程[13-15]，最后使得位于同一聚簇內(nèi)的所有記錄彼此間高度相似（同質(zhì)性），而位于不同聚簇內(nèi)的所有記錄彼此間高度不相似（整齊分隔性（neatly separation））[12，16]。無監(jiān)督聚類結(jié)果的好壞取決于精心設(shè)計的算法是否能最小化聚類過程中可能存在的兩種不正確匹配情形：false-positives（錯誤肯定）和false-negatives（錯誤否定），前者表示被算法認為匹配的兩條記錄實際上卻不與同一實體相對應(yīng)，后者表示兩條記錄實際上對應(yīng)于同一實體但卻被算法認為不匹配[17]。鑒于此，本文主要從無監(jiān)督聚類角度，梳理和總結(jié)一些重要的引導(dǎo)無監(jiān)督聚類過程的啟發(fā)式方法，并分析現(xiàn)有研究中取得的成果及存在的不足，最后提出未來的研究重點。

2　基于特定類型的無監(jiān)督聚類方法

針對特定類型的分析有助于引導(dǎo)無監(jiān)督聚類過程?，F(xiàn)有研究中基于特定類型的無監(jiān)督聚類方法主要分為4種：基于優(yōu)先隊列的無監(jiān)督聚類、基于圖分割的無監(jiān)督聚類、基于中心結(jié)點的無監(jiān)督聚類和基于緊湊集的無監(jiān)督聚類。

2.1　基于優(yōu)先隊列的無監(jiān)督聚類

基于優(yōu)先隊列的聚類思路：首先，使用記錄的若干屬性產(chǎn)生排序鍵（sorting key），繼而得到排序鍵值（sorting key values），然后，將數(shù)據(jù)集中記錄按排序鍵值升序（或降序）進行排序，這讓那些最有可能相似的記錄相鄰地排列在一起；最后，依次取出排序后的記錄并與優(yōu)先隊列中的元素進行比較（從優(yōu)先級高的元素開始），以判定當前記錄是分配到與其比較的元素所指定的聚簇中，還是分配到新增的聚簇中（此時，當前記錄還需要加入到優(yōu)先隊列中作為新的元素，同時其優(yōu)先級設(shè)定為最高）[18-19]。具體過程如圖1所示，其中聚簇C1中的點表示對應(yīng)的記錄，以下類似。

基于優(yōu)先隊列的聚類具有以下優(yōu)點：（1）在速度上，實驗結(jié)果表明，它能減少近75%的記錄對比較次數(shù)，因為每條記錄僅與少量的元素進行比較即可，無需與整個數(shù)據(jù)集進行比較[20-21]。（2）在精度上，由于融合了近鄰排序思想（sorted neighborhood），它的匹配精度與基本近鄰排序方法（basic sorted neighborhood）相當。（3）在比較過程中，它能很好地自適應(yīng)通過排序鍵值所發(fā)現(xiàn)的記錄塊（如圖1內(nèi)表格中的虛線框所示）。其存在的不足：（1）聚類過程在很大程度上依賴于產(chǎn)生的排序鍵值，如果記錄中充當或部分充當排序鍵值的屬性值出現(xiàn)異常（例如不一致、過時、冗余和不精確等），那么該記錄將很少有機會獲得成功的匹配。（2）隊列中的元素通常并不能代表它所對應(yīng)的聚簇本身，元素本質(zhì)上是一個在比較過程中動態(tài)產(chǎn)生的由若干記錄組成的集合，因此在將元素與其他記錄進行比較時，就可能無法正確算出它們之間的相似性值，從而容易出現(xiàn)錯誤肯定或錯誤否定的情形。

2.2　基于圖分割的無監(jiān)督聚類

事實上，記錄之間的兩兩比較結(jié)果可表示成一個相似性圖形（similarity graph），其中結(jié)點表示記錄，邊表示其所連接的兩條記錄被算法判定為相似，邊上的權(quán)值表示記錄間的相似性值，如圖2所示。很顯然，圖2中的相似性圖形包含兩個子圖，一個由結(jié)點r1～r4組成（S1），另一個由結(jié)點r5～r6組成（S2）。基于圖分割的聚類思路：首先，預(yù)先設(shè)定每個子圖中允許最多包含的結(jié)點數(shù)量，或設(shè)定邊的權(quán)值不能少于某個閾值；之后，依據(jù)這些特征持續(xù)分割子圖，直到滿足要求；最后，分割后的每個子圖表示一個新的聚簇[13，22]。

圖1　基于優(yōu)先隊列的聚類

圖2　基于比較結(jié)果構(gòu)成的相似性圖形

以子圖S1為例，如果設(shè)定子圖中允許包含的最大結(jié)點數(shù)量為nc=2，那么該子圖上具有最小權(quán)值（5.05）的邊將首先被刪除（假設(shè)從最小權(quán)值開始），于是子圖被分割成兩個新的子圖。由于此時兩個新的子圖各自所包含的結(jié)點數(shù)量均未大于2，因此分割將不再持續(xù)，這時它們表示兩個不同的聚簇，一個由結(jié)點r1和r2組成，另一個由結(jié)點r3和r4組成。

同樣以子圖S1為例，如果設(shè)定子圖中邊的權(quán)值不能少于閾值tc=5.25，那么結(jié)點r2和r3之間的邊將最先被刪除，之后結(jié)點r1和r2之間的邊也將被刪除，最后由于r3和r4之間邊上的權(quán)值為5.25。因此刪除過程將不再持續(xù)，最后子圖被分割成3個子圖，表示3個不同的聚簇，一個由結(jié)點r1組成，一個由結(jié)點r2組成，另一個由結(jié)點r3和r4組成。

基于圖分割的聚類具有以下優(yōu)點：分割過程容易實現(xiàn)；不需要復(fù)雜的計算。其存在的不足：本應(yīng)屬于同一子圖的結(jié)點可能會因閾值選取不當而被劃分到不同的子圖中，從而導(dǎo)致真正的匹配被遺漏，錯誤的匹配被認可。

2.3　基于中心結(jié)點的無監(jiān)督聚類

為在相似性圖形上進行聚類分析，除采用分割思想外，還可以采用中心結(jié)點思想?；谥行慕Y(jié)點的聚類思路：首先，將子圖中所有邊按其權(quán)值降序進行排序；然后，將最靠前的邊(ri,rj)上的結(jié)點ri指定為聚簇的中心結(jié)點；最后，將所有出現(xiàn)在排序列表中的邊(ri,rj)上的結(jié)點rj分配到該聚簇中，而不是任何其他聚簇[23]。

同樣以子圖S1為例，起初，所有邊按其權(quán)值降序排序后形成的列表為：(r3,r4)、(r1,r2)和(r2,r3)，分別對應(yīng)權(quán)值5.25、5.20和5.05。首先，考慮最靠前的邊(r3,r4)，如果結(jié)點r3被標記為聚簇的中心結(jié)點，那么結(jié)點r4也屬于該聚簇，因為它們由同一條邊相連。隨后考慮邊(r1,r2)，很顯然，此時結(jié)點r1和r2均沒有被標記為聚簇的中心結(jié)點或?qū)儆谀硞€聚簇，因此結(jié)點r1應(yīng)被標記為另一個聚簇的中心結(jié)點，同理，結(jié)點r2屬于該聚簇。最后考慮邊(r2,r3)，由于其中兩個結(jié)點均已被分配給某些聚簇，因此這條邊將不再作進一步考慮。最后，通過采用中心結(jié)點思想，可在該子圖上產(chǎn)生兩個聚簇，一個由結(jié)點r1和r2組成，另一個由結(jié)點r3和r4組成。

在實際應(yīng)用中，從一對結(jié)點中選擇哪個結(jié)點作為聚簇的中心結(jié)點，有時可能會顯著影響最終的聚類結(jié)果。為解決這一問題，MERGE-CENTER方法[23]認為，當兩個聚簇的中心結(jié)點非常相似時，可將兩個聚簇合并為一個聚簇。

基于中心結(jié)點的聚類方法可能會產(chǎn)生比基于圖分割的聚類方法更多的聚簇，因為它只將那些與聚簇中心的記錄相似的記錄放入同一個聚簇。

2.4　基于緊湊集的無監(jiān)督聚類

在相似性圖形上進行聚類分析有一定的局限性，因為相似性圖形結(jié)構(gòu)本身由用于判定記錄對為匹配或非匹配的閾值決定，它是一個用于所有被比較的記錄對的全局參數(shù)。為此，有專家認為可利用緊湊集（Compact Set，CS）特征來進行聚類分析[13，24]，它定義表示同一實體的記錄彼此更相似，可為每個聚簇設(shè)置不同的閾值，以半徑p表示?；诰o湊集的聚類思路：利用記錄對之間計算出的所有相似性值，而不僅僅是那些被判定為匹配的記錄對之間的相似性值，來對數(shù)據(jù)集進行聚類，同時利用那些彼此相似的記錄，以及位于它們周圍的記錄的數(shù)量來引導(dǎo)聚類過程[13]，最后使得形成的聚簇是一個具有稀疏鄰居的緊湊集。這種方法類似于基于密度的聚類方法[15]。

緊湊集內(nèi)部的記錄對之間的距離小于任何非緊湊集內(nèi)的記錄對之間的距離，表示為：ri,rj∈CS：dist(ri,rj)＜dist(ri,rk)，?rk?CS 。此外，記錄 ri的鄰居集定義為：N(ri)=p·nn(ri)，其中，nn(ri)是記錄ri到其最近鄰居的距離，p決定以ri為中心的圓的半徑大小。如果ri的鄰居集N(ri)中的記錄數(shù)量低于某一常數(shù)閾值，那么ri的鄰居就被定義為稀疏的。如圖3顯示了一個緊湊集，包含結(jié)點r1、r2和r3，以及作為邊的權(quán)值的距離（等于1減去相似性值），其中r1的鄰居集N(r1)=p·nn(r1)=0.1×p=0.1p，假定它包含結(jié)點r4和r5。

圖3　基于緊湊集的聚類

基于緊湊集的聚類具有以下優(yōu)點：大小受限的聚簇有助于高效計算；能避免產(chǎn)生過大的聚簇。其存在的不足：聚簇的形成取決于記錄的鄰近記錄的數(shù)量和密度，而不是一個全局閾值。

3　基于經(jīng)典算法的無監(jiān)督聚類方法

基于特定類型的無監(jiān)督聚類具有一定的局限性：算法可擴展性不強，算法理論基礎(chǔ)不完備和算法性能不穩(wěn)定等；相比之下，基于經(jīng)典算法的無監(jiān)督聚類卻具有諸多優(yōu)越性：理論基礎(chǔ)堅實，算法實現(xiàn)簡單，可擴展性較好和可處理高維數(shù)據(jù)等。現(xiàn)有研究中基于經(jīng)典算法的無監(jiān)督聚類方法主要分為3種：基于凝聚層次聚類的無監(jiān)督聚類（Agglomerative Hierarchical Clustering，AHC）、基于相關(guān)性聚類的無監(jiān)督聚類（Correlation Clustering，CC），以及基于局部敏感哈希的無監(jiān)督聚類（Locality-Sensitive Hashing，LSH）。

3.1　基于凝聚層次聚類的無監(jiān)督聚類

凝聚層次聚類的基本思想：在給定待聚類的N個記錄對象和N×N的距離矩陣的情況下，從每個對象作為個體聚簇開始，每一步合并兩個最接近的聚簇[25-26]。凝聚層次聚類涉及兩個重要參數(shù)：相似性度量方法和閾值，前者通過歐式距離來判斷兩個聚簇之間的相似度，后者用作聚類迭代過程的終止條件，即當最近的兩個聚簇的距離大于閾值時，則認為迭代可以終止。圖4（a）顯示了迭代聚類過程，最終返回C1、C3和r6（單獨作為一個聚簇）3個聚簇（假定滿足終止條件）；圖4（b）相應(yīng)地顯示了這一自底向上的迭代聚類過程，同時也說明了凝聚層次聚類具有“層次”特性。

凝聚層次聚類的關(guān)鍵是如何計算聚簇之間的距離，現(xiàn)有研究主要采用4種方法：單鏈接方法、全鏈接方法、平均鏈接方法和權(quán)威記錄方法[26]。單鏈接方法又稱最小值方法，聚簇之間的距離等于聚簇內(nèi)成員間的最短距離。這種方法容易造成“Chaining”效應(yīng)，即兩個實際上相離較遠的聚簇因為聚簇內(nèi)個別距離較近的點而合并，使得相離較遠的點因為若干相離較近的“中介點”而被鏈接起來，并且這種效應(yīng)可能會逐漸擴大。全鏈接方法又稱最大值方法，聚簇之間的距離等于聚簇內(nèi)成員間的最遠距離，與單鏈接方法相反，全鏈接方法中相離較近的聚簇可能因為其中個別相離較遠的點而無法合并。平均鏈接方法是單鏈接方法和全鏈接方法的折中策略。權(quán)威記錄方法需要首先為每個聚簇構(gòu)造權(quán)威記錄，之后任意兩個聚簇之間的相似度就定義為二者的權(quán)威記錄之間的相似度。一般情況下，選擇哪種方法與具體的應(yīng)用相關(guān)。

基于凝聚層次聚類的無監(jiān)督聚類具有以下優(yōu)點：（1）定義距離和規(guī)則的相似度較容易，并且限制少；（2）可以發(fā)現(xiàn)聚簇的層次關(guān)系；（3）可以聚類成其他形狀。其存在的不足：（1）計算復(fù)雜度較高，尤其在處理大量數(shù)據(jù)時，因為每次都要計算多個聚簇內(nèi)所有數(shù)據(jù)點的兩兩距離；（2）奇異值也能對聚類過程產(chǎn)生很大影響，甚至對聚類的結(jié)果起到?jīng)Q定性作用；（3）可能會出現(xiàn)鏈狀的聚類結(jié)果。

3.2　基于相關(guān)性聚類的無監(jiān)督聚類

相關(guān)性聚類的基本思想：在帶權(quán)的相似性圖形上進行劃分（聚類），使得每個劃分盡可能地與結(jié)點間的相似性保持一致，最后劃分出的最佳聚類結(jié)果滿足“最大化一致性權(quán)值”原則或“最小化不一致性權(quán)值”原則[27-28]。其中，一致性權(quán)值定義為：聚簇內(nèi)部標記為“+”邊的權(quán)值和聚簇之間標記為“-”邊的權(quán)值的總和。同理，不一致性權(quán)值定義為：聚簇內(nèi)部標記為“-”邊的權(quán)值和聚簇之間標記為“+”邊的權(quán)值的總和。簡單來說，相關(guān)性聚類就是在不需要預(yù)先指定聚簇數(shù)量的情況下，盡可能地將所有記錄聚類成具有最佳數(shù)量的聚簇。

圖4　基于凝聚層次聚類的聚類

進行相關(guān)性聚類實質(zhì)上是求解整數(shù)線性規(guī)劃問題（Integer Linear Programming，ILP）。假設(shè) erirj∈{0,1}表示兩條記錄ri、rj是否位于同一個聚簇（其中1表示位于同一個聚簇）∈[0,1]表示將記錄ri、rj聚類到一起的代價，∈[0,1]表示將記錄ri、rj放置到兩個不同聚簇的代價。于是，相關(guān)性聚類的目標就是在保證滿足傳遞性性質(zhì)的約束式子?ri,rj,rk,erirj+erirk+erjrk≠2成立的條件下，盡量最小化目標函數(shù)的值。圖5顯示了一個聚類后的結(jié)果，其中發(fā)生錯誤的是三條標記為“＋”的邊，它們的總權(quán)值為5。

圖5　基于相關(guān)性聚類的聚類

基于相關(guān)性聚類的無監(jiān)督聚類具有以下優(yōu)點：不需要選擇距離閾值；不是孤立考慮記錄對之間（聚簇之間）的相似性值，而是綜合考慮多個待識別結(jié)點之間的相似性值；能夠有效消除噪聲對聚類結(jié)果產(chǎn)生的影響。其存在的不足：聚類過程本質(zhì)上是一個NP-hard問題[29]，即在費時的聚類過程后可能無法得到滿意的聚類結(jié)果。鑒于此，現(xiàn)有研究提出了許多近似的貪婪方法以對相關(guān)性聚類進行改進，例如 BEST/FIRST/VOTE[30]、PIVOT[29]和Local Search[31-32]等方法。

3.3　基于局部敏感哈希的無監(jiān)督聚類

局部敏感哈希的基本思想：在空間轉(zhuǎn)換過程中保持數(shù)據(jù)之間的相似性，對于原始空間中相似的兩個數(shù)據(jù)點，經(jīng)過相同的哈希函數(shù)映射后，這兩個數(shù)據(jù)點在映射后的空間中依然相似，即位于同一個桶中（聚簇）；反之，如果兩個數(shù)據(jù)點在原始空間中不相似，那么映射后的兩個數(shù)據(jù)點依然不相似，即位于不同的桶中[33-34]。簡單來說，如果原來的數(shù)據(jù)相似，那么哈希以后的數(shù)據(jù)同樣保持相似性。

事實上，為對數(shù)據(jù)集中記錄進行有效聚類，局部敏感哈希使用哈希函數(shù)簇來產(chǎn)生多個鍵（Keys），以便相似的記錄能被劃分到同一聚簇中[35]。值得指出的是，哈希函數(shù)的值域一般都是有限的，而被哈希的數(shù)據(jù)卻是先前無法預(yù)知的，可能會大大超過值域，這會導(dǎo)致多余一個的數(shù)據(jù)點不可避免地擁有相同的哈希值，從而使得位于同一個桶中的數(shù)據(jù)點可能彼此并不全部相似。圖6中存在一個發(fā)生沖突的桶，即桶中的數(shù)據(jù)點彼此并不相似。

圖6　基于局部敏感哈希的聚類

基于局部敏感哈希的聚類具有以下優(yōu)點：（1）能夠克服鄰居驅(qū)動的數(shù)據(jù)聚類過程中的有限可擴展性[10]；（2）能夠有效處理高維空間中的最近鄰搜索（nearest neighbor）[36]；（3）更新哈希索引結(jié)構(gòu)的代價較小；（4）查找最近鄰的時間復(fù)雜度為Ο(1)，具有極高的性能。其存在的不足：（1）需要大量存儲空間；（2）不能100%保證找到最近鄰，因為相似數(shù)據(jù)可能分布在多個桶中。

4　基于經(jīng)典算法改進的無監(jiān)督增量聚類方法

隨著大數(shù)據(jù)時代的到來和不斷發(fā)展，數(shù)據(jù)集愈發(fā)具有動態(tài)性，即數(shù)據(jù)更新速度更快，同時數(shù)據(jù)量也更大[2，37-38]。這時，上述具有接近平方級計算復(fù)雜性等局限性的無監(jiān)督聚類方法，將難以滿足動態(tài)數(shù)據(jù)集上的增量聚類需求。鑒于此，考慮到經(jīng)典算法具有的諸多優(yōu)越性，以及動態(tài)數(shù)據(jù)集本身所具有的特征，現(xiàn)有研究通過對經(jīng)典算法進行改進以滿足動態(tài)數(shù)據(jù)集上的增量聚類需求：基于凝聚層次聚類的無監(jiān)督增量聚類、基于相關(guān)性聚類的無監(jiān)督增量聚類，以及基于局部敏感哈希的無監(jiān)督增量聚類。

4.1　基于凝聚層次聚類的無監(jiān)督增量聚類

針對動態(tài)環(huán)境中新出現(xiàn)數(shù)據(jù)的聚類效率偏低問題，Widyantoro等[39]提出了增量凝聚層次聚類算法（Incremental Hierarchical Clustering，IHC），旨在構(gòu)建一個能同時滿足同質(zhì)性（homogeneity）與單調(diào)性（monotonicity）的概念層次結(jié)構(gòu)。這讓滿足同質(zhì)性的聚簇具有相似密度的對象集，滿足單調(diào)性的聚簇具有其聚簇的密度總是高于其父輩聚簇的特征。通過自底向上的方式，算法能將新出現(xiàn)數(shù)據(jù)放置于層次結(jié)構(gòu)中，之后僅對受其影響的區(qū)域進行一系列層次結(jié)構(gòu)調(diào)整。通過在不同領(lǐng)域上的實驗結(jié)果表明，算法能產(chǎn)生高質(zhì)量的聚簇層次結(jié)構(gòu)，能有效減少計算時間，同時對數(shù)據(jù)的出現(xiàn)順序不敏感。Li等[40]提出了另一增量聚類算法（Herarchical Incremental RELational clustering，HIREL），包含Incremental-Divisive和Agglomerative兩個階段，其中Incremental-Divisive階段負責自底向上遞歸地更新葉子結(jié)點，直到根結(jié)點，Agglomerative階段負責改善聚簇質(zhì)量。由于算法僅需要對數(shù)據(jù)集進行一遍掃描，并能利用代表對象（representative objects）和平衡查找樹（balanced search tree）來減少聚類過程中的距離計算量，因此它能顯著加快學習過程并改善聚類效率。Jin等[41]提出了一種適用于單鏈接層次聚類的增量分布式算法IncDiSC，它克服了統(tǒng)一框架下的數(shù)據(jù)依賴性和算法復(fù)雜性挑戰(zhàn)。該算法不僅可以擴展到大型數(shù)據(jù)集，還可以合并新數(shù)據(jù)的增量累積。

4.2　基于相關(guān)性聚類的無監(jiān)督增量聚類

針對在線數(shù)據(jù)的在線聚類問題，Claire等[42]提出了基于相關(guān)性聚類的增量相關(guān)性聚類算法（incremental correlation clustering）。該算法可執(zhí)行4個基本操作：為到來的結(jié)點v產(chǎn)生一個新的聚簇{v}；將結(jié)點v加入到現(xiàn)有的聚簇中；合并任何原先存在的聚簇；分裂原先存在的聚簇。盡管算法最終輸出的結(jié)果可能與真實聚類情形不一致，因為分類器本身可能存在錯誤，或可能根本不存在真實的最優(yōu)聚簇數(shù)量信息，但作者結(jié)合實例證明了該算法實施增量聚類時的有效性和合理性，即能最小化不一致性值或最大化一致性值。

為解決動態(tài)數(shù)據(jù)集上的聚類問題，Anja等[38]研究了融合相關(guān)性聚類的增量聚類算法，并在此基礎(chǔ)上提出了一個端到端框架end-to-end framework。它能在數(shù)據(jù)集中不斷出現(xiàn)插入、刪除和更新數(shù)據(jù)情形時，僅針對這些相關(guān)數(shù)據(jù)去增量更新數(shù)據(jù)集中的匹配結(jié)果，從而可避免每次對整個數(shù)據(jù)集重新運用聚類分析。此外，考慮到數(shù)據(jù)集中的每次動態(tài)更新可能會影響較大范圍的記錄集，因此作者繼而提出了一個貪婪算法來合并或劃分與每次更新相連的聚簇，并能在這些聚簇之間有效移動記錄。值得說明的是，由于作者綜合考慮了3種數(shù)據(jù)操作情形，因此提出的算法不僅能輕松實現(xiàn)之前研究的合并、分裂等操作，而且能充分利用每次更新中的新證據(jù)來修正原先聚類結(jié)果中存在的匹配錯誤，并且無損聚類質(zhì)量。

4.3　基于局部敏感哈希的無監(jiān)督增量聚類

針對大型文本序列數(shù)據(jù)集上新出現(xiàn)記錄的聚類問題，Costa等[43]提出了基于哈希索引結(jié)構(gòu)的最近鄰分類（nearest-neighbor classi fi cation）方法，它通過索引結(jié)構(gòu)映射任何記錄到一個索引鍵（indexing keys）集合中，并將語法上高度相似的記錄分配到相同的桶中。索引鍵由鍵產(chǎn)生程序分兩步產(chǎn)生：首先，識別記錄之間相似的記錄分量，盡管其中可能存在一定程度上的語法異構(gòu)性；然后，通過另一個最小哈希函數(shù)將先前產(chǎn)生的記錄的中間表示與它們的索引鍵關(guān)聯(lián)起來。

事實上，在兩步之間可能會使用多個最小哈希函數(shù)，一些基于最小獨立分布（min-wise independent permutations）[44-45]的局部敏感哈希函數(shù)，它們被分層結(jié)合在一起，以反映記錄及其分量之間的語法差異性，并使在線匹配更有效。重要的是，使用多個最小哈希函數(shù)有兩個目的：降低錯誤肯定和錯誤否定；直接控制用于索引任何記錄的鍵的數(shù)量，從而為整體存儲空間的緊湊性提供必要保證。值得說明的是，盡管進行增量聚類時需要依賴一個合適的基于哈希的索引結(jié)構(gòu)，但該方法不需要完全掃描原始數(shù)據(jù)集，也不需要使用代價高昂的相似性度量。

5　基于演化分析的無監(jiān)督增量聚類方法

動態(tài)數(shù)據(jù)集本質(zhì)上是一個演化的數(shù)據(jù)集，其中數(shù)據(jù)不斷頻繁產(chǎn)生或更新[17，46-47]。這種演化特性形成了一種新的數(shù)據(jù)形態(tài)——數(shù)據(jù)流?，F(xiàn)有針對數(shù)據(jù)流的聚類研究相當于是在動態(tài)數(shù)據(jù)集上進行增量聚類研究[48]。為實現(xiàn)數(shù)據(jù)流上的聚類，現(xiàn)有研究主要從兩個方面展開工作：基于數(shù)據(jù)流分析的無監(jiān)督增量聚類和基于規(guī)則演化分析的無監(jiān)督增量聚類。

5.1　基于數(shù)據(jù)流分析的無監(jiān)督增量聚類

針對給定記錄流的聚類問題，Charikar等[49]在分析一些貪婪算法的基礎(chǔ)上，提出了新的確定性隨機增量聚類算法（Deterministic and Randomized Incremental Clustering Algorithms），它的目標是在新記錄出現(xiàn)時維護具有較小直徑的聚簇。作者通過與先前算法進行對比分析證明了提出的算法具有較好的優(yōu)越性。Aggarwal等[50]認為針對大量流數(shù)據(jù)的傳統(tǒng)聚類算法大部分效率偏低，例如一些針對數(shù)據(jù)流的“單遍掃描（One-Pass）”聚類算法，盡管解決了聚類過程中的可擴展性問題，但它們通常無視數(shù)據(jù)演化問題，而且沒有解決以下兩個問題：（1）當數(shù)據(jù)隨時間快速演化時，形成聚簇的質(zhì)量較差；（2）數(shù)據(jù)流聚類算法需要更多功能以發(fā)現(xiàn)和探索數(shù)據(jù)流中不同部分上的聚簇。鑒于此，提出了CluStream算法，它將數(shù)據(jù)流看成是一個隨時間推移而不斷變化的過程，并能在這個演化環(huán)境中不同時間區(qū)間上進行聚類，這與其他試圖一次性聚類整個數(shù)據(jù)流的算法相比有著明顯的區(qū)別。實驗結(jié)果證實CluStream算法具有較高的聚簇質(zhì)量、效率，而且可擴展性也強。

為在聚類數(shù)據(jù)流時保證正確性，Whang等[37]定義了通用增量性質(zhì)（General Incremental），并據(jù)此提出了滿足通用增量性質(zhì)的增量數(shù)據(jù)算法（Incremental Data Algorithm）。由于算法能充分利用之前得到的中間聚類結(jié)果，并能一次解析數(shù)據(jù)流中的一條記錄，因此在聚類時有較好的效率和正確性。Can等[51]將操作數(shù)據(jù)集時涉及的一系列數(shù)據(jù)看成是動態(tài)數(shù)據(jù)流，并認為數(shù)據(jù)集上之前形成的聚簇需要據(jù)此進行定期更新。在明確研究背景的基礎(chǔ)上，作者提出了一個針對動態(tài)數(shù)據(jù)的增量聚類算法(C2ICM)，它通過“種子（Seed）”思想來僅對與動態(tài)數(shù)據(jù)相關(guān)的聚簇進行聚類。由于聚類過程整體上不顯著影響其他聚簇結(jié)構(gòu)，因此它能提升聚類效率。

此外，為解決數(shù)據(jù)集中新數(shù)據(jù)或新特征（記錄屬性）不斷出現(xiàn)時的聚類問題，Omar等[52]提出了“Incremetnal F-Swoosh”算法，它起初利用一些哈希表和集合來保存初始運行過程后的相應(yīng)值，之后就能在新的運行過程中避免進行一些不必要的記錄比較，尤其是在它們之間不匹配情形已知曉的情況下。事實上，通過這種方式，能避免已在初始運行過程中進行過的任何屬性值比較。

5.2　基于規(guī)則演化分析的無監(jiān)督增量聚類

隨著實際應(yīng)用中數(shù)據(jù)被更好地理解，用于聚類的匹配規(guī)則也應(yīng)作相應(yīng)演化，以便據(jù)此得到的聚類結(jié)果更能真實反映數(shù)據(jù)（流）的聚類形態(tài)。為實現(xiàn)面向數(shù)據(jù)流的基于規(guī)則演化分析的聚類，Whang等[53]提出了規(guī)則演化框架（Rule Evolution Framework），它利用物化的（Materialization）結(jié)果來減少冗余工作量，并引入兩個性質(zhì)（規(guī)則單調(diào)性、上下文無關(guān)性）來使用于聚類的匹配規(guī)則更為有效。其中，匹配規(guī)則是判定兩條記錄是否相似的基本邏輯，例如，匹配規(guī)則“如果兩條記錄的“名稱”屬性值相似，那么這兩條記錄將匹配”。

隨著更多記錄不斷出現(xiàn)（同時也被更好地理解），如果一成不變地使用上述匹配規(guī)則去對它們進行聚類，那么勢必會產(chǎn)生不正確的聚類結(jié)果，同時效率也不佳。但如果將匹配規(guī)則演化為“如果兩條記錄的“名稱”屬性值相似，并且“郵政編碼”屬性值也相似，那么這兩條記錄將匹配”，這樣就可從舊匹配規(guī)則下產(chǎn)生的聚類結(jié)果中，容易得到新匹配規(guī)則所產(chǎn)生的聚類結(jié)果，從而減少不必要的比較次數(shù)。值得指出，新匹配規(guī)則應(yīng)比舊匹配規(guī)則更嚴格。具體過程如圖7所示。

圖7　基于規(guī)則演化分析的聚類

此外，考慮到規(guī)則演化的重要性，Whang等[37]在已有研究的基礎(chǔ)上又另外提出了兩個性質(zhì)：通用增量性、順序無關(guān)性，這讓滿足這些性質(zhì)的聚類過程在速度上和精度上都得到了一定的保障。

6　結(jié)論

實體解析在數(shù)據(jù)分析、信息集成和知識庫構(gòu)建等領(lǐng)域起著至關(guān)重要的作用，并且為大數(shù)據(jù)環(huán)境下的智能推理提供了極為重要的數(shù)據(jù)質(zhì)量保障。無監(jiān)督聚類因?qū)⒔馕鲇涗浛闯墒且粋€不需要利用訓(xùn)練數(shù)據(jù)的聚簇構(gòu)建過程，而成為實體解析研究的一種重要方法。本文通過對以往研究中一些比較有代表性的無監(jiān)督聚類算法、無監(jiān)督增量聚類算法的思路進行梳理和總結(jié)，以便進一步揭示它們的策略與技巧，最終有助于從更深一層意義上認識、完善和發(fā)展實體解析。如表1，對面向?qū)嶓w解析的無監(jiān)督聚類方法在邏輯思路、性能特點、適用范圍和局限性這四方面進行了詳細比較。

展望未來，面向?qū)嶓w解析的無監(jiān)督聚類方法在準確性、可擴展性和解析效率等方面仍存在一些開放性的研究方向：

（1）深層挖掘記錄之間的鏈接關(guān)系。當前的聚類算法在聚類記錄時更多地考慮獨立的記錄對（independent pairwise）之間的相似性值，而不是記錄組內(nèi)部的協(xié)作關(guān)系[54-55]，因而導(dǎo)致較為準確的記錄之間的屬性相似性值未被包含進聚類決策過程中，從而較易出現(xiàn)記錄漏配情形。因此，研究如何推理出協(xié)作組以充分挖掘記錄之間的鏈接關(guān)系，并降低推理過程中的計算復(fù)雜性是無監(jiān)督聚類方法面臨的主要挑戰(zhàn)之一。

（2）動態(tài)調(diào)整記錄之間的聚類規(guī)則。在大多數(shù)實體解析場景中，用于實體解析的聚類規(guī)則會隨著時間的變化而演化，因為應(yīng)用程序本身會發(fā)展演化，而且用于比較記錄的專業(yè)知識也會逐步得到改善等[37，53]。因此，在記錄之間相似關(guān)系的復(fù)雜性提高的情況下，研究如何利用深厚的領(lǐng)域知識來動態(tài)構(gòu)造聚類規(guī)則以讓實體解析過程仍保持較高的聚類性能，是無監(jiān)督聚類方法面臨的主要挑戰(zhàn)之一。

（3）有效增強記錄之間的實時聚類。隨著信息技術(shù)，尤其是傳感器、通信、計算機和互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展和廣泛應(yīng)用，人們獲取數(shù)據(jù)的手段越來越多，速度也大大加快，與此同時，數(shù)據(jù)的層次和尺度更為精細，其揭示的自然現(xiàn)象和社會現(xiàn)象也更為深刻。因此，一些實體解析應(yīng)用在要求解析結(jié)果準確可靠的同時，更要求解析過程必須在規(guī)定時間內(nèi)或近乎實時完成[56-57]。例如，金融信貸領(lǐng)域數(shù)據(jù)實時分析、互聯(lián)網(wǎng)領(lǐng)域數(shù)據(jù)實時監(jiān)測、公共安全領(lǐng)域數(shù)據(jù)實時查詢和工農(nóng)業(yè)領(lǐng)域數(shù)據(jù)實時預(yù)測等。

表1　面向?qū)嶓w解析的無監(jiān)督聚類方法詳細比較

參考文獻：

[1]Naimi A I，Westreich D J.Big data：A revolution that will transform how we live，work，and think[J].Mathematics&Computer Education，2013，47（17）：181-183.

[2]孟小峰，杜治娟.大數(shù)據(jù)融合研究：問題與挑戰(zhàn)[J].計算機研究與發(fā)展，2016，53（2）：231-246.

[3]朱燦，曹健.實體解析技術(shù)綜述與展望[J].計算機科學，2015，42（3）：8-12.

[4]Dong X L，Srivastava D.Big data integration[C]//Proceedings of IEEE International Conference on Data Engineering，2013：1245-1248.

[5]Brizan D G，Tansel A U.A survey of entity resolution and record linkage methodologies[J].Communications of the IIMA，2006，6（3）：41-50.

[6]Benjelloun O，Garcia-Molina H，Menestrina D，et al.Swoosh：A generic approach to entity resolution[J].The International Journal on Very Large Data Bases，2009，18（1）：255-276.

[7]Mccallum A，Nigam K，Ungar L H.Efficient clustering of high-dimensional data sets with application to reference matching[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2000：169-178.

[8]Getoor L，Machanavajjhala A.Entity resolution：Theory，practice&open challenges[J].Proceedings of the VLDB Endowment，2012，5（12）：2018-2019.

[9]孫琛琛，申德榮，寇月，等.面向?qū)嶓w識別的聚類算法[J].軟件學報，2016，27（9）：2303-2319.

[10]Costa G，Cuzzocrea A，Manco G，et al.Data de-duplication：A review[M]//Learning Structure and Schemas from Documents.Berlin：Springer，2011：385-412.

[11]Enr Quez J，Dom Nguez-mayo F，Escalona M，et al.Entity reconciliation in big data sources：A systematic mapping study[J].Expert Systems with Applications，2017，80：14-27.

[12]莊嚴，李國良，馮建華.知識庫實體對齊技術(shù)綜述[J].計算機研究與發(fā)展，2016，53（1）：165-192.

[13]Naumann F，Herschel M.An introduction to duplicate detection[J].Synthesis Lectures on Data Management，2010，2（1）：1-87.

[14]高廣尚.面向數(shù)據(jù)演化的實體解析述評[J].情報學報，2016，35（3）：326-336.

[15]Han J，Kamber M.The Morgan Kaufmann series in data management systems，data mining：Concepts and techniques[J].Antimicrobial Agents&Chemotherapy，2015，59（3）：1435-1440.

[16]Grabmeier J，Rudolph A.Techniques of cluster algorithms in data mining[J].Data Mining and Knowledge Discovery，2002，6（4）：303-360.

[17]Batini C，Scannapieco M.Data and information quality：Dimensions，principles and techniques[M].Berlin：Springer，2016.

[18]Monge A E.Matching algorithms within a duplicate detection system[J].IEEE Data Eng Bull，2000，23（4）：14-20.

[19]Adumanusarpong K，Kingsley Arthur J.A review of data cleansing concepts achievable goals and limitations[J].International Journal of Computer Applications，2014，76（7）：19-22.

[20]Hern M A.The merge/purge problem for large databases[C]//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data，San Jose，California，USA，1995：127-138.

[21]Dez M A H，Stolfo S J.Real-world data is dirty：Data cleansing and the merge/purge problem[J].Data Min Knowl Discov，1998，2（1）：9-37.

[22]Christen P.Data matching：Concepts and techniques for record linkage，entity resolution，and duplicate detection[M].Berlin：Springer Science&Business Media，2012.

[23]Hassanzadeh O，Miller R J.Creating probabilistic databases from duplicated data[J].The International Journal on Very Large Data Bases，2009，18（5）：1141-1166.

[24]Chaudhuri S，Ganti V，Motwani R.Robust identification of fuzzy duplicates[C]//Proceedings 21st International Conference on Data Engineering，2005：865-876.

[25]Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering：A review[J].ACM Computing Surveys（CSUR），1999，31（3）：264-323.

[26]Doan A H，Halevy A，Ives Z.Principles of data integration[M].San Francisco：Morgan Kaufmann Publishers Inc，2012：459-485.

[27]Bansal N，Blum A，Chawla S.Correlation clustering[J].Machine Learning，2004，56（1/3）：89-113.

[28]Ahn K J，Cormode G，Guha S，et al.Correlation clustering in data streams[C]//Proceedings of the International Conference on Machine Learning，2015：2237-2246.

[29]Ailon N，Charikar M，Newman A.Aggregating inconsistent information：Ranking and clustering[J].Journal of the ACM（JACM），2008，55（5）：1-27.

[30]Elsner M，Charniak E.You talking to me?A corpus and algorithm for conversation disentanglement[C]//Proceedings of Meeting of ACL，2008：834-842.

[31]Gionis A，Mannila H，Tsaparas P.Clustering aggregation[J].ACM Transactions on Knowledge Discovery from Data（TKDD），2007，1（1）：4.

[32]Goder A，F(xiàn)ilkov V.Consensus clustering algorithms：Comparison and refinement[C]//Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments（ALENEX），2008：109-117.

[33]Verroios V，Garcia-molina H.Top-K entity resolution with adaptive locality-sensitive hashing[R].Stanford University，2017.

[34]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proceedings of Conference on Very Large Data Bases，1999：518-529.

[35]Kim H S，Lee D.HARRA：Fast iterative hashed record linkage for large-scale data collections[C]//Proceedings of the 13th International Conference on Extending Database Technology，2010：525-536.

[36]Har-peled S，Indyk P，Motwani R.Approximate nearest neighbor：Towards removing the curse of dimensionality[J].Theory of Computing，2012，8（1）：321-350.

[37]Whang S E，Garcia-Molina H.Incremental entity resolution on rules and data[J].The VLDB Journal，2014，23（1）：77-102.

[38]Gruenheid A，Dong X L，Srivastava D.Incremental record linkage[J].Proceedings of the VLDB Endowment，2014，7（9）：697-708.

[39]Widyantoro D H，Ioerger T R，Yen J.An incremental approach to building a cluster hierarchy[C]//Proceedings of IEEE International Conference on Data Mining，2002：705-708.

[40]Li T，Anand S S.Hirel：An incremental clustering algorithm for relational datasets[C]//Proceedings of the 8th IEEE International Conference on Data Mining，2008：887-892.

[41]Jin C，Chen Z，Hendrix W，et al.Incremental，distributed single-linkage hierarchical clustering algorithm using mapreduce[C]//Proceedings of Symposium on High Performance Computing，2015：83-92.

[42]Mathieu C，Sankur O，Schudy W.Online correlation clustering[J].Computational Statistics，2010，21（2）：211-229.

[43]Costa G，Manco G，Ortale R.An incremental clustering scheme for data de-duplication[J].Data Mining and Knowledge Discovery，2010，20（1）：152-187.

[44]Broder A Z，Charikar M，F(xiàn)rieze A M，et al.Min-wise independent permutations[C]//Proceedings of the 30th Annual ACM Symposium on Theory of Computing，1998：327-336.

[45]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proceedings of Conference on Very Large Data Bases，1999：518-529.

[46]Ilyas I F，Chu X.Trends in cleaning relational data：Consistency and deduplication[J].Foundations and Trends in Databases，2015，5（4）：281-393.

[47]Ramadan B.Indexing techniques for real-time entity resolution[D].Australian National University，2016.

[48]張長水，張見聞.演化數(shù)據(jù)的學習[J].計算機學報，2013，36（2）：310-316.

[49]Charikar M，Chekuri C，F(xiàn)eder T，et al.Incremental clustering and dynamic information retrieval[J].SIAM Journal on Computing，2004，33（6）：1417-1440.

[50]Aggarwal C C，Han J，Wang J，et al.A framework for clustering evolving data streams[C]//Proceedings of the 29th International Conference on Very Large Data Bases，2003：81-92.

[51]Can F.Incremental clustering for dynamic information processing[J].ACM Transactions on Information Systems，1993，11（2）：143-164.

[52]Benjelloun O，Garcia-Molina H，Menestrina D，et al.Swoosh：A generic approach to entity resolution[J].The VLDB Journal，2009，18（1）：255-276.

[53]Whang S E，Garcia-Molina H.Entity resolution with evolving rules[J].Proceedings of the VLDB Endowment，2010，3（1/2）：1326-1337.

[54]Bhattacharya I，Getoor L.A latent dirichlet model for unsupervised entity resolution[C]//Proceedings of the 2006 SIAM International Conference on Data Mining，2006：47-58.

[55]Zhu L，Ghasemi-Gol M，Szekely P，et al.Unsupervised entity resolution on multi-type graphs[C]//Proceedings of International Semantic Web Conference，2016：649-667.

[56]Christen P，Gayler R，Hawking D.Similarity-aware indexing for real-time entity resolution[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management，2009：1565-1568.

[57]Ramadan B，Christen P.Unsupervised blocking key selection for real-time entity resolution[C]//Proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining，2015：574-585.