許福徐建

基于組合增量聚類的數(shù)據(jù)流異常檢測(cè)研究?

許福徐建

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院南京210094）

面向數(shù)據(jù)流的異常檢測(cè)方法在諸如實(shí)時(shí)監(jiān)控、網(wǎng)絡(luò)入侵檢測(cè)等領(lǐng)域有著廣泛的應(yīng)用。然而，數(shù)據(jù)流連續(xù)不斷的特點(diǎn)，以及數(shù)據(jù)流處理的特殊性和時(shí)效性等限制使得傳統(tǒng)的聚類算法已不再適用，因此增量聚類成為當(dāng)前面向數(shù)據(jù)流異常檢測(cè)的研究熱點(diǎn)。論文在改進(jìn)了兩類增量聚類方法的基礎(chǔ)上，針對(duì)單一增量聚類檢測(cè)率低，誤報(bào)率較高的問題，提出了一種基于組合增量聚類的數(shù)據(jù)流異常檢測(cè)方法，該方法以改進(jìn)的增量聚類算法為基礎(chǔ)，設(shè)計(jì)了有效的共識(shí)函數(shù)對(duì)多種聚類算法的結(jié)果進(jìn)行融合。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的聚類算法在處理效率上有明顯提升，適用于增量聚類，并且提出的組合增量聚類相比于單一聚類方法，具有更好的聚類性能。

數(shù)據(jù)流；異常檢測(cè)；增量聚類；子空間聚類；聚類融合

Class NumberTP391

1引言

數(shù)據(jù)流異常檢測(cè)技術(shù)［14～15］是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一，在網(wǎng)絡(luò)安全、信用欺詐和金融分析等領(lǐng)域有著廣泛的應(yīng)用。隨著大數(shù)據(jù)時(shí)代的到來，許多數(shù)據(jù)如電話記錄、網(wǎng)絡(luò)文件等都以數(shù)據(jù)流的形式出現(xiàn)，然而數(shù)據(jù)流具有的海量、概念漂移等特點(diǎn)對(duì)于現(xiàn)有的數(shù)據(jù)挖掘方法研究提出了一些新的挑戰(zhàn)。目前，研究人員針對(duì)數(shù)據(jù)流的上述特點(diǎn)，開展了不少研究工作來應(yīng)對(duì)這些挑戰(zhàn)。例如，文獻(xiàn)［1］中提出基于CluStream算法的數(shù)據(jù)流聚類框架，引入了微簇和時(shí)間幀概念，將數(shù)據(jù)流聚類過程分為在線和離線兩個(gè)階段，在線部分實(shí)時(shí)處理流數(shù)據(jù)，離線部分提供所有時(shí)間的聚類結(jié)果。文獻(xiàn)［11］提出一種基于數(shù)據(jù)流聚類，盡管這些研究工作取得了不錯(cuò)的檢測(cè)效果，然而仍然面臨著一些問題，比如聚類算法的處理效率不高，隨著新數(shù)據(jù)的不斷到來，需要不斷調(diào)整和更新聚類的結(jié)果，增量聚類［8］的效率不高等。此外，任何聚類算法本身都有一定的局限性，將不同聚類算法相結(jié)合，采用分階段、分層次的增量聚類，即將聚類對(duì)象加細(xì)，或者將同一時(shí)刻不同的聚類結(jié)果進(jìn)行融合來考慮，有機(jī)會(huì)去進(jìn)一步改善聚類的結(jié)果穩(wěn)定性，提升聚類質(zhì)量。基于上述分析，研究有效的增量聚類方法來進(jìn)一步提升聚類的效率和檢測(cè)效果成為一個(gè)重要的研究課題。

