亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        面向?qū)嶓w解析的無監(jiān)督聚類方法綜述

        2018-04-08 05:46:23高廣尚
        關(guān)鍵詞:哈希結(jié)點(diǎn)相似性

        高廣尚

        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ù)碛邢嗤墓V?,從而使得位于同一個(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.

        猜你喜歡
        哈希結(jié)點(diǎn)相似性
        一類上三角算子矩陣的相似性與酉相似性
        淺析當(dāng)代中西方繪畫的相似性
        Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
        低滲透黏土中氯離子彌散作用離心模擬相似性
        基于OpenCV與均值哈希算法的人臉相似識(shí)別系統(tǒng)
        基于維度分解的哈希多維快速流分類算法
        基于同態(tài)哈希函數(shù)的云數(shù)據(jù)完整性驗(yàn)證算法
        基于Raspberry PI為結(jié)點(diǎn)的天氣云測量網(wǎng)絡(luò)實(shí)現(xiàn)
        一種基于Bigram二級(jí)哈希的中文索引結(jié)構(gòu)
        V4國家經(jīng)濟(jì)的相似性與差異性
        久久99热只有频精品8国语| 亚洲av美女在线播放啊| 狠狠躁夜夜躁人人爽天天不卡 | 亚洲国产精品久久久久秋霞小说| 亚洲av成人无码网站大全| 任你躁国产自任一区二区三区| 91亚洲国产成人久久精品网站| 亚洲成人av在线第一页| 在线看片免费人成视频久网下载| 欧美在线专区| 日韩av中文字幕亚洲天| 日韩精品在线免费视频| 人妻丰满熟妇av无码区不卡| 亚洲欧美日韩国产色另类| 国産精品久久久久久久| 亚洲AV毛片无码成人区httP| 玩弄丝袜美腿超短裙校花| 中文字幕av久久亚洲精品| 性激烈的欧美三级视频| 国产肉体XXXX裸体784大胆| 亚洲国产综合精品一区最新| 成人片黄网站a毛片免费| 欧美人妻精品一区二区三区 | 人妻av有码中文字幕| 国产精一品亚洲二区在线播放 | 国产精品国产三级国产一地| 在线观看视频亚洲一区二区三区| 18禁免费无码无遮挡不卡网站| 午夜成人理论无码电影在线播放| 无码一区二区三区网站| 美女视频黄a视频全免费网站色| 99精品国产丝袜在线拍国语| 国产黄色免费网站| 亚洲男女视频一区二区| 女人的天堂av免费看| 九一精品少妇一区二区三区 | 少妇做爰免费视频网站| 国产一区二区三区韩国| 蜜桃高清视频在线看免费1| 国产欧美日韩精品专区| 在线欧美精品二区三区|