Systems and methods for discovering fully dependent patterns
AssigneeInternational Business Machines Corporation
InventorsSheng Ma, Joseph L. Hellerstein, Feng Liang
Life of this patent
Estimating the term…
Abstract
A new form of pattern referred to as a fully dependent pattern or d-pattern is provided. The d-pattern captures dependence among a set of items based on a dependency test. An efficient algorithm is provided for discovering all d-patterns in data. Specifically, a linear algorithm is provided for testing whether a pattern is an d-pattern. Further, a pruning algorithm is provided that prunes the search space effectively. Still further, a level-wise algorithm for mining d-patterns is provided.
Claims34
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and
- outputting the one or more identified patterns based on results of the dependency tests.
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and
- outputting the one or more identified patterns based on results of the dependency tests.
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and (ii) output the one or more identified patterns based on results of the dependency tests;
- 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.
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and (iii) output the one or more identified patterns based on results of the dependency tests;
- 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.
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and
- outputting the one or more identified patterns based on results of the dependency tests.
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 whether the one or more sets respectively satisfy a dependency test, the dependency test being satisfied when each of the items in a set of items is dependent upon each other item with a prescribed significance level;
- and
- outputting the one or more identified patterns based on results of the dependency tests.
Dependencies are inferred from the claim text.