Method and system for mining quantitative association rules in large relational tables

• US 5,724,573 A
• Filed: 12/22/1995
• Issued: 03/03/1998
• Est. Priority Date: 12/22/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Srikant, Ramakrishnan
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/577,945
• Time in Patent Office: 802 Days
• Field of Search: 395/601, 395/603, 395/606
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus are disclosed for mining quantitative association rules from a relational table of records. The method comprises the steps of: partitioning the values of selected quantitative attributes into intervals, combining adjacent attribute values and intervals into ranges, generating candidate itemsets, determining frequent itemsets, and outputting an association rule when the support for a frequent itemset bears a predetermined relationship to the support for a subset of the frequent itemset. Preferably, the partitioning step includes determining whether to partition and the number of partitions based on a partial incompleteness measure. The candidate generation includes discarding those itemsets not meeting a user-specified interest level and those having a subset which is not a frequent itemset. The frequent itemsets are determined using super-candidates that include information of the candidate itemsets. Preferably, each super-candidate has a data structure, such as a multi-dimensional tree or array, representing quantitative attributes common to the replaced candidate itemsets.

Claims

1. A method for identifying quantitative association rules from a table of records, each record having a plurality of attributes associated therewith, the attributes including quantitative and categorical attributes, each attribute having a value, the method comprising the steps of:

partitioning the values of each quantitative attribute from a selected group of quantitative attributes into a respective plurality of intervals;

determining a support for each value of the categorical attributes and the non-partitioned quantitative attributes, and a support for each interval of the partitioned quantitative attributes, the support for a value being a number of records in the table whose attribute values include the value, the support for an interval being a number of records in the table whose attribute values are part of the interval;

for each quantitative attribute, combining adjacent values of the attribute if the attribute is not partitioned, or adjacent intervals of the attribute if the attribute is partitioned, into ranges, as long as the support for each range is less than a maximum support;

identifying items with at least a minimum support, each item representing a quantitative attribute and a range, or a categorical attribute and a value, the items with at least the minimum support making up a seed set;

generating candidate itemsets from the seed set, each itemset being a set of items and having a support, the support of the itemset being a number of records in the table which support the itemset;

determining frequent itemsets from the candidate itemsets, the frequent itemsets being those itemsets whose support is more than the minimum support, the determined frequent itemsets becoming the next seed set;

repeating the steps of generating candidate itemsets and determining frequent itemsets until all the frequent itemsets are found; and

outputting an association rule when the support of a selected frequent itemset bears a predetermined relationship to the support of a subset of the selected frequent itemset, thereby satisfying a minimum confidence constraint, the association rule being an expression of the form XY where X and Y are itemsets.

2. The method as recited in claim 1, wherein the step of partitioning includes the steps of, for each quantitative attribute:

(a) determining whether to partition the values of the quantitative attribute into the intervals, based on a measure of partial completeness which indicates potential information loss due to the partitioning; and

(b) if the values of the quantitative attribute are to be partitioned, then;

(i) determining a number of partitions into which the values of the quantitative attribute are partitioned, based on the measure of partial completeness; and

(ii) partitioning the values of the quantitative attribute into the intervals.

3. The method as recited in claim 1, wherein the step of generating candidate itemsets includes the steps of:

joining the itemsets of the seed set to generate a next set of candidate itemsets; and

discarding any candidate itemset having a subset that is not a frequent itemset.

4. The method as recited in claim 3 further comprises the step of discarding any candidate itemset whose support is more than 1/R, where R is a user-specified interest measure.

5. The method as recited in claim 1 further comprising the steps of:

for each categorical attribute, mapping the values of the categorical attribute into a set of consecutive integers;

for each quantitative attribute whose values are partitioned into intervals, mapping the intervals into a set of consecutive integers such that the order of the intervals are preserved; and

for each quantitative attribute whose values are not partitioned into intervals, mapping the values of the quantitative attribute into a set of consecutive integers such that the order of the values are preserved.

6. The method as recited in claim 1 further comprising the step of discarding those association rules that do not satisfy a user-specified interest measure.

7. The method as recited in claim 1, wherein the step of determining frequent itemsets includes the steps of:

(a) dividing the candidate itemsets into groups, each group including the candidate itemsets that have common quantitative and categorical attributes, and common values for the respective common categorical attributes;

(b) replacing each group with a super-candidate, each super-candidate having (i) the common categorical attributes and their respective values, and (ii) a data structure representing the common quantitative attributes and their values;

(c) for each record of the table;

(i) determining which super-candidates are supported by the categorical attributes in the record; and

(ii) updating the data structure for each determined super-candidate with the values of the quantitative attributes in the record; and

