Method and system for associating events

• US 20050080806A1
• Filed: 10/08/2003
• Published: 04/14/2005
• Est. Priority Date: 10/08/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kozakov, Lev, Kim, Moon J., Drissi, Youssef, Jeng, Jun-Jang, Fin, Tong-Haing, Doganata, Yurdaer N.
• Granted Patent: US 7,089,250 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method, system, and computer program product for associating events. A provided event dataset includes events occurring in each of N successive time intervals (N≧3). Association rules pertaining to successive events in the event dataset are deduced. Sequences of events are generated from the association rules. Clusters of the sequences of events are formed. Sequences of the clusters are created. The clusters of the sequences may be used: to identify at least one event occurring in a time interval of the N time intervals as being a probable cause of at least one event occurring in a later-occurring time interval of the N time intervals; or to predict an occurrence of at least one event in a time interval occurring after the N time intervals, wherein the at least one event had occurred within the N time intervals.

Claims

1. A method for associating events, comprising the steps of:

providing an event dataset that includes a plurality of events occurring in each of N successive time intervals, said N≧

3;

deducing from the event dataset a plurality of association rules, each association rule E_KE_L of the plurality of association rules expressing an association between events E_K and E_L respectively occurring in two successive time intervals of the N time intervals, said events E_K and E_L being in the event dataset;

generating a plurality of sequences of events, each sequence of the plurality of sequences being generated from at least two sequentially ordered association rules of the plurality of association rules;

forming a plurality of clusters from the plurality of sequences in accordance with a clustering algorithm, each cluster of the plurality of clusters including at least two sequences of the plurality of sequences; and

creating S_C sequences of clusters from the plurality of clusters, said S_C≧

1, each sequence of the S_C sequences including at least two clusters of the plurality of clusters.

2. The method of claim 1, said method further comprising after the creating step:

using at least one sequence of the S_C sequences to identify at least one event occurring in a first time interval of the N time intervals as being a probable cause of at least one event occurring in a later-occurring time interval of the N time intervals.

3. The method of claim 1, said method further comprising after the creating step:

using a first sequence of the S_C sequences to predict an occurrence of at least one event in a time interval occurring after the N time intervals, wherein the at least one event had occurred within the N time intervals.

4. The method of claim 1, wherein each pair of sequentially ordered association rules of the plurality of association rules consists of a first association rule and a second association rule, and wherein the first association rule and the second association rule are independent of each other.

5. The method of claim 1, wherein the association rules from which a first sequence of the plurality of sequences has been generated include a pair of consecutively ordered first and second association rules which are not independent of each other.

6. The method of claim 1, wherein the N time intervals are contiguously sequenced.

7. The method of claim 1, wherein the N time intervals are not contiguously sequenced.

8. The method of claim 1, wherein each sequence of the plurality of sequences is of the form E₁→

E₂→

E₃→

. . . E<sub>I−

1</sub>→

E₁ in relation to sequentially ordered association rules E₁E₂, E₂E₃, . . . , E<sub>I−

1</sub>E₁ of the plurality of association rules, and wherein I≧

3.

9. The method of claim 1, wherein said each association rule satisfies a condition of α

≦

P_KL<

1, wherein P_KL is the probability that E_K and E_L respectively occur in the two successive time intervals, and wherein α

is a predetermined positive real number satisfying α

<

1.

10. The method of claim 9, wherein α

is within a range selected from the group consisting of a first range of 0.50≦

α

<

1, a second range of 0.60≦

α

<

1, a third range of 0.70≦

α

<

1, a fourth range of 0.80≦

α

<

1, a fifth range of 0.90≦

α

<

1, and a sixth range of 0.95≦

α

<

1.

11. The method of claim 9, wherein each sequence of the plurality of sequences has a probability of occurrence no less than β

, and wherein β

is a predetermined positive real number satisfying β

<

α

.

12. The method of claim 11, wherein β

is within a range selected from the group consisting of a first range of 0.20≦

β

<

α

, a second range of 0.30≦

β

<

α

, a third range of 0.40≦

β

<

α

, a fourth range of 0.50≦

β

<

α

, a fifth range of 0.60β

≦

α

, and a sixth range of 0.70≦

β

<

α

.

13. A system for associating events, comprising the steps of:

means for providing an event dataset that includes a plurality of events occurring in each of N successive time intervals, said N≧

3;

means for deducing, from the event dataset, a plurality of association rules, each association rule E_KE_L of the plurality of association rules expressing an association between events E_K and E_L respectively occurring in two successive time intervals of the N time intervals, said events E_K and E_L being in the event dataset;

means for generating a plurality of sequences of events, each sequence of the plurality of sequences being generated from at least two sequentially ordered association rules of the plurality of association rules;

means for forming a plurality of clusters from the plurality of sequences in accordance with a clustering algorithm, each cluster of the plurality of clusters including at least two sequences of the plurality of sequences; and

means for creating S_C sequences of clusters from the plurality of clusters, said S_C≧

1, each sequence of the S_C sequences including at least two clusters of the plurality of clusters.

14. The system of claim 13, said system further comprising means for using at least one sequence of the S_C sequences to identify at least one event occurring in a first time interval of the N time intervals as being a probable cause of at least one event occurring in a later-occurring time interval of the N time intervals.

15. The system of claim 13, said system further comprising means for using a first sequence of the S_C sequences to predict an occurrence of at least one event in a time interval occurring after the N time intervals, wherein the at least one event had occurred within the N time intervals.

