Module 4: (Association Rule Analysis) Association Rules-Introduction, Methods to discover

Association rules, Apriori(Level-wise algorithm), Partition Algorithm, Pincer Search Algorithm,

Dynamic Itemset Counting Algorithm, FP-tree Growth Algorithm.

ASSOCIATION RULES – INTRODUCTION

• Association rule mining finds interesting associations and relationships among large sets of
data items. This rule shows how frequently an itemset occurs in a transaction.
• A typical example is a Market Based Analysis.
o It allows retailers to identify relationships between the items that people buy together
frequently.
o This process analyzes customer buying habits by finding associations between the
different items that customers place in their “shopping baskets”.
o The discovery of such associations can help retailers develop marketing strategies by
gaining insight into which items are frequently purchased together by customers.
o For instance, if customers are buying milk, how likely are they to also buy bread (and
what kind of bread) on the same trip to the supermarket?
o Such information can lead to increased sales by helping retailers do selective
marketing and plan their shelf space.

Frequent Itemsets, Closed Itemsets, and Association Rules

• A set of items is referred to as an itemset.
• An itemset that contains k items is a k-itemset.
• For eg: The set {computer, antivirus_software} is a 2-itemset.
• The occurrence frequency of an itemset is the number of transactions that contain the
itemset. This is also known, simply, as the frequency, support count, or count of the itemset.
• Frequent patterns are patterns (such as itemsets, subsequences, or substructures) that
appear in a data set frequently. For example, a set of items, such as milk and bread, that
appear frequently together in a transaction data set is a frequent itemset.
• A subsequence, such as buying first a PC, then a digital camera, and then a memory card, if it
occurs frequently in a shopping history database, is a (frequent) sequential pattern.
Frequent Item Set
• A frequent item set is a set of items that occur together frequently in a dataset.
• Let T be the transaction database and a be the user-specified minimum support σ.
• An itemset X ϵ A is said to be a frequent itemset in T with respect to σ, if Support(X) ≥ σ
• Downward closure property : Any subset of a frequent set is a frequent set.
• Upward closure property : Any superset of a infrequent set is a infrequent set.
Maximal Frequent Set
• A frequent set is a maximal frequent set if it is a frequent set and no superset of this is a
frequent set.
Border Set
• An itemset is a border set if it is not a frequent set, but all its proper subsets are frequent sets
• Eg1: In a supermarket environment, the items bread and butter are likely to be purchased
together by many customers.
So, {bread, butter} is an example for frequent itemset.
The association between the items are represented by the association rule; bread=>butter
• Eg2: In an electronic store, customers who purchase computers also tend to buy antivirus
software at the same time.
So, {computer, antivirus_software} is an example for frequent itemset.
It is represented by the following association rule; computer => antivirus_software

Question (A1, A2, A3, A4, A5, A6, A7, A8, A9). Assume support= 20%.
Answer

• {1} – Not a frequent set

• {3} - is a frequent set
• {5, 6, 7} - is a border set
• {5, 6} - is a maximal frequent set
• {2, 4} - is also a maximal frequent set
• But there is no border set having {2, 4} as a proper subset

Two measures of rule interestingness.

• Rule support and confidence are two measures of rule interestingness. They respectively
reflect the usefulness and certainty of discovered rules.
• For eg: computer => antivirus_software [support = 2%; confidence = 60%]
• A support of 2% for Association Rule means that 2% of all the transactions under analysis
show that computer and antivirus software are purchased together.
• A confidence of 60% means that 60% of the customers who purchased a computer also
bought the software.
• Association rules are considered interesting if they satisfy both a minimum support threshold
and a minimum confidence threshold. Such thresholds can be set by users or domain experts.
Question Find support value of each itemset

Answer
Support (item) = Frequency of item/Number of transactions

Association rule mining can be viewed as a two-step process:

1. Find all frequent itemsets: By definition, each of these itemsets will occur at least as
frequently as a predetermined minimum support count, min sup.
2. Generate strong association rules from the frequent itemsets: By definition, these rules
must satisfy minimum support and minimum confidence.

THE APRIORI ALGORITHM: FINDING FREQUENT ITEMSETS USING CANDIDATE GENERATION

• 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
used to explore (k+1)-itemsets.
• First, the set of frequent 1-itemsets is found by scanning the database to accumulate the
count for each item, and collecting those items that satisfy minimum support. The resulting
set is denoted L1
• Next, L1 is used to find L2, the set of frequent 2-itemsets, which is used to find L3, and so on,
until no more frequent k-itemsets can be found.
• The finding of each Lk requires one full scan of the database.
• To improve the efficiency of the level-wise generation of frequent itemsets, an important
property called the Apriori property, presented below, is used to reduce the search space.

