基于字段過濾和伸縮窗口的SNM算法優(yōu)化*

周世杰,婁淵勝

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院，江蘇 南京 211100)

1 引言

隨著社會(huì)工業(yè)化和信息化水平的不斷提高，存儲(chǔ)在數(shù)據(jù)倉庫中的數(shù)據(jù)迅速增加。通過數(shù)據(jù)挖掘可在這些海量的數(shù)據(jù)中找出蘊(yùn)含的重要信息，這些信息往往對(duì)信息決策支持系統(tǒng)有重要作用，但挖掘的前提是有高質(zhì)量的數(shù)據(jù)。高質(zhì)量的數(shù)據(jù)是充分發(fā)揮其蘊(yùn)含的效能的前提和基礎(chǔ)，而低質(zhì)量的數(shù)據(jù)可能對(duì)決策產(chǎn)生不利的影響[1,2]。數(shù)據(jù)清洗可以對(duì)存儲(chǔ)在數(shù)據(jù)倉庫中的“問題”數(shù)據(jù)進(jìn)行剔除或改正[3]，從而提高數(shù)據(jù)質(zhì)量，為決策分析提供數(shù)據(jù)支撐。數(shù)據(jù)清洗的主要清洗對(duì)象是不完整數(shù)據(jù)、沖突數(shù)據(jù)和重復(fù)數(shù)據(jù)[4]，其中需要解決的主要問題是對(duì)相似重復(fù)數(shù)據(jù)的查找與去除。相似重復(fù)數(shù)據(jù)是指對(duì)于現(xiàn)實(shí)世界的同一或類似實(shí)體，由于在各數(shù)據(jù)源存儲(chǔ)時(shí)可能出現(xiàn)的格式或拼寫錯(cuò)誤、結(jié)構(gòu)或表述不同等問題，數(shù)據(jù)庫管理系統(tǒng)DBMS(Database Management System)不能準(zhǔn)確識(shí)別而存儲(chǔ)的多條不完全相同的記錄[5]。在信息管理系統(tǒng)中，重復(fù)數(shù)據(jù)的存在會(huì)影響存儲(chǔ)效率，造成數(shù)據(jù)冗余，識(shí)別和消除無用數(shù)據(jù)可以提高數(shù)據(jù)質(zhì)量,保證決策數(shù)據(jù)的可靠性。

清除相似重復(fù)記錄常用“排序-合并”的方式，其思想是將待檢測的數(shù)據(jù)集按照某個(gè)或某些屬性排序，使得數(shù)據(jù)集中的相似重復(fù)記錄彼此靠近，然后通過比對(duì)鄰近位置的記錄判斷是否為相似重復(fù)記錄。常見的排序-合并算法包括鄰近排序算法SNM(Sorted-Neighborhood Method)[6]、多趟鄰近排序算法MPN (Multi-Pass Sorted Neighborhood)[7]和優(yōu)先隊(duì)列算法[8]等。其中，鄰近排序算法SNM是一種比較流行的排序-合并算法，因其思想簡單、效果明顯和易于實(shí)現(xiàn)的優(yōu)點(diǎn)而被人們廣泛使用。SNM算法在排序后的數(shù)據(jù)集上設(shè)置一個(gè)固定大小的窗口，每次只比對(duì)窗口內(nèi)的數(shù)據(jù)，窗口內(nèi)的數(shù)據(jù)比對(duì)完畢后向下移動(dòng)窗口再次進(jìn)行比對(duì)，這種方式極大地減少了比對(duì)次數(shù)，從而加快了檢測的速度。

