UNIT III Mining Frequent Patterns, Associations and Correlations: Basic

Concepts, Market Basket Analysis, Efficient and Scalable Frequent Item set
Mining Methods, Mining various kinds of Association Rules, From Association
Mining to Correlation Analysis, Constraint- Based Association Mining.
Basic Concepts:
This section introduces the basic concepts of frequent pattern mining for the
discovery of interesting associations and correlations between item sets in
transactional and relational databases.
A typical example of frequent item set mining is market basket analysis. This
process analyzes customer buying habits by finding associations between the
different items that customers place in their “shopping baskets” as shown in figure.

Market Basket Analysis

Market basket analysis is a data mining technique used by retailers to increase
sales by better understanding customer purchasing patterns. It involves analyzing

1 | Page
large data sets, such as purchase history, to reveal product groupings, as well as
products that are likely to be purchased together.
Definition:
“Technique which identifies the strength of association between pairs of products
purchased together and identify patterns of co-occurrence.”
Terms of Market Basket Analysis:
● Antecedent
● Consequent
● Support
● Confidence
● Lift ratio

2 | Page
3 | Page
Apriori Algorithm in Data Mining
The Apriori algorithm in data mining is a popular algorithm used for finding
frequent item sets in a dataset.
It is widely used in association rule mining to discover relationships between
items in a dataset. The Apriori algorithm was developed by R. Agrawal and R.
Srikant in 1994.
Introduction to Apriori Algorithm
● The Apriori algorithm in data mining is a widely used algorithm to find frequent
item sets in a dataset. The Apriori algorithm is used to implement frequent
pattern mining (FPM). Frequent pattern mining is a data mining technique to
discover frequent patterns or relationships between items in a dataset.
● Frequent pattern mining involves finding sets of items or item sets that occur
together frequently in a dataset. These sets of items or item sets are called

4 | Page
 frequent patterns, and their frequency is measured by the number of
transactions in which they occur.
● The Apriori algorithm is called "apriori" because it uses prior knowledge about
the frequent item sets. The algorithm uses the concept of "apriori property,"
which states that if an item set is frequent, then all of its subsets must also be
frequent.
Steps in Apriori
Apriori algorithm is a sequence of steps to be followed to find the most frequent
item set in the given database. This data mining technique follows the join and the
prune steps iteratively until the most frequent item set 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 ( eg 2). The set of 1 – item
sets 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 –item sets with min-sup only.
5) The next iteration will form 3 –item sets using join and prune step. This
iteration will follow anti monotone property where the subsets of 3-itemsets
that is the 2 –item set 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 item set is achieved.
Example:

5 | Page
6 | Page
Therefore frequent item set are I1, I2, I5 and I1, I2, I3
Next we are going to define the association rules which supports min confidence
level.

7 | Page
8 | Page
Q) Explain the FP growth algorithm with an example?
The FP-Growth Algorithm is an alternative way to find frequent item sets without
using candidate generations, thus improving performance. The core of this method
is special data structure named frequent-pattern tree (FP-tree).

Frequent Pattern Algorithm Steps

The frequent pattern growth method lets us find the frequent pattern without
candidate generation.
Let us see the steps followed to mine the frequent pattern using frequent
pattern growth algorithm:
#1) the first step is to scan the database to find the occurrences of the item sets in
the database. This step is the same as the first step of Apriori. The count of 1-
itemsets in the database is called support count or frequency of 1-itemset.
#2) the second step is to construct the FP tree. For this, create the root of the tree.
The root is represented by null.
#3) the next step is to scan the database again and examine the transactions.
Examine the first transaction and find out the item set in it. The item set with the
max count is taken at the top, the next item set with lower count and so on. It
means that the branch of the tree is constructed with transaction item sets in
descending order of count.

9 | Page
#4) the next transaction in the database is examined. The item sets are ordered in
descending order of count. If any item set of this transaction is already present in
another branch (for example in the 1st transaction), then this transaction branch
would share a common prefix to the root.
This means that the common item set is linked to the new node of another item set
in this transaction.
#5) Also, the count of the item set is incremented as it occurs in the transactions.
Both the common node and new node count is increased by 1 as they are created
and linked according to transactions.
#6) the next step is to mine the created FP Tree. For this, the lowest node is
examined first along with the links of the lowest nodes. The lowest node represents
the frequency pattern length 1. From this, traverse the path in the FP Tree. This
path or paths are called a conditional pattern base.

Example:

3. Build FP Tree

10 | Page
4. Construct a conditional database table as follow:

Q) Explain how to Mining Various Kinds of Association Rules.

For many applications, it is difficult to find strong associations among data
items at low or primitive levels of abstraction due to the sparsity of data at
those levels.
Therefore, data mining systems should provide capabilities for mining
association rules at multiple levels of abstraction as follows
� Mining Multilevel Association Rules
To mine multilevel association rules, we utilize concept hierarchies. These
hierarchies organize data into levels of abstraction.
Suppose we are given the task-relevant set of transactional data in Table for
sales in an AllElectronics store, showing the items purchased for each
transaction.

11 | Page
 The concept hierarchy for the items is shown in Figure. A concept
hierarchy defines a sequence of mappings from a set of low-level
concepts to higher level, more general concepts.

Association rules generated from mining data at multiple levels of

