數據清洗中重復記錄清洗算法的研究

謝文閣等

摘 要：介紹了數據清洗中的SNM算法和全文索引技術，通過引入全文索引技術對SNM算法進行了改進，以此提高了重復記錄查找的速度和準確率，從而較好地提升了SNM算法的性能。

關鍵詞：數據清洗；全文索引；重復記錄；清洗算法

中圖分類號： TM399 文獻標識碼：A

1 引言（Introduction）

數據清洗（Data Clean）就是將錯誤的、不一致的、冗余的數據在裝入數據倉庫之前進行刪除或修正，從而保證決策分析時數據的正確性.其主要工作就是從原始數據中檢測錯誤和沖突的數據并消除的過程[1]。此項工作中檢查并清除重復記錄數據是數據清洗要解決的重要問題之一。重復記錄就是指現實世界中同一個實體的不同數據記錄，由于表述方式不同或者是因為拼寫不同等使得DBMS不能識別它們為重復記錄。如果這些記錄不去掉，有可能導致數據模型建立的不準確，從而影響以后的數據決策分析。所以，在數據清洗中，檢測并清除掉重復記錄是非常重要的。

近鄰排序算法（Sorted-Neighborhood Method， SNM）是數據清洗過程中的經典算法，而SNM算法卻需要對數據集進行先期的排序[2]，全文索引是一種特殊的基于標記的功能性索引，兩者結合，可以在提高排序速度的同時有效的消除重復記錄。

2 SNM算法（SNM algorithm ）

SNM算法是當前比較流行的一類匹配與合并算法，而且該算法目前已被一些數據清洗工具所采用。目前采用比較普遍的方法是基于近鄰排序算法[3]，它的設計步驟可以分為下面三步：

（1）創建排序關鍵字，即從數據集中抽取記錄屬性中的一個屬性值或者是子集序列的字串作為關鍵字，為數據記錄集中每一條記錄計算出關鍵字的鍵值。

（2）排序。根據該排序關鍵字對整個數據記錄集進行排序。排序中應盡可能地使可能的重復記錄排列到一個鄰近的區域內，使得特定的記錄可以將進行記錄匹配的對象調整到在一定的范圍之內。

（3）重復檢測。排序后，就可以在排序后的數據記錄集上滑動固定大小的窗口，滑動時，最先進入窗口內的記錄將滑出窗口，最后一條記錄的下一條記錄將移入窗口，數據記錄集中新進入的記錄與窗口內的記錄進行比較。如果窗口的大小為W條記錄，則每條新進入到窗口內的記錄就要與先前進入窗口的W-1條記錄進行逐一比較，以此來檢測重復記錄，如不重復，則把此信進入的第W條記錄作為下一輪比較對象，以此類推，直到完成所有記錄集中記錄得比較，如圖1所示。

SNM算法采用的滑動窗口比較檢測重復記錄的方法，每次只比較窗口中的W條記錄，采用滑動窗口提高了比較速度，從而有效地提高了匹配效率。但SNM算法也存在一些不足：（1）對排序關鍵字的依賴性較大。SNM算法檢測重復記錄的精度某種程度上受到創建的排序關鍵字的限制，關鍵字的好壞直接影響了匹配的效率和精度。而且關鍵字的選取還依賴于應用領域。當選取關鍵字不當時，就有可能使得本來是重復記錄的兩條記錄在排序后物理位置相距較遠，可能永遠不會同時位于同一個滑動窗口內，也就不能被識別出是重復記錄，即在重復檢測時會漏掉很多重復記錄。（2）滑動窗口的大小W的選取也不好選擇。W較大時比較次數會增多，而有些比較是沒有必要的；當W較小時可能又會遺漏匹配；如果記錄中各種重復記錄聚類差別較大時，W的選取無論是大還是小又都不恰當。

3 全文索引（Full-text index）

所謂全文索引，就是面向全文并提供全文信息的檢索技術，它不需要對信息進行標引就可以完成檢索，它采取將原文中有意義的字或者詞作為檢索內容，由其指向原文有關頁面或進行鏈接[4]。基于這種詞索引的全文檢索主要有以下幾步：首先進行漢語自動分詞，其次對文檔中有意義的詞進行倒排索引，在檢索時將通過用戶輸入的檢索條件按照匹配機制與詞索引庫中的信息進行匹配，最后將檢索結果返回給用戶。

