龐家樂，張 彥

(北京交通大學(xué)，北京 100044)

1 引言

在信息的錄入與集成過程中，若含有冗余、異常等屬性的數(shù)據(jù)沒有及時(shí)被處理，直接影響數(shù)據(jù)后續(xù)處理的準(zhǔn)確性。數(shù)據(jù)清洗作為一種應(yīng)用非常廣泛的、能提高數(shù)據(jù)質(zhì)量的方法之一，清洗對(duì)象主要以重復(fù)數(shù)據(jù)為主，包括缺失數(shù)據(jù)、重復(fù)數(shù)據(jù)以及亂碼數(shù)據(jù)等。其中，由于多數(shù)據(jù)融合而產(chǎn)生的重復(fù)數(shù)據(jù)是數(shù)據(jù)清洗的重點(diǎn)。標(biāo)注重復(fù)網(wǎng)絡(luò)數(shù)據(jù)，一方面可以去除掉空間內(nèi)重復(fù)存儲(chǔ)的數(shù)據(jù)集或者文件，優(yōu)化存儲(chǔ)空間；同時(shí)也可以降低網(wǎng)絡(luò)傳輸壓力，為數(shù)據(jù)復(fù)制節(jié)省了部分網(wǎng)絡(luò)帶寬。目前，數(shù)據(jù)清洗技術(shù)已經(jīng)非常成熟，但如何精準(zhǔn)標(biāo)注網(wǎng)絡(luò)重復(fù)數(shù)據(jù)仍是相關(guān)領(lǐng)域?qū)W者的重點(diǎn)分析難題。

文獻(xiàn)[1]通過無線傳感網(wǎng)絡(luò)的應(yīng)用坐標(biāo)系對(duì)數(shù)據(jù)重新配置，根據(jù)配置結(jié)果選擇其中存在的重復(fù)數(shù)據(jù)節(jié)點(diǎn)；然后，計(jì)算各個(gè)協(xié)議點(diǎn)的覆蓋面積大小，利用分類數(shù)據(jù)初始化的方法，使得各個(gè)協(xié)議點(diǎn)之間實(shí)現(xiàn)有效連接，完成無線傳感網(wǎng)絡(luò)重復(fù)數(shù)據(jù)的優(yōu)化檢測。該方法未考慮數(shù)據(jù)屬性和唯一IP之間的關(guān)系，檢測標(biāo)記效率過低，對(duì)于大規(guī)模的數(shù)據(jù)并不適合；文獻(xiàn)[2]提出利用多通道卷積機(jī)制，自動(dòng)化提取和處理公式圖片內(nèi)特征向量，使標(biāo)記過程更能適應(yīng)大規(guī)模的公式數(shù)量；將卷積神經(jīng)網(wǎng)絡(luò)的輸出模式設(shè)置為端到端，降低因步驟過多而出現(xiàn)誤差累積的幾率；最后，將重復(fù)數(shù)據(jù)檢測問題量化為對(duì)重復(fù)公式的檢測，實(shí)現(xiàn)冗余數(shù)據(jù)標(biāo)記。該方法對(duì)于不同質(zhì)量的公式圖片均能實(shí)現(xiàn)重復(fù)性檢測，但是該方法的標(biāo)注準(zhǔn)確率較低。

基于此，本文基于反向梯度深度學(xué)習(xí)算法，提出一種新的重復(fù)網(wǎng)絡(luò)數(shù)據(jù)標(biāo)注方法。首先，利用綜合加權(quán)法，檢測數(shù)據(jù)庫中的重復(fù)數(shù)據(jù)，再利用三區(qū)分快速算法對(duì)相似度過高的重復(fù)數(shù)據(jù)標(biāo)注。仿真結(jié)果也表明，本文方法具有非常理想的標(biāo)注效果，與其它方法相比，可在成本最低的前提下實(shí)現(xiàn)最高效率的檢測與標(biāo)注。

2 重復(fù)網(wǎng)絡(luò)數(shù)據(jù)檢測

2.1 數(shù)據(jù)字符串編輯距離的計(jì)算

本文利用綜合加權(quán)法計(jì)算各個(gè)數(shù)據(jù)的屬性權(quán)重值[3]，對(duì)每個(gè)數(shù)據(jù)字符串之間的編輯距離重新定義[4]，得到數(shù)據(jù)與數(shù)據(jù)距離之間相似度值。實(shí)現(xiàn)過程如下所示：

(1)

