基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法

陳國(guó)瑞，袁旭華

(1.長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北荊州 434000；2.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西延安 716000)

1 引言

目前網(wǎng)絡(luò)技術(shù)高速發(fā)展，網(wǎng)絡(luò)應(yīng)用逐漸深入到人們生活的各個(gè)方面，面對(duì)海量的數(shù)據(jù)信息，需要更高的網(wǎng)絡(luò)安全性能[1]。網(wǎng)絡(luò)上各類攻擊手段屢見不鮮，全網(wǎng)流量的測(cè)量以及大規(guī)模數(shù)據(jù)處理相對(duì)困難。在某些情形下，異常數(shù)據(jù)實(shí)時(shí)檢測(cè)可發(fā)揮重要作用，依據(jù)獲取的異常數(shù)據(jù)，判斷突發(fā)事件是否發(fā)生，例如突發(fā)地震、突發(fā)火災(zāi)等[2]。

為此相關(guān)學(xué)者對(duì)其進(jìn)行了研究，并取得了一定的研究成果，文獻(xiàn)[3]提出基于鏈路狀態(tài)數(shù)據(jù)庫(kù)的數(shù)據(jù)中心網(wǎng)絡(luò)異常檢測(cè)算法，搜集鏈路狀態(tài)數(shù)據(jù)庫(kù)，采用改進(jìn)路由算法，得到全網(wǎng)路由形成路由域信息庫(kù)數(shù)據(jù)，對(duì)比準(zhǔn)確關(guān)聯(lián)鏈路和路由變化，檢測(cè)鏈路異常并定位故障。該算法能夠快速發(fā)現(xiàn)拓?fù)渥兓瑱z測(cè)時(shí)間較短，但該算法的誤報(bào)率較高。文獻(xiàn)[4]提出基于邊緣計(jì)算的傳感數(shù)據(jù)異常實(shí)時(shí)檢測(cè)算法，采用“時(shí)間序列”形式表示傳感數(shù)據(jù)，構(gòu)建傳感數(shù)據(jù)異常檢測(cè)模型，運(yùn)用時(shí)間序列相關(guān)特性，檢測(cè)實(shí)時(shí)傳感數(shù)據(jù)異常，輸出融合處理檢測(cè)結(jié)果。該算法的檢測(cè)準(zhǔn)確性較高，但檢測(cè)運(yùn)行時(shí)間較長(zhǎng)。

針對(duì)上述問題，提出了基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法，依據(jù)基于HDFS數(shù)據(jù)分布式云存儲(chǔ)體系所獲數(shù)據(jù)，使用多級(jí)哈希表搜索算法，完成異常數(shù)據(jù)查詢，采用基于支持向量數(shù)據(jù)描述，實(shí)現(xiàn)異常數(shù)據(jù)實(shí)時(shí)檢測(cè)。該算法具有較高的檢測(cè)能力，能夠有效降低誤報(bào)率，縮短運(yùn)行時(shí)間。

2 基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法

2.1 檢測(cè)算法框架

基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法是在Hadoop開源架構(gòu)上，搭建基于HDFS的數(shù)據(jù)分布式云存儲(chǔ)體系，實(shí)現(xiàn)異常數(shù)據(jù)實(shí)時(shí)檢測(cè)。檢測(cè)算法框架如圖1所示。

圖1 檢測(cè)算法框架

基于HDFS的數(shù)據(jù)分布式云存儲(chǔ)體系，通過布設(shè)在各區(qū)域的數(shù)據(jù)采集終端，采集異常檢測(cè)相關(guān)數(shù)據(jù)，并將數(shù)據(jù)存儲(chǔ)于各個(gè)二級(jí)數(shù)據(jù)中心的實(shí)體存儲(chǔ)節(jié)點(diǎn)中，將各二級(jí)數(shù)據(jù)中心的數(shù)據(jù)匯總后，存儲(chǔ)至數(shù)據(jù)中心，該數(shù)據(jù)中心可為數(shù)據(jù)查詢模塊和異常檢測(cè)模塊提供數(shù)據(jù)支撐[5]。數(shù)據(jù)查詢模塊采用多級(jí)哈希算法完成數(shù)據(jù)查詢，異常檢測(cè)模塊基于支持向量數(shù)據(jù)描述完成異常數(shù)據(jù)實(shí)時(shí)檢測(cè)。

