基于字段過濾和伸縮窗口的SNM算法優化*

周世杰,婁淵勝

(河海大學計算機與信息學院，江蘇 南京 211100)

1 引言

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

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

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

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

2 SNM算法介紹

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

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

(2) 排序。根據(1)中選取的關鍵字排序數據集。排序后重復記錄會彼此靠近，從而將比對限定到一定范圍內。

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

圖1為SNM算法滑動窗口示意圖。

Figure 1 Sliding window in SNM algorithm

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

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

Table1 Example of similar duplicate records

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

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

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

3 ISNM算法

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

Figure 2 Flow of ISNM algorithm

3.1 屬性區分法計算權值

記錄的屬性體現了現實實體的某個特性，屬性的權值又代表了該特性對實體的重要性，屬性權值越大，則該屬性對其所表示的現實實體的重要程度就越大，因此權值的設定不應該有較強的主觀性。本文提出使用“屬性區分度”來確定屬性權值，一方面避免了權值設定的主觀性，另一方面不需要多用戶參與，在實際應用中容易實現。

屬性區分度是指屬性區分數據集中不同記錄的能力，某個屬性取值種類越多，則該屬性的屬性區分度就越大。屬性的區分度代表了該屬性記錄的差異性，因此屬性區分度越大，該屬性的權值就越大。將計算得到的屬性區分度值歸一化處理后得各屬性權值。

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

(1)

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

算法1屬性區分算法

輸入：數據集D={D1,D2,…,DN}。

輸出：字段權值(W1,W2,…,Wp)(p表示記錄的屬性個數)。

1.Fori=1 topDo

2. 計算屬性i的取值種類數YAttri；

3.Endfor

4.Fori=1 topDo

5. 根據式(1)計算屬性i的屬性區分度Attrdisi；

6.Endfor

7.對Attrdisi進行歸一化處理；

8.ReturnWi

3.2 關鍵字的選取與預處理

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

對數據集進行排序之前，首先把字段中標點符號、不能辨別的或有標示性含義的符號刪除，例如銀行系統的“￥”“$”等;其次將字段中的單詞按照字典序排列;最后再按照排序關鍵字對整個數據集進行排序。假設選擇表1中Name和Address屬性的組合作為排序關鍵字，按照上述方法對記錄進行排序后的結果如表2所示。由此可見，經過預處理之后，可以使這2條記錄存儲位置相距較近，確保它們在同一個窗口中。

Table 2 Record sorting results table after preprocessing

3.3 字段過濾算法

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

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