雖然SNM算法加快了檢測的速度，但依然存在一些缺點(diǎn)：(1)對(duì)排序關(guān)鍵字依賴程度大；(2)字段權(quán)重多為單一用戶或領(lǐng)域?qū)＜以O(shè)定，主觀程度大；(3)窗口的大小難以確定；(4)記錄匹配過程采用笛卡爾乘積的方式，比對(duì)時(shí)間較長。許多研究人員針對(duì)上述缺點(diǎn)提出了一些改進(jìn)方案。文獻(xiàn)[7]采用的方式是多次獨(dú)立地執(zhí)行SNM算法，每次選用不同的關(guān)鍵字對(duì)數(shù)據(jù)集排序，然后在小窗口中進(jìn)行比對(duì)，此方法可以減少關(guān)鍵字選取不當(dāng)所帶來的影響，但該方式需要頻繁計(jì)算傳遞閉包，降低了查準(zhǔn)率。文獻(xiàn)[9,10]使用的屬性確定方法結(jié)合了客觀數(shù)理統(tǒng)計(jì)方法和主觀經(jīng)驗(yàn)，雖然可以較為客觀地確定屬性權(quán)值，但此方法需要多用戶的參與，在實(shí)際運(yùn)用中耗時(shí)過長且不易實(shí)現(xiàn)。文獻(xiàn)[11,12]依據(jù)窗口內(nèi)重復(fù)記錄的總數(shù)與窗口大小的比例動(dòng)態(tài)調(diào)整滑動(dòng)窗口的大小，但此種方式將SNM歸并過程的時(shí)間復(fù)雜度從O(WN)提高到O(N2)(N為數(shù)據(jù)集總記錄數(shù)，W為窗口的大小)，時(shí)間效率不高。文獻(xiàn)[13,14]提出了長度過濾算法，在識(shí)別重復(fù)記錄前根據(jù)字符串的長度比例去除不相似的數(shù)據(jù)集，減少記錄比較次數(shù)，提高檢測效率，但如果屬性值采用簡寫的方式或?qū)傩允欠潜靥铐?xiàng)，采用此方式可能會(huì)將重復(fù)記錄排除，致使算法精度降低。

綜上，本文提出了一種SNM的改進(jìn)算法ISNM(Improved Sorted-Neighborhood Method)。該算法采用屬性區(qū)分法客觀地計(jì)算權(quán)值，提高了檢測精度；采用字段過濾算法計(jì)算記錄相似度，減少了比對(duì)次數(shù)；采用可變窗口來防止漏配，減少了無用的記錄比對(duì)。實(shí)驗(yàn)結(jié)果表明，ISNM算法提高了檢測精度，加快了記錄比對(duì)速度。

2 SNM算法介紹

基本的SNM算法主要包括以下3步：

(1) 選取排序關(guān)鍵字。抽取記錄的重要屬性作為記錄排序關(guān)鍵字。

(2) 排序。根據(jù)(1)中選取的關(guān)鍵字排序數(shù)據(jù)集。排序后重復(fù)記錄會(huì)彼此靠近，從而將比對(duì)限定到一定范圍內(nèi)。

(3) 相似重復(fù)記錄檢測。設(shè)置一個(gè)大小為W的窗口，在第(2)步的基礎(chǔ)上向下移動(dòng)窗口。窗口的末尾記錄與其余的W-1條記錄比對(duì)，比對(duì)完成后將首條記錄移出，將第W+1條記錄移入，重復(fù)上述步驟直到所有記錄都完成比對(duì)。

圖1為SNM算法滑動(dòng)窗口示意圖。

Figure 1 Sliding window in SNM algorithm

由上述描述可知，SNM算法將記錄的比對(duì)限定在大小為W的固定窗口中，總比對(duì)次數(shù)為N(W-1)次;而傳統(tǒng)的方法是將每一條記錄與剩余的N-1條記錄進(jìn)行比對(duì)，總比對(duì)次數(shù)為N(N-1)/2。由此可見，SNM算法極大地減少了比對(duì)次數(shù)，因此極大地加快了檢測速度，提高了運(yùn)行效率。但是，SNM算法也存在以下不足：

(1) 對(duì)選取的排序關(guān)鍵字依賴性較大。選用不合適的關(guān)鍵字對(duì)數(shù)據(jù)集排序，會(huì)使相似重復(fù)記錄不能同時(shí)出現(xiàn)在同一個(gè)窗口中，因無法比對(duì)而造成漏配。例如表1的2條記錄，無論是按照Name屬性排序，還是按照Address屬性排序，或者2個(gè)屬性組合排序，都存在因它們存儲(chǔ)的位置不相鄰而產(chǎn)生漏配的可能。

Table1 Example of similar duplicate records