本文針對(duì)傳統(tǒng)聚類方法［9，12］的局限性以及單一增量聚類方法存在的隨機(jī)性大、不穩(wěn)定和準(zhǔn)確性低等缺點(diǎn)，在比較分析不同聚類算法的思想、應(yīng)用領(lǐng)域和應(yīng)用特點(diǎn)的基礎(chǔ)上，提出一種基于組合增量聚類的數(shù)據(jù)流異常檢測(cè)方法，該方法以改進(jìn)的子空間聚類算法和DBSCAN聚類作為基聚類算法，設(shè)計(jì)基于投票策略的共識(shí)函數(shù)用于實(shí)現(xiàn)不同聚類結(jié)果融合，并驗(yàn)證了算法的有效性。

2改進(jìn)的子空間聚類算法

在面向數(shù)據(jù)流異常檢測(cè)的聚類研究中，所要處理的數(shù)據(jù)通常是高維數(shù)據(jù)。作為一種有效的解決高維數(shù)據(jù)［6］聚類的方法，子空間聚類［2，5，10］在諸如圖像處理、計(jì)算機(jī)視覺等領(lǐng)域有著重要的應(yīng)用。文獻(xiàn)［3］提出了一種基于稀疏表示的隱子空間聚類算法LSC（Latent Subspace Clustering），其使用K-SVD算法訓(xùn)練字典，雖然字典有優(yōu)秀的重構(gòu)能力，但是缺乏足夠的判別信息，導(dǎo)致LSC算法的聚類精度不高。針對(duì)以上問題，Jiang等［7］提出了具有標(biāo)簽一致性的LC-KSVD算法來改進(jìn)字典訓(xùn)練方法以提高LSC算法的聚類精度，然而，字典訓(xùn)練階段的耗時(shí)也隨之大幅增加，數(shù)據(jù)流聚類受到時(shí)間和內(nèi)存、CPU等資源的限制。為了緩解這些方面的限制，能將LSC應(yīng)用于組合增量聚類方法中，本文提出了一種新的增量式字典訓(xùn)練方法，使其效率能滿足增量聚類要求。

稀疏表示［17～18］是指用盡可能少的基或字典原子的線性組合表示數(shù)據(jù)，其目的在于刻畫數(shù)據(jù)的子空間特性，提供了一種高維數(shù)據(jù)在低維子空間表示的自然模型。字典訓(xùn)練表示是從數(shù)據(jù)中學(xué)習(xí)稀疏表示下的最優(yōu)表示，同時(shí)訓(xùn)練初始字典使得字典的原子特性更接近于所需表示的原始信號(hào)，以此獲得誤差更小的新字典。LSC算法在構(gòu)建字典的過程中具有一定的隨機(jī)性，使得訓(xùn)練出的字典缺少足夠的重構(gòu)能力和判別能力。為了改進(jìn)這一缺陷，綜合考慮重構(gòu)誤差，判別能力以及線性分類性能這三方面因素提出了新的學(xué)習(xí)模型：

其解為

參數(shù)W的初始化與參數(shù)A類似，利用上訴模型求得如下的解：

其中，參數(shù)X是在已知初始字典D0的情況下，使用K-SVD算法所求得的信號(hào)Y的稀疏表示系數(shù)矩陣。

具體的增量式字典訓(xùn)練算法如算法1所示。

算法1增量式字典訓(xùn)練算法

輸入：Y，m，D1，A1，W1，ρ，n，M，μ，v1，v2，b

輸出：測(cè)試信號(hào)Y2的聚類標(biāo)簽

1）將信號(hào)Y分為Y1∈RK×T和Y2∈RK×N兩部分，Y1為帶有標(biāo)簽信息的訓(xùn)練信號(hào)用于訓(xùn)練字典，Y2為不帶標(biāo)簽信息的測(cè)試信號(hào)用于聚類算法。

2）求得訓(xùn)練信號(hào)Y1的判別式稀疏編碼矩陣Q∈RM×T和類標(biāo)矩陣H∈Rm×T。

3）增量式訓(xùn)練字典D：

for i=1…n：

（1）依次從信號(hào)Y1中隨機(jī)抽取一批信號(hào)

其中D代表字典矩陣，X是稀疏表示稀疏矩陣，A=|X|，W是非負(fù)臨接矩陣，α和β是平滑因子，Q是關(guān)于信號(hào)Y的判別式稀疏編碼矩陣。

