面向高維大數據的局部離群點并行檢測算法

何美玲，李佩雅

(1.浙江中醫藥大學信息技術中心，浙江 杭州 310000；2.暨南大學網絡空間安全學院，廣東 廣州 510632)

1 引言

在數據挖掘研究領域中局部離群點檢測算法可以發現高維大數據集中存在的異常數據，是重要的研究方法之一[1]。目前的檢測算法面向高維大數據時，無法準確獲取局部離群點的屬性，花費大量的時間也無法有效的檢測到局部離群點，對數據采集和應用產生嚴重的影響[2]。因此，需要在高維大數據環境下研究局部離群點檢測算法。丁天一[3]等人提出基于相似度剪枝的離群點檢測算法，該算法對數據點之間的相似度進行計算，并利用數據點對應的相似度組成相似度矩陣，構建離群點候選集，對非離群點在檢測之前做剪枝操作，通過LOF算法在離群點候選集中計算數據點的局部離群因子，根據計算結果實現局部離群點的檢測。但該算法沒有對高維大數據進行降維處理，容易受到“維度災難”的影響，導致檢測精度較低。劉芳[4]等人提出基于密度的局部離群點檢測算法，對LOF和融合索引結構進行分析，根據分析結構制定剪枝方案，在數據稀疏區域中根據剪枝方案獲取初始局部離群點，并對剪枝臨界值進行設定，實現局部離群點的檢測，該方法未對高維大數據進行降維，剔除數據中的無用特征，導致整體檢測率較低。毛亞瓊[5]等人提出一種引入局部向量點積密度的高維數據離群點快速檢測算法，首先以保存少量中間結果的方式只對窗口內受影響的數據點進行增量計算，同時設計2種優化策略和1條剪枝規則，減少檢測過程中各點之間距離的計算次數，降低算法的時空開銷，但該方法未對高維大數據進行降維處理，消除無用的數據對象、縮小數據集的容量，導致檢測效率過低，不能被廣泛使用。為解決上述問題，提出面向高維大數據的局部離群點并行檢測算法，首先基于E-PCA算法對高維大數據進行降維處理，然后面向高維大數據從離散點集合和離群點檢測算法并行化兩方面實現局部離群點并行檢測算法設計，最后通過仿真驗證所提算法的有效性。

2 基于E-PCA算法的高維大數據降維處理

數據降維是從高維數據中檢測局部離群點的必要步驟[6]。所提算法采用E-PCA算法實現高維大數據降維處理。

1)特征值與特征向量篩選

設A為對稱矩陣，該矩陣可以在維度空間中描述正交分解操作，反映在不同特征向量中對稱矩陣A對應的投影長度，特征值可以通過投影長度計算得到，獲得特征值為K的分量在投影前對應的值，并丟棄其余分量，降低對稱矩陣的維度，保留有效信息[7]。

2)信息熵

(1)

式(1)中，信號信息熵的單位為bit。設信息熵閾值為δ，通過設定的閾值判斷保留或剔除特征，δ通常情況下可通過以下方法計算得到：

①根據應用分析中特征對應的重要性進行判斷，無用特征信息對應的熵值和有用特征對應的熵值之間的差異較大；

②通過下述公式對原始數據中特征對應的比重進行計算

(2)

根據上述信息熵閾值判斷方法，得到如圖1所示的Arcene數據集中數據點對應的信息熵值構成的曲線圖。

圖1 數據集前50個屬性的信息熵值

3)E-PCA降維算法

面向高維大數據的局部離群點并行檢測算法采用E-PAC算法消除高維大數據中存在的冗余數據，基于信息熵的高維數據降維處理具體流程如圖2所示[8]。

圖2 基于信息熵的高維數據降維處理流程

根據圖2所示的基于信息熵的高維數據降維處理流程，首先用描述數據矩陣，其中，m代表的是樣本數量；n代表的是特征數量；f代表的是貢獻率；Yk*m代表的是降維后的數據，則得到E-PCA算法的具體步驟如下所示：

步驟一：計算每個屬性對應的信息熵值，并將計算結果與設定的閾值δ進行對比，消除冗余特征，對U進行以下計算：為了使i=1，計算屬性ai對應的信息熵H(ai)，如果H(ai)>δ，在集合A中存儲屬性ai；

步驟二：樣本矩陣中心化，得到矩陣Xn*m，其中，X的關系表達式如式(3)所示

X=A-repmat[mean(A，2)，1，m]

(3)