Apriori property:
• All nonempty subsets of a frequent itemset must also be frequent.
• if an itemset I does not satisfy the minimum support threshold, min_sup, then I is not
frequent; that is, P(I) < min_sup.
• If an item A is added to the itemset I, then the resulting itemset (i.e., IUA) cannot occur more
frequently than I.
• Therefore, I UA is not frequent either; that is, P(I [A) < min sup.

Apriori Algorithm is a two step process

1. The join step:
• To find Lk, a set of candidate k-itemsets is generated by joining Lk-1 with itself. This set of
candidates is denoted Ck.
• Apriori assumes that items within a transaction or itemset are sorted in lexicographic
order
2. The 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 in Ck.
• A scan of the database to determine the count of each candidate in Ck would result in the
determination of Lk (i.e., all candidates having a count no less than the minimum support
count are frequent by definition, and therefore belong to Lk).

The Apriori algorithm

• For discovering frequent itemsets for mining Boolean association rules.
• Find frequent itemsets using an iterative level-wise approach based on candidate generation.
Pseudocode

Algorithm
Generating Association Rules from Frequent Itemsets
• Once the frequent itemsets from transactions in a database D have been found, it is
straightforward to generate strong association rules from them (where strong association
rules satisfy both minimum support and minimum confidence). This can be done using
Equation for confidence.
• The conditional probability is expressed in terms of itemset support count, where support
count(AUB) is the number of transactions containing the itemsets AUB, and support count(A)
is the number of transactions containing the itemset A.
• Based on this equation, association rules can be generated as follows:
o For each frequent itemset l, generate all nonempty subsets of l.

o For every nonempty subset s of l, output the rule “s => (l - s)” if >= min
conf, where min conf is the minimum confidence threshold.

Question: The AllElectronics transaction database, D is given below. There are nine transactions
in this database, that is, |D| = 9. Find the frequent itemset and strong association rules. Given
minimum support count is 2 and minimum confidence threshold is70%

Answer:
Step1: Finding Frequent Itemset
3-itemset: {{I1, I2, I3}, {I1, I2, I5}}
No 4 itemset.

Explanation
Step 2: Generation of strong association rules from the frequent-itemset.
Frequent itemset l1 = {I1, I2, I5}. The nonempty subsets of l1 are {I1, I2}, {I1, I5}, {I2, I5}, {I1}, {I2},
and {I5}. The resulting association rules are as shown below, each listed with its confidence:
I1^I2 => I5, confidence = 2/4 = 50%
I1^I5 => I2, confidence = 2/2 = 100%
I2^I5 => I1, confidence = 2/2 = 100%
I1 => I2^I5, confidence = 2/6 = 33%
I2 => I1^I5, confidence = 2/7 = 29%
I5 => I1^I2, confidence = 2/2 = 100%
Strong association rules are I1^I5 => I2, I2^I5 => I1, I5 => I1^I2.(Only 3 rules have minimum
confidence threshold >70%)
Frequent itemset l2 = {I1, I2, I3}. The nonempty subsets of l1 are {I1, I2}, {I1, I3}, {I2, I3}, {I1}, {I2},
and {I3}. The resulting association rules are as shown below, each listed with its confidence:
I1^I2 => I3, confidence = 2/4 = 50%
I1^I3 => I2, confidence = 2/4 = 50%
I2^I3 => I1, confidence = 2/2 = 50%
I1 => I2^I3, confidence = 2/6 = 33%
I2 => I1^I3, confidence = 2/7 = 29%
I3 => I1^I2, confidence = 2/6 = 38%
Strong association rules are Nil (No rules have minimum confidence threshold >70%)

Strong association rules are I1^I5 => I2, I2^I5 => I1, I5 => I1^I2.

Question Find association rules with minimum support of 50% and minimum confidence of 75%.
Transaction ID Items

100 Bread, Cheese, Eggs, Juice

200 Bread, Cheese, Juice

300 Bread, Milk, Yogurt

400 Bread, Juice, Milk

500 Cheese, Juice, Milk

Answer First find L1. 50% support requires that each frequent item appear in at least three
transactions. Therefore L1 is given by:
Item Frequnecy
Bread 4
Cheese 3
Juice 4
Milk 3
The candidate 2-itemsets or C2 therefore has six pairs (why?). These pairs and their frequencies
are:
Item Pairs Frequency
(Bread, Cheese) 2
(Bread, Juice) 3
(Bread, Milk) 2
(Cheese, Juice) 3
(Cheese, Milk) 1
(Juice, Milk) 2
L2 has only two frequent item pairs {Bread, Juice} and {Cheese, Juice}. After these two frequent
pairs, there are no candidate 3-itemsets
Apriori property that all subsets of a frequent itemset must also be frequent
The two frequent pairs lead to the following possible rules:
Bread → Juice
Juice → Bread
Cheese → Juice
Juice → Cheese
The confidence of these rules is obtained by dividing the support for both items in the rule by the
support of the item on the left hand side of the rule.
The confidence of the four rules therefore are
Bread → Juice) ----- 3/4 = 75%