(2)難以確定滑動(dòng)窗口的大小W。如果W較大會(huì)增加無用的比對(duì)，降低檢測效率；如果W較小又可能導(dǎo)致漏配，降低檢測精度。

(3)確定屬性權(quán)值的主觀性大。屬性權(quán)值大多是采用單一用戶或者專家打分的方法來確定，因此主觀性大。

(4)在重復(fù)相似度檢測過程中，相似記錄的判別基本上都是采用笛卡爾積的方式，采用該種方式會(huì)導(dǎo)致記錄的匹配時(shí)間較長，檢測效率不高。

3 ISNM算法

本文針對(duì)SNM算法的缺點(diǎn)提出了改進(jìn)的ISNM算法，其思想是：首先通過屬性區(qū)分法計(jì)算各屬性權(quán)值，并通過權(quán)值來確定排序關(guān)鍵字；其次采用字段過濾算法進(jìn)行判重，提高檢測效率；最后使用可變窗口進(jìn)行比對(duì)。ISNM算法流程圖如圖2所示。

Figure 2 Flow of ISNM algorithm

3.1 屬性區(qū)分法計(jì)算權(quán)值

記錄的屬性體現(xiàn)了現(xiàn)實(shí)實(shí)體的某個(gè)特性，屬性的權(quán)值又代表了該特性對(duì)實(shí)體的重要性，屬性權(quán)值越大，則該屬性對(duì)其所表示的現(xiàn)實(shí)實(shí)體的重要程度就越大，因此權(quán)值的設(shè)定不應(yīng)該有較強(qiáng)的主觀性。本文提出使用“屬性區(qū)分度”來確定屬性權(quán)值，一方面避免了權(quán)值設(shè)定的主觀性，另一方面不需要多用戶參與，在實(shí)際應(yīng)用中容易實(shí)現(xiàn)。

屬性區(qū)分度是指屬性區(qū)分?jǐn)?shù)據(jù)集中不同記錄的能力，某個(gè)屬性取值種類越多，則該屬性的屬性區(qū)分度就越大。屬性的區(qū)分度代表了該屬性記錄的差異性，因此屬性區(qū)分度越大，該屬性的權(quán)值就越大。將計(jì)算得到的屬性區(qū)分度值歸一化處理后得各屬性權(quán)值。

為方便描述，假設(shè)待檢測的數(shù)據(jù)集D={D1,D2,…,DN}，N為記錄總數(shù)，每條記錄有p個(gè)屬性，即Di={Attr1,Attr2,…,Arrtp}，則每個(gè)屬性的區(qū)分度計(jì)算公式為：

(1)

其中,YAttri表示屬性Attri的取值種類數(shù)，也就是說如果按照屬性Attri的不同取值進(jìn)行聚類，會(huì)有YAttri個(gè)簇。將各個(gè)屬性的區(qū)分度值進(jìn)行歸一化處理后，得到屬性的權(quán)值向量W={W1,W2,…,Wp}。屬性區(qū)分算法如算法1所示。

算法1屬性區(qū)分算法

輸入：數(shù)據(jù)集D={D1,D2,…,DN}。

輸出：字段權(quán)值(W1,W2,…,Wp)(p表示記錄的屬性個(gè)數(shù))。

1.Fori=1 topDo

2. 計(jì)算屬性i的取值種類數(shù)YAttri；

3.Endfor

4.Fori=1 topDo

5. 根據(jù)式(1)計(jì)算屬性i的屬性區(qū)分度Attrdisi；

6.Endfor

7.對(duì)Attrdisi進(jìn)行歸一化處理；

8.ReturnWi

3.2 關(guān)鍵字的選取與預(yù)處理

