UNIT III

3.1 Mining Frequent Patterns

 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 sub sequence, 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.
 A sub structure can refer to different structural forms, such as subgraphs, subtrees, or
sublattices, which may be combined with itemsets or subsequences. If a substructure
occurs frequently, it is called a (frequent) structured pattern.
 Finding such frequent patterns plays an essential role in mining associations, correlations,
and many other interesting relationships among data.

Applications

• Market Basket Analysis: given a database of customer transactions, where each

transaction is a set of items the goal is to find groups of items which are frequently
purchased together.
• Telecommunication (each customer is a transaction containing the set of phone calls)
• Credit Cards/ Banking Services (each card/account is a transaction containing the set of
customer’s payments)
• Medical Treatments (each patient is represented as a transaction containing the ordered
set of diseases)
• Basketball-Game Analysis (each game is represented as a transaction containing the
ordered set of ball passes)
Association Rule Definitions

 I={i1, i2, ..., in}: a set of all the items

 Transaction T: a set of items such that T I

1
  Transaction Database D: a set of transactions

 A transaction T  I contains a set A  I of some items, if A T

 An Association Rule: is an implication of the form A  B, where A, B  I

 It has two measure

 Support

 Confidence

 The rule A  B holds in the transaction set D with support s, where s is the percentage
