Method and apparatus for data mining to discover associations and covariances associated with data

• US 20040073534A1
• Filed: 10/11/2002
• Published: 04/15/2004
• Est. Priority Date: 10/11/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Robson, Barry
• Granted Patent: US 7,043,476 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16H 10/60 for patient-specific data, e.g. for electronic patient records
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Data mining techniques are provided which are effective and efficient for discovering useful information from an amorphous collection or data set of records. For example, the present invention provides for the mining of data, e.g., of several or many records, to discover interesting associations between entries of qualitative text, and covariances between data of quantitative numerical types, in records. Although not limited thereto, the invention has particular application and advantage when the data is of a type such as clinical, pharmacogenomic, forensic, police and financial records, which are characterized by many varied entries, since the problem is then said to be one of “high dimensionality” which has posed mathematical and technical difficulties for researchers. This is especially true when considering strong negative associations and negative covariance, i.e., between items of data which may so rarely come together that their concurrence is never seen in any record, yet the fact that this is not expected is of potential great interest.

Claims

1. An automated method of discovering information relating to a collection of input data, the method comprising the steps of:

obtaining the collection of input data, wherein the collection of input data comprises data items;

discovering information relating to the collection of input data based on a computation of a mutual information measure in accordance with at least a portion of the data items, wherein expected values of the mutual information measure are expressed as linear combinations of an incomplete Riemann zeta function; and

outputting at least a portion of results associated with the computation of the mutual information measure, wherein at least a portion of the results represent the discovered information relating to the collection of input data.

2. The method of claim 1, wherein the mutual information measure is represented as I[a;

b;

c;

. . . ;

M]=ζ

[s=1, n(a, b, c, . . . , M)−

1]−

ζ

[s=1, ε

(a, b, c, . . . , M)−

1], wherein I represents the measure computed with respect to M items, n represents the actual number of items, ζ

represents the Riemann zeta function, ε

represents an expected frequency, the subtraction of one represents a Dirichlet prior density, and s represents an adjustable parameter.

3. The method of claim 1, wherein the collection of input data comprises at least one of qualitative data and quantitative data.

4. The method of claim 1, wherein the information discovery step comprises an association analysis when the collection of input data is qualitative data.

5. The method of claim 4, wherein the association analysis is capable of discovering negative associations.

6. The method of claim 1, wherein the information discovery step comprises a covariance analysis when the collection of input data is quantitative data.

7. The method of claim 1, wherein the information discovery step comprises encoding the data items in association with prime numbers.

8. The method of claim 7, wherein a given prime number is assigned to a type of data item based on a frequency of occurrence of the data item type in the collection of input data.

9. The method of claim 7, wherein, when the collection of input data comprises one or more records and each of the one or more records comprise data items, the information discovery step further comprises encoding each record as a product of the prime numbers representing the data items in the record or as a sum of the logarithms of the prime numbers representing the data items in the record.

10. The method of claim 9, further comprising the step of generating one or more subrecords from a record.

11. The method of claim 9, further comprising the step of determining similarity between two records by comparing the respective products of the two records or the respective sums of the two records.

12. Apparatus for discovering information relating to a collection of input data, the apparatus comprising:

at least one processor operative to;

(i) obtain the collection of input data, wherein the collection of input data comprises data items;

(ii) discover information relating to the collection of input data based on a computation of a mutual information measure in accordance with at least a portion of the data items, wherein expected values of the mutual information measure are expressed as linear combinations of an incomplete Riemann zeta function; and

(iii) output at least a portion of results associated with the computation of the mutual information measure, wherein at least a portion of the results represent the discovered information relating to the collection of input data; and

memory, coupled to the at least one processor, for storing at least a portion of results associated with one or more of the obtaining, discovering and outputting operations.

13. The apparatus of claim 12, wherein the mutual information measure is represented as I[a;

b;

c;

. . . ;

M]=ζ

[s=1, n(a, b, c, . . . , M)−

1]−

ζ

[s=1, ε

(a, b, c, . . . , M)−

1], wherein I represents the measure computed with respect to M items, n represents the actual number of items, ζ

represents the Riemann zeta function, ε

represents an expected frequency, the subtraction of one represents a Dirichlet prior density, and s represents an adjustable parameter.

14. The apparatus of claim 12, wherein the collection of input data comprises at least one of qualitative data and quantitative data.

15. The apparatus of claim 12, wherein the information discovery operation comprises an association analysis when the collection of input data is qualitative data.

16. The apparatus of claim 15, wherein the association analysis is capable of discovering negative associations.

17. The apparatus of claim 12, wherein the information discovery operation comprises a covariance analysis when the collection of input data is quantitative data.

18. The apparatus of claim 12, wherein the information discovery operation comprises encoding the data items in association with prime numbers.

19. The apparatus of claim 18, wherein a given prime number is assigned to a type of data item based on a frequency of occurrence of the data item type in the collection of input data.

20. The apparatus of claim 18, wherein, when the collection of input data comprises one or more records and each of the one or more records comprise data items, the information discovery operation further comprises encoding each record as a product of the prime numbers representing the data items in the record or as a sum of the logarithms of the prime numbers representing the data items in the record.

21. The apparatus of claim 20, wherein the at least one processor is further operative to generate one or more subrecords from a record.

22. The apparatus of claim 20, wherein the at least one processor is further operative to determine similarity between two records by comparing the respective products of the two records or the respective sums of the two records.

23. An article of manufacture for discovering information relating to a collection of input data, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining the collection of input data, wherein the collection of input data comprises data items;

discovering information relating to the collection of input data based on a computation of a mutual information measure in accordance with at least a portion of the data items, wherein expected values of the mutual information measure are expressed as linear combinations of an incomplete Riemann zeta function; and

outputting at least a portion of results associated with the computation of the mutual information measure, wherein at least a portion of the results represent the discovered information relating to the collection of input data.