郭文龍，董建懷

福建江夏學(xué)院電子信息科學(xué)學(xué)院，福建 福州 350108

基于模糊綜合評判和長度過濾的SNM改進算法

郭文龍，董建懷

福建江夏學(xué)院電子信息科學(xué)學(xué)院，福建 福州 350108

為了提高數(shù)據(jù)庫的數(shù)據(jù)質(zhì)量，需要對相似重復(fù)記錄進行清洗，基本鄰近排序算法是目前常用的清洗算法之一.針對判重過程中屬性權(quán)值計算主觀性過強的問題，提出通過多用戶綜合評判確定屬性權(quán)值的方法，該方法能更客觀地評判屬性的重要性程度.在此基礎(chǔ)上，結(jié)合屬性權(quán)值計算兩條記錄的長度比例，排除不可能構(gòu)成相似重復(fù)的記錄，減少了比較次數(shù)，提高了檢測效率.實驗結(jié)果表明改進算法在查全率、查準(zhǔn)率及時間效率等方面均有所提高.

相似重復(fù)記錄；模糊綜合評判；屬性；長度過濾；SNM；算法

當(dāng)前，全球各行各業(yè)均組建了可以管理和推廣自身業(yè)務(wù)的管理信息系統(tǒng)，如何有效管理和利用各類數(shù)據(jù)資源，是科學(xué)研究和決策支持的前提.隨著信息化水平的不斷提高，全球的各類數(shù)據(jù)庫中存儲的數(shù)據(jù)都呈現(xiàn)井噴式的增長.諸如銀行、證券公司、通信公司等數(shù)據(jù)庫的存儲量均在百萬以上，且可以預(yù)見隨業(yè)務(wù)擴張的趨勢將繼續(xù)推動數(shù)據(jù)增長；而政府的人口基礎(chǔ)數(shù)據(jù)庫的數(shù)據(jù)量更是以億計.在這些數(shù)據(jù)量龐大的數(shù)據(jù)庫中存在著諸多重復(fù)數(shù)據(jù)，如何清理相似重復(fù)數(shù)據(jù)便成了亟需解決的問題.

目前常用的相似重復(fù)記錄清洗算法是基本鄰近排序算法（basic sorted-neighborhood method，SNM）［1-3］.該算法基于排序和合并的思路，通過關(guān)鍵字對數(shù)據(jù)記錄進行排序，再在一定的窗口內(nèi)比較臨近的數(shù)據(jù)記錄是否構(gòu)成相似重復(fù)記錄，如果構(gòu)成重復(fù)記錄則合并.由于算法簡單且易于實現(xiàn)，所以得到了大量的應(yīng)用［4］.

相似重復(fù)記錄的識別通常由兩個步驟實現(xiàn)，第一步是逐一對記錄屬性進行匹配，第二步綜合考慮所有屬性的相似度并計算兩條記錄的相似度，最后通過事先設(shè)定的閾值判定兩條記錄是否構(gòu)成相似重復(fù)記錄.而在綜合考慮所有屬性的相似度并計算兩條記錄的相似度前必須為記錄的所有屬性設(shè)置權(quán)值，逐一利用屬性權(quán)值乘以屬性匹配度，方可客觀地判斷兩條記錄是否相似重復(fù)，所以屬性權(quán)值的設(shè)置便成了判重的關(guān)鍵.