由3.1節(jié)可知，屬性的區(qū)分度代表了該屬性記錄的差異性，選擇區(qū)分度大的屬性對(duì)數(shù)據(jù)集進(jìn)行排序，可以最大程度保證相似重復(fù)記錄位置靠近，并將非相似重復(fù)記錄分隔開。對(duì)數(shù)據(jù)集中每條數(shù)據(jù)的各個(gè)屬性利用算法1計(jì)算其屬性權(quán)值，并按由大到小順序排序，根據(jù)實(shí)際情況選取排名靠前的屬性作為排序關(guān)鍵屬性，并從每個(gè)關(guān)鍵屬性中提取一部分組成排序關(guān)鍵字對(duì)數(shù)據(jù)集進(jìn)行排序。如針對(duì)滁河流域水文數(shù)據(jù)集，經(jīng)過上述方法處理后，最終選取“站點(diǎn)名稱”“地區(qū)”“獲取數(shù)據(jù)時(shí)間”和“傳感器編號(hào)”作為排序關(guān)鍵屬性，取每個(gè)關(guān)鍵屬性的前4個(gè)字符作為排序關(guān)鍵字對(duì)數(shù)據(jù)集進(jìn)行排序。

對(duì)數(shù)據(jù)集進(jìn)行排序之前，首先把字段中標(biāo)點(diǎn)符號(hào)、不能辨別的或有標(biāo)示性含義的符號(hào)刪除，例如銀行系統(tǒng)的“￥”“$”等;其次將字段中的單詞按照字典序排列;最后再按照排序關(guān)鍵字對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序。假設(shè)選擇表1中Name和Address屬性的組合作為排序關(guān)鍵字，按照上述方法對(duì)記錄進(jìn)行排序后的結(jié)果如表2所示。由此可見，經(jīng)過預(yù)處理之后，可以使這2條記錄存儲(chǔ)位置相距較近，確保它們?cè)谕粋€(gè)窗口中。

Table 2 Record sorting results table after preprocessing

3.3 字段過濾算法

SNM算法檢測相似重復(fù)記錄常用的方法是求出2條記錄各屬性值的相似度，并加權(quán)求和得到記錄相似度，然后將該值與相似度閾值對(duì)比來判定記錄是否相似重復(fù)。然而字段比對(duì)大多采用的是笛卡爾乘積的方式[15]，采用這種方式的問題是記錄匹配時(shí)間過長，效率不高。本節(jié)針對(duì)該問題提出使用字段過濾算法來提高檢測效率。

字段過濾算法的核心思想是：記錄的不同屬性值可以區(qū)分不同的記錄，且關(guān)鍵屬性的屬性值對(duì)記錄的區(qū)分度更高。若對(duì)關(guān)鍵屬性的相似度進(jìn)行加權(quán)求和后可以確定2條記錄為相似重復(fù)記錄，則無需計(jì)算剩余屬性的相似度；否則需要計(jì)算所有屬性的相似度，加權(quán)求和后判斷2條記錄是否為相似重復(fù)記錄。因此,在進(jìn)行相似度檢測時(shí)，首先選擇關(guān)鍵屬性進(jìn)行比較，將關(guān)鍵屬性的相似度與權(quán)值相乘并求和得到記錄相似度，然后將其與相似度閾值相對(duì)比，若前者大于后者，則斷定這2條記錄相似重復(fù)，同時(shí)完成屬性比對(duì)，否則，繼續(xù)比對(duì)剩余屬性。

(2)

否則有:

(3)

字段過濾算法如算法2所示。

算法2字段過濾算法

輸入：待比較的記錄Di和Dj,相似度閾值U。

輸出：SimR(Di,Dj)。

1.Fort=1 tomDo

2.SimR(Di,Dj)=SimA(Dit,Djt)Wt;

3.Endfor

