高維數(shù)據(jù)流的聚類離群點(diǎn)檢測算法研究

程 艷，苗永春

(江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院，江西南昌330022)

0 引言

隨著云計(jì)算、物聯(lián)網(wǎng)及社交網(wǎng)絡(luò)等技術(shù)的興起，數(shù)據(jù)的類型和規(guī)模正在不斷增長和積累，大數(shù)據(jù)時(shí)代已到來.半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)是大數(shù)據(jù)時(shí)代的重要數(shù)據(jù)類型組成部分［1］.除此之外，數(shù)據(jù)像從“池塘”變成“海洋”，不僅數(shù)據(jù)的量大，數(shù)據(jù)的維數(shù)也劇增，結(jié)構(gòu)化數(shù)據(jù)的處理方式無法滿足時(shí)代需求，因此數(shù)據(jù)流的離群點(diǎn)檢測成為當(dāng)代研究的熱點(diǎn).離群點(diǎn)檢測［2－4］目的是試圖捕獲那些顯著偏離多數(shù)模式的異常情況.可用來避免疾病擴(kuò)散、網(wǎng)絡(luò)入侵檢測、信用卡惡意透支、貸款證明的審核等，這些用途正是大數(shù)據(jù)時(shí)代下離群點(diǎn)檢測盛行的原因.

迄今為止，對傳統(tǒng)的離群點(diǎn)檢測算法的研究已經(jīng)取得豐碩的研究成果，但將其運(yùn)用到采用數(shù)據(jù)流環(huán)境的應(yīng)用領(lǐng)域，離群點(diǎn)檢測的效果難以達(dá)到用戶滿意.問題在于數(shù)據(jù)流的數(shù)據(jù)是按照時(shí)間序列到達(dá)，一旦流過處理節(jié)點(diǎn)就不可再現(xiàn)，而傳統(tǒng)靜態(tài)數(shù)據(jù)集離群點(diǎn)檢測算法對數(shù)據(jù)要進(jìn)行多次掃描，無法滿足數(shù)據(jù)流一次掃描的條件.另外，數(shù)據(jù)流的數(shù)據(jù)動(dòng)態(tài)變化的頻率遠(yuǎn)遠(yuǎn)高于靜態(tài)數(shù)據(jù)的更新頻率，現(xiàn)有算法無法跟上數(shù)據(jù)流變化的速度，效率低.大數(shù)據(jù)時(shí)代數(shù)據(jù)流的維數(shù)比較高，已有算法對高維數(shù)據(jù)集檢測離群點(diǎn)的結(jié)果并不理想.

針對上述存在的問題，本文提出一種高維數(shù)據(jù)流的聚類離群點(diǎn)檢測(clustering－based outlier detection for high－dimensional data stream，CODHD－Stream)算法.該算法采用滑動(dòng)窗口技術(shù)控制數(shù)據(jù)流，運(yùn)用屬性約簡算法對高維數(shù)據(jù)流預(yù)處理和基于距離的信息熵過濾機(jī)制的K－means聚類算法挖掘離群點(diǎn)，最后實(shí)驗(yàn)表明，該算法在較大程度上提高了對高維數(shù)據(jù)流離群點(diǎn)檢測的效率和精確度.

1 問題描述和相關(guān)定義

1.1 數(shù)據(jù)流離群點(diǎn)挖掘

數(shù)據(jù)流［2］是一種高速到來的實(shí)時(shí)、連續(xù)、有序、只能被讀一遍或少數(shù)遍的記錄構(gòu)成的序列.數(shù)據(jù)流中的記錄的類型可以是關(guān)系元組，也可以是一個(gè)對象實(shí)例.在實(shí)際應(yīng)用中，記錄的類型多指關(guān)系元組，則數(shù)據(jù)流是由關(guān)系元組構(gòu)成的數(shù)據(jù)集，數(shù)據(jù)流的長度是所包含記錄的個(gè)數(shù).