2.2 基于多級(jí)哈希算法的數(shù)據(jù)查詢

依據(jù)基于HDFS數(shù)據(jù)分布式云存儲(chǔ)體系所獲數(shù)據(jù)建立分布式哈希表，并設(shè)計(jì)多級(jí)哈希表搜索算法，完成數(shù)據(jù)查詢。當(dāng)請(qǐng)求數(shù)據(jù)查找時(shí)，先檢索第一級(jí)哈希索引表，再檢索第二級(jí)哈希索引表，進(jìn)入第二級(jí)哈希索引表之前要依據(jù)(key，value)內(nèi)key對(duì)應(yīng)的value值進(jìn)入，一級(jí)哈希表內(nèi)分化出的數(shù)據(jù)信息存在二級(jí)哈希索引表，循環(huán)以上過程直至該數(shù)據(jù)被找到結(jié)束[6]。

使用此算法需在多級(jí)索引表內(nèi)存放全部數(shù)據(jù)對(duì)應(yīng)信息所需的索引。用O(log(m1+m2+…))表示算法的時(shí)間復(fù)雜度，第一級(jí)索引的信息條數(shù)用m1表示，第二級(jí)索引的信息條數(shù)用m2表示，逐次向下使用此方式對(duì)各級(jí)索引表的key列進(jìn)行檢索[7]。因?yàn)楦鞅淼乃饕龡l目在設(shè)計(jì)的多級(jí)索引表算法中數(shù)量一致，所以對(duì)此時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)化，用O(logm*n)表示簡(jiǎn)化后的時(shí)間復(fù)雜度，其內(nèi)索引的級(jí)數(shù)用n表示，單個(gè)索引表內(nèi)信息條數(shù)用m表示。

O(logN)+O(logM)用來表示常規(guī)哈希算法的時(shí)間復(fù)雜度。平均從異常數(shù)據(jù)表內(nèi)查找所需數(shù)據(jù)的key所用的時(shí)間用O(logN)表示，平均從一條擁有各個(gè)數(shù)據(jù)量記錄內(nèi)查找指定信息的時(shí)間用O(logM)表示。m、n、M、N等值決定了兩種算法的時(shí)間復(fù)雜度，而m、n、M、N的參數(shù)值由數(shù)據(jù)量大小和多級(jí)索引的設(shè)計(jì)方式?jīng)Q定。由于搜索路由表時(shí)需要大量時(shí)間，常規(guī)哈希算法的總開銷超過了多級(jí)哈希算法。

2.3 基于支持向量數(shù)據(jù)描述的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)

2.3.1 支持向量數(shù)據(jù)描述分類器

支持向量數(shù)據(jù)描述為一種數(shù)據(jù)描述算法，是基于支持向量機(jī)形成。其主要內(nèi)容是：通過計(jì)算最小超球體邊界形容數(shù)據(jù)的分布范圍，其最小超球體邊界涵蓋一組數(shù)據(jù)。

設(shè)定一個(gè)數(shù)據(jù)集{xi，i=1，…N}，其中包含N個(gè)數(shù)據(jù)對(duì)象，設(shè)定一個(gè)根據(jù)中心a和半徑R>0確定的超球體，其中容納此數(shù)據(jù)集，該數(shù)據(jù)集用體積最小的超球體來表示，為尋求一個(gè)體積最小的超球體，使用支持向量數(shù)據(jù)描述通過最小化R2來尋找，使此球體能容納所有(或更多)的xi。在超球體外側(cè)存放異常點(diǎn)，將異常點(diǎn)排除在超球體外側(cè)是為了達(dá)到減輕異常點(diǎn)的影響，利用松弛變量ξi進(jìn)行排除[8]。上述過程可形容為二次規(guī)劃問題，由如下式(1)表示