在使用字典學(xué)習(xí)模型時(shí)，需要對(duì)參數(shù)D，A，W進(jìn)行初始化，具體方法如下：

對(duì)于字典D的初始化，針對(duì)每一類別的信號(hào)用K-SVD算法訓(xùn)練得到各自類別的字典，再將訓(xùn)練得到的字典合并為一個(gè)完整的初始字典D0，即所有類共享的字典。

對(duì)于參數(shù)A的初始化，使用多元嶺回歸正則化模型來求解其初始值，相應(yīng)的目標(biāo)函數(shù)如下計(jì)算其對(duì)應(yīng)的qi∈Q和 hi∈H。

for j=1…T/b：

（2）計(jì)算y(i)的稀疏表示xi。

（3）根據(jù)xi中非零值的位置，得到索引集合Ai，并計(jì)算輔助變量φ1和φ2。

（4）選擇學(xué)習(xí)率ρi=min(ρ，ρi0/i)。

（5）通過公式更新參數(shù)D，A，W

end for

end for

4）使用OMP算法，利用字典D構(gòu)建測(cè)試信號(hào)Y2的稀疏表示矩陣C∈RM×N，使得Y=D C。

5）構(gòu)建矩陣A=|C|，計(jì)算度矩陣D1和D2，求得矩陣

6）使用SVD奇異值分解算法計(jì)算矩陣An的前[logm2]個(gè)左右奇異向量和

8）對(duì)logm2維數(shù)據(jù)集Z進(jìn)行K-means［13］聚類，聚類標(biāo)簽的最后N行是測(cè)試信號(hào)Y2的聚類結(jié)果。

在增量式字典訓(xùn)練算法中，使用的字典訓(xùn)練模型與LSC算法類似，但求解最優(yōu)化的方式不同，使用增量式算法每次讀取一小批信號(hào)來訓(xùn)練字典，并用梯度下降算法更新最優(yōu)參數(shù)，由于梯度下降算法擁有較快的尋優(yōu)速度，因此增量式字典訓(xùn)練算法在保證字典判別性的同時(shí)，減少了字典訓(xùn)練的耗時(shí)。

3增量DBSCAN聚類算法

DBSCAN［4］是代表性的基于密度的聚類算法，其顯著優(yōu)點(diǎn)是聚類速度快且能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類。然而，此算法［16］每次只能孤立地處理一個(gè)更新，存在太多的冗余操作，從而增量聚類的效率很低。為了克服上述缺點(diǎn)，本文提出一種支持批量更新的改進(jìn)算法，該算法利用基于密度的聚類特性來提高增量聚類的效率。

·ε鄰域：以對(duì)象p為中心，ε為半徑的空間，其中ε＞0；

·核心對(duì)象：如果對(duì)象p的ε鄰域內(nèi)的樣本數(shù)大于等于Minpts，則稱p為核心對(duì)象；

·直接密度可達(dá)：如果對(duì)象p在核心對(duì)象k的ε鄰域內(nèi)，則p是從k直接密度可達(dá)的；

·密度可達(dá)：存在對(duì)象鏈p1，p2，…，pn，pi+1是從pi直接密度可達(dá)，則pn從p1密度可達(dá)；

假設(shè)D為對(duì)象集合，p為插入或移除的對(duì)象，

分別表示對(duì)象插入和移除操作，Near(x)表示x的鄰域?qū)ο?，n與x均為核心對(duì)象。

在批量模式中，無論插入還是移除對(duì)象p時(shí)，都會(huì)影響其ε鄰域?qū)ο竺芏?。插入?duì)象時(shí)，可能會(huì)出現(xiàn)噪聲、新的聚類、歸入某一聚類、合并相鄰聚類等影響；而移除對(duì)象時(shí)，可能會(huì)出現(xiàn)噪聲、聚類撤銷、聚類對(duì)象減少、分裂聚類等影響。因此，下文依次闡述支持批量更新是對(duì)象插入和對(duì)象移除的方法。

