US5884305A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for data mining from relational data by sieving through iterated relational reinforcement
Assignee: International Business Machines Corp
•
Filing: 1997-06-13
•
Granted: 1999-03-16
•
Expires: 2017-06-13
Abstract
Abstract A system and method are provided for performing the process known as "data mining" on a database of raw data records having common data elements, to obtain categorical cluster rules as to what elements of the data tend to occur in common in multiple records. Initial values are assigned to the elements. In an iterative process, the associated value for each given one of the elements is recalculated based on the values of other elements which occur in records together with the given element. Thus, the associated values will tend to grow for elements occurring together in multiple records. Those common occurrences of elements in multiple records represent categorical cluster rules the owner of the data is likely to want to know about. Thus, these rules may be identified based on the growth of the associated values for the records.
Inventors
- 👤 Jon Michael Kleinberg
- 👤 Prabhakar Raghavan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:51
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/27; G06F16/278; G06F16/24; G06F16/242; G06F16/2425; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
122 words
A method for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the method comprising the steps of: initializing an associated value for each of the elements of the records; performing a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and deriving, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 2
Independent Claim
122 words
A method for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the method comprising the steps of: initializing an associated value for each of the elements of the records; performing a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and deriving, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 3
Dependent Claim
26 words
A method as recited in claim 1, wherein the step of initializing includes initializing the associated values for all of the elements to a constant value.
Claim 4
Dependent Claim
27 words
A method as recited in claim 1, wherein the step of initializing includes initializing the associated values for all of the elements based on a probability distribution.
Claim 5
Dependent Claim
40 words
A method as recited in claim 1, wherein the step of initializing includes: initializing a subset of the associated values based on a first probability distribution; and initializing the associated values outside the subset based on a second probability distribution.
Claim 6
Dependent Claim
38 words
A method as recited in claim 1, wherein the step of initializing includes: initializing a subset of the associated values based on a first probability distribution; and initializing the associated values outside the subset to a constant value.
Claim 7
Dependent Claim
21 words
A method as recited in claim 1, wherein the step of performing a computation is performed a plurality of times, iteratively.
Claim 8
Dependent Claim
55 words
A method as recited in claim 1, wherein the step of performing a computation includes: computing weights for the elements, the weight for each given one of the elements being based on the associated values of other elements contained within the records containing the given element; and updating the associated values based on the weights.
Claim 9
Dependent Claim
43 words
A method as recited in claim 7, wherein the step of computing weights includes, for each given one of the elements, computing an additive weight based on a sum of associated values of other elements contained within records which contain the given element.
Claim 10
Dependent Claim
43 words
A method as recited in claim 7, wherein the step of computing weights includes, for each given one of the elements, computing a multiplicative weight based on a product of associated values of other elements contained within records which contain the given element.
Claim 11
Dependent Claim
39 words
A method as recited in claim 7, wherein the step of performing a computation further includes one of: (i) adding a pre-set additive amount to the associated values; and (ii) scaling the associated values by a pre-set multiplicative amount.
Claim 12
Dependent Claim
20 words
A method as recited in claim 1, wherein the step of deriving includes providing, as an output, the associated values.
Claim 13
Dependent Claim
29 words
A method as recited in claim 11, wherein the step of deriving further includes providing, as an output, a subset of the associated values which meet a predetermined criterion.
Claim 14
Dependent Claim
51 words
A method as recited in claim 12, wherein, in the step of providing, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of the largest values, and (ii) the values that exceed a predetermined threshold value.
Claim 15
Dependent Claim
68 words
A method as recited in claim 12, wherein, in the step of providing, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of values having the largest additive weight, (ii) values whose additive weights exceed a predetermined value, (iii) the largest multiplicative weigh, and (iv) values whose multiplicative weights exceed a predetermined value.
Claim 16
Dependent Claim
59 words
A method as recited in claim 12, wherein the step of deriving further includes: identifying, from the subset of associated values which meet the predetermined criterion, a set of database records having elements whose associated values meet the predetermined criterion; and providing, as an output, the subset of database records, the subset of database records being the categorical cluster.
Claim 17
Independent Claim
125 words
A system for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the system comprising: means for initializing an associated value for each of the elements of the records; means for performing a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and means for deriving, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 18
Independent Claim
125 words
A system for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the system comprising: means for initializing an associated value for each of the elements of the records; means for performing a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and means for deriving, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 19
Dependent Claim
28 words
A system as recited in claim 16, wherein the means for initializing includes means for initializing the associated values for all of the elements to a constant value.
Claim 20
Dependent Claim
29 words
A system as recited in claim 16, wherein the means for initializing includes means for initializing the associated values for all of the elements based on a probability distribution.
Claim 21
Dependent Claim
44 words
A system as recited in claim 16, wherein the means for initializing includes: means for initializing a subset of the associated values based on a first probability distribution; and means for initializing the associated values outside the subset based on a second probability distribution.
Claim 22
Dependent Claim
42 words
A system as recited in claim 16, wherein the means for initializing includes: means for initializing a subset of the associated values based on a first probability distribution; and means for initializing the associated values outside the subset to a constant value.
Claim 23
Dependent Claim
21 words
A system as recited in claim 16, wherein the means for performing a computation is operative a plurality of times, iteratively.
Claim 24
Dependent Claim
59 words
A system as recited in claim 16, wherein the means for performing a computation includes: means for computing weights for the elements, the weight for each given one of the elements being based on the associated values of other elements contained within the records containing the given element; and means for updating the associated values based on the weights.
Claim 25
Dependent Claim
46 words
A system as recited in claim 22, wherein the means for computing weights includes means, operable for each given one of the elements, for computing an additive weight based on a sum of associated values of other elements contained within records which contain the given element.
Claim 26
Dependent Claim
46 words
A system as recited in claim 22, wherein the means for computing weights includes means, operable for each given one of the elements, for computing a multiplicative weight based on a product of associated values of other elements contained within records which contain the given element.
Claim 27
Dependent Claim
41 words
A system as recited in claim 22, wherein the means for performing a computation further includes means for one of: (i) adding a pre-set additive amount to the associated values; and (ii) scaling the associated values by a pre-set multiplicative amount.
Claim 28
Dependent Claim
22 words
A system as recited in claim 16, wherein the means for deriving includes means for providing, as an output, the associated values.
Claim 29
Dependent Claim
31 words
A system as recited in claim 26, wherein the means for deriving further includes means for providing, as an output, a subset of the associated values which meet a predetermined criterion.
Claim 30
Dependent Claim
51 words
A system as recited in claim 27, wherein, in the means for providing, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of the largest values, and (ii) the values that exceed a predetermined threshold value.
Claim 31
Dependent Claim
68 words
A system as recited in claim 27, wherein, in the means for providing, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of values having the largest additive weight, (ii) values whose additive weights exceed a predetermined value, (iii) the largest multiplicative weigh, and (iv) values whose multiplicative weights exceed a predetermined value.
Claim 32
Dependent Claim
63 words
A system as recited in claim 27, wherein the means for deriving further includes: means for identifying, from the subset of associated values which meet the predetermined criterion, a set of database records having elements whose associated values meet the predetermined criterion; and means for providing, as an output, the subset of database records, the subset of database records being the categorical cluster.
Claim 33
Dependent Claim
165 words
A computer program product, for use with a computer system, for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the computer program product comprising: a computer-usable medium; means, provided on the medium, for directing the computer system to initialize an associated value for each of the elements of the records; means, provided on the medium, for directing the computer system to perform a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and means, provided on the medium, for directing the computer system to derive, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 34
Dependent Claim
165 words
A computer program product, for use with a computer system, for extracting elements satisfying a predetermined criterion of correlation (a "categorical cluster") from a body of data, the data including a plurality of records, the records containing elements from among a set of common fields, the elements having respective values, some of the values being common to different ones of the records, the computer program product comprising: a computer-usable medium; means, provided on the medium, for directing the computer system to initialize an associated value for each of the elements of the records; means, provided on the medium, for directing the computer system to perform a computation to update the associated values based on the associated values of other elements, the computation causing the associated values to change value in a manner related to a degree of correlation; and means, provided on the medium, for directing the computer system to derive, from the updated associated values, a categorical cluster rule which identifies highly correlated elements.
Claim 35
Dependent Claim
41 words
A computer program product as recited in claim 31, wherein the means for directing to initialize includes means, provided on the medium, for directing the computer system to initialize the associated values for all of the elements to a constant value.
Claim 36
Dependent Claim
42 words
A computer program product as recited in claim 31, wherein the means for directing to initialize includes means, provided on the medium, for directing the computer system to initialize the associated values for all of the elements based on a probability distribution.
Claim 37
Dependent Claim
66 words
A computer program product as recited in claim 31, wherein the means for directing to initialize includes: means, provided on the medium, for directing the computer system to initialize a subset of the associated values based on a first probability distribution; and means, provided on the medium, for directing the computer system to initialize the associated values outside the subset based on a second probability distribution.
Claim 38
Dependent Claim
64 words
A computer program product as recited in claim 31, wherein the means for directing to initialize includes: means, provided on the medium, for directing the computer system to initialize a subset of the associated values based on a first probability distribution; and means, provided on the medium, for directing the computer system to initialize the associated values outside the subset to a constant value.
Claim 39
Dependent Claim
25 words
A computer program product as recited in claim 31, wherein the means for directing to perform a computation is operable a plurality of times, iteratively.
Claim 40
Dependent Claim
81 words
A computer program product as recited in claim 31, wherein the means for directing to perform a computation includes: means, provided on the medium, for directing the computer system to compute weights for the elements, the weight for each given one of the elements being based on the associated values of other elements contained within the records containing the given element; and means, provided on the medium, for directing the computer system to update the associated values based on the weights.
Claim 41
Dependent Claim
59 words
A computer program product as recited in claim 37, wherein the means for directing to compute weights includes means, provided on the medium, operable for each given one of the elements, for directing the computer system to computing an additive weight based on a sum of associated values of other elements contained within records which contain the given element.
Claim 42
Dependent Claim
59 words
A computer program product as recited in claim 37, wherein the means for directing to compute weights includes means, provided on the medium, operable for each given one of the elements, for directing the computer system to compute a multiplicative weight based on a product of associated values of other elements contained within records which contain the given element.
Claim 43
Dependent Claim
54 words
A computer program product as recited in claim 37, wherein the means for directing to perform a computation further includes means, provided on the medium, for directing the computer system to one of: (i) add a pre-set additive amount to the associated values; and (ii) scale the associated values by a pre-set multiplicative amount.
Claim 44
Dependent Claim
35 words
A computer program product as recited in claim 31, wherein the means for directing to derive includes means, provided on the medium, for directing the computer system to provide, as an output, the associated values.
Claim 45
Dependent Claim
44 words
A computer program product as recited in claim 41, wherein the means for directing to derive further includes means, provided on the medium, for directing the computer system to provide, as an output, a subset of the associated values which meet a predetermined criterion.
Claim 46
Dependent Claim
55 words
A computer program product as recited in claim 42, wherein, in the means for directing to provide, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of the largest values, and (ii) the values that exceed a predetermined threshold value.
Claim 47
Dependent Claim
72 words
A computer program product as recited in claim 42, wherein, in the means for directing to provide, as an output, a subset of the associated values which meet a predetermined criterion, the predetermined criterion is one of (i) a predetermined number of values having the largest additive weight, (ii) values whose additive weights exceed a predetermined value, (iii) the largest multiplicative weigh, and (iv) values whose multiplicative weights exceed a predetermined value.
Claim 48
Dependent Claim
85 words
A computer program product as recited in claim 42, wherein the means for directing to derive further includes: means, provided on the medium, for directing the computer system to identify, from the subset of associated values which meet the predetermined criterion, a set of database records having elements whose associated values meet the predetermined criterion; and means, provided on the medium, for directing the computer system to provide, as an output, the subset of database records, the subset of database records being the categorical cluster.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-15 | 2002-09-14 | 2003-03-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-15 | 2006-09-14 | 2007-03-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-15 | 2010-09-14 | 2011-03-16 | $7700.00 | Window Closed / Lapsed |