DETECTING AN ABNORMAL SUBSEQUENCE IN A DATA SEQUENCE

• US 20150212868A1
• Filed: 01/16/2015
• Published: 07/30/2015
• 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
• Granted Patent: US 9,552,243 B2
• Time in Patent Office: 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. A method 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 method comprising:

constructing, with a processing device, 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;

determining a second number of neighbors of the target subsequence based on the hierarchical data structure of the target subsequence and hierarchical data structures of the first number of reference subsequences constructed in advance, the second number of neighbors of the target subsequence being the second number of reference subsequences, which have minimum Euclidean distances from the target subsequence, in the first number of reference subsequences;

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

determining 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 method of claim 1, wherein the hierarchical data structure is a binary tree.

3. The method of claim 1, wherein the value 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 is an average value, a maximum value and a minimum value of the data stored in the corresponding node, and wherein the determining a second number of neighbors of the target subsequence based on the hierarchical data structure of the target subsequence and hierarchical data structures of the first number of reference subsequences constructed in advance includes:

determining upper limit values and lower limit values of Euclidean distances between the target subsequence and the respective reference subsequences, corresponding to one or more layers of the hierarchical data structures 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 structures, respectively, starting from an uppermost layer of the hierarchical data structures, and determining 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 method of claim 3, wherein the determining the neighbors of the target subsequence on the basis of the upper limit values and the lower limit values includes:

determining one reference subsequence in the first number of reference subsequences as the neighbor of the target subsequence, in response to that the upper limit value of the Euclidean distance between the target subsequence and the one reference subsequence is smaller than the 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 method of claim 1, wherein the third number is equal to the second number, and wherein the determining 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 includes:

determining 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 method of claim 5, wherein, the determining 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 includes:

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, which has 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 method of claim 6, wherein the 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 includes:

calculating 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

determining that the target subsequence is the abnormal subsequence, in response to that the ratio is greater than a predetermined threshold value.

8. 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 a 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 the 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 the third number of subsequences, which have minimum Euclidean distances from the each reference subsequence, 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.

9. The apparatus of claim 8, wherein the hierarchical data structure is a binary tree.

10. The apparatus of claim 8, wherein the value 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 is an average value, a maximum value and a minimum value of the data stored in the corresponding node, 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 the respective reference subsequences, corresponding to one or more layers of the hierarchical data structures 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 structures, respectively, starting from an uppermost layer of the hierarchical data structures, and determine 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.

11. The apparatus of claim 10, 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 that the upper limit value of the Euclidean distance between the target subsequence and the one reference subsequence is smaller than the lower limit values of the Euclidean distances between the target subsequence and the other reference subsequences in the first number of reference subsequences.

12. The apparatus of claim 8, 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.

13. The apparatus of claim 12, 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, which has 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.

14. The apparatus of claim 13, 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 that the ratio is greater than a predetermined threshold value.