Systems and methods for discovering mutual dependence patterns
First Claim
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 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.
1 Assignment
0 Petitions
Accused Products
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.
35 Citations
38 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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 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. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26)
-
-
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;
(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. - View Dependent Claims (28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. 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 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.
-
-
38. 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 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.
-
Specification