步驟三：對屬性不同維度之間存在的協方差進行計算，根據計算結果組成協方差矩陣cov，其關系表達式如式(4)所示

cov=XXT/[size(x，2)-1]

(4)

步驟四：計算cov 的特征值與特征向量；

步驟五：通過上述過程計算得到的特征值和特征向量構建特征向量矩陣Vn*k；

步驟六：通過下述式(5)實現降維

Y=VTX

(5)

步驟七：算法結束，在特征值貢獻率f的基礎上確定參數k

(6)

3 面向高維大數據的局部離群點并行檢測算法

3.1 離群點集合

當高維數據進行降維處理后，消除了高維數據中存在的無用數據，并減少了高維數據集的容量，為了提高局部離群點的并行檢測效率，在計算可達距離時，需要改進傳統的LOF算法，具體過程如下：設D′代表的是高維數據集；E代表的是離群點構成的集合；ξ代表的是離群因子對應的閾值。

步驟一：對任意對象y(y∈D′)的k-y距離k(y)進行計算，根據計算結果獲取y的距離鄰域Nk(y)；

步驟二：計算y與s(s∈D且s≠y)之間存在的可達距離；

步驟三：當對象s和對象y都不屬于中心點時，利用式(7)對可達距離reachdist(s，y)進行計算：

reachdist(s，y)=max{k(y)，dist(s，y)}

(7)

步驟四：如果對象s、y都是簇Cl和Cm的中心點，此時可達距離如式(8)所示

(8)

步驟五：如果對象s、y只有一個是簇Cl的中心點，可達距離的計算如式(9)所示

(9)

此時y的局部可達密度如式(10)所示

(10)

步驟六：根據步驟二～步驟五利用對應的公式對不同對象對應的局部可達密度進行計算；

步驟七：通過式(1)獲得對象對應的局部離群因子

(11)

步驟八：當ξ

3.2 離群點檢測算法并行化

面向高維大數據的局部離群點并行檢測算法將Hbase作為數據源，在Hadoop平臺中完成局部離群點的并行檢測，具體過程如下：

步驟一：采用DSP算法均勻劃分輸入的原始數據集D，獲得若干個數據塊，在DataNobe節點中存入獲取的數據塊[10]；

步驟二：利用獲取的數據塊建立鍵值對〈K，V〉，其中K代表的是行號，V代表的是字符串中存在的內容。在Reduce階段中對數據進行過濾處理，獲得屬性值，輸出〈id，property〉，其中，id值代表的是能夠反映數據對象xi的一種標識，property描述的是xi對應的屬性值，表達式如式(12)所示

{xi1，xi2，…，xin}

(12)

步驟三：輸入〈id，property〉，在Map階段不做處理，在Reduce階段根據式(13)計算所有對象xi與其它對象的距離dist(xi，xj)，輸出鍵值對〈id，dist〉，dist中表示xi的與其它對象的距離dist(xi，xj)值，并存入輸出文件中

(13)

步驟四：輸入步驟三產生的鍵值對〈id，dist〉，在Map階段不做處理，在Reduce階段計算出xi的距離領域，輸出鍵值為〈id，neighbor〉，其中neighbor表示每個數據對象xi的距離鄰域N∈(xi)；

步驟五：輸入步驟四產生〈id，neighbor〉，Map階段根據式(14)確定核心對象集O，在Reduce階段確定簇劃分C={C1，C2，…，CK}，輸出〈c，object〉，其中，c代表的是簇類號；簇中對象為object，得到核心對象集O如式(14)所示

O=O∪{xj}

(14)

步驟六：輸入步驟五產生的鍵值對〈c，object〉，Map階段融合步驟二產生的鍵值對，并根據式(15)分別計算各簇Cl的平均距離avg(Cl)、最大距離diam(Cl)

(15)

在Reduce階段根據式(16)找出各簇的中心點μ={μ1，μ2，…，μk}

(16)

初步確定離群數據集D′=D/C∪μ，輸出〈D′id，Ccore〉。其中，Ccore代表的是集群點最大距離；D′id代表的是數據對象；

步驟七：輸入上述過程計算得到的鍵值對〈D′id，Ccore〉，并在Map階段中對〈id，dist〉進行融合處理，根據3.1節的步驟一獲取的各對象對應的距離鄰域，在Reduce階段根據3.1節的步驟二～步驟五計算其對應的可達距離，輸出〈D′id，reach〉；

步驟八：輸入步驟七產生的鍵值對〈D′id，reach〉，在Map階段根據3.1節的步驟六計算離群對象的局部可達密度，在Reduce階段根據3.1節的步驟七計算各個對象的局部離群因子，輸出鍵值對〈D′id，lof〉，其中，lof代表的是數據對象的局部離群因子；

