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

有效

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

1.一種檢測數據序列中的異常子序列的方法，所述數據序列包括要檢測的目標子序列和第一數量的參考子序列，所述方法包括：

構造目標子序列的分層數據結構，所述分層數據結構的最底層的每個節點存儲目標子序列的對應數據，最底層之上的層的每個節點存儲基于在本層的下一層的對應節點中存儲的數據導出的值；

基于所述目標子序列的分層數據結構以及預先構造的所述第一數量的參考子序列的分層數據結構，確定目標子序列的第二數量的鄰居，所述目標子序列的第二數量的鄰居是所述第一數量的參考子序列中、與目標子序列的歐幾里德距離最小的第二數量的參考子序列；

確定所述第二數量的參考子序列中的每個參考子序列的第三數量的鄰居，其中所述第三數量的鄰居是所述數據序列中、與所述每個參考子序列的歐幾里德距離最小的第三數量的子序列；以及

根據目標子序列的第二數量的鄰居、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列的第三數量的鄰居，確定所述目標子序列是否為異常子序列。

2.如權利要求1所述的方法，其中，所述分層數據結構是二叉樹。

3.如權利要求1或2所述的方法，其中，所述最底層之上的層的每個節點存儲的、基于在本層的下一層的對應節點中存儲的數據導出的值是所述對應節點中存儲的數據的平均值、最大值和最小值，并且其中，所述基于目標子序列的分層數據結構以及預先構造的所述第一數量的參考子序列的分層數據結構，確定目標子序列的第二數量的鄰居包括：

從目標子序列和所述第一數量的參考子序列的分層數據結構的最上層開始，分別基于所述分層數據結構的一層或多層上的節點中存儲的數據或值，計算與所述一層或多層對應的、目標子序列與各個參考子序列之間的歐幾里德距離的上限值和下限值，并且基于所述上限值和下限值確定目標子序列的鄰居，直到確定目標子序列的第二數量的鄰居為止。

4.如權利要求3所述的方法，其中，所述基于所述上限值和下限值確定目標子序列的鄰居包括：

響應于目標子序列與所述第一數量的參考子序列中的一個參考子序列之間的歐幾里德距離的上限值小于目標子序列與所述第一數量的參考子序列中的其他參考子序列之間的歐幾里德距離的下限值，將所述一個參考子序列確定為目標子序列的鄰居。

5.如權利要求4所述的方法，其中，所述第三數量與所述第二數量相同，并且其中，根據目標子序列的第二數量的鄰居、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列的第三數量的鄰居，確定所述目標子序列是否為異常子序列包括：

根據目標子序列與其第二數量的鄰居之間的接近程度、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列與其第三數量的鄰居之間的接近程度，確定所述目標子序列是否為異常子序列。

6.如權利要求5所述的方法，其中，所述根據目標子序列與其第二數量的鄰居的接近程度、以及所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列與其第三數量的鄰居的接近程度，確定所述目標子序列是否為異常子序列包括：

計算所述目標子序列與其第二數量的鄰居之間的歐幾里德距離的平均值的倒數，以確定目標子序列與該目標子序列的第二數量的鄰居的接近程度；

計算所述第二數量的參考子序列中以所述目標子序列為其鄰居的每個參考子序列與其第三數量的鄰居之間的歐幾里德距離的平均值的倒數；

計算與所述第二數量的參考子序列中以所述目標子序列為其鄰居的各個參考子序列對應的平均值的倒數的平均值，以確定所述第二數量的參考子序列中以所述目標子序列為其鄰居的參考子序列與其第三數量的鄰居的接近程度；以及

基于所述目標子序列與其第二數量的鄰居之間的歐幾里德距離的平均值的倒數、以及與所述第二數量的參考子序列中以所述目標子序列為其鄰居的各個參考子序列對應的平均值的倒數的平均值，確定所述目標子序列是否為異常子序列。