[發明專利]一種支持動態更新的在線屬性異常點檢測方法

有效

• 申請號: 201010237922.6
• 申請日: 2010-07-27
• 公開（公告）號: CN101908065A
• 公開（公告）日: 2010-12-08
• 發明（設計）人: 陳剛;壽黎但;胡天磊;陳珂;曹暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林懷禹

1.一種支持動態更新的在線屬性異常點檢測方法，其特征在于該方法的步驟如下：

(1)選取符合流數據系統在數據生成、檢測方式和用戶需求三方面的要求的數據模型維護持續動態更新的流數據；

(2)使用在線聚類方法對流數據進行持續動態聚類，實現基于數據屬性相關性的聚類劃分；

(3)動態維護流數據更新下的聚類劃分，并持續更新數據點之間的鄰居關系和距離信息，在線維護聚類相關信息，隨著數據的動態更新保持維護相關概要信息結構；

(4)建立數據降載方法，根據流數據系統中實際負載以及對實時性的要求，選取能夠達到流數據系統實時性要求的降載方法以及近似技術保證檢測方法的實時完成，并能保證最后近似結果的誤差可控；

(5)根據聚類劃分及數據點鄰居兩方面相關數據信息及屬性異常點評價方法，在每個聚類劃分中檢測異常點作為最終屬性異常點結果輸出。

2.根據權利要求1所述的一種支持動態更新的在線屬性異常點檢測方法，其特征在于：所述步驟(1)選取符合流數據系統在數據生成、檢測方式和用戶需求三方面的要求的數據模型維護持續動態更新的流數據，該步驟選取的數據模型需要滿足能夠快速高效維護數據動態更新，滿足在主流應用服務器部署實施，因此采用當前業內主流應用模型滑動窗口模型，對于流數據僅保存并保持更新最近一部分作為滑動窗口，并基于當前最新窗口進行查詢處理。

3.根據權利要求1所述的一種支持動態更新的在線屬性異常點檢測方法，其特征在于：所述步驟(2)使用在線聚類方法對流數據進行持續動態聚類，此線聚類方法需要對持續更新的流數據進行動態聚類劃分，并且針對流數據內容漂移的特性，在線聚類方法能夠始終維護保持反映最新數據內容的聚類劃分狀態；方法的具體實施包含以下內容：

1)在流數據更新之前建立初始化聚類劃分，在初始化階段對當前滑動窗口內數據進行聚類，并利用計算數據點之間幾何距離來衡量數據之間的屬性相關性，根據數據點間距離聚集相似、相關數據形成初始的聚類劃分；

2)建立簡潔的時間聚類特征數據結構維護聚類劃分概要信息，描述每個劃分的關鍵特征，能夠根據概要信息還原聚類的中心以及劃分范圍半徑；

3)針對動態更新的流數據在線維護聚類劃分，流數據系統中每一時刻都有大量新生成數據到達，在線聚類方法需要實時的對這些新數據進行聚類，即時完成對劃分的更新；

4)對時間聚類特征切片維護，實現聚類信息的動態更新，在完成對新生成數據的動態聚類后，需要及時更新聚類特征概要信息，由于采用滑動窗口模型，數據不斷更新，產生新數據的同時大量陳舊數據需要過期，因此在對新數據聚類的同時還需要消除過期數據的概要信息；

5)根據在線聚類劃分總數，進行必要的聚類合并操作保持聚類結果的質量以及總數的穩定；由于采用的聚類方法的特點，以及流數據不斷生成的大量全新數據點，滑動窗口內將出現大量的微型聚簇，這些微型劃分會嚴重降低最終聚類結果質量，同時將會占用大量內存，消耗系統資源，因此需要進行聚類合并。

4.根據權利要求1所述的一種支持動態更新的在線屬性異常點檢測方法，其特征在于：所述步驟(3)動態維護流數據更新下的聚類劃分，并持續更新數據點之間的鄰居關系和距離信息，需要在線維護后續異常點檢測步驟中所需要的數據相關信息，采用基于距離的度量來計算數據點間的相關性以及檢測異常點，因此對于每個數據點需要計算在在其指定距離領域內的鄰居數目，當鄰居總數低于用戶指定閾值時，則說明該數據點異常，另外由于屬性異常點的特點實際檢測過程發生在每個獨立的聚類劃分中，所以在數據相關信息的維護過程中對每個聚類僅需維護更新其內部數據點相關信息。

5.根據權利要求1所述的一種支持動態更新的在線屬性異常點檢測方法，其特征在于：所述步驟(3)在線維護聚類相關信息，隨著數據的動態更新保持維護相關概要信息結構，在線維護過程中還需要針對動態更新的流數據對鏈表進行動態維護更新操作，具體步驟包括：

1)對于剛進入聚類的新數據點，生成對應節點加入鏈表尾部，接下來對鏈表進行反向遍歷，計算各個前序節點與新節點的距離及鄰居關系；

2)隨著滑動窗口的滑動，將過期數據對應節點由鏈表中移除，保證之后檢測過程中在其后序鄰居的前向鄰居數組中節點號為無效；

3)在發生聚類合并操作后，同時需要合并兩個聚類的鏈表及更新節點信息。