UNIT IV:

Association Analysis: Problem Definition, Frequent Item set Generation, Rule Generation: Confident
Based Pruning, Rule Generation in Apriori Algorithm, Compact Representation of frequent item sets, FPGrowth
Algorithm.

Association analysis is useful for discovering interesting relationships hidden in large data sets.
The uncovered relationships can be represented in the form of association rules or sets of
frequent items.

For example, given a table of market basket transactions

TI
Items
D

1 {Bread, Milk}

{Bread, Diapers, Beer,

2
Eggs}

{Milk, Diapers, Beer,

3
Cola}

{Bread, Milk, Diapers,

4
Beer}

{Bread, Milk, Diapers,

5
Cola}

The follwing rule can be extracted from the table:

{Milk,Diaper}→{Beer}{Milk,Diaper}→{Beer}

A common strategy adopted by many association rule mining algorithms is to decompose the
problem into 2 major subtasks:
1. Frequent Itemset Generation
Find all the itemsets that satisfy the minsup threshold.
2. Rule Generation
Extract all the high-confidence rules (strong rules) from the frequent itemsets found in the
previous step.
Frequent Itemset Generation
A lattice structure can be used to enumerate the list of all possible itemsets:

However, the cost of frequent itemset generation is large. Given dd items, there
are 2d2d possible candidate itemsets. There are several ways to reduce the computational
complexity of frequent itemset generation:
1. Reduce the number of candidate itemsets (M): The Apriori Principle
2. Reduce the number of comparison while counting supports: By using more advanced
data structures, we can reduce the number of comparisons for matching each
candidate itemset against every transaction.
Factors Affecting Complexity:
 Choice of minimum support threshold lowering support threshold results in more
frequent itemsets. This may increase number of candidates and max length of
frequent itemsets
 Dimensionality (number of items) of the data set More space is needed to
store support count of each item.
 Number of transactions Since Apriori makes multiple passes, run time of
algorithm may increase with number of transactions.
 Average transaction width This may increase max length of frequent itemsets
and traversals of hash tree.
Apriori Algorithm – Frequent Pattern Algorithms
Apriori algorithm was the first algorithm that was proposed for frequent itemset mining. It was later
improved by R Agarwal and R Srikant and came to be known as Apriori. This algorithm uses two steps
“join” and “prune” to reduce the search space. It is an iterative approach to discover the most frequent
itemsets.
The steps followed in the Apriori Algorithm of data mining are:
1. Join Step: This step generates (K+1) itemset from K-itemsets by joining each item with itself.
2. Prune Step: This step scans the count of each item in the database. If the candidate item does
not meet minimum support, then it is regarded as infrequent and thus it is removed. This step is
performed to reduce the size of the candidate itemsets.
Steps In Apriori
Apriori algorithm is a sequence of steps to be followed to find the most frequent itemset in the given
database. This data mining technique follows the join and the prune steps iteratively until the most
frequent itemset is achieved. A minimum support threshold is given in the problem or it is assumed by
the user.
#1) In the first iteration of the algorithm, each item is taken as a 1-itemsets candidate. The algorithm will
count the occurrences of each item.
#2) Let there be some minimum support, min_sup . The set of 1 – itemsets whose occurrence is
satisfying the min sup are determined. Only those candidates which count more than or equal to
min_sup, are taken ahead for the next iteration and the others are pruned.
#3) Next, 2-itemset frequent items with min_sup are discovered. For this in the join step, the 2-itemset is
generated by forming a group of 2 by combining items with itself.
#4) The 2-itemset candidates are pruned using min-sup threshold value. Now the table will have 2 –
itemsets with min-sup only.
#5) The next iteration will form 3 –itemsets using join and prune step. This iteration will follow
antimonotone property where the subsets of 3-itemsets, that is the 2 –itemset subsets of each group fall
in min_sup. If all 2-itemset subsets are frequent then the superset will be frequent otherwise it is pruned.
#6) Next step will follow making 4-itemset by joining 3-itemset with itself and pruning if its subset does
not meet the min_sup criteria. The algorithm is stopped when the most frequent itemset is achieved.

Example of Apriori: Support threshold=50%, Confidence= 60%

TABLE-1
Transaction List of items

T1 I1,I2,I3

T2 I2,I3,I4

T3 I4,I5

T4 I1,I2,I4

T5 I1,I2,I3,I5

T6 I1,I2,I3,I4
Solution:
Support threshold=50% => 0.5*6= 3 => min_sup=3
1. Count Of Each Item
TABLE-2
Item Count

I1 4

I2 5

I3 4

I4 4

I5 2
2. Prune Step: TABLE -2 shows that I5 item does not meet min_sup=3, thus it is deleted, only I1, I2, I3,
I4 meet min_sup count.
TABLE-3
Item Count

I1 4

I2 5

I3 4

I4 4
3. Join Step: Form 2-itemset. From TABLE-1 find out the occurrences of 2-itemset.
TABLE-4
Item Count

I1,I2 4

I1,I3 3

I1,I4 2

I2,I3 4

I2,I4 3

I3,I4 2
4. Prune Step: TABLE -4 shows that item set {I1, I4} and {I3, I4} does not meet min_sup, thus it is
deleted.
TABLE-5
Item Count

I1,I2 4

I1,I3 3

I2,I3 4

I2,I4 3
5. Join and Prune Step: Form 3-itemset. From the TABLE- 1 find out occurrences of 3-itemset.
From TABLE-5, find out the 2-itemset subsets which support min_sup.
We can see for itemset {I1, I2, I3} subsets, {I1, I2}, {I1, I3}, {I2, I3} are occurring in TABLE-5 thus {I1, I2,
I3} is frequent.
We can see for itemset {I1, I2, I4} subsets, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} is not frequent, as it is not
occurring in TABLE-5 thus {I1, I2, I4} is not frequent, hence it is deleted.
TABLE-6
Item

