基于SNM改進算法的相似重復記錄消除

余肖生， 胡孫枝

(三峽大學 計算機與信息學院,湖北 宜昌　443002)

?

基于SNM改進算法的相似重復記錄消除

余肖生， 胡孫枝

(三峽大學 計算機與信息學院,湖北 宜昌443002)

摘要：高質量的數據是構建數據倉庫的最重要因素，低質量的數據可能對決策產生不利影響。來自不同數據源的相似重復記錄是數據倉庫構建中影響數據質量的主要問題之一，在源數據進入數據倉庫之前盡可能地消除相似重復記錄能很大程度地提高數據質量。為此，比較了現有的相似重復記錄消除算法，改進了SNM算法，并通過實驗比較了傳統SNM方法與改進SNM算法。實驗結果顯示：在相似重復記錄消除方面，SNM改進算法具有明顯的優勢。

關鍵詞：SNM算法；SNM改進算法；相似重復記錄消除

在企業中，各級管理人員需要面對不同層次的大量信息，并需要分析這些信息，以便及時了解市場變化，做出正確有效的判斷和決策。為了保證信息的正確性和有效性，企業通常利用長期積累的分散數據構建自己的數據倉庫，然后利用數據挖掘工具從企業數據倉庫中獲得用于支持管理決策的戰略信息[1]。由于長期積累的數據往往是海量的和分散的，存在數據錯誤、數據丟失、格式不統一、規則不一致等多種問題，因此導致從數據倉庫挖掘出的信息不能有效地支持管理決策。高質量的數據可能是數據倉庫成功的最重要因素[2]，而低質量的數據可能對決策產生不利影響[3-4]。在數據倉庫構建的眾多數據質量問題中，來自不同數據源的相似重復記錄占有相對較大的比例。數據倉庫中的相似重復記錄直接影響著信息的有效性，因此在源數據進入數據倉庫之前盡可能地消除相似重復記錄能很大程度提高數據質量，對成功構建數據倉庫具有深遠的意義。

本文比較了現有相似重復記錄消除算法，并改進了SNM算法。通過實驗比較傳統SNM方法與改進SNM算法，結果顯示：在相似重復記錄消除方面，SNM改進算法具有明顯的優勢。

1現有相似重復記錄消除算法的比較

相似重復記錄是指對于現實世界中同一個實體，在各個數據源數據庫或平面文件中存儲時，由于可能出現格式錯誤、結構不一致、拼寫差異等問題導致數據庫管理系統沒有正確識別而產生的兩條或者多條不完全相同的記錄[5]。相似重復記錄是導致數據倉庫構建中數據質量不符合標準的最常見的問題之一，是大部分低質量數據產生的源頭。相似重復記錄會損害數據的唯一性，產生數據冗余，導致資源浪費。因此，相似重復記錄的消除成為數據倉庫構建成功的關鍵因素之一。優先隊列算法、Delphi算法和SNM算法是目前常見的消除海量數據環境下數據庫中相似重復記錄的策略。

1.1優先隊列算法

假設S是一個數據集，S中的記錄都有鍵值，優先隊列就是一種關于S的數據結構。優先隊列包括最大優先隊列、最小優先隊列，支持INSERT等多種操作。優先隊列算法中使用優先隊列中的元素作為一組記錄，每一個元素包含的這一組記錄都是屬于最新探測到的記錄簇中的一部分。算法按照順序匹配數據庫中的記錄，判定記錄是否為優先隊列中相關記錄簇中的成員。若是，則掃描下一條；否則，這條記錄將和優先隊列中的記錄進行比較，如果存在重復記錄，那么就將該記錄合并到匹配記錄所在簇。如果不存在重復數據，則將該條記錄加入一個新的簇，并進入優先隊列，且具有最高優先級[6-7]。

1.2Delphi算法