在實(shí)際工程應(yīng)用領(lǐng)域，交互的數(shù)據(jù)多為高維數(shù)據(jù)流，高維是指數(shù)據(jù)屬性比較多.高維數(shù)據(jù)流形式化的描述為:設(shè)S為高維數(shù)據(jù)流集，S為n維空間，其屬性為A1，A2，…，An，則記 S=A1×A2× … ×An.n維數(shù)據(jù)流記為 D={D1，D2，…，Dm}，數(shù)據(jù)項(xiàng)分別為T1，T2，…，Tm時(shí)刻到達(dá)，每個(gè) Di，i=1，2，…，m 均為一個(gè)n維記錄，用Di={ai1，ai2，…，ain}∈S表示，其中aij表示為(i=1，2，…，m，j=1，2，…，n)數(shù)據(jù)項(xiàng)Di在屬性Aj上的值.

由于數(shù)據(jù)流是不可再現(xiàn)的，即數(shù)據(jù)只能按照產(chǎn)生的順序訪問一次或少數(shù)次［3］，數(shù)據(jù)流的動(dòng)態(tài)變化特性要求算法數(shù)據(jù)流的預(yù)處理速度要不低于數(shù)據(jù)流的更新頻率，且能利用有限的存儲(chǔ)空間對“無限”的數(shù)據(jù)流進(jìn)行處理［4］.本文采用的數(shù)據(jù)流離群點(diǎn)檢測框架圖如圖1所示.

圖1 數(shù)據(jù)流離群點(diǎn)檢測框架圖

數(shù)據(jù)流離群點(diǎn)檢測算法可分為聚類、分類和頻繁模式算法等.典型的聚類離群點(diǎn)檢測算法包括K均值(K－means)、DBSCAN和CluStream聚類算法.K－means［5－6］算法和 DBSCAN［7］算法不能處理數(shù)據(jù)流中不同時(shí)間區(qū)間的聚類問題，另外該算法在處理高維數(shù)據(jù)流，一次完成數(shù)據(jù)處理，不僅運(yùn)算量大，時(shí)間和空間復(fù)雜度也高.CluStream［8］算法利用界標(biāo)窗口模型對數(shù)據(jù)流進(jìn)行聚類分析，數(shù)據(jù)流的動(dòng)態(tài)變化特性決定數(shù)據(jù)流中的微簇和離群點(diǎn)是可以相互轉(zhuǎn)化的，而該算法不能適應(yīng)滑動(dòng)窗口下的聚類需求，且形成的微簇不能反映當(dāng)前數(shù)據(jù)流中的數(shù)據(jù)分布狀況.本文在借鑒上述K－means聚類算法的基礎(chǔ)上，引入基于距離的信息熵過濾機(jī)制，提出了一種高維數(shù)據(jù)流的聚類離群點(diǎn)檢測算法.

1.2 相關(guān)定義

定義1(屬性的支持度p)屬性集U={u1，u2，…，un}(n ≥ 1)，對應(yīng)的關(guān)注度A={a1，a2，…，an}(0≤ai≤1，i=1，2，…，n)，則屬性u(píng)i的支持度定義為

其中0≤p(ui)≤1，計(jì)算中對分母為0的情況進(jìn)行消除，將式子分子、分母同時(shí)加1，避免接近于0的極其小的正數(shù).

定義2(信息熵)對于有限集的隨機(jī)變量X={x1，x2，…，xn}(n ≥ 1)，對應(yīng)的概率為 p={p1，p2，…，pn}(0≤pi≤1，i=1，2，…，n)，且有1，則該有限集的信息熵為

其中pi為發(fā)生事件xi的概率，n為可能發(fā)生的事件總數(shù).

定義3(熵均值)對于有限集的隨機(jī)變量X={x1，x2，…，xn}(n ≥ 1)，對應(yīng)的信息熵值為 E={E(a1)，E(a2)，…，E(an)}，則該有限集的熵均值定義為

定義4(距離矩陣)KCoi和KCoj是微聚類KCo中的2個(gè)對象，則KCo的距離矩陣DM定義為

