基于最小哈希的網(wǎng)絡(luò)多路虛假數(shù)據(jù)清洗算法

王 影,李柯景

(1. 長(zhǎng)春工業(yè)大學(xué)人文信息學(xué)院,吉林 長(zhǎng)春 130122;2. 長(zhǎng)春大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,吉林 長(zhǎng)春 130022)

1 引言

計(jì)算機(jī)網(wǎng)絡(luò)與人們的生活密切相關(guān),但由于網(wǎng)絡(luò)儲(chǔ)存、計(jì)算與通信資源方面的約束,網(wǎng)絡(luò)內(nèi)的重要信息很容易被攻擊者竊取[1]。網(wǎng)絡(luò)安全極大程度上影響了用戶的正常應(yīng)用需求,網(wǎng)絡(luò)安全不光牽涉通信內(nèi)容的保密性、完備性與可用性,還要考慮是否會(huì)被攻擊者注入數(shù)量眾多的虛假數(shù)據(jù)。此類虛假數(shù)據(jù)會(huì)讓網(wǎng)絡(luò)做出錯(cuò)誤的預(yù)警判斷,耗損網(wǎng)絡(luò)生命周期,無(wú)法保證自身正常運(yùn)行。清洗虛假數(shù)據(jù),維護(hù)網(wǎng)絡(luò)合理運(yùn)行是當(dāng)前計(jì)算機(jī)領(lǐng)域亟需解決的重要問(wèn)題[2]。

針對(duì)數(shù)據(jù)清洗問(wèn)題,文獻(xiàn)[3]針對(duì)風(fēng)速-功率散點(diǎn)圖中的離群異常點(diǎn)、0功率堆積點(diǎn)等異常點(diǎn),分別組建基于密度聚類法、截?cái)喾?、斜率控制法、核密度估?jì)法的異常數(shù)據(jù)識(shí)別模型,完成數(shù)據(jù)定向清洗。文獻(xiàn)[4]提出一種滑動(dòng)標(biāo)準(zhǔn)差下的異常數(shù)據(jù)清洗方法。分析異常數(shù)據(jù)來(lái)源與分布特性,推導(dǎo)滑動(dòng)標(biāo)準(zhǔn)差。將滑動(dòng)標(biāo)準(zhǔn)差曲線上翹當(dāng)作異常評(píng)估準(zhǔn)則,達(dá)到數(shù)據(jù)定向清洗目的。

上述兩種方案都能抵抗虛假數(shù)據(jù)的注入攻擊,但無(wú)法降低網(wǎng)絡(luò)資源損耗,不適用于節(jié)點(diǎn)眾多的網(wǎng)絡(luò)多路數(shù)據(jù)。為此,提出一種基于最小哈希的網(wǎng)絡(luò)多路虛假數(shù)據(jù)清洗算法。首先將多路數(shù)據(jù)進(jìn)行編碼轉(zhuǎn)換,確保數(shù)據(jù)完整性,使用最小哈希計(jì)算數(shù)據(jù)之間的相似度,明確虛假數(shù)據(jù)與真實(shí)數(shù)據(jù)的區(qū)別,最后使用遺傳神經(jīng)網(wǎng)絡(luò)方法實(shí)現(xiàn)虛假數(shù)據(jù)清洗。

2 網(wǎng)絡(luò)多路數(shù)據(jù)編碼轉(zhuǎn)換

在完成多路網(wǎng)絡(luò)虛假數(shù)據(jù)清洗之前,首先要把網(wǎng)絡(luò)多路數(shù)據(jù)進(jìn)行編碼轉(zhuǎn)換,讓網(wǎng)絡(luò)數(shù)據(jù)格式更加統(tǒng)一,增強(qiáng)虛假數(shù)據(jù)清洗準(zhǔn)確性。數(shù)據(jù)編碼轉(zhuǎn)換的核心要素是設(shè)計(jì)編碼對(duì)照表,使用代碼關(guān)聯(lián)屬性特質(zhì),構(gòu)造映射統(tǒng)計(jì)表,實(shí)現(xiàn)多路數(shù)據(jù)全局整合。數(shù)據(jù)編碼轉(zhuǎn)換過(guò)程參考圖1。

圖1 數(shù)據(jù)編碼轉(zhuǎn)換過(guò)程

按照過(guò)往對(duì)不同類型數(shù)據(jù)標(biāo)準(zhǔn)與結(jié)構(gòu)數(shù)據(jù)庫(kù)實(shí)現(xiàn)對(duì)照轉(zhuǎn)換遷移累積的經(jīng)驗(yàn),融合專家建議,在著重分析業(yè)務(wù)庫(kù)數(shù)據(jù)準(zhǔn)則與結(jié)構(gòu)前提下,使用機(jī)器學(xué)習(xí)模式逐漸改善規(guī)則缺陷,構(gòu)成可以支撐數(shù)據(jù)視圖展示與數(shù)據(jù)表項(xiàng)擇取的先驗(yàn)知識(shí)庫(kù)[5]。