4.If(SimR(Di,Dj)

5.Fort=m+1 topDo

6.SimR(Di,Dj)+=SimA(Dit,Djt)Wt；

7.Endfor

8.Endif

字段過濾算法極大地減少了字段比對(duì)的次數(shù)，從而加快了檢測速度。

3.4 可伸縮滑動(dòng)窗口

原SNM算法滑動(dòng)窗口的大小不易確定，窗口設(shè)置得太大會(huì)增加很多無用的記錄比對(duì)，降低檢測效率；窗口設(shè)置得太小又可能導(dǎo)致重復(fù)記錄的漏配，降低檢測精度。使用可變窗口可以在檢測過程中動(dòng)態(tài)調(diào)整窗口的大小，從而減小固定窗口給檢測結(jié)果帶來的影響。本文根據(jù)相似重復(fù)記錄的位置動(dòng)態(tài)調(diào)整滑動(dòng)窗口的大小,其基本思想是：假設(shè)窗口C的開始大小為W，若新移入C的記錄Rw與即將移出C的記錄R1是相似重復(fù)記錄，則Rw+1與R1相似的概率較高，此時(shí)應(yīng)當(dāng)增大窗口的大小，避免相似重復(fù)記錄的漏配；若與Rw互為相似重復(fù)的記錄Ri(1≤i≤w)距離Rw較近，則應(yīng)該縮小窗口大小，減少無用的比對(duì)。設(shè)窗口C大小的最大最小值分別為Wmax和Wmin，窗口C大小的初始值Wn設(shè)定為Wmin。C中記錄的位置為[1，w]，位置為1的記錄為C內(nèi)的首條記錄，位置為w的記錄為新移入C中的記錄，則動(dòng)態(tài)計(jì)算滑動(dòng)窗口大小的方法如式(4)所示：

(4)

其中,Bi表示第i條記錄是否與末尾記錄Rw互為相似重復(fù)記錄，若是，則Bi=1，否則，Bi=0。由式(4)不難看出，若C內(nèi)的所有記錄都相似重復(fù)，則下一輪C的大小從Wn變成Wmax，若C內(nèi)的所有記錄都不相似重復(fù)，則下一輪C的大小從Wn變成Wmin，距離末尾紀(jì)錄Rw越遠(yuǎn)的相似重復(fù)記錄對(duì)C的取值作用越大。

3.5 相似重復(fù)記錄檢測改進(jìn)方法

ISNM算法的基本流程是：使用屬性區(qū)分法計(jì)算各屬性權(quán)值，并在權(quán)值的基礎(chǔ)上選擇排序關(guān)鍵字，對(duì)字段預(yù)處理后，再按照排序關(guān)鍵字排列數(shù)據(jù)集中的記錄，在窗口內(nèi)對(duì)數(shù)據(jù)子集進(jìn)行判重，在判重的過程中使用字段過濾算法提高檢測效率，然后調(diào)整窗口大小并向下移動(dòng)窗口，重復(fù)進(jìn)行判重。ISNM算法流程如算法3所示。

算法3ISNM算法

輸入：數(shù)據(jù)記錄集D，相似度閾值U，窗口最大值Wmax與最小值Wmin。

輸出：去重后的數(shù)據(jù)集。

步驟1計(jì)算屬性權(quán)值。

使用算法1計(jì)算記錄各屬性的權(quán)值Wi。

步驟2關(guān)鍵字的選取與數(shù)據(jù)記錄預(yù)處理。

根據(jù)3.2節(jié)描述的方法選取排序關(guān)鍵字

Fori=1 toNDo/*N表示數(shù)據(jù)總量。去除字段中的無用符號(hào)，并將字段中的單詞按照字典序排列*/

Endfor

步驟3按照排列關(guān)鍵字對(duì)數(shù)據(jù)集進(jìn)行排列。

步驟4在滑動(dòng)窗口中使用字段過濾算法進(jìn)行重復(fù)記錄檢測，并動(dòng)態(tài)調(diào)整窗口的大小。

While(滑動(dòng)窗口沒有滑到數(shù)據(jù)集的尾部)

使用算法2計(jì)算相似度值；

If(SimR(Di,Dj)≥U)

D=D-Ri；∥Ri表示第i條記錄

Endif

根據(jù)式(4)計(jì)算下一個(gè)滑動(dòng)窗口大小；

向下滑動(dòng)窗口；

Endwhile

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

本次實(shí)驗(yàn)數(shù)據(jù)來自滁河流域近3年各站點(diǎn)所觀測的水位記錄，記錄了站點(diǎn)名稱、數(shù)據(jù)獲取時(shí)間、地區(qū)、傳感器編號(hào)和水位等內(nèi)容。由于記錄過程中傳感器異常導(dǎo)致同一時(shí)間重復(fù)記錄水位信息，因此采集到的數(shù)據(jù)存在大量的重復(fù)數(shù)據(jù)。

實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i5-1035G1 CPU @ 2.2 GHz，16 GB內(nèi)存，Windows 10操作系統(tǒng)。數(shù)據(jù)存儲(chǔ)在MySQL 5.6中，采用IntelliJ IDEA編程工具和Java語言實(shí)現(xiàn)優(yōu)化算法，jdk版本為1.8。

4.2 實(shí)驗(yàn)方案及評(píng)價(jià)指標(biāo)

4.2.1 性能實(shí)驗(yàn)

實(shí)驗(yàn)1為了更好地分析ISNM算法帶來的性能提升，本次實(shí)驗(yàn)把ISNM算法與傳統(tǒng)的SNM算法、文獻(xiàn)[14]的LF-SNM(SNM based on Length Filtering and Dynamic Fault-tolerance)算法、文獻(xiàn)[16]的SNM改進(jìn)方法(在本文中稱為chen-SNM算法)、MPN(Multi-Pass Sorted Neighborhood)算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)每一次從數(shù)據(jù)集中隨機(jī)抽出10萬,20萬,30萬,40萬和50萬條記錄，分別用上述5種算法進(jìn)行檢測。為了便于統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，將上述各數(shù)據(jù)集處理成包含0.12萬,0.25萬,0.43萬,0.56萬和0.71萬條相似重復(fù)記錄的數(shù)據(jù)集，用人工統(tǒng)計(jì)的方式判斷實(shí)驗(yàn)得出的相似重復(fù)數(shù)據(jù)集是否正確。實(shí)驗(yàn)中設(shè)定相似度閾值為0.75，可變窗口的最小值為40，最大值為60，固定大小的窗口值為40。

