一種基于二分圖最優(yōu)匹配的重復(fù)記錄檢測算法

1、一種基于二分圖最優(yōu)匹配的重復(fù)記錄檢測算法計算機科學(xué)與技術(shù)學(xué)院：李默涵 指導(dǎo)教師：王宏志摘 要： 信息集成系統(tǒng)中存在重復(fù)記錄，重復(fù)記錄的存在為數(shù)據(jù)處理和分析帶來了困難。重復(fù)記錄檢測已經(jīng)成為當(dāng)前數(shù)據(jù)庫研究中的熱點問題之一。目前的方法主要集中在計算具有同樣數(shù)據(jù)類型屬性的相似性上，而現(xiàn)實系統(tǒng)中存在大量具有不同數(shù)據(jù)類型、不同模式的記錄。本文針對具有多種類型不同模式的數(shù)據(jù)的重復(fù)記錄檢測問題，提出了一種基于二分圖的最優(yōu)匹配的記錄相似度計算方法，并基于這種記錄相似性提出了重復(fù)記錄檢測算法。理論分析和實驗結(jié)果都表明了方法的正確性和有效性。關(guān)鍵詞：信息集成；重復(fù)檢測；記錄相似度；異構(gòu)記錄Abstract： In

2、information integration systems, duplicate records brings challenges for data processing and analysis. The duplicate record detection has become one of the hot issues in database research. Most current methods focus on computing the similarity of the data with same data type. However, there are a la

3、rge number of records with different data type and schema in real system. In this paper, we focus on duplicate records which have different schemas with multiple data types. A method based on optimal matching of bipartite graph is proposed to compute the similarity of the records. Further more, an a

4、lgorithm based on this kind of similarity is proposed to detect the duplicate records. Theoretical analysis and experimental results show that the method proposed in this paper is correct and effective.Keywords： Information integration; Duplicate record detection; Record similarity1 引 言隨著信息技術(shù)的發(fā)展，信息集

5、成系統(tǒng)在許多領(lǐng)域得到了廣泛的應(yīng)用。在信息集成系統(tǒng)中通常存在大量表達(dá)相同含義的記錄，稱為相似重復(fù)記錄。直接提交包含重復(fù)記錄的數(shù)據(jù)會造成數(shù)據(jù)的冗余，從而造成網(wǎng)絡(luò)帶寬、存儲空間等資源的浪費，還會使用戶從系統(tǒng)中查詢到無用的重復(fù)結(jié)果，降低系統(tǒng)的可用性。鑒于重復(fù)記錄帶來的危害，需要對其進(jìn)行檢測，并將檢測出的重復(fù)記錄聚為一類，作為一個單元進(jìn)行處理。重復(fù)記錄的檢測工作帶來了技術(shù)上的挑戰(zhàn)。主要體現(xiàn)在兩個方面：一方面，來自于不同數(shù)據(jù)庫中相同含義的數(shù)據(jù)存在異構(gòu)表達(dá)，表達(dá)的異構(gòu)可能體現(xiàn)在以下三個方面：1）數(shù)據(jù)物理存儲順序差異，即兩條相同記錄的同一屬性可能存儲在記錄的不同位置，例如表達(dá)同一個學(xué)生的姓名和國籍的信息對應(yīng)著

