面向高維大數(shù)據(jù)的局部離群點(diǎn)并行檢測算法

何美玲，李佩雅

(1.浙江中醫(yī)藥大學(xué)信息技術(shù)中心，浙江 杭州 310000；2.暨南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，廣東 廣州 510632)

1 引言

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

2 基于E-PCA算法的高維大數(shù)據(jù)降維處理

數(shù)據(jù)降維是從高維數(shù)據(jù)中檢測局部離群點(diǎn)的必要步驟[6]。所提算法采用E-PCA算法實(shí)現(xiàn)高維大數(shù)據(jù)降維處理。

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

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

2)信息熵

(1)

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

①根據(jù)應(yīng)用分析中特征對(duì)應(yīng)的重要性進(jìn)行判斷，無用特征信息對(duì)應(yīng)的熵值和有用特征對(duì)應(yīng)的熵值之間的差異較大；

②通過下述公式對(duì)原始數(shù)據(jù)中特征對(duì)應(yīng)的比重進(jìn)行計(jì)算

(2)

根據(jù)上述信息熵閾值判斷方法，得到如圖1所示的Arcene數(shù)據(jù)集中數(shù)據(jù)點(diǎn)對(duì)應(yīng)的信息熵值構(gòu)成的曲線圖。

圖1 數(shù)據(jù)集前50個(gè)屬性的信息熵值

3)E-PCA降維算法

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

圖2 基于信息熵的高維數(shù)據(jù)降維處理流程

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

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

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

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

(3)

步驟三：對(duì)屬性不同維度之間存在的協(xié)方差進(jìn)行計(jì)算，根據(jù)計(jì)算結(jié)果組成協(xié)方差矩陣cov，其關(guān)系表達(dá)式如式(4)所示

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

(4)

步驟四：計(jì)算cov 的特征值與特征向量；

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

步驟六：通過下述式(5)實(shí)現(xiàn)降維

Y=VTX

(5)

步驟七：算法結(jié)束，在特征值貢獻(xiàn)率f的基礎(chǔ)上確定參數(shù)k

(6)

3 面向高維大數(shù)據(jù)的局部離群點(diǎn)并行檢測算法

3.1 離群點(diǎn)集合

當(dāng)高維數(shù)據(jù)進(jìn)行降維處理后，消除了高維數(shù)據(jù)中存在的無用數(shù)據(jù)，并減少了高維數(shù)據(jù)集的容量，為了提高局部離群點(diǎn)的并行檢測效率，在計(jì)算可達(dá)距離時(shí)，需要改進(jìn)傳統(tǒng)的LOF算法，具體過程如下：設(shè)D′代表的是高維數(shù)據(jù)集；E代表的是離群點(diǎn)構(gòu)成的集合；ξ代表的是離群因子對(duì)應(yīng)的閾值。

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

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

步驟三：當(dāng)對(duì)象s和對(duì)象y都不屬于中心點(diǎn)時(shí)，利用式(7)對(duì)可達(dá)距離reachdist(s，y)進(jìn)行計(jì)算：

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

(7)

步驟四：如果對(duì)象s、y都是簇Cl和Cm的中心點(diǎn)，此時(shí)可達(dá)距離如式(8)所示

(8)

步驟五：如果對(duì)象s、y只有一個(gè)是簇Cl的中心點(diǎn)，可達(dá)距離的計(jì)算如式(9)所示

(9)

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

(10)

步驟六：根據(jù)步驟二～步驟五利用對(duì)應(yīng)的公式對(duì)不同對(duì)象對(duì)應(yīng)的局部可達(dá)密度進(jìn)行計(jì)算；

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

(11)

步驟八：當(dāng)ξ

3.2 離群點(diǎn)檢測算法并行化

面向高維大數(shù)據(jù)的局部離群點(diǎn)并行檢測算法將Hbase作為數(shù)據(jù)源，在Hadoop平臺(tái)中完成局部離群點(diǎn)的并行檢測，具體過程如下：

步驟一：采用DSP算法均勻劃分輸入的原始數(shù)據(jù)集D，獲得若干個(gè)數(shù)據(jù)塊，在DataNobe節(jié)點(diǎn)中存入獲取的數(shù)據(jù)塊[10]；

步驟二：利用獲取的數(shù)據(jù)塊建立鍵值對(duì)〈K，V〉，其中K代表的是行號(hào)，V代表的是字符串中存在的內(nèi)容。在Reduce階段中對(duì)數(shù)據(jù)進(jìn)行過濾處理，獲得屬性值，輸出〈id，property〉，其中，id值代表的是能夠反映數(shù)據(jù)對(duì)象xi的一種標(biāo)識(shí)，property描述的是xi對(duì)應(yīng)的屬性值，表達(dá)式如式(12)所示

{xi1，xi2，…，xin}

(12)

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

(13)

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

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

O=O∪{xj}