其中n為微聚類的對象數(shù)，m為對象的維數(shù)，dij是KCoi和KCoj之間的距離.

定義5(偏離度)微聚類中對象i的偏離度定義為

其中Deg為矩陣DM中第i行的和，對微簇類中的任意一個(gè)對象，都存在一個(gè)偏離度Deg，偏離度值越大，說明該對象與其他對象的距離越遠(yuǎn)，其為離群點(diǎn)的可能性越大.

2 高維數(shù)據(jù)流的聚類離群點(diǎn)檢測(CODHD－Stream)算法

2.1 屬性約簡算法

針對實(shí)際應(yīng)用，屬性集中的屬性存在核屬性和非核屬性之分［9］.其中，核屬性是表述知識(shí)必不可少的屬性，反之為非核屬性.如果在數(shù)據(jù)挖掘前僅選取核屬性參與運(yùn)算，不僅可以排除非核屬性帶來的干擾，還可以大大降低算法的復(fù)雜度.

目前，數(shù)據(jù)降維方法［10－11］主要分為2類:線性降維和非線性降維，能夠有效地對數(shù)據(jù)流進(jìn)行特征提取，實(shí)現(xiàn)高維數(shù)據(jù)降維.如果采用這類降維方法，則CODHD－Stream算法必須2次遍歷數(shù)據(jù)流.第1次遍歷從數(shù)據(jù)中提取特征，輸出數(shù)據(jù)集的特征空間，第2次遍歷才可以根據(jù)提取到的特征空間，將數(shù)據(jù)投影到低維空間，再進(jìn)行離群點(diǎn)檢測.這種做法較難提高高維數(shù)據(jù)流的離群點(diǎn)檢測的效率.一般針對實(shí)際應(yīng)用，用戶關(guān)注的數(shù)據(jù)的特征空間是有限的，只需要用戶給出對數(shù)據(jù)項(xiàng)的各個(gè)屬性的關(guān)注度T∈［0，1］，對不關(guān)注屬性T取值為0，關(guān)注的屬性，關(guān)注度T∈［0，1］，其中，決策屬性的關(guān)注度為1.

算法1 屬性約簡算法

輸入:m維數(shù)據(jù)流DS;數(shù)據(jù)項(xiàng)屬性的關(guān)注度a1，a2，…，am

輸出:核屬性集CoreSet

(i)讀數(shù)據(jù)流，移動(dòng)滑動(dòng)窗口界標(biāo)，向前推n個(gè)元組;

(ii)根據(jù)用戶給出對數(shù)據(jù)項(xiàng)屬性的關(guān)注度A={a1，a2，…，an}，根據(jù)定義1計(jì)算出對應(yīng)的屬性支持度 P={p(a1)，p(a2)，…，p(an)};

(iii)根據(jù)定義2計(jì)算各維屬性的信息熵概率E={E(a1)，E(a2)，…，E(an)}其中 E(a1)=log2p(ai);

(iv)刪除最大的max(E(ai))，根據(jù)定義3計(jì)算屬性組合的熵均值;

(v)判斷屬性的信息熵E(ai)是否大于屬性組合的熵均值，若大于，則計(jì)算除去該屬性后的信息熵E'(aA)－E(aA)=ε，若ε足夠小，則i為核屬性，反之，為非核屬性;

(vi)返回核屬性集CoreSet.

2.2 基于距離信息熵過濾機(jī)制的K－means離群點(diǎn)檢測算法

根據(jù)定義2，聚類中的對象分布的信息熵E(x)，用來描述聚類中對象分布指數(shù).信息熵的閾值設(shè)定為

其中E'(x)為指每個(gè)聚類的信息熵，E(x)為去除偏離度最大的對象之后的微聚類的信息熵.比較對象排除前后信息熵變化，設(shè)定對應(yīng)的一個(gè)閾值σ，如果σ變化無限小，幾乎趨于0，則說明不包含離群點(diǎn)，從而把該微聚類過濾掉;反之，該對象是一個(gè)離群點(diǎn)，應(yīng)該將其加入到離群點(diǎn)數(shù)據(jù)集中.

