Association Rules

Association Rules

1. Basic concept

   • Market Basket Analysis
     • Frequent itemsets mining leads to the discovery of associations and correlations among items in large transactional or relational data sets.
   • Frequent,closed itemsets,Association rules
     • A set of items is referred to as an itemset.2 An itemset that contains k items is a k-itemset.The occurrence frequency of an itemset is the number of transactions that contain the itemset
   • Road map

2. Efficient and scalable frequent Itemsets

   • Apriori, the basic algorithm for finding frequent itemsets .
   • Apriori algorithm
     • Apriori is a seminal algorithm proposed by R. Agrawal and R. Srikant in 1994 for mining frequent itemsets for Boolean association rules. The name of the algorithm is based on the fact that the algorithm uses prior knowledge of frequent itemset properties,Apriori employs an iterative approach known as a level-wise search, where k-itemsets are usedtoexplore (k+1)-itemsets.
     • join step
       • To find Lk, a set of candidate k-itemsets is generated by joining Lk
     • Prune step
       • Ck is a superset of Lk, that is, its members may or may not be frequent,but all of the frequent k-itemsets are included inCk
   • Association rules from frequent itemsets
   • Improving the Efficiency of Apriori
     • Hash based technique
       • A hash-based technique can be used to reduce the size of the candidate k-itemsets, Ck, for k > 1.
     • Transaction reduction
       • Atransaction that does not contain any frequent k-itemsets cannot contain any frequent (k+1)-itemsets.
     • Partitioning
       • A partitioning technique can be used that requires just two database scans to mine the frequent itemsets
     • Sampling
       • The basic idea of the sampling approach is to pick a random sample S of the given data D, and then search for frequent itemsets in S instead of D. 
     • Dynamic item counting
       • A dynamic itemset counting technique was proposed in which the database is partitioned into blocks marked by start points.
   • mining closed frequent itemsets
     • Item merging
     • sub itemsets pruning
     • iItem skipping

3. Mining frequent itemsets without candidate generation

   • An interestingmethod in this attempt is called frequent-pattern growth, or simply FP-growth, which adopts a divide-and-conquer strategy

4. Mining frequent itemsets using vertical data format

   • TID is a transaction-id and itemset is the set of items bought in transaction TID. This data format is known as horizontal data format. This format is known as vertical data format.

5. Mining Multilevel Association rules

   • Multilevel association rules involve concepts at different levels of abstraction.Multidimensional association rules involve more than one dimension or predicate (e.g., rules relating what a customer buys as well as the customer’s age.)

6. Multidimension Association rules

   • They store aggregates (such as counts), in multidimensional space, which is essential for computing the support and confidence of multidimensional association rules.