面向時序的相似重復數據清洗算法優化

沈 沛，毛海濤，胡文林，芮 波

(1.中國人民解放軍92728部隊，上海 200436；2.杭州冪鏈科技有限公司)

0 引言

隨著智能設備和傳感器技術的大量應用，在大數據處理中出現了一類典型特征的數據——時序數據。時序數據在商業、氣象、農業、航天、生物科學等各個領域都有著廣泛而重要的應用，其特點是數據隨時間生成，且數據量巨大、對實時分析處理要求高。但由于各種因素，如設備異常、網絡波動、重復輸入、多源合并等等，使得在時序數據記錄中統一實體容易在相同時間單位產生相似重復數據。針對時序數據體量大這一特點，更高效的相似重復數據檢測和清洗算法就顯得十分重要了。

1 相關工作

目前，在相似重復數據檢測和清洗方面已經有不少研究。如很多研究者提出了分區處理的思想，其本質是將大塊數據分成更小的子集，這樣可以在清洗過程中使單條數據記錄僅與本分區中的其余記錄比對識別，而不需要比對全數據集，從而大大提高了算法效率。在分區思想中，最常用的方法是分塊和窗口技術。分塊技術，先將數據集切分成適合處理的獨立子集，再在獨立子集內采用聚類算法來進行進一步的處理；窗口技術則是通過滑動窗口，選取固定大小的數據量依次比對。

其中，基于窗口技術的算法已有較多的研究和應用，在重復數據檢測方面也有了一些成果。例如基于“排序合并”的算法先將數據按關鍵特征排序，然后通過比對鄰近記錄特征是否相等或相似來識別相似重復記錄。在“排序合并”思想的基礎上，又有研究者提出了SNM(Sorted Neighborhood Method)及其改進算 法、排序分塊算法 SBM(SortedBlocks Method)、多趟近鄰排序算法MPN（Multi-Pass Sorted Neighborhood）等等。其中SNM 算法主要思想是先通過關鍵屬性對數據記錄進行排序，將相似重復記錄聚在一起；然后移動一個固定大小為w 的窗口，每個新進入窗口的數據記錄都會與前w-1 條記錄進行比對，當比對完成后，窗口會繼續往下移動一格。該算法的不足主要有兩點。①固定窗口的大小w選擇困難。太小的窗口容易遺漏重復記錄，太大則增加時間復雜度；②窗口單格滑動，效率低，每次窗口內的數據比對完成后，窗口都只向前滑動一格，在重復數據率低的數據段，效率非常低。MPN 則進一步將相似數據集中后，再進行識別。但該算法不僅要多次使用SNM 還需要多次選擇不同特征進行排序，計算時間復雜度遠高于SNM。

因此，以上算法都不適合重復度低的時序數據，本文以窗口技術為基礎，針對低重復度時序數據的特征，提出一種相似重復數據檢測算法DS-SNM（Dynamic Sliding-Sorted Neighborhood Method），該算法減少非重復數據的比對次數，提高了算法的效率。

2 DS-SNM算法

眾所周知，在實際的應用中，相似重復數據通常分布并不均勻，比如在某裝備信息管理系統數據中，部分區域相似重復記錄特別集中，部分區域十分稀疏，而更多部分則完全沒有重復記錄。這樣的數據分布特點，就要求算法窗口能根據實際數據分布情況動態調節大小，以實現最高效率。具體需要當相似重復記錄密集時，縮小窗口，而當重復記錄稀疏時，則增大窗口。通過窗口大小的自動伸縮能力來適配相似重復記錄的分布，從而提高數據清洗的效率。

另一方面，對于時序數據，時間屬性是排序和比較的關鍵特征。時序數據產生相似重復的主要原因是在相同抽樣時間點產生了多條數據記錄。以某裝備信息管理系統數據為例，其數據來源主要來自某裝備在服役期間各時間點的采樣上報，樣本特征屬性包含完好率、故障率、剩余壽命等幾十項指標，這些數據為后續對裝備質量的評估、預測和預警打下了基礎。但是由于系統數據以人工錄入為主，且單個業務流程中人工干預的步驟較多，導致數據質量不高，易產生相似重復記錄。如多單位重復上報、漏報、錯報，存在主觀性指標等。該場景下數據量較大，且要求在同一時間單位內單臺裝備只能有一條有效數據。