對于數(shù)據(jù)集A有m個(gè)數(shù)據(jù)項(xiàng)Ai組成Ai={ai1，ai2，…，ain}(i=1，2，…，m)，數(shù)據(jù)為 n 維.算法首先設(shè)定滑動(dòng)窗口的大小為N，即滑動(dòng)窗口內(nèi)有N條n維的數(shù)據(jù)項(xiàng)A1，A2，…，An;然后將滑動(dòng)窗口的數(shù)據(jù)流劃分，順序的m個(gè)數(shù)據(jù)點(diǎn)構(gòu)成一個(gè)劃分，采用屬性約簡算法對數(shù)據(jù)項(xiàng)降維，再對每個(gè)劃分內(nèi)的m個(gè)數(shù)據(jù)點(diǎn)進(jìn)行k均值聚類.k均值聚類是一個(gè)改進(jìn)的聚類算法.

算法2 基于距離信息熵過濾機(jī)制的K－means離群點(diǎn)檢測算法

輸入:m個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集;

輸出:k個(gè)離群點(diǎn);

(i)將m個(gè)數(shù)據(jù)點(diǎn)的數(shù)據(jù)集初始化一個(gè)對應(yīng)的簇m1，m2，…，mn和簇均值 Km1，Km2，…，Kmn;

(ii)計(jì)算任意2個(gè)聚類之間的距離，選擇距離最小的2個(gè)聚類mi，mj，創(chuàng)建一個(gè)新的聚類mk和簇中心 Kmk，令mk={mi∪mj}，刪除mi，mj即對應(yīng)的簇中心Kmi，Kmj，并返回微聚類的個(gè)數(shù)c;

(iii)續(xù)處理下一個(gè)數(shù)據(jù)集劃分中的m個(gè)數(shù)據(jù)點(diǎn)，根據(jù)簇中對象的均值，將m個(gè)數(shù)據(jù)點(diǎn)指派到最相似的簇中，更新每個(gè)聚類的簇均值;

(iv)反復(fù)執(zhí)行，直至某一時(shí)段內(nèi)的數(shù)據(jù)已全部遍歷時(shí)，輸出該數(shù)據(jù)集中微聚類的個(gè)數(shù)c和微聚類的中心;

(v)根據(jù)定義2計(jì)算聚類的信息熵，根據(jù)定義4得到相關(guān)的距離矩陣，根據(jù)定義5計(jì)算微聚類內(nèi)對象的偏離度，并按降序排列;

(vi)從第1個(gè)對象開始依次取出，并計(jì)算余下數(shù)據(jù)集的信息熵值，判斷該值是否小于閾值σ，若小于σ，則說明不包含離群點(diǎn)，排除掉此對象，否則取出該數(shù)據(jù)點(diǎn)，按照偏離度從大到小存至OSet離群點(diǎn)集合中;

(vii)輸出OSet離群點(diǎn)集合前k個(gè)離群點(diǎn).

2.3 CODHD－Stream算法思想

CODHD－Stream算法的主要思想是把滑動(dòng)窗口的數(shù)據(jù)流按照到達(dá)的時(shí)間的先后順序劃分m個(gè)數(shù)據(jù)點(diǎn)，通過屬性約簡算法對數(shù)據(jù)集降維，得到核屬性，即低維空間;把高維數(shù)據(jù)流中的數(shù)據(jù)項(xiàng)投影到該低維空間;用基于距離信息熵過濾機(jī)制的K－means算法檢測數(shù)據(jù)集中的離群點(diǎn)，直至某時(shí)間段的數(shù)據(jù)流結(jié)束;最后輸出OSet離群點(diǎn)集合前k個(gè)離群點(diǎn).

3 算法性能與實(shí)驗(yàn)結(jié)果分析

3.1 算法理論分析

