Association Rules

Introduction

Concepts

Initial proposed for market basket analysis

Items that frequent occur together

Discover the interesting
relationships in data

Items that have association with other items

Lift

Support

How frequently the items appear in the data

Sup(X)=|X|transaction
where
|X| = Number of transaction contain item X

\(Sup(X,Y) = \frac{|X,Y|}{transaction} \)

Confidence

How likely an item is purchased
when another item is purchased

Value close to 1 indicates
rule holds enough confidence

\(Conf(X\rightarrow Y) = \frac {Sup(X,Y)}{Sup(X)} \)

If lift is close to 1

  • X & Y are independent

If lift > 1

  • X make Y more likely

If lift <1

  • X make Y less likely

\(Lift(X \rightarrow Y) = \frac{Sup(X,Y)}{Sup(X)Sup(Y)} \)

Apriori Algorithm

An algorithm for frequent item mining
& association rule mining

Implementation

  1. Start with k =1
  2. Calculate support and keep frequent š‘˜-item sets that has enough support
  3. In each iteration, generate frequent k+1 item sets from frequent k-item sets
  4. Calculate support and keep frequent š‘˜+1 item sets that has enough support
  5. Repeat 3 & 4 until no more frequent item set

Reduce the number of itemsets we
that need to examine