of transactions in D that contain A[B (i.e., the union of sets A and B, or say, both A and
B). This is taken to be the probability, P(AUB)
 The rule A  B has confidence c in the transaction set D, where c is the percentage of
transactions in D containing A that also contain B. This is taken to be the conditional
probability, P(B|A).
 That is,

Example Problems are discussed in classwork note.

In general, 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.

3.2 Efficient and Scalable Frequent Itemset Mining Methods

2
Approaches for mining association rule are:

 Apriori Algorithm
 FP – Growth generation

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
usedtoexplore (k+1)-itemsets.
 First, the setof 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.
The Apriori Principle
Any subset of a frequent itemset must be frequent.
The Apriori property follows a two step process:
Join Step: Ck is generated by joining Lk-1 with itself.
Prune Step: Any (K-1) itemset that is not frequent cannot be a subset of a
frequent k itemset.

Algorithm: Apriori. Find frequent itemsets using an iterative level-wise approach based on
candidate generation.

3
 The Apriori algorithm for discovering frequent itemsets for mining Boolean association rules.

Note: Problems Sloved in class work note refer it.

Improving the Efficiency of Apriori

 Hash-based itemset counting: A k-itemset whose corresponding hashing bucket count is

below the threshold cannot be frequent.
 Transcation reduction: A transaction does not contain any frequent k-itemset is useless
in subsequent scans.
 Partitoning: Any itemset that is potentially frequent in DB must be frequent in atleast
one of the partitions of DB.

4
 Mining by partitioning the Data
 Sampling: Mining on a subset of given data, lower support threshold + a method to
determine the completeness.
 Dyanamic Itemset counting: Add new candidate itemsets only when all of their subsets
are estimated to be frequent.

Problem or Drawback of Bottlenecks of this Algorithm

 It may need to generate a huge number of candidate sets.

 It may need to repeatedly scan the database and check a large set of candidates by pattern
matching.

FP Growth Mining Frequent Itemsets without Candidate Generation

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.
Algorithm: FP-Growth. Mine frequent itemset using an FP-tree by pattern fragment growth.

Input:

 D, a transaction database.
 Min_sup, the minimum support count threshold.

5
Output:

 The Complete set of frequent patterns.

6
3.3 Pattern Evaluation

Pattern evaluation is used to identify the truly interesting patterns representing knowledge based on some
interestingness measures.
Most association rule mining algorithms employ a support–confidence framework.
Although minimum support and confidence thresholds help weed out or exclude the exploration
of a good number of uninteresting rules, many of the rules generated are still not interesting to
the users.
Unfortunately, this is especially true when mining at low support thresholds or mining for long
patterns. This has been a major bottleneck for successful application of association rule mining.
To tackle this weakness, a correlation measure can be used to augment the support–confidence
framework for association rules. This leads to correlation rules of the form

A correlation rule is measured not only by its support and confidence but also by the correlation
between itemsets A and B. There are many different correlation measures from which to choose.

7
Correlation Measures
1. Lift
Lift is a simple correlation measure that is given as follows. The occurrence of itemset

A is independent of the occurrence of itemset B if ;

otherwise, itemsets A and B are dependent and correlated as events. This definition can
easily be extended to more than two itemsets. The lift between the occurrence of A and B
can be measured by computing

If the resulting value of Eq. (6.8) is less than 1, then the occurrence of A is negatively correlated
with the occurrence of B, meaning that the occurrence of one likely leads to the absence of the
other one.
If the resulting value is greater than 1, then A and B are positively correlated, meaning that the
occurrence of one implies the occurrence of the other.
If the resulting value is equal to 1, then A and B are independent and there is no correlation
between them.
2. Correlation analysis using Chi Square (ᵪ2)
To compute the correlation using ᵪ2 analysis for nominal data, we need the observed
value and expected value (displayed in parenthesis) for each slot of the contingency table,
as shown in Table 6.7.

From the table, we can compute the ᵪ2 value as follows:

8
Support, confidence lift and ᵪ2, often disclose more intrinsic pattern relationships. Researchers
have studied many pattern evaluation measures even before the start of in-depth research on
scalable methods for mining frequent patterns.
There are four such measures: all confidence, max confidence, Kulczynski, and cosine.

9
3.4 Pattern Mining in Multilevel, Multidimensional Space

Mining Multilevel Associations

A concept hierarchy defines a sequence of mappings from a set of low-level concepts to a
higher-level, more general concept set. Data can be generalized by replacing low-level concepts
within the data by their corresponding higher-level concepts, or ancestors, from a concept
hierarchy.
Example: The task-relevant set of transactional data in Table 7.1 for sales in an AllElectronics
store, showing the items purchased for each transaction. The concept hierarchy for the items is
shown in Figure 7.2.

Association rules generated from mining data at multiple abstraction levels are called multiple-
level or multilevel association rules. Multilevel association rules can be mined efficiently using
concept hierarchies under a support-confidence framework.
In general, a top-down strategy is employed, where counts are accumulated for the calculation of
frequent itemsets at each concept level, starting at concept level 1 and working downward in the
hierarchy toward the more specific concept levels, until no more frequent itemsets can be found.
10
For each level, any algorithm for discovering frequent itemsets may be used, such as
Apriori or its variations.

A number of variations to this approach are described next, where each variation involves
“playing” with the support threshold in a slightly different way.

1. Using uniform minimum support for all levels (referred to as uniform support): The
same minimum support threshold is used when mining at each abstraction level. For
example, in Figure 7.3, a minimum support threshold of 5% is used throughout (e.g., for
mining from“computer” downward to “laptop computer”). Both “computer” and “laptop
computer” are found to be frequent, whereas “desktop computer” is not.

2. 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 7.4, 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.

11
 3. Using item or group-based minimum support (referred to as group-based support):
Because users or experts often have insight as to which groups are more important than others, it
is sometimes more desirable to set up user-specific, item, or group-based minimal support
thresholds when miningmultilevel rules. For example, a user could set up the minimum support
thresholds based on product price or on items of interest, such as by setting particularly low
support thresholds for “camera with price over $1000” or “Tablet PC.
Note: A serious side effect of mining multilevel association rules is its generation of many
redundant rules across multiple abstraction levels due to the “ancestor” relationships
among items.

3.5 Mining Multidimensional Associations

 A single dimensional or intradimensional association rule because it contains a single
distinct predicate (e.g., buys) with multiple occurrences (i.e., the predicate occurs more
than once within the rule).

 Association rules that involve two or more dimensions or predicates can be referred to as
multidimensional association rules. Rule below contains three predicates (age,
occupation, and buys), each of which occurs only once in the rule. Hence, we say that it
has no repeated predicates. Multidimensional association rules with no repeated
predicates are called interdimensional association rules.

Multidimensional association rules with repeated predicates, which contain multiple occurrences
of some predicates. These rules are called hybrid-dimensional association rules.

Database attributes can be nominal or quantitative.

The values of nominal (or categorical) attributes are “names of things.” Nominal attributes have
a finite number of possible values, with no ordering among the values (e.g., occupation, brand,
color).
Quantitative attributes are numeric and have an implicit ordering among values (e.g.,age,
income, price).

12
There are two basic approaches regarding the treatment of quantitative attributes, they are
 In the first approach, quantitative attributes are discretized using predefined concept
hierarchies. For example, a concept hierarchy for income may be used to replace the
original numeric values of this attribute by interval labels such as “0..20K,” “21K..30K,”
“31K..40K,” and so on. Here, discretization is static and predetermined. This is refer as
mining multidimensional association rules using static discretization of quantitative
attributes.
 In the second approach, quantitative attributes are discretized or clustered into “bins”
based on the data distribution. These bins may be further combined during the mining
process. The discretization process is dynamic and established so as to satisfy some
mining criteria such as maximizing the confidence of the rules mined. It is referred to as
(dynamic) quantitative association rules

Mining Quantitative Association Rules

There are three methods
(1) a data cube method,
(2) a clustering-based method, and
(3) a statistical analysis method to uncover exceptional behaviors.

1) Data Cube–Based Mining of Quantitative Associations

