Methods and apparatus for mining attribute associations

• US 7,243,100 B2
• Filed: 07/30/2003
• Issued: 07/10/2007
• Est. Priority Date: 07/30/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-Lung, Wang, Haixun, Perng, Chang-shing, Ma, Sheng
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US10/630,992
• Publication Number:
  US 20050027710A1
• Time in Patent Office: 1,441 Days
• Field of Search: 707 1- 7, 707100-103 R, 707/104.1, 707/200, 706 45- 50, 706/52, 709218-220, 700 30- 31, 700/44
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Attribute association discovery techniques that support relational-based data mining are disclosed. In one aspect of the invention, a technique for mining attribute associations in a relational data set comprises the following steps/operations. Multiple items are obtained from the relational data set. Then, attribute associations are discovered using: (i) multi-attribute mining templates formed from at least a portion of the multiple items; and (ii) one or more mining preferences specified by a user. The invention provides a novel architecture for the mining search space so as to exploit the inter-relationships among patterns of different templates. The framework is relational-sensitive and supports interactive and online mining.

Claims

1. A method of mining attribute associations in a relational data set, comprising the steps of:

inputting multiple items from the relational data set;

discovering attribute associations using;

(i) multi-attribute mining templates formed from at least a portion of the multiple items, wherein each multi-attribute mining template comprises at least one item described by at least two attributes; and

(ii) one or more mining preferences specified by a user, wherein the one or more mining preferences specified by the user comprise specification of at least one of;

(a) one or more desired multi-attribute mining templates;

(b) one or more irrelevant multi-attribute mining templates; and

(c) one or more rules concerning values of attributes in the multi-attribute mining templates, further wherein the attribute association discovering step further comprises generating candidate patterns at a template level, wherein candidate patterns of multi-attribute mining templates are derived by merge-joining patterns of nodes of at least a portion of the templates without pre-sorting; and

outputting the discovered attribute associations to at least one of the user and another system;

wherein the multi-attribute mining templates are related by an anti-monotonicity property such that the property holds when mining top-down from k-itemsets to (k+1)-itemsets and when mining items defined by a set of k attributes to items defined by k+1 attributes.

2. The method of claim 1, wherein the candidate pattern generating step further comprises maintaining one or more occurrence buffers to count occurrences of patterns.

3. The method of claim 1, wherein the attribute association discovering step further comprises pruning candidate patterns at a template level.

4. Apparatus for mining attribute associations in a relational data set, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) input multiple items from the relational data set;

(ii) discover attribute associations using;

(i) multi-attribute mining templates formed from at least a portion of the multiple items, wherein each multi-attribute mining template comprises at least one item described by at least two attributes; and

(ii) one or more mining preferences specified by a user, wherein the one or more mining preferences specified by the user comprise specification of at least one of;

(a) one or more desired multi-attribute mining templates;

(b) one or more irrelevant multi-attribute mining templates; and

(c) one or more rules concerning values of attributes in the multi-attribute mining templates, further wherein the attribute association discovering operation further comprises generating candidate patterns at a template level, wherein candidate patterns of multi-attribute mining templates are derived by merge-joining patterns of nodes of at least a portion of the templates without pre-sorting; and

(iii) output the discovered attribute associations to at least one of the user and another system;

wherein the multi-attribute mining templates are related by an anti-monotonicity property such that the property holds when mining top-down from k-itemsets to (k+1)-itemsets and when mining items defined by a set of k attributes to items defined by k+1 attributes.

5. The apparatus of claim 4, wherein the candidate pattern generating operation further comprises maintaining one or more occurrence buffers to count occurrences of patterns.

6. The apparatus of claim 4, wherein the attribute association discovering operation further comprises pruning candidate patterns at a template level.

7. An article of manufacture for mining attribute associations in a relational data set, comprising a computer readable storage medium containing executable program code which implements the steps of:

inputting multiple items from the relational data set;

discovering attribute associations using;

(i) multi-attribute mining templates formed from at least a portion of the multiple items, wherein each multi-attribute mining template comprises at least one item described by at least two attributes; and

(ii) one or more mining preferences specified by a user, wherein the one or more mining preferences specified by the user comprise specification of at least one of;

(a) one or more desired multi-attribute mining templates;

(b) one or more irrelevant multi-attribute mining templates; and

(c) one or more rules concerning values of attributes in the multi-attribute mining templates, further wherein the attribute association discovering step further comprises generating candidate patterns at a template level, wherein candidate patterns of multi-attribute mining templates are derived by merge-joining patterns of nodes of at least a portion of the templates without pre-sorting; and

outputting the discovered attribute associations to at least one of the user and another system;

wherein the multi-attribute mining templates are related by an anti-monotonicity property such that the property holds when mining top-down from k-itemsets to (k+1)-itemsets and when mining items defined by a set of k attributes to items defined by k+1 attributes.

8. The article of claim 7, wherein the candidate pattern generating step further comprises maintaining one or more occurrence buffers to count occurrences of patterns.

9. The article of claim 7, wherein the attribute association discovering step further comprises pruning candidate patterns at a template level.