馬可 鄭廣海

摘要：在大數(shù)據(jù)處理分析中，需要對(duì)數(shù)據(jù)記錄進(jìn)行相似重復(fù)記錄檢測(cè)并消除，可以提高數(shù)據(jù)記錄的質(zhì)量。鄰近排序算法（SNM算法）是對(duì)數(shù)據(jù)庫(kù)所有記錄進(jìn)行排序比對(duì)，新記錄和舊記錄都需要比對(duì)，而舊記錄的相互比是已經(jīng)做過(guò)的，這就造成了一定的計(jì)算浪費(fèi)。在考慮盡量減少這種計(jì)算浪費(fèi)的基礎(chǔ)上，提出了一種針對(duì)關(guān)系數(shù)據(jù)庫(kù)記錄的相似重復(fù)記錄檢測(cè)算法，算法首先創(chuàng)建記錄屬性關(guān)系表，設(shè)定屬性的相應(yīng)權(quán)重和相似度閾值，通過(guò)屬性關(guān)系表計(jì)算記錄和其他記錄的相似度，從而完成對(duì)相似重復(fù)記錄的檢測(cè)。實(shí)驗(yàn)表明新的算法的效率比SNM算法有一定提高。

關(guān)鍵詞：相似重復(fù)記錄；snm算法；檢測(cè)

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）13-0025-04

1引言

隨著移動(dòng)互聯(lián)網(wǎng)、物聯(lián)網(wǎng)的迅速發(fā)展，大數(shù)據(jù)時(shí)代正在不同程度影響著我們的生活。企業(yè)收集、處理的數(shù)據(jù)越來(lái)越多，各類應(yīng)用數(shù)據(jù)庫(kù)中存在著大量的臟數(shù)據(jù)，這些數(shù)據(jù)可能與業(yè)務(wù)無(wú)關(guān)或錯(cuò)誤格式或不規(guī)范描述甚至相似重復(fù)的數(shù)據(jù)。這些不正確的記錄，影響企業(yè)數(shù)據(jù)統(tǒng)計(jì)分析利用的效率與準(zhǔn)確性，甚至可能對(duì)企業(yè)的決策過(guò)程起到錯(cuò)誤的幫助。這些相似重復(fù)記錄是不正確的，相似重復(fù)記錄嚴(yán)重?fù)p害了數(shù)據(jù)的一致性，造成了一定程度上的數(shù)據(jù)冗余，產(chǎn)生了資源的浪費(fèi)，對(duì)數(shù)據(jù)的準(zhǔn)確性產(chǎn)生了影響。如何處理這些臟數(shù)據(jù)是我們面臨的挑戰(zhàn)。

要處理這些相似重復(fù)記錄，可以通過(guò)常用算法，如聚類算法，N-Grams算法[1]，字段匹配算法等識(shí)別出相似重復(fù)記錄，隨后通過(guò)人工或代碼進(jìn)行清除處理；也可以通過(guò)基于排序和合并的算法對(duì)數(shù)據(jù)庫(kù)相似重復(fù)記錄進(jìn)行識(shí)別，并找出的重復(fù)記錄進(jìn)行刪除或合并操作。基于排序和合并的常用算法有鄰近排序算法（SNM算法），多趟近鄰排序算法（MPN算法）等[2-7]。