(d) determining the support for each candidate itemset using the data structures of the super-candidates.

8. The method as recited in claim 7 further comprising the step of:

entering the super-candidates into a hash-tree data structure; and

wherein the step of determining which super-candidates is based on the hash-tree data structure.

9. The method as recited in claim 7, wherein:

the data structure is a multi-dimensional tree having a plurality of hyper-rectangles, each hyper-rectangle corresponding to a candidate itemset and having a plurality of boundaries and a plurality of dimensions, the boundaries of the hyper-rectangle in the n-th dimension corresponding, respectively, to the ranges of the n-th quantitative attribute of the candidate itemset, whereby the values of the quantitative attributes in a record correspond to an n-dimensional point; and

the step of updating the data structure includes incrementing a support count for each hyper-rectangle that contains the n-dimensional point corresponding to the quantitative attributes of the record.

10. The method as recited in claim 7, wherein:

the data structure is an n-dimensional array having a plurality of cells, n being the number of the common quantitative attributes in the respective super-candidate, each dimension of the array corresponding to a common quantitative attribute, the number of cells in a j-th dimension of the array being equal to the number of partitions of the common quantitative attribute if the common quantitative attribute is partitioned, or the number of values of the common quantitative attribute if the common quantitative attribute is not partitioned, each candidate itemset of the super-candidate corresponding to the cells within a hyper-rectangle, the boundaries of the hyper-rectangle corresponding respectively to the ranges of the n-th quantitative attribute of the candidate itemset, and the values of the quantitative attributes in a record corresponding to an n-dimensional point;

the step of updating the data structure includes incrementing a support count for a cell corresponding to the n-dimensional point; and

the step of determining a support for each candidate itemset includes adding, for each candidate itemset replaced by the super-candidate, the support counts of all the cells within the hyper-rectangle corresponding to the quantitative attributes of the candidate itemset, in order to obtain the support for the candidate itemset.

11. A computer program product for use with a computer system for identifying quantitative association rules from a table of records, each record having a plurality of attributes associated therewith, the attributes including quantitative and categorical attributes, each attribute having a value, the computer program product comprising:

a recording medium;

means, recorded on the recording medium, for directing the computer system to partition the values of each quantitative attribute from a selected group of quantitative attributes into a respective plurality of intervals;

means, recorded on the recording medium, for directing the computer system to determine a support for each value of the categorical attributes and the non-partitioned quantitative attributes, and a support for each interval of the partitioned quantitative attributes, the support for a value being a number of records in the table whose attribute values include the value, the support for an interval being a number of records in the table whose attribute values are part of the interval;

means, recorded on the recording medium, for directing the computer system, for each quantitative attribute, to combine adjacent values of the attribute if the attribute is not partitioned, or adjacent intervals of the attribute if the attribute is partitioned, into ranges, as long as the support for each range is less than a maximum support;

means, recorded on the recording medium, for directing the computer system to identify items with at least a minimum support, each item representing a quantitative attribute and a range, or a categorical attribute and a value, the items with at least the minimum support making up a seed set;

means, recorded on the recording medium, for directing the computer system to generate candidate itemsets from the seed set, each itemset being a set of items and having a support, the support of the itemset being a number of records in the table which support the itemset;

means, recorded on the recording medium, for directing the computer system to determine frequent itemsets from the candidate itemsets, the frequent itemsets being those itemsets whose support is more than the minimum support, the determined frequent itemsets becoming the next seed set;

means, recorded on the recording medium, for directing the computer system to repeat the steps of generating candidate itemsets and determining frequent itemsets until all the frequent itemsets are found; and

means, recorded on the recording medium, for directing the computer system to output an association rule when the support of a selected frequent itemset bears a predetermined relationship to the support of a subset of the selected frequent itemset, thereby satisfying a minimum confidence constraint, the association rule being an expression of the form XY where X and Y are itemsets.

12. The computer program product as recited in claim 11, wherein the means for directing to partition includes, for each quantitative attribute:

(a) means, recorded on the recording medium, for directing the computer system to determine whether to partition the values of the quantitative attribute into the intervals, based on a measure of partial completeness which indicates potential information loss due to the partitioning; and

(b) if the values of the quantitative attribute are to be partitioned, then;

(i) means, recorded on the recording medium, for directing the computer system to determine a number of partitions into which the values of the quantitative attribute are partitioned, based on the measure of partial completeness; and

(ii) means, recorded on the recording medium, for directing the computer system to partition the values of the quantitative attribute into the intervals.

13. The computer program product as recited in claim 11, wherein the means for directing to generate candidate itemsets includes:

