基于離群點檢測的不確定數(shù)據(jù)流聚類算法研究

葉福蘭

(福州外語外貿(mào)學(xué)院,福建 福州 350202)

0 引 言

伴隨信息技術(shù)快速發(fā)展，數(shù)據(jù)流模型的應(yīng)用逐漸深入各個應(yīng)用領(lǐng)域。這些領(lǐng)域要求數(shù)據(jù)傳輸速度快，且傳輸規(guī)模大[1]。但由于各種外界環(huán)境因素干擾，數(shù)據(jù)流出現(xiàn)不確定性，不確定數(shù)據(jù)流的挖掘和研究逐漸成為相關(guān)專業(yè)人員關(guān)注的重點問題。相關(guān)研究表明[2]，基于離群點檢測的不確定數(shù)據(jù)流聚類可檢測網(wǎng)絡(luò)惡意攻擊行為，能夠挖掘網(wǎng)絡(luò)中被忽視的異常數(shù)據(jù)，為維護網(wǎng)絡(luò)安全起到十分重要的作用。。

一些現(xiàn)有的研究成果，如文獻[3]基于距離準(zhǔn)則進行數(shù)據(jù)間離群點判斷，提出了離群點檢測DOKM算法。根據(jù)數(shù)據(jù)流概念漂移檢測結(jié)果來自適應(yīng)地調(diào)整滑動窗口大小，從而實現(xiàn)對數(shù)據(jù)流的離群點檢測，結(jié)果表明，DOKM算法在人工數(shù)據(jù)集和真實數(shù)據(jù)集中均可以實現(xiàn)對離群點的有效檢測。文獻[4]提出了障礙空間中基于密度的不確定聚類算法。利用三角模糊數(shù)和R樹的性質(zhì)提出TF-Initialseeds算法來解決數(shù)據(jù)的不確定性問題，在基于密度聚類方法的基礎(chǔ)上，利用Voronoi圖剪枝策略可以有效減少計算量的特性。文獻[5]提出了改進的DBSCAN聚類和LAOF兩階段混合數(shù)據(jù)離群點檢測方法。針對DBSCAN算法中參數(shù)ε和Minpts需要人為確定而導(dǎo)致聚類質(zhì)量差的缺點，給出了通過輸入K近鄰的個數(shù)代替Minpts，并通過K近鄰確定聚類半徑，從而減少參數(shù)輸入提高聚類質(zhì)量。通過改進的DBSCAN聚類算法對混合數(shù)據(jù)進行初步篩選，然后利用新構(gòu)造的LAOF基于區(qū)域密度的局部異常因子計算篩選后數(shù)據(jù)對象的局部異常程度。結(jié)果顯示該算法能夠提高離群點檢測的精度。

上述算法存在檢測性能差以及聚類質(zhì)量低的問題，因此，本文提出基于離群點檢測的不確定數(shù)據(jù)流聚類算法，獲取的全局離群點與局部離群點兩種不確定數(shù)據(jù)流，采用一種不確定數(shù)據(jù)流子空間聚類算法完成聚類，以提高不確定數(shù)據(jù)流聚類效果。

1 不確定數(shù)據(jù)流聚類算法研究

本文研究的數(shù)據(jù)不確定性主要是由于數(shù)據(jù)受帶寬傳輸、延遲和能量等制約因素引起的數(shù)據(jù)缺失，以及數(shù)據(jù)的不準(zhǔn)確性。一些粗粒度的數(shù)據(jù)處理也考慮在內(nèi)。數(shù)據(jù)的結(jié)構(gòu)大多來自網(wǎng)絡(luò)web網(wǎng)絡(luò)，一般是基于流量特征的屬性元組。

1.1 基于聚類劃分的兩階段離群點檢測算法

1.1.1微聚類劃分算法

微聚類劃分算法主要功能是獲取數(shù)據(jù)集，選取數(shù)據(jù)集中微聚類間最小值，建立新聚類。詳細步驟見算法1。

算法1：使用微聚類算法獲取數(shù)據(jù)集的簇數(shù)量k與高質(zhì)量的簇中心。

輸入：數(shù)據(jù)集A={A1,A2,…,Ai,…,Am}中對象數(shù)量m。

