葉福蘭

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

0 引 言

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

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

上述算法存在檢測(cè)性能差以及聚類質(zhì)量低的問題，因此，本文提出基于離群點(diǎn)檢測(cè)的不確定數(shù)據(jù)流聚類算法，獲取的全局離群點(diǎn)與局部離群點(diǎn)兩種不確定數(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 基于聚類劃分的兩階段離群點(diǎn)檢測(cè)算法

1.1.1微聚類劃分算法

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

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

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

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

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

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

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

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

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

1.1.2基于信息熵的微聚類過濾機(jī)制

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

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

網(wǎng)格建立流程是：將m維目標(biāo)空間劃分為X1×X2×…×Xm網(wǎng)格，各個(gè)網(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ù)雜性，將各個(gè)對(duì)象所占網(wǎng)格的方位用地址描述。

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

(2)

(3)

(4)

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

(5)

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

圖1 網(wǎng)格建立

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

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

圖3 網(wǎng)格密度

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

(6)

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

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

(7)

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

1.1.3基于距離的離群點(diǎn)挖掘算法

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

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

(8)

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

(9)

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

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

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

(10)

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

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

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

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í)驗(yàn)分析

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

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

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

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

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

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

采用本文算法、基于密度的聚類算法和DBSCAN聚類算法進(jìn)行對(duì)比實(shí)驗(yàn)。

(1)離群點(diǎn)檢測(cè)性能對(duì)比

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

表1 三種算法離群點(diǎn)檢測(cè)性能對(duì)比結(jié)果

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

(2)聚類效果對(duì)比

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

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

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

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

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

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

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

(4)聚類算法的伸縮性

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

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

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

3 結(jié) 語

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