means, recorded on the recording medium for directing the computer system to join the itemsets of the seed set to generate a next set of candidate itemsets; and

means, recorded on the recording medium for directing the computer system to discard any candidate itemset having a subset that is not a frequent itemset.

14. The computer program product as recited in claim 13 further comprises means, recorded on the recording medium for directing the computer system to discard any candidate itemset whose support is more than 1/R, where R is a user-specified interest measure.

15. The computer program product as recited in claim 11 further comprising:

means, recorded on the recording medium for directing the computer system to map, for each categorical attribute, the values of the categorical attribute into a set of consecutive integers;

means, recorded on the recording medium for directing the computer system to map, for each quantitative attribute whose values are partitioned into intervals, the intervals into a set of consecutive integers such that the order of the intervals are preserved; and

means, recorded on the recording medium for directing the computer system to map, for each quantitative attribute whose values are not partitioned into intervals, the values of the quantitative attribute into a set of consecutive integers such that the order of the values are preserved.

16. The computer program product as recited in claim 11 further comprising means, recorded on the recording medium for directing the computer system to discard those association rules that do not satisfy a user-specified interest measure.

17. The computer program product as recited in claim 11, wherein the means for directing to determine frequent itemsets includes:

(a) means, recorded on the recording medium for directing the computer system to divide the candidate itemsets into groups, each group including the candidate itemsets that have common quantitative and categorical attributes, and common values for the respective common categorical attributes;

(b) means, recorded on the recording medium for directing the computer system to replace each group with a super-candidate, each super-candidate having (i) the common categorical attributes and their respective values, and (ii) a data structure representing the common quantitative attributes and their values;

(c) means, recorded on the recording medium for directing the computer system, for each record of the table, to;

(i) determine which super-candidates are supported by the categorical attributes in the record; and

(ii) update the data structure for each determined super-candidate with the values of the quantitative attributes in the record; and

(d) means, recorded on the recording medium for directing the computer system to determine the support for each candidate itemset using the data structures of the super-candidates.

18. The computer program product as recited in claim 17 further comprising:

means, recorded on the recording medium for directing the computer system to enter the super-candidates into a hash-tree data structure; and

wherein the means for directing to determine which super-candidates is based on the hash-tree data structure.

19. The computer program product as recited in claim 17, wherein:

the data structure is multi-dimensional tree having a plurality of hyper-rectangles, each hyper-rectangle corresponding to a candidate itemset of the super-candidate and having a plurality of boundaries and dimensions, the boundaries of the hyper-rectangle in the n-th dimension corresponding, respectively, to the ranges of the n-th quantitative attribute of the candidate itemset, whereby the values of the quantitative attributes in a record correspond to an n-dimensional point; and

the means for directing to update the data structure includes means, recorded on the recording medium for directing the computer system to increment a support count for each hyper-rectangle that contains the n-dimensional point corresponding to the quantitative attributes of the record.

20. The computer program product as recited in claim 17, wherein:

the data structure is an n-dimensional array having a plurality of cells and a plurality of hyper-rectangles, n being the number of the common quantitative attributes in the respective super-candidate, each dimension of the array corresponding to a common quantitative attribute, the number of cells in a j-th dimension of the array being equal to the number of partitions of the common quantitative attribute if the common quantitative attribute is partitioned, or the number of values of the common quantitative attribute if the common quantitative attribute is not partitioned, each hyper-rectangle corresponding to a candidate itemset, and the values of the quantitative attributes in a record corresponding to an n-dimensional point;

the means for directing to update the data structure includes means, recorded on the recording medium for directing the computer system to increment a support count for a cell corresponding to the n-dimensional point; and

the means for directing to determine a support for each candidate itemset includes means, recorded on the recording medium for directing the computer system to add, for each candidate itemset replaced by the super-candidate, the support counts of all the cells within the hyper-rectangle corresponding to the quantitative attribute of the candidate itemset, in order to obtain the support for the candidate itemset.

21. A computer-based system for identifying quantitative association rules from a table of records, each record having a plurality of attributes associated therewith, the attributes including quantitative and categorical attributes, each attribute having a value, the system comprising:

means for partitioning the values of each quantitative attribute from a selected group of quantitative attributes into a respective plurality of intervals;

means for determining a support for each value of the categorical attributes and the non-partitioned quantitative attributes, and a support for each interval of the partitioned quantitative attributes, the support for a value being a number of records in the table whose attribute values include the value, the support for an interval being a number of records in the table whose attribute values are part of the interval;

means for combining, for each quantitative attribute, adjacent values of the attribute if the attribute is not partitioned, or adjacent intervals of the attribute if the attribute is partitioned, into ranges, as long as the support for each range is less than a maximum support;

