基于Hadoop的局部異常檢測算法*

李永政，郝新兵

(1.華北計算機系統工程研究所，北京 100083; 2.中國信息安全研究院有限公司，北京 100000)

0 引言

異常檢測作為數據挖掘領域里的一個重要研究方向，是從大量數據中檢測出少量與多數數據產生機制不同的數據點[1]。異常檢測技術可以應用于很多領域，如網絡入侵檢測、電信和信用卡欺詐、氣象預報等[2]。異常檢測方法有基于統計學的方法、基于深度的方法、基于距離的方法、基于聚類的方法、基于密度的方法。基于統計的方法[3]是假設數據符合某種統計規律，將那些嚴重偏離數據分布曲線的數據點定義為異常點，但這種方法需先得知數據分布規律并且只適用于只有一個維度屬性的數據，事實上這兩種條件都難以滿足。基于深度的方法是為每一個對象分配一個深度值，根據不同的深度值，將數據對象映射到二維空間相應的層上，處在淺層的數據對象更可能是異常點[4]。但是這種方法對高維數據的檢測效率較低。基于距離的方法最早由KNORR E M等人[5]提出，其將與絕大部分數據點的距離都大于某一個閾值的數據點定義為異常點。RAMASWAMY S等人[6]在此基礎上提出了K最近鄰異常點檢測方法，該方法首先計算每個數據對象的第k鄰居距離，然后將所有數據對象第k鄰居距離排序，距離最大的top(n)的數據對象作為異常點。但這種方法對于參數的選擇十分敏感，并且時間復雜度偏高。基于聚類的方法[7]是在聚類的基礎上，將距離所屬簇中心比較遠的點以及數據規模較小、分布比較稀疏的簇歸為異常點，但這種方法高度依賴所選擇的聚類算法。基于密度的方法，將密度明顯小于其鄰域密度的數據點定義為異常點，最具代表性的就是由BREUNIG M M等人[8]于2000年提出的Local Outlier Factor(LOF)離群因子異常檢測算法。該算法通過計算數據集中每個數據點的離群因子的值來判斷該點是否為異常點。在LOF算法基礎上，眾多學者提出了改進算法。Jin Wen等人[9]在LOF算法基礎上提出了INFLuenced Outlierness(INFLO)算法，該算法基于對稱鄰居關系，引入了新的離群因子計算方法，在計算數據點的離群程度時，同時考慮近鄰與逆向近鄰。當不同密度數據區域離得很近時，可以防止邊緣點被誤判[10]。Tang Jian等人[11]提出了Connectivity-based Outlier Factor(COF)算法，它采用鏈距離的方法解決了異常點的密度與正常點的密度相差不大，屬于模式偏離的情況。雖然以上方法提高了LOF算法檢測準確度，但當數據規模較大、數據復雜度較高時，檢測效率較低。

為了提高局部異常檢測算法的檢測效率和檢測準確度，本文提出一種基于Hadoop的分布式局部異常檢測算法MR-DINFLO。該方法在INFLO算法的基礎上，引入信息熵來確定數據的離群屬性，在計算各個數據對象之間距離時采用加權距離，給離群屬性以較大的權重，提高了檢測準確度。該算法還通過引入Hadoop的MapReduce計算模型，實現了檢測算法的并行化，提高了檢測效率。

1 研究基礎

1.1 INFLO算法

INFLO算法是在LOF算法的基礎上提出的，該算法重新定義了離群因子的計算方法，避免了不同密度區域的點離得很近時，邊緣點有可能被誤判的情況[12]。相關定義如下。

1.1.1 對象p的第k距離

對于任意一個正整數k，對象p的第k距離記作k-dis(p)，在數據集D中存在一個對象o，該對象與對象p之間的距離記作d(p,o)。

(1)

滿足以下條件，則取k-dis(p)等于d(p,o)：

(1)至少存在k個對象o′∈D滿足d(p,o′)≤d(p,o)；

(2)至多存在k-1個對象o′∈D滿足d(p,o′)

1.1.2 對象p的k距離鄰域

已知對象p的第k距離，那么數據集D中到對象p的距離不大于p的第k距離的對象的集合定義為p的k距離鄰域。即:

Nk(p)={q∈D{p}|d(p,q)≤k-dis(p)}

(2)

1.1.3 對象p的反向k近鄰

p的反向k近鄰定義如下：

RNNk(p)={q|q∈D,p∈NNk(q)}

(3)

其中，NNk(p)與Nk(p)一樣，都表示對象p的k距離鄰域。

1.1.4 對象p的局部密度

對象p的局部密度表示如下：

(4)

1.1.5 對象p的局部離群因子

對象p的局部離群因子定義如下：

(5)

其中：

(6)

ISk(p)=NNk(p)∪ RNNk(p)