式中，Gst表示第s個(gè)操作者對(duì)屬性At設(shè)定的等級(jí)，Gt表示第t個(gè)屬性的最終統(tǒng)一等級(jí)。

通過式(2)計(jì)算數(shù)據(jù)屬性取值種數(shù)，減少數(shù)據(jù)因?qū)傩匀≈挡煌霈F(xiàn)計(jì)算復(fù)雜情況，在一定程度上提高算法的整體計(jì)算效率。

(2)

(3)

(4)

(5)

綜上所述，網(wǎng)絡(luò)中的重復(fù)數(shù)據(jù)利用綜合加權(quán)法計(jì)算各個(gè)數(shù)據(jù)屬性的權(quán)重值后，重新定義每個(gè)數(shù)據(jù)字符串之間的編輯距離，得到各個(gè)數(shù)據(jù)距離之間的相似度值，為后續(xù)進(jìn)行重復(fù)數(shù)據(jù)的檢測做好準(zhǔn)備工作。

2.2 重復(fù)數(shù)據(jù)檢測

(6)

(7)

(8)

(9)

3 反向梯度深度學(xué)習(xí)下重復(fù)網(wǎng)絡(luò)數(shù)據(jù)標(biāo)注

在實(shí)際的應(yīng)用網(wǎng)絡(luò)中，流動(dòng)數(shù)據(jù)量是非常巨大的，要對(duì)所有數(shù)據(jù)逐一檢測和重復(fù)數(shù)據(jù)標(biāo)記是非常困難的。因此，本文引入反向梯度學(xué)習(xí)算法，實(shí)現(xiàn)過程如下所示：

1)由于網(wǎng)絡(luò)數(shù)據(jù)庫中記錄的數(shù)據(jù)并不只有一個(gè)關(guān)鍵字，所以可以通過設(shè)置ID編號(hào)形式對(duì)其重新設(shè)定[9]。ID編號(hào)的權(quán)重值為0，不影響后續(xù)的計(jì)算過程中，可忽略不計(jì)。

2)建立數(shù)據(jù)關(guān)系記錄屬性表。遍歷所有數(shù)據(jù)，根據(jù)數(shù)據(jù)的屬性建立不同的屬性記錄庫，在屬性記錄庫中根據(jù)每個(gè)屬性建立屬性值記錄表。該表中記錄了各個(gè)數(shù)據(jù)不同的屬性值，以及屬性值相同的數(shù)據(jù)信息。這里所做的工作與倒排索引的思想類似，將“單詞”與“文本”按照倒排索引鏈表的結(jié)構(gòu)進(jìn)行排列，其中的記錄就用ID編號(hào)來表示。

3)將數(shù)據(jù)記錄設(shè)定為R={R1，R2，…，Rl}，用l來表示數(shù)據(jù)記錄的數(shù)量，與之對(duì)應(yīng)的某個(gè)數(shù)據(jù)記錄為Ri(1≤i≤l)。這兩個(gè)數(shù)據(jù)記錄的任意一個(gè)屬性p間關(guān)系用公式表示為：

M=A(Rip，Rjp)={0，1}(1≤i≤l，1≤j≤l，1≤p≤n)

(10)

式中，Rip=(ID1，ID2，…，IDm)，IDm表示某個(gè)數(shù)據(jù)屬性值出現(xiàn)相似或重復(fù)的記錄次數(shù)，n表示任意一個(gè)數(shù)據(jù)記錄具有n個(gè)屬性值的長度值，p表示某個(gè)屬性的第p個(gè)屬性值。

當(dāng)M=1時(shí)，可以判定這兩個(gè)數(shù)據(jù)記錄在p屬性下具有非常相似甚至重復(fù)部分；當(dāng)M=0時(shí)，則可以判定這兩個(gè)數(shù)據(jù)在p屬性下相似程度較低、不存在重復(fù)的情況。按照這種思路，對(duì)數(shù)據(jù)庫中的所有數(shù)據(jù)在某屬性下進(jìn)行計(jì)算比較。經(jīng)過比較，還可以得到數(shù)據(jù)記錄屬性值的具體值。對(duì)數(shù)據(jù)記錄之間的相似度定義過程如(11)所示

Qi，j，p=M*Wp

(11)

(12)

式中，Zi，j表示數(shù)據(jù)記錄i與數(shù)據(jù)記錄j之間的相似程度高低。

4)給定相似閾值U，用來判定二者之間是否存在重復(fù)。

Zi，j?U

(13)