16. The system of claim 13, wherein each pair of sequentially ordered association rules of the plurality of association rules consists of a first association rule and a second association rule, and wherein the first association rule and the second association rule are independent of each other.

17. The system of claim 13, wherein the association rules from which a first sequence of the plurality of sequences is generated by said means for generating include a pair of consecutively ordered first and second association rules which are not independent of each other.

18. The system of claim 13, wherein the N time intervals are contiguously sequenced.

19. The system of claim 13, wherein the N time intervals are not contiguously sequenced.

20. The system of claim 13, wherein each sequence of the plurality of sequences is of the form E₁→

E₂→

E₃→

. . . E<sub>I−

1</sub>→

E₁ in relation to sequentially ordered association rules E₁E₂, E₂E₃, . . . E<sub>I−

1</sub>E₁ of the plurality of association rules, and wherein I≧

3.

21. The system of claim 13, wherein said each association rule satisfies a condition of α

≦

P_KL<

1, wherein P_KL is the probability that E_K and E_L respectively occur in the two successive time intervals, and wherein α

is a predetermined positive real number satisfying α

<

1.

22. The system of claim 21, wherein α

is within a range selected from the group consisting of a first range of 0.50≦

α

<

1, a second range of 0.60≦

α

<

1, a third range of 0.70≦

α

<

1, a fourth range of 0.80≦

α

<

1, a fifth range of 0.90≦

α

<

1, and a sixth range of 0.95≦

α

<

1.

23. The system of claim 21, wherein each sequence of the plurality of sequences has a probability of occurrence no less than β

, and wherein β

is a predetermined positive real number satisfying β

<

α

.

24. The system of claim 23, wherein β

is within a range selected from the group consisting of a first range of 0.20≦

β

<

α

, a second range of 0.30≦

β

<

α

, a third range of 0.40≦

β

<

α

, a fourth range of 0.50≦

β

<

α

, a fifth range of 0.60β

≦

α

, and a sixth range of 0.70≦

β

<

α

.

25. A computer program product comprising a computer usable medium having a computer readable program embodied therein, said computer readable program adapted to access an event dataset that includes a plurality of events occurring in each of N successive time intervals, said computer readable program further adapted execute a method for associating events, said method comprising the steps of:

deducing from the event dataset a plurality of association rules, each association rule E_KE_L of the plurality of association rules expressing an association between events E_K and E_L respectively occurring in two successive time intervals of the N time intervals, said events E_K and E_L being in the event dataset;

generating a plurality of sequences of events, each sequence of the plurality of sequences being generated from at least two sequentially ordered association rules of the plurality of association rules;

forming a plurality of clusters from the plurality of sequences in accordance with a clustering algorithm, each cluster of the plurality of clusters including at least two sequences of the plurality of sequences; and

creating S_C sequences of clusters from the plurality of clusters, said S_C≧

1, each sequence of the S_C sequences including at least two clusters of the plurality of clusters.

26. The computer program product of claim 25, said method further comprising after the creating step:

using at least one sequence of the S_C sequences to identify at least one event occurring in a first time interval of the N time intervals as being a probable cause of at least one event occurring in a later-occurring time interval of the N time intervals.

27. The computer program product of claim 25, said method further comprising after the creating step:

using a first sequence of the S_C sequences to predict an occurrence of at least one event in a time interval occurring after the N time intervals, wherein the at least one event had occurred within the N time intervals.

28. The computer program product of claim 25, wherein each pair of sequentially ordered association rules of the plurality of association rules consists of a first association rule and a second association rule, and wherein the first association rule and the second association rule are independent of each other.

29. The computer program product of claim 25, wherein the association rules from which a first sequence of the plurality of sequences has been generated include a pair of consecutively ordered first and second association rules which are not independent of each other.

30. The computer program product of claim 25, wherein the N time intervals are contiguously sequenced.

31. The computer program product of claim 25, wherein the N time intervals are not contiguously sequenced.

32. The computer program product of claim 25, wherein each sequence of the plurality of sequences is of the form E₁→

E₂→

E₃→

. . . . E<sub>I−

1</sub>→

E₁ in relation to sequentially ordered association rules E₁ E₂, E₂E₃, . . . , E<sub>I−

1</sub>E₁ of the plurality of association rules, and wherein I≧

3.

33. The computer program product of claim 25, wherein said each association rule satisfies a condition of α

≦

P_KL<

1, wherein P_KL is the probability that E_K and E_L respectively occur in the two successive time intervals, and wherein α

is a predetermined positive real number satisfying α

<

1.

34. The computer program product of claim 33, wherein α

is within a range selected from the group consisting of a first range of 0.50≦

α

<

1, a second range of 0.60≦

α

<

1, a third range of 0.70≦

α

<

1, a fourth range of 0.80≦

α

<

1, a fifth range of 0.90≦

α

<

1, and a sixth range of 0.95 ≦

α

<

1.

35. The computer program product of claim 33, wherein each sequence of the plurality of sequences has a probability of occurrence no less than β

, and wherein β

is a predetermined positive real number satisfying β

<

α

.

36. The computer program product of claim 35, wherein β

is within a range selected from the group consisting of a first range of 0.20≦

β

<

α

, a second range of 0.30≦

β

<

α

, a third range of 0.40≦

β

<

α

, a fourth range of 0.50≦

β

<

α

, a fifth range of 0.60β

≦

α

, and a sixth range of 0.70≦

β

<

α

.