(7)

相比較LOF算法，INFLO既考慮了k近鄰，又考慮了反向k近鄰，可以很好地表征數據對象所在區域的密度特征。

1.2 距離加權策略

為了提高檢測準確度，在計算兩個數據對象之間距離時，胡采平等[13]采用加權距離,通過計算屬性信息熵來確定屬性的權重。

熵是信息論中用來描述信息和隨機變量不確定性的重要工具，設X為隨機變量，其取值集合為S(X)，P(x)表示X可能取值的概率，則X的熵定義為：

(8)

數據的混亂程度是由數據在各個屬性上的混亂程度決定的，屬性的信息熵反映了數據在各個屬性上分布的混亂程度，屬性的信息熵越大，數據在該屬性上分布越不規律，進而可能導致整個數據分布越不規律。假設d維數據集D的屬性集為A={A1,A2,…,Ad}，D中數據對象p在屬性Ai上的值記為fAi(p)。

1.2.1 離群屬性

對于p∈D,Ai∈A,若滿足以下關系：

則稱屬性Ai為離群屬性。

如果屬性Ai的信息熵不小于其他屬性信息熵的平均值，說明屬性Ai的不確定性較大。因此稱屬性Ai為離群屬性。

1.2.2 加權距離

設p,q∈D,其中fAi(p)和fAi(q)是第i(i=1,2,…,d)維屬性的值，wi是第i維的權重，數據對象p和q的加權距離為:

(9)

其中：

(10)

離群屬性對于數據對象之間距離計算有較大的貢獻，因此給離群屬性較大的權重。

1.3 Hadoop與MapReduce核心技術

Hadoop是由Apache基金會開源的一個分布式系統架構，它主要由分布式文件系統Hadoop Distributed File System(HDFS)和MapReduce分布式計算框架兩大核心內容組成[14]。

1.3.1 HDFS

HDFS是Hadoop的分布式文件系統，為Hadoop的分布式系統提供海量數據存儲支持。HDFS可以部署在商用硬件的集群上，并且具有容錯機制。HDFS采用Master/Slave的體系架構，集群由Namenode和多個Datanode組成[15]。Namenode是管理節點，負責管理文件系統的元數據。Datanode是文件系統的工作節點，負責存儲或檢索實際的數據。

1.3.2 MapReduce

MapReduce是Hadoop的分布式計算框架，它可分為兩個主要階段，即Map階段和Reduce階段。輸入數據被分割到多個數據塊中，每個數據塊內每行數據都要執行Map函數，Map階段輸入key/value對，key為文件中行偏移量，value為這行數據內容。用戶自定義Map函數，輸出中間key/value對，Reduce階段合并所有具有相同key值的鍵值對，根據用戶自定義Reduce函數，計算最終結果[16]。MapReduce模型計算方法如圖1所示。

圖1 MapReduce計算模型

2 MR-DINFLO算法

為了提高局部異常檢測算法的檢測效率和檢測準確度，本文提出基于Hadoop的局部異常檢測算法MR-DINFLO。該算法在INFLO算法的基礎上，利用MapReduce框架實現了算法的并行化，提高了檢測效率。同時，該算法在計算各數據點之間距離時采用加權距離，給離群屬性以較大的權重，提高了檢測準確度。MR-DINFLO算法的輸入和輸出描述如下：

輸入：m維數據集D；參數k；異常點個數n。

輸出：前n個異常點及所對應的離群因子。

該算法主要分為四個階段。每個階段都是按照MapReduce計算流程來進行。除了第一個階段，每個階段Map的輸入來源于上一階段Reduce的輸出。Reduce的輸出寫入到HDFS中。

(1)第一階段。此階段包含兩個相互依賴的MapReduce程序。輸入是數據集D，輸出是各個屬性的信息熵。方法如下：

FirstMapper

輸入：數據集D

輸出：〈di_valuei,1〉，其中di表示數據的第i個屬性，i=1,2,…,m；valuei是數據對象在第i個屬性的取值;“1”表示數據對象在第i個屬性取值為valuei的個數為1;di_valuei表示將di與valuei作為一個整體輸出。下劃線連接表示將下劃線兩邊內容作為一個整體輸出，以下同理。

FirstReducer

輸入：〈di_valuei,1〉

輸出：〈di_valuei,countvaluei〉，其中countvaluei表示數據對象在第i個屬性取valuei的總個數。

SecondMapper

輸入：〈di_valuei,countvaluei〉

輸出：〈di,valuei_countvaluei〉

SecondReducer

輸入：〈di,valuei_countvaluei〉

根據式(8)計算第i個屬性的信息熵。

輸出：〈di,E(i)〉，其中E(i)表示第i個屬性的信息熵。