(1)

式(1)中，控制球體體積與誤差之間折中得出常數(shù)用C表示。其約束條件可表示

(xi-a)T(xi-a)≤R2+ζ2

?iζ≥0

(2)

根據(jù)拉格朗日泛函的鞍點(diǎn)給出上述問題最優(yōu)解，可表示為

(3)

式(3)內(nèi)，拉格朗日系數(shù)用ai≥0，γi≥0表示。該泛函對(duì)R，a和ζi的偏倒數(shù)設(shè)為等于零，以獲取最小值表示為

(4)

(5)

C-ai-γi=0，i=1，…N

(6)

根據(jù)上述公式可得，線性加權(quán)組合加權(quán)系數(shù)ai與數(shù)據(jù)對(duì)象xi可獲得最小超球體的中心。對(duì)偶問題的最大化問題可由最小化問題轉(zhuǎn)化可表示為

(7)

由式(8)表示其約束條件

(8)

假如球體的半徑等于或大于新數(shù)據(jù)對(duì)象z到球體之間的距離，則此數(shù)據(jù)對(duì)象可稱為正常數(shù)據(jù)，反之為異常數(shù)據(jù)表示為

(z-a)T(z-a)≤R2

(9)

數(shù)據(jù)空間在球形的分布可由上述方法描述。現(xiàn)實(shí)情況中，呈現(xiàn)球狀分布的緊湊數(shù)據(jù)依然不能由去掉異常數(shù)據(jù)之后獲取。內(nèi)積形式描述式(7)最大值求解問題，為獲取一個(gè)更精準(zhǔn)的數(shù)據(jù)描述，利用滿足Mercer定理的核函數(shù)[9]K(xi·xj)替代內(nèi)積(xi·xj)，表示為

(10)

正常數(shù)據(jù)是指該測(cè)試對(duì)象滿足上述公式，不滿足為異常數(shù)據(jù)。核函數(shù)用K(x·y)表示，通常使用以下核函數(shù)

多項(xiàng)式核：K(x·y)=(x·y+1)d

Sigmoid核：K(x·y)=tanh(v(x·y)+c)

經(jīng)廣泛研究，對(duì)于大量不同類型的分類問題，更適合應(yīng)用較廣的高斯核函數(shù)，因?yàn)槠渚哂休^強(qiáng)的泛化學(xué)習(xí)能力，所以本文使用高斯核函數(shù)。

2.3.2 支持向量數(shù)據(jù)描述異常檢測(cè)分類器優(yōu)化求解

設(shè)計(jì)最小閉包球算法優(yōu)化求解支持向量數(shù)據(jù)描述異常檢測(cè)分類器，通過找到最小閉包球解決支持向量機(jī)問題，用來降低訓(xùn)練算法的時(shí)間和空間復(fù)雜度。支持向量數(shù)據(jù)描述通常解決單類問題，其也可表示為一個(gè)最小閉包球問題。最小閉包球問題形式化描述及求解算法過程如下：

用以下式(11)形容支持向量數(shù)據(jù)描述問題

(11)

上述式(11)中，從輸入空間至高維特征空間的映射用φ(xi)表示。

用矩陣描述與式(11)對(duì)應(yīng)的對(duì)偶問題

(12)

上述式(12)內(nèi)，核函數(shù)矩陣是K=[k(xi，xj)]；拉格朗日系數(shù)[11]是a=[a1，…，am]。

式(12)為二次規(guī)劃問題，依據(jù)求解a可得

(13)

R=a’diag(K)-a′Ka

(14)

可用最小閉包球問題表示式(12)形式的優(yōu)化問題[12]。

