高廣尚

GAO Guangshang1，2

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

2.桂林理工大學(xué) 商學(xué)院，廣西 桂林 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ù)對(duì)象）描述現(xiàn)實(shí)世界同一實(shí)體。由于這些記錄的某些對(duì)應(yīng)屬性的值之間存在細(xì)微差別，因而它們被稱為近似重復(fù)記錄（approximate duplicate record）[3-4]。而演化性體現(xiàn)在，屬性值會(huì)以相對(duì)較快的速度產(chǎn)生細(xì)微變化。從聚類角度來看，實(shí)體解析（Entity Resolution，ER）定義為：通過合適的相似性函數(shù)以盡可能快地將描述現(xiàn)實(shí)世界同一實(shí)體的所有近似重復(fù)記錄聚類到同一個(gè)聚簇中（或劃分到同一個(gè)組中），使得每個(gè)聚簇表示不同的實(shí)體[5-9]。目前從整體上來看，實(shí)體解析分為兩大類：成對(duì)實(shí)體解析（Pairwise ER）和基于聚類的實(shí)體解析（Clustering-based ER）[8]。其中，成對(duì)實(shí)體解析需要對(duì)數(shù)據(jù)集中所有記錄進(jìn)行兩兩比較，涉及的時(shí)間復(fù)雜度為Ο(n2)，而基于聚類的實(shí)體解析則無需進(jìn)行兩兩比較，因此涉及的時(shí)間復(fù)雜度可能會(huì)遠(yuǎn)小于Ο(n2)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于中心結(jié)點(diǎn)的聚類方法可能會(huì)產(chǎn)生比基于圖分割的聚類方法更多的聚簇，因?yàn)樗粚⒛切┡c聚簇中心的記錄相似的記錄放入同一個(gè)聚簇。

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

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

緊湊集內(nèi)部的記錄對(duì)之間的距離小于任何非緊湊集內(nèi)的記錄對(duì)之間的距離，表示為：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顯示了一個(gè)緊湊集，包含結(jié)點(diǎn)r1、r2和r3，以及作為邊的權(quán)值的距離（等于1減去相似性值），其中r1的鄰居集N(r1)=p·nn(r1)=0.1×p=0.1p，假定它包含結(jié)點(diǎn)r4和r5。

圖3　基于緊湊集的聚類

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

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

基于特定類型的無監(jiān)督聚類具有一定的局限性：算法可擴(kuò)展性不強(qiáng)，算法理論基礎(chǔ)不完備和算法性能不穩(wěn)定等；相比之下，基于經(jīng)典算法的無監(jiān)督聚類卻具有諸多優(yōu)越性：理論基礎(chǔ)堅(jiān)實(shí)，算法實(shí)現(xiàn)簡單，可擴(kuò)展性較好和可處理高維數(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個(gè)記錄對(duì)象和N×N的距離矩陣的情況下，從每個(gè)對(duì)象作為個(gè)體聚簇開始，每一步合并兩個(gè)最接近的聚簇[25-26]。凝聚層次聚類涉及兩個(gè)重要參數(shù)：相似性度量方法和閾值，前者通過歐式距離來判斷兩個(gè)聚簇之間的相似度，后者用作聚類迭代過程的終止條件，即當(dāng)最近的兩個(gè)聚簇的距離大于閾值時(shí)，則認(rèn)為迭代可以終止。圖4（a）顯示了迭代聚類過程，最終返回C1、C3和r6（單獨(dú)作為一個(gè)聚簇）3個(gè)聚簇（假定滿足終止條件）；圖4（b）相應(yīng)地顯示了這一自底向上的迭代聚類過程，同時(shí)也說明了凝聚層次聚類具有“層次”特性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6　結(jié)論

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

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

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

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

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

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

參考文獻(xià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].計(jì)算機(jī)研究與發(fā)展，2016，53（2）：231-246.

[3]朱燦，曹健.實(shí)體解析技術(shù)綜述與展望[J].計(jì)算機(jī)科學(xué)，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識(shí)別的聚類算法[J].軟件學(xué)報(bào)，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]莊嚴(yán)，李國良，馮建華.知識(shí)庫實(shí)體對(duì)齊技術(shù)綜述[J].計(jì)算機(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ù)演化的實(shí)體解析述評(píng)[J].情報(bào)學(xué)報(bào)，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ù)的學(xué)習(xí)[J].計(jì)算機(jī)學(xué)報(bào)，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.