一種相似重復(fù)記錄檢測(cè)算法的改進(jìn)與應(yīng)用

李 軍

(安徽職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，合肥 230011)

一種相似重復(fù)記錄檢測(cè)算法的改進(jìn)與應(yīng)用

李 軍

(安徽職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，合肥 230011)

介紹數(shù)據(jù)清洗與相似重復(fù)記錄檢測(cè)算法的相關(guān)概念以及相似重復(fù)記錄的清洗原理。對(duì)基本近鄰排序算法SNM進(jìn)行了深入分析和研究，指出其中的不足，在此基礎(chǔ)上給出改進(jìn)策略并加以應(yīng)用。實(shí)踐證明：該改進(jìn)算法在關(guān)鍵性能上有明顯改善。

大數(shù)據(jù)；數(shù)據(jù)清洗；相似重復(fù)記錄

信息化社會(huì)每天都產(chǎn)生大量的數(shù)據(jù)，這些海量數(shù)據(jù)通常包含一些重要信息，這些信息往往是信息決策支持系統(tǒng)的決策依據(jù)。但龐大的數(shù)據(jù)集中除了含有重要信息的數(shù)據(jù)之外，也夾雜著一些無(wú)用的、錯(cuò)誤的、不一致的、不完整的、重復(fù)的數(shù)據(jù)，即“臟數(shù)據(jù)”。臟數(shù)據(jù)的存在不可避免，它不僅可能導(dǎo)致信息失真，還極有可能給依此而建立的決策支持系統(tǒng)以及應(yīng)用商務(wù)智能帶來(lái)隱患[1]。因此，在數(shù)據(jù)進(jìn)入實(shí)用系統(tǒng)前進(jìn)行數(shù)據(jù)清洗(data cleaning)是非常重要的。數(shù)據(jù)清洗是將數(shù)據(jù)庫(kù)中的臟數(shù)據(jù)通過(guò)一定的技術(shù)和手段轉(zhuǎn)變成合乎系統(tǒng)要求的數(shù)據(jù)處理過(guò)程。本文在分析鄰近排序算法(Sorted-Neighborhood Method,SNM)原理的基礎(chǔ)上，針對(duì)SNM算法的不足，提出了排序關(guān)鍵字預(yù)處理和伸縮窗口等改進(jìn)措施，以提高數(shù)據(jù)的聚類速度和比較速度。

1 相似重復(fù)記錄清洗

數(shù)據(jù)清洗通常是從數(shù)據(jù)是否完整準(zhǔn)確、有無(wú)冗余以及時(shí)空有效性等方面來(lái)進(jìn)行。從數(shù)據(jù)清洗的內(nèi)容來(lái)看，主要包括錯(cuò)誤數(shù)據(jù)、不完整數(shù)據(jù)以及相似重復(fù)記錄3種清洗對(duì)象[2]。由于相似重復(fù)記錄幾乎會(huì)出現(xiàn)在所有未經(jīng)清洗的稍大規(guī)模的數(shù)據(jù)集中，因此，針對(duì)相似重復(fù)記錄的清洗尤為重要。

一個(gè)客觀實(shí)體在同一個(gè)數(shù)據(jù)庫(kù)中以多條完全相同或高度相似的記錄形式存在，則這些記錄之間彼此互稱為相似重復(fù)記錄。簡(jiǎn)單地說(shuō),在同一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)中，如果出現(xiàn)兩條或兩條以上的記錄，它們之間出現(xiàn)足夠多的相同或相似的屬性值，即可認(rèn)定其為相似重復(fù)記錄，如表1所示。

表1 相似重復(fù)記錄實(shí)例

最簡(jiǎn)單的相似重復(fù)記錄檢測(cè)方法是用一條記錄與數(shù)據(jù)集中的每條記錄進(jìn)行匹配比較。若數(shù)據(jù)庫(kù)中的記錄總數(shù)為n，則需要進(jìn)行n(n-1)/2次比較，其時(shí)間復(fù)雜度為O(n2)，對(duì)于海量數(shù)據(jù)來(lái)說(shuō)，顯然是不可取的方法。