假設(shè)批量插入對(duì)象集合為InsList。對(duì)象插入的處理過程如下：

1：forall p in InsList

2：If InsNod es(p)=φand Near(p)內(nèi)無核心對(duì)象then p→噪聲

3：If核心對(duì)象in InsNodes(p)且不與任一聚類核心對(duì)象密度可達(dá)

4：then創(chuàng)建新聚類

5：If核心對(duì)象in InsNod es(p)均屬于同一個(gè)聚類，then將p歸入此聚類中

6：If核心對(duì)象in InsNod es(p)不屬于同一個(gè)聚類，且互相密度可達(dá)，

7：then合并這些聚類

8：end for

批量插入新對(duì)象時(shí)，算法以插入對(duì)象為核心點(diǎn)進(jìn)行擴(kuò)充，尋找從該對(duì)象出發(fā)的所有密度可達(dá)的數(shù)據(jù)點(diǎn)，與InsList順序無關(guān)，因此能較快發(fā)現(xiàn)新聚類中的對(duì)象，減少了聚類合并的處理。聚類合并時(shí)，算法也能快速發(fā)現(xiàn)不同聚類間的核心對(duì)象，減少了部分不必要的聚類生成再合并的處理，提高了聚類合并的效率。批量插入模式中，算法只需檢索一次插入對(duì)象，避免了更新對(duì)象的重復(fù)檢索。

刪除對(duì)象時(shí)，由于待刪除對(duì)象具有聚類的標(biāo)識(shí)，可能會(huì)對(duì)原聚類產(chǎn)生影響，例如引起聚類分裂，此時(shí)處理方法為：記錄下密度不可達(dá)的點(diǎn)，找出所有可能引起分裂的核心對(duì)象后，再選擇任一核心對(duì)象檢索其密度可達(dá)對(duì)象，最終求出對(duì)象的直接密度可達(dá)對(duì)象。該方法最多檢索一遍聚類中的對(duì)象，就可得到聚類最后的分裂情況，提高了增量聚類的效率。

假設(shè)待刪除對(duì)象集合為DelList，其具體處理過程是：

1：從DelList中選取屬于同一個(gè)聚類的一組對(duì)象，設(shè)為S

2：forall p in S

3：If DelNodes(p)≠φand DelNod es(p)內(nèi)對(duì)象彼此不能直接密度可達(dá)

4：then從對(duì)象集選取代表點(diǎn)加入到d_link

5：If p in d_link

6：if p有直接密度可達(dá)核心對(duì)象and D為p的直接密度可達(dá)核心對(duì)象集合

7：then從D中選擇任一對(duì)象替換p

8：else delete p from d_link（p直接密度可達(dá)的對(duì)象變?yōu)樵肼暎?/p>

9：end for

10：while d_link≠φ（刪除對(duì)象p）

11：p=pop（d_link）p加入到分裂后形成的聚類Q R為p的密度可達(dá)對(duì)象集合

12：for q in R

13：ifq in d_link

14：then delete q and Q=Q+｛q｝

15：End for

16：end while

假設(shè)算法已有N個(gè)對(duì)象，增量插入M個(gè)對(duì)象時(shí)，原算法可能需要檢索M次已有對(duì)象集，時(shí)間復(fù)雜度為O（N*M），而以上算法的處理思路最多檢索一遍已有對(duì)象集即可得到最終分裂結(jié)果，時(shí)間復(fù)雜度為O（N），算法時(shí)間復(fù)雜度大大降低，提高了增量聚類的效率，同時(shí)該算法也消除了一些刪除對(duì)象的多余的密度可達(dá)關(guān)系的檢索。

4基于聚類融合的增量聚類算法

為了避免使用單一聚類算法的局限性，本文設(shè)計(jì)一種組合聚類分析算法，并以改進(jìn)的子空間聚類算法和DBSCAN聚類算法作為基聚類算法，設(shè)計(jì)基于投票策略的共識(shí)函數(shù)實(shí)現(xiàn)不同聚類結(jié)果融合，綜合利用了不同聚類算法的優(yōu)點(diǎn)，從不同角度對(duì)空間樣本進(jìn)行全方位的聚類。

