Mining of generalized disjunctive association rules

• US 6,754,651 B2
• Filed: 04/17/2001
• Issued: 06/22/2004
• Est. Priority Date: 04/17/2001
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Krishnapuram, Raghuram, Nanavati, Amit Anil, Chitrapura, Krishna Prasad, Joshi, Sachindra
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): EHICHIOYA, FRED I
• Application Number:
  US09/836,118
• Publication Number:
  US 20020152201A1
• Time in Patent Office: 1,162 Days
• Field of Search: 705/10, 705/1, 705/3, 705/7, 705/51, 706/12, 706/47, 706/42, 706/4, 706/8, 706/10, 706/13, 706/21, 706/25, 706/45, 706/46, 706/52, 706/59, 706/60, 707/3, 707/6, 707/12, 707/104.1, 707/2, 707/10, 707/102, 438/118, 709/213, 709/244, 709/248, 709/250, 709/400
• US Class Current: 707/694
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/961 Associative
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The present invention provides a system and a method for mining a new kind of association rules called disjunctive association rules, where the antecedent or the consequent of a rule may contain disjuncts of terms (XY or X⊕Y). Such rules are a natural generalisation to the kind of rules that have been mined hitherto. Furthermore, disjunctive association rules are generalised in the sense that the algorithm also mines rules which have disjunctions of conjuncts (C(AB)(DE)). Since the number of combinations of disjuncts is explosive, we use clustering to find a generalized subset. The said clustering is preferably performed using agglomerative clustering methods for finding the greedy subset.

Claims

1. A method for mining data, wherein said method generates generalized disjunctive association rules to capture local relationships between data items with reference to a given context comprising any arbitrary subset of a set of transactions in order to provide improved data analysis independently of taxonomies, said method comprising:

generating a list of all possible data items that can influence said context, discovering disjunctive association rules for data items in said list that co-occur based on a defined overlap threshold within said context,

using a cutoff parameter to eliminate trivial data items from said list, wherein said trivial data items create trivial disjunctive association rules having disjunctive antecedents or consequents greater than disjunctive antecedents or consequents of said disjunctive association rules occurring in said defined overlap threshold,

clustering said data items to form a set of generalized disjunctive rules based on a defined confidence/support threshold, and

iterating the above steps until all items in said list are covered.

2. The method as claimed in claim 1, wherein said list is generated by selecting those data items that have a significant overlap with said context.

3. The method as claimed in claim 1, wherein said disjunctive association rules are discovered by merging data items that overlap above said defined threshold within said context and confirmation that the strength of the relation is beyond a defined minimum support value.

4. The method as claimed in claim 3, wherein the discovery of said disjunctive association rules uses a functionally complete set of operators including “

AND”

, “

OR”

, NOT” and

“

EXCLUSIVE-OR”

.

5. The method as claimed in claim 1, wherein said clustering is agglomerative.

6. The method as claimed in claim 1, applied to clustering of query results in a search engine where the query is the context, a word is mapped to an item, a document to a transaction, the recall is the confidence, and the resulting disjuncts are the labels of the clusters of documents.

7. The method as claimed in claim 6 extended to interactive query refinement.

8. The method as claimed in claim 1, applied to customer targeting by determining generalized disjunctive association rules on data such as customer purchase history, customer segments, product information and the like.

9. The method as claimed in claim 1, used for making recommendations to customers where the customer'"'"'s purchase history is the context and the generalized disjunctive association rules provide the recommendations.

10. The method as claimed in claim 1, applied to gene analysis by finding the generalized disjunctive association rules from gene databases.

11. The method as claimed in claim 1, applied to cause-and-effect analysis in applications such as medical analysis, market survey analysis and census analysis, by finding generalized disjunctive association rules from the database of causes and effects.

12. The method as claimed in claim 1, applied to fraud detection by finding generalized disjunctive association rules from transaction databases.

13. The method in claim 1, wherein support of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent, divided by the total number of transactions.

14. The method in claim 1, wherein confidence of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent, divided by the cardinality of the union of disjunctive terms in the antecedent.

15. A system for mining data, and operable for generalized disjunctive association rules to capture local relationships between data items with reference to a given context comprising any arbitrary subset of a set of transactions in order to provide improved data analysis independently of taxonomies, said system comprising:

means for generating a list of all possible data items that can influence said context,

means for discovering disjunctive association rules for data items in said list that co-occur based on a defined overlap threshold within said context,

means for using a cutoff parameter to eliminate trivial data items from said list, wherein said trivial data items create trivial disjunctive association rules having disjunctive antecedents or consequences greater than disjunctive antecedents or consequents of said disjunctive association rules occurring in said defined overlap threshold,

means for clustering said data items to form a set of generalized disjunctive rules based on a defined confidence threshold, and

means for iterating the above steps until all items in said list are covered.

