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

李永政，郝新兵

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

0 引言

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

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

1 研究基礎(chǔ)

1.1 INFLO算法

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

1.1.1 對象p的第k距離

對于任意一個正整數(shù)k，對象p的第k距離記作k-dis(p)，在數(shù)據(jù)集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距離，那么數(shù)據(jù)集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近鄰，可以很好地表征數(shù)據(jù)對象所在區(qū)域的密度特征。

1.2 距離加權(quán)策略

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

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

(8)

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

1.2.1 離群屬性

對于p∈D,Ai∈A,若滿足以下關(guān)系：

則稱屬性Ai為離群屬性。

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

1.2.2 加權(quán)距離

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

(9)

其中：

(10)

離群屬性對于數(shù)據(jù)對象之間距離計算有較大的貢獻(xiàn)，因此給離群屬性較大的權(quán)重。

1.3 Hadoop與MapReduce核心技術(shù)

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

1.3.1 HDFS

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

1.3.2 MapReduce

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

圖1 MapReduce計算模型

2 MR-DINFLO算法

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

輸入：m維數(shù)據(jù)集D；參數(shù)k；異常點個數(shù)n。

輸出：前n個異常點及所對應(yīng)的離群因子。

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

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

FirstMapper

輸入：數(shù)據(jù)集D

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

FirstReducer

輸入：〈di_valuei,1〉

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

SecondMapper

輸入：〈di_valuei,countvaluei〉

輸出：〈di,valuei_countvaluei〉

SecondReducer

輸入：〈di,valuei_countvaluei〉

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

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

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

輸入：階段1中Reduce的輸出

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

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

Mapper

輸入：數(shù)據(jù)集D

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

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

Reducer

不做任何處理

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

Mapper

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

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

輸出：〈p,INFLOk(p)〉

Reducer

不做任何處理

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

Mapper

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

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

Reducer

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

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

3 實驗與分析

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

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

3.1 算法準(zhǔn)確度的比較

采用如下度量對算法準(zhǔn)確度進(jìn)行評價：

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

表1 各算法在不同規(guī)模數(shù)據(jù)集上的準(zhǔn)確度

圖2 算法準(zhǔn)確度對比

3.2 算法時間效率的比較

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

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

圖3 算法時間效率對比

4 結(jié)論

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