基于HDFS開源架構的異常數據實時檢測算法

陳國瑞，袁旭華

(1.長江大學計算機科學學院，湖北荊州 434000；2.延安大學數學與計算機科學學院，陜西延安 716000)

1 引言

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

為此相關學者對其進行了研究，并取得了一定的研究成果，文獻[3]提出基于鏈路狀態數據庫的數據中心網絡異常檢測算法，搜集鏈路狀態數據庫，采用改進路由算法，得到全網路由形成路由域信息庫數據，對比準確關聯鏈路和路由變化，檢測鏈路異常并定位故障。該算法能夠快速發現拓撲變化，檢測時間較短，但該算法的誤報率較高。文獻[4]提出基于邊緣計算的傳感數據異常實時檢測算法，采用“時間序列”形式表示傳感數據，構建傳感數據異常檢測模型，運用時間序列相關特性，檢測實時傳感數據異常，輸出融合處理檢測結果。該算法的檢測準確性較高，但檢測運行時間較長。

針對上述問題，提出了基于HDFS開源架構的異常數據實時檢測算法，依據基于HDFS數據分布式云存儲體系所獲數據，使用多級哈希表搜索算法，完成異常數據查詢，采用基于支持向量數據描述，實現異常數據實時檢測。該算法具有較高的檢測能力，能夠有效降低誤報率，縮短運行時間。

2 基于HDFS開源架構的異常數據實時檢測算法

2.1 檢測算法框架

基于HDFS開源架構的異常數據實時檢測算法是在Hadoop開源架構上，搭建基于HDFS的數據分布式云存儲體系，實現異常數據實時檢測。檢測算法框架如圖1所示。

圖1 檢測算法框架

基于HDFS的數據分布式云存儲體系，通過布設在各區域的數據采集終端，采集異常檢測相關數據，并將數據存儲于各個二級數據中心的實體存儲節點中，將各二級數據中心的數據匯總后，存儲至數據中心，該數據中心可為數據查詢模塊和異常檢測模塊提供數據支撐[5]。數據查詢模塊采用多級哈希算法完成數據查詢，異常檢測模塊基于支持向量數據描述完成異常數據實時檢測。

2.2 基于多級哈希算法的數據查詢

依據基于HDFS數據分布式云存儲體系所獲數據建立分布式哈希表，并設計多級哈希表搜索算法，完成數據查詢。當請求數據查找時，先檢索第一級哈希索引表，再檢索第二級哈希索引表，進入第二級哈希索引表之前要依據(key，value)內key對應的value值進入，一級哈希表內分化出的數據信息存在二級哈希索引表，循環以上過程直至該數據被找到結束[6]。

使用此算法需在多級索引表內存放全部數據對應信息所需的索引。用O(log(m1+m2+…))表示算法的時間復雜度，第一級索引的信息條數用m1表示，第二級索引的信息條數用m2表示，逐次向下使用此方式對各級索引表的key列進行檢索[7]。因為各表的索引條目在設計的多級索引表算法中數量一致，所以對此時間復雜度進行簡化，用O(logm*n)表示簡化后的時間復雜度，其內索引的級數用n表示，單個索引表內信息條數用m表示。

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

2.3 基于支持向量數據描述的異常數據實時檢測

2.3.1 支持向量數據描述分類器

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

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

(1)

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

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

?iζ≥0

(2)

根據拉格朗日泛函的鞍點給出上述問題最優解，可表示為

(3)

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

(4)

(5)

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

(6)

根據上述公式可得，線性加權組合加權系數ai與數據對象xi可獲得最小超球體的中心。對偶問題的最大化問題可由最小化問題轉化可表示為

(7)

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

(8)

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

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

(9)

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

(10)

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

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

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

經廣泛研究，對于大量不同類型的分類問題，更適合應用較廣的高斯核函數，因為其具有較強的泛化學習能力，所以本文使用高斯核函數。

2.3.2 支持向量數據描述異常檢測分類器優化求解

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

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

(11)

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

用矩陣描述與式(11)對應的對偶問題

