面向時(shí)序的相似重復(fù)數(shù)據(jù)清洗算法優(yōu)化

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

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

0 引言

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

1 相關(guān)工作

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

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

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

2 DS-SNM算法

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

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

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

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

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

2.1 算法描述

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

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

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

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

2.2 算法實(shí)現(xiàn)

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

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

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

算法描述如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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