聚類融合是指將多個(gè)聚類算法或者同一個(gè)聚類算法不同參數(shù)下得到的聚類成員進(jìn)行合并，其可形式化地表述為：假設(shè)有n個(gè)數(shù)據(jù)點(diǎn)x= {x1，x2，x3，…，xn}，對(duì)數(shù)據(jù)集x使用H個(gè)聚類算法或用一個(gè)聚類算法運(yùn)行H次得到H個(gè)聚類成員，H={h1，h2，h3，…，hH}，其中hk(k=1，2，3，…，H)為對(duì)第k次聚類結(jié)果，然后設(shè)計(jì)一種有效的共識(shí)函數(shù)，將H個(gè)聚類成員的聚類結(jié)果進(jìn)行合并，得到聚類融合的結(jié)果，具體過程如圖1所示。

圖1 聚類融合過程

聚類融合［19～20］技術(shù)主要分為兩個(gè)階段：1）產(chǎn)生n個(gè)具有差異性的聚類結(jié)果，本文中主要采用兩種改進(jìn)的聚類算法，對(duì)同一個(gè)數(shù)據(jù)集進(jìn)行多次聚類得到；2）設(shè)計(jì)有效的共識(shí)函數(shù)，對(duì)聚類成員進(jìn)行集成得到聚類結(jié)果。下面重點(diǎn)介紹共識(shí)函數(shù)的設(shè)計(jì)。

目前常用的共識(shí)函數(shù)構(gòu)造方法主要有信息論方法、投票法、共聯(lián)矩陣法、超圖法和混合模型法等。本文采用基于投票策略的聚類融合策略，如算法2所示。

算法2：基于投票策略的聚類融合

輸入：數(shù)據(jù)集S，異常簇記錄數(shù)閾值θ，異常次數(shù)閾值λ

輸出：異常集OS

1：初始化la［N］=0 j=0

2：while j＜h do

3：采用LSC/DBSCAN作為基聚類算法，生成簇集合C={C1，C2，…，Cw}

4：l=0

5：while l＜w do

6：if|Cl|＜θ

7：then Cl被標(biāo)記為候選異常

8：?pi∈Cl(i∈[1，N])

9：la[i-1]++

10：end if

11：l++

12：end while

13：i=0，OS=?

14：while i＜N do

15：if la[i]＞λ

16：then pi被標(biāo)記為真正的異常，O S=OS∪{pi}

17：end if

18：end while

其中，N表示記錄總數(shù)，h表示融合次數(shù)，元素la[i](i∈1，N)表示在h次不同劃分中對(duì)象pi被標(biāo)記為異常的次數(shù)。以子空間聚類算法和DB?SCAN算法為基礎(chǔ)，對(duì)數(shù)據(jù)集進(jìn)行多次聚類，將每次聚類形成的簇集合中包含對(duì)象數(shù)小于閾值θ的簇所有對(duì)象都作為候選異常點(diǎn)，統(tǒng)計(jì)異常次數(shù)加1。最后，將多次檢測(cè)結(jié)果進(jìn)行融合，如果一個(gè)數(shù)據(jù)點(diǎn)的異常投票數(shù)超過異常閾值λ，這個(gè)數(shù)據(jù)點(diǎn)看作異常點(diǎn)。

5實(shí)驗(yàn)

本文選用KDD Cup99數(shù)據(jù)集進(jìn)行模型實(shí)驗(yàn)。該數(shù)據(jù)集是麻省理工學(xué)院提供的網(wǎng)絡(luò)入侵檢測(cè)評(píng)估測(cè)試數(shù)據(jù)集，被廣泛應(yīng)用于入侵檢測(cè)算法的檢驗(yàn)。數(shù)據(jù)集收集了9個(gè)星期網(wǎng)絡(luò)連接和系統(tǒng)審計(jì)數(shù)據(jù)，大約500萬條連接記錄。本次實(shí)驗(yàn)從KDD Cup99中隨機(jī)抽取40000條網(wǎng)絡(luò)連接記錄，分為四組數(shù)據(jù)子集test1，test2，test3，test4。每個(gè)測(cè)試集包含10000條網(wǎng)絡(luò)連接記錄，其中正常行為占90%，異常行為占10%。