(Juice → Bread) ------ 3/4 = 75%

(Cheese → Juice) ----- 3/3 = 100%
(Juice → Cheese) ----- 3/4 = 75%
Since all of them have a minimum 75% confidence, they all qualify

Improve the efficiency of Apriori-based mining

1. Use hash-based techniques: - A hash-based technique can be used to reduce the size of the
candidate k-itemsets, Ck, for k > 1.
2. Transaction reduction: - Reducing the number of transactions scanned in future iterations. -
A transaction that does not contain any frequent k-itemsets cannot contain any frequent
 (k+1)-itemsets. - Therefore, such a transaction can be marked or removed from further
consideration
3. Partitioning - Partitioning the data to find candidate itemsets. A partitioning technique can
be used that requires just two database scans to mine the frequent itemsets.
4. Dynamic itemset counting - Adding candidate itemsets at different points during a scan. 5.
Sampling

FP GROWTH: MINING FREQUENT ITEMSETS WITHOUT CANDIDATE GENERATION

• This algorithm is an improvement to the Apriori method.
• An interesting method in this attempt is called frequent-pattern growth, or simply FP-
growth, which adopts a divide-and-conquer strategy as follows.
• First, it compresses the database representing frequent items into a frequent-pattern tree,
or FP-tree, which retains the itemset association information. It then divides the compressed
database into a set of conditional databases (a special kind of projected database), each
associated with one frequent item or “pattern fragment,” and mines each such database
separately.
• A frequent pattern is generated without the need for candidate generation.
• FP growth algorithm represents the database in the form of a tree called a frequent pattern
tree or FP tree. This tree structure will maintain the association between the itemsets.
• FP Tree
o Frequent Pattern Tree is a tree-like structure that is made with the initial itemsets of the
database.
o The purpose of the FP tree is to mine the most frequent pattern.
o Each node of the FP tree represents an item of the itemset.
o The root node represents null while the lower nodes represent the itemsets.
o The association of the nodes with the lower nodes that is the itemsets with the other
itemsets are maintained while forming the tree.

FP Growth Algorithm
Question: Suppose we have a dataset of transactions as shown. Let’s consider minimum support
as 3.
Transaction ID Items
T1 {M, N, O, E, K, Y}
T2 {D, O, E, N, Y, K}
T3 {K, A, M, E}
T4 {M, C, U, Y, K}
T5 {C, O, K, O, E, I}

Answer:
Step 1: scan the above database and compute the frequency of each item.
 Item Frequency
A 1
C 2
D 1
E 4
I 1
K 5
M 3
N 2
O 3
U 1
Y 3

Step 2: Remove all the items below minimum support is 3

Item Frequency
E 4
K 5
M 3
O 3
Y 3

{K: 5, E: 4, M : 3, O : 3, Y : 3}.

Step 3: Rearrange the transaction based on the item above minimum support.

Transaction ID Items Ordered Itemset

T1 {M, N, O, E, K, Y} {K, E, M, O, Y}
T2 {D, O, E, N, Y, K} {K, E, O, Y}
T3 {K, A, M, E} {K, E, M}
T4 {M, C, U, Y, K} {K, M, Y}
T5 {C, O, K, O, E, I} {K, E, O}

Step 4 : Construct FP tree

Step 5: Create a Conditional Pattern Base and Conditional FP Tree
Item Conditional Pattern Base Conditional FP Tree Frequent Patterns
Y {K, E, M, O : 1}, {K, E, O : 1}, {K, M : 1} {K : 3} {K, Y - 3}
{K, O - 3}, {E, O - 3}, {K, E, O -
O {K, E, M : 1}, {K, E : 2} {K, E : 3}
3}
M {K, E : 2}, {K: 1} {K : 3} {K, M - 3}
E {K: 4} {K: 4} {K, E - 4}
K

Advantages of FP Growth Algorithm

• This algorithm needs to scan the database only twice when compared to Apriori which scans
the transactions for each iteration.
• The pairing of items is not done in this algorithm and this makes it faster.
• The database is stored in a compact version in memory.
• It is efficient and scalable for mining both long and short frequent patterns

Disadvantages Of FP-Growth Algorithm

• FP Tree is more difficult to build than Apriori.
• It may be expensive.
• When the database is large, the algorithm may not fit in the shared memory
FP Growth vs Apriori
FP Growth Apriori
Pattern FP growth generates pattern by Apriori generates pattern by pairing
Generation constructing a FP tree the items into singletons, pairs and
triplets.
Candidate There is no candidate generation Apriori uses candidate generation
Generation
Process The process is faster as compared to The process is comparatively slower
Apriori. The runtime of process than FP Growth, the runtime
increases linearly with increase in increases exponentially with increase
number of itemsets. in number of itemsets
Memory A compact version of database is saved The candidates combinations are
Usage saved in memory