關(guān)于網(wǎng)絡(luò)多源及異構(gòu)數(shù)據(jù)庫(kù)內(nèi)不同數(shù)據(jù)的編碼準(zhǔn)則,為處理類別差異較大的數(shù)據(jù)字段與屬性編碼狀態(tài)各異的問(wèn)題,采用特征歸納相關(guān)性模型完成分類,即探尋和總結(jié)特征相關(guān)性特質(zhì),對(duì)比結(jié)果在特征上的相近程度。倘若類型集合C=(C1,C2,…,Cn),訓(xùn)練集D包含m個(gè)屬性,把編碼分類定義成編碼類型下的后驗(yàn)概率問(wèn)題,設(shè)置固定編碼為d,將從屬類型Ci的概率描述成

(1)

式中,P(ci)表示類型先驗(yàn)概率。

編碼轉(zhuǎn)換特征的挑選是對(duì)編碼特征集合從上至下降維的流程[6],通常剔除部分特征組來(lái)完成降維目標(biāo)。按照特征真實(shí)偏重情況,對(duì)應(yīng)增添特征項(xiàng)權(quán)重,計(jì)算過(guò)程為

W(tik)=tf(tik)*idf(tk)*MI(w,tik)*Dk*

(2)

式中,W(tik)代表類Ci內(nèi)第k個(gè)特征的權(quán)重值,Dk是類間偏差的均值,MI(w,tik)表示互信息,即第k個(gè)特征項(xiàng)與類型間的獨(dú)立關(guān)系。

為增強(qiáng)特征網(wǎng)絡(luò)多路數(shù)據(jù)的編碼變換精度,使用多維特征匹配手段對(duì)低維數(shù)據(jù)編碼特征空間實(shí)施匹配[7]。將兩種數(shù)據(jù)通過(guò)特征挑選與降維后得到的自身低維特征矢量空間記作

(3)

為完善數(shù)據(jù)編碼轉(zhuǎn)換特征匹配正確性,把低關(guān)聯(lián)度大于0.6的設(shè)定成標(biāo)準(zhǔn)匹配,低關(guān)聯(lián)大于0.4且高關(guān)聯(lián)大于0.6的設(shè)定成基礎(chǔ)匹配,高關(guān)聯(lián)小于0.4的為軟性匹配,實(shí)現(xiàn)高精度特征編碼轉(zhuǎn)換目標(biāo)。

3 基于最小哈希的網(wǎng)絡(luò)多路數(shù)據(jù)相似度計(jì)算

最小哈希是衡量?jī)蓚€(gè)集合相關(guān)性最常用的方法之一,本文提出基于最小哈希的網(wǎng)絡(luò)多路數(shù)據(jù)相似度計(jì)算方法,在相似度小于設(shè)定閾值狀態(tài)下,認(rèn)定該數(shù)據(jù)為虛假數(shù)據(jù),完成虛假數(shù)據(jù)篩選。

(4)

(5)

(6)

最小哈希下網(wǎng)絡(luò)多路數(shù)據(jù)相似度推算過(guò)程是

(7)

利用式(7)就能得到多路網(wǎng)絡(luò)數(shù)據(jù)之間的相似度。數(shù)據(jù)間相似度等于設(shè)定閾值1則為真實(shí)數(shù)據(jù),小于設(shè)定閾值1判定此數(shù)據(jù)為虛假數(shù)據(jù),需要對(duì)其采取數(shù)據(jù)清洗,從而保證網(wǎng)絡(luò)數(shù)據(jù)安全,獲得高質(zhì)量數(shù)據(jù)集。

4 基于遺傳神經(jīng)網(wǎng)絡(luò)的多路虛假數(shù)據(jù)清洗算法

在明確劃分真實(shí)數(shù)據(jù)與虛假數(shù)據(jù)前提下,設(shè)計(jì)一種基于遺傳神經(jīng)網(wǎng)絡(luò)的多路虛假數(shù)據(jù)清洗算法。首先構(gòu)建前饋型神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)清洗模型,如圖2所示。

圖2 前饋型神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)清洗模型示意圖

該模型包含輸入、隱含與輸出三個(gè)層次,每個(gè)層次中均擁有數(shù)量眾多的神經(jīng)元節(jié)點(diǎn)。神經(jīng)元之間由權(quán)值Wij互相連接。各神經(jīng)元節(jié)點(diǎn)都擁有較多的輸入和一個(gè)輸出,將其數(shù)學(xué)解析式記作