I1,I2,I3
 Item

I1,I2,I4

I1,I3,I4

I2,I3,I4
Only {I1, I2, I3} is frequent.
6. Generate Association Rules: From the frequent itemset discovered above the association could be:
{I1, I2} => {I3}
Confidence = support {I1, I2, I3} / support {I1, I2} = (3/ 4)* 100 = 75%
{I1, I3} => {I2}
Confidence = support {I1, I2, I3} / support {I1, I3} = (3/ 3)* 100 = 100%
{I2, I3} => {I1}
Confidence = support {I1, I2, I3} / support {I2, I3} = (3/ 4)* 100 = 75%
{I1} => {I2, I3}
Confidence = support {I1, I2, I3} / support {I1} = (3/ 4)* 100 = 75%
{I2} => {I1, I3}
Confidence = support {I1, I2, I3} / support {I2 = (3/ 5)* 100 = 60%
{I3} => {I1, I2}
Confidence = support {I1, I2, I3} / support {I3} = (3/ 4)* 100 = 75%
This shows that all the above association rules are strong if minimum confidence threshold is 60%.
The Apriori Algorithm: Pseudo Code
Aprioir Algorithm:
 Generate frequent itemsets of length k (initially k=1)
 Repeat until no new frequent itemsets are identified
o Generate length (k+1) candidate itemsets from length k frequent itemsets
o Prune length (k+1) candidate itemsets that contain subsets of length k that are
infrequent
o Count the support of each candidate
o Eliminate length (k+1) candidates that are infrequent
Advantages
1. Easy to understand algorithm
2. Join and Prune steps are easy to implement on large itemsets in large databases
Disadvantages
1. It requires high computation if the itemsets are very large and the minimum support is kept very
low.
2. The entire database needs to be scanned.
Applications Of Apriori Algorithm
Some fields where Apriori is used:
1. In Education Field: Extracting association rules in data mining of admitted students through
characteristics and specialties.
2. In the Medical field: For example Analysis of the patient’s database.
3. In Forestry: Analysis of probability and intensity of forest fire with the forest fire data.
4. Apriori is used by many companies like Amazon in the Recommender System and by Google
for the auto-complete feature.
Conclusion
Apriori algorithm is an efficient algorithm that scans the database only once.
It reduces the size of the itemsets in the database considerably providing a good performance. Thus,
data mining helps consumers and industries better in the decision-making process.

Frequent Pattern Growth Algorithm

The two primary drawbacks of the Apriori Algorithm are:
1. At each step, candidate sets have to be built.
2. To build the candidate sets, the algorithm has to repeatedly scan the database.
These two properties inevitably make the algorithm slower. To overcome these redundant steps, a
new association-rule mining algorithm was developed named Frequent Pattern Growth Algorithm. It
overcomes the disadvantages of the Apriori algorithm by storing all the transactions in a Trie Data
Structure. Consider the following data:-
The above-given data is a hypothetical dataset of transactions with each letter representing an item.
The frequency of each individual item is computed:-

Let the minimum support be 3. A Frequent Pattern set is built which will contain all the elements
whose frequency is greater than or equal to the minimum support. These elements are stored in
descending order of their respective frequencies. After insertion of the relevant items, the set L looks
like this:-
L = {K : 5, E : 4, M : 3, O : 4, Y : 3}
Now, for each transaction, the respective Ordered-Item set is built. It is done by iterating the
Frequent Pattern set and checking if the current item is contained in the transaction in question. If the
current item is contained, the item is inserted in the Ordered-Item set for the current transaction. The
following table is built for all the transactions:

Now, all the Ordered-Item sets are inserted into a Trie Data Structure.
a) Inserting the set {K, E, M, O, Y}:
Here, all the items are simply linked one after the other in the order of occurrence in the set and
initialize the support count for each item as 1.
b) Inserting the set {K, E, O, Y}:
Till the insertion of the elements K and E, simply the support count is increased by 1. On inserting O
we can see that there is no direct link between E and O, therefore a new node for the item O is
initialized with the support count as 1 and item E is linked to this new node. On inserting Y, we first
initialize a new node for the item Y with support count as 1 and link the new node of O with the new
node of Y.

c) Inserting the set {K, E, M}:

Here simply the support count of each element is increased by 1.

d) Inserting the set {K, M, Y}:
Similar to step b), first the support count of K is increased, then new nodes for M and Y are initialized
and linked accordingly.

e) Inserting the set {K, E, O}:

Here simply the support counts of the respective elements are increased. Note that the support count
of the new node of item O is increased.
Now, for each item, the Conditional Pattern Base is computed which is path labels of all the paths
which lead to any node of the given item in the frequent-pattern tree. Note that the items in the below
table are arranged in the ascending order of their frequencies.

Now for each item, the Conditional Frequent Pattern Tree is built. It is done by taking the set of
elements that is common in all the paths in the Conditional Pattern Base of that item and calculating
its support count by summing the support counts of all the paths in the Conditional Pattern Base.
From the Conditional Frequent Pattern tree, the Frequent Pattern rules are generated by pairing the
items of the Conditional Frequent Pattern Tree set to the corresponding to the item as given in the
below table.

For each row, two types of association rules can be inferred for example for the first row which
contains the element, the rules K -> Y and Y -> K can be inferred. To determine the valid rule, the
confidence of both the rules is calculated and the one with confidence greater than or equal to the
minimum confidence value is retained.
Advantages of FP growth algorithm:-
1. Faster than apriori algorithm

2. No candidate generation

3. Only two passes over dataset

Disadvantages of FP growth algorithm:-

1. FP tree may not fit in memory

2. FP tree is expensive to build