DYNAMIC ITEMSET COUNTING

• Alternative to Apriori Itemset Generation

• Itemsets are dynamically added and deleted as transactions are read
• Relies on the fact that for an itemset to be frequent, all of its subsets must also be
frequent, so we only examine those itemsets whose subsets are all frequent

Itemset are marked in 4 different ways

Algorithm
Question
Given minsupp = 25% (support count= 0.25*4=1) and M = 2.
Answer
 PARTITION ALGORITHM
• Apriori scans the database (set of transactions) several times, in order to compute the
supports of candidate frequent k-itemset.
• The Partition Algorithm scans the database only twice.
First scan: generate a set of all potentially large itemset
Second scan: set up counters for each potentially large itemset and compute
their actual supports
• During the first scan, a superset of the actual large itemsets is generated. (i.e. false positives
may be generated, but no false negatives are generated)
• The Partition Algorithm executes in two phases:
Phase I: the algorithm logically divides the database into a number of non- overlapping
partitions. The partitions are considered one at a time and all large itemsets for that
partition are generated. At the end of phase I, these large itemsets are merged to
generate a set of all potentially large itemsets.
 Phase II: the actual supports for these itemsets are generated and the large itemsets are
identified.
• The partition sizes are chosen such that each partition can be accommodated in the main
memory so that the partitions are read only once in each phase.

Algorithm
Question

Given support 20% and no of partition = 3

Answer

PINCER SEARCH ALGORITHM

• The Pincer Search algorithm in data mining is an efficient method for discovering
the maximum frequent itemsets (MFS) by combining both bottom-up and top-down search
approaches.
• Apriori algorithm operates in a bottom – up, breadth – first search method
• The computation starts from the smallest set of frequent item sets and moves upward till it
reaches the largest frequent itemset
• The number of database passes is equal to the largest size of the frequent item set.
• As a result, the performance decreases
• pincer – search algorithm is based on bi – directional search, which takes advantages of
both the bottom – up as well as the top – down process.
• It attempts to find the frequent item sets in a bottom – up manner but, at the same time, it
maintains a list of maximal frequent item sets.
• In this algorithm, in each pass, in addition to counting the supports of the candidate in the
bottom – up direction, it also counts the supports of the item sets of some item sets using a
top – down approach.
• These are called the Maximal Frequent Candidate Set(MFCS).
• This process helps in pruning the candidate sets very early on in the algorithm.
• MFCS is initialized to contain one itemset, which contains all of the database items.
• MFCS is updated whenever new infrequent itemsets are found

Core Concepts
• Maximum Frequent Set (MFS): The goal of the algorithm is to find the MFS, which is the set
of all frequent itemsets that have no frequent supersets. Once the MFS is known, all other
frequent itemsets can be immediately derived as their subsets.
• Hybrid Approach: The algorithm primarily uses a bottom-up, breadth-first search like Apriori,
but simultaneously conducts a restricted top-down search. This dual approach allows it to
leverage both the downward and upward closure properties for pruning candidates.
• Maximum Frequent Candidate Set (MFCS): A key data structure used in the top-down
search. The MFCS is a dynamic set that acts as a border, storing the maximal itemsets that
are not known to be infrequent at any given time. It is initialized to contain the single itemset
of all items in the database.
• Pruning: The algorithm uses information from one search direction to prune candidates in
the other, which significantly reduces the number of candidates for whom support needs to
be counted and the number of database passes required

Data Structures
• Maximum Frequent Candidate Set (MFCS): A minimum cardinality set of itemsets that
contains all frequent itemsets but no known infrequent itemsets. It helps the top-down
search skip many levels in a single pass.
• Maximum Frequent Set (MFS): The final output containing only the maximal frequent
itemsets—those with no frequent supersets

The Pincer Search operates in passes over the database:

• Bottom-up process: This part is similar to the Apriori algorithm, generating candidate
itemsets of increasing length (1-itemsets, 2-itemsets, and so on) and counting their support.
Infrequent itemsets found here are used to prune their supersets from future candidate
consideration (upward closure property).
• Top-down process: Concurrently, the algorithm maintains and updates the MFCS. If an
itemset in the MFCS is found to be frequent, its subsets can be pruned from the bottom-up
candidate sets because they are guaranteed to be frequent as well (downward closure
property).
• Termination: The algorithm terminates when the Maximum Frequent Candidate Set (MFCS)
equals the Maximum Frequent Set (MFS), meaning all maximal frequent itemsets have been
identified.
Algorithm