System and method for data mining from relational data by sieving through iterated relational reinforcement

• US 5,884,305 A
• Filed: 06/13/1997
• Issued: 03/16/1999
• Est. Priority Date: 06/13/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Raghavan, Prabhakar, Kleinberg, Jon Michael
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/874,381
• Time in Patent Office: 641 Days
• Field of Search: 707/7, 707/6, 707/1, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. A method as recited in claim 1, wherein the step of performing a computation is performed a plurality of times, iteratively.

7. 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.

8. 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.

9. 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.

10. 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.

11. A method as recited in claim 1, wherein the step of deriving includes providing, as an output, the associated values.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. A system as recited in claim 16, wherein the means for performing a computation is operative a plurality of times, iteratively.

22. 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.

23. 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.

24. 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.

25. 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.

26. A system as recited in claim 16, wherein the means for deriving includes means for providing, as an output, the associated values.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.