為了評(píng)價(jià)和比較各種異常檢測(cè)方法的優(yōu)劣，需要利用相關(guān)的評(píng)價(jià)指標(biāo)體系來衡量。檢測(cè)率、誤報(bào)率，兩者是評(píng)價(jià)異常檢測(cè)最重要的指標(biāo)。兩者具體用公式描述為

即

標(biāo)準(zhǔn)化信息（Normalized Mutual information，NMI）常用在聚類中，度量?jī)蓚€(gè)聚類結(jié)果的相近程度。

為了驗(yàn)證改進(jìn)的子空間聚類算法的精度和運(yùn)行時(shí)間開銷，將改進(jìn)的增量子空間聚類與LSC算法進(jìn)行比較。在字典訓(xùn)練中，為了保證實(shí)驗(yàn)的隨機(jī)性，實(shí)驗(yàn)中隨機(jī)選取m=2，…，8類，即m個(gè)尺度劃分，每個(gè)類別選取T=60個(gè)信號(hào)構(gòu)成包含T*m列的訓(xùn)練數(shù)據(jù)集，用于字典訓(xùn)練，剩余的信號(hào)構(gòu)成測(cè)試數(shù)據(jù)集，用于測(cè)試。每個(gè)類別實(shí)驗(yàn)重復(fù)40次，統(tǒng)計(jì)兩種聚類算法的整體耗時(shí)和聚類精度，實(shí)驗(yàn)結(jié)果如圖2，圖3所示，增量LSC相比LSC不同類簇之間區(qū)分度更明顯，聚類效果更好，還能保證較快的運(yùn)行速度。

即

圖2 NMI值

圖3 算法耗時(shí)

我們將本文提出的批量模式的DBSCAN與非批量的增量聚類進(jìn)行比較。實(shí)驗(yàn)每個(gè)測(cè)試集選取2000個(gè)對(duì)象進(jìn)行DBSCAN聚類，然后模擬數(shù)據(jù)流批量插入新數(shù)據(jù)，進(jìn)行增量聚類。如圖4所示，可以看出批量模式處理效率高于非批量模式，特別是隨著數(shù)據(jù)的不斷插入，當(dāng)形成新聚類時(shí)或發(fā)生聚類合并時(shí)批量模式速度優(yōu)勢(shì)更明顯，與預(yù)期結(jié)果相符合。

圖4 算法耗時(shí)

為了驗(yàn)證本文提出的模型聚類效果優(yōu)于單一聚類算法，將組合模型的聚類結(jié)果與單獨(dú)使用子空間聚類算法和DBSCAN算法的聚類結(jié)果進(jìn)行了比較。為了保證實(shí)驗(yàn)的正確性，針對(duì)每個(gè)模型每個(gè)測(cè)試子集進(jìn)行了10次實(shí)驗(yàn)，如圖5和圖6所示。

圖5 10次實(shí)驗(yàn)檢測(cè)率平均值

圖6 10次實(shí)驗(yàn)誤報(bào)率平均值

從圖5和圖6可以看出，組合模型算法檢測(cè)率較高，誤報(bào)率較低，且對(duì)不同數(shù)據(jù)集的檢測(cè)率穩(wěn)定，使用子空間聚類、密度聚類算法進(jìn)行數(shù)據(jù)集的組合聚類分析，能夠在不改變?cè)袛?shù)據(jù)屬性的情況下，通過多次和多角度的聚類，有效提高入侵行為的檢測(cè)率。

6結(jié)語