輸出：數(shù)據(jù)集中微聚類數(shù)量k與微聚類KBA1,KBA2,…,KBAi,…,KBAk中心。

第1步：將數(shù)據(jù)集A中的全部對象A1,A2,…,Am都初始化成一個相應(yīng)的簇BA1,BA2,…,BAm，也稱微聚類BAm；

第2步：選取2個微聚類間最小值BAi、BAj并刪掉，建立新聚類BAh，原始對象并集即為該聚類里的對象，則BAh={BAi∪BAj}；每個對象代表一個微聚類的初始均值，均值的計算是通過歐式距離求均值獲得。

第3步：基于簇里對象的均值，將各個對象指定至最類似簇KBAk中，刷新簇均值，再次判定各個聚類中心[6]；聚類中心是簇(歐式空間)的形心。

第4步：多次執(zhí)行，簇均值固定后停止[7]；

第5步：輸出數(shù)據(jù)集里微聚類數(shù)量k與微聚類KBA1,KBA2,…,KBAi,…,KBAk中心。

1.1.2基于信息熵的微聚類過濾機制

信息熵可體現(xiàn)數(shù)據(jù)集狀態(tài)，描述數(shù)據(jù)集中數(shù)據(jù)的不確定性，因此，本文采用信息熵描述數(shù)據(jù)集聚類中數(shù)據(jù)對象的部分情況。如果將某些數(shù)據(jù)點從數(shù)據(jù)集中剔除，數(shù)據(jù)集整體便出現(xiàn)不確定性或者無序性[8-9]，此類數(shù)據(jù)點即為全局離群點。變量的不確定性與信息熵具有較大關(guān)聯(lián)性。

根據(jù)上述算法1，將數(shù)據(jù)集A分成k個微聚類KBA={KBA1,KBA2,…,KBAi,…,KBAk}，每個子集個體數(shù)量是k1,k2,…,km；對各微聚類建立一個矩形框R(存在最大個體數(shù))，將此矩形框?qū)嵭芯W(wǎng)格劃分，通過網(wǎng)格中個體分布信息，運算各個網(wǎng)格中個體數(shù)量krn；獲取各個網(wǎng)格中個體占據(jù)的概率qi，便能獲取各聚類的信息熵。

網(wǎng)格建立流程是：將m維目標(biāo)空間劃分為X1×X2×…×Xm網(wǎng)格，各個網(wǎng)絡(luò)第j維目標(biāo)寬度bj是：

(1)

式中，第j維目標(biāo)寬度與目標(biāo)函數(shù)值依次設(shè)成bj、Rj(x)；第j維目標(biāo)劃分?jǐn)?shù)量設(shè)成Xj；x軸決策變量設(shè)成x。為降低復(fù)雜性，將各個對象所占網(wǎng)格的方位用地址描述。

為降低分析復(fù)雜性，設(shè)定：

(2)

(3)

(4)

yj=mod(xj,bj)+j=1,2,…，m

(5)

存在兩個目標(biāo)時的目標(biāo)劃分示意圖如圖1所示。

圖1 網(wǎng)格建立

圖2 數(shù)據(jù)分布

計算網(wǎng)格單元密度，獲取各網(wǎng)格的數(shù)據(jù)點數(shù)量見圖3。

圖3 網(wǎng)格密度

根據(jù)網(wǎng)格中數(shù)據(jù)的分布狀態(tài)，判定個體占據(jù)的概率qi是：

(6)

根據(jù)信息熵原理建立該聚類中對象分布的信息熵D(x)，信息熵變動閾值是：

β=|D(x)-D′(x)|

(7)

式中，各聚類信息熵設(shè)成D′(x)；剔除偏離度最大值后微聚類的信息熵設(shè)成D(x)。對比前后信息熵的變動，設(shè)置變動的閾值為β，若β接近0，則不存在離群點，使用該種過濾方過濾掉微聚類[11]；反之該對象即為離群點，把它導(dǎo)入離群點數(shù)據(jù)集中，該數(shù)據(jù)集稱為全局離群點。

1.1.3基于距離的離群點挖掘算法

上小節(jié)獲取全局離群點后，采用基于距離的離群點挖掘算法挖掘微聚類中的局部離群點[12]。基于距離的離群點挖掘算法第一步運算各微聚類中兩對象間的距離，第二步總結(jié)各對象和剩余對象距離，若剔除對象后的信息熵變動大于閾值β，則該對象為離群點。