(2)第二階段。輸入是數據集D和第一階段的輸出，輸出是數據集D中數據對象的局部密度和k近鄰。方法描述如下：

輸入：階段1中Reduce的輸出

根據式(10)確定各個屬性的權重，為下面計算數據對象之間加權距離做準備。

輸出：〈di,wi〉，i=1,2,…,m

Mapper

輸入：數據集D

根據式(9)計算一個數據對象p與其他所有數據對象之間的加權距離d(p,q)，接著根據式(2)計算數據對象p的k-dis(p)和Nk(p)。根據式(4)計算對象p的局部密度den(p)。

輸出：〈p_den(p),Nk(p)〉

Reducer

不做任何處理

(3)第三階段。輸入是第二階段Mapper的輸出，輸出是各個數據對象的離群因子。方法如下：

Mapper

輸入：階段2中Mapper輸出結果[p_den(p),Nk(p)]

根據式(3)和式(7)先計算出數據對象p的k近鄰和反向k近鄰的并集ISk(p)，然后根據式(6)計算出數據對象p的ISk(p)內所有對象平均局部密度denavg(ISk(p))，最后根據式(5)計算出離群因子INFLOk(p)。

輸出：〈p,INFLOk(p)〉

Reducer

不做任何處理

(4)第四階段。輸入是第三階段Mapper的輸出，輸出是前n個離群數據對象及所對應的離群因子。方法如下：

Mapper

輸入：階段3中Mapper輸出的結果〈p,INFLOk(p)〉

輸出：〈str,Topn-INFLOk(D′)〉，其中str為任意字符串，D′表示在Map中的數據集，Topn-INFLOk(D′)表示Map中前n個最大離群因子所對應的數據對象的集合。

Reducer

輸入：〈str,Topn-INFLOk(D′)〉

輸出：〈p,INFLOk(p)〉，對象p表示整體數據集D的前n個異常數據對象之一。

3 實驗與分析

實驗平臺配置：本文采用3節點的Hadoop集群，每個節點配置為CentOS-7系統，JDK1.8版本，Hadoop為2.7.6版本。其中一個節點為Master節點，即Namenode，另外兩個為Slave節點，即Datanode。

實驗數據集：對數據進行預處理，首先，調整攻擊(離群點)占比，保證攻擊(離群點)占數據集的2%；然后，對非數值型屬性進行數值化處理。

3.1 算法準確度的比較

采用如下度量對算法準確度進行評價：

本文從KDD-CUP 99數據集中選取5種不同規模的子集，首先進行預處理操作，然后進行數據標準化處理，以排除數據屬性不同量綱帶來的影響。各算法在不同規模數據集上檢測的準確度大小如表1所示。從表1數據可以看出，本文提出的MR-DINFLO算法的準確度從數據集為100萬時的0.86增長到500萬時的0.94。這也說明了隨著數據量的逐漸增大，算法越趨穩定。算法準確度評價結果如圖2所示，從圖2可以看出，在處理相同規模的數據時，本文提出的MR-DINFLO算法的準確度比MR-DINFLO(無信息熵)高，因此可以看出引入信息熵提高了檢測準確度。同時可以看出INFLO算法準確度比LOF算法高。

表1 各算法在不同規模數據集上的準確度

圖2 算法準確度對比

3.2 算法時間效率的比較

時間效率一般由算法運行時間來衡量，指的是從程序啟動到得到實驗輸出結果的時間。本文提出的MR-DINFLO算法運行在3節點Hadoop集群上，INFLO算法以及LOF算法運行在單機上。它們的輸入都是相同規模的數據集。各算法在不同規模數據集上的運行時間如表2所示。算法時間效率評價結果如圖3所示，從圖3可以看出，在數據量較少時，MR-DINFLO算法的運行效率與LOF算法和INFLO算法相當，這是因為一個MapReduce程序開始執行時，各個節點啟動、任務初始化會消耗一部分時間。然而隨著數據量的增大，MR-DINFLO算法的運行效率遠高于LOF算法和INFLO算法。當數據集大小為300萬條時，MR-DINFLO算法的運行時間為1 538 s，LOF算法運行時間為3 013 s，INFLO算法運行時間為3 562 s。

表2 各算法在不同規模數據集上的運行時間 (s)

圖3 算法時間效率對比

4 結論

異常檢測是數據挖掘中非常重要的領域之一，具有很高的研究價值。為了提高局部異常檢測算法的檢測效率和檢測準確度，本文提出基于Hadoop的局部異常檢測算法MR-DINFLO。該算法在INFLO算法的基礎上，利用MapReduce框架實現了算法的并行化，提高了檢測效率。另外，該算法在計算各數據點之間距離時采用加權距離，給離群屬性以較大的權重，提高了檢測準確度。在真實數據下驗證了MR-DINFLO算法具有高效可行性。