基于聚類的異常挖掘算法研究.pdf

1、在網(wǎng)絡(luò)、金融、氣象、醫(yī)學(xué)、保險和電信等眾多應(yīng)用領(lǐng)域，稀有的、特殊的異常數(shù)據(jù)往往代表一種偏差或者新模式的開始，對這些異常數(shù)據(jù)的識別比對正常數(shù)據(jù)的分析更有價值，可從新的視角開啟新的理論，從而帶來新的應(yīng)用。從數(shù)據(jù)分析的角度而言，識別這些異常數(shù)據(jù)就需要相應(yīng)的異常挖掘算法。隨著應(yīng)用日益廣泛以及數(shù)據(jù)不斷積累，異常挖掘需處理的數(shù)據(jù)量越來越大，應(yīng)用環(huán)境也越來越復(fù)雜。已存在方法主要針對中、小規(guī)模數(shù)值屬性數(shù)據(jù)集，面對大規(guī)?；旌蠈傩詳?shù)據(jù)集和動態(tài)數(shù)據(jù)流時，算法

2、的可擴(kuò)展性、時效性及準(zhǔn)確性都難以滿足實(shí)際應(yīng)用的需求。
　　 在模式識別領(lǐng)域，異常挖掘可看作是一種特殊的分類問題。作為無監(jiān)督模式識別的一個重要分支，聚類具有不需要任何先驗(yàn)知識的特性，比較適合面向大規(guī)模數(shù)據(jù)集的異常挖掘。因此，基于聚類的異常挖掘得到了廣泛研究，提出了許多有效的異常挖掘算法，但仍有許多問題尚待研究和解決。本文主要針對已有異常挖掘算法存在的不足，從不同角度研究了基于聚類的異常挖掘算法。
　　 目前，已有基于聚類的

3、異常挖掘算法大多直接將聚類形成的小簇作為異常，由于采用的類球形聚類算法限制，有些小簇可能是任意形狀正常簇的邊界，從而導(dǎo)致較高的FR(FalsePositiveRate)。為了提高挖掘結(jié)果的準(zhǔn)確性，研究任意形狀聚類對異常挖掘來說具有非常重要的意義。本文首先介紹了兩種任意形狀聚類算法OBASC和EASSC。算法OBASC針對小規(guī)模數(shù)據(jù)集，根據(jù)提出的可兼顧分類屬性取值頻率差異與頻率高低的差異性度量方式，僅需輸入一個近鄰閾值參數(shù)就可發(fā)現(xiàn)任意形狀

4、的簇;增強(qiáng)的譜聚類算法EASSC使用改進(jìn)的高斯核函數(shù)作為簇間相似性度量，可處理大規(guī)模高維變密度數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果表明算法OBASC和EASSC聚類精度高，適用于混合屬性數(shù)據(jù)集中任意形狀聚類。這兩種算法為設(shè)計(jì)高效的異常挖掘奠定了基礎(chǔ)，但參數(shù)確定困難，必須經(jīng)過多次試探。為減少用于預(yù)處理的聚類算法對用戶的依賴，本文提出了基于聚類融合的異常挖掘算法CEBOM，將任意形狀聚類算法中的一種——OBASC作為基礎(chǔ)聚類算法，對較大范圍內(nèi)不同閾值下得到的候

5、選異常進(jìn)行融合，識別真正的異常。實(shí)驗(yàn)結(jié)果表明，CEBOM算法可降低直接將小簇作為異常的高FR，并且能提供給用戶更為“友好”的操作。
　　 基于任意形狀聚類的異常挖掘雖然可有效檢測到異常數(shù)據(jù)，但時間復(fù)雜度較高。在內(nèi)存有限的情況下，處理大規(guī)模數(shù)據(jù)集需要頻繁的內(nèi)外存數(shù)據(jù)交換，從而導(dǎo)致難以容忍的時空復(fù)雜度。針對此種問題，本文提出了兩種面向大規(guī)?；旌蠈傩詳?shù)據(jù)集的異常挖掘算法ICBOM和SNNOM。算法ICBOM在對原始數(shù)據(jù)集增量聚類的基礎(chǔ)

6、上，過濾掉大量正常數(shù)據(jù)，根據(jù)提出的異常簇定義識別數(shù)據(jù)集中的邊界異常和內(nèi)部異常，同時探討了算法中的參數(shù)取值;算法SNNOM計(jì)算增量聚類結(jié)果簇間的共享最近鄰相似度，不但能夠發(fā)現(xiàn)任意形狀的簇，還可挖掘到變密度數(shù)據(jù)集中的全局異常。理論分析與實(shí)驗(yàn)結(jié)果表明，這兩種算法關(guān)于數(shù)據(jù)集的大小和屬性個數(shù)呈近似線性時間復(fù)雜度，較之同類算法具有更高的DR(DetectionRate)以及較低的FR。
　　 算法CEBOM、ICBOM和SNNOM挖掘到的都

7、是全局異常，但由于現(xiàn)實(shí)世界復(fù)雜多變，所獲得的數(shù)據(jù)集往往不完整，特別是在動態(tài)數(shù)據(jù)流環(huán)境下，數(shù)據(jù)具有時間特性，且不斷流逝，由此基于“在線聚類、離線異常挖掘”的思想，提出了兩種不同模型下的混合屬性數(shù)據(jù)流異常挖掘算法DMDSOM和SWMSOM。算法DMDSOM基于衰減模型，在線維護(hù)具有時間維的簇特征。異常挖掘階段僅計(jì)算特定簇的整體偏離程度，是一種節(jié)省時間的策略;同時提出了一種可有效區(qū)分異常簇與數(shù)據(jù)進(jìn)化初始階段的方法，半徑閾值動態(tài)改變。算法SWM

8、SOM基于滑動窗口模型，使用宏簇與帶時間戳的微簇增量聚類數(shù)據(jù)流，始終維護(hù)W個時間單位的宏簇。當(dāng)接收到檢測請求時，計(jì)算特定宏簇的多粒度偏差因子并按降序排列。理論分析與實(shí)驗(yàn)結(jié)果表明，這兩種算法在線建立模型時具有近似線性時間復(fù)雜度，內(nèi)存開銷較小，可有效挖掘到混合屬性數(shù)據(jù)流中的局部異常，是對現(xiàn)有異常挖掘算法的有益補(bǔ)充和改進(jìn)。
　　 作為異常挖掘的一類實(shí)際應(yīng)用領(lǐng)域，入侵檢測中的正常行為和入侵行為彼此分離，同樣可采用聚類技術(shù)來解決。本文提出

9、了一種基于半監(jiān)督人工免疫聚類的入侵檢測算法，定義了混合屬性抗原與抗體間的差異度，結(jié)合半監(jiān)督學(xué)習(xí)僅使用少量標(biāo)記數(shù)據(jù)的指導(dǎo)作用對訓(xùn)練集進(jìn)行人工免疫聚類，建立分類模型，依據(jù)模型分類測試集，檢測入侵行為。動態(tài)增長的網(wǎng)絡(luò)數(shù)據(jù)因具有高速、無窮到達(dá)的特點(diǎn)，可看作數(shù)據(jù)流，因此又提出一種可用于混合屬性數(shù)據(jù)流的入侵檢測算法，在界標(biāo)模型下增量聚類數(shù)據(jù)流，對結(jié)果簇進(jìn)行加權(quán)模糊聚類，依據(jù)隸屬度矩陣的最大隸屬原則，將正常行為與入侵行為區(qū)分開來。實(shí)驗(yàn)結(jié)果進(jìn)一步表明，