針對(duì)鄰近排序算法，張建中[8]提出來(lái)對(duì)滑動(dòng)窗口的大小采取動(dòng)態(tài)變化和窗口的移動(dòng)速度進(jìn)行動(dòng)態(tài)變化，使得改進(jìn)后SNM算法比傳統(tǒng)SNM算法的效率得到了提升；余肖生[9]提出了對(duì)記錄進(jìn)行字符串單詞化處理，較好地彌補(bǔ)了傳統(tǒng)算法的缺陷，得到了比傳統(tǒng)SNM算法更好的效果；李軍[10]提出了對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，使記錄格式更加規(guī)范，采用預(yù)處理后算法性能得到提升。殷秀葉[11]針對(duì)記錄的屬性，提出了同級(jí)屬性的概念，利用同級(jí)屬性進(jìn)行檢測(cè)大大縮短了檢測(cè)時(shí)間，提高了檢測(cè)的效率。郭文龍[12]針對(duì)客戶關(guān)系數(shù)據(jù)庫(kù)提出了一種清洗算法，獲得了較好的效果。劉雅思[13]提出來(lái)基于長(zhǎng)度過(guò)濾和動(dòng)態(tài)容錯(cuò)的SNM改進(jìn)算法，使得準(zhǔn)確率和時(shí)間效率獲得了顯著提升。宋興國(guó)[14]利用R-樹(shù)檢索提出了DRR算法，獲得了更高的準(zhǔn)確率和時(shí)間效率。楊巧巧[15]提出來(lái)基于聚類分組和屬性綜合權(quán)值的SNM改進(jìn)算法，獲得了查全率和查準(zhǔn)率的提升。

從上述文獻(xiàn)的論述中，我們可以看出存在這樣一個(gè)問(wèn)題，關(guān)系數(shù)據(jù)庫(kù)記錄量往往不是一成不變的，隨時(shí)間變化而變化。在添加了新記錄后，使用SNM算法對(duì)所有記錄進(jìn)行排序比對(duì)時(shí)，不僅要對(duì)新記錄和舊記錄進(jìn)行比對(duì)，還有在舊記錄之間相互比對(duì)，這些舊記錄的相互比對(duì)往往是過(guò)去已經(jīng)做過(guò)的，這樣就造成了一定的計(jì)算浪費(fèi)。在此基礎(chǔ)上，本文在SNM算法基礎(chǔ)上提出了一種改進(jìn)算法，一種針對(duì)關(guān)系數(shù)據(jù)庫(kù)記錄的相似重復(fù)記錄檢測(cè)算法即ISNM算法（improved sorted-neighborhood method）。SNM算法是通過(guò)對(duì)記錄按照一定要求方法進(jìn)行排序，從而進(jìn)行附近比較，而改進(jìn)ISNM算法在SNM算法基礎(chǔ)上添加了一定的記憶功能，對(duì)記錄進(jìn)行分類存儲(chǔ)，通過(guò)調(diào)取在同一分類的記錄進(jìn)行比對(duì)而不是原本的附近比對(duì)，使得改進(jìn)算法不用對(duì)已經(jīng)處理過(guò)的記錄進(jìn)行重復(fù)比對(duì)。

2 算法描述

2.1相關(guān)定義

我們提出的ISNM算法，是基于SNM算法，在SNM算法中添加記憶信息，以減少比對(duì)次數(shù)，稱為記憶鄰近排序算法。算法具體處理過(guò)程是先將記錄按照屬性創(chuàng)建屬性關(guān)系表，把記錄按照每個(gè)屬性的屬性值進(jìn)行分類，查找具有相同屬性值的其他記錄進(jìn)行相似度檢測(cè)，從而找出相似重復(fù)記錄。為了描述方便，我們給出如下定義：

定義1 設(shè)數(shù)據(jù)庫(kù)記錄一共有n個(gè)屬性。每個(gè)屬性都有一定的判讀可能性即權(quán)重

2.2構(gòu)建親屬記錄

考慮到記錄可能沒(méi)有唯一標(biāo)識(shí)的主鍵，或者姓名身份證號(hào)碼作為主鍵時(shí)可能這些主鍵有錯(cuò)誤內(nèi)容。根據(jù)數(shù)據(jù)庫(kù)記錄，創(chuàng)建唯一表示記錄的屬性編號(hào)，編號(hào)屬性權(quán)重為0。可以通過(guò)編號(hào)找到該記錄，也方便存儲(chǔ)。按照記錄創(chuàng)建屬性關(guān)系表，把所有屬性分成不同的屬性庫(kù)，每個(gè)屬性庫(kù)記錄該屬性所有的屬性值表，每個(gè)屬性值表里存放著具有該屬性值的所有記錄的編號(hào)。如果手動(dòng)輸入，大量記錄的工作量十分巨大，考慮代碼輸入記錄。首先創(chuàng)建屬性庫(kù)，這些屬性庫(kù)創(chuàng)建后都是空庫(kù)。按照編號(hào)從小到大的順序依次讀取數(shù)據(jù)庫(kù)記錄，對(duì)屬性庫(kù)進(jìn)行訪問(wèn)，查詢?cè)撚涗浀膶傩灾祵?duì)應(yīng)的屬性庫(kù)的屬性值表。如果存在該屬性值表，就在該屬性值表加入該記錄；如果不存在，就在屬性庫(kù)中添加該屬性值表，并在屬性值表里存入該記錄編號(hào)。讀取完記錄后，屬性庫(kù)和屬性值表填充完畢。