本文構(gòu)造的CODHD－Stream算法具有良好的時(shí)間效率和精確度.由于屬性集的約簡可以排除不相關(guān)數(shù)據(jù)元素的干擾，便于針對特征空間劃分微聚類，增加相似數(shù)據(jù)聚集度，從而提高算法的精確度.

定理1 CODHD－Stream算法具有相對于數(shù)據(jù)流數(shù)據(jù)集N線性的時(shí)間復(fù)雜度.

證滑動(dòng)窗口的長為N，設(shè)數(shù)據(jù)的維數(shù)為m為常數(shù)，屬性約簡算法的復(fù)雜度O(m×N)，屬性約簡后的屬性為m'為常數(shù)，最壞的情況下m'=m.離群點(diǎn)檢測階段，將數(shù)據(jù)集劃分成微聚類，劃分需要時(shí)間復(fù)雜度為O(2m'×N).最壞的情況下，劃分成的微聚類的個(gè)數(shù)為N，算法檢測微聚類的離群點(diǎn)需要O(m×N)，CODHD－Stream算法總共需要時(shí)間復(fù)雜度為O((2m'+m)×N)，因此，算法具有線性的時(shí)間復(fù)雜度.

實(shí)際情況下，由于高維數(shù)據(jù)流比較稀疏，屬性約簡后的維數(shù)遠(yuǎn)小于m，劃分成的微聚類個(gè)數(shù)一定小于N，則CODHD－Stream算法對高維數(shù)據(jù)流進(jìn)行離群點(diǎn)檢測的效果較理想.

3.2 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證CODHD－Stream算法的效率及有效性，將通過實(shí)驗(yàn)類比較CODHD－Stream算法和CluStream算法各自的性能，通過實(shí)驗(yàn)對CODHD－Stream算法的檢測精確度和效率進(jìn)行分析.算法采用C++語言實(shí)現(xiàn)，硬件配置:CPU 2.6 GHz、內(nèi)存1 GB、硬盤512 GB;開發(fā)工具:VS2010;所采用的實(shí)驗(yàn)數(shù)據(jù)是在基于Moodle網(wǎng)絡(luò)教學(xué)平臺(tái)采集的數(shù)據(jù)，本實(shí)驗(yàn)用到的數(shù)據(jù)記錄來源于虛擬學(xué)習(xí)社區(qū)局域網(wǎng)防攻擊行為模塊所得的TCP、UDP連接記錄.

由于采集到的數(shù)據(jù)量比較大，本實(shí)驗(yàn)選擇最新的2600條記錄，每個(gè)數(shù)據(jù)項(xiàng)有40個(gè)屬性構(gòu)成，包括登錄的IP地址、登錄時(shí)間、傳輸字節(jié)數(shù)、文件創(chuàng)建量、登錄次數(shù)、失敗登錄次數(shù)等，給定屬性的關(guān)注度分別為 1，0.98，0.97，0.87，0.88，0.90，….

本實(shí)驗(yàn)的精確度的評(píng)價(jià)標(biāo)準(zhǔn)是實(shí)際檢測出離群點(diǎn)個(gè)數(shù)占數(shù)據(jù)集中包含離群點(diǎn)個(gè)數(shù)的比例，比例越大，精度越高.通過6次實(shí)驗(yàn)，取實(shí)驗(yàn)結(jié)果的平均值，實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 2種算法的精度比較圖

由圖2可知，對于相同的數(shù)據(jù)集，CODHDStream算法的精度在90%左右，而CluStream算法的精度不到80%，采用改進(jìn)的算法CODHD－Stream的離群點(diǎn)檢測的精度更高.由于CODHD－Stream算法采用了屬性約簡算法對高維數(shù)據(jù)流進(jìn)行降維處理，排除無用屬性的干擾，因此該算法適合處理高維數(shù)據(jù)集.

處理數(shù)據(jù)集的執(zhí)行時(shí)間是在單個(gè)局部站點(diǎn)進(jìn)行的，所有結(jié)果均取自10次實(shí)驗(yàn)平均值，實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 2種算法的運(yùn)行效率的比較圖

