數(shù)據(jù)清洗中重復(fù)記錄清洗算法的研究

謝文閣等

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

關(guān)鍵詞：數(shù)據(jù)清洗；全文索引；重復(fù)記錄；清洗算法

中圖分類號(hào)： TM399 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

數(shù)據(jù)清洗（Data Clean）就是將錯(cuò)誤的、不一致的、冗余的數(shù)據(jù)在裝入數(shù)據(jù)倉庫之前進(jìn)行刪除或修正，從而保證決策分析時(shí)數(shù)據(jù)的正確性.其主要工作就是從原始數(shù)據(jù)中檢測(cè)錯(cuò)誤和沖突的數(shù)據(jù)并消除的過程[1]。此項(xiàng)工作中檢查并清除重復(fù)記錄數(shù)據(jù)是數(shù)據(jù)清洗要解決的重要問題之一。重復(fù)記錄就是指現(xiàn)實(shí)世界中同一個(gè)實(shí)體的不同數(shù)據(jù)記錄，由于表述方式不同或者是因?yàn)槠磳懖煌仁沟肈BMS不能識(shí)別它們?yōu)橹貜?fù)記錄。如果這些記錄不去掉，有可能導(dǎo)致數(shù)據(jù)模型建立的不準(zhǔn)確，從而影響以后的數(shù)據(jù)決策分析。所以，在數(shù)據(jù)清洗中，檢測(cè)并清除掉重復(fù)記錄是非常重要的。

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

2 SNM算法（SNM algorithm ）

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

（1）創(chuàng)建排序關(guān)鍵字，即從數(shù)據(jù)集中抽取記錄屬性中的一個(gè)屬性值或者是子集序列的字串作為關(guān)鍵字，為數(shù)據(jù)記錄集中每一條記錄計(jì)算出關(guān)鍵字的鍵值。

（2）排序。根據(jù)該排序關(guān)鍵字對(duì)整個(gè)數(shù)據(jù)記錄集進(jìn)行排序。排序中應(yīng)盡可能地使可能的重復(fù)記錄排列到一個(gè)鄰近的區(qū)域內(nèi)，使得特定的記錄可以將進(jìn)行記錄匹配的對(duì)象調(diào)整到在一定的范圍之內(nèi)。

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

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

3 全文索引（Full-text index）

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

全文索引與普通索引不同之處在于普通索引采取B-tree的結(jié)構(gòu)進(jìn)行維護(hù)，而全文索引是基于標(biāo)記的功能性索引，由Microsoft SQL Server全文引擎服務(wù)創(chuàng)建并維護(hù)。全文索引可以快速、靈活地為存儲(chǔ)在SQL Server數(shù)據(jù)庫中的文本數(shù)據(jù)機(jī)建立面向關(guān)鍵字查詢的索引，它與like語句不同之處是like語句的搜索主要適合字符模式的查詢，而全文索引是針對(duì)語言的搜索，它根據(jù)語言的規(guī)則對(duì)詞和短語進(jìn)行搜索。所以，在對(duì)大量的數(shù)據(jù)進(jìn)行查詢時(shí)，全文索引可以提高查詢的性能，對(duì)于上百萬條記錄的數(shù)據(jù)進(jìn)行l(wèi)ike查詢需要幾分鐘才能得到結(jié)果，而全文索引只需幾秒鐘甚至更少的時(shí)間就可以得到結(jié)果。

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

records cleaning algorithm）

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

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

//檢索之前對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化處理的偽代碼：

UPDATE [dbo].[TABLENAME]

SET [COLUMN]=STANDARD VALUE

WHERE CONTAINS（[COLUMN]，UNSTANDARDIZED VALUE）

//標(biāo)準(zhǔn)化處理后再對(duì)數(shù)據(jù)集進(jìn)行算法處理：

Set w（column1）=column1 weight value；

w（column2）=column2 weight value；……//為每個(gè)字段設(shè)定權(quán)值

Set w=a；threshold=b；

//設(shè)定滑動(dòng)窗口大小為a，

//閾值為bor（int t=w-1；t//數(shù)組中第一個(gè)記錄為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是兩個(gè)字符串比較函數(shù)，相等值為1，否則為0；

//通過權(quán)值分配比較兩條記錄的相似度

If（newtheshold> theshold）

Delete array[t]；

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

}

對(duì)記錄比較時(shí)對(duì)記錄集中的滑動(dòng)窗口的設(shè)置過程中，采用算法如下：

SELECT num=COUNT（*）

FROM [dbo].[TABLENAME]

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

Set w=m；

滑動(dòng)窗口中記錄比較代碼

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算法對(duì)記錄進(jìn)行比較時(shí)，兩條記錄的匹配流程是對(duì)不同的字段根據(jù)在元組中的重要程度賦予不同的權(quán)值，在設(shè)定好閾值的基礎(chǔ)上，計(jì)算每條記錄的權(quán)值總和，如果總值大于設(shè)定的閾值，則作為重復(fù)記錄處理，否則視為兩條記錄。具體工作匹配流程如圖3所示。

5 結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

[1] 楊輔祥，劉云超，段智華.數(shù)據(jù)清理綜述[J].計(jì)算機(jī)應(yīng)用研

究，2004（4）：3-5.

[2] 郭文龍.一種改進(jìn)的相似重復(fù)記錄檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用與

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

[3] 張建中，等.對(duì)基于SNM數(shù)據(jù)清洗算法的優(yōu)化[J].中南大學(xué)學(xué)

報(bào)，2010（6）：2240-2245.

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

（2）：101-103.

作者簡(jiǎn)介：

謝文閣（1966-），男，本科，教授.研究領(lǐng)域：數(shù)據(jù)倉庫，軟件

開發(fā).

佟玉軍（1970-），男，本科，副教授.研究領(lǐng)域：算法，數(shù)據(jù)

挖掘.

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

開發(fā).

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

件開發(fā).