16. The system as claimed in claim 15, wherein said list is generated by means for selecting those data items that have a significant overlap with said context.

17. The system as claimed in claim 15, wherein said disjunctive association rules are discovered by means for merging data items that overlap above said defined threshold within said context and confirmation that the strength of the relation is beyond a defined minimum support value.

18. The system as claimed in claim 17, wherein the discovery of said disjunctive association rules uses a functionally complete set of operators including “

AND”

, “

OR”

, NOT” and

“

EXCLUSIVE-OR”

.

19. The system as claimed in claim 15, wherein said clustering is agglomerative.

20. The system as claimed in claim 15, used for clustering of query results in a search engine where the query is the context, a word is mapped to an item, a document to a transaction, the recall is the confidence, and the resulting disjuncts are the labels of the clusters of documents.

21. The system as claimed in claim 20, extended to interactive query refinement.

22. The system as claimed in claim 15, used for customer targeting by means for determining generalized disjunctive association rules on data such as customer purchase history, customer segments, product information and the like.

23. The system as claimed in claim 15, used for making recommendations to customers where the customer'"'"'s purchase history is the context and the generalized disjunctive association rules provide the recommendations.

24. The system as claimed in claim 15, used for gene analysis by means for finding the generalized disjunctive association rules from gene databases.

25. The system as claimed in claim 15, used for cause-and-effect analysis in applications such as medical analysis, market survey analysis and census analysis, by means for finding generalized disjunctive association rules from the database of causes and effects.

26. The system as claimed in claim 15, used for fraud detection by means for finding generalized disjunctive association rules from transaction databases.

27. The system in claim 15, wherein support of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent divided by the total number of transactions.

28. The system in claim 15, wherein confidence of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent, divided by the cardinality of the union of disjunctive terms in the antecedent.

29. A computer program product comprising computer readable program code stored on computer readable storage medium embodied therein for mining data, wherein said method generates generalized disjunctive association rules to capture local relationships between data items with reference to a given context comprising any arbitrary subset of a set of transactions in order to provide improved data analysis independently of taxonomies, said computer program product comprising:

computer readable program code means configured for generating a list of all possible data items that can influence said context,

computer readable program code means configured for discovering disjunctive association rules for data items in said list that co-occur based on a defined overlap threshold within said context,

computer readable program code means configured for using a cutoff parameter to eliminate trivial data items from said list wherein said trivial data items create trivial disjunctive association rules having disjunctive antecedents or consequents greater than disjunctive antecedents or consequents of said disjunctive association rules occurring in said defined overlap threshold,

computer readable program code means configured for clustering of said data items to form a set of generalized disjunctive rules based on a defined confidence threshold, and

computer readable program code means configured for iterating the above steps until all items in said list are covered.

30. The computer program product as claimed in claim 29, wherein said list is generated by computer readable program code means configured for selecting those data items that have a significant overlap with said context.

31. The computer program product as claimed in claim 29, wherein said disjunctive association rules are discovered by computer readable program code means configured for merging data items that overlap above said defined threshold using traditional association rules within said context and confirmation that the strength of the relation is beyond a defined minimum support value.

32. The computer program product as claimed in claim 31, wherein the discovery of said disjunctive association rules uses a functionally complete set of operators including “

AND”

, “

OR”

, NOT” and

“

EXCLUSIVE-OR”

.

33. The computer program product as claimed in claim 29, wherein said clustering is agglomerative.

34. The computer program product as claimed in claim 29, configured for clustering of query results in a search engine where the query is the context, a word is mapped to an item, a document to a transaction, the recall is the confidence, and the resulting disjuncts are the labels of the clusters of documents.

35. The computer program product as claimed in claim 34 is extended to interactive query refinement.

36. The computer program product as claimed in claim 29, configured for customer targeting by computer readable program code means for determining generalized disjunctive association rules on data such as customer purchase history, customer segments, product information and the like.

37. The computer program product as claimed in claim 29, configured for making recommendations to customers where the customer'"'"'s purchase history is the context and the generalized disjunctive association rules provide the recommendations.

38. The computer program product as claimed in claim 29, configured for gene analysis by computer readable program code means for finding the generalized disjunctive association rules from gene databases.

39. The computer program product as claimed in claim 29, configured for cause-and-effect analysis in applications such as medical analysis, market survey analysis and census analysis, by computer readable program code means for finding generalized disjunctive association rules from the database of causes and effects.

40. The computer program product as claimed in claim 29, configured for fraud detection by computer readable program code means for finding generalized disjunctive association rules from transaction databases.

41. The computer program product in claim 29, wherein support of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent, divided by the total number of transactions.

42. The computer program product in claim 29, wherein confidence of a disjunctive rule is defined as the cardinality of the union of the disjunctive terms in the antecedent intersected with the union of the disjunctive terms in the consequent, divided by the cardinality of the union of disjunctive terns in the antecedent.