[發明專利]檢測數據序列中的異常子序列的方法和設備

有效

• 申請號: 201410040085.6
• 申請日: 2014-01-27
• 公開（公告）號: CN104809134B
• 公開（公告）日: 2018-03-09
• 發明（設計）人: 劉凱;陳垚亮;陳曉艷;黃勝;王晨
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市柳沈律師事務所11105
• 代理人: 于小寧

技術領域

本發明涉及異常數據檢測，并且更具體地涉及一種檢測數據序列中的異常子序列的方法和設備。

背景技術

在物聯網（IOT）或智慧地球等的場景中，通過某種數據產生機制，可以隨著時間不斷地產生數據，從而形成時間數據序列。例如，在使用檢測器檢測大氣污染物的場景中，檢測器隨著時間不斷地輸出數據，從而形成反映各個時刻的大氣污染水平的時間數據序列。在時間數據序列中，可能有某些數據與其他數據偏離得很大，這樣的數據可以稱為異常數據。由于異常數據能夠反映數據產生機制存在的某種問題或者與該數據相關聯的對象的某些重要狀態，因此，檢測時間數據序列中的異常數據非常重要。

目前，已經提出了多種方法來檢測時間數據序列中的異常數據。在這些傳統方法中，在檢測時間數據序列中的某些數據是否異常時，需要使用該序列的全部數據，并且在檢測期間需要多次掃描整個時間數據序列，使得檢測操作的計算量非常大，并且需要花費很長的時間。此外，由于時間數據序列（特別是在較長的時間段內產生的時間數據序列）的全部數據在映射空間內的分布密度往往差異較大，因此如果基于全部數據的分布密度來檢測某些數據是否異常，可能會將分布密度與其他數據差異較大的正常數據認定為異常數據，使得結果不準確。而且，傳統方法只能對時間序列數據進行離線（非實時）檢測，而非在線（實時）檢測，這對于某些希望盡快獲得檢測結果的場景來說是不可接受的。

發明內容

本發明的目的是提供一種檢測數據序列中的異常子序列的方法和設備，其能夠實時且準確地檢測數據序列中的異常子序列，從而實時且準確地檢測數據序列中的異常數據。

根據本發明的一個方面，提供了一種檢測數據序列中的異常子序列的方法，所述數據序列包括要檢測的目標子序列和第一數量的參考子序列，所述方法包括：構造目標子序列的分層數據結構，所述分層數據結構的最底層的每個節點存儲目標子序列的對應數據，最底層之上的層的每個節點存儲基于在本層的下一層的對應節點中存儲的數據導出的值；基于所述目標子序列的分層數據結構以及預先構造的所述第一數量的參考子序列的分層數據結構，確定目標子序列的第二數量的鄰居，所述目標子序列的第二數量的鄰居是所述第一數量的參考子序列中、與目標子序列的歐幾里德距離最小的第二數量的參考子序列；確定所述第二數量的參考子序列中的每個參考子序列的第三數量的鄰居，其中所述第三數量的鄰居是所述數據序列中、與所述每個參考子序列的歐幾里德距離最小的第三數量的子序列；以及根據目標子序列的第二數量的鄰居、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列的第三數量的鄰居，確定所述目標子序列是否為異常子序列。

根據本發明的另一方面，提供了一種檢測數據序列中的異常子序列的設備，所述數據序列包括要檢測的目標子序列和第一數量的參考子序列，所述設備包括：構造裝置，被配置為構造目標子序列的分層數據結構，所述分層數據結構的最底層的每個節點存儲目標子序列的對應數據，最底層之上的層的每個節點存儲基于在本層的下一層的對應節點中存儲的數據導出的值；目標鄰居確定裝置，被配置為基于所述目標子序列的分層數據結構以及預先構造的所述第一數量的參考子序列的分層數據結構，確定目標子序列的第二數量的鄰居，所述目標子序列的第二數量的鄰居是所述第一數量的參考子序列中、與目標子序列的歐幾里德距離最小的第二數量的參考子序列；參考鄰居確定裝置，被配置為確定所述第二數量的參考子序列中的每個參考子序列的第三數量的鄰居，其中所述第三數量的鄰居是所述數據序列中、與所述每個參考子序列的歐幾里德距離最小的第三數量的子序列；以及異常檢測裝置，被配置為根據目標子序列的第二數量的鄰居、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列的第三數量的鄰居，確定所述目標子序列是否為異常子序列。

利用根據本發明上述方面的方法和設備，基于數據序列中受到目標子序列影響的參考子序列的數據，而不是基于數據序列的全部數據，來檢測目標子序列是否是異常子序列，從而可以減小檢測的計算量和所需時間，并且提高檢測的準確性。此外，對于隨著時間不斷產生的數據形成的時間數據序列，每當產生一個新的子序列時，就可以利用上述方法和設備檢測該子序列是否是異常子序列，從而可以實現在線（實時）檢測。

附圖說明

通過結合附圖對本公開示例性實施方式進行更詳細的描述，本公開的上述以及其它目的、特征和優勢將變得更加明顯，其中，在本公開示例性實施方式中，相同的參考標號通常代表相同部件。

圖1示出了適于用來實現本發明實施方式的示例性計算機系統/服務器12的框圖。