實(shí)驗(yàn)2為了檢驗(yàn)ISNM算法在相同數(shù)據(jù)規(guī)模、不同相似重復(fù)記錄條數(shù)下的有效性，設(shè)置如下實(shí)驗(yàn)：從數(shù)據(jù)集中隨機(jī)抽取20萬條記錄，并將此數(shù)據(jù)集處理成包含0.09萬,0.12萬,0.18萬,0.25萬和0.31萬條相似重復(fù)記錄的數(shù)據(jù)集，仍采用人工統(tǒng)計(jì)的方式處理實(shí)驗(yàn)結(jié)果。此次實(shí)驗(yàn)設(shè)定相似度閾值為0.75，可變窗口的最小值為40，最大值為60。

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

實(shí)驗(yàn)3為了看出不同窗口對(duì)實(shí)驗(yàn)結(jié)果的影響，設(shè)置可變窗口的最小值為60，最大值為80，可變窗口與固定窗口的初始值為80，在與實(shí)驗(yàn)1同樣的實(shí)驗(yàn)環(huán)境中進(jìn)行實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與實(shí)驗(yàn)1的結(jié)果進(jìn)行比較分析。

實(shí)驗(yàn)4為了檢驗(yàn)ISNM算法在相同數(shù)據(jù)規(guī)模和相似重復(fù)記錄條數(shù)下，不同窗口范圍對(duì)實(shí)驗(yàn)結(jié)果的影響，設(shè)置如下實(shí)驗(yàn)：從數(shù)據(jù)集中隨機(jī)抽取20萬條記錄，并將此數(shù)據(jù)集處理成包含0.25萬條相似重復(fù)記錄的數(shù)據(jù)集，將可變窗口的最小最大值分別設(shè)置成[20,40],[40,60],[60,80],[80,100]和[100,120]，設(shè)定窗口的初始值取窗口的最小值，相似度閾值為0.75。

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

實(shí)驗(yàn)性能評(píng)價(jià)指標(biāo)采用查準(zhǔn)率(precision) 、查全率(recall)[17]和運(yùn)行時(shí)間開銷。查全率和查準(zhǔn)率定義如式(5)和式(6)所示：

(5)

(6)

其中,tp表示檢測出來的相似重復(fù)記錄是正確的數(shù)量，fp表示檢測出來的相似重復(fù)記錄是錯(cuò)誤的數(shù)量，fn表示沒有檢測出來的相似重復(fù)記錄的數(shù)量[17]。故tp+fp表示檢測出來的相似重復(fù)記錄的總量，tp+fn表示數(shù)據(jù)集中原本存在的重復(fù)記錄總量。

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 性能實(shí)驗(yàn)