6、不同記錄(J.Smith，England)和(England, J.Smith)。2）數(shù)據(jù)丟失，即由于模式的不同，有的屬性不同時存在于所有數(shù)據(jù)庫；3）個別字符的錄入差異，即同樣的屬性取值可能在錄入時存在誤差。另一方面，數(shù)據(jù)源的模式可能不一致，甚至存在數(shù)據(jù)源模式未知的情況，這使得人們在檢測重復(fù)記錄時很難精確地將兩條記錄的表達(dá)同一含義的屬性對應(yīng)起來。當(dāng)前的計算記錄相似度的方法主要是將整條記錄當(dāng)做是一個整體，然后通過編輯距離等基于字符串比較的屬性相似度計算方法得出記錄的相似度1。但是這種方法在處理數(shù)據(jù)的異構(gòu)表達(dá)時存在著一些問題。首先，現(xiàn)有的方法并不能有效的處理數(shù)據(jù)物理存儲順序差異，例如，記錄R1(0

7、07, J.Smith, England)和R2(007, England, J.Smith)是兩條完全相同的記錄，但是如果將每條記錄都當(dāng)作一個整體計算字符串相似度（如編輯距離），則會低估兩條記錄的相似度。其次，個別字符不同可能導(dǎo)致整條記錄意義的改變，比如記錄（J.Smith, M）和（J.Smith, F），當(dāng)M和F表示性別時，兩條記錄相似性很高，但表示的是兩個重名但是不同性別的學(xué)生的信息，這時傳統(tǒng)方法又會高估記錄的相似度。為了彌補傳統(tǒng)的方法上述缺點，本文以關(guān)系數(shù)據(jù)庫為基礎(chǔ)，提出了快速有效的重復(fù)記錄檢測方法。本文的貢獻(xiàn)可以歸納為以下3點：1）研究了在存在異構(gòu)模式的信息集成系統(tǒng)中進(jìn)行重復(fù)記錄檢

8、測的問題；2)提出了一種考慮到不同模式、不同類型的記錄相似度定義，能夠有效表達(dá)具有異構(gòu)模式記錄的相似性；3）在本文定義的相似度基礎(chǔ)上，提出了一種適用于大規(guī)模數(shù)據(jù)的重復(fù)記錄檢測算法；4）本文從理論和實驗兩方面驗證了本文提出方法的正確性和有效性。本文組織結(jié)構(gòu)如下。第2節(jié)介紹重復(fù)記錄檢測的相關(guān)工作。第3節(jié)對本文研究的重復(fù)記錄檢測問題進(jìn)行定義。第4節(jié)定義屬性和記錄的相似度。第5節(jié)描述本文提出的重復(fù)記錄檢測方法。第6節(jié)通過實驗驗證本文提出的方法。最后給出結(jié)論。2 相關(guān)工作由于其重要性，當(dāng)前有一系列檢測重復(fù)記錄檢測技術(shù)提出。1是對早期重復(fù)記錄檢測工作的綜述。文5用記錄的相關(guān)字段構(gòu)成鍵，按照鍵對相關(guān)字段進(jìn)行

9、排序，并使用滑動窗口的方法進(jìn)行相似重復(fù)記錄檢測；文6把每條記錄看成一個字符串，對記錄進(jìn)行排序，然后使用固定大小的優(yōu)先隊列來順序掃描所有的已排序的記錄，并將它們聚類；文7給每條記錄賦予一個N-gram值，將記錄排序后使用優(yōu)先隊列對記錄聚類；文8將每個字段值分解成多個tokens，對tokens進(jìn)行排序，進(jìn)而對記錄進(jìn)行排序，使用滑動窗的方法來比較臨近范圍的記錄。這些工作都未考慮記錄的模式異構(gòu)，不適用于處理具有異構(gòu)模式的信息集成系統(tǒng)中的重復(fù)記錄檢測。3 問題定義信息集成系統(tǒng)中存在來自多個數(shù)據(jù)源的數(shù)據(jù)，不同記錄可能具有不同模式和信息表示方式。例如兩條來自不同的關(guān)系數(shù)據(jù)庫的本科學(xué)生信息記錄：R1（007

10、，John_Smith，19，England）和R2（007，J.Smith， 19）。R1的模式是Student（id，name，age，nationality），R2的模式是Undergraduate（id，name， age）。R1與R2是重復(fù)記錄，但它們在多方面存在著不同：它們所在表名分別是Student和Undergraduate；姓名John_Smith在R2中縮寫為J.Smith；R2中沒有記錄學(xué)生的國籍信息。此外，對于某些數(shù)據(jù)源，我們僅能獲得記錄的內(nèi)容，卻無法獲取相應(yīng)的模式信息。在上述情況下，無法利用簡單的并、交、差等運算歸類重復(fù)記錄，而需要對記錄的內(nèi)容加以分析，根據(jù)內(nèi)容的相似