2.3 ISNM算法

改進(jìn)算法簡(jiǎn)單地說(shuō)就是對(duì)于新紀(jì)錄和所有舊記錄的比對(duì)，如果一一比對(duì)，計(jì)算量是非常大的。而兩個(gè)記錄在某屬性是非親屬記錄，其相對(duì)于的相對(duì)相似度為0，那么只要找出相對(duì)相似度不為0的相對(duì)相似度求其和就是兩個(gè)記錄的相似度。相對(duì)相似度不為0只有親屬記錄，可以通過(guò)屬性關(guān)系表，找到這些親屬記錄，利用親屬記錄求記錄的相似度。親屬記錄相對(duì)所有記錄來(lái)說(shuō)是非常少的，利用親屬記錄可以大量減少計(jì)算量。

步驟如下：

Input（R，W，U）

For（a= 0；a

For（b=0；b

SimR（Ra，Rb）=0；//初始化所有相似度

For（s=0；s

{For（p=1；p<=n；p++） //n表示屬性個(gè)數(shù)

{

//根據(jù)s記錄的第p屬性的屬性值，

//讀取屬性關(guān)系表s記錄的第p屬性的所有親屬記錄

Select p屬性 from 屬性關(guān)系表s記錄 where s記錄的第p屬性值=親屬記錄

Insert into 親屬記錄表

Simp（Rs，Ri）=Wp；

//i是親屬記錄是數(shù)據(jù)庫(kù)第i個(gè)記錄

SimR（Rs，Ri）+= Simp（Rs，Ri）；

If（SimR（Rs，Rj） > U）

output（Rs，Rj）

SimR（Rs，Rj）=0；//賦值為0，防止重復(fù)出現(xiàn)該對(duì)相似重復(fù)記錄

}

}

3 實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)方案和配置

在同樣實(shí)驗(yàn)環(huán)境條件下使用ISNM算法和傳統(tǒng)SNM算法對(duì)同一數(shù)據(jù)集進(jìn)行處理。實(shí)驗(yàn)數(shù)據(jù)來(lái)自某地區(qū)的數(shù)據(jù)庫(kù)，8萬(wàn)條左右記錄，8個(gè)屬性。實(shí)驗(yàn)中隨機(jī)提取2萬(wàn)，4萬(wàn)，6萬(wàn)，8萬(wàn)條記錄進(jìn)行測(cè)試，對(duì)提取的這些記錄進(jìn)行處理使其成為包括187，259，337，421條相似重復(fù)記錄的數(shù)據(jù)集。使用人工方式統(tǒng)計(jì)檢測(cè)出來(lái)的相似重復(fù)記錄和正確識(shí)別的相似重復(fù)記錄。在總數(shù)據(jù)集為8萬(wàn)條記錄的基礎(chǔ)上，每次隨機(jī)提取1萬(wàn)條，2萬(wàn)條，4萬(wàn)條，8萬(wàn)條作為數(shù)據(jù)集的新紀(jì)錄，分別計(jì)算兩種算法消耗的時(shí)間。

本文實(shí)驗(yàn)計(jì)算機(jī)配置：處理器Inel（R）i-4210M CPU @ 2.60GHz 雙核，8GB內(nèi)存，1T硬盤；操作系統(tǒng)：windows8.1；軟件mysql+vs2013。