設(shè)定微聚類KBA中存在KBAj與KBAi，微聚類的對象數(shù)量設(shè)成m，n表示對象的維數(shù)(屬性)，KBAj與KBAi間的距離設(shè)成bij，那么KBA的聚類矩陣N是：

(8)

微聚類中第i個數(shù)據(jù)對象設(shè)成KBAi，KBAi的偏離度Eoli是：

(9)

式中，矩陣N里第i行的和等于偏離度Eoli。微聚類中各對象都具有各自偏離度Eoli，Eoli值較大，表示對象i和剩余對象聚類較遠，屬于異常屬性的機率較大。如果k是用戶期望的離群點數(shù)量，那么偏離度最大的k個對象就是局部離群點。

1.2 一種不確定數(shù)據(jù)流子空間聚類算法

基于2.1獲取的全局離群點與局部離群點兩種不確定數(shù)據(jù)流，采用一種不確定數(shù)據(jù)流子空間聚類算法完成不確定數(shù)據(jù)流的聚類[13-14]。將相似聚類特征的高維數(shù)據(jù)設(shè)成F，假定不確定數(shù)據(jù)流為C={vfo1,vfo2,…,vfon}，其中vfoi表示隨機一個不確定元組，i∈[1,n]，它的概率距離特征集合是vfoi={F1,F2,…,Fn}，那么對于Cq中隨機兩個不確定元組vfoi和vfoj間的距離近似度可根據(jù)概率距離q≤w(vfoi,vfoj,Cq)進行計算：

(10)

根據(jù)q≤w(vfoi,vfoj,Cq)計算，可將不確定元組vfo集成至非一致的Cq中，之后根據(jù)最優(yōu)概率把數(shù)據(jù)流C集成不一樣的簇B1,B2,…,Bm，Bi代表第i個簇。隨機一個簇Bi存在多個元組，基于整體而言，元組聚集于中心點周圍，能夠構(gòu)建新的元組。

不確定數(shù)據(jù)流子空間聚類算法必須構(gòu)建NC、SW以及OC三種緩沖區(qū)。不確定數(shù)據(jù)流子空間聚類算法的聚類流程如下所示：

a：在數(shù)據(jù)流中選取n個元組設(shè)成中心點；

b：若有新元組加入SW緩沖區(qū)，SW緩沖區(qū)已滿，提取SW里最老元組；

c：若OC緩沖區(qū)中存在最老元組，提取OC中最老元組，且剔除SW最老元組；

d：將新元組導(dǎo)至SW中；

e：BSW(SW緩沖區(qū)的簇)=Bα(新元組)；

f：若返回BSW是非空狀態(tài)便將新元組導(dǎo)至BSW中；

g：反之將新元組放置OC中；

h：若OC已滿，提取OC中最老元組；

i：BOC=Bα；

j：若BOC融合了最老元組，那么將新元組導(dǎo)入BOC；

k：剔除OC中的最老元組；

l:引入新元組，完成聚類[15-16]。

2 實驗分析

實驗數(shù)據(jù)集由網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集KDDUP99中獲取，該數(shù)據(jù)集來源于美國空軍局域網(wǎng)9個星期的網(wǎng)絡(luò)連載數(shù)據(jù)。實驗在數(shù)據(jù)集中的各數(shù)據(jù)中添加一個符合高斯分布的概率，讓其變成不確定數(shù)據(jù)集，通過經(jīng)驗法則，確定聚類數(shù)據(jù)量范圍為1000 GB至5000 GB。實驗設(shè)置本文算法的參數(shù)為SW=200，OC=100。

實驗為測試本文算法有效性，隨機選取60 k的實驗數(shù)據(jù)集，設(shè)定4個不同形狀的聚類，原始數(shù)據(jù)集的示意圖見圖4。

圖4 原始數(shù)據(jù)集分布

采用本文算法聚類后的效果圖如圖5所示。

圖5 本文算法聚類結(jié)果