11、程度，確定其是否重復(fù)。并且把重復(fù)的記錄劃歸一類。本文一共解決3個問題：1)根據(jù)內(nèi)容定義屬性的相似度；2)根據(jù)屬性的相似度定義記錄的相似度；3)根據(jù)記錄相似度對原始數(shù)據(jù)集合進(jìn)行重復(fù)檢測。4 相似度的確定本節(jié)介紹屬性和記錄相似度的定義及計算方法。4.1節(jié)定義了屬性相似度。4.2節(jié)提出基于二分圖最優(yōu)匹配的記錄相似度定義和計算記錄相似度的算法，并給出算法的復(fù)雜性分析。4.1 屬性的相似度由于編輯距離2廣泛適用于各種類型的屬性，我們以編輯距離為基礎(chǔ)定義兩個屬性A1和A2的相似度。在此定義中，編輯距離越大的屬性其相似性越小，并且屬性的編輯距離被映射到了0,1區(qū)間，從而更清晰地表示記錄相似的程度。相似度定義

12、如下：將A1和A2看做字符串，其編輯距離為d(A1,A2)、字符串長度分別為len(A1)和len(A2)，則其相似度屬性相似度可以利用2中方法計算得的字符串編輯距離求得。時間復(fù)雜性為O(len(A1)len(A2)。4.2 記錄的相似度基于4.1中定義的屬性相似性，本節(jié)提出記錄的相似性及其高效計算方法?？紤]到數(shù)據(jù)的異構(gòu)表達(dá)，在定義記錄相似性時需要首先匹配記錄中相同或相似的屬性，利用屬性的相似度定義記錄的相似度?；谶@種考慮，提出了一種基于二分圖最優(yōu)匹配的相似度定義，方法如下。根據(jù)待比較兩條記錄Ri和Rj生成一個完全有權(quán)二分圖B=(V1V2, E, W)，其中V1中每個節(jié)點u代表的Ri的一個屬

13、性ui，V2中每個節(jié)點v代表的Rj的一個屬性vj，E=V1×V2, 權(quán)函數(shù)W:E0,1定義為W(u,v)=Sim(ui, vj), 其中Sim(ui, vj)是4.1中定義的屬性相似性。M=(V,E)是B的最優(yōu)匹配，其中VV1V2，EE。則記錄R1和R2的相似度定義為：其中m, n分別代表R1和R2的屬性個數(shù)。上述方法定義相似度在0,1區(qū)間內(nèi)，使得具有各種長度記錄間相似性在同一區(qū)間內(nèi)，從而得以比較，并且有助于用戶確定所需要的相似度閾值。計算記錄的相似度的關(guān)鍵是求二分圖的最優(yōu)匹配。KuhnMunkras算法3,4（KM算法）是一種求二分圖的最優(yōu)完備匹配的有效算法，通過給屬性個數(shù)較少的元

14、組添加幾個虛擬屬性并讓和其鄰接的所有邊的權(quán)值都為0，KM算法可以用來計算記錄相似性。下面給出算法的具體流程如算法1和算法2所示。算法1描述了由兩條記錄構(gòu)造完全二分圖的算法。算法2描述了由式(2)計算出記錄R1和R2的相似度的方法。其中attribute_similarity(R1i,R2j )返回R1第i個屬性和R2第j個屬性的相似度。optimal_match(B,w,m)使用KM算法求出二分圖的最優(yōu)匹配，返回最優(yōu)匹配中所有邊權(quán)值之和，其中B表示完全二分圖，w是B的權(quán)值矩陣，m是w的階。算法1：兩條記錄中抽象出帶權(quán)的完全二分圖record_to_ bipartite(R1, R2)/ R1,

15、 R2是兩條記錄1.mR1的屬性個數(shù)2.nR2的屬性個數(shù)3.Foreach i, jdo4.wi, j 0/ w 是二分圖的權(quán)值矩陣5.Foreach i, jdo6./Ri 是R的第i個屬性7. wi,jattribute_similarity(R1i, R2j )8. X R1的所有屬性, Y R2的所有屬性9. if m < n then 向X中加入n-m 個點10.else 向Y中加入m-n個點11. E X中的每個點到Y(jié)中所有點均有邊12. B (XY, E)13. return （w , B, maxm, n）算法2：計算記錄相似度record_similarity (R1,

16、 R2)1. (w,B,m)record_to_bipartite (R1, R2)2. sum optimal_match(B,w,m)3. Sim(R1,R2) sum/m4. return Sim(R1, R2) 圖4-1 兩條記錄生成的權(quán)值矩陣及二分圖 圖4-2 對原始記錄集合進(jìn)行劃分例如記錄R1(007, John_Smith, England)和R2(008, England, Jane_Smith)，其二分圖權(quán)值矩陣及完全有權(quán)二分圖如圖4-1所示，二分圖中虛線表示的邊權(quán)值都為0。求出最優(yōu)匹配，得到兩條記錄的相似度為0.79。record_to_bipartite(R1, R2)的