要驗(yàn)證改進(jìn)算法的優(yōu)劣，通常的標(biāo)準(zhǔn)是計(jì)算查重的查準(zhǔn)率RZ和查全率RQ。查準(zhǔn)率表示檢測(cè)出來(lái)正確的相似重復(fù)記錄在所有檢測(cè)出來(lái)的相似重復(fù)記錄的比例，數(shù)據(jù)記錄的查全率表示檢測(cè)出來(lái)正確的相似重復(fù)記錄在數(shù)據(jù)庫(kù)里實(shí)際存在的相似重復(fù)記錄的比例。設(shè)MSJ表示數(shù)據(jù)庫(kù)實(shí)際存在的相似重復(fù)記錄，MZQ表示檢測(cè)出來(lái)正確的相似重復(fù)記錄，MJC表示檢測(cè)出來(lái)的所有相似重復(fù)記錄。則查準(zhǔn)率RZ和查全率RQ的計(jì)算公式如下：

查準(zhǔn)率RZ=MZQ /MJC，查全率RQ=MZQ /MSJ。

3.2結(jié)果與分析

根據(jù)上面的內(nèi)容，在相同的實(shí)驗(yàn)條件下，使用SNM算法和ISNM算法對(duì)同一數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn) 。實(shí)驗(yàn)的結(jié)果如圖1-圖2所示。圖1表示了利用SNM算法和ISNM算法得出的查準(zhǔn)率RZ。圖2表示了利用SNM算法和ISNM算法得出的查全率RQ。

從圖1可以看出，ISNM算法的查準(zhǔn)率始終高于傳統(tǒng)SNM算法，提高了檢測(cè)相似重復(fù)記錄的效率，雖然隨著數(shù)據(jù)量的增加，二者的準(zhǔn)確率都有一定程度的下降，但是ISNM算法依然保持較高的準(zhǔn)確度，而且其下降趨勢(shì)也小于傳統(tǒng)SNM算法。

從圖2可以看出，ISNM算法顯著提高了查全率。傳統(tǒng)SNM算法因?yàn)榕判蛞?guī)則導(dǎo)致一些相似重復(fù)記錄無(wú)法被檢測(cè)到。而ISNM算法使用相對(duì)合適的閾值U，其查全率幾乎達(dá)到了100%，解決了傳統(tǒng)SNM算法可能因?yàn)榕判蛞?guī)則導(dǎo)致一些記錄無(wú)法被檢測(cè)的問(wèn)題。

從圖3可以看出，往數(shù)據(jù)集添加新數(shù)據(jù)后，ISNM算法處理時(shí)間小于傳統(tǒng)SNM算法。傳統(tǒng)SNM算法要對(duì)所有記錄進(jìn)行排序比對(duì)，不僅有新紀(jì)錄之間的比對(duì)，新舊記錄的比對(duì)，還有大量舊記錄之間的比對(duì)。而ISNM算法不會(huì)包含舊記錄之間的比對(duì)，減少了大量的計(jì)算量。ISNM算法僅對(duì)新數(shù)據(jù)記錄進(jìn)行檢測(cè)，從數(shù)據(jù)庫(kù)調(diào)取新記錄的親屬記錄進(jìn)行處理。雖然可能處理某些新數(shù)據(jù)記錄消耗的時(shí)間比使用傳統(tǒng)SNM算法要高，但不會(huì)像傳統(tǒng)SNM算法對(duì)所有記錄進(jìn)行處理，只對(duì)新紀(jì)錄進(jìn)行處理，在時(shí)間效率上得到提升。對(duì)于現(xiàn)代企業(yè)數(shù)據(jù)庫(kù)來(lái)說(shuō)，增加的記錄和自身總數(shù)據(jù)量相比很小，使用ISNM算法比使用傳統(tǒng)SNM算法消耗的時(shí)間要小很多。

4 小結(jié)

