1、一種基于二分圖最優匹配的重復記錄檢測算法計算機科學與技術學院：李默涵 指導教師：王宏志摘 要： 信息集成系統中存在重復記錄，重復記錄的存在為數據處理和分析帶來了困難。重復記錄檢測已經成為當前數據庫研究中的熱點問題之一。目前的方法主要集中在計算具有同樣數據類型屬性的相似性上，而現實系統中存在大量具有不同數據類型、不同模式的記錄。本文針對具有多種類型不同模式的數據的重復記錄檢測問題，提出了一種基于二分圖的最優匹配的記錄相似度計算方法，并基于這種記錄相似性提出了重復記錄檢測算法。理論分析和實驗結果都表明了方法的正確性和有效性。關鍵詞：信息集成；重復檢測；記錄相似度；異構記錄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 引 言隨著信息技術的發展，信息集

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

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

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

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

9、排序，并使用滑動窗口的方法進行相似重復記錄檢測；文6把每條記錄看成一個字符串，對記錄進行排序，然后使用固定大小的優先隊列來順序掃描所有的已排序的記錄，并將它們聚類；文7給每條記錄賦予一個N-gram值，將記錄排序后使用優先隊列對記錄聚類；文8將每個字段值分解成多個tokens，對tokens進行排序，進而對記錄進行排序，使用滑動窗的方法來比較臨近范圍的記錄。這些工作都未考慮記錄的模式異構，不適用于處理具有異構模式的信息集成系統中的重復記錄檢測。3 問題定義信息集成系統中存在來自多個數據源的數據，不同記錄可能具有不同模式和信息表示方式。例如兩條來自不同的關系數據庫的本科學生信息記錄：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是重復記錄，但它們在多方面存在著不同：它們所在表名分別是Student和Undergraduate；姓名John_Smith在R2中縮寫為J.Smith；R2中沒有記錄學生的國籍信息。此外，對于某些數據源，我們僅能獲得記錄的內容，卻無法獲取相應的模式信息。在上述情況下，無法利用簡單的并、交、差等運算歸類重復記錄，而需要對記錄的內容加以分析，根據內容的相似

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

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

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

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

15、 R2是兩條記錄1.mR1的屬性個數2.nR2的屬性個數3.Foreach i, jdo4.wi, j 0/ w 是二分圖的權值矩陣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中所有點均有邊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 兩條記錄生成的權值矩陣及二分圖 圖4-2 對原始記錄集合進行劃分例如記錄R1(007, John_Smith, England)和R2(008, England, Jane_Smith)，其二分圖權值矩陣及完全有權二分圖如圖4-1所示，二分圖中虛線表示的邊權值都為0。求出最優匹配，得到兩條記錄的相似度為0.79。record_to_bipartite(R1, R2)的

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

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

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

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

21、的所有記錄相似度都滿足要求，則當前記錄投入桶，并將相應的棧內記錄移至棧頂（行7-10）。否則繼續在棧內向下搜索滿足條件的記錄（行11）。如果在搜索完棧內的所有記錄后，當前記錄仍沒有被投入桶，則將當前記錄入棧，置于棧頂（行13）。算法3：對原始記錄集合R進行劃分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對應的桶;9.將stacknow移至棧頂1

22、0.break11. else now now112.while now = -113. if now=-1 then stack.push(Ri)14. return （stack, buckets）算法結束后，每條棧內記錄（稱為標志性記錄）及其對應桶中記錄劃歸一個集合，所有這樣的集合形成對R的一個滿足條件的劃分。我們仍以集合R=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)為例說明劃分算法的過程。設=

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

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

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

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

27、逐步細化的策略來提高速度。基本思想是：先對元組進行一遍掃描，將其粗糙的分為若干類，再在這些粗糙分類中進行精確的分類。這樣，每次精確分類只需要在這些粗糙分類中進行，使得精確分類要判定的元組數目大大減少，從而提高算法的運行速度。具體的做法類似于算法3。設當前正在檢測的記錄記為Rk，從棧頂開始，依次和棧內標志性記錄（記為Rs）比較相似度，若Rk和Rs的相似度不小于，則投入Rs對應的桶。這樣一遍掃描后，桶內記錄形成一個粗糙分類。如果得到的粗糙分類仍很大，則在已有粗糙分類基礎上再進行多遍粗糙分類。事實上，在記錄集合里的記錄兩兩相似度比較大的情況下，也可以僅使用粗糙分類來實現快速分類。逐步細化分類的缺點是

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

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

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

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

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