17、時間復(fù)雜度為O(m2max|A1|A2|)，其中m是兩條記錄中屬性較多的記錄的屬性數(shù)，A1是R1的屬性，A2是R2的屬性。KM算法的時間復(fù)雜度為O(m4)。所以算法的時間復(fù)雜度為O(maxm2max|A1|A2|, m4)。算法中最大的空間開銷為權(quán)值矩陣的開銷，空間復(fù)雜度為O(m2)。實際數(shù)據(jù)中，記錄中不同屬性的重要性不同，如主屬性要比非主屬性重要?？紤]到這個特點，可以給不同的屬性賦予不同的屬性權(quán)值，在計算二分圖邊權(quán)值時將屬性權(quán)值作為系數(shù)。設(shè)在記錄Ri中，屬性v的權(quán)值為tv, 在記錄Rj中屬性u的權(quán)值tu, 則考慮到屬性權(quán)重的代價W(v, u)=W(v, u)×tv×tu。

18、由于僅有邊的權(quán)發(fā)生改變，屬性權(quán)重的記錄相似性計算方法和原來的方法完全相同，這種方法可以提高相似度計算的準(zhǔn)確性。其中屬性的重要性可以由用戶指定。5 重復(fù)記錄的檢測算法本節(jié)提出基于第4節(jié)中記錄相似度的重復(fù)記錄檢測算法以及實現(xiàn)策略。5.1節(jié)對重復(fù)記錄檢測進(jìn)行定義。5.2節(jié)提出了集合劃分的算法，并在章節(jié)的末尾對算法進(jìn)行優(yōu)化。5.1 重復(fù)記錄的定義在一個記錄集合中，不能簡單根據(jù)記錄相似性定義記錄重復(fù)。考慮下面情況，對于記錄R1(23, England, 007, J.Smith)、R2(007, J.Smith)和R3(23, England)，R1和R2、R1和R3的相似度都較高，但是R2和R3完全不

19、同。這種情況下，如果簡單根據(jù)相似性將R1和R2看成重復(fù)記錄，R1和R3看成重復(fù)記錄，則R2和R3也應(yīng)當(dāng)是重復(fù)記錄，然而他們并不相似，出現(xiàn)了矛盾。為了避免這種矛盾，只有一個任兩條記錄的相似度都足夠大的聚類中的記錄才可以看成是重復(fù)對象。于是，數(shù)據(jù)集合的重復(fù)檢測可以轉(zhuǎn)化為這樣的問題：將原始記錄集合R劃分成若干不相交的子集（聚類），每個子集中任兩條記錄都具有較大的相似度。我們給出問題的形式化定義：定義1：給定一個記錄集合R=R1,R2,Rm。R上的重復(fù)檢測定義為：由用戶給定一個相似度閾值。將R劃分成若干不相交的子集合S1,S2,Sn，滿足如下3條性質(zhì)：1)對于任意子集Si，其中每兩條記錄的相似度都不小

20、于；2)對于 Si,Sj，ij，有SiSj=；3)對于 Si,Sj，ij，有SiSj不滿足條件1）。5.2 記錄集合R的劃分算法算法的基本思想是順序掃描記錄集合，每次將掃描到的記錄歸到可能的類中，如果該記錄不屬于當(dāng)前的任何類，則建立一個新類。算法使用棧保存已經(jīng)生成的類，棧中的每個元素對應(yīng)一個桶，存儲該類中的記錄。算法的流程如圖4-2所示，算法的偽代碼在算法3中：初始情況下棧為空（行1），算法每次從記錄集合獲得一條記錄（行2），并從棧頂開始向下搜索與當(dāng)前記錄滿足相似度要求的棧內(nèi)記錄（行3-6），每找到一條滿足條件的棧內(nèi)記錄，則將當(dāng)前記錄與找到的棧中記錄對應(yīng)的桶內(nèi)的每條記錄比較，如果當(dāng)前記錄和桶中

