王琛

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

關(guān)鍵詞： 相似重復(fù)記錄； 聚類； 特征屬性； 字段匹配； 記錄匹配

中圖分類號： TP 391 文獻(xiàn)標(biāo)志碼： A 文章編號： 1671-2153（2015）02-0072-04

0 引 言

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

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

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

1 算法基本思想

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

2 屬性權(quán)重設(shè)定

2.1 特征屬性

在進(jìn)行記錄匹配時(shí)，首先應(yīng)該選取最能描述記錄特征的屬性，去除無關(guān)屬性，從而減少字段匹配的次數(shù)和記錄匹配的運(yùn)行時(shí)間，提高算法的運(yùn)行效率，同時(shí)有效降低大數(shù)量數(shù)據(jù)相似重復(fù)記錄檢測的復(fù)雜性。一般作為特征屬性，不能存在值缺失、不唯一、重復(fù)太多的情況。例如：開本等，因?yàn)楹芏嗖煌臅捎孟嗤拈_本，如16開等，但它們不是重復(fù)記錄。

2.2 權(quán)重值設(shè)定

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

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

2.3 初始聚類

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

聚類的方法：權(quán)重值越大的屬性越重要，因?yàn)樗钅荏w現(xiàn)實(shí)體的特征，通常先按權(quán)重值最大的屬性對記錄分組，從而得到若干數(shù)據(jù)子集，對于子集較大的，可按第二大權(quán)重值對應(yīng)的屬性進(jìn)行二次分組，以此類推，最終得到的分組要求大小適宜。

3 字段匹配

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

字段的類型分為數(shù)值型和字符型，數(shù)值型字段的匹配一般為精確匹配，判斷值是否相等即可。而字符型字段的匹配則較為復(fù)雜，也是研究的重點(diǎn)。因?yàn)閃eb上抽取到的數(shù)據(jù)集中字段幾乎都為字符型數(shù)據(jù)，也是最易產(chǎn)生重復(fù)數(shù)據(jù)的根源。

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

6 結(jié)束語

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

參考文獻(xiàn)：

[1] 張建中，方進(jìn). 對基于SNM數(shù)據(jù)清洗算法的優(yōu)化[J]. 中南大學(xué)學(xué)報(bào)：自然科學(xué)版，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] 佘春紅，許向陽. 關(guān)系數(shù)據(jù)庫中近似重復(fù)記錄的識別[J]. 計(jì)算機(jī)應(yīng)用研究，2003，20（9）：36-37.

[5] 邱越峰，田增平，季文贊，等. 一種高效的檢測相似重復(fù)記錄的方法[J]. 計(jì)算機(jī)學(xué)報(bào)，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] 張永，遲忠先. 位置編碼在數(shù)據(jù)倉庫中的應(yīng)用[J]. 計(jì)算機(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

（責(zé)任編輯：徐興華）