鑒于傳統(tǒng)增量聚類算法存在的不足，本文將聚類融合方法引入數(shù)據(jù)流增量聚類中，提出了基于聚類融合的數(shù)據(jù)流異常檢測(cè)方法，以避免由單一聚類帶來的局限性和隨機(jī)性的缺點(diǎn)。該算法由子空間聚類算法和DBSCAN聚類算法產(chǎn)生聚類成員，采用聚類融合方法進(jìn)行融合，從而獲得聚類的結(jié)果。通過對(duì)KDD數(shù)據(jù)集進(jìn)行實(shí)例分析，表明了改進(jìn)的組合增量聚類算法能夠改善單一聚類不穩(wěn)定性和隨機(jī)性，具有很好的聚類效果。

［1］Aggarwal C C，Yu P S.A Framework for Clustering Uncer?tain Data Streams［C］//IEEE，International Conference on Data Engineering.IEEE，2008：150-159.

［2］朱林，雷景生，畢忠勤，等.一種基于數(shù)據(jù)流的軟子空間聚類算法［J］.軟件學(xué)報(bào)，2013（11）：2610-2627.

ZHU Lin，LEI Jingsheng，BI Zhongqin，et al.Soft Sub? space Clustering Algorithm for Streaming Data［J］.Journal of Software，2013（11）：2610-2627.

［3］Adler A，Elad M，Hel-Or Y.Probabilistic Subspace Clus?tering Via Sparse Representations［J］.IEEE Signal Pro?cessing Letters，2013，20（1）：63-66.

［4］Ester M，Kriegel H P，Sander J，et al.Incremental Clus?tering for Mining in a Data Warehousing Environment［C］//VLDB'98，Proceedings of，International Conference on Very Large Data Bases，August 24-27，1998，New York City，New York，USA.1998：323-333.

［5］Ller E，Nnemann S，Assent I，etal.Evaluating clustering in subspace projections of high dimensional data［J］.Pro?ceedings of the VLDB Endowment，2009，2（1）：1270-1281.

［6］Kriegel H P，Ger P，Zimek A.Clustering high-dimension?al data：A survey on subspace clustering，pattern-based clustering，and correlation clustering［J］.ACM Transac?tions on Knowledge Discovery from Data，2009，3（1）：337-348.

［7］Karimian S H，Kelarestaghi M，Hashemi S.I-IncLOF：Im?proved incremental local outlier detection for data streams［M］.2012.

［8］蔣盛益，楊博泓，王連喜.一種基于增量式譜聚類的動(dòng)態(tài)社區(qū)自適應(yīng)發(fā)現(xiàn)算法［J］.自動(dòng)化學(xué)報(bào)，2015（12）：2017-2025.

JIANG Shengyi，YANG Bohong，WANG Lianxi.An Adap?tive Dynamic Community Detection Algorithm Based on Incremental Spectral Clustering［J］.Acta Automatica Sini?ca，2015（12）：2017-2025.

［9］李桃迎，陳燕，秦勝君，等.增量聚類算法綜述［J］.科學(xué)技術(shù)與工程，2010（35）：8752-8759.

LI Taoying，CHEN Yan，Qin Shengjun，etal.Review of In?cremental Clustering Algorithm［J］.Science Technology and Engineering，2010（35）：8752-8759.

［10］劉展杰，陳曉云.局部子空間聚類［J］.自動(dòng)化學(xué)報(bào)，2016，42（8）：1238-1247.

LIU Zhanjie，CHEN Xiaoyun.Local Subspace Clustering［J］.Journal of Automatica Sinica，2016，42（8）：1238-1247.

［11］李艷紅，李德玉，崔夢(mèng)天，等.基于數(shù)據(jù)流的網(wǎng)絡(luò)入侵實(shí)時(shí)檢測(cè)框架［J］.計(jì)算機(jī)應(yīng)用，2015，35（2）：416-419.

LI Yanhong，LI Deyu，CUI Mengtian，et al.Real-time Detection Framework for Network Intrusion Based on Da?ta Stream［J］.Computer Application，2015，35（2）：416-419.