21、的所有記錄相似度都滿足要求，則當(dāng)前記錄投入桶，并將相應(yīng)的棧內(nèi)記錄移至棧頂（行7-10）。否則繼續(xù)在棧內(nèi)向下搜索滿足條件的記錄（行11）。如果在搜索完棧內(nèi)的所有記錄后，當(dāng)前記錄仍沒有被投入桶，則將當(dāng)前記錄入棧，置于棧頂（行13）。算法3：對原始記錄集合R進(jìn)行劃分Divide_R(R, )1.stack 2.For each Rk R do3. nowstack.top4. Ristacknow5. do6. if Sim(Rk , Ri) >= then7. if 對RjRibucket有Sim(Rk, Ri) >=8.then Rk投入Rj對應(yīng)的桶;9.將stacknow移至棧頂1

22、0.break11. else now now112.while now = -113. if now=-1 then stack.push(Ri)14. return （stack, buckets）算法結(jié)束后，每條棧內(nèi)記錄（稱為標(biāo)志性記錄）及其對應(yīng)桶中記錄劃歸一個集合，所有這樣的集合形成對R的一個滿足條件的劃分。我們?nèi)砸约蟁=R1(007, John_Smith, M, 19, England)，R2(008, Jane_Smith, F, 18, England)，R3(007, J.Smith, M, 19)，R4(007, J.Smith, M, 18)為例說明劃分算法的過程。設(shè)=

23、0.6，過程如下：棧初始為空；當(dāng)前記錄為R1，在棧中尋找與R1相似度不小于0.6的記錄，由于棧為空，所以找不到滿足條件的記錄，將R1壓入棧，建立新類，置R1對應(yīng)的桶為空；當(dāng)前記錄為R2，在棧中尋找滿足相似度要求的記錄，此時棧中為R1，和棧頂?shù)腞1比較，不滿足，繼續(xù)在棧中向下尋找，棧中僅有一條記錄，找不到滿足條件的記錄，將R2壓入棧，建立新類，置R2對應(yīng)的桶為空；當(dāng)前記錄為R3，在棧中尋找滿足相似度要求的記錄，此時棧中為R2 , R1，和棧頂?shù)腞2比較，不滿足相似度要求，繼續(xù)在棧中向下尋找，棧中下一條記錄為R1，R3和R1比較相似度，滿足相似度要求，將R3與R1對應(yīng)的桶中記錄比較，此時R1對應(yīng)的

24、桶為空，所以R3直接被投入桶，將R1移至棧頂；當(dāng)前記錄為R4，在棧中尋找滿足相似度要求的記錄，此時棧中元素為R1 , R2，和棧頂?shù)腞1比較，滿足相似度要求，將R4與R1對應(yīng)的桶中記錄比較，此時R1對應(yīng)的桶中為R3，R4和R3比較，也滿足相似度要求，所以R4被投入R1對應(yīng)的桶，此時R1已經(jīng)在棧頂，無需進(jìn)一步操作；記錄集合中的所有記錄均被處理，最后的劃分結(jié)果是兩個集合，分別為R2和R1 , R3 , R4。算法的正確性基于以下定理：定理1：算法3可以從記錄集合得到滿足定義1的劃分。證明：根據(jù)算法中將元素加入類的條件，劃分結(jié)果顯然滿足定義1的性質(zhì)1）和2）?，F(xiàn)在用反證法證明滿足性質(zhì)3）。如果算法得

25、到的結(jié)果不滿足性質(zhì)3），則存在Si,Sj，ij，SiSj滿足條件1），不妨設(shè)Si的標(biāo)志性記錄先于Sj的標(biāo)志性記錄入棧，那么Sj的標(biāo)志性記錄在入棧時一定會被投入Si對應(yīng)的桶，從而Si和Sj對應(yīng)相同的桶，而由ij 可以推出Si和Sj有不同的桶，矛盾。所以性質(zhì)3）也一定滿足。正確性得證。（證畢）注意到這個劃分可能不唯一，在現(xiàn)實中這是合理的，考慮記錄集合R1(23, England, 007, J.Smith)、R2(007, J.Smith)和R3(23, England)，當(dāng)用戶定義=0.5時，此集合上的劃分就不唯一，R1既可以劃歸到R2所在的集合又可以劃歸到R3所在的集合。對R進(jìn)行劃分時，最壞情