基于上述實(shí)驗(yàn)方案，使用各算法在相同的實(shí)驗(yàn)環(huán)境下對(duì)待檢測的數(shù)據(jù)集進(jìn)行重復(fù)記錄檢測，實(shí)驗(yàn)結(jié)果如圖3～圖5所示。

Figure 3 Comparison of precision of each algorithm

由圖3可以看出，ISNM算法的查全率優(yōu)于其他各算法的。ISNM算法采用屬性區(qū)分法確定字段權(quán)值，解決了權(quán)值主觀性過強(qiáng)的問題，在排序之前對(duì)排序關(guān)鍵字進(jìn)行預(yù)處理，使相似重復(fù)記錄存儲(chǔ)在靠近的位置以避免漏配，并使用大小可變的窗口進(jìn)行檢測，避免了因窗口過小而引起的漏配，從而提高了查全率。MPN算法多次獨(dú)立地執(zhí)行SNM算法，每次選用不同的關(guān)鍵字對(duì)數(shù)據(jù)集進(jìn)行排序，故查全率較高，但MPN算法固定移動(dòng)窗口大小，窗口設(shè)置得太大或太小對(duì)查全率都有比較大的影響，因此MPN算法的查全率低于ISNM算法的。LF-SNM算法與chen-SNM算法采用的字段權(quán)值調(diào)整方法需先人為設(shè)定再進(jìn)行調(diào)整，仍具有一定的主觀性，故查全率較低。

Figure 4 Comparison of recall of each algorithm

由圖4可以看出，ISNM算法的查準(zhǔn)率要優(yōu)于其他算法的。ISNM采用了伸縮滑動(dòng)窗口的方式，當(dāng)窗口較大時(shí)可以動(dòng)態(tài)縮小窗口，避免了因不必要的記錄比對(duì)導(dǎo)致檢測出來的記錄是錯(cuò)誤的情況，并且使用字段過濾算法減少了比較次數(shù)，而不使用傳遞閉包的方式，降低了誤識(shí)別率，故查準(zhǔn)率高。而chen-SNM算法、LF-SNM算法和MPN算法均采用傳遞閉包的方式整合重復(fù)記錄，會(huì)產(chǎn)生很多的誤識(shí)別，因此這3種算法的查全率不如ISNM算法的。

Figure 5 Comparison of running time of each algorithm

由圖5可以看出，在同樣的實(shí)驗(yàn)環(huán)境中ISNM算法的時(shí)間效率優(yōu)于其他算法的。ISNM算法使用了可變窗口的方式，避免了無用的記錄比對(duì)，并同時(shí)使用字段過濾算法計(jì)算記錄的相似度，提高了記錄的比對(duì)效率，因此ISNM算法的時(shí)間開銷小。chen-SNM算法與LF-SNM算法分別采用了伸縮窗口和長度過濾的方式來提高效率，但這2個(gè)算法需要計(jì)算傳遞閉包，因此這2個(gè)算法的時(shí)間開銷與ISNM算法的相近但低于ISNM算法的。MPN算法需要多次獨(dú)立執(zhí)行SNM算法，每次選擇不同的關(guān)鍵字排列數(shù)據(jù)集，并且合并數(shù)據(jù)集合時(shí)需要計(jì)算傳遞閉包，因此時(shí)間開銷較大。

4.2.1節(jié)中的實(shí)驗(yàn)2的實(shí)驗(yàn)結(jié)果如圖6所示。

Figure 6 Comparison results under different similar repeat scales

由圖6可以看出，ISNM算法在相同數(shù)據(jù)規(guī)模、不同相似重復(fù)記錄條數(shù)下，查全率與查準(zhǔn)率一直處于相對(duì)穩(wěn)定的狀態(tài)，并同時(shí)保持了較高水準(zhǔn)。其次運(yùn)行時(shí)間隨著相似重復(fù)數(shù)的增加而逐漸增大，但是仍在可接受的范圍內(nèi)，由此可進(jìn)一步證明本文所提算法的優(yōu)越性。

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

基于4.2.2節(jié)中的實(shí)驗(yàn)3的實(shí)驗(yàn)結(jié)果如圖7～圖9所示。

Figure 7 Comparison of precision between ISNM algorithm and SNM algorithm

