US5983222A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for computing association rules for data mining in large database
Assignee: International Business Machines Corp
•
Filing: 1996-10-25
•
Granted: 1999-11-09
•
Expires: 2016-10-25
Abstract
Abstract A method is disclosed for computing an association rule in a database having numerical attributes and 0-1 attributes. First, a numerical attribute is divided into a plurality of intervals (or buckets), and each data set is placed into a single bucket according to the value of the numerical attribute. The number of data sets in each bucket and the number of data sets with a 0-1 attribute being 1 are counted. Second, the starting bucket of an interval to be detected is to be detected. Third, the terminating bucket corresponding to the starting bucket is detected. That is, the largest interval with a confidence equal to or larger than a predetermined value. Fourth, one of the detected pairs of starting and terminating buckets which includes the largest number of customers is the answer to this question. Finally, the required data attributes of data included in this interval is subsequently retrieved.
Inventors
- 👤 Yasuhiko Morimoto
- 👤 Takeshi Fukuda
- 👤 Shinichi Morishida
- 👤 Takeshi Tokuyama
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:42
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
200 words
A database retrieval method for retrieving data in a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, by computing an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is α or higher and a maximum number of data sets exist, the method comprising the steps of: counting the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute, and counting the number of those data sets in each bucket, whose 0-1 attributes are 1; determining a starting index s so that ##EQU9## is satisfied, where u i is the number of data sets included in a bucket, and v i is the number of data sets in a bucket whose 0-1 attributes are 1; determining a maximum terminating index t that is equal to or larger than said determined starting index s, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; selecting an interval [s, t] with the largest number of data sets; and retrieving data from the database included in said interval [s, t].
Claim 2
Dependent Claim
200 words
A database retrieval method for retrieving data in a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, by computing an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is α or higher and a maximum number of data sets exist, the method comprising the steps of: counting the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute, and counting the number of those data sets in each bucket, whose 0-1 attributes are 1; determining a starting index s so that ##EQU9## is satisfied, where u i is the number of data sets included in a bucket, and v i is the number of data sets in a bucket whose 0-1 attributes are 1; determining a maximum terminating index t that is equal to or larger than said determined starting index s, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; selecting an interval [s, t] with the largest number of data sets; and retrieving data from the database included in said interval [s, t].
Claim 3
Dependent Claim
25 words
The database retrieval method according to claim 1, wherein each said bucket is set so as to include a substantially identical number of data sets.
Claim 4
Dependent Claim
83 words
The database retrieval method according to claim 1, wherein said counting step comprises the steps of: randomly sampling X of said N data sets; sorting said X data sets according to the value of said numerical attribute; storing the value of said numerical attribute of the i×X/M-th of the sorted data sets, where i=1, 2, . . . , M-1, and M is the number of buckets; and counting the number of data sets included in each bucket, based on said stored value.
Claim 5
Dependent Claim
74 words
The database retrieval method according to claim 1, wherein the step of determining a starting index comprises the steps of: judging whether or not w<0 and v s-1 -αu s-1 ≧0; if the result of said judging step is positive, then setting w=v s-1 -αu s-1 and determining whether or not w<0; and if the result of said judging step is negative, then setting w=w+v s-1 -αu s-1 and determining whether or not w<0.
Claim 6
Dependent Claim
31 words
The database retrieval method according to claim 1, wherein said terminating index determining step starts with an operation for determining a terminating index t corresponding to the largest starting index s.
Claim 7
Dependent Claim
48 words
The database retrieval method according to claim 5, wherein a terminating index t corresponding to one starting index s is determined by processing a value equal to or less than a terminating index t' corresponding to a starting index s' processed immediately before said one starting index s.
Claim 8
Dependent Claim
212 words
A database retrieval apparatus for retrieving data in a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, by computing an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is α or higher and a maximum number of data sets exist, the apparatus comprising: means for counting the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute, and for counting the number of data sets in each bucket whose 0-1 attributes are 1; means for determining a starting index s so that ##EQU10## is satisfied, where u i is the number of data sets included in a bucket, and v i is the number of data sets in a bucket, whose 0-1 attributes are 1; means for determining a maximum terminating index t that is equal to or larger than s, s being determined by said starting index determining means, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; means for selecting an interval [s, t] with the largest number of data sets; and means for retrieving data from the database included in said interval [s, t].
Claim 9
Dependent Claim
212 words
A database retrieval apparatus for retrieving data in a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, by computing an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is α or higher and a maximum number of data sets exist, the apparatus comprising: means for counting the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute, and for counting the number of data sets in each bucket whose 0-1 attributes are 1; means for determining a starting index s so that ##EQU10## is satisfied, where u i is the number of data sets included in a bucket, and v i is the number of data sets in a bucket, whose 0-1 attributes are 1; means for determining a maximum terminating index t that is equal to or larger than s, s being determined by said starting index determining means, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; means for selecting an interval [s, t] with the largest number of data sets; and means for retrieving data from the database included in said interval [s, t].
Claim 10
Dependent Claim
25 words
The database retrieval apparatus according to claim 7, wherein each said bucket is set so as to include a substantially identical number of data sets.
Claim 11
Dependent Claim
88 words
The database retrieval apparatus according to claim 7, wherein said counting means comprises: means for randomly sampling X of said N data sets; means for sorting said X data sets according to the value of said numerical attribute; means for storing the value of said numerical attribute of the i×X/M-th of the sorted data sets, for i=1, 2, . . . , M-1 where M is the number of buckets; and means for counting the number of data sets included in each bucket, based on said stored value.
Claim 12
Dependent Claim
73 words
The database retrieval apparatus according to claim 7, wherein said starting index detecting means comprises: means for judging whether or not w<0 and v s-1 -αu s-1 ≧0; means for setting w=v s-1 -αu s-1 and determining whether or not w<0 if the result of said judging step is positive; and means for setting w=w+v s-1 -αu s-1 and determining whether or not w<0, if the result of said judging step is negative.
Claim 13
Dependent Claim
31 words
The database retrieval apparatus according to claim 7, wherein said terminating index determining means starts with an operation for determining a terminating index t corresponding to the largest starting index s.
Claim 14
Dependent Claim
48 words
The database retrieval apparatus according to claim 11, wherein a terminating index t corresponding to one starting index s is determined by processing a value equal to or less than a terminating index t' corresponding to a starting index s' processed immediately before said one starting index s.
Claim 15
Dependent Claim
242 words
A computer readable medium comprising program code means for causing a computer connected to a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, to compute an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is equal to or greater than α and the maximum number of data sets exists, said program code means comprising: program code means for causing said computer to count the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute to count the number of data sets in each bucket, whose 0-1 attributes are 1; starting index determining program code means for causing said computer to determine a starting index s so that ##EQU11## is satisfied, where u i is the number of data sets included in a bucket, and v i is the rate of those data sets in a bucket, whose 0-1 attributes are 1; terminating index determining program code means for causing said computer to determine a maximum terminating index t that is equal to or larger than s, s being determined by said starting index determining program code means, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; and program code means for causing said computer to select a interval [s, t] with the largest number of data sets.
Claim 16
Dependent Claim
242 words
A computer readable medium comprising program code means for causing a computer connected to a database having a plurality of data sets, each said data set including a numerical attribute and a 0-1 attribute, to compute an interval of said numerical attribute in which the probability of said 0-1 attribute being 1 is equal to or greater than α and the maximum number of data sets exists, said program code means comprising: program code means for causing said computer to count the number of data sets included in each bucket which is arranged along an axis corresponding to said numerical attribute to count the number of data sets in each bucket, whose 0-1 attributes are 1; starting index determining program code means for causing said computer to determine a starting index s so that ##EQU11## is satisfied, where u i is the number of data sets included in a bucket, and v i is the rate of those data sets in a bucket, whose 0-1 attributes are 1; terminating index determining program code means for causing said computer to determine a maximum terminating index t that is equal to or larger than s, s being determined by said starting index determining program code means, wherein the probability of said 0-1 attribute being 1 is α or higher between s and t; and program code means for causing said computer to select a interval [s, t] with the largest number of data sets.
Claim 17
Dependent Claim
25 words
The computer readable medium according to claim 13, wherein each said bucket is set so as to include a substantially identical number of data sets.
Claim 18
Dependent Claim
115 words
The computer readable medium according to claim 13, wherein said counting program code means comprises: program code means for causing said computer to randomly sample X of said N data sets; program code means for causing said computer to sort said X data sets according to the value of said numerical attribute; program code means for causing said computer to store the value of said numerical attribute of the i×X/M-th of the sorted data sets, for i=1, 2, . . . , M-1 where M is the number of buckets; and program code means for causing said computer to count the number of data sets corresponding to each data set, based on said stored value.
Claim 19
Dependent Claim
94 words
The computer readable medium according to claim 13, wherein said starting index determining program code means comprises: judging program code means for causing said computer to judge whether or not w<0 and v s-1 -αu s-1 ≧0; program code means for causing the computer to set w=v s-1 -αu s-1 and determine whether or not w<0 if the result of said judging means is positive; and program code means for causing the computer to set w=w+v s-1 -αu s-1 and determine whether or not w<0 if the result of said judging means is negative.
Claim 20
Dependent Claim
37 words
The computer readable medium according to claim 13, wherein said terminating index determining program code means causes the computer to start with an operation for determining a terminating index t corresponding to the largest starting index s.
Claim 21
Dependent Claim
48 words
The computer readable medium according to claim 17, wherein a terminating index t corresponding to one starting index s is determined by processing a value equal to or less than a terminating index t' corresponding to a starting index s' processed immediately before said one starting index s.
References Cited (Backward Citations)
US5615341A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |