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

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

0 引言

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

1 相關(guān)工作

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

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

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

2 DS-SNM算法

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

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

航空質(zhì)控數(shù)據(jù)如表1 所示，其中，第3 和第4 條為相似記錄，第3和第5條記錄為重復(fù)記錄。

表1 重復(fù)數(shù)據(jù)的示例

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

2.1 算法描述

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

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

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

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

2.2 算法實現(xiàn)

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

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

設(shè)窗口內(nèi)相似重復(fù)記錄數(shù)為d，則窗口內(nèi)記錄的相似重復(fù)率為：

算法描述如下：

⑴先按時間戳排序，時間戳相同的記錄按屬性排序，當(dāng)時間戳和屬性均相同時，則按特征集排序，得到排序數(shù)據(jù)集，并初始化相關(guān)窗口參數(shù)。

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

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

⑷如果S=，則表示該窗口內(nèi)均為非重復(fù)記錄，則不需要對窗口中的數(shù)據(jù)再進(jìn)行比對，窗口大小調(diào)整至當(dāng)前窗口的兩倍，如果窗口大小已經(jīng)大于w，則= w，且窗口直接滑動至D 處，本輪結(jié)束。

⑸如果T= T ，則表示該窗口內(nèi)均為相似重復(fù)的記錄，則同樣窗口大小調(diào)整至當(dāng)前窗口的兩倍，如果窗口大小大于w，則= w，且窗口直接滑動至D 處，本輪結(jié)束。

⑹ 否則，表示該窗口中有重復(fù)記錄，或者缺失記錄，轉(zhuǎn)向⑺。

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

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

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

3 實驗結(jié)果與分析

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

本文采用SNM 與DS-SNM 算法在不同窗口大?。ㄆ渲蠨S-SNM 為最大窗口大?。┮约安煌瑪?shù)據(jù)集規(guī)模的實際效果進(jìn)行了對比。窗口大小選擇了4、16、32和64四個等級，數(shù)據(jù)集則選擇了從5萬到50萬的不同規(guī)模做對比。實驗中，我們以算法名加窗口大小表示一個帶具體配置的算法，例如SNM4 表示窗口大小為4 的SNM 算法，DS-SNM32 則表示最大窗口為32 的DS-SNM算法，以此類推，結(jié)果如圖1、圖2、圖3所示。

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

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

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

圖3 窗口大小對比對次數(shù)產(chǎn)生的影響

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

4 結(jié)束語

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