Delphi算法可用來判定兩條或者多條記錄是否相似，主要是利用文本相似度函數和共同出現相似度函數來進行相似重復記錄的探測，并利用聚合策略減少記錄比較次數[8]。對于“winxp pro”和“windows XP Professional”這樣的等價錯誤，其識別效率較高。

1.3傳統SNM算法

SNM算法[9-10]即鄰近排序算法。SNM算法的基本思想是：將數據集R中的所有記錄按照相應指定的關鍵詞(key)進行排序。絕大部分情況下，經過排序后的數據集中，如果存在相似重復記錄，則認為它們是相鄰的，且聚集在一定范圍內，可在很大程度上提高匹配效率。另外，采用滑動窗口極大地減少了記錄比較的次數，提高了比較速度，縮短了匹配時間。

1.4現有相似重復記錄消除算法的比較

綜合上述幾種常見的消除相似重復記錄算法，可知它們各自都有自己的適用范圍和應用環境。其優勢和不足如表1所示。

數據倉庫構建過程中，相似重復記錄的消除首先要考慮針對海量數據的執行效率，在此基礎上對算法進行改進以提高相似重復數據的探測率，得到更好的消除效果，進而提高數據倉庫中的數據質量。通過對幾種常見的消除相似重復記錄算法的比較，全面分析各自的優勢與不足，對SNM算法進行討論和改進。

表1　幾種常見消除相似重復記錄算法的比較

2基于SNM算法的改進與實現

傳統的SNM算法識別相似重復記錄的做法是：對數據預處理后，選定關鍵屬性，然后將記錄生成記錄字符串，并對其進行排序；排序后按照設定的窗口大小對窗口內記錄進行記錄匹配；最后根據設定的文本相似度判定是否為相似重復記錄。SNM算法的思想是盡量只對排序后鄰近的記錄進行匹配，從而大大減少比較次數和縮短比較時間，因此SNM算法對相似重復數據的匹配效果的好壞取決于排序后相似重復記錄被排在相鄰位置的鄰近程度，相似重復記錄越鄰近，匹配效果就越好。然而，在對數據源的數據進行排序時，選擇的排序字段不同對排序結果有很大影響。在實際數據中，往往有很大一部分記錄的數據值不是單個的單詞或詞語，而是一個句子，如地址字段。對于屬性值為句子之類的數據，如果直接排序，則相似重復記錄很可能并非鄰近，相反會分離得較遠。有時候由于屬性值的順序規則不同，甚至較短的句子也有可能出現類似的問題。例如：有兩條主要屬性是(Name,Sex,Birthday,Phone,Address)的記錄：(Wang Mei,F,1989-10-10,18671745011,Hubei Yichang Xiling University Road)，(Mei Wang,W,1989-10-10,18671745011,University Road，Xiling，Yichang，Hubei)。無論按照Name屬性排序，還是Address屬性排序，其排序后的結果都會將這兩條記錄分離得很遠，而事實上這兩條記錄屬于重復數據。

筆者將記錄字符串單詞化分割后再進行排序，較好地彌補了傳統算法的缺陷。同樣以上述兩條記錄為例，本文首先對不一致的屬性進行預處理，示例中，對Sex屬性，采用男性為“1”，女性為“0”，將記錄中的Sex屬性做歸一化處理；其次選定關鍵屬性(Name,Sex,Birthday,Address)，并生成記錄字符串分別為“Wang Mei 0 1989-10-10 Hubei Yichang Xiling University Road”，“Mei Wang 0 1989-10-10 University Road，Xiling，Yichang，Hubei”；然后針對記錄字符串單詞化處理并排序，得到結果字符串分別為“0 1989-10-10 Hubei Mei Road University Wang Xiling Yichang”，“0 1989-10-10 Hubei Mei Road University Wang Xiling Yichang”。經過該處理后的相似重復記錄很大程度上增加了聚合的機會，再通過窗口內計算文本相似度就能很容易判定這兩條記錄是重復數據。因此，對記錄字符串單詞化處理后再排序能很大程度上將相似重復記錄排到鄰近位置，進而更好地消除相似重復記錄。改進的SNM算法流程如圖1所示，算法步驟及實現過程具體如下(以示例客戶數據表為例)：1) 輸入客戶表記錄，設定窗口大小S=3，文本相似度閾值u=0.95。客戶數據表包括客戶編號、姓名、性別、出生日期、手機號碼、地址這6個屬性。客戶表記錄中包含4條示例記錄，如圖2所示。

