14-11-2012, 05:06 PM
APRIORI ALGORITHM
APRIORI ALGORITHM.ppt (Size: 2.33 MB / Downloads: 52)
Association Rules
The Apriori algorithm calculates rules that express probabilistic relationships between items in frequent itemsets.
Itemset
A collection of one or more items
Example: {Ups, EmergencyLight, Battery}
k-itemset
An itemset that contains k items
Frequent Itemset
An itemset whose support is greater than or equal to a minsup threshold
Rule Evaluation Metrics
Support (s)
Fraction of transactions that contain both X and Y
Example: Database with transactions
( customer_# : item_a1, item_a2, … )
Association rule
Confidence ©
Measures how often items in Y appear in transactions that contain X
Confidence(X=>Y) equals support(X,Y) / support(X)
On Apriori Algorithm
We first find the set of frequent 1-itemsets, Lk:- this is done by scanning the database and accumulating the count for each item and then keeping those that meet the minimum support in a new set called Lk.
Then we use Lk to find Ck+1 (the set of candidate 2-itemsets):- This is a two step process that first generates Ck+1 based on Lk and then secondly prunes Ck+1 by getting rid of those Ck+1 itemsets using the Apriori principle.
We find Lk+1: we do this by finding the support count for all the itemsets in Ck+1 and getting rid of those that are below the minsup.
We continue step 2&3 until no new frequent (k+1)-itemset are found.