An analytical survey of some efficient current approaches to mining all kind of logical rules is presented including implicative and functional dependencies, association and classification rules. The interconnection between these approaches is analyzed. It is demonstrated that all the approaches are equivalent with respect to using the same key concepts of frequent itemsets (maximally redundant or closed itemset, generator, non-redundant or minimal generator, classification test) and the same procedures of their lattice structure construction. The main current tendencies in developing these approaches are considered.
TopIntroduction
Our objectives, in this chapter, are the following ones:
- 1.
To give an analytical survey and comparison of existing and most effective approaches for mining all kinds of logical rules (implicative, association rules and functional dependencies) in the following frameworks: Apriori-like search, Formal Concept Analysis, closure operations of Galois connections, and Diagnostic Test Approach.
- 2.
To show that all these approaches use the equivalent definitions of the key concepts in mining all kinds of logical rules: item, itemset, frequent itemset, maximal itemset, maximally redundant itemset, generator, minimal generator (non-redundant or irredundant itemset), closed itemset, support, and confidence.
- 3.
To consider all these approaches on the base of the same mathematical language (the lattice theory) and to analyze the interconnections between them.
- 4.
To present the Diagnostic Test Approach (DTA) to mining logical rules. This approach is an integrated system of operations and methods capable to solve any kind of supervised symbolic machine learning problems including mining implications, association rules, and functional dependences both in incremental and non-incremental manner.
TopNotations And Basic Concepts
Mining itemsets of different properties (as a basis of logical rule mining) is a core problem for several data mining applications as inferring association rules, implicative and functional dependencies, correlations, document classification and analysis, and many others, which are extensively studied. Moreover, databases are becoming increasingly larger, thus requiring a higher computing power to mine different itemsets in reasonable time.
We begin with the definitions of the main concepts of itemset mining: item, itemset, transaction, tid, and tid-set or tid-list. The definitions of these concepts go from database system applications.
By Lal, & Mahanti, 2010, the set I = { i1, i2…... im } is a set of m distinct literals called items. Transaction is a set of items over I. Items may be products, special equipments, service options, objects, properties of objects, etc.
Any subset X of I is called an itemset. As an example of the itemset, it may be considered a set of products that can be bought (together). An example of customer purchase data as a set of itemsets is given in Table 1.
Table 1. An example of market basket transactions
| TID | Itemsets (Transactions) |
| 1 | Bread, Milk |
| 2 | Bread, Diapers, Beer, Eggs |
| 3 | Milk, Diapers, Cola, Beer |
| 4 | Bread, Milk, Diapers, Beer |
| 5 | Bread, Milk, Coffee, Cheese |
| 6 | Bread, Milk, Butter, Coffee, Cakes |