Basic Approach of Association Rule
Step 1:find all frequent itemsets
Step 2:generate strong association rules from frequent itensets
Brute-force approach
Each itemset in the lattice is a candidate frequent itemset
Count the support of each candidate by scanning the database
O(NWM) => M=2^d
Apriori Algorithm
Apriori property
all non-empty subsets of a frequent itemset must also be frequent
Apriori principle holds due to the following property of the support measure
For any(X,Y) : (X include in Y ) => s(X) >= s(Y)
support of an items never exceeds the support of its subsets
notation
frequent k-itemset(denoted as Lk):satisfy mini support
candidate k-itemset(denoted as Ck):possible frequent k-itemset
Level-wise approach
(k-1)-itemsets are used to explore k-itemsets
prune Ck by subset test
generate Lk by scanning transaction DB
How to Count Supports of candidates
Candidate itemisers are stored in a hash-tree
Leaf node of hash-tree contains a list of itemisers and counts
Interior node contains a hash table
Challenges
Multiple scans of transaction database
Huge number of candidates
Tedious workload of support counting for candidats
improvement
reduce passes of transaction database scans
shrink number of candidates
facilitate support counting of candidates
DHP
Observation of performance in association rule mining
initial candidate set generation is key issue to improve
amount of transaction data that must be scanned
Major features of DHP
efficient generation for frequent itemsets
effective reduction on transaction database size
option of reducing #(database scan) required
Partitioning
Observation
Partition size is chosen to be resident in main memory
Observation: any potential frequent itemset appears as a frequent itemset in at least one of the partitions.
Transaction DB is divided into non- overlapping partitions
Twophasesscanning
Firstscan:generatesasetofallpotentially frequent itemsets
Each partition generates the local frequent itemsets
Secondscan:actualsupportismeasured
Collection of local frequent itemset = global candidate itemset
Global frequent itemsets are found by scan DB
Advantages:
Adapts to available main memory
Easily parallelized
Maximum number of database scans is two
Disadvantage
May have many candidates during second scan
Sampling
Observation
Sample the database and apply Apriori to the sample.
Potentially Large Itemsets (PL): Large itemsets from sample
Negative Border (BD - ):
Generalization of Apriori-Gen
applied to itemsets of varying sizes.
Minimal set of itemsets which are not in PL, but whose subsets are all in PL.
Advantages
Reduces number of database scans to one
in the best case and two in worst n Scales better
Disadvantages
Potentially large number of candidates in second pass