5)在比較屬性值記錄表中的數(shù)據(jù)屬性時(shí)，如果按照順序逐個(gè)比較會(huì)花費(fèi)大量的時(shí)間。因此，本文引入快速排序算法，按照從大到小的順序排列，當(dāng)出現(xiàn)了相等的兩個(gè)屬性值后，把該數(shù)據(jù)挑選出來，后續(xù)不再進(jìn)行比較，減少計(jì)算時(shí)間。本文采用的是三區(qū)間比較方法，使得挑選出來的數(shù)據(jù)不再進(jìn)行排列比較，只允許大于或者小于選定的數(shù)再進(jìn)行排列比較。假設(shè)選定的數(shù)值為x，那么只針對(duì)大于x或者小于x的數(shù)值進(jìn)行排列比較即可，如圖1所示。

圖1 三區(qū)間數(shù)值排序示意圖

從圖1中可以看出，按照從左到右的掃描順序，指針lt始終保持[lo…lt]中的數(shù)字比x小，其它指針gt保持[g(t+1)…h(huán)y]中的數(shù)字比x大，指針y保持[lt…(y-1)]中的數(shù)字與x相等。[y…gt]之間的數(shù)字表示沒有進(jìn)行排列比較的數(shù)字，y從lo處開始進(jìn)行掃描：

當(dāng)a[y]

當(dāng)a[y]>v時(shí)，交換a[y]和a[gt]，gt指針會(huì)出現(xiàn)自減的情況；

當(dāng)a[y]=v時(shí)，y指針出現(xiàn)自增的情況。

4 算法實(shí)現(xiàn)步驟

1)為網(wǎng)絡(luò)數(shù)據(jù)庫中的數(shù)據(jù)記錄設(shè)置唯一的ID編號(hào)，同時(shí)構(gòu)建屬性記錄庫，在記錄庫中為每個(gè)屬性設(shè)置專屬的屬性值記錄表。

2)為數(shù)據(jù)庫中的每個(gè)數(shù)據(jù)都構(gòu)建一個(gè)單獨(dú)的屬性值記錄表，將數(shù)據(jù)的屬性值與ID編號(hào)存入到數(shù)據(jù)庫中，形成數(shù)據(jù)關(guān)系表，后續(xù)進(jìn)行排列與比較時(shí)直接參考該表即可。

3)完成以上操作后，根據(jù)屬性值記錄表和數(shù)據(jù)關(guān)系表，從屬性記錄庫中挑選數(shù)據(jù)，利用三區(qū)分快速算法按照數(shù)據(jù)屬性值從大到小的順序排列，與讀取的屬性值比較，以此來判斷數(shù)據(jù)之間是否存在相似度過高或者重復(fù)的情況。

當(dāng)出現(xiàn)相似度過高或者重復(fù)的情況時(shí)，用相應(yīng)的權(quán)重值乘以1，挑選出來，當(dāng)相似度過低時(shí)，結(jié)果直接等于0，不做任何計(jì)算。

將數(shù)據(jù)記錄與屬性值記錄表中的數(shù)據(jù)逐一進(jìn)行比較，最后的比較結(jié)果整合為數(shù)據(jù)之間的相似度值。

4)根據(jù)上述數(shù)據(jù)之間的相似度值以及預(yù)先設(shè)定的閾值大小，來判斷數(shù)據(jù)之間是否存在相似度過高或者重復(fù)的情況。

5)當(dāng)網(wǎng)絡(luò)數(shù)據(jù)庫中錄入了新的數(shù)據(jù)后，重復(fù)以上操作步驟，實(shí)現(xiàn)新數(shù)據(jù)與數(shù)據(jù)庫內(nèi)其它數(shù)據(jù)之間的相似度比較，以此實(shí)現(xiàn)對(duì)相似度過高或者重復(fù)數(shù)據(jù)的有效檢測與標(biāo)注。

5 仿真研究

5.1 仿真環(huán)境

仿真用到的計(jì)算機(jī)為Inter 133702.40GHzCPU，編程選擇的是JAVA語言。實(shí)驗(yàn)中用到是Oraclellg數(shù)據(jù)庫中隨機(jī)選取的6組數(shù)據(jù)，6組數(shù)據(jù)的數(shù)據(jù)量分別為45.6萬、53.6萬、184.7萬、207.9萬、294.5萬、315.5萬，運(yùn)用相關(guān)技術(shù)對(duì)數(shù)據(jù)進(jìn)行處理，使其分別包含0.48萬、1.21萬、1.35萬、2.15萬、3.12萬、3.66萬條重復(fù)數(shù)據(jù)。為了進(jìn)一步驗(yàn)證本文方法的性能，與文獻(xiàn)[1]提出的基于無線傳感網(wǎng)絡(luò)配置的重復(fù)數(shù)據(jù)標(biāo)注方法以及文獻(xiàn)[2]提出的基于多通道卷積機(jī)制的重復(fù)數(shù)據(jù)標(biāo)注方法展開了對(duì)比實(shí)驗(yàn)。