步驟九：輸入步驟八產生的鍵值對〈D′id，lof〉，在Map階段不做處理，再在Reduce階段根據3.1節步驟八找出離群對象，輸出鍵值對〈Outlierid，Outlierlof〉，其中，Outlierid代表的是離群對象的id；Outlierlof代表的是離群對象的離群因子。

綜上所述可知，當前的局部離群點檢測算法受到“維度災難”的影響，在處理大規模數據上存在很多不足，因此，所提方法首先對高維數據進行降維處理，然后將傳統的離群點檢測算法(LOF)和Hadoop分布式平臺下的Mapreduce分布式框架結合，得到初始離群數據集，再對傳統的LOF算法進行相應的改進，計算局部離群因子，找出高維數據中的離群點集合并判斷其準確位置，實現局部離群點并行化檢測。

4 實驗分析

為了驗證面向高維大數據的局部離群點并行檢測算法的整體有效性，需要對面向高維大數據的局部離群點并行檢測算法進行仿真測試。分別采用所提算法、文獻[4]基于密度的Top-n局部異常點快速檢測算法和文獻[5]引入局部向量點積密度的數據流離群點快速檢測算法進行檢測k值、局部可達密度和檢測時長對比測試。

4.1 k值測試結果

k值的選擇會引起局部離群因子LOFk(y)值的波動，k值太小雖能減少計算量，但會降低檢測準確率，k值太大，計算開銷會急劇增大，因此將k值作為測試指標對所提算法、文獻[4]算法和文獻[5]算法進行測試，結果如圖3所示。

圖3 不同算法的k值對比結果

由圖3不同算法的k值對比結果可知，文獻[4]算法的k值在0.8以上，相對較高，計算開銷急劇增大；文獻[5]算法的k值低于0.2，相對較低，計算開銷較??；所提算法的k值穩定在0.6附近，表明該算法能夠有效并行檢測高維大數據中的局部離群點。原因是所提算法在對局部離群點并行檢測前，采用E-PCA算法對高維大數據進行了降維處理，避免受到“維度災難”的影響，出現離群點被冗余維度屬性所掩蓋的現象，進而穩定了k值。

4.2 局部可達密度

將局部可達密度作為測試指標對所提算法、文獻[4]算法和文獻[5]算法進行測試，結果如圖4所示。

圖4 不同算法局部可達密度對比結果

圖4中剪枝率代表的是離群點所占百分比。分析圖4的不同算法局部可達密度對比結果可知，隨著剪枝率的增大，局部可達密度呈下降趨勢，但是所提算法的局部可達密度依舊是三種算法中最高的在80以上，因為該算法利用了對局部離群點進行檢測之前，提取了高維大數據的特征，并進行了特征篩選，保留了有效特征，完成了高維數據的降維處理，降低了檢測的數據量，因此，該算法的局部可達密度也明顯高于其它方法。

4.3 數據尺度

取k值為0.6，特征維度為5，分別測試所提算法、文獻[4]算法和文獻[5]算法在不同數據尺度下的檢測時長，結果如表1所示。

表1 不同算法檢測時長對比結果(ms)

由表1不同算法檢測時長對比結果可知，隨著數據尺度的增加，局部離群點檢測時長增長。對表2的數據分析可知，與文獻[4]算法和文獻[5]算法相比，所提算法的檢測時長最快，最短為6.57ms。因為該算法在實現局部離群點并行檢測之前，結合了E-PCA算法對高維大數據進行了降維處理，剔除了無用的數據對象，縮小了數據集的容量，降低了數據尺度對檢測時間的影響。

5 結束語

隨著大數據時代的到來，局部離群檢測算法已經逐漸成為行業學者們的研究熱點，為了使數據在應用時能夠不受“維度災難”的影響，發現數據集中的異常行為對象，對高維大數據的局部離群點并行檢測算法進行了研究。

1)當前算法實現并行檢測時存在k值不穩定、局部可達密度低、檢測時間長的問題，因此提出面向高維大數據的局部離群點并行檢測算法，結合了E-PCA算法對高維大數據進行了降維處理，剔除無用的數據對象，并通過LOF和Maperduce分布式框架完成局部離群點并行化檢測。

2)仿真結果表明，所提方法k值穩定在0.6附近，局部可達密度在80以上，檢測時長最短為6.57ms，有效解決當前方法中存在的問題。