2) 數據預處理。客戶表中的Sex和Birthday屬性存在表示方式不一致的情況，對于這一類型的數據問題，通過數據預處理即可消除。

3) 選擇關鍵屬性。在判定兩條或多條記錄是否為相似重復記錄時，并非所有屬性都是關鍵屬性。本文對客戶表選擇的關鍵屬性是Name，Sex，Birthday，Address。

4) 針對選擇關鍵屬性后的記錄生成字符串記錄，并存入字符串記錄表中。

5) 將字符串記錄單詞化處理，如圖3所示。

圖1　改進的SNM算法流程

圖2　客戶表記錄

圖3　單詞化后的字符串記錄

6) 將單詞化的子串進行排序。

7) 為了最大限度地使相似重復記錄處于鄰近位置，將子串排序后的字符串記錄表按照排序后的字符串進行排序。通過這一步的操作和處理，相似重復數據將處于鄰近位置，即在算法的窗口之內。

8) 根據設定的窗口大小以及文本相似度，對排序后的字符串記錄計算文本相似度，消除相似重復記錄。示例中消除相似重復記錄后的結果見圖5。

圖4　排序后的字符串記錄

圖5　消除相似重復記錄后的結果

3實現方法與結果分析

3.1實驗環境和數據選擇

考慮到真實數據涉及到商業機密，用來進行實驗的數據獲取比較困難，另外，實際數據中相似重復記錄的總量不確定性也會對實驗評價帶來很大的困難，因此筆者利用來自Internet的測試數據生成器構造了用于本文測試的數據。構造的客戶數據表主要包括ID，Name，Sex，Birthday，Phone，Address等6個屬性。構造客戶數據表之后，生成了10 000條客戶記錄，同時生成了8 000條相似重復記錄，將其隨機插入客戶表中。

3.2評價指標

筆者將算法消除相似重復記錄的比例作為評價算法改進程度的指標。測試數據中相似重復記錄的數量為已知量，因此通過算法消除的相似重復記錄的比例很容易得到，且該百分比能在很大程度上說明算法的性能和數據質量。

相似重復記錄消除率表示算法可以消除的相似重復記錄占數據表中所有相似重復記錄的比例，定義為

(1)

其中：NV表示算法消除相似重復記錄的數量；N表示數據表中相似重復記錄的總量。

3.3結果分析

3.3.1不同初始參數對消除結果的影響

根據算法流程可知，不同的初始參數對最終消除的相似重復記錄的數量會產生影響。這里選擇不同的窗口大小和文本相似度閾值進行實驗和結果分析。

1) 不同窗口大小S對消除結果的影響

為測試不同窗口大小對消除結果的影響，這里對文本相似度閾值取定值u=0.85。測試結果如表2所示。

表2　不同窗口大小消除結果

由圖6的實驗結果可知：在本文實驗的數據中，相似重復記錄消除率隨窗口大小的增加而升高，當窗口增大到一定程度時，相似重復記錄消除率上升緩慢并逐漸趨于平穩。可見，針對本文實驗數據，最優窗口大小為S=20。

圖6　不同窗口大小消除結果折線

2) 不同文本相似度閾值u對消除結果的影響

為了測試不同文本相似度閾值對消除結果的影響，這里對窗口大小取上述最優值S=20，測試結果如表3所示。

表3　不同文本相似度閾值消除結果

