李 軍

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

一種相似重復記錄檢測算法的改進與應用

李 軍

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

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

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

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

1 相似重復記錄清洗

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

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

表1 相似重復記錄實例

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

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

圖1 相似重復記錄的清洗過程

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

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

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

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

2 鄰近排序算法

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

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

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

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

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

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

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

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

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

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

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

3)滑動窗口內(nèi)兩條記錄的比較時間長。這是因為在滑動窗口內(nèi)，兩條記錄基本上采用笛卡爾成績方式進行字段比較。

3 鄰近排序算法的改進思想

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

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

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

(1)

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

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

4 驗證結(jié)果及衡量標準

衡量相似重復記錄檢測算法的性能指標通常用召回率和誤識別率來加以描述。

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

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

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

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

5 結(jié)語

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

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

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

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

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

[5]戴穎,李興國,趙啟飛.一種相似重復記錄檢測算法的改進研究[J].計算機技術與發(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