對比分析圖4和圖5可知，采用本文算法檢測實驗不確定數(shù)據(jù)集中的離群點聚類后，可去除原始數(shù)據(jù)集中大量離群點進行聚類，挖掘出原始數(shù)據(jù)集中4種聚類類，驗證了本文算法的有效性。

采用本文算法、基于密度的聚類算法和DBSCAN聚類算法進行對比實驗。

(1)離群點檢測性能對比

采用三種算法簇是4和5的實驗數(shù)據(jù)集中離群點進行檢測，結(jié)果見表1。

表1 三種算法離群點檢測性能對比結(jié)果

分析表1可知，不同簇條件下本文算法對實驗數(shù)據(jù)集離群點檢測的數(shù)量與實際數(shù)量最大差值為1個，其他兩種算法檢測的數(shù)量與實際相差較大，主要原因在于本文算法采用信息熵描述數(shù)據(jù)集聚類中數(shù)據(jù)對象的部分情況，降低了聚類分析復(fù)雜性。由此可見，本文算法檢測不確定數(shù)據(jù)集中的離群點性能顯著。

(2)聚類效果對比

圖6是三種算法的聚類效果對比結(jié)果。

圖6 三種算法聚類質(zhì)量對比結(jié)果

圖6(a)顯示隨著數(shù)據(jù)量的增多，本文算法的聚類質(zhì)量大于90%，基于密度的聚類算法和DBSCAN聚類算法聚類質(zhì)量都低于80%，圖6(b)顯示隨著維度的增大，本文算法在維度值是5～23之間的聚類質(zhì)量呈現(xiàn)上升階段，維度值24之后聚類質(zhì)量高達100%，而另外兩種算法的聚類質(zhì)量在維度是15之后不斷降低，質(zhì)量較差，說明數(shù)據(jù)集中數(shù)據(jù)維度對基于密度的聚類算法和DBSCAN聚類算法影響較大。由此可見，數(shù)據(jù)量和維度的增加未對本文算法的聚類質(zhì)量產(chǎn)生不良干擾，本文算法聚類質(zhì)量較好。主要原因在于本文算法采用基于距離的離群點挖掘算法挖掘微聚類中的局部離群點，降低異常屬性的機率，提高了聚類質(zhì)量。

(3)聚類算法的效率對比

圖7為三種算法的聚類時間對比結(jié)果。

圖7 三種算法的聚類時間對比結(jié)果

分析圖7可知，隨著數(shù)據(jù)量的增多，三種算法的聚類時間也隨之增多，但本文算法耗費的時間始終低于另外兩種算法，當(dāng)數(shù)據(jù)量為5000 GB時，本文算法的耗時僅有75 s。

(4)聚類算法的伸縮性

圖8描述三種算法的伸縮性對比結(jié)果，首先調(diào)整數(shù)據(jù)集的維度，自10變化至60，設(shè)定數(shù)據(jù)流的長度與簇數(shù)量；然后分析在數(shù)據(jù)量從1000 GB升至5000 GB時三種算法的伸縮性。

圖8 三種算法伸縮性對比結(jié)果

分析圖8可知，在維度與數(shù)據(jù)量逐漸增大時，本文算法的聚類時間增長斜率低于另外兩種算法，由此可知，隨著維度與數(shù)據(jù)量的增長，本文算法運行時間的上升速度低于另外兩種算法，說明本文算法的伸縮性優(yōu)于另外兩種算法，不會因為維度與數(shù)量的變動產(chǎn)生較大的反應(yīng)。

3 結(jié) 語

本文提出基于離群點檢測的不確定數(shù)據(jù)流聚類算法。首先采用微聚類劃分算法將數(shù)據(jù)集劃分為若干個微聚類，再使用信息熵判斷微聚類里是否存在離群點，如果不存在離群點，便不必進行檢測，此舉可減少計算量和檢測誤差；反之將離群點導(dǎo)入離群點數(shù)據(jù)集中，計算聚類里其余對象信息熵，獲取全局離群點，并通過基于距離的離群點挖掘算法獲取局部離群點。最終采用不確定數(shù)據(jù)流子空間聚類算法聚類不確定的數(shù)據(jù)流。本文算法與同類算法相比，離群點檢測精度較高，聚類效率與聚類質(zhì)量都高于同類算法，且維度與數(shù)量的變動不會對本文算法產(chǎn)生較大干擾。