Data cubes are well suited for the mining of multidimensional association rules: They store
aggregates (e.g., counts) in multidimensional space, which is essential for computing the support
and confidence of multidimensional association rules.
Figure 7.5 shows the lattice of cuboids defining a data cube for the dimensions age, income, and
buys. The cells of an n-dimensional cuboid can be used to store the support counts of the
corresponding n-predicate sets. The base cuboid aggregates the task-relevant data by age,
income, and buys; the 2-D cuboid, (age, income), aggregates by age and income, and so on; the
0-D (apex) cuboid contains the total number of transactions in the task-relevant data.

13
2) Mining Clustering-Based Quantitative Associations
 In Top Down approach, each quantitative dimension, a standard clustering algorithm
(e.g., k-means or a density-based clustering algorithm) can be applied to find clusters in
this dimension that satisfy the minimum support threshold.
 For each cluster, we then examine the 2-D spaces generated by combining the cluster
with a cluster or nominal value of another dimension to see if such a combination passes
the minimum support threshold.
 A bottom-up approach for finding clustering-based frequent patterns works by first
clustering in high-dimensional space to form clusters with support that satisfies the
minimum support threshold, and then projecting and merging those clusters in the space
containing fewer dimensional combinations.
3) Using Statistical Theory to Disclose Exceptional Behavior
 It is possible to discover quantitative association rules that disclose exceptional behavior,
where “exceptional” is defined based on a statistical theory. For example, the following
association rule may indicate exceptional behavior:

14
Mining Rare Patterns and Negative Patterns
An infrequent (or rare) pattern is a pattern with a frequency support that is below (or far
below) a user-specified minimum support threshold.
Example: In jewelry sales data, sales of diamond watches are rare;
Negative Patterns

Example: In supermarket data, if we find that customers frequently buy Coca-Cola Classic or
Diet Coke but not both, then buying Coca-Cola Classic and buying Diet Coke together is
considered a negative (correlated) pattern.

3.6 Constraint-Based Frequent Pattern Mining

Constraint-based mining allows the users to specify intuition or expectations as constraints to
confine the search space.
The constraints can include the following:
 Knowledge type constraints: These specify the type of knowledge to be mined, such as
association, correlation, classification, or clustering.
 Data constraints: These specify the set of task-relevant data.
 Dimension/level constraints: These specify the desired dimensions (or attributes) of the
data, the abstraction levels, or the level of the concept hierarchies to be used in mining.
 Interestingness constraints: These specify thresholds on statistical measures of rule
interestingness such as support, confidence, and correlation.
 Rule constraints: These specify the form of, or conditions on, the rules to be mined.
Such constraints may be expressed as metarules (rule templates), as the maximum or
minimum number of predicates that can occur in the rule antecedent or consequent, or as
relationships among attributes, attribute values, and/or aggregates.

Metarule-Guided Mining of Association Rules

15
A metarule can be used to specify the information describing the form of rules you are interested
in finding. An example of such a metarule is

where P1 and P2 are predicate variables that are instantiated to attributes from the given
database during the mining process, X is a variable representing a customer, and Y and W take on
values of the attributes assigned to P1 and P2, respectively.

Pruning Pattern Space with Pattern Pruning Constraints

Based on how a constraint may interact with the pattern mining process, there are fivevcategories
of pattern mining constraints: (1) antimonotonic, (2) monotonic, (3) succinct, (4) convertible, and
(5) inconvertible.
 If an itemset does not satisfy the rule constraint, none of its supersets can satisfy the
constraint. If a rule constraint obeys this property, it is antimonotonic.
 if an itemset satisfies the rule constraint, so do all of its supersets. If a rule constraint
obeys this property, it is monotonic.
 Succinct enumerate all and only those sets that are guaranteed to satisfy the constraint.
That is,
 if a rule constraint is succinct, we can directly generate precisely the sets that satisfy it,
even before support counting begins.
 The constraint which belongs to none of the above category they are convertible rules.

16