用以下過程表示求解最小閉包球問題的算法：

假設(shè)用St、ct與Rt描述算法在第t次迭代中球的核心集、中心與半徑。將M(S)的(1+ε)近似為球B(cB，rB)、ε>0給出，球B的中心與半徑依次用cB與rB描述。

步驟4：對(duì)新的最小閉包球MEB(St+1)采用式(14)進(jìn)行尋找；然后對(duì)新球的中心與半徑采用式(15)(16)來計(jì)算；用ct+1=cMEB(St+1)、Rt+1=rMEB(St+1)表示。

步驟5：t=t+1，轉(zhuǎn)到步驟2；

步驟4內(nèi)找尋新的最小閉包球可以探知算法的空間復(fù)雜度，在找尋新的最小閉包球時(shí)，式(13)與式(14)的二次規(guī)劃問題計(jì)算才采用核心集。用O(|St|2)表示空間復(fù)雜度，其在第t次迭代中需要使用。O(1/ε2)表示整個(gè)算法的空間復(fù)雜度，源于算法收斂之前最多循環(huán)2/ε次。算法的空間復(fù)雜度線性和樣本點(diǎn)數(shù)集m不發(fā)生關(guān)系，基于ε是不變的。

對(duì)上述算法分析，分析時(shí)間和空間復(fù)雜度，得知此算法空間復(fù)雜度與樣本點(diǎn)數(shù)m無關(guān)，但時(shí)間復(fù)雜度與樣本點(diǎn)數(shù)m呈線性。通過上述步驟，利用最小閉包球算法，根據(jù)樣本數(shù)量的增多，使該優(yōu)化算法的時(shí)間、空間復(fù)雜度緩慢增長(zhǎng)，對(duì)于高維大規(guī)模數(shù)據(jù)集求解，優(yōu)化求解支持向量數(shù)據(jù)描述異常檢測(cè)分類器，實(shí)現(xiàn)異常數(shù)據(jù)實(shí)時(shí)檢測(cè)。

3 實(shí)驗(yàn)分析

為了驗(yàn)證基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法的有效性，在Redis網(wǎng)絡(luò)數(shù)據(jù)集(https:∥github.com/microsoftarchive/redis/releases)中選取4000個(gè)數(shù)據(jù)，分別采用文獻(xiàn)[3]算法、文獻(xiàn)[4]算法和所提算法，在MATLAB軟件平臺(tái)上進(jìn)行對(duì)比測(cè)試，分析不同算法檢測(cè)網(wǎng)絡(luò)異常數(shù)據(jù)的通信開銷比值，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 不同算法的通信開銷對(duì)比

由圖2實(shí)驗(yàn)結(jié)果可知，隨著數(shù)據(jù)量的增加，不同算法的通信開銷比值隨之增大，當(dāng)數(shù)據(jù)量為4000MB時(shí)，文獻(xiàn)[3]算法的通信開銷比值為28%，文獻(xiàn)[4]算法的通信開銷比值為22%，而所提算法的通信開銷比值為10%。由此可知，所提算法的通信開銷比值較小，在異常數(shù)據(jù)檢測(cè)時(shí)，可有效節(jié)省通信開銷。

進(jìn)一步驗(yàn)證基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法的檢測(cè)運(yùn)行時(shí)間，在數(shù)據(jù)量不同時(shí)，分析不同算法的檢測(cè)運(yùn)行時(shí)間，結(jié)果如圖3所示。

圖3 不同算法的檢測(cè)運(yùn)行時(shí)間對(duì)比

