Detecting an abnormal subsequence in a data sequence

• US 9,552,243 B2
• Filed: 01/16/2015
• Issued: 01/24/2017
• Est. Priority Date: 01/27/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Xiao Yan, Chen, Yao Liang, Huang, Sheng, Liu, Kai, Wang, Chen
• Primary Examiner(s): KUDIRKA, JOSEPH R
• Application Number:
  US14/598,843
• Publication Number:
  US 20150212868A1
• Time in Patent Office: 739 Days
• US Class Current: 1/1
• CPC Class Codes: G05B 23/0232 based on qualitative trend analysis, e.g. system evolution
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06

Abstract

A method for detecting abnormal subsequences in data sequence includes constructing a hierarchical data structure of a target subsequence, each node in a bottommost layer of the data structure storing corresponding data of the target subsequence, and each node in a layer above the bottommost layer storing values based on data stored in corresponding nodes in a lower layer next to the layer above the bottommost layer; determining a second number of neighbors of the target subsequence based on the data structure of the target subsequence and of the first number of reference subsequences constructed in advance, the second number of neighbors having minimum Euclidean distances from the target subsequence; determining a third number of neighbors of each reference subsequence in the second number of reference subsequences, which have minimum Euclidean distances from each reference subsequence and determining whether the target subsequence is an abnormal subsequence.

Claims

1. An apparatus for detecting an abnormal subsequence in a data sequence, the data sequence including a target subsequence to be detected and a first number of reference subsequences, the apparatus comprising:

a constructing device, configured to construct a hierarchical data structure of the target subsequence, each node in a bottommost layer of the hierarchical data structure storing corresponding data of the target subsequence, and each node in a layer above the bottommost layer storing values derived based on data stored in corresponding nodes in a lower layer next to the layer above the bottommost layer;

a target neighbor determining device, configured to determine a second number of neighbors of the target subsequence based on the hierarchical data structure of the target subsequence and a pre-constructed hierarchical data structure of the first number of reference subsequences, the second number of neighbors of the target subsequence being a second number of reference subsequences, which have minimum Euclidean distances from the target subsequence, in the first number of reference subsequences;

a reference neighbor determining device, configured to determine a third number of neighbors of each reference subsequence in the second number of reference subsequences, the third number of neighbors being a third number of subsequences, which have minimum Euclidean distances from the each reference subsequence in the second number of reference subsequences, in the data sequence; and

an anomaly detecting device, configured to determine whether the target subsequence is an abnormal subsequence, according to the second number of neighbors of the target subsequence, and the third number of neighbors of a reference subsequence, which has the target subsequence as a neighbor thereof, in the second number of reference subsequences.

2. The apparatus of claim 1, wherein the hierarchical data structure is a binary tree.

3. The apparatus of claim 1, wherein the values stored by the each node in the layer above the bottommost layer and derived based on the data stored in the corresponding nodes in the lower layer next to the layer above the bottommost layer comprise an average value, a maximum value and a minimum value of the data stored in the corresponding nodes, and wherein the target neighbor determining device is configured to determine upper limit values and lower limit values of Euclidean distances between the target subsequence and respective reference subsequences, corresponding to one or more layers of the hierarchical data structure of the target subsequence and the first number of reference subsequences, based on the data or values stored in nodes in the one or more layers of the hierarchical data structure, respectively, starting from an uppermost layer of the hierarchical data structure, and determine the second number of the neighbors of the target subsequence on the basis of the upper limit values and the lower limit values, until the second number of neighbors of the target subsequence are determined.

4. The apparatus of claim 3, wherein the target neighbor determining device is configured to determine one reference subsequence in the first number of reference subsequences as the neighbor of the target subsequence, in response to determining that an upper limit value of the Euclidean distance between the target subsequence and the one reference subsequence is smaller than lower limit values of the Euclidean distances between the target subsequence and the other reference subsequences in the first number of reference subsequences.

5. The apparatus of claim 1, wherein the third number is equal to the second number, and wherein the anomaly detecting device is configured to determine whether the target subsequence is the abnormal subsequence, according to an approximation degree between the target subsequence and the second number of neighbors, and an approximation degree between the reference subsequence, which has the target subsequence as the neighbor thereof, in the second number of reference subsequences and the third number of neighbors thereof.

6. The apparatus of claim 5, wherein the anomaly detecting device is configured to determine whether the target subsequence is the abnormal subsequence, according to the approximation degrees by:

calculating a reciprocal of an average value of Euclidean distances between the target subsequence and the second number of neighbors thereof, so as to determine the approximation degree between the target subsequence and the second number of neighbors of the target subsequence;

calculating a reciprocal of an average value of Euclidean distances between each reference subsequence in the second number of reference subsequences, which have the target subsequence as the neighbor thereof, in the second number of reference subsequences and the third number of neighbors;

calculating an average value of reciprocals of average values corresponding to the respective reference subsequence, which has the target subsequence as the neighbor thereof, in the second number of reference subsequences, so as to determine the approximation degree between the reference subsequence, which has the target subsequence as the neighbor thereof, in the second number of reference subsequences and the third number of neighbors thereof; and

determining whether the target subsequence is the abnormal subsequence, based on the reciprocal of the average value of the Euclidean distances between the target subsequence and the second number of neighbors thereof, and the average value of the reciprocals of the average values corresponding to the respective reference subsequence, which has the target subsequence as the neighbor thereof, in the second number of reference subsequences.

7. The apparatus of claim 6, wherein the anomaly detecting device is configured to calculate a ratio between the average value of the reciprocals of the average values corresponding to the respective reference subsequence, which has the target subsequence as the neighbor thereof, in the second number of reference subsequences and the reciprocal of the average value of the Euclidean distances between the target subsequence and the second number of neighbors thereof, and determine that the target subsequence is the abnormal subsequence, in response to determining that the ratio is greater than a predetermined threshold value.