Oj=f(netj)

(8)

netj=∑Wij·Xi-θj

(9)

其中,Oj表示某層內(nèi)第j個(gè)節(jié)點(diǎn)的輸出值,Wij是上層第i個(gè)節(jié)點(diǎn)和目前層第j個(gè)節(jié)點(diǎn)的連接權(quán)值,Xi代表上一層節(jié)點(diǎn)i對(duì)目前層節(jié)點(diǎn)j的輸入,θj是目前層第j個(gè)節(jié)點(diǎn)的臨界值,f(·)是神經(jīng)元激勵(lì)函數(shù),通常使用Sigmoid函數(shù),得到

(10)

設(shè)置一個(gè)訓(xùn)練樣本p,在輸入層輸入樣本,則網(wǎng)絡(luò)模型樣本訓(xùn)練偏差是

(11)

其中,dpj表示輸出層第j個(gè)節(jié)點(diǎn)的預(yù)期輸出,Opj是輸出層中,第j個(gè)節(jié)點(diǎn)的真實(shí)輸出,假如訓(xùn)練樣本數(shù)據(jù)集內(nèi)一共包含P′個(gè)樣本,那么網(wǎng)絡(luò)模型訓(xùn)練偏差總和為

(12)

如果網(wǎng)絡(luò)模型擁有p個(gè)輸入,q個(gè)輸出,那么可以把輸出結(jié)果看作從p維歐式空間至q維歐式空間的非線性映射,此類映射能夠接近隨機(jī)的連續(xù)函數(shù)。實(shí)施虛假數(shù)據(jù)清洗過(guò)程中,輸出層內(nèi)的值是一個(gè)待補(bǔ)充值,輸入層是一個(gè)和缺失值有關(guān)的值,隱含層節(jié)點(diǎn)個(gè)數(shù)通常利用實(shí)驗(yàn)來(lái)明確。把神經(jīng)網(wǎng)絡(luò)的整體權(quán)值替換成矩陣W,就能呈現(xiàn)出神經(jīng)網(wǎng)絡(luò)模型對(duì)待處理問(wèn)題的知識(shí)儲(chǔ)備情況。經(jīng)過(guò)不斷地訓(xùn)練樣本與修正權(quán)值,讓網(wǎng)絡(luò)模型輸出結(jié)果逐步趨近預(yù)期值,在網(wǎng)絡(luò)輸出實(shí)現(xiàn)預(yù)期精準(zhǔn)度后,再進(jìn)行網(wǎng)絡(luò)收斂。

遺傳算法是一種在自然擇取與遺傳的全局優(yōu)化條件下的計(jì)算方法,使用選擇、交叉與變異三類基礎(chǔ)遺傳算子計(jì)算參變量,完成整體最優(yōu)搜尋,是一種可靠的網(wǎng)絡(luò)訓(xùn)練算法,同時(shí)也能獲得更好的虛假數(shù)據(jù)清洗結(jié)果。

把神經(jīng)網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的權(quán)值根據(jù)一定次序進(jìn)行排列,構(gòu)成一條染色體。染色體內(nèi)的基因就是神經(jīng)元權(quán)值。從種群內(nèi)挑選一條染色體u,將染色體內(nèi)的基因輸入至圖2的模型內(nèi)。依次引入訓(xùn)練樣本,推算網(wǎng)絡(luò)偏差總值E,并獲得染色體適應(yīng)度f(wàn)u

(13)

將遺傳算法運(yùn)算過(guò)程表示為圖3。

圖3 遺傳算法運(yùn)算過(guò)程

首先對(duì)參變量與種群進(jìn)行初始化。輸入神經(jīng)網(wǎng)絡(luò)的原始拓?fù)浣Y(jié)構(gòu)是m-n-k,m是輸入層節(jié)點(diǎn)數(shù)值,n是隱含層節(jié)點(diǎn)數(shù)值,輸入種群規(guī)模t=population,交叉概率為Pc,變異概率是Pm。

遺傳算法調(diào)節(jié)權(quán)值的性能較差,為了防止權(quán)值太小導(dǎo)致算法收斂性能遲緩,運(yùn)用勻稱分布的任意數(shù)值來(lái)完成種群初始化目標(biāo),將種群P與染色體選擇概率分別描述成

P={p1,p2,…,pt}

(14)

Si=α*(1-α)i-1

(15)

其中,α值通常為0.04,i=1,2,…,t。

