Sequential anomaly detection

• US 9,727,821 B2
• Filed: 08/16/2013
• Issued: 08/08/2017
• Est. Priority Date: 08/16/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Ching-Yung, Song, Yale, Wen, Zhen
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Wu, Fuming
• Application Number:
  US13/969,151
• Publication Number:
  US 20150052090A1
• Time in Patent Office: 1,453 Days
• Field of Search: None
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A dataset including at least one temporal event sequence is collected. A one-class sequence classifier f(x) that obtains a decision boundary is statistically learned. At least one new temporal event sequence is evaluated, wherein the at least one new temporal event sequence is outside of the dataset. It is determined whether the at least one new temporal event sequence is one of a normal sequence or an abnormal sequence based on the evaluation. Numerous additional aspects are disclosed.

Claims

1. A method comprising:

collecting a first computer process related dataset comprising a plurality of normal temporal event sequences;

learning, using the first computer process related dataset, a one-class sequence classifier f(x) that obtains a decision boundary configured to label temporal event sequences;

collecting a second computer process related dataset comprising at least one new temporal event sequence; and

evaluating the at least one new temporal event sequence using the decision boundary to label the at least one new temporal event sequence as an abnormal sequence, causing a computer system to issue an alert,

wherein learning the classifier learning comprises;

randomly initializing a solution space (Ω

);

constructing an undirected graph for the normal temporal event sequences in the first computer process related dataset;

capturing at least one temporal dynamic of the normal temporal event sequences of the first computer process related dataset;

assigning labels to each of the normal temporal event sequences of the first computer process related dataset by computing, for each of the normal temporal event sequences a probability that the at least one normal temporal event sequence of the first computer process related dataset is a normal sequence or an abnormal sequence, wherein at least one of the at least one normal temporal event sequences is labeled as an abnormal sequence; and

refining the classifier using the plurality of normal temporal event sequences of the first computer process related dataset with respective labels.

2. The method of claim 1, wherein the normal temporal event sequences of the first computer process related dataset are unlabeled.

3. The method of claim 1, wherein evaluating the new temporal event sequence uses the learned classifier to compute a probabilistic distance of the new temporal event sequence to the decision boundary.

4. The method of claim 1, wherein the first computer process related dataset further comprises latent random variables, and wherein each latent random variable is associated with each event in the sequence.

5. The method of claim 1, further comprising:

repeating the steps for learning the classifier until a termination criterion is satisfied.

6. The method of claim 5, wherein repeating the steps for learning the classifier until the termination criterion is satisfied further comprises:

enforcing, using a user defined parameter, a plurality of the datasets to have a higher probability of having a normal sequence, while keeping a solution vector of the solution space (Ω

) small as compared to a number of normal sequences.

7. The method of claim 1, further comprising:

reviewing an automatic classification of at least one of the normal temporal event sequences in the first computer process related dataset as abnormal;

receiving a user inputted label of “

true anomaly”

for at least one of the reviewed automatically classified sequences;

adding the “

true anomaly”

labeled sequences to the first computer process related dataset; and

re-training the classifier using the first computer process related dataset including the “

true anomaly”

labeled sequences.

8. The method of claim 7, wherein during the re-training, a relative weight of the “

true anomaly”

labeled sequences is higher than a weight given to other sequences in the first computer process related dataset by distribution-sensitive learning.

9. The method of claim 8, wherein the relative weight of the “

true anomaly”

labeled sequences is inversely proportional to a distribution of the sequences in the first computer process related dataset.

10. The method of claim 1, wherein learning the one-class classifier further comprises:

defining at least one view configuration organizing at least one feature of the normal temporal event sequences of the first computer process related dataset into multiple views;

refining the classifier with at least one of the defined configuration of views using multi-view learning;

determining an automatic classification of the at least one new temporal event sequence with the refined classifier, wherein the automatic classification is a negative label;

receiving user input regarding the automatic classification of the at least one new temporal event sequence, the user input updating a negative label of the at least new temporal event sequence to a positive label; and

generating at least one suggestion to adjust the at least one view configuration based on classification results of the refined classifier.

