面向實體解析的無監督聚類方法綜述

高廣尚

GAO Guangshang1，2

1.桂林理工大學 現代企業管理研究中心，廣西 桂林 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　引言

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

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

2　基于特定類型的無監督聚類方法

針對特定類型的分析有助于引導無監督聚類過程。現有研究中基于特定類型的無監督聚類方法主要分為4種：基于優先隊列的無監督聚類、基于圖分割的無監督聚類、基于中心結點的無監督聚類和基于緊湊集的無監督聚類。

2.1　基于優先隊列的無監督聚類

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

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

2.2　基于圖分割的無監督聚類

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

圖1　基于優先隊列的聚類

圖2　基于比較結果構成的相似性圖形

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

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

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

2.3　基于中心結點的無監督聚類

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

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

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

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

2.4　基于緊湊集的無監督聚類

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

緊湊集內部的記錄對之間的距離小于任何非緊湊集內的記錄對之間的距離，表示為：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)中的記錄數量低于某一常數閾值，那么ri的鄰居就被定義為稀疏的。如圖3顯示了一個緊湊集，包含結點r1、r2和r3，以及作為邊的權值的距離（等于1減去相似性值），其中r1的鄰居集N(r1)=p·nn(r1)=0.1×p=0.1p，假定它包含結點r4和r5。

圖3　基于緊湊集的聚類

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

3　基于經典算法的無監督聚類方法

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

3.1　基于凝聚層次聚類的無監督聚類

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

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

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

3.2　基于相關性聚類的無監督聚類

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

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

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

圖5　基于相關性聚類的聚類

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

3.3　基于局部敏感哈希的無監督聚類

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

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

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

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

4　基于經典算法改進的無監督增量聚類方法

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

4.1　基于凝聚層次聚類的無監督增量聚類

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

4.2　基于相關性聚類的無監督增量聚類

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

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

4.3　基于局部敏感哈希的無監督增量聚類

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

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

5　基于演化分析的無監督增量聚類方法

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

5.1　基于數據流分析的無監督增量聚類

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

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

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

5.2　基于規則演化分析的無監督增量聚類

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

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

圖7　基于規則演化分析的聚類

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

6　結論

實體解析在數據分析、信息集成和知識庫構建等領域起著至關重要的作用，并且為大數據環境下的智能推理提供了極為重要的數據質量保障。無監督聚類因將解析記錄看成是一個不需要利用訓練數據的聚簇構建過程，而成為實體解析研究的一種重要方法。本文通過對以往研究中一些比較有代表性的無監督聚類算法、無監督增量聚類算法的思路進行梳理和總結，以便進一步揭示它們的策略與技巧，最終有助于從更深一層意義上認識、完善和發展實體解析。如表1，對面向實體解析的無監督聚類方法在邏輯思路、性能特點、適用范圍和局限性這四方面進行了詳細比較。

展望未來，面向實體解析的無監督聚類方法在準確性、可擴展性和解析效率等方面仍存在一些開放性的研究方向：

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

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

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

表1　面向實體解析的無監督聚類方法詳細比較

參考文獻：

[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]孟小峰，杜治娟.大數據融合研究：問題與挑戰[J].計算機研究與發展，2016，53（2）：231-246.

[3]朱燦，曹健.實體解析技術綜述與展望[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]孫琛琛，申德榮，寇月，等.面向實體識別的聚類算法[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]莊嚴，李國良，馮建華.知識庫實體對齊技術綜述[J].計算機研究與發展，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]高廣尚.面向數據演化的實體解析述評[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，Flynn 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，Filkov 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，Frieze 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]張長水，張見聞.演化數據的學習[J].計算機學報，2013，36（2）：310-316.

[49]Charikar M，Chekuri C，Feder 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.