Detecting an abnormal subsequence in a data sequence

Patent metadata

Field	Value
Publication number	US-9547543-B2
Application number	US-201514741819-A
Country	US
Kind code	B2
Filing date	Jun 17, 2015
Priority date	Jan 27, 2014
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

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.

First claim

What is claimed is:

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 a 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 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
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 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 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 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 determining 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 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 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 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 in the second number of reference subsequences, which have 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 determining that the ratio is greater than a predetermined threshold value.

Assignees

• IBM

Inventors

• Chen Xiao Yan
• Chen yao liang
• Huang Sheng
• Liu Kai
• Wang Chen

Classifications

• G05B23/0232 Primary

  based on qualitative trend analysis, e.g. system evolution · CPC title

• G06F11/0751 Primary

  Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06) · CPC title