Systems and methods for discovering mutual dependence patterns

• US 6,829,608 B2
• Filed: 07/30/2001
• Issued: 12/07/2004
• Est. Priority Date: 07/30/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ma, Sheng, Hellerstein, Joseph L.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/918,253
• Publication Number:
  US 20030023591A1
• Time in Patent Office: 1,226 Days
• Field of Search: 707/101, 707/10, 707/6, 707/1, 707/7, 707/103, 707/2, 707/3
• US Class Current: 707/776
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A new form of pattern is provided, referred to as a mutual dependence pattern or m-pattern. The m-pattern captures mutual dependence among a set of items. Intuitively, the m-pattern represents a set of items that often occur together. In our experience, such m-patterns often provide great values for certain tasks, such as event correlation in event management. Further, an efficient algorithm is provided for discovering all m-patterns in data for a given minimum mutual dependence threshold. Specifically, a linear algorithm is provided for testing whether a pattern is an m-pattern. Further, a pruning algorithm is provided that prunes the search space effectively. Still further, a level-wise algorithm for mining m-patterns is provided.

Claims

1. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

identifying sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

outputting the identified mutual dependence patterns based on results of the comparisons.

2. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

identifying one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

outputting the one or more identified patterns based on results of the comparisons;

wherein the identifying step further comprises identifying a set of items in the input data set, which includes at least two subsets of at least one item, as a pattern when the set of items has a conditional probability value computed therefor that is not less than a predetermined threshold value, wherein the conditional probability value is indicative of a probability that both of the at least two subsets of at least one item will occur given that one of the at least two subsets of at least one item has occurred.

3. The method of claim 2, wherein the predetermined threshold value is between zero and one.

4. The method of claim 2, wherein the conditional probability value is estimated by the number of occurrences in the input data set of the two subsets divided by the number of occurrences in the data set of one of the two subsets.

5. The method of claim 2, wherein the input data set comprises transaction data.

6. The method of claim 2, wherein the input data set comprises event data.

7. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

identifying one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

outputting the one or more identified patterns based on results of the comparisons;

wherein the identifying step further comprises identifying a set of items in the input data set as a pattern when the set of items has a conditional probability value computed for the set of items minus a particular item of the set, given the particular item of the set, that is not less than a predetermined threshold value.

8. The method of claim 7, wherein the predetermined threshold value is between zero and one.

9. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

obtaining an input data set of items;

searching the input data set of items to identify sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

outputting the identified mutual dependence patterns based on results of the comparisons.

10. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

obtaining an input data set of items;

normalizing the input data set;

searching the input data set of items to identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

outputting the one or more identified patterns based on results of the comparisons,

where in the input data set comprises event data and the normalizing step comprises transforming at least a portion of the event data into event classes such that the event data is non-application-dependent.

11. The method of claim 10, wherein the event data transformation step further comprises the step of mapping two or more attributes associated with an event into an event class.

12. The method of claim 11, wherein the mapping step is performed in accordance with a lookup table.

13. The method of claim 10, wherein the event data is in a tabular form with a first number of columns before the transformation step and in a tabular form with a second number of columns after the transformation step, the second number of columns being less than the first number of columns.

14. The method of claim 10, wherein the outputting step further comprises converting the one or more identified patterns into a human readable format.

15. A computer-based method of mining one or more patterns in an input data set of items, the method comprising the steps of:

obtaining an input data set of items;

searching the input data set of items to identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

outputting the one or more identified patterns based on results of the comparisons;

wherein the searching step further comprises the step of performing a level-wise scan based on a set length to determine candidate sets of items in the input data set that have conditional probability values respectively computed therefor that are not less than the predetermined threshold value.

16. The method of claim 15, further comprising the step of pruning candidate sets based on an upper bound property.

17. The method of claim 16, wherein the upper bound property specifies that only candidate sets are considered where the conditional probability of a set of items minus a particular subset of items given the particular subset of items is not greater than the number of occurrences of the set of items minus the particular subset of items divided by the number of occurrences of the subset of items.

18. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) identify sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

(ii) output the identified mutual dependence patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the identified mutual dependence patterns.

19. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

(ii) output the one or more identified patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the one or more identified patterns;

wherein the identifying operation further comprises identifying a set of items in the input data set, which includes at least two subsets of at least one item, as a pattern when the set of items has a conditional probability value computed therefor that is not less than a predetermined threshold value, wherein the conditional probability value is indicative of a probability that both of the at least two subsets of at least one item will occur given that one of the at least two subsets of at least one item has occurred.

20. The apparatus of claim 19, wherein the predetermined threshold value is between zero and one.

21. The apparatus of claim 19, the conditional probability value is estimated by the number of occurrences in the input data set of the two subsets divided by the number of occurrences in the data set of one of the two subsets.

22. The apparatus of claim 19, wherein the input data set comprises transaction data.

23. The apparatus of claim 19, wherein the input data set comprises event data.

24. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

(ii) output the one or more identified patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the one or more identified patterns;

wherein the identifying operation further comprises identifying a set of items in the input data set as a pattern when the set of items has a conditional probability value computed for the set of items minus a particular item of the set, given the particular item of the set, that is not less than a predetermined threshold value.

25. The apparatus of claim 24, wherein the predetermined threshold value is between zero and one.

26. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) obtain an input data set of items;

(ii) search the input data set of items to identify sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

(iii) output the identified mutual dependence patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the identified mutual dependence patterns.

27. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) obtain an input data set of items;

(iii) search the input data set of items to identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

(iii) output the one or more identified patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the one or more identified patterns;

wherein the at least one processor is further operative to, prior to the searching operation, normalize the input data set, and further wherein the input data set comprises event data and the normalizing operation comprises transforming at least a portion of the event data into event classes such that the event data is non-application-dependent.

28. The apparatus of claim 27, wherein the event data transformation operation further comprises mapping two or more attributes associated with an event into an event class.

29. The apparatus of claim 28, wherein the mapping operation is performed in accordance with a lookup table.

30. The apparatus of claim 27, wherein the event data is in a tabular form with a first number of columns before the transformation operation and in a tabular form with a second number of columns after the transformation operation, the second number of columns being less than the first number of columns.

31. The apparatus of claim 27, wherein the outputting operation further comprises converting the one or more identified patterns into a human readable format.

32. Apparatus for mining one or more patterns in an input data set of items, the apparatus comprising:

at least one processor operative to;

(i) obtain an input data set of items;

(ii) search the input data set of items to identify one or more sets of items in the input data set as one or more patterns based on respective comparisons of conditional probability values associated with each of the one or more sets of items to a predetermined threshold value; and

(iii) output the one or more identified patterns based on results of the comparisons; and

a memory, coupled to the at least one processor, which stores at least one of the input data set and the one or more identified patterns;

wherein the searching operation further comprises performing a level-wise scan based on a set length to determine candidate sets of items in the input data set that have conditional probability values respectively computed therefor that are not less than the predetermined threshold value.

33. The apparatus of claim 32, wherein the at least one processor is further operative to prune candidate sets based on an upper bound property.

34. The apparatus of claim 33, wherein the upper bound property specifies that only candidate sets are considered where the conditional probability of a set of items minus a particular subset of items given the particular subset of items is not greater than the number of occurrences of the set of items minus the particular subset of items divided by the number of occurrences of the subset of items.

35. An article of manufacture for mining one or more patterns in an input data set of items, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

identifying sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

outputting the identified mutual dependence patterns based on results of the comparisons.

36. An article of manufacture for mining one or more patterns in an input data set of items, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining an input data set of items;

searching the input data set of items to identify sets of items in the input data set as mutual dependence patterns based on respective comparisons of conditional probability values associated with each of the sets of items to a predetermined mutual dependence threshold value; and

outputting the identified mutual dependence patterns based on results of the comparisons.