分析圖3可知，隨著數(shù)據(jù)量的增加，不同算法的檢測(cè)運(yùn)行時(shí)間隨之增加。當(dāng)數(shù)據(jù)量達(dá)到4000MB時(shí)，文獻(xiàn)[3]算法的平均檢測(cè)運(yùn)行時(shí)間為5.3s，文獻(xiàn)[4]算法的平均檢測(cè)運(yùn)行時(shí)間為4.6s，而所提算法的平均檢測(cè)運(yùn)行時(shí)間僅為2.5s。由此可知，所提算法的檢測(cè)運(yùn)行時(shí)間較短。因?yàn)樗崴惴ɡ镁€性關(guān)系描述時(shí)間復(fù)雜度，對(duì)于高維大規(guī)模數(shù)據(jù)集求解，根據(jù)樣本數(shù)量的增多，優(yōu)化算法時(shí)間，從而有效縮短檢測(cè)運(yùn)行時(shí)間。

在此基礎(chǔ)上，對(duì)比不同算法的異常數(shù)據(jù)檢測(cè)率，對(duì)比結(jié)果如圖4所示。

圖4 不同算法的異常數(shù)據(jù)檢測(cè)率對(duì)比

根據(jù)圖4可知，當(dāng)數(shù)據(jù)量達(dá)到4000MB時(shí)，文獻(xiàn)[3]算法的平均異常數(shù)據(jù)檢測(cè)率為89.6%，文獻(xiàn)[4]算法的平均異常數(shù)據(jù)檢測(cè)率為91.2%，而所提算法的平均異常數(shù)據(jù)檢測(cè)率高達(dá)98%。由此可知，所提算法的異常數(shù)據(jù)檢測(cè)率較高，具有較高的檢測(cè)能力。因?yàn)樗崴惴▽?duì)于求解高維大規(guī)模數(shù)據(jù)集，采用最小閉包球算法，隨著樣本數(shù)量增長(zhǎng)，其空間復(fù)雜度較為緩慢，從而提高了異常數(shù)據(jù)檢測(cè)率。

為了驗(yàn)證所提算法的準(zhǔn)確性，在數(shù)據(jù)量不同時(shí)，對(duì)比不同算法的誤報(bào)率，結(jié)果如圖5所示。

圖5 不同算法的誤報(bào)率對(duì)比

由圖5可知，隨著數(shù)據(jù)規(guī)模的增大，不同算法的誤報(bào)率逐漸增高，當(dāng)數(shù)據(jù)量為4000MB時(shí)，文獻(xiàn)[3]算法與文獻(xiàn)[4]算法的最高誤報(bào)率為2.8%、2.48%，而所提算法的最高誤報(bào)率為0.8%，低于其它兩種算法，且所提算法的誤報(bào)率始終保持在1.0%以下，由此可知，所提算法的誤報(bào)率較低。因?yàn)樗崴惴ㄔO(shè)計(jì)最小閉包球算法優(yōu)化求解支持向量數(shù)據(jù)描述異常檢測(cè)分類器，通過最小閉包球解決支持向量機(jī)問題，從而降低訓(xùn)練算法的誤報(bào)率。

4 結(jié)論

為了提高異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法檢測(cè)率，降低誤報(bào)率高，縮短運(yùn)行時(shí)間，提出基于HDFS開源架構(gòu)的異常數(shù)據(jù)實(shí)時(shí)檢測(cè)算法。根據(jù)HDFS建立數(shù)據(jù)分布式云存儲(chǔ)體系，設(shè)計(jì)多級(jí)哈希表搜索算法查詢異常數(shù)據(jù)，采用支持向量數(shù)據(jù)描述，結(jié)合最小閉包球算法，降低訓(xùn)練算法的時(shí)間和空間復(fù)雜度的同時(shí)，實(shí)現(xiàn)異常數(shù)據(jù)檢測(cè)。該算法可以有效提高檢測(cè)率，降低誤報(bào)率，縮短運(yùn)行時(shí)間。在未來仍需進(jìn)一步研究，對(duì)于數(shù)據(jù)的海量增長(zhǎng)繼續(xù)對(duì)算法性能進(jìn)行改善，盡可能實(shí)時(shí)檢測(cè)更多的異常數(shù)據(jù)。