程 艷，苗永春

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

0 引言

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

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

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

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

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

數(shù)據(jù)流［2］是一種高速到來的實時、連續(xù)、有序、只能被讀一遍或少數(shù)遍的記錄構(gòu)成的序列.數(shù)據(jù)流中的記錄的類型可以是關(guān)系元組，也可以是一個對象實例.在實際應(yīng)用中，記錄的類型多指關(guān)系元組，則數(shù)據(jù)流是由關(guān)系元組構(gòu)成的數(shù)據(jù)集，數(shù)據(jù)流的長度是所包含記錄的個數(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ù)項分別為T1，T2，…，Tm時刻到達，每個 Di，i=1，2，…，m 均為一個n維記錄，用Di={ai1，ai2，…，ain}∈S表示，其中aij表示為(i=1，2，…，m，j=1，2，…，n)數(shù)據(jù)項Di在屬性Aj上的值.

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

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

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

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)，則屬性ui的支持度定義為

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

定義2(信息熵)對于有限集的隨機變量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(熵均值)對于有限集的隨機變量X={x1，x2，…，xn}(n ≥ 1)，對應(yīng)的信息熵值為 E={E(a1)，E(a2)，…，E(an)}，則該有限集的熵均值定義為

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

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

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

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

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

2.1 屬性約簡算法

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

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

輸出:核屬性集CoreSet

(i)讀數(shù)據(jù)流，移動滑動窗口界標，向前推n個元組;

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

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

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

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

(vi)返回核屬性集CoreSet.

2.2 基于距離信息熵過濾機制的K－means離群點檢測算法

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

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

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

算法2 基于距離信息熵過濾機制的K－means離群點檢測算法

輸入:m個數(shù)據(jù)點的數(shù)據(jù)集;

輸出:k個離群點;

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

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

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

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

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

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

(vii)輸出OSet離群點集合前k個離群點.

2.3 CODHD－Stream算法思想

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

3 算法性能與實驗結(jié)果分析

3.1 算法理論分析

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

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

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

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

3.2 實驗結(jié)果分析

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

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

本實驗的精確度的評價標準是實際檢測出離群點個數(shù)占數(shù)據(jù)集中包含離群點個數(shù)的比例，比例越大，精度越高.通過6次實驗，取實驗結(jié)果的平均值，實驗結(jié)果如圖2所示.

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

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

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

圖3 2種算法的運行效率的比較圖

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

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

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

4 結(jié)束語

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