Association Rules - created from Mind Map

Page 1

Basic concept

Efficient and scalable frequent Itemsets

Apriori, the basic algorithm for finding frequent itemsets .

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

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 horizontaldata format. This format is known as vertical data format.

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.)

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.

Market Basket Analysis

Frequent itemset mining leads to the discovery of associations and correlations amongitems 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

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.

Association rules from frequent itemsets

Improving the Efficiency of Apriori

mining closed frequent 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

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 anyfrequent (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 frequentitemsets in S instead of D.

Dynamic item counting

A dynamic itemset counting technique was proposed in which the database ispartitioned into blocks marked by start points.

Item merging

sub itemsets pruning

iItem skipping