(14)

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

(15)

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

(16)

初步確定離群數(shù)據(jù)集D′=D/C∪μ，輸出〈D′id，Ccore〉。其中，Ccore代表的是集群點(diǎn)最大距離；D′id代表的是數(shù)據(jù)對(duì)象；

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

步驟八：輸入步驟七產(chǎn)生的鍵值對(duì)〈D′id，reach〉，在Map階段根據(jù)3.1節(jié)的步驟六計(jì)算離群對(duì)象的局部可達(dá)密度，在Reduce階段根據(jù)3.1節(jié)的步驟七計(jì)算各個(gè)對(duì)象的局部離群因子，輸出鍵值對(duì)〈D′id，lof〉，其中，lof代表的是數(shù)據(jù)對(duì)象的局部離群因子；

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

綜上所述可知，當(dāng)前的局部離群點(diǎn)檢測算法受到“維度災(zāi)難”的影響，在處理大規(guī)模數(shù)據(jù)上存在很多不足，因此，所提方法首先對(duì)高維數(shù)據(jù)進(jìn)行降維處理，然后將傳統(tǒng)的離群點(diǎn)檢測算法(LOF)和Hadoop分布式平臺(tái)下的Mapreduce分布式框架結(jié)合，得到初始離群數(shù)據(jù)集，再對(duì)傳統(tǒng)的LOF算法進(jìn)行相應(yīng)的改進(jìn)，計(jì)算局部離群因子，找出高維數(shù)據(jù)中的離群點(diǎn)集合并判斷其準(zhǔn)確位置，實(shí)現(xiàn)局部離群點(diǎn)并行化檢測。

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

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

4.1 k值測試結(jié)果

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

圖3 不同算法的k值對(duì)比結(jié)果

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

4.2 局部可達(dá)密度

將局部可達(dá)密度作為測試指標(biāo)對(duì)所提算法、文獻(xiàn)[4]算法和文獻(xiàn)[5]算法進(jìn)行測試，結(jié)果如圖4所示。

圖4 不同算法局部可達(dá)密度對(duì)比結(jié)果

圖4中剪枝率代表的是離群點(diǎn)所占百分比。分析圖4的不同算法局部可達(dá)密度對(duì)比結(jié)果可知，隨著剪枝率的增大，局部可達(dá)密度呈下降趨勢，但是所提算法的局部可達(dá)密度依舊是三種算法中最高的在80以上，因?yàn)樵撍惴ɡ昧藢?duì)局部離群點(diǎn)進(jìn)行檢測之前，提取了高維大數(shù)據(jù)的特征，并進(jìn)行了特征篩選，保留了有效特征，完成了高維數(shù)據(jù)的降維處理，降低了檢測的數(shù)據(jù)量，因此，該算法的局部可達(dá)密度也明顯高于其它方法。

4.3 數(shù)據(jù)尺度

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

表1 不同算法檢測時(shí)長對(duì)比結(jié)果(ms)

由表1不同算法檢測時(shí)長對(duì)比結(jié)果可知，隨著數(shù)據(jù)尺度的增加，局部離群點(diǎn)檢測時(shí)長增長。對(duì)表2的數(shù)據(jù)分析可知，與文獻(xiàn)[4]算法和文獻(xiàn)[5]算法相比，所提算法的檢測時(shí)長最快，最短為6.57ms。因?yàn)樵撍惴ㄔ趯?shí)現(xiàn)局部離群點(diǎn)并行檢測之前，結(jié)合了E-PCA算法對(duì)高維大數(shù)據(jù)進(jìn)行了降維處理，剔除了無用的數(shù)據(jù)對(duì)象，縮小了數(shù)據(jù)集的容量，降低了數(shù)據(jù)尺度對(duì)檢測時(shí)間的影響。

5 結(jié)束語

隨著大數(shù)據(jù)時(shí)代的到來，局部離群檢測算法已經(jīng)逐漸成為行業(yè)學(xué)者們的研究熱點(diǎn)，為了使數(shù)據(jù)在應(yīng)用時(shí)能夠不受“維度災(zāi)難”的影響，發(fā)現(xiàn)數(shù)據(jù)集中的異常行為對(duì)象，對(duì)高維大數(shù)據(jù)的局部離群點(diǎn)并行檢測算法進(jìn)行了研究。

1)當(dāng)前算法實(shí)現(xiàn)并行檢測時(shí)存在k值不穩(wěn)定、局部可達(dá)密度低、檢測時(shí)間長的問題，因此提出面向高維大數(shù)據(jù)的局部離群點(diǎn)并行檢測算法，結(jié)合了E-PCA算法對(duì)高維大數(shù)據(jù)進(jìn)行了降維處理，剔除無用的數(shù)據(jù)對(duì)象，并通過LOF和Maperduce分布式框架完成局部離群點(diǎn)并行化檢測。

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