(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

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

3.4 可伸縮滑動窗口

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

(4)

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

3.5 相似重復記錄檢測改進方法

ISNM算法的基本流程是：使用屬性區分法計算各屬性權值，并在權值的基礎上選擇排序關鍵字，對字段預處理后，再按照排序關鍵字排列數據集中的記錄，在窗口內對數據子集進行判重，在判重的過程中使用字段過濾算法提高檢測效率，然后調整窗口大小并向下移動窗口，重復進行判重。ISNM算法流程如算法3所示。

算法3ISNM算法

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

輸出：去重后的數據集。

步驟1計算屬性權值。

使用算法1計算記錄各屬性的權值Wi。

步驟2關鍵字的選取與數據記錄預處理。

根據3.2節描述的方法選取排序關鍵字

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

Endfor

步驟3按照排列關鍵字對數據集進行排列。

步驟4在滑動窗口中使用字段過濾算法進行重復記錄檢測，并動態調整窗口的大小。

While(滑動窗口沒有滑到數據集的尾部)

使用算法2計算相似度值；

If(SimR(Di,Dj)≥U)

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

Endif

根據式(4)計算下一個滑動窗口大小；

向下滑動窗口；

Endwhile

4 實驗與結果分析

4.1 實驗環境及數據

本次實驗數據來自滁河流域近3年各站點所觀測的水位記錄，記錄了站點名稱、數據獲取時間、地區、傳感器編號和水位等內容。由于記錄過程中傳感器異常導致同一時間重復記錄水位信息，因此采集到的數據存在大量的重復數據。

實驗環境為Intel(R) Core(TM) i5-1035G1 CPU @ 2.2 GHz，16 GB內存，Windows 10操作系統。數據存儲在MySQL 5.6中，采用IntelliJ IDEA編程工具和Java語言實現優化算法，jdk版本為1.8。

4.2 實驗方案及評價指標

4.2.1 性能實驗

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

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

4.2.2 不同窗口大小對消除結果的影響

實驗3為了看出不同窗口對實驗結果的影響，設置可變窗口的最小值為60，最大值為80，可變窗口與固定窗口的初始值為80，在與實驗1同樣的實驗環境中進行實驗，并將實驗結果與實驗1的結果進行比較分析。

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

4.2.3 評價指標

實驗性能評價指標采用查準率(precision) 、查全率(recall)[17]和運行時間開銷。查全率和查準率定義如式(5)和式(6)所示：

(5)

(6)

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

4.3 實驗結果分析

4.3.1 性能實驗

基于上述實驗方案，使用各算法在相同的實驗環境下對待檢測的數據集進行重復記錄檢測，實驗結果如圖3～圖5所示。

Figure 3 Comparison of precision of each algorithm

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

Figure 4 Comparison of recall of each algorithm

由圖4可以看出，ISNM算法的查準率要優于其他算法的。ISNM采用了伸縮滑動窗口的方式，當窗口較大時可以動態縮小窗口，避免了因不必要的記錄比對導致檢測出來的記錄是錯誤的情況，并且使用字段過濾算法減少了比較次數，而不使用傳遞閉包的方式，降低了誤識別率，故查準率高。而chen-SNM算法、LF-SNM算法和MPN算法均采用傳遞閉包的方式整合重復記錄，會產生很多的誤識別，因此這3種算法的查全率不如ISNM算法的。

Figure 5 Comparison of running time of each algorithm

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

4.2.1節中的實驗2的實驗結果如圖6所示。

Figure 6 Comparison results under different similar repeat scales

由圖6可以看出，ISNM算法在相同數據規模、不同相似重復記錄條數下，查全率與查準率一直處于相對穩定的狀態，并同時保持了較高水準。其次運行時間隨著相似重復數的增加而逐漸增大，但是仍在可接受的范圍內，由此可進一步證明本文所提算法的優越性。

4.3.2 不同窗口大小對消除結果的影響

基于4.2.2節中的實驗3的實驗結果如圖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算法的查全率和查準率明顯優于SNM算法的。隨著窗口的增大，窗口內覆蓋的重復記錄變多，避免了目標記錄的漏配，故SNM算法的查全率會提高，但查準率會下降，這是因為固定窗口不能調節大小，增加了無用的記錄比對導致誤識別增多。初始值為80的窗口幾乎包括了所有目標記錄，故ISNM算法的查全率變化不大，但查準率會稍微下降，這也是由于窗口增大造成誤識別增多導致的，但可變窗口會及時縮小窗口大小來避免這種情況的發生。

由圖9可以看出，ISNM算法的時間開銷要優于SNM算法的。隨著窗口的增大，增加了窗口內的記錄比對次數，故ISNM算法與SNM算法的時間開銷都會變大，其中SNM算法的時間開銷變化較大，而ISNM算法由于采用了可變窗口，可以及時調整窗口的大小，所以時間開銷變化的幅度不大。

基于4.2.2節中的實驗4的實驗結果如圖10所示。

Figure 10 Comparison results of different window ranges

由圖10可以看出，隨著窗口范圍的增大，查全率先增大，然后趨于平穩;而查準率先增大，然后減小。在此使用查全率和查準率的調和均值F值來反映ISNM算法的性能。從圖10中的折線可以看出，窗口大小在[60,80]和[80,100]時F值達到最大，再結合2個范圍的運行時間可以得出，針對本文的實驗數據，最優的窗口為[60,80]。

5 結束語

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