abstraction are called multiple-level or multilevel association rules.
Multilevel association rules can be mined efficiently using concept
hierarchies under a support-confidence framework. For each level, any
algorithm for discovering frequent item sets may be used, such as Apriori
or its variations.
There are different approaches for finding relationships between items at
various different levels:
Using uniform minimum support for all levels (referred to as
uniform support):
The same minimum support threshold is used when mining at each level
of abstraction. For example, in Figure, a minimum support threshold of

12 | Page
 5% is used throughout. Both “computer” and “laptop computer” are found
to be frequent, while “desktop computer” is not.

This approach uses a minimum support threshold for all levels. The approach
is simple as we have to decide only a single threshold value that will be used
for all the levels.
However, selecting the minimum support threshold value could be difficult if
the value is too high. It could miss meaningful associations which occur at
low abstraction levels, or if the value selected is low, then lower levels of
data abstraction items would also qualify.
However, it is unlikely that low levels of data abstraction would occur so
frequently as high levels of abstraction.
Using reduced minimum support at lower levels (referred to as
reduced support): Each abstraction level has its own minimum support
threshold. The deeper the abstraction level, the smaller the corresponding
threshold. For example, in Figure, the minimum support thresholds for levels
1 and 2 are 5% and 3%, respectively. In this way, “computer,” “laptop
computer,” and “desktop computer” are all considered frequent.
� Mining Multidimensional Associations
So far, we have studied association rules that imply a single predicate, that is, the
predicate buys. For instance, in mining our AllElectronics database, we may
discover the Boolean association rule
Buys(X, “digital camera”) ⇒ buys(X, “HP printer”). 🡪Rule1

13 | Page
Following the terminology used in multidimensional databases, we refer to each
distinct predicate in a rule as a dimension. Hence, we can refer to Rule1 as a “single
dimensional or intra dimensional” association rule because it contains a single
distinct predicate (e.g., buys) with multiple occurrences.
Association rules that involve two or more dimensions or predicates can be referred
to as “multidimensional association rules”.

Rule above contains three predicates (age, occupation, and buys), each of which
occurs only once in the rule. Hence, we say that it has no predicates.
Multidimensional association rules with no repeated predicates are called “inter
Dimensional association rules.” We can also mine multidimensional association
rules with repeated predicates, which contain multiple occurrences of some
predicates. These rules are called “hybrid-dimensional association rules”.
Example:

Q) Discus about the following

A. From Association Mining to Correlation Analysis
B. Constraint-Based Association Mining
A. From Association Mining to Correlation Analysis:
✔ Most association rule mining algorithms employ a "support-confidence
framework". Often, many interesting rules can be found using low support
thresholds.
✔ Although minimum support and confidence thresholds help to exclude the
uninteresting rules, many rules so generated are still not interesting to the
users.
✔ consider the scenario:
Strong Rules Are Not Necessarily Interesting:
An Example a rule is interesting can be assessed either subjectively or objectively.
Ultimately, only the user can judge if a given rule is interesting, and this judgment,
being subjective, may differ from one user to another. However, objective
interestingness measures, based on the statistics.

14 | Page
 ✔ The support and confidence measures are insufficient for uninteresting
association rules. To tackle this weakness, a correlation measure can be used.
This leads to correlation rules of the form

B. Constraint-Based Association Mining

⮚ A data mining process may uncover thousands of rules from a given set of
data, most of which end up being unrelated or uninteresting to the users.
⮚ Often, users have a good sense of which ―direction of mining may lead to
interesting patterns and the form of the patterns or rules they would like to
find.
⮚ Thus, a good heuristic is to have the users specify such expectations as
constraints to confine the search space. This strategy is known as constraint-
based mining.
The constraints can include the following:
1. Knowledge type: They specify the type of knowledge to mined such as
association or correlation.
2. Data constraints: These specify the set of task relevant data
3. Dimension constraints: These specify the desired dimensions (or attributes)
of the data or levels of the concept hierarchies to be used in mining.
4. Interestingness constraints: These specify thresholds on statistical measure
of rule interestingness such as support, confidence and correlation.
5. Rule constraints: These specify the form of rules to be mined. Such
constraints can be expressed as Meta rules or as relationships among
attributes, attribute values and or aggregate.

Metarule-Guided Mining of Association Rules:

⮚ The user can specify the syntactic form of rules that the user is interested in
mining when using a metarule.

15 | Page
 ⮚ Metarules can be developed manually by the analyst based on their prior
knowledge, expectations, or intuition in relation to the data, or they can be
generated automatically depending on the schema of the database.
EXAMPLE:
✔ Assume you are a market analyst for AllElectronics and have access to both a
list of customer transactions and demographic information about the
company's clientele (such as age, residence, and credit score).
✔ You want to learn if there is a correlation between certain consumer
characteristics and the products they buy.
✔ You may use a metarule to define the type of rules you want to uncover. For
example Metarules like P1(X, Y) ∧ P2(X, W) ⇒ buys(X, “office software”) are
examples of such expressions.
✔ where P1 and P2 are predicate variables that are instantiated to
attributes from the given database during mining, X is a variable
representing a customer, and Y and W take on values of the attributes
assigned to P1 and P2 during the process. To examine P1 and P2
instantiations, a user will often provide a set of properties.
Constraint Pushing:
✔ Rule constraints specify expected set/subset relationships of the
variables in the mined rules, constant initiation of variables, and
aggregate functions.
✔ Users typically employ their knowledge of the application or data to
specify rule constraints for the mining task.
✔ These rule constraints may be used together with, or as an alternative
to, metarule -guided mining.

16 | Page