在數(shù)據(jù)庫(kù)中存放在大量的數(shù)據(jù)記錄，一些記錄因?yàn)楝F(xiàn)實(shí)收集處理中的可能存在的錯(cuò)誤，使得這些記錄構(gòu)成了相似重復(fù)記錄，通過(guò)一定的算法可以對(duì)這些相似重復(fù)記錄進(jìn)行檢測(cè)，方便數(shù)據(jù)庫(kù)維護(hù)人員進(jìn)行修改，提高了數(shù)據(jù)庫(kù)記錄的準(zhǔn)確性和有效性。本文提出的ISNM算法對(duì)數(shù)據(jù)庫(kù)記錄進(jìn)行處理，檢測(cè)相似重復(fù)記錄，取得了較好的效果。然而也存在一些不足之處，如果處理完全是新的記錄集，沒(méi)有過(guò)去的記錄集，消耗的時(shí)間與傳統(tǒng)SNM算法消耗的時(shí)間沒(méi)多少差別，極端情況下甚至更高。而且憑經(jīng)驗(yàn)設(shè)置屬性權(quán)重和相似度值，現(xiàn)實(shí)使用中應(yīng)設(shè)置多大沒(méi)有進(jìn)行討論以及減少物理內(nèi)存地址占用，這將是接下來(lái)研究的工作。

參考文獻(xiàn)：

[1]邱越峰，田增平，季文贇，等.一種高效的檢測(cè)相似重復(fù)記錄的方法[J].計(jì)算機(jī)學(xué)報(bào)，2001（1）：69-77.

[2]Zhang， Zhongnan，He， Ling，Tan， Yize，Liao， Minghong. A Heuristic Approximately Duplicate Records Detection Algorithm Based on Attributes Analysis[J]. EN，2012，6（4）.

[3]WenfeiFan，ShuaiMa，NanTang，Wenyuan Yu. Interaction between Record Matching and Data Repairing[J]. Journal of Data and Information Quality （JDIQ），2014，4（4）.

[4]he merge purge problem for large databases. Mauricio A H，Salvatore J S. Proceedings of the ACM SIGMOD International Conference on Management of Data， 1995

[5]李堅(jiān)，鄭寧.對(duì)基于MPN數(shù)據(jù)清洗算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，2008（2）：245-247.

[6]郭文龍.一種改進(jìn)的相似重復(fù)記錄檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（1）：293-295.

[7]郭文龍，董建懷.基于模糊綜合評(píng)判的相似重復(fù)記錄清洗方法[J].北京信息科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，32（4）：59-63.

[8]張建中，方正，熊擁軍，等.對(duì)基于SNM數(shù)據(jù)清洗算法的優(yōu)化[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，41（6）：2240-2245.

[9]余肖生，胡孫枝.基于SNM改進(jìn)算法的相似重復(fù)記錄消除[J].重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2016，30（4）：91-96.

[10]李軍.一種相似重復(fù)記錄檢測(cè)算法的改進(jìn)與應(yīng)用[J].成都工業(yè)學(xué)院學(xué)報(bào)，2017，20（2）：17-20.

[11]殷秀葉.大數(shù)據(jù)環(huán)境下一種高效的重復(fù)記錄檢測(cè)方法[J].洛陽(yáng)師范學(xué)院學(xué)報(bào)，2014，33（11）：52-54.

[12]郭文龍.一種客戶關(guān)系數(shù)據(jù)庫(kù)相似重復(fù)記錄清洗算法[J].衡水學(xué)院學(xué)報(bào)，2014，16（1）：15-17.

[13]劉雅思，程力，李曉.基于長(zhǎng)度過(guò)濾和動(dòng)態(tài)容錯(cuò)的SNM改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，2017，34（1）：147-150+155.

[14]宋國(guó)興，周喜，馬博，等.基于R-樹(shù)索引的高維相似重復(fù)記錄檢測(cè)改進(jìn)算法[J].微電子學(xué)與計(jì)算機(jī)，2017，34（9）：97-102.

[15]楊巧巧，郭振波，王開(kāi)西.基于聚類分組和屬性綜合權(quán)值的SNM改進(jìn)算法[J].工業(yè)控制計(jì)算機(jī)，2017，30（9）：27-28+31.