為提高檢測(cè)效率，目前通常使用“排序-合并法”，它先以數(shù)據(jù)表的某個(gè)特征屬性或組合屬性對(duì)數(shù)據(jù)表進(jìn)行排序處理，盡可能地使相似重復(fù)記錄聚集在一起，再將記錄與一個(gè)較小范圍內(nèi)的記錄逐一比較，如發(fā)現(xiàn)相似重復(fù)記錄，則根據(jù)預(yù)定義的相關(guān)規(guī)則，對(duì)它們進(jìn)行合并。其清洗過(guò)程如圖1所示。

圖1 相似重復(fù)記錄的清洗過(guò)程

由圖1可知，排序-合并法一般包括3個(gè)階段：

1)作為數(shù)據(jù)預(yù)處理的方式之一，數(shù)據(jù)排序依據(jù)排序關(guān)鍵字對(duì)數(shù)據(jù)庫(kù)中的記錄進(jìn)行排序處理。這一環(huán)節(jié)的主要目的是把可能的相似重復(fù)記錄盡可能地排在一起。排序的結(jié)果顯然依賴于排序關(guān)鍵字，采用不同的排序關(guān)鍵字，可能得到差異很大的排序結(jié)果。因此，如何選擇和處理排序關(guān)鍵字，在數(shù)據(jù)排序這一環(huán)節(jié)中尤為重要。

2)第2階段是對(duì)相似重復(fù)記錄的檢測(cè)。由于進(jìn)行相似重復(fù)記錄檢測(cè)是在一個(gè)經(jīng)過(guò)排序處理后所得到的子集范圍內(nèi)實(shí)現(xiàn)，其算法的時(shí)間復(fù)雜度為O(nlogn)，檢測(cè)效率明顯提升。目前已有的相似重復(fù)記錄檢測(cè)方法大多依此思想為基礎(chǔ)[3]。

3)數(shù)據(jù)合并是對(duì)數(shù)據(jù)集進(jìn)行增刪補(bǔ)改的清洗階段。經(jīng)過(guò)檢測(cè)被認(rèn)定為相似重復(fù)記錄的兩條記錄需要進(jìn)行數(shù)據(jù)合并。如果兩條相似重復(fù)記錄是完全重復(fù)記錄，只需刪除兩者之一即可；如果僅是相似重復(fù)記錄，則需將兩條記錄合并為一條新記錄，新記錄中保留被合并的兩條記錄中的關(guān)鍵屬性(排序關(guān)鍵字)和相同屬性，對(duì)于差異化的屬性則根據(jù)具體實(shí)用系統(tǒng)的要求而制定的合并規(guī)則進(jìn)行合并。

2 鄰近排序算法

目前基于“排序-合并”思想的相似重復(fù)記錄檢測(cè)方法有很多，如鄰近排序算法(Sorted-Neighborhood Method,SNM)、多趟近鄰排序算法和優(yōu)先權(quán)隊(duì)列算法等。

多趟近鄰排序算法一般能夠得到較全的相似重復(fù)記錄的集合，降低漏配的可能性，但該算法需多次獨(dú)立地執(zhí)行SNM算法，且每趟執(zhí)行之前需重新創(chuàng)建不同的排序關(guān)鍵字，時(shí)間性能不佳。

優(yōu)先權(quán)隊(duì)列算法借用Union-Find數(shù)據(jù)結(jié)構(gòu)，將記錄根據(jù)相似性程度的不同，分別放在不同的優(yōu)先權(quán)隊(duì)列。這種算法能夠減少記錄的比較次數(shù)，但如采用單趟優(yōu)先權(quán)隊(duì)列算法，很有可能造成相似重復(fù)記錄的漏配，實(shí)際應(yīng)用中多采用多趟優(yōu)先隊(duì)列算法，但這又導(dǎo)致消耗較多的時(shí)間。