26、況是劃分結(jié)果中每條記錄單獨屬于一個分類，或者所有記錄屬于同一分類，在這兩種情況下需要O(|R|2)時間。但是，通常情況所需的時間要比最壞情況少的多，因為如果當(dāng)前記錄和棧內(nèi)的標(biāo)志性記錄的相似度小于時是不需要和相應(yīng)桶內(nèi)的記錄比較的，所以，通常情況下，記錄只需要在棧內(nèi)進(jìn)行很少的比較就可以投入正確的桶。算法空間復(fù)雜度為O(|R|)。從上面的分析可以看出，算法的瓶頸在于，每條記錄入桶時都要經(jīng)過多次相似度比較。因此對算法效率的優(yōu)化主要著眼于減少記錄相似度的比較次數(shù)。精確分類在數(shù)據(jù)量不大的情況下可以達(dá)到不錯的效果，但當(dāng)數(shù)據(jù)量非常大時，執(zhí)行效率受到影響。在這種情況下，我們可以以精度換取效率，可以通過多遍分類，

27、逐步細(xì)化的策略來提高速度?；舅枷胧牵合葘υM進(jìn)行一遍掃描，將其粗糙的分為若干類，再在這些粗糙分類中進(jìn)行精確的分類。這樣，每次精確分類只需要在這些粗糙分類中進(jìn)行，使得精確分類要判定的元組數(shù)目大大減少，從而提高算法的運行速度。具體的做法類似于算法3。設(shè)當(dāng)前正在檢測的記錄記為Rk，從棧頂開始，依次和棧內(nèi)標(biāo)志性記錄（記為Rs）比較相似度，若Rk和Rs的相似度不小于，則投入Rs對應(yīng)的桶。這樣一遍掃描后，桶內(nèi)記錄形成一個粗糙分類。如果得到的粗糙分類仍很大，則在已有粗糙分類基礎(chǔ)上再進(jìn)行多遍粗糙分類。事實上，在記錄集合里的記錄兩兩相似度比較大的情況下，也可以僅使用粗糙分類來實現(xiàn)快速分類。逐步細(xì)化分類的缺點是

28、最終結(jié)果可能會不滿足定義1中的性質(zhì)3）。為了彌補這一缺點，我們可以把標(biāo)志性記錄相似度高的類關(guān)聯(lián)起來，如果用戶在當(dāng)前分類中得不到想要的記錄，則可以在與其相關(guān)聯(lián)的分類中尋找需要的記錄。此外，重復(fù)記錄的某些屬性(如主鍵)相似的可能性要比其他屬性大。從不同的數(shù)據(jù)源收集到哪些屬性更有可能相似，再根據(jù)這些屬性對原始記錄集合進(jìn)行排序，在算法執(zhí)行時可以減少很多的無用比較。6 實驗分析本節(jié)對第4節(jié)和第5節(jié)描述的算法進(jìn)行實驗，驗證其效率和有效性。6.1說明了實驗配置。6.2給出記錄相似度計算的實驗結(jié)果及其分析。6.3給出了原始記錄集合R上重復(fù)檢測的實驗結(jié)果及其分析。6.1 實驗配置實驗采用的硬件環(huán)境為AMD Se

29、mpron 3000+，內(nèi)存512M，操作系統(tǒng)為Windows XP，程序代碼用Visual C+實現(xiàn)。我們采用自己編寫數(shù)據(jù)生成工具和噪聲引入工具來產(chǎn)生實驗數(shù)據(jù)。兩條重復(fù)的記錄可能存在的差異有：1）數(shù)據(jù)物理存儲順序差異；2）數(shù)據(jù)丟失；3）個別字符的錄入差異。我們針對這三種差別定義了三種修改操作：改變屬性的物理存儲順序、隨機刪除若干屬性以及隨機改變記錄中的若干字符。我們用數(shù)據(jù)生成工具來產(chǎn)生基準(zhǔn)記錄，對于一條給定的基準(zhǔn)記錄，使用上述三種修改操作引入噪聲，生成重復(fù)記錄。6.2 記錄相似度計算實驗結(jié)果及其分析這一節(jié)我們通過實驗比較本文的記錄相似度計算方法和傳統(tǒng)的記錄相似度計算方法的準(zhǔn)確度?；诙謭D匹