航空質控數據如表1 所示，其中，第3 和第4 條為相似記錄，第3和第5條記錄為重復記錄。

表1 重復數據的示例

基于上述數據特征，本文在SNM 算法的基礎上，不降低查全率的前提下，針對時序數據提出了DSSNM算法，目的是為了改善SNM 算法中窗口大小選擇難、單格窗口移動效率低的問題。

2.1 算法描述

DS-SNM主要引入以下思想：

⑴ 利用時序特性，減少比對的次數。在原始SNM 算法窗口中數據記錄進行比對的過程中，假設窗口大小為，則需要每次將滑動窗口中的最后一條記錄與窗口內前-1 條數據做-1 次比對。而時序性數據有著天然的時序特點，理論上，對于同一個實體，每個采樣時間點t有且僅有一條數據。假設某個時間塊中有個采樣點，那應該有且僅有n 條數據。據此，我們對窗口中的數據比對次數進行優化。假設，在窗口中實體A 有條時序數據，第一條數據為D，其時間戳為，最后一條數據記錄為D ，其時間戳為，數據記錄的采樣頻率為，當(-)*+1=時，則表示該窗口中沒有重復數據，不需要再對窗口中的數據做額外的比對。因此，當連續無相似重復記錄時，一個窗口中只需要做一次比對，該策略在相似重復記錄稀疏的數據段的效果最明顯，能極大降低比對的次數。

⑵采用跳躍滑動窗口，提高窗口移動效率。在SNM 算法中，每次處理完本窗口的比對后，會自動向下移動一條記錄的位移，對于包含n 條數據的數據集，一共要移動n-w+1 次窗口。本文對窗口滑動的方式做了優化，根據不同的情況給出了不同的滑動策略。假設，當前窗口中有n 條時序數據為＜…,D＞，如果窗口時段內的理論采樣次數亦等于，且窗內第一條記錄和最后一條記錄實體類型相同，則表示該窗口中沒有重復記錄，我們直接將窗口移動至窗口的末端，即D為下一窗口的第一條記錄；當本窗口中對應的n條記錄經過首尾比對，發現窗口中不止一個實體，我們先通過二分搜索法找到最早發生實體變化的位置，窗口則滑動到該變化位置處。

⑶窗口大小自適應。SNM 算法采用固定大小的窗口，而窗口大小的選擇除了對相似重復記錄清除的效率有很大影響外，同時也影響識別準確性。對此，本文引入窗口自適應策略，當前窗口大小由上一窗口重復率決定。

2.2 算法實現

基于以上思想，DS-SNM算法的具體步驟如下：

設窗口大小為，初始值為2，最大值為w，數據采樣頻率為，窗口內記錄為＜D,D,D…,D ＞，每條記錄至少包含時間戳、實體唯一標識和用于對比相似重復性的特征集三個屬性。第一條數據D，對應的時間戳為T，最后一條數據D ，對應的時間戳為T ，那么，對于同一個實體而言，從T到T 之間的理論記錄條數應為：

設窗口內相似重復記錄數為d，則窗口內記錄的相似重復率為：

算法描述如下：

⑴先按時間戳排序，時間戳相同的記錄按屬性排序，當時間戳和屬性均相同時，則按特征集排序，得到排序數據集，并初始化相關窗口參數。

⑵ 比較窗口中第一條記錄D和最后一條記錄D 的實體標識屬性。如果兩條記錄的屬性相同，轉向⑶，否則轉向⑺。

⑶ 計算窗口中第一條記錄D和最后一條記錄D 的理論記錄數S，將S和窗口大小比較。

⑷如果S=，則表示該窗口內均為非重復記錄，則不需要對窗口中的數據再進行比對，窗口大小調整至當前窗口的兩倍，如果窗口大小已經大于w，則= w，且窗口直接滑動至D 處，本輪結束。