means for identifying items with at least a minimum support, each item representing a quantitative attribute and a range, or a categorical attribute and a value, the items with at least the minimum support making up a seed set;

means for generating candidate itemsets from the seed set, each itemset being a set of items and having a support, the support of the itemset being a number of records in the table which support the itemset;

means for determining frequent itemsets from the candidate itemsets, the frequent itemsets being those itemsets whose support is more than the minimum support, the determined frequent itemsets becoming the next seed set;

means for repeating the operation of the means for generating candidate itemsets and means for determining frequent itemsets until a. II the frequent itemsets are found; and

means for outputting an association rule when the support of a selected frequent itemset bears a predetermined relationship to the support of a subset of the selected frequent itemset, thereby satisfying a minimum confidence constraint, the association rule being an expression of the form XY where X and Y are itemsets.

22. The system as recited in claim 21, wherein the means for partitioning includes, for each quantitative attribute:

(a) means for determining whether to partition the values of the quantitative attribute into the intervals, based on a measure of partial completeness which indicates potential information loss due to the partitioning; and

(b) if the values of the quantitative attribute are to be partitioned, then;

(i) means for determining a number of partitions into which the values of the quantitative attribute are partitioned, based on the measure of partial completeness; and

(ii) means for partitioning the values of the quantitative attribute into the intervals.

23. The system as recited in claim 21, wherein the means for generating candidate itemsets includes:

means for joining the itemsets of the seed set to generate a next set of candidate itemsets; and

means for discarding any candidate itemset having a subset that is not a frequent itemset.

24. The system as recited in claim 23 further comprising means for discarding any candidate itemset whose support is more than 1/R, where R is a user-specified interest measure.

25. The system as recited in claim 21 further comprising:

means for mapping, for each categorical attribute, the values of the categorical attribute into a set of consecutive integers;

means for mapping, for each quantitative attribute whose values are partitioned into intervals, the intervals into a set of consecutive integers such that the order of the intervals are preserved; and

means for mapping, for each quantitative attribute whose values are not partitioned into intervals, the values of the quantitative attribute into a set of consecutive integers such that the order of the values are preserved.

26. The system as recited in claim 21 further comprising means for discarding those association rules that do not satisfy a user-specified interest measure.

27. The system as recited in claim 21, wherein the means for determining frequent itemsets includes:

(a) means for dividing the candidate itemsets into groups, each group including the candidate itemsets that have common quantitative and categorical attributes, and common values for the respective common categorical attributes;

(b) means for replacing each group with a super-candidate, each super-candidate having (i) the common categorical attributes and their respective values, and (ii) a data structure representing the common quantitative attributes and their values;

(c) for each record of the table;

(i) means for determining which super-candidates are supported by the categorical attributes in the record; and

(ii) means for updating the data structure for each determined super-candidate with the values of the quantitative attributes in the record; and

(d) means for determining the support for each candidate itemset using the data structures of the super-candidates.

28. The system as recited in claim 27 further comprising:

means for entering the super-candidates into a hash-tree data structure; and

wherein the means for determining which super-candidates is based on the hash-tree data structure.

29. The system as recited in claim 27, wherein:

the data structure is a multi-dimensional tree having a plurality of hyper-rectangles, each hyper-rectangle corresponding to a candidate itemset and having a plurality of boundaries and a plurality of dimensions, the boundaries of the hyper-rectangle in the n-th dimension corresponding, respectively, to the ranges of the n-th quantitative attribute of the candidate itemset, whereby the values of the quantitative attributes in a record correspond to an n-dimensional point; and

the means for updating the data structure includes means for incrementing a support count for each hyper-rectangle that contains the n-dimensional point corresponding to the quantitative attributes of the record.

30. The system as recited in claim 27, wherein:

the data structure is an n-dimensional array having a plurality of cells and a plurality of hyper-rectangles, n being the number of the common quantitative attributes in the respective super-candidate, each dimension of the array corresponding to a common quantitative attribute, the number of cells in a j-th dimension of the array being equal to the number of partitions of the common quantitative attribute if the common quantitative attribute is partitioned, or the number of values of the common quantitative attribute if the common quantitative attribute is not partitioned, each hyper-rectangle corresponding to a candidate itemset, and the values of the quantitative attributes in a record corresponding to an n-dimensional point;

the means for updating the data structure includes means for incrementing a support count for a cell corresponding to the n-dimensional point; and

the means for determining a support for each candidate itemset includes means for adding, for each candidate itemset replaced by the super-candidate, the support counts of all the cells within the hyper-rectangle corresponding to the quantitative attribute of the candidate itemset, in order to obtain the support for the candidate itemset.