30、配的方法簡記為bi_sim，傳統(tǒng)的將記錄看做是一個屬性的記錄相似度比較方法簡記為ed_sim。實驗使用噪聲引入工具對每條記錄引入不同的數(shù)據(jù)差異，生成100條重復(fù)記錄，分別使用bi_sim和ed_sim來計算每兩條記錄的相似度，得出平均相似度。實驗結(jié)果如表1所示：表6-1：不同數(shù)據(jù)集合上兩種方法求得的平均相似度數(shù)據(jù)編號存在的差別平均相似度bi_simed_sim11）1.00000.779121）和2）0.86000.661531）、2）和3）0.69700.6362由以上數(shù)據(jù)可以看出，在僅存在物理存儲順序差異時，我們的方法可以準(zhǔn)確的計算出1.0000的相似度，傳統(tǒng)的方法僅0.7791，高出傳統(tǒng)

31、方法0.2209；在物理存儲順序差異的基礎(chǔ)上隨機增加了至多為50%的數(shù)據(jù)丟失差異之后，我們的方法得出的相似度仍然高出傳統(tǒng)方法0.1985；再隨機增加不超過50%的字符錄入差異后，我們的方法高出傳統(tǒng)方法0.0602，這時準(zhǔn)確率略有下降，這是因為在同時存在三種差異時記錄本身的差別已經(jīng)比較大了，很難判定兩條記錄是不是真正重復(fù)。綜上來看，我們的相似度計算方法準(zhǔn)確性要優(yōu)于傳統(tǒng)的方法。6.3 原始記錄集合R重復(fù)記錄檢測實驗分析對原始記錄集合進(jìn)行重復(fù)檢測時，共有3個重要參數(shù)：相似度閾值、基準(zhǔn)記錄數(shù)(NR)和每條基準(zhǔn)記錄對應(yīng)的重復(fù)記錄數(shù)（ND）。共進(jìn)行3次實驗，每次僅改變一個參數(shù)，用平均比較次數(shù)來測試重復(fù)檢測

32、算法的執(zhí)行效率。對所有記錄在被投入正確的桶之前經(jīng)過的比較次數(shù)進(jìn)行加和，然后除以記錄總數(shù)，得到平均比較次數(shù)。實驗結(jié)果如表2、3、4所示：表6-2：改變時平均比較次數(shù)（NR=100，ND=50）數(shù)據(jù)編號的取值數(shù)據(jù)集合大小（|R|）最終得到的分類數(shù)目平均比較次數(shù)10.3500040類81.1680次20.55000258類16.2186次30.950001192類21.4196次表6-3：NR改變時平均比較次數(shù)（=0.5，ND=50）數(shù)據(jù)編號NR的取值數(shù)據(jù)集合大?。▅R|）最終得到的分類數(shù)目平均比較次數(shù)11050032類14.0620次2502500192類9.5736次31005000357類10.2918次表6-4：ND改變時平均比較次數(shù)（=0.5，NR=100）數(shù)據(jù)編號ND的取值數(shù)據(jù)集合大?。▅R|）最終得到的分類數(shù)目平均比較次數(shù)1550095類2.6240次2252500215類7.7716次3505000354類10.4666次從實驗結(jié)果看來，每條記錄只需要經(jīng)過很少次的比較就可以被投入正確的桶，算法的實際效率要遠(yuǎn)高于最壞情況。結(jié) 論本文研究了具有多種類型不同模式的數(shù)據(jù)的重復(fù)記錄檢測問題，提出了一種基于二分圖的最優(yōu)匹配的記錄相似度計算方法，并基于這種記錄相似性提出了重復(fù)記錄檢測算法。理論分析和實驗結(jié)果表明，這種方法是正確并且有效的。參考文獻(xiàn)1. Elm