從圖3可以看到算法的處理時(shí)間都隨數(shù)據(jù)流量的增加呈線性增長，變化趨勢總體上保持一致，CODHD－Stream算法的處理時(shí)間明顯大于CluStream算法.可見，CODHD－Stream算法時(shí)間復(fù)雜度比CluStream算法小，這是由于CODHD－Stream算法中的離群點(diǎn)檢測算法是基于K－means和距離信息熵過濾機(jī)制挖掘離群點(diǎn)算法，該算法較大程度上降低了算法的時(shí)間復(fù)雜度.

為了測試數(shù)據(jù)維數(shù)對算法的影響，人工生成分別為15，20，25，30，35 維數(shù)的數(shù)據(jù)集，如圖 4 所示，隨著維數(shù)的增加，算法執(zhí)行時(shí)間幾乎呈線性增長趨勢，說明該算法對高維數(shù)據(jù)流具有較好的伸縮性.

圖4 維數(shù)對算法的影響圖

4 結(jié)束語

本文在深入研究當(dāng)前比較典型的數(shù)據(jù)流的聚類算法的基礎(chǔ)上，提出了適合高維數(shù)據(jù)流的聚類算法，該算法首先設(shè)定合適的滑動(dòng)窗口大小，對滑動(dòng)窗口的數(shù)據(jù)流按順序進(jìn)行劃分，對每段數(shù)據(jù)集先用屬性約簡算法進(jìn)行預(yù)處理，再用基于K－means和距離信息熵過濾機(jī)制挖掘離群點(diǎn)算法進(jìn)行離群點(diǎn)檢測.該算法具有較快的處理速度，較高的精確度，能夠滿足高維數(shù)據(jù)流的離群點(diǎn)檢測的要求.在下一步的工作中，筆者打算將本文提出高維數(shù)據(jù)流的聚類算法運(yùn)用在智能網(wǎng)絡(luò)教學(xué)的異常學(xué)習(xí)行為檢測的領(lǐng)域中.

［1］ Wu Xindong，Zhu Xingquan，Wu Gongqing，et al.Datamining with big data ［J］.Knowledge and Data Engineering，2014，26(1):97－107.

［2］ Wang Changdong，Lai Jianghuang，Huang Dong，et al.SVStream:a support vector－based algorithm for clustering data streams［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25(6):1410－1424.

［3］AlbaneseA，Pal S K，Petrosino，A.Rough sets，kernel set，and spatiotemporal outlier detection ［J］.Knowledge and Data Engineering，2014，26(1):194－207.

［4］Kollios G，Gunopulos D，Koudas N，et al.Efficient biased sampling for approximate clustering and outlier detection in large data sets［J］.Knowledge and Data Engineering，2003，15(5):1170－1187.

［5］Charalampidis D.Amodified k－means algorithm for circular invariant clustering［J］.PatternAnalysis and MachineIntelligence，2005，27(12):1856－1865.

［6］Kanungo Tapas，Mount D M，Netanyahu N S，et al.An efficient k－means clustering algorithm:analysis and implementation ［J］.PatternAnalysis and MachineIntelligence，2002，24(7):881－892.

［7］YipA M，Ding C，Chan T F.Dynamic cluster formation using level setmethods［J］.PatternAnalysis and MachineIntelligence，2006，28(6):877－889.

［8］ Guha S，MeyersonA，Mishra N，et al.Clustering data streams:Theory and practice［J］.Knowledge and Data Engineering，2003，15(3):515－528.

［9］Jiang Feng，Sui Yuefei，Cao Cungen.An information entropy－based approach to outlier detection in rough sets［J］.Expert SystAppl，2010，37(1):6338－6344.

［10］Kapoor R，Gupta R.Non－linear dimensionality reduction using fuzzy lattices［J］.IET ComputerVision，2013，7(3):201－208.

［11］Nie Bin，Wang Zhuo，Du Jianqiang，et al.The research for information granule reduction and cluster based on the partial least squares ［J］.Journal of Jiangxi NormalUniversity:Natural Science，2012，36(5):472－476.