⑸如果T= T ，則表示該窗口內均為相似重復的記錄，則同樣窗口大小調整至當前窗口的兩倍，如果窗口大小大于w，則= w，且窗口直接滑動至D 處，本輪結束。

⑹ 否則，表示該窗口中有重復記錄，或者缺失記錄，轉向⑺。

⑺窗口內第一條記錄D開始在D到D 之間二分折半搜索尋找，即先對比D與 不滿足條件則比對D與 以此類推。如果遇到屬性與D不相同的記錄D，則轉向⑻，如果直到D處依然未轉向⑻，則最后轉向⑼。

⑻窗口直接滑動至D處，窗口大小不變，重新回到⑵。

⑼對窗口內的記錄采用SNM 比對，清洗相似重復記錄并計算出當前窗口內的重復率，清洗完成后將窗口滑動到下一條待處理記錄，并調整窗口大小=(×(1-))+2。重新回到⑵。

3 實驗結果與分析

本文將DS-SNM 應用于某裝備信息管理系統數據，選取其中50萬條連續記錄用于實驗。數據采樣率為每日一條記錄，每條記錄包含單位、時間、裝備型號、出廠號碼、狀態等多個屬性，以裝備型號和出廠號碼唯一確定單臺裝備實體，且理論上，該記錄表應該每天每臺裝備有且僅有一條記錄。但實際中，因一天中會有多個單位同時對單臺裝備進行記錄，或人工失誤多次輸入相似記錄的情況，因此存在不少重復數據。

本文采用SNM 與DS-SNM 算法在不同窗口大小（其中DS-SNM 為最大窗口大小）以及不同數據集規模的實際效果進行了對比。窗口大小選擇了4、16、32和64四個等級，數據集則選擇了從5萬到50萬的不同規模做對比。實驗中，我們以算法名加窗口大小表示一個帶具體配置的算法，例如SNM4 表示窗口大小為4 的SNM 算法，DS-SNM32 則表示最大窗口為32 的DS-SNM算法，以此類推，結果如圖1、圖2、圖3所示。

圖1 DS-SNM與SNM在不同窗口大小和不同數據集大小下的耗時對比

從圖1 和圖2 可以看出在選擇不同窗口大小及不同規模數據集下，DS-SNM 算法在時序數據的清洗上所產生的比對次數和耗時都顯著優于傳統的SNM。而從圖3 可以看出，SNM 算法隨窗口變大，比對次數線性增加，而DS-SNM 算法在最大窗口變大的情況下反而比對次數會小幅度下降。在準確率方面。效率提升的同時，相似重復數據的清洗準確率幾乎無變化，DS-SNM 與SNM 在該數據集上均達到95.6%以上的清洗率。在該數據集的不同規模子集下的準確率略有波動，均不超過1%。

圖2 DS-SNM與SNM在不同窗口大小和不同數據集大小下的比對次數對比

圖3 窗口大小對比對次數產生的影響

從實驗結果中我們可以看到，改進算法DS-SNM在不同規模的數據集下都比原SNM 算法大幅提高了效率，且數據集規模越大效率提升越明顯。該結果也印證了算法理論，由于DS-SNM 專門針對相似重復較稀疏的數據集而設計，在稀疏數據段做了跳躍優化策略，在密集相似重復的數據段則依然使用SNM，所以能在保證準確率的前提下提高算法效率。同時可以發現，原始的SNM 算法比對次數會隨著窗口變大而成倍增大，從而導致耗時大幅增加，而DS-SNM 中最大窗口變大所帶來的對比次數反而減少，因此該算法在窗口大小變化上也更具魯棒性。

4 結束語

時序數據隨時間產生，數據量大，時效性要求高，因此提高檢測算法的效率非常必要。本文針對時序相似重復數據清洗，對傳統SNM 算法進行改進提高，提出DS-SNM 算法。該算法引入多種有效機制，大大減少了數據比對次數，減少了時間的消耗。該算法特別適合大規模的時序數據處理，實驗結果也表明，該算法顯著提高了相似重復數據的檢測效率。