Figure 8 Comparison of recall between ISNM algorithm and SNM algorithm

Figure 9 Comparison of running time between ISNM algorithm and SNM algorithm

由圖7和圖8可以看出，ISNM算法的查全率和查準(zhǔn)率明顯優(yōu)于SNM算法的。隨著窗口的增大，窗口內(nèi)覆蓋的重復(fù)記錄變多，避免了目標(biāo)記錄的漏配，故SNM算法的查全率會(huì)提高，但查準(zhǔn)率會(huì)下降，這是因?yàn)楣潭ù翱诓荒苷{(diào)節(jié)大小，增加了無用的記錄比對(duì)導(dǎo)致誤識(shí)別增多。初始值為80的窗口幾乎包括了所有目標(biāo)記錄，故ISNM算法的查全率變化不大，但查準(zhǔn)率會(huì)稍微下降，這也是由于窗口增大造成誤識(shí)別增多導(dǎo)致的，但可變窗口會(huì)及時(shí)縮小窗口大小來避免這種情況的發(fā)生。

由圖9可以看出，ISNM算法的時(shí)間開銷要優(yōu)于SNM算法的。隨著窗口的增大，增加了窗口內(nèi)的記錄比對(duì)次數(shù)，故ISNM算法與SNM算法的時(shí)間開銷都會(huì)變大，其中SNM算法的時(shí)間開銷變化較大，而ISNM算法由于采用了可變窗口，可以及時(shí)調(diào)整窗口的大小，所以時(shí)間開銷變化的幅度不大。

基于4.2.2節(jié)中的實(shí)驗(yàn)4的實(shí)驗(yàn)結(jié)果如圖10所示。

Figure 10 Comparison results of different window ranges

由圖10可以看出，隨著窗口范圍的增大，查全率先增大，然后趨于平穩(wěn);而查準(zhǔn)率先增大，然后減小。在此使用查全率和查準(zhǔn)率的調(diào)和均值F值來反映ISNM算法的性能。從圖10中的折線可以看出，窗口大小在[60,80]和[80,100]時(shí)F值達(dá)到最大，再結(jié)合2個(gè)范圍的運(yùn)行時(shí)間可以得出，針對(duì)本文的實(shí)驗(yàn)數(shù)據(jù)，最優(yōu)的窗口為[60,80]。

5 結(jié)束語

數(shù)據(jù)清洗可以有效地提高數(shù)據(jù)源的數(shù)據(jù)質(zhì)量，消除數(shù)據(jù)中的重復(fù)記錄是其中的一個(gè)熱門課題。本文分析了傳統(tǒng)SNM算法，并指出了傳統(tǒng)SNM算法的缺陷，針對(duì)原算法的缺陷提出了基于SNM的改進(jìn)算法——ISNM算法。主要提出了4點(diǎn)改進(jìn)：(1)采用屬性區(qū)分法確定屬性權(quán)值，解決了單一用戶設(shè)定固定權(quán)值的不足，提高了算法檢測的精度；(2)根據(jù)權(quán)值選取排序關(guān)鍵字，避免了關(guān)鍵字選取不當(dāng)對(duì)SNM算法精度的影響，并對(duì)關(guān)鍵字進(jìn)行預(yù)處理，使得相似重復(fù)記錄位置彼此靠近以避免漏配；(3)使用字段過濾算法計(jì)算相似度，減少了窗口內(nèi)記錄屬性的比對(duì)次數(shù)，加快了算法的檢測速度;(4)使用可變窗口的方式進(jìn)行檢測，既防止了記錄的漏配，也減少了無用的匹配。通過對(duì)實(shí)際系統(tǒng)中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，采用查全率、查準(zhǔn)率和運(yùn)行時(shí)間評(píng)價(jià)標(biāo)準(zhǔn)驗(yàn)證了ISNM算法的可行性與優(yōu)勢。然而改進(jìn)算法無法識(shí)別文字不同但語義相同的相似重復(fù)記錄，另外相似度閾值的取值范圍也是一個(gè)亟需解決的問題，過大或過小的閾值都會(huì)對(duì)查重精度產(chǎn)生影響，下一步將針對(duì)這些問題進(jìn)行研究。