SNM算法是比較成熟的相似重復(fù)記錄檢測(cè)算法，它包括以下3步：

1)組建排序關(guān)鍵字。從數(shù)據(jù)表中提取若干關(guān)鍵屬性或?qū)傩灾档囊徊糠肿鳛榕判蜿P(guān)鍵字。被抽取作為排序關(guān)鍵字的屬性通常是對(duì)記錄具有較強(qiáng)區(qū)分度的屬性或?qū)傩宰哟?/p>

2)排序。根據(jù)上步設(shè)定的關(guān)鍵字對(duì)數(shù)據(jù)庫(kù)排序，通過(guò)排序，即可把原來(lái)分散在數(shù)據(jù)庫(kù)不同位置的可能的重復(fù)記錄聚集在一個(gè)鄰近的區(qū)域內(nèi)。為了實(shí)現(xiàn)這一目的，在確定排序關(guān)鍵字時(shí)，需要做更深入的研究。如何確定排序關(guān)鍵字，對(duì)于排序結(jié)果的影響起到關(guān)鍵作用。

3)合并。為數(shù)據(jù)集設(shè)定一個(gè)大小固定的可滑動(dòng)窗口[4]，其大小可根據(jù)經(jīng)驗(yàn)確定，最后進(jìn)入滑動(dòng)窗口的記錄將與窗口內(nèi)的其他記錄逐一比對(duì)。若窗口最多可存放W條記錄，則稱窗口寬度為W。顯然，最后進(jìn)入窗口的記錄只需與窗口中先期進(jìn)入的W-1條記錄進(jìn)行比較，最多判斷W-1次即可確定其是否為相似重復(fù)記錄。若判斷出兩條記錄是相似重復(fù)記錄，則對(duì)它們進(jìn)行合并操作。窗口中的記錄采用先進(jìn)先出的隊(duì)列方式來(lái)組織，一旦處理完一條記錄，則窗口自動(dòng)向下(高地址方向)滑動(dòng)一條記錄的位移，再次進(jìn)行一次新的檢測(cè)與合并操作，如此反復(fù)，直到數(shù)據(jù)集最后。

該算法先通過(guò)排序把可能的相似重復(fù)記錄盡可能地聚集在一起，再引進(jìn)滑動(dòng)窗口，每次只比較窗口中的W-1條記錄，通過(guò)總共N×(W-1)次的比較，實(shí)現(xiàn)相似重復(fù)記錄的檢測(cè)。通常情況下，W總是遠(yuǎn)遠(yuǎn)小于N，所以采用這種方法進(jìn)行相似重復(fù)記錄檢測(cè)，可提高匹配效率和檢測(cè)速度。

但SNM算法仍存在以下不足：

1)排序關(guān)鍵字的選定對(duì)排序結(jié)果影響太大。實(shí)踐表明，排序關(guān)鍵字選取的好壞不僅直接檢測(cè)效率，對(duì)相似性檢測(cè)的精度也有很大影響，如果選取不當(dāng)，還有可能漏配一些重復(fù)記錄。

2)難以適當(dāng)控制滑動(dòng)窗口的大小W。W較小時(shí)可能漏配掉相似重復(fù)記錄；W較大時(shí)，會(huì)導(dǎo)致比較次數(shù)增多，降低檢測(cè)效率；對(duì)于一個(gè)確定的數(shù)據(jù)集，如果重復(fù)記錄聚類數(shù)值差別較大，則根本無(wú)法選擇出較為恰當(dāng)?shù)腤。

3)滑動(dòng)窗口內(nèi)兩條記錄的比較時(shí)間長(zhǎng)。這是因?yàn)樵诨瑒?dòng)窗口內(nèi)，兩條記錄基本上采用笛卡爾成績(jī)方式進(jìn)行字段比較。

3 鄰近排序算法的改進(jìn)思想

針對(duì)SNM算法的不足，做出以下修改：