殷秀葉［5］提出了屬性加權(quán)和同義屬性的概念對相似重復(fù)記錄進行判定.文獻［6］通過計算記錄字段間的相似度，組成特征向量；然后采用改進的量子粒子群優(yōu)化算法優(yōu)化反向傳播（back propaga?tion，BP）神經(jīng)網(wǎng)絡(luò)進行學(xué)習(xí)，建立最優(yōu)相似重復(fù)記錄檢測模型.李鑫等提出了一種分組模糊聚類的特征優(yōu)選方法，首先進行分組記錄的屬性處理，然后采用一種相似度比較計算方法進行組內(nèi)相似重復(fù)記錄的檢測［7］.周典瑞等采用綜合加權(quán)法和基于字符串長度過濾法對數(shù)據(jù)集進行相似重復(fù)檢測［8］.然而這些方法的屬性權(quán)值均是人為主觀設(shè)置，未能體現(xiàn)不同屬性的重要性程度.針對屬性權(quán)值確定主觀性過強的問題，肖滿生等提出基于數(shù)據(jù)分組和模糊綜合評判的相似重復(fù)記錄識別方法，該方法能較客觀反映屬性的重要性程度，取得較高的識別精度［9-10］.文獻［11］提出一種基于長度過濾的SNM改進算法，首先在窗口內(nèi)根據(jù)兩條記錄的長度比例將構(gòu)成相似重復(fù)記錄可能性極小的數(shù)據(jù)排除在外，減少了記錄比較的次數(shù)，提高了檢測效率，為了降低因?qū)傩匀笔У纫蛩貙ε兄氐挠绊?，進一步提出添加屬性有效性因子并通過設(shè)定可變權(quán)值的方法取得了一定的效果.劉雅思等提出動態(tài)容錯法，解決了因?qū)傩匀笔Ф`判的問題，提高了準(zhǔn)確率［12］.然而文獻［11-12］中的權(quán)值仍然憑借單用戶主觀設(shè)定.

筆者結(jié)合文獻［10-12］的思想提出了基于模糊綜合評判和長度過濾的相似重復(fù)記錄檢測方法，主要思路為：采用模糊綜合評判方法確定屬性權(quán)值，提高判重精度；在檢測相似重復(fù)記錄前，采用長度過濾并充分考慮屬性缺失的影響，排除不可能構(gòu)成相似重復(fù)的記錄，減少記錄的比較次數(shù)，從而提高檢測效率；基于SNM算法思想對數(shù)據(jù)記錄集進行檢測.

1 相關(guān)算法描述

1.1 模糊綜合評判法

模糊綜合評判法是基于模糊數(shù)學(xué)的評價法，也就是用模糊數(shù)學(xué)對現(xiàn)實世界中多種相互制約和關(guān)聯(lián)的事物做出定量的評價［13］.該方法可以將定性評價轉(zhuǎn)為定量評價，可以較好解決非確定性的難以量化的評價問題［14］.

在相似重復(fù)記錄的屬性權(quán)重計算中，可以通過多個用戶分別對屬性進行等級評價，然后取這些評價的平均值，通過模糊綜合評判可以更客觀的反映屬性的重要性程度.

1.2 SNM算法

該算法由Hernandez M等人提出，其主要思路是先利用關(guān)鍵字或關(guān)鍵字的組合對所有數(shù)據(jù)進行排序，然后設(shè)定一個固定長度的窗口，在窗口內(nèi)進行相似重復(fù)記錄檢測，隨后滑動窗口，重復(fù)查重的過程［1-3，15］.

SNM算法的主要過程如下：

1）排序.根據(jù)屬性的重要性程度，選擇重要性程度高的一個關(guān)鍵字或若干個關(guān)鍵字的組合作為排序關(guān)鍵字，對數(shù)據(jù)記錄集進行排序.經(jīng)排序后，潛在的相似重復(fù)記錄將被調(diào)整到相鄰或鄰近的一個范圍內(nèi).

2）歸并.設(shè)置固定長度的窗口，將第一條記錄依次和窗口內(nèi)的其他記錄匹配，如果構(gòu)成相似重復(fù)記錄則合并處理.當(dāng)前窗口處理完畢，將窗口內(nèi)第一條記錄移除，然后將當(dāng)前窗口內(nèi)最后一條記錄的下一條相鄰記錄移入窗口，循環(huán)執(zhí)行匹配的過程.

由于該方法限定記錄的匹配在窗口內(nèi)進行，所以極大提高了判重效率.

1.3 長度過濾算法

針對大數(shù)據(jù)集，相似重復(fù)記錄所占比例較小，如果在相似重復(fù)記錄識別前首先將不可能構(gòu)成相似重復(fù)的記錄排除在外，顯然可以提高檢測效率.長度過濾算法是根據(jù)兩個字符串的長度比例找出每條記錄的可能相似重復(fù)數(shù)據(jù)集范圍的方法［11］.然而，實際數(shù)據(jù)庫中的記錄常出現(xiàn)屬性缺失或?qū)傩圆捎煤唽懛绞捷斎氲惹闆r，如在有些數(shù)據(jù)庫中地址屬性不是必填項，可能出現(xiàn)缺失也可能采用簡寫輸入，而地址字符串長度在記錄總字符串長度中的占比較高，此時再單純進行記錄長度過濾顯然存在偏差.

針對上述問題，結(jié)合模糊綜合評判計算出的屬性權(quán)重，本文提出改進的長度過濾方法.設(shè)C表示待檢測的數(shù)據(jù)記錄集，n表示數(shù)據(jù)量，Ri表示第i條記錄，Rj表示第 j條記錄，則 C=｛R1，R2，……，Rn｝.設(shè)記錄有m個屬性，經(jīng)模糊綜合評判后計算出來的第k個屬性權(quán)值為 Wk（0≤k≤m）.設(shè) Len（Rik）表示第i條記錄的第k個屬性值長度，u表示預(yù)先設(shè)置的長度比例閾值，則當(dāng)兩條記錄的長度比例低于u時認為這兩條記錄不構(gòu)成相似重復(fù)記錄，即當(dāng)時，應(yīng)將記錄 Ri排除在記錄Rj的相似重復(fù)記錄集外.

2 模糊綜合評判法計算權(quán)值

記錄屬性反映實體的某個特征，但每個屬性在實體中的重要程度不同，屬性權(quán)值可以有效衡量屬性的重要程度.對于相同的屬性集，每個用戶由于主觀性不同，如果單獨設(shè)置屬性權(quán)值必然會不一致.在相似重復(fù)記錄清洗中，采用單一用戶設(shè)置的屬性權(quán)值來判重顯然欠合理，采用多用戶模糊綜合評判來設(shè)置屬性權(quán)值可以很好地解決這個問題.

基于上述思想，記錄屬性權(quán)值的計算方法如下：

1）設(shè)數(shù)據(jù)集的記錄屬性有m個，按照其重要性將屬性等級設(shè)置為1～m，其中1表示該屬性重要性最低、m表示該屬性重要性最高.

2）組織s個不同用戶分別對記錄集的屬性進行等級評價，結(jié)果如表1所示.

表1 等級評價Tab.1 Grade evaluation

其中，Gij表示第i個用戶對第j個屬性的等級評價.

4）計算屬性權(quán)值：

3 基于模糊綜合評判和長度過濾的改進算法

基于SNM算法通過實驗設(shè)定滿足要求的窗口大小N，窗口內(nèi)的記錄利用記錄屬性長度過濾掉不可能構(gòu)成相似重復(fù)的記錄，減少數(shù)據(jù)記錄的比較次數(shù).設(shè)W_C表示窗口內(nèi)待檢測數(shù)據(jù)記錄集，Ri表示第i條記錄，記錄有m個屬性，長度閾值為u，權(quán)值向量為W，增設(shè)長度過濾標(biāo)志數(shù)組flag［N］，初始化狀態(tài)flag數(shù)組元素全部置0.判重前窗口內(nèi)第一條記錄和窗口內(nèi)其他記錄進行長度過濾，如果窗口內(nèi)某一記錄Ri和窗口內(nèi)第一條記錄R1長度比小于長度閾值u，則flag［i］置1.在窗口內(nèi)依據(jù)長度過濾非相似重復(fù)記錄算法如下：

經(jīng)過濾后，和窗口內(nèi)第一條記錄可能構(gòu)成相似重復(fù)的數(shù)據(jù)集變小了，接下來則只要在窗口內(nèi)可能構(gòu)成相似重復(fù)的數(shù)據(jù)集中進行判重即可.一個窗口判重結(jié)束，向下滑動窗口，循環(huán)執(zhí)行這一過程.

基于如上分析，記錄清洗算法描述如下：

輸入：數(shù)據(jù)記錄集C，屬性權(quán)重向量W，滑動窗口大小N，記錄相似度閾值t，長度比例閾值u

輸出：相似重復(fù)記錄集

Input（C，W，N，t，u）

for（i=0，i＜L，i++）∕∕L表示數(shù)據(jù)集大小

｛

數(shù)據(jù)集格式化處理；

數(shù)據(jù)清洗預(yù)處理；

｝

根據(jù)模糊綜合評判的屬性權(quán)值，按權(quán)值高的字段或字段組合對數(shù)據(jù)集進行排序；

for（i=0，i＜L-N+1，i++） ∕∕根據(jù)設(shè)定的窗口大小，總共需滑動L-N+1次窗口

｛

4 實驗部分

4.1 實驗環(huán)境

實驗硬件配置：intel（R）Core（TM）i3-3110M CPU@2.40 GHz，內(nèi)存4.0 GB，硬盤空間500 GB.

軟件環(huán)境：操作系統(tǒng)WIN7，數(shù)據(jù)庫軟件SQL Serve2005，算法在VC++6.0中編譯運行.

4.2 評價方案

衡量清洗算法優(yōu)劣標(biāo)準(zhǔn)的通常做法是計算查重的查全率和查準(zhǔn)率，設(shè)C表示數(shù)據(jù)集中實際的重復(fù)記錄，T表示檢測出來的重復(fù)記錄，F(xiàn)表示檢測出來的錯誤的重復(fù)記錄，則查全率R和查準(zhǔn)率P的定義如下：

除了查全率和查準(zhǔn)率外，運行速度也是算法優(yōu)劣評判的指標(biāo)之一.本文算法主要在文獻［11］的基礎(chǔ)上改進，故其性能通過在相同的數(shù)據(jù)集上分別對比文獻［11］算法的查全率、查準(zhǔn)率及運行時間來分析.

4.3 實驗過程

實驗數(shù)據(jù)來自某地人口基礎(chǔ)數(shù)據(jù)庫，共包含76.3萬條記錄和31個屬性.實驗中分別隨機提取2萬條、4萬條及6萬條數(shù)據(jù)量，基于人工和軟件結(jié)合方法將數(shù)據(jù)集依次處理成包含407條、823條及1 478條的相似重復(fù)記錄集，實驗后檢測出來的重復(fù)記錄數(shù)及正確的相似重復(fù)記錄數(shù)由人工方式統(tǒng)計.

在實驗中共組織100個用戶對記錄屬性進行等級評判，相似度閾值設(shè)為0.9，長度閾值設(shè)為0.8.在同樣的數(shù)據(jù)集合上，分別利用文獻［11］算法和本文算法進行判重，通過分別計算兩種算法的查全率、查準(zhǔn)率及運行時間并進行對比.

4.4 實驗結(jié)果分析

在相同的數(shù)據(jù)集上分別對文獻［11］算法及本文算法進行實驗，為了描述方便，將文獻［11］算法稱為原算法，而將本文算法稱為改進算法.根據(jù)以上所述方法，分別統(tǒng)計兩種算法的查全率、查準(zhǔn)率及運行時間，并整合繪制成圖來表示，其結(jié)果如圖1～圖3所示.

圖1 查準(zhǔn)率比較Fig.1 Comparison of precision ratio

圖2 查全率比較Fig.2 Comparison of recall ratio

從圖1和圖2中可以看出，改進算法不管是查準(zhǔn)率還是查全率均比原算法有所提高.文獻［11］首先根據(jù)單用戶的主觀意識設(shè)置屬性權(quán)值，然后基于SNM算法在窗口內(nèi)對數(shù)據(jù)記錄進行長度過濾.而改進算法基于多用戶對記錄集的屬性進行模糊綜合評判，進而計算出屬性權(quán)值，此方法必然能更客觀地反映出記錄屬性的重要程度.此外，改進算法在長度過濾時再次利用到模糊綜合評判法計算出來的屬性權(quán)值，首先依次計算出兩條記錄每個屬性的長度，然后分別利用兩條記錄各自的屬性長度依次乘以前面計算出來的對應(yīng)的屬性權(quán)值，再把計算出來的兩個結(jié)果進行相除得出一個值，根據(jù)其值和事先設(shè)定的記錄相似度閾值進行比較，如果超過閾值則表示兩條記錄重復(fù)，否則兩條記錄不構(gòu)成相似重復(fù).改進算法在長度過濾時充分考慮到屬性值缺失的情況，如果記錄的某個屬性值缺失則該屬性長度為0，這更能客觀反應(yīng)兩條記錄的相似重復(fù)情況.綜上，改進算法的查全率及查準(zhǔn)率必然有所提高.

圖3 運行時間比較Fig.3 Comparison of running time

從圖3中可以看出，對于同樣的數(shù)據(jù)量，改進算法在運行時間上均比原算法有所減少.判重算法中均涉及到排序的操作，而排序操作所耗費的時間一致，兩種算法均采用了長度過濾的方法，花費的時間也一致.但是原算法采用添加屬性有效性因子并在算法運行過程中根據(jù)實際情況調(diào)整屬性權(quán)值，這必然耗費了時間，所以運行時間更長.從圖3中可知，隨著數(shù)據(jù)量增大，兩種算法的時間差越大，這說明改進算法的時間效率更高.

5 結(jié) 語

當(dāng)前，數(shù)據(jù)呈現(xiàn)井噴式增長，各類數(shù)據(jù)庫中所包含的相似重復(fù)記錄不斷增多，清洗相似重復(fù)記錄也變得日趨重要.基于相關(guān)文獻，本文提出基于模糊綜合評判計算屬性權(quán)值，更客觀地反映出屬性重要性程度.在此基礎(chǔ)上，充分考慮屬性缺失等情況，利用模糊綜合評判的屬性權(quán)值計算記錄長度，將不可能構(gòu)成相似重復(fù)的記錄過濾掉，進一步減少判重過程中的匹配次數(shù).實驗證明，改進算法一定程度提高了判重的精度和時間效率.然而，在相似重復(fù)記錄清洗過程中相似度閾值及長度閾值的設(shè)置問題仍是一個值得探討的問題，兩者設(shè)置過大或過小都將對查重精度產(chǎn)生影響，這將是今后應(yīng)繼續(xù)研究的問題.

［1］HERNANDEZ M，STOLFO S.The merge∕purge problem forlargedatabases［C］∕∕ProceedingsoftheACM SIGMOD international conference on management of data.California：San Jose，1995：127-138.

［2］HERNANDEZ M，STOLFO S.Real-world data is dirty：data cleansing and the merge∕purge problem［J］.Data Mining and Knowledge Discovery，1998，2（1）：9-37.

［3］葉煥倬，吳迪.相似重復(fù)記錄清理方法研究綜述［J］.現(xiàn)代圖書情報技術(shù)，2010，26（9）：56-66.YE H Z，WU D.A survey of approximately duplicate data cleaning method［J］.New Technology of Library and Information Service，2010，26（9）：56-66.

［4］陳爽，宋金玉，刁興春，等.基于伸縮窗口和等級調(diào)整的SNM改進方法［J］.計算機應(yīng)用研究，2013，30（9）：2736-2739.CHEN S，SONG J Y，DIAO X C，et al.Amelioration method of SNM based on flexible window and ranking adjusting［J］.Application Research ofComputers，2013，30（9）：2736-2739.

［5］殷秀葉.大數(shù)據(jù)環(huán)境下的相似重復(fù)記錄檢測方法［J］.武漢工程大學(xué)學(xué)報，2014，36（9）：66-69.YIN X Y.Method for detecting approximately duplicate database records in big data environment［J］.Journal of Wuhan Institute of Technology，2014，36（9）：66-69.

［6］陳芬.改進量子粒子群算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)庫重復(fù)記錄檢測［J］.計算機應(yīng)用與軟件，2014，31（3）：20-21，115.CHEN F.Database duplicate records detection using neuralnetwork optimized by iqpso［J］.Computer Applications and Software，2014，31（3）：20-21，115.

［7］李鑫，李軍，豐繼林，等.面向相似重復(fù)記錄檢測的特征優(yōu)選方法［J］.傳感器與微系統(tǒng)，2011，30（2）：37-40.LI X，LI J，F(xiàn)ENG J L，et al.An optimal feature selection method for approximately duplicate records detecting ［J］. Transducer and Microsystem Technologies，2011，30（2）：37-40.

［8］周典瑞，周蓮英.海量數(shù)據(jù)的相似重復(fù)記錄檢測算法［J］.計算機應(yīng)用，2013，33（8）：2208-2211.ZHOU D R，ZHOU L Y.Algorithm for detecting approximate duplicate records in massive data［J］.Journal of Computer Applications，2013，33（8）：2208-2211.

［9］周麗娟，肖滿生.基于數(shù)據(jù)分組匹配的相似重復(fù)記錄檢測［J］.計算機工程，2010，36（12）：104-106.ZHOU L J，XIAO M S.Detection of approximately duplicated records based on data grouping matching［J］.Computer Engineering，2010，36（12）：104-106.

［10］肖滿生，周浩慧，王宏.基于模糊綜合評判的相似重復(fù)記錄識別方法［J］.計算機工程，2010，36（13）：51-53.XIAO M S，ZHOU H H，WANG H.Identification method of approximately duplicate records based on fuzzy integrated estimation［J］.Computer Engineering，2010，36（13）：51-53.

［11］郭文龍.基于長度過濾和有效權(quán)值的SNM改進算法［J］.計算機工程與應(yīng)用，2014，50（19）：123-127.GUO W L.Improved SNM algorithm based on length filtering and effective weights［J］.Computer Engineer?ing and Applications，2014，50（19）：123-127.

［12］劉雅思，程力，李曉.基于長度過濾和動態(tài)容錯的SNM 改進算法［J］.計算機應(yīng)用研究，2017，34（1）：147-150.LIU Y S，CHENG L，LI X.Improved SNM algorithm based on length filtering and dynamic fault-tolerance［J］.Application Research of Computers，2017，34（1）：147-150.

［13］劉河香.模糊數(shù)學(xué)理論及其應(yīng)用［M］.北京：科學(xué)出版社，2012.

［14］張勝禮，李永明.廣義模糊集GFScom在模糊綜合評判中的應(yīng)用［J］.計算機科學(xué)，2015，42（7）：125-128，161.ZHANG S L，LI Y M.Application of generalized fuzzy sets GFScom to fuzzy comprehensive evaluation［J］.Computer Science，2015，42（7）：125-128，161.

［15］余肖生，胡孫枝.基于SNM改進算法的相似重復(fù)記錄消除［J］.重慶理工大學(xué)學(xué)報（自然科學(xué)版），2016，30（4）：91-96.YU X S，HU S Z.Research on eliminating duplicate records based on SNM improved algorithm［J］.Journal ofChongqing University ofTechnology（Natural Science），2016，30（4）：91-96.

本文編輯：陳小平

Improved SNM Algorithm Based on Fuzzy Comprehensive Evaluation and Length Filtering

GUO Wenlong，DONG Jianhuai
College of Electronics and Information Science，F(xiàn)ujian Jiangxia University，F(xiàn)uzhou 350108，China

To improve the quality of data，the approximately duplicated records need to be cleaned.The basic sorted-neighborhood method（SNM）is one of the commonly used cleaning algorithms.Aimed at the problem of excessive subjectivity of attribute weight calculation in detection algorithm，the article proposes a method based on the fuzzy comprehensive evaluation of multiuser to determine the attribute weight，which can be more objective to judge the importance level of the attribute.The proposed algorithm calculates the length ratio of the two records with attribute weight，then uses the length ratio to exclude records that are impossible to be approximately duplicated，reduces comparison times，and improves the detection efficiency.The experiment results show that the recall，precision and time efficiency are enhanced.

approximately duplicated records；fuzzy comprehensive evaluation；attribute；length filtering；SNM；algorithm

TP311

A

10.3969∕j.issn.1674?2869.2017.04.015

2017-04-08

福建省自然科學(xué)基金（2015J01653）；福建江夏學(xué)院青年科研人才培育基金（JXZ2014011）

郭文龍，碩士，副教授.E-mail：wlg1688@sina.com

郭文龍，董建懷.基于模糊綜合評判和長度過濾的SNM改進算法［J］.武漢工程大學(xué)學(xué)報，2017，39（4）：403-408.

GUO W L，DONG J H.The improved SNM algorithm based on the fuzzy comprehensive evaluation and length filtering［J］.Journal of Wuhan Institute of Technology，2017，39（4）：403-408.

1674-2869（2017）04-0403-06