余肖生， 胡孫枝

(三峽大學(xué) 計(jì)算機(jī)與信息學(xué)院,湖北 宜昌　443002)

?

基于SNM改進(jìn)算法的相似重復(fù)記錄消除

余肖生， 胡孫枝

(三峽大學(xué) 計(jì)算機(jī)與信息學(xué)院,湖北 宜昌443002)

摘要：高質(zhì)量的數(shù)據(jù)是構(gòu)建數(shù)據(jù)倉庫的最重要因素，低質(zhì)量的數(shù)據(jù)可能對(duì)決策產(chǎn)生不利影響。來自不同數(shù)據(jù)源的相似重復(fù)記錄是數(shù)據(jù)倉庫構(gòu)建中影響數(shù)據(jù)質(zhì)量的主要問題之一，在源數(shù)據(jù)進(jìn)入數(shù)據(jù)倉庫之前盡可能地消除相似重復(fù)記錄能很大程度地提高數(shù)據(jù)質(zhì)量。為此，比較了現(xiàn)有的相似重復(fù)記錄消除算法，改進(jìn)了SNM算法，并通過實(shí)驗(yàn)比較了傳統(tǒng)SNM方法與改進(jìn)SNM算法。實(shí)驗(yàn)結(jié)果顯示：在相似重復(fù)記錄消除方面，SNM改進(jìn)算法具有明顯的優(yōu)勢(shì)。

關(guān)鍵詞：SNM算法；SNM改進(jìn)算法；相似重復(fù)記錄消除

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

本文比較了現(xiàn)有相似重復(fù)記錄消除算法，并改進(jìn)了SNM算法。通過實(shí)驗(yàn)比較傳統(tǒng)SNM方法與改進(jìn)SNM算法，結(jié)果顯示：在相似重復(fù)記錄消除方面，SNM改進(jìn)算法具有明顯的優(yōu)勢(shì)。

1現(xiàn)有相似重復(fù)記錄消除算法的比較

相似重復(fù)記錄是指對(duì)于現(xiàn)實(shí)世界中同一個(gè)實(shí)體，在各個(gè)數(shù)據(jù)源數(shù)據(jù)庫或平面文件中存儲(chǔ)時(shí)，由于可能出現(xiàn)格式錯(cuò)誤、結(jié)構(gòu)不一致、拼寫差異等問題導(dǎo)致數(shù)據(jù)庫管理系統(tǒng)沒有正確識(shí)別而產(chǎn)生的兩條或者多條不完全相同的記錄[5]。相似重復(fù)記錄是導(dǎo)致數(shù)據(jù)倉庫構(gòu)建中數(shù)據(jù)質(zhì)量不符合標(biāo)準(zhǔn)的最常見的問題之一，是大部分低質(zhì)量數(shù)據(jù)產(chǎn)生的源頭。相似重復(fù)記錄會(huì)損害數(shù)據(jù)的唯一性，產(chǎn)生數(shù)據(jù)冗余，導(dǎo)致資源浪費(fèi)。因此，相似重復(fù)記錄的消除成為數(shù)據(jù)倉庫構(gòu)建成功的關(guān)鍵因素之一。優(yōu)先隊(duì)列算法、Delphi算法和SNM算法是目前常見的消除海量數(shù)據(jù)環(huán)境下數(shù)據(jù)庫中相似重復(fù)記錄的策略。

1.1優(yōu)先隊(duì)列算法

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

1.2Delphi算法

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

1.3傳統(tǒng)SNM算法

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

1.4現(xiàn)有相似重復(fù)記錄消除算法的比較

綜合上述幾種常見的消除相似重復(fù)記錄算法，可知它們各自都有自己的適用范圍和應(yīng)用環(huán)境。其優(yōu)勢(shì)和不足如表1所示。

數(shù)據(jù)倉庫構(gòu)建過程中，相似重復(fù)記錄的消除首先要考慮針對(duì)海量數(shù)據(jù)的執(zhí)行效率，在此基礎(chǔ)上對(duì)算法進(jìn)行改進(jìn)以提高相似重復(fù)數(shù)據(jù)的探測(cè)率，得到更好的消除效果，進(jìn)而提高數(shù)據(jù)倉庫中的數(shù)據(jù)質(zhì)量。通過對(duì)幾種常見的消除相似重復(fù)記錄算法的比較，全面分析各自的優(yōu)勢(shì)與不足，對(duì)SNM算法進(jìn)行討論和改進(jìn)。

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

2基于SNM算法的改進(jìn)與實(shí)現(xiàn)