11. The method of claim 1, further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied on a computer-readable storage medium, and wherein the distinct software modules comprise a data collection module, an optimization engine module, an evaluation engine module, and an analysis module;

wherein;

said dataset collection is carried out by said data collection module executing on at least one hardware processor;

said classifier learning is carried out by said optimization engine module executing on said at least one hardware processor;

said evaluating is carried out by said evaluation engine module executing on said at least one hardware processor; and

said determining is carried out by said analysis module executing on said at least one hardware processor.

12. A computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therewith, said computer readable program code comprising:

computer readable program code configured to;

collect a dataset comprising a plurality of normal temporal event sequences;

learn, using the dataset, a one-class sequence classifier f(x) that obtains a decision boundary labeling each temporal event sequence;

evaluate, using the decision boundary, at least one new temporal event sequence, wherein the at least one new temporal event sequence is outside of the dataset; and

determine that the at least one new temporal event sequence is an abnormal sequence based on the evaluating step, causing an alert to be issued,

wherein the computer readable program code configured to learn the classifier learning comprises computer readable program code configured to;

randomly initialize a solution space (Ω

);

construct an undirected graph for the normal temporal event sequences in the dataset;

capture at least one temporal dynamic of the normal temporal event sequences of the dataset;

assign labels to each of the normal temporal event sequences of the dataset by computing, for each of the normal temporal event sequences a probability that the at least one normal temporal event sequence of the dataset is a normal sequence or an abnormal sequence, wherein at least one of the at least one normal temporal event sequences is labeled as an abnormal sequence; and

refine the classifier using the plurality of normal temporal event sequences of the dataset with respective labels.

13. An apparatus comprising:

a memory; and

at least one processor, coupled to said memory, and operative to;

collect a dataset comprising a plurality of normal temporal event sequences;

learn, using the plurality of normal temporal event sequences, a one-class sequence classifier f(x) that obtains a decision boundary labeling each temporal event sequence;

evaluate, using the decision boundary, at least one new temporal event sequence, wherein the at least one new temporal event sequence is outside of the dataset; and

determine that the at least one new temporal event sequence is an abnormal sequence based on the evaluating step, causing an alert to be issued,

wherein the processor in learning the one-class sequence classifier f(x) is operative to;

randomly initialize a solution space (Ω

);

construct an undirected graph for the normal temporal event sequences in the dataset;

capture at least one temporal dynamic of the normal temporal event sequences of the dataset;

assign labels to each of the normal temporal event sequences of the dataset by computing, for each of the normal temporal event sequences a probability that the at least one normal temporal event sequence of the dataset is a normal sequence or an abnormal sequence, wherein at least one of the at least one normal temporal event sequences is labeled as an abnormal sequence; and

refine the classifier using the plurality of normal temporal event sequences of the dataset with respective labels.

14. The apparatus of claim 13, wherein the temporal event sequences of the dataset are unlabeled.

15. The apparatus of claim 13, wherein a probabilistic distance of the new temporal event sequence to the decision boundary is computed with the learned classifier to evaluate the at least one new temporal event sequence.

16. The apparatus of claim 13 wherein the at least one processor is operative to automatically classify the at least one temporal event sequence in the dataset as abnormal.

17. The apparatus of claim 16, wherein the at least one processor is operative to receive a user inputted label of “

true anomaly”

for at least one of automatically classified sequences.

18. The apparatus of claim 17, wherein the at least one processor is operative to re-train the classifier using the dataset including the “

true anomaly”

labeled sequences.

19. The apparatus of claim 13, further comprising a plurality of distinct software modules, each of the distinct software modules being embodied on a computer-readable storage medium, and wherein the distinct software modules comprise a data collection module, an optimization engine module, an evaluation engine module, and an analysis module;

wherein;

said at least one processor is operative to collect said dataset by executing said data collection module;

said at least one processor is operative to learn said classifier by executing said optimization engine module;

said at least one processor is operative to evaluate said sequence by executing said evaluation engine module; and

said at least one processor is operative to determine whether the at least one new temporal event sequence is one of a normal sequence or an abnormal sequence by executing said analysis module.