王琛

摘 要： 為了提高數據集中相似重復記錄的檢測效率，提出一種基于屬性權值的分組聚類算法。該方法在記錄集中選取特征屬性，通過設定的權值對記錄進行聚類，在形成的數據子集中進行字段匹配和記錄匹配，來識別相似重復記錄，并給出了相關算法。實驗表明，該方法能減少字段的匹配次數和記錄的匹配范圍，節(jié)省運行時間，具有較高的查全率和查準率。

關鍵詞： 相似重復記錄； 聚類； 特征屬性； 字段匹配； 記錄匹配

中圖分類號： TP 391 文獻標志碼： A 文章編號： 1671-2153（2015）02-0072-04

0 引 言

消除通過Web上的信息抽取獲得的重復記錄是目前數據清洗領域研究最多的內容，其關鍵問題就是判斷兩個記錄是否近似重復。從查全率和查準率的角度來說，檢測重復記錄最可靠的方法就是逐個比較數據集中的每條記錄。目前識別重復記錄的經典算法主要是基于排序比較的思想，主要有基本鄰近排序算法（Basic Sorted?Neighborhood Method，SNM）[1]、多趟鄰近排序算法（Multi?Pass Sorted?Neighborhood，MPN）[2]，以及優(yōu)先隊列清洗策略[3]。

檢測重復記錄的核心則是字段的匹配問題，主要算法有：遞歸字段匹配算法[4]、Smith Waterman（S?W）算法[4]、N?Grams算法[5]以及基于編輯距離的字段匹配算法等。

利用這些傳統(tǒng)的算法在海量數據中查找相似重復記錄，時間復雜度和空間復雜度均很大，并且某些字段中字符所在位置的敏感性將導致相似的記錄未必能相鄰排列，往往會降低檢測的效果。本文提出一種基于屬性權值的記錄分組聚類算法來檢測相似重復記錄，主要包括字段匹配和記錄匹配兩個方面。

1 算法基本思想

Web上抽取的數據集中記錄的各個屬性均用來表示該實體的特征，但在描述某個實體時，各個屬性的重要程度不同，首先選取特征屬性，刪除無關屬性，并為特征屬性劃分不同的級別，賦予不同的權重值，根據分層分級的思想，按照屬性權重值的大小，對數據集進行初始聚類，使相似記錄盡可能排在相鄰區(qū)域，將大數據集分割成不相交的小數據集；然后對小數據集通過計算字段相似度進行字段匹配；最后進行記錄匹配，利用字段加權匹配的方法來檢測相似重復記錄。

2 屬性權重設定

2.1 特征屬性

在進行記錄匹配時，首先應該選取最能描述記錄特征的屬性，去除無關屬性，從而減少字段匹配的次數和記錄匹配的運行時間，提高算法的運行效率，同時有效降低大數量數據相似重復記錄檢測的復雜性。一般作為特征屬性，不能存在值缺失、不唯一、重復太多的情況。例如：開本等，因為很多不同的書籍均采用相同的開本，如16開等，但它們不是重復記錄。

2.2 權重值設定

若記錄間具有的相同屬性越多，且這些相同屬性的權值越大，則越相似。假設將關系表中各條記錄的特征屬性選取出來，形成特征向量C=（C1，C2，…，Cn），Ck表示關系表中第k個字段，其中，1≤k≤n；對于任意記錄Ri={Ri1，Ri2，…，Rin}，其中Rik表示記錄Ri中第k個字段的值；同時需要設置一個值，用來表示Rik這個字段在這條記錄中的重要程度，值越大，說明越重要，將這個值稱為屬性的權重，則權重向量為

Weight={Weight1，Weight2，…，Weightm}。

2.3 初始聚類

初始聚類的目的，就是根據分組的思想，將可能存在的相似重復的記錄排在相鄰區(qū)域，這樣可以限制記錄匹配范圍，既可以減少檢測時間，又可以獲得較好的查全率和查準率。

聚類的方法：權重值越大的屬性越重要，因為它最能體現實體的特征，通常先按權重值最大的屬性對記錄分組，從而得到若干數據子集，對于子集較大的，可按第二大權重值對應的屬性進行二次分組，以此類推，最終得到的分組要求大小適宜。