傳統(tǒng)的SNM算法識(shí)別相似重復(fù)記錄的做法是：對(duì)數(shù)據(jù)預(yù)處理后，選定關(guān)鍵屬性，然后將記錄生成記錄字符串，并對(duì)其進(jìn)行排序；排序后按照設(shè)定的窗口大小對(duì)窗口內(nèi)記錄進(jìn)行記錄匹配；最后根據(jù)設(shè)定的文本相似度判定是否為相似重復(fù)記錄。SNM算法的思想是盡量只對(duì)排序后鄰近的記錄進(jìn)行匹配，從而大大減少比較次數(shù)和縮短比較時(shí)間，因此SNM算法對(duì)相似重復(fù)數(shù)據(jù)的匹配效果的好壞取決于排序后相似重復(fù)記錄被排在相鄰位置的鄰近程度，相似重復(fù)記錄越鄰近，匹配效果就越好。然而，在對(duì)數(shù)據(jù)源的數(shù)據(jù)進(jìn)行排序時(shí)，選擇的排序字段不同對(duì)排序結(jié)果有很大影響。在實(shí)際數(shù)據(jù)中，往往有很大一部分記錄的數(shù)據(jù)值不是單個(gè)的單詞或詞語，而是一個(gè)句子，如地址字段。對(duì)于屬性值為句子之類的數(shù)據(jù)，如果直接排序，則相似重復(fù)記錄很可能并非鄰近，相反會(huì)分離得較遠(yuǎn)。有時(shí)候由于屬性值的順序規(guī)則不同，甚至較短的句子也有可能出現(xiàn)類似的問題。例如：有兩條主要屬性是(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屬性排序，其排序后的結(jié)果都會(huì)將這兩條記錄分離得很遠(yuǎn)，而事實(shí)上這兩條記錄屬于重復(fù)數(shù)據(jù)。

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

2) 數(shù)據(jù)預(yù)處理?？蛻舯碇械腟ex和Birthday屬性存在表示方式不一致的情況，對(duì)于這一類型的數(shù)據(jù)問題，通過數(shù)據(jù)預(yù)處理即可消除。

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

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

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

圖1　改進(jìn)的SNM算法流程

圖2　客戶表記錄

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

6) 將單詞化的子串進(jìn)行排序。

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

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

圖4　排序后的字符串記錄

圖5　消除相似重復(fù)記錄后的結(jié)果

3實(shí)現(xiàn)方法與結(jié)果分析

3.1實(shí)驗(yàn)環(huán)境和數(shù)據(jù)選擇

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

3.2評(píng)價(jià)指標(biāo)

筆者將算法消除相似重復(fù)記錄的比例作為評(píng)價(jià)算法改進(jìn)程度的指標(biāo)。測(cè)試數(shù)據(jù)中相似重復(fù)記錄的數(shù)量為已知量，因此通過算法消除的相似重復(fù)記錄的比例很容易得到，且該百分比能在很大程度上說明算法的性能和數(shù)據(jù)質(zhì)量。

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

(1)

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

3.3結(jié)果分析

3.3.1不同初始參數(shù)對(duì)消除結(jié)果的影響

根據(jù)算法流程可知，不同的初始參數(shù)對(duì)最終消除的相似重復(fù)記錄的數(shù)量會(huì)產(chǎn)生影響。這里選擇不同的窗口大小和文本相似度閾值進(jìn)行實(shí)驗(yàn)和結(jié)果分析。

1) 不同窗口大小S對(duì)消除結(jié)果的影響

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

表2　不同窗口大小消除結(jié)果

由圖6的實(shí)驗(yàn)結(jié)果可知：在本文實(shí)驗(yàn)的數(shù)據(jù)中，相似重復(fù)記錄消除率隨窗口大小的增加而升高，當(dāng)窗口增大到一定程度時(shí)，相似重復(fù)記錄消除率上升緩慢并逐漸趨于平穩(wěn)。可見，針對(duì)本文實(shí)驗(yàn)數(shù)據(jù)，最優(yōu)窗口大小為S=20。

圖6　不同窗口大小消除結(jié)果折線

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

為了測(cè)試不同文本相似度閾值對(duì)消除結(jié)果的影響，這里對(duì)窗口大小取上述最優(yōu)值S=20，測(cè)試結(jié)果如表3所示。

表3　不同文本相似度閾值消除結(jié)果

由圖7的實(shí)驗(yàn)結(jié)果可知：在本文實(shí)驗(yàn)的數(shù)據(jù)中，相似重復(fù)記錄消除率隨文本相似度閾值的增大而降低，當(dāng)文本相似度閾值增大到一定程度時(shí)，相似重復(fù)記錄消除率降低緩慢并逐漸趨于平穩(wěn)，即文本相似度要求越嚴(yán)格，探測(cè)到的相似重復(fù)記錄比例會(huì)越低。由上述實(shí)驗(yàn)結(jié)果可見，針對(duì)本文實(shí)驗(yàn)數(shù)據(jù)，可選擇文本相似度閾值大小為u=0.85。

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

3.3.2改進(jìn)SNM算法與傳統(tǒng)SNM算法的消除效果比較

為了比較改進(jìn)SNM算法和傳統(tǒng)SNM算法的消除效果，采用本文中的測(cè)試數(shù)據(jù)，并設(shè)定文本相似度閾值u=0.85進(jìn)行不同窗口大小下的對(duì)比實(shí)驗(yàn)。消除效果對(duì)比見表4。

表4　改進(jìn)SNM算法與傳統(tǒng)SNM算法消除效果對(duì)比

從圖8顯示的結(jié)果可知：相同窗口大小的情況下，改進(jìn)SNM算法相比傳統(tǒng)算法有較好的相似重復(fù)記錄消除率，說明算法改進(jìn)有一定的效果。

圖8　改進(jìn)SNM算法與傳統(tǒng)算法對(duì)比消除結(jié)果折線

參考文獻(xiàn)：

[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]張建中,方正,熊擁軍,等.對(duì)基于SNM數(shù)據(jù)清洗算法的優(yōu)化[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2010(6):2240-2245.

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

[8]葉煥倬,吳迪.相似重復(fù)記錄清理方法研究綜述[J].現(xiàn)代圖書情報(bào)技術(shù),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.

(責(zé)任編輯楊黎麗)

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

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

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71473185)

收稿日期：2016-01-18

引用格式：余肖生， 胡孫枝.基于SNM改進(jìn)算法的相似重復(fù)記錄消除[J].重慶理工大學(xué)學(xué)報(bào)(自然科學(xué))，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.