由圖7的實驗結果可知：在本文實驗的數據中，相似重復記錄消除率隨文本相似度閾值的增大而降低，當文本相似度閾值增大到一定程度時，相似重復記錄消除率降低緩慢并逐漸趨于平穩，即文本相似度要求越嚴格，探測到的相似重復記錄比例會越低。由上述實驗結果可見，針對本文實驗數據，可選擇文本相似度閾值大小為u=0.85。

圖7　不同文本相似度閾值消除結果折線

3.3.2改進SNM算法與傳統SNM算法的消除效果比較

為了比較改進SNM算法和傳統SNM算法的消除效果，采用本文中的測試數據，并設定文本相似度閾值u=0.85進行不同窗口大小下的對比實驗。消除效果對比見表4。

表4　改進SNM算法與傳統SNM算法消除效果對比

從圖8顯示的結果可知：相同窗口大小的情況下，改進SNM算法相比傳統算法有較好的相似重復記錄消除率，說明算法改進有一定的效果。

圖8　改進SNM算法與傳統算法對比消除結果折線

參考文獻：

[1]KIMBALL R,REEVES L,ROSS M,et al.The Data Warehouse Lifecycle Toolkit:The Definitive Guide to Dimensional Modeling[M].Indiana:Wiley Publishing Inc,2013.

[2]LOSHIN D.Data Quality ROI in the Absence of Profits[J].Information & Management,2003(9):22.

[3]HUANG K,LEE T,Y W WANG,et al.Quality Information and Knowledge[M].NJ:Prentice-Hall,1999.

[4]CLIKEMAN P M.Improving information quality[J].Internal Auditor,1999(3):32-33.

[5]SINGH R,SINGH K.A descriptive classification of causes of data quality problems in data warehousing[J].International Journal of Computer Science Issues,2010.

[6]張建中,方正,熊擁軍,等.對基于SNM數據清洗算法的優化[J].中南大學學報(自然科學版),2010(6):2240-2245.

[7]陳爽,刁興春,宋金玉,等.基于伸縮窗口和等級調整的SNM改進方法[J].計算機應用研究,2013(9):2736-2739.

[8]葉煥倬,吳迪.相似重復記錄清理方法研究綜述[J].現代圖書情報技術,2010(9):56-66.

[10]HERNANDEZ M,STOLFO S.The Merge/Purge Problem for Large Databases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.San Jose,California:[s.n.],1995:127-138.

(責任編輯楊黎麗)

Research on Eliminating Duplicate Records Based on SNM Improved Algorithm

YU Xiao-sheng, HU Sun-zhi

(College of Computer and Information Technology,China Three Gorges University, Yichang 443002, China)

Abstract:High quality data is the most important factor to build the data warehouse. The low quality data may be bad for decision making. An approximately duplicate record from different data sources is one of the main data quality issues to build data warehouse. To eliminate approximately duplicate data as far as possible before the source data enters into a data warehouse can greatly improve the quality of data. Firstly, the existing approximately duplicate records elimination algorithms were compared, and then SNM algorithm was improved. The authors compared traditional SNM method and SNM improved algorithm by the experiment, and the results show: SNM improved algorithm has obvious advantages in eliminating duplicate records.

Key words:SNM algorithm; SNM improved algorithm; approximately duplicate records elimination

文章編號：1674-8425(2016)04-0091-06

中圖分類號：TP311

文獻標識碼：A

doi:10.3969/j.issn.1674-8425(z).2016.04.016

作者簡介：余肖生(1973—),男，湖北監利人，博士后，副教授，主要從事信息管理與電子商務研究。

基金項目：國家自然科學基金資助項目(71473185)

收稿日期：2016-01-18

引用格式：余肖生， 胡孫枝.基于SNM改進算法的相似重復記錄消除[J].重慶理工大學學報(自然科學)，2016(4):91-96.

Citation format：YU Xiao-sheng, HU Sun-zhi.Research on Eliminating Duplicate Records Based on SNM Improved Algorithm [J].Journal of Chongqing University of Technology(Natural Science)，2016(4):91-96.