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

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

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

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

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

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

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

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

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

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