全文索引與普通索引不同之處在于普通索引采取B-tree的結構進行維護，而全文索引是基于標記的功能性索引，由Microsoft SQL Server全文引擎服務創建并維護。全文索引可以快速、靈活地為存儲在SQL Server數據庫中的文本數據機建立面向關鍵字查詢的索引，它與like語句不同之處是like語句的搜索主要適合字符模式的查詢，而全文索引是針對語言的搜索，它根據語言的規則對詞和短語進行搜索。所以，在對大量的數據進行查詢時，全文索引可以提高查詢的性能，對于上百萬條記錄的數據進行like查詢需要幾分鐘才能得到結果，而全文索引只需幾秒鐘甚至更少的時間就可以得到結果。

4 重復記錄清洗算法的研究（Research of duplicate

records cleaning algorithm）

根據前面SNM算法的分析，知道它存在的缺點，就此引入全文索引技術，將全文索引技術與傳統的SNM算法相結合，形成一種新的重復記錄清洗算法。它的設計思想就是在排序過程中，結合漢語檢索方法引入全文索引技術，以此來彌補SNM算法的不足，從而提高排序速度，同時全文索引技術還可以有效的使得重復記錄盡可能出現在同一個滑動窗口中，減少重復記錄檢測的失誤，提高檢測效率。在進行兩條記錄的相似度匹配時，還根據元組各不同字段的重視程度的不同設置不同的權值，再與比較相似度閾值進行比較，決定兩條記錄是否是重復記錄。設計思想的具體工作流程請見如圖2所示。

基于全文索引的SNM算法中主要功能的偽代碼如下：

//檢索之前對數據集進行標準化處理的偽代碼：

UPDATE [dbo].[TABLENAME]

SET [COLUMN]=STANDARD VALUE

WHERE CONTAINS（[COLUMN]，UNSTANDARDIZED VALUE）

//標準化處理后再對數據集進行算法處理：

Set w（column1）=column1 weight value；

w（column2）=column2 weight value；……//為每個字段設定權值

Set w=a；threshold=b；

//設定滑動窗口大小為a，

//閾值為bor（int t=w-1；t//數組中第一個記錄為array[0]

{Int newtheshold=

（array[t].column1）compare（array[t-w+1].column1）*w（column1）+

（array[t].column2）compare（array[t-w+1].column2）*w（column2）+……

//compare是兩個字符串比較函數，相等值為1，否則為0；

//通過權值分配比較兩條記錄的相似度

If（newtheshold> theshold）

Delete array[t]；

//如果記錄相似度大于閾值則刪除后面的記錄

}

對記錄比較時對記錄集中的滑動窗口的設置過程中，采用算法如下：

SELECT num=COUNT（*）

FROM [dbo].[TABLENAME]

WHERE CONTAINS（[COLUMN]，array[0].column）

Set w=m；

滑動窗口中記錄比較代碼

If（（array[t].column）compare（array[t-w+1].column）=0）

SELECT n=COUNT（*）

FROM [dbo].[TABLENAME]

WHERE CONTAINS（[COLUMN]，array[t].column）

Set w=（int）n/num*m；

在使用SNM算法對記錄進行比較時，兩條記錄的匹配流程是對不同的字段根據在元組中的重要程度賦予不同的權值，在設定好閾值的基礎上，計算每條記錄的權值總和，如果總值大于設定的閾值，則作為重復記錄處理，否則視為兩條記錄。具體工作匹配流程如圖3所示。

5 結論（Conclusion）

本論文通過在SNM算法中引入全文索引方法，較好的降低了索引處理成本并加快了處理速度，不僅較好的解決了記錄排序效率低的問題，同時通過滑動窗口的隨時改變，對字段設定不同的權值，將記錄的權值的總和與設定的閾值進行相似度檢測，在不影響查找重復記錄效率的情況下減少了不必要的比較次數，從而更好的提高了算法的效率。

參考文獻（References）

[1] 楊輔祥，劉云超，段智華.數據清理綜述[J].計算機應用研

究，2004（4）：3-5.

[2] 郭文龍.一種改進的相似重復記錄檢測算法[J].計算機應用與

軟件，2014（1）：293-295.

[3] 張建中，等.對基于SNM數據清洗算法的優化[J].中南大學學

報，2010（6）：2240-2245.

[4] 徐小剛，王俊杰，于玉.全文索引的研究[J].計算機工程，2002

（2）：101-103.

作者簡介：

謝文閣（1966-），男，本科，教授.研究領域：數據倉庫，軟件

開發.

佟玉軍（1970-），男，本科，副教授.研究領域：算法，數據

挖掘.

賈 丹（1972-），女，碩士，副教授.研究領域：算法，軟件

開發.

梅紅巖（1978-），女，博士，副教授.研究領域：人工智能，軟

件開發.