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

郭文龍，董建懷

福建江夏學院電子信息科學學院，福建 福州 350108

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

郭文龍，董建懷

福建江夏學院電子信息科學學院，福建 福州 350108

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

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

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

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

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

殷秀葉［5］提出了屬性加權和同義屬性的概念對相似重復記錄進行判定.文獻［6］通過計算記錄字段間的相似度，組成特征向量；然后采用改進的量子粒子群優化算法優化反向傳播（back propaga?tion，BP）神經網絡進行學習，建立最優相似重復記錄檢測模型.李鑫等提出了一種分組模糊聚類的特征優選方法，首先進行分組記錄的屬性處理，然后采用一種相似度比較計算方法進行組內相似重復記錄的檢測［7］.周典瑞等采用綜合加權法和基于字符串長度過濾法對數據集進行相似重復檢測［8］.然而這些方法的屬性權值均是人為主觀設置，未能體現不同屬性的重要性程度.針對屬性權值確定主觀性過強的問題，肖滿生等提出基于數據分組和模糊綜合評判的相似重復記錄識別方法，該方法能較客觀反映屬性的重要性程度，取得較高的識別精度［9-10］.文獻［11］提出一種基于長度過濾的SNM改進算法，首先在窗口內根據兩條記錄的長度比例將構成相似重復記錄可能性極小的數據排除在外，減少了記錄比較的次數，提高了檢測效率，為了降低因屬性缺失等因素對判重的影響，進一步提出添加屬性有效性因子并通過設定可變權值的方法取得了一定的效果.劉雅思等提出動態容錯法，解決了因屬性缺失而誤判的問題，提高了準確率［12］.然而文獻［11-12］中的權值仍然憑借單用戶主觀設定.

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

1 相關算法描述

1.1 模糊綜合評判法

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

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

1.2 SNM算法

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

SNM算法的主要過程如下：

1）排序.根據屬性的重要性程度，選擇重要性程度高的一個關鍵字或若干個關鍵字的組合作為排序關鍵字，對數據記錄集進行排序.經排序后，潛在的相似重復記錄將被調整到相鄰或鄰近的一個范圍內.

2）歸并.設置固定長度的窗口，將第一條記錄依次和窗口內的其他記錄匹配，如果構成相似重復記錄則合并處理.當前窗口處理完畢，將窗口內第一條記錄移除，然后將當前窗口內最后一條記錄的下一條相鄰記錄移入窗口，循環執行匹配的過程.

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

1.3 長度過濾算法

針對大數據集，相似重復記錄所占比例較小，如果在相似重復記錄識別前首先將不可能構成相似重復的記錄排除在外，顯然可以提高檢測效率.長度過濾算法是根據兩個字符串的長度比例找出每條記錄的可能相似重復數據集范圍的方法［11］.然而，實際數據庫中的記錄常出現屬性缺失或屬性采用簡寫方式輸入等情況，如在有些數據庫中地址屬性不是必填項，可能出現缺失也可能采用簡寫輸入，而地址字符串長度在記錄總字符串長度中的占比較高，此時再單純進行記錄長度過濾顯然存在偏差.

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

2 模糊綜合評判法計算權值

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

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

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

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

表1 等級評價Tab.1 Grade evaluation

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

4）計算屬性權值：

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

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

經過濾后，和窗口內第一條記錄可能構成相似重復的數據集變小了，接下來則只要在窗口內可能構成相似重復的數據集中進行判重即可.一個窗口判重結束，向下滑動窗口，循環執行這一過程.

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

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

輸出：相似重復記錄集

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

for（i=0，i＜L，i++）∕∕L表示數據集大小

｛

數據集格式化處理；

數據清洗預處理；

｝

根據模糊綜合評判的屬性權值，按權值高的字段或字段組合對數據集進行排序；

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

｛

4 實驗部分

4.1 實驗環境

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

軟件環境：操作系統WIN7，數據庫軟件SQL Serve2005，算法在VC++6.0中編譯運行.

4.2 評價方案

衡量清洗算法優劣標準的通常做法是計算查重的查全率和查準率，設C表示數據集中實際的重復記錄，T表示檢測出來的重復記錄，F表示檢測出來的錯誤的重復記錄，則查全率R和查準率P的定義如下：

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

4.3 實驗過程

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

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

4.4 實驗結果分析

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

圖1 查準率比較Fig.1 Comparison of precision ratio

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

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

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

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

5 結 語

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

［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］葉煥倬，吳迪.相似重復記錄清理方法研究綜述［J］.現代圖書情報技術，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］陳爽，宋金玉，刁興春，等.基于伸縮窗口和等級調整的SNM改進方法［J］.計算機應用研究，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］殷秀葉.大數據環境下的相似重復記錄檢測方法［J］.武漢工程大學學報，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］陳芬.改進量子粒子群算法優化神經網絡的數據庫重復記錄檢測［J］.計算機應用與軟件，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］李鑫，李軍，豐繼林，等.面向相似重復記錄檢測的特征優選方法［J］.傳感器與微系統，2011，30（2）：37-40.LI X，LI J，FENG 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］周典瑞，周蓮英.海量數據的相似重復記錄檢測算法［J］.計算機應用，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］周麗娟，肖滿生.基于數據分組匹配的相似重復記錄檢測［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］肖滿生，周浩慧，王宏.基于模糊綜合評判的相似重復記錄識別方法［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］郭文龍.基于長度過濾和有效權值的SNM改進算法［J］.計算機工程與應用，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］劉雅思，程力，李曉.基于長度過濾和動態容錯的SNM 改進算法［J］.計算機應用研究，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］劉河香.模糊數學理論及其應用［M］.北京：科學出版社，2012.

［14］張勝禮，李永明.廣義模糊集GFScom在模糊綜合評判中的應用［J］.計算機科學，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改進算法的相似重復記錄消除［J］.重慶理工大學學報（自然科學版），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，Fujian Jiangxia University，Fuzhou 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

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

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

郭文龍，董建懷.基于模糊綜合評判和長度過濾的SNM改進算法［J］.武漢工程大學學報，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