把目前具備的染色體代入到圖2的模型內(nèi),并引入訓(xùn)練樣本,推算此染色體的偏差總值E、適應(yīng)度f(wàn)u,評(píng)估網(wǎng)絡(luò)偏差能否實(shí)現(xiàn)預(yù)期的偏差或最高迭代次數(shù),就可以實(shí)現(xiàn)終止迭代,反之繼續(xù)迭代,并把每個(gè)染色體根據(jù)適應(yīng)度從大到小進(jìn)行排列。

針對(duì)染色體v來(lái)說(shuō),推導(dǎo)它的累積概率qv,將其描述成

(16)

反復(fù)執(zhí)行上面的選擇、交叉、變異行為,持續(xù)生成全新的子代染色體,直到新一代種群規(guī)模和父代相等,這樣就實(shí)現(xiàn)了高精度虛假數(shù)據(jù)清洗全過(guò)程,為網(wǎng)絡(luò)數(shù)據(jù)的安全操作與應(yīng)用發(fā)揮關(guān)鍵作用。

5 仿真研究

分別從查全率、數(shù)據(jù)清洗效率兩方面驗(yàn)證本文網(wǎng)絡(luò)多路虛假數(shù)據(jù)清洗有效性,并與文獻(xiàn)[3]、[4]進(jìn)行仿真對(duì)比。把剔除的虛假數(shù)據(jù)和真實(shí)虛假數(shù)據(jù)個(gè)數(shù)的比率定義成查全率,查全率是權(quán)衡數(shù)據(jù)清洗方法優(yōu)劣的關(guān)鍵指標(biāo),查全率越大,表明所檢測(cè)的虛假數(shù)據(jù)記錄越多,充分說(shuō)明了數(shù)據(jù)清洗方法的真實(shí)性能。將查全率計(jì)算公式寫(xiě)成

(17)

式中,Nt表示剔除的虛假數(shù)據(jù)數(shù)量,N是真實(shí)虛假數(shù)據(jù)。

圖4是本文方法與兩個(gè)文獻(xiàn)方法的查全率實(shí)驗(yàn)對(duì)比結(jié)果。從圖4可知,三種方法在實(shí)驗(yàn)初期的查全率相差不多,但伴隨數(shù)據(jù)量的持續(xù)增多,本文方法的查全率逐漸變大,并最終趨于穩(wěn)定,維持在95%左右,文獻(xiàn)[3]方法查全率約為82%,文獻(xiàn)[4]查全率控制在75%上下。出現(xiàn)此種現(xiàn)象的原因在于,本文方法采用了最小哈希算法,可以有效計(jì)算出網(wǎng)絡(luò)多路數(shù)據(jù)之間的相似度,對(duì)真實(shí)數(shù)據(jù)與虛假數(shù)據(jù)采取有效劃分,極大提高虛假數(shù)據(jù)的查全率。

圖4 三種方法查全率對(duì)比

圖5是三種方法的虛假數(shù)據(jù)清洗效率對(duì)比。從圖5看到,在數(shù)據(jù)量為500時(shí),本文方法虛假數(shù)據(jù)清洗效率略低于兩個(gè)文獻(xiàn)方法,但在數(shù)據(jù)量不斷增多情況下,三種方法數(shù)據(jù)清洗效率之間的差別越來(lái)越少,最終在數(shù)據(jù)量為1000時(shí),本文方法數(shù)據(jù)清洗效率為最優(yōu),消耗時(shí)間最短,時(shí)間變化幅度基本趨于平穩(wěn),這也表明了所提方法尤為適用于網(wǎng)絡(luò)多路數(shù)據(jù)清洗的應(yīng)用環(huán)境,在龐大的多路數(shù)據(jù)量狀態(tài)下,依舊能以最快的速度完成虛假數(shù)據(jù)清洗目標(biāo),實(shí)用性強(qiáng)。

圖5 三種方法虛假數(shù)據(jù)清洗效率對(duì)比

6 結(jié)論

網(wǎng)絡(luò)多路數(shù)據(jù)具有易被攻擊的特性,為確保數(shù)據(jù)真實(shí)性與安全性,提出一種基于最小哈希的網(wǎng)絡(luò)多路虛假數(shù)據(jù)清洗算法。通過(guò)數(shù)據(jù)編碼轉(zhuǎn)換、相似度計(jì)算兩個(gè)步驟,了解虛假數(shù)據(jù)屬性特征,構(gòu)建前饋型神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)清洗模型,引入遺傳算法進(jìn)行網(wǎng)絡(luò)訓(xùn)練,完成高效準(zhǔn)確的虛假數(shù)據(jù)清洗任務(wù)。但在計(jì)算時(shí)并未考慮算法的收斂性,極易導(dǎo)致算法迭代次數(shù)偏高,在接下來(lái)的研究中會(huì)對(duì)此點(diǎn)加以精進(jìn)。