1)改進(jìn)關(guān)鍵字預(yù)處理方法。由于排序關(guān)鍵字的選定對(duì)SNM算法的排序結(jié)果影響很大，在對(duì)數(shù)據(jù)集進(jìn)行排序之前，提前對(duì)排序關(guān)鍵字做一些預(yù)處理，以進(jìn)一步提高相似重復(fù)記錄集中的效果。具體做法是先用統(tǒng)一的標(biāo)準(zhǔn)格式對(duì)排序關(guān)鍵字中的繁雜表示形式實(shí)現(xiàn)規(guī)格化處理，形成統(tǒng)一格式的數(shù)據(jù)；再對(duì)排序關(guān)鍵字中的單詞進(jìn)行排序處理，以增強(qiáng)數(shù)據(jù)庫(kù)中數(shù)據(jù)排序結(jié)果的單一性[5]。

2)采用可伸縮窗口。為彌補(bǔ)在SNM算法中因滑動(dòng)窗口大小固定而帶來(lái)的不良影響，在改進(jìn)算法中，滑動(dòng)窗口的大小可以隨著已排序記錄聚類規(guī)模的大小來(lái)進(jìn)行自適應(yīng)式的調(diào)整。設(shè)當(dāng)前窗口寬度Wdi為：

(1)

其中：Wd1為最小窗口寬度；Wd2為最大窗口寬度；Match_num為窗口中相似記錄數(shù)目，其取值范圍為[0,Wdi-1]。

由式(1)可知，當(dāng)Match_num變大時(shí)，在該窗口內(nèi)聚集的相似重復(fù)記錄變多，Wdi也隨之變大，即通過(guò)增大滑動(dòng)窗口來(lái)擴(kuò)大相似重復(fù)記錄的檢索范圍，以減少相似重復(fù)記錄遺漏的可能性；當(dāng)Match_num增大到Wdi-1，即意味著整個(gè)滑動(dòng)窗口的記錄均為相似重復(fù)記錄，此時(shí)的Wdi=Wd2。如果當(dāng)前窗口中沒(méi)有相似重復(fù)記錄，則Match_num=0，那么Wdi=Wd1，即通過(guò)縮小滑動(dòng)窗口來(lái)減小比較范圍，以避免過(guò)多的無(wú)效檢索。

4 驗(yàn)證結(jié)果及衡量標(biāo)準(zhǔn)

衡量相似重復(fù)記錄檢測(cè)算法的性能指標(biāo)通常用召回率和誤識(shí)別率來(lái)加以描述。

1)召回率R(Recall)也叫查全率。設(shè)T為數(shù)據(jù)集中的相似重復(fù)記錄的實(shí)際條數(shù)，C為檢測(cè)算法實(shí)際檢測(cè)出來(lái)的相似重復(fù)記錄條數(shù)，則有R=C/T。顯然，R的值域?yàn)閇0,1]，求得的R值越大，表明檢測(cè)算法的查全性能越好。

2)誤識(shí)別率PF(False Percent)也叫失誤率。在相似重復(fù)記錄檢測(cè)過(guò)程中，算法錯(cuò)誤地判定為重復(fù)記錄的數(shù)目用F表示，被算法判定為重復(fù)記錄的總數(shù)用A表示，則PF=F/A。PF越低，算法判別的準(zhǔn)確性越高。

實(shí)驗(yàn)數(shù)據(jù)來(lái)自于當(dāng)?shù)匾患忆N售公司的部分客戶信息數(shù)據(jù)集，該部分?jǐn)?shù)據(jù)集共有1 218條記錄，數(shù)據(jù)表含有姓名、性別、身份證號(hào)碼、通信地址、聯(lián)系電話、單位名稱、單位地址、辦公電話共8個(gè)屬性。在實(shí)驗(yàn)中設(shè)定相似度閾值U=0.85，表2記錄了4種不同情況下的檢測(cè)結(jié)果。