(12)

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

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

(13)

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

(14)

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

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

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

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

步驟5：t=t+1，轉到步驟2；

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

對上述算法分析，分析時間和空間復雜度，得知此算法空間復雜度與樣本點數m無關，但時間復雜度與樣本點數m呈線性。通過上述步驟，利用最小閉包球算法，根據樣本數量的增多，使該優化算法的時間、空間復雜度緩慢增長，對于高維大規模數據集求解，優化求解支持向量數據描述異常檢測分類器，實現異常數據實時檢測。

3 實驗分析

為了驗證基于HDFS開源架構的異常數據實時檢測算法的有效性，在Redis網絡數據集(https:∥github.com/microsoftarchive/redis/releases)中選取4000個數據，分別采用文獻[3]算法、文獻[4]算法和所提算法，在MATLAB軟件平臺上進行對比測試，分析不同算法檢測網絡異常數據的通信開銷比值，實驗結果如圖2所示。

圖2 不同算法的通信開銷對比

由圖2實驗結果可知，隨著數據量的增加，不同算法的通信開銷比值隨之增大，當數據量為4000MB時，文獻[3]算法的通信開銷比值為28%，文獻[4]算法的通信開銷比值為22%，而所提算法的通信開銷比值為10%。由此可知，所提算法的通信開銷比值較小，在異常數據檢測時，可有效節省通信開銷。

進一步驗證基于HDFS開源架構的異常數據實時檢測算法的檢測運行時間，在數據量不同時，分析不同算法的檢測運行時間，結果如圖3所示。

圖3 不同算法的檢測運行時間對比

分析圖3可知，隨著數據量的增加，不同算法的檢測運行時間隨之增加。當數據量達到4000MB時，文獻[3]算法的平均檢測運行時間為5.3s，文獻[4]算法的平均檢測運行時間為4.6s，而所提算法的平均檢測運行時間僅為2.5s。由此可知，所提算法的檢測運行時間較短。因為所提算法利用線性關系描述時間復雜度，對于高維大規模數據集求解，根據樣本數量的增多，優化算法時間，從而有效縮短檢測運行時間。

在此基礎上，對比不同算法的異常數據檢測率，對比結果如圖4所示。

圖4 不同算法的異常數據檢測率對比

根據圖4可知，當數據量達到4000MB時，文獻[3]算法的平均異常數據檢測率為89.6%，文獻[4]算法的平均異常數據檢測率為91.2%，而所提算法的平均異常數據檢測率高達98%。由此可知，所提算法的異常數據檢測率較高，具有較高的檢測能力。因為所提算法對于求解高維大規模數據集，采用最小閉包球算法，隨著樣本數量增長，其空間復雜度較為緩慢，從而提高了異常數據檢測率。

為了驗證所提算法的準確性，在數據量不同時，對比不同算法的誤報率，結果如圖5所示。

圖5 不同算法的誤報率對比

由圖5可知，隨著數據規模的增大，不同算法的誤報率逐漸增高，當數據量為4000MB時，文獻[3]算法與文獻[4]算法的最高誤報率為2.8%、2.48%，而所提算法的最高誤報率為0.8%，低于其它兩種算法，且所提算法的誤報率始終保持在1.0%以下，由此可知，所提算法的誤報率較低。因為所提算法設計最小閉包球算法優化求解支持向量數據描述異常檢測分類器，通過最小閉包球解決支持向量機問題，從而降低訓練算法的誤報率。

4 結論

為了提高異常數據實時檢測算法檢測率，降低誤報率高，縮短運行時間，提出基于HDFS開源架構的異常數據實時檢測算法。根據HDFS建立數據分布式云存儲體系，設計多級哈希表搜索算法查詢異常數據，采用支持向量數據描述，結合最小閉包球算法，降低訓練算法的時間和空間復雜度的同時，實現異常數據檢測。該算法可以有效提高檢測率，降低誤報率，縮短運行時間。在未來仍需進一步研究，對于數據的海量增長繼續對算法性能進行改善，盡可能實時檢測更多的異常數據。