［12］Akter M，Rahman M O，Islam M N，et al.Incremental clustering-based object tracking in wireless sensor net?works［C］//International Conference on NETWORKING Systems and Security.IEEE，2015：1-6.

［13］Jonathan D A S，Hruschka E R.Extending k-Means-Based Algorithms for Evolving Data Streams with Variable Number of Clusters［C］//International Con?ference on Machine Learning and Applications and Workshops.IEEE Computer Society，2011：14-19.

［14］耿志強(qiáng)，姬威，韓永明，等.基于維度最大熵?cái)?shù)據(jù)流聚類的異常檢測(cè)方法［J］.控制與決策，2016（2）：343-348.

GENG Zhiqiang，JI Wei，HAN Yongming，et al.Data Stream Clustering Algorithm Based on the Maximum En?tropy of Data Dimension and its Applications for Anoma?ly Detection［J］.Control and Decision，2016（2）：343-348.

［15］Sommer R，Paxson V.Outside the Closed World：On Us?ing Machine Learning for Network Intrusion Detection［C］//Security and Privacy.IEEE，2010：305-316.

［16］Patwary M M A，Palsetia D，Agrawal A，et al.A new scalable parallel DBSCAN algorithm using the dis?joint-setdata structure［C］//SC Conference，2012：1-11.

［17］Elhamifar E，Vidal R.Clustering disjoint subspaces via sparse representation［C］//Acoustics Speech and Signal Processing（ICASSP），2010 IEEE International Confer?ence on.IEEE，2010：1926-1929.

［18］Feng J，Lin Z，Xu H，etal.Robust Subspace Segmenta?tion with Block-Diagonal Prior［J］.2014：3818-3825.

［19］周林，平西建，徐森，等.基于譜聚類的聚類集成算法［J］.自動(dòng)化學(xué)報(bào)，2012（8）：1335-1342.

ZHOU Lin，PING Xijian，XU Sen，et al.Cluster Ensem?ble Based on Spectral Clustering［J］.Acta Automatica Si?nica，2012（8）：1335-1342.

［20］李桃迎，陳燕，張金松，等.基于聚類融合的混合屬性數(shù)據(jù)增量聚類算法［J］.控制與決策，2012（4）：603-608.

LI Taoying，CHEN Yan，ZHANG Jinsong，et al.Incre?mental Clustering Algorithm of Mixed Numericaland Cat?egorical Data Based on Clustering ensemble［J］.Control and Decision，2012（4）：603-608.

Research on Data Stream Amonaly Detection Using Incremental Clustering Ensemble

XU Fu XU Jian
（Schoolof Computer Science and Engineering，Nanjing University ofScience and Technology，Nanjing 210094）

Anomaly detection in data stream has gained a high attraction due to its applications，including real-time surveil?lance，network intrusion detection.However，traditionalclustering is no longer suitable due to the particularity and timeliness ofthe data stream and the continuous characteristics of the data flow.Therefore，incremental clustering has become the research hotspots towards anomaly detection in data stream.An anomaly detection modelin data stream is proposed based on two improved incremen?tal clustering aiming at the problem of low efficiency，high false positives and lack of pertinence of single clustering.The mothod is based on improved incrementalclustering and an effective consensus function is designed to merge the results ofa variety ofcluster?ing algorithms.The experimental results show that the improved clustering algorithms are applicable to incremental clustering and they have better efficiency and better clustering resultthan single clustering method.

data stream，anomaly detection，incrementalclustering，subspace clustering，clustering ensemble

TP391

10.3969/j.issn.1672-9722.2017.08.003

2017年3月19日，

2017年4月23日

國家自然科學(xué)基金項(xiàng)目“虛擬計(jì)算環(huán)境下的軟件自愈機(jī)理和方法研究”（編號(hào)：61300053）資助。

許福，男，碩士，研究方向：數(shù)據(jù)挖掘。徐建，副教授，博士，研究方向：數(shù)據(jù)挖掘。