實(shí)驗(yàn)表明，在傳統(tǒng)SNM算法的基礎(chǔ)上，適當(dāng)修改算法，采取諸如對(duì)排序關(guān)鍵字進(jìn)行統(tǒng)一數(shù)據(jù)格式處理、對(duì)排序關(guān)鍵字中的單詞進(jìn)行排序、根據(jù)屬性對(duì)記錄的區(qū)分度不同為部分屬性設(shè)置權(quán)重值，在進(jìn)行相似重復(fù)記錄檢測(cè)時(shí)采用可伸縮窗口等措施，能夠顯著改善SNM算法的性能。此外，改進(jìn)后的SNM算法相較于多趟近鄰排序算法，具有更加優(yōu)越的時(shí)間性能；而相較于單趟優(yōu)先權(quán)隊(duì)列算法，改進(jìn)后的SNM算法則具有更好的查全性能。

5 結(jié)語(yǔ)

本文針對(duì)SNM算法的不足，提出了一些改進(jìn)措施。通過(guò)排序關(guān)鍵字的預(yù)處理，提高記錄聚類的速度；采用伸縮窗口思維可以使滑動(dòng)窗口的大小，自動(dòng)跟隨滑動(dòng)窗口內(nèi)的相似重復(fù)記錄的數(shù)目呈現(xiàn)正相關(guān)的變化，既能避免過(guò)多的無(wú)效檢索，又能進(jìn)一步減少相似重復(fù)記錄因窗口固定大小而被遺漏的可能。為關(guān)鍵屬性或其部分屬性設(shè)置權(quán)重值，只需對(duì)設(shè)有權(quán)重值的屬性進(jìn)行比較，省略了非關(guān)鍵屬性的比較，明顯加快了窗口內(nèi)兩條記錄的比較速度。但本改進(jìn)算法也還存在一些不足，主要是：1)窗口內(nèi)兩條記錄的比對(duì)沒(méi)能找到更加高效的算法，導(dǎo)致整個(gè)檢測(cè)算法的時(shí)間性能還有待提高；2)伸縮窗口的引入，確實(shí)提升了SNM算法的性能，但依然存在極少數(shù)相似重復(fù)記錄漏配的現(xiàn)象。此外，實(shí)驗(yàn)系統(tǒng)的數(shù)據(jù)集規(guī)模偏小，可能掩蓋了改進(jìn)算法的某些缺點(diǎn)等，這將是今后工作的研究重點(diǎn)。

[1]HAN J,KAMBER M.Data mining: concepts and techniques[M].2版.北京：高等教育出版社,2011:1-18.

[2]劉喜文,鄭昌興,王文龍,等.構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)過(guò)程中的數(shù)據(jù)清洗研究[J].圖書與情報(bào),2013(5):22-28.

[3]郭志懋,周傲英.數(shù)據(jù)質(zhì)量和數(shù)據(jù)清洗研究綜述[J].軟件學(xué)報(bào),2002,13(11):2076-2082.

[4]謝文閣,佟玉軍,賈丹,等.數(shù)據(jù)清洗中重復(fù)記錄清洗算法的研究[J].軟件工程師,2015,18(9):61-62.

[5]戴穎,李興國(guó),趙啟飛.一種相似重復(fù)記錄檢測(cè)算法的改進(jìn)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010,20(7):13-16.

Improvement and Application of a Detection Algorithm for
Similar and Duplicated Records

LIJun

(School of Information Engineering,Anhui Vocational and Technical College,Hefei 230011,China)

In the age of big data,the research of data cleaning algorithm is very important.This paper briefly introduces the concept of data cleaning and detection algorithm for similar duplicate records,then introduces the principle of cleaning the similar duplicate records.The Sorted-Neighborhood Method(SNM) is analyzed and studied and its shortcomings are pointed out,based on this improved strategy and application,the practice proves that the improved algorithm,the key performance is significantly improved.

big data；data cleaning；similar duplicate record

10.13542/j.cnki.51-1747/tn.2017.02.004

2017-05-09

李軍(1967—),男，講師，碩士，研究方向：數(shù)據(jù)挖掘、智能算法，電子郵箱：wodejiaren2017@126.com。

TP311

A

2095-5383(2017)02-0017-04