3 字段匹配

字段匹配是記錄匹配的基礎，主要用來判斷各記錄中對應字段的相似度，若對應字段的值在語義上相等，或可以表示同一實體，即為等價。

字段的類型分為數值型和字符型，數值型字段的匹配一般為精確匹配，判斷值是否相等即可。而字符型字段的匹配則較為復雜，也是研究的重點。因為Web上抽取到的數據集中字段幾乎都為字符型數據，也是最易產生重復數據的根源。

5 實驗結果與分析

對于相似重復記錄的檢測，將基于屬性權值的記錄分組聚類算法（簡稱權值分組算法），與文獻[3]提出的優(yōu)先隊列算法進行對比，分別獲取抽取數據5000，10000，15000，通過軟件和手動方式分別處理成有45，110，165對相似重復記錄，用權值分組和優(yōu)先隊列兩種方法檢測重復記錄，從查準率、查全率和運行時間三個方面進行比較，結果如圖1～圖3所示。

由圖1與圖2可以看出，優(yōu)先隊列算法的查準率與查全率均低于權值分組，隨著數據量的增多，權值分組算法仍然可以保持較高的查全率和查準率，而優(yōu)先隊列算法的查全率和查準率均出現了下降。這主要是因為優(yōu)先隊列算法在排序時由于字符位置的敏感性，導致了相似記錄在排序后，不能完全處在相鄰區(qū)域，而權值分組是給不同字段賦予不同權值，并能進行多趟分組查找，可以提高精度。

由圖3可以看出，兩種方法在3個不同數據量上進行測試，權值分組算法運行時間分別為8，11，13 s；而優(yōu)先隊列算法運行時間為9，15，26 s，顯然比權值分組算法慢得多。這主要是由于權值分組是對記錄進行特征屬性優(yōu)選，再根據分組思想將大的數據集分割成小的不相交的數據集，從而減少了字段的匹配次數，與記錄匹配的范圍，自然節(jié)省了運行時間。

6 結束語

相似重復記錄的檢測是數據清洗工作的核心問題。本文提出了一種基于屬性權值的記錄分組聚類算法來檢測相似重復記錄。該方法從記錄集中選取特征屬性，刪除無關屬性，按照設定的權值對數據集進行聚類，使相似記錄盡可能排在相鄰區(qū)域，從而可以減少字段的匹配次數和記錄的匹配范圍，節(jié)省運行時間，可以解決大規(guī)模數據量中的相似重復記錄檢測問題，并從查準率、查全率和運行時間三個方面驗證了該方法的合理性和有效性。

參考文獻：

[1] 張建中，方進. 對基于SNM數據清洗算法的優(yōu)化[J]. 中南大學學報：自然科學版，2010：41（6）：2240-2245.

[2] HERNANDEZ M A，STOLFO J S. Real?world data is dirty：data cleansing and the merge/purge problem[J]. Journal of Data Mining and Knowledge Discovery，1998（2）：9-37.

[3] MONGE A E. Matching algorithm within a duplicate detection system[J]. IEEE Data Engineering Bulletin， 2000，23（4）：14-20.

[4] 佘春紅，許向陽. 關系數據庫中近似重復記錄的識別[J]. 計算機應用研究，2003，20（9）：36-37.

[5] 邱越峰，田增平，季文贊，等. 一種高效的檢測相似重復記錄的方法[J]. 計算機學報，2001（1）：69-77.

[6] DEY D，SARKAR S，D E P. A distance?based approach to entity reconciliation in heterogeneous databases[J]. IEEE Transactions on Knowledge and Data Engineering，2002，14（3）：567-582.

[7] 張永，遲忠先. 位置編碼在數據倉庫中的應用[J]. 計算機工程，2007，33（l）：50-52.

Abstract： In order to improve the efficiency of detection of approximately duplicated records in the Data collection， a clustering algorithm based on the attribute weights grouping is presented. This method selects attributes in a recordset，clusters records through the set of weights and then completes field matching and records matching in the generated data subsets. The correlation algorithms are gived. Experimental results show this method can reduce the number of field matching， reduce the range of record matching， save the running time and achieve high recall and precision.

Key words： approximately duplicate records； clustering； attributions； field matching； record matching

（責任編輯：徐興華）