5.2 重復(fù)數(shù)據(jù)檢測與標(biāo)注數(shù)量對(duì)比

將本文方法與其它兩種方法在重復(fù)數(shù)據(jù)檢測與標(biāo)注數(shù)量方面進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 三種方法重復(fù)數(shù)據(jù)檢測與標(biāo)注數(shù)量對(duì)比

從圖2中可以看出，當(dāng)面對(duì)數(shù)據(jù)量跨度較大的數(shù)據(jù)集時(shí)，本文方法始終展現(xiàn)出了較高的檢測精度與標(biāo)注能力。文獻(xiàn)兩種算法檢測精度波動(dòng)起伏較大，且偏離正確值較遠(yuǎn)。這是由于這兩種方法沒有對(duì)數(shù)據(jù)記錄的屬性計(jì)算賦值，只考慮了主觀因素，而沒有將客觀因素考慮在內(nèi)，由此導(dǎo)致了較大的誤差。而本文方法可以深入挖掘數(shù)據(jù)之間的內(nèi)在聯(lián)系，對(duì)相似度過高或者重復(fù)的數(shù)據(jù)可以實(shí)現(xiàn)精準(zhǔn)的檢測與標(biāo)注。

5.3 重復(fù)數(shù)據(jù)檢測與標(biāo)注時(shí)間對(duì)比

接下來利用三種方法從檢測與標(biāo)注所需時(shí)間方面展開對(duì)比仿真，結(jié)果如圖3所示。

圖3 三種方法檢測與標(biāo)注所需時(shí)間對(duì)比

從圖3中可以看出，本文方法檢測與標(biāo)注所花費(fèi)的時(shí)間最少，并且隨著數(shù)據(jù)量的不斷增加，文獻(xiàn)方法所花費(fèi)的時(shí)間增長幅度越來越大。這是由于本文方法在進(jìn)行重復(fù)數(shù)據(jù)檢測與標(biāo)注的同時(shí)，利用三區(qū)分快速算法，將已經(jīng)完成比較的數(shù)據(jù)不再重復(fù)計(jì)算，只針對(duì)大于或小于特定數(shù)值的數(shù)據(jù)進(jìn)行排列比較，在一定程度上提高了算法整體的運(yùn)算效率。

5.4 本地服務(wù)器吞吐量及CPU占用率對(duì)比

接下來對(duì)三種算法在進(jìn)行重復(fù)數(shù)據(jù)的檢測與標(biāo)注時(shí)，本地服務(wù)器吞吐量情況進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 三種方法本地服務(wù)器吞吐量對(duì)比

從圖4中可以看出，三種方法中本文方法本地服務(wù)器吞吐量下降幅度最大，說明運(yùn)用本文方法不會(huì)對(duì)服務(wù)器性能產(chǎn)生較大的影響。其它兩種方法均占用了大量的本地服務(wù)器存儲(chǔ)空間。這是由于本文方法將經(jīng)過比較的數(shù)據(jù)挑選出來，不再重復(fù)進(jìn)行計(jì)算，在提高了算法計(jì)算效率的同時(shí)減少了計(jì)算成本。

本地服務(wù)器CPU占用情況如表1所示。

表1 本地服務(wù)器CPU占用情況對(duì)比/%

從表1中可以看出，相較于其它兩種方法來說，運(yùn)行本文方法占用的CPU內(nèi)存最少。這說明在運(yùn)行本文方法時(shí)，對(duì)服務(wù)器內(nèi)其它程序的運(yùn)行不會(huì)產(chǎn)生較大的影響。

6 結(jié)論

本文利用反向梯度深度學(xué)習(xí)算法實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)數(shù)據(jù)庫中重復(fù)數(shù)據(jù)的檢測與標(biāo)注，并與無線傳感網(wǎng)絡(luò)和深度卷積神經(jīng)網(wǎng)絡(luò)兩種方法展開對(duì)比實(shí)驗(yàn)，結(jié)果表明本文方法可以在花費(fèi)時(shí)間最少的前提下可實(shí)現(xiàn)最高精度的檢測與標(biāo)注，并且不限制數(shù)據(jù)集中數(shù)據(jù)量的多少。