Data Mining: Concepts and Techniques October 27, 2020 1

 Association rule mining

 Mining single-dimensional Boolean association rules
from transactional databases
 Mining multilevel association rules from transactional
databases
 Mining multidimensional association rules from
transactional databases and data warehouse
 From association mining to correlation analysis
 Constraint-based association mining
 Summary

Data Mining: Concepts and Techniques October 27, 2020 2

 Association rule mining:
 Finding frequent patterns, associations, correlations, or
causal structures among sets of items or objects in
transaction databases, relational databases, and other
information repositories.
 Applications:
 Basket data analysis, cross-marketing, catalog design,
loss-leader analysis, clustering, classification, etc.
 Examples.
 Rule form: “Body ead [support, confidence]”.
 buys(x, “diapers”)  buys(x, “beers”) [0.5%, 60%]
 major(x, “CS”) ^ takes(x, “DB”) grade(x, “A”) [1%,
75%]
Data Mining: Concepts and Techniques October 27, 2020 3
 Given: (1) database of transactions, (2) each transaction is a
list of items (purchased by a customer in a visit)
 Find: all rules that correlate the presence of one set of items
with that of another set of items
 E.g., 98% of people who purchase tires and auto accessories
also get automotive services done
 Applications
 *  Maintenance Agreement (What the store should do
to boost Maintenance Agreement sales)
 Home Electronics  * (What other products should the
store stocks up?)
 Attached mailing in direct marketing

Data Mining: Concepts and Techniques October 27, 2020 4

Based on the types of values, the association rules can be
classified into two categories:
 Boolean Association Rules and
 Quantitative Association Rules
Example:
Boolean Association Rule
Keyboard ⇒ Mouse [support = 6%, confidence = 70%]
Quantitative Association Rule
(Age = 26…30) ⇒ (Cars =1, 2) [Support 3%, confidence =
36%]

Data Mining: Concepts and Techniques October 27, 2020 5

 Boolean vs. quantitative associations
 (Based on the types of values handled)
 buys(x, “SQLServer”) ^ buys(x, “DMBook”)
buys(x, “DBMiner”) [0.2%, 60%]
 age(x, “30..39”) ^ income(x, “42..48K”) buys(x,
“PC”) [1%, 75%]
 Single dimension vs. multiple dimensional
associations
 Single level vs. multiple-level analysis
 What brands of beers are associated with what
brands of diapers?

Data Mining: Concepts and Techniques October 27, 2020 6

The support of an association pattern is the percentage
of task-relevant data transactions for which the pattern
is true.

IF A ⇒ B

Data Mining: Concepts and Techniques October 27, 2020 7

Confidence is defined as the measure of certainty or
trustworthiness associated with each discovered
pattern.
IF A ⇒ B

Data Mining: Concepts and Techniques October 27, 2020 8

A set of items is referred to as itemset.
An itemset containing k items is called k-itemset.
An itemset can also be seen as a conjunction of items
(or a predicate)

Data Mining: Concepts and Techniques October 27, 2020 9

 Suppose min_sup is the minimum support threshold.
 An itemset satisfies minimum support if the
occurrence frequency of the itemset is greater than or
equal to min_sup.
 If an itemset satisfies minimum support, then it is a
frequent itemset.

Data Mining: Concepts and Techniques October 27, 2020 10

Rules that satisfy both a minimum support threshold
and a minimum confidence threshold are called
strong.

Data Mining: Concepts and Techniques October 27, 2020 11

 Find all frequent itemsets
 Generate strong association rules from the frequent

itemsets

Data Mining: Concepts and Techniques October 27, 2020 12

 The Apriori Algorithm is an influential algorithm for
mining frequent itemsets for boolean association rules.

Key Concepts :

• Frequent Itemsets: The sets of item which has minimum

support (denoted by Li for ith-Itemset).
• Apriori Property: Any subset of frequent itemset must be
frequent.
• Join Operation: To find Lk, a set of candidate k-itemsets is
generated by joining Lk-1with itself.
Data Mining: Concepts and Techniques October 27, 2020 13
Reducing the search space to avoid finding of each L k
requires one full scan of the database

If an itemset I does not satisfy the minimum support

threshold, min_sup, the 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.,I∪A) cannot occur more
frequently than I. Therefore, I ∪ A is not frequent
either, that is, P (I ∪A) < min_sup.

Data Mining: Concepts and Techniques October 27, 2020 14

Find the frequent itemsets: the sets of items that have
minimum support
–A subset of a frequent itemset must also be a frequent
itemset
i.e., if {AB} is a frequent itemset, both {A} and {B}
should be a frequent itemset
–Iteratively find frequent itemsets with cardinality from
1 to k (k-itemset)
– Use the frequent itemsets to generate association
rules.

Data Mining: Concepts and Techniques October 27, 2020 15

 Consider a database, D , consisting of
9 transactions.

Suppose min. support count required

is 2 (i.e. min_sup = 2/9 = 22 % )

Let minimum confidence required is

70%.

We have to first find out the frequent

itemset using Apriori algorithm.

Then, Association rules will be

generated using min. support & min.
confidence.

Data Mining: Concepts and Techniques October 27, 2020 16

The set of frequent 1-itemsets, L1, consists of the
candidate 1-itemsets satisfying minimum support.

In the first iteration of the algorithm, each item is a

member of the set of candidate.

Data Mining: Concepts and Techniques October 27, 2020 17

Data Mining: Concepts and Techniques October 27, 2020 18
The generation of the set of candidate 3-itemsets, C3, involves use of
the Apriori Property.

In order to find C3, we compute L2 Join L2.

C3= L2 Join L2 = {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2,
I3, I5}, {I2, I4, I5}}.

Now, Join step is complete and Prune step will be used to reduce the
size of C3. Prune step helps to avoid heavy computation due to large
Ck. 19
Data Mining: Concepts and Techniques October 27, 2020
Based on the Apriori property that all subsets of a frequent itemset must
also be frequent, we can determine that four latter candidates cannot
possibly be frequent. How ?
For example , lets take {I1, I2, I3}.The 2-item subsets of it are {I1, I2}, {I1, I3} &
{I2, I3}. Since all 2-item subsets of {I1, I2, I3} are members of L2, We will
keep {I1, I2, I3} in C3.
•Lets take another example of {I2, I3, I5}which shows how the pruning is
performed. The 2-item subsets are {I2, I3}, {I2, I5} & {I3,I5}.
•BUT, {I3, I5} is not a member of L2 and hence it is not frequent violating
Apriori Property. Thus We will have to remove {I2, I3, I5} from C3.
•Therefore, C3= {{I1, I2, I3}, {I1, I2, I5}} after checking for all members of
result of Join operation for Pruning.
•Now, the transactions in D are scanned in order to determine L3, consisting
of those candidates 3-itemsets in C3having minimum support.

20
Data Mining: Concepts and Techniques October 27, 2020
 The algorithm uses L3 Join L3 to generate a candidate
set of 4-itemsets, C4. Although the join results in {{I1, I2,
I3, I5}}, this itemset is pruned since its subset {{I2, I3,
I5}} is not frequent.
• Thus, C4= φ, and algorithm terminates, having found all
of the frequent items. This completes our Apriori
Algorithm.
• What’s Next ?
These frequent itemsets will be used to generate strong
association rules (where strong association rules satisfy
both minimum support & minimum confidence).

Data Mining: Concepts and Techniques October 27, 2020 21

Procedure:
• For each frequent itemset “ l ”, generate all nonempty
subsets of l.
• For every nonempty subset s of l, output the rule
“s ->(l-s)” if
support_count(l) / support_count(s) >= min_conf
where min_conf is minimum confidence threshold.

Data Mining: Concepts and Techniques October 27, 2020 22

We had L = {{I1}, {I2}, {I3}, {I4}, {I5}, {I1,I2}, {I1,I3}, {I1,I5},
{I2,I3}, {I2,I4}, {I2,I5}, {I1,I2,I3}, {I1,I2,I5}}.

– Lets take l = {I1,I2,I5}

– Its all nonempty subsets are {I1,I2}, {I1,I5}, {I2,I5},
{I1}, {I2}, {I5}

Data Mining: Concepts and Techniques October 27, 2020 23

Let minimum confidence threshold is , say 70%.
The resulting association rules are shown below, each listed with its
confidence.
–R1: I1 ^ I2 ->I5
Confidence = sc{I1,I2,I5}/sc{I1,I2} = 2/4 = 50%
R1 is Rejected.
–R2: I1 ^ I5 ->I2
Confidence = sc{I1,I2,I5}/sc{I1,I5} = 2/2 = 100%
R2 is Selected.
–R3: I2 ^ I5 ->I1
Confidence = sc{I1,I2,I5}/sc{I2,I5} = 2/2 = 100%
R3 is Selected.

24
Data Mining: Concepts and Techniques October 27, 2020
 –R4: I1 -> I2 ^ I5
Confidence = sc{I1,I2,I5}/sc{I1} = 2/6 = 33%
R4 is Rejected.
–R5: I2 -> I1 ^ I5
Confidence = sc{I1,I2,I5}/{I2} = 2/7 = 29%
R5 is Rejected.
–R6: I5-> I1 ^ I2
Confidence = sc{I1,I2,I5}/ {I5} = 2/2 = 100%
R6 is Selected.

In this way, We have found three strong association rules.

Data Mining: Concepts and Techniques October 27, 2020 25

Data Mining: Concepts and Techniques October 27, 2020 26
 Join Step: Ck is generated by joining Lk-1with itself
 Prune Step: Any (k-1)-itemset that is not frequent cannot be a
subset of a frequent k-itemset
 Pseudo-code:
Ck: Candidate itemset of size k
Lk : frequent itemset of size k
L1 = {frequent items};
for (k = 1; Lk !=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
increment the count of all candidates in Ck+1
that are contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return k Lk;
Data Mining: Concepts and Techniques October 27, 2020 27
Advantages
Uses large itemset property
Easily parallelized
Easy to implement
Disadvantages
Assumes transaction database is memory
resident.
Requires many database scans.

Data Mining: Concepts and Techniques October 27, 2020 28

An example with a transactional data D contents a list of
5 transactions in a supermarket.

Data Mining: Concepts and Techniques October 27, 2020 29

Step 1 min_sup = 40% (2/5)

C1 L1

Data Mining: Concepts and Techniques October 27, 2020 30

Step 2

C2

Step 3

L2

Data Mining: Concepts and Techniques October 27, 2020 31

Step 4: L2 is not Null, so repeat Step2

C3 =Null

Data Mining: Concepts and Techniques October 27, 2020 32

Step 5
min_sup=40% min_conf=70%

Data Mining: Concepts and Techniques October 27, 2020 33

Data Mining: Concepts and Techniques October 27, 2020 34
Step 6
min_sup = 40% min_conf = 70%

Data Mining: Concepts and Techniques October 27, 2020 35

 Some rules are believable, like Baby powder ⇒Diaper.
 Some rules need additional analysis, like Milk ⇒Beer.
 Some rules are unbelievable, like Diaper ⇒ Beer.

Note this example could contain unreal results

because its small data.

Data Mining: Concepts and Techniques October 27, 2020 36

 Association rule mining
 Mining single-dimensional Boolean association rules
from transactional databases
 Mining multilevel association rules from transactional
databases
 Mining multidimensional association rules from
transactional databases and data warehouse
 From association mining to correlation analysis
 Constraint-based association mining
 Summary
Data Mining: Concepts and Techniques October 27, 2020 37
 Hash-based itemset counting: A k-itemset whose corresponding

hashing bucket count is below the threshold cannot be frequent

 Transaction reduction: A transaction that does not contain any

frequent k-itemset is useless in subsequent scans

 Partitioning: Any itemset that is potentially frequent in DB must be

frequent in at least one of the partitions of DB

 Sampling: mining on a subset of given data, lower support threshold

+ a method to determine the completeness

 Dynamic itemset counting: add new candidate itemsets only when

all of their subsets are estimated to be frequent

Data Mining: Concepts and Techniques October 27, 2020 38

 The core of the Apriori algorithm:
 Use frequent (k – 1)-itemsets to generate candidate frequent k-
itemsets
 Use database scan and pattern matching to collect counts for the
candidate itemsets

 The bottleneck of Apriori: candidate generation

 Huge candidate sets:
 Multiple scans of database:

Data Mining: Concepts and Techniques October 27, 2020 39

 Reduce the number of candidates:
A k-itemset whose corresponding hashing bucket count is
below the threshold cannot be frequent.
 While scanning to generate 1-itemsets , we can generate 2-
itemsets for each transaction and hash(map) them into
different buckets of a hash table structure and increase the
corresponding bucket counts. A 2-itemset whose
corresponding bucket count is below the support
threshold can not be frequent.

Data Mining: Concepts and Techniques October 27, 2020 40

 DHP
Apriori
Generate candidate set
Generate candidate set

Count support
Count support

Make new hash table

Data Mining: Concepts and Techniques October 27, 2020 41

 Consider two item sets, all items are numbered as i1, i2, …in.
For any pair (x, y), has according to

 Hash function bucket #=

h({x y}) = ((order of x)*10+(order of y)) % 7
 Example:
 Items = A, B, C, D, E, Order = 1, 2, 3 , 4, 5,
 H({C, E})= (3*10 + 5)% 7 = 0
 Thus, {C, E} belong to bucket 0.

42
Data Mining: Concepts and Techniques October 27, 2020
In k-iteration, hash all “appearing” k+1 itemsets in a
hashtable, count all the occurrences of an itemset in
the correspondent bucket.

In k+1 iteration, examine each of the candidate

itemset to see if its correspondent bucket value is
above the support ( necessary condition )

Data Mining: Concepts and Techniques October 27, 2020 43

TID Items

100 ACD

200 BCE

300 ABCE

400 BE

Data Mining: Concepts and Techniques October 27, 2020 44

Itemset Sup
Itemset Sup
{A} 2
{A} 2
{B} 3
{B} 3
{C} 3
{C} 3
{D} 1
{E} 3
{E} 3

C1 L1
Data Mining: Concepts and Techniques October 27, 2020 45
Find all 2-itemset of each transaction

TID 2-itemset
100 {A C} {A D} {C D}
200 {B C} {B E} {C E}
300 {A B} {A C} {A E} {B C} {B E} {C E}
400 {B E}

Data Mining: Concepts and Techniques October 27, 2020 46

Hash function
h({x y}) = ((order of x)*10+(order of y)) % 7

Hash table
{C E} {A E} {B C} {B E} {A B} {A C}
{C E} {B C} {B E} {C D}
{A D} {B E} {A C}

3
bucket 0
1
1 2
2 3
0 4
3 5
1 6
3

Data Mining: Concepts and Techniques October 27, 2020 47

 # in the C2 of
L1*L1 Apriori
bucket
Resulted {A B}
{A B} 1
C2
{A C} 3 {A C}
{A C}
{A E} 1 {A E}
{B C}
{B C} 2
{B C}
{B E} 3 {B E}
{B E}
{C E} 3 {C E}
{C E}

Data Mining: Concepts and Techniques October 27, 2020 48

 Compress a large database into a compact, Frequent-
Pattern tree (FP-tree) structure
 highly condensed, but complete for frequent pattern
mining
 avoid costly database scans
 Develop an efficient, FP-tree-based frequent pattern mining
method
 A divide-and-conquer methodology: decompose mining
tasks into smaller ones
 Avoid candidate generation: sub-database test only!

Data Mining: Concepts and Techniques October 27, 2020 49

A transaction that does not contain any frequent k-
item sets cannot contain any frequent (k+1) item sets.
Such transactions can be marked or remoned from
further considerations.

Data Mining: Concepts and Techniques October 27, 2020 50

Data Mining: Concepts and Techniques October 27, 2020 51
Use a compressed representation of the database
using an FP-tree

Once an FP-tree has been constructed, it uses a

recursive divide-and-conquer approach to mine the
frequent itemsets

Data Mining: Concepts and Techniques October 27, 2020 52

Data Mining: Concepts and Techniques October 27, 2020 53
Data Mining: Concepts and Techniques October 27, 2020 54
 ECLAT(Equivalence CLASS Transformation Algorithm) :
Developed by Zaki 2000.

 For each item, store a list of transaction ids (tids); vertical data layout

Instead of {TID: itemset} it stores {item: TID_set}

Data Mining: Concepts and Techniques October 27, 2020 55

 Horizontal
Data Layout Vertical Data Layout
TID Items A B C D E
1 A,B,E 1 1 2 2 1
2 B,C,D 4 2 3 4 3
3 C,E 5 5 4 5 6
4 A,C,D 6 7 8 9
5 A,B,C,D 7 8 9
6 A,E 8 10
7 A,B 9
8 A,B,C
9 A,C,D
10 B TID-list

Data Mining: Concepts and Techniques October 27, 2020 56

 Determine support of any k-itemset by intersecting tid-lists of
two of its (k-1) subsets.
A B AB
1 1 1
4 2 5
5
6
 5
7
 7
8
7 8
8 10
9
 3 traversal approaches:
 top-down, bottom-up and hybrid
 Advantage: very fast support counting
 Disadvantage: intermediate tid-lists may become too large for
memory
Data Mining: Concepts and Techniques October 27, 2020 57
Data Mining: Concepts and Techniques October 27, 2020 58
Data Mining: Concepts and Techniques October 27, 2020 59
 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
 if number of frequent items also increases, both computation and
I/O costs may also increase
 Size of database
 since Apriori makes multiple passes, run time of algorithm may
increase with number of transactions
 Average transaction width
 transaction width increases with denser data sets
 This may increase max length of frequent itemsets and traversals of
hash tree (number of subsets in a transaction increases with its
width)
Data Mining: Concepts and Techniques October 27, 2020 60
 Association rule mining
 Mining single-dimensional Boolean association rules
from transactional databases
 Mining multilevel association rules from transactional
databases
 Mining multidimensional association rules from
transactional databases and data warehouse
 From association mining to correlation analysis
 Constraint-based association mining
 Summary
Data Mining: Concepts and Techniques October 27, 2020 61
 Items often form hierarchy.
 Items at the lower level are expected to have lower support.
 Rules regarding itemsets at appropriate levels could be quite useful.
 ARs generated form mining data at multiple levels of abstraction are called
multiple-level or multilevel AR
 Multilevel ARs can be mined under a support-confidence framework.

62
Data Mining: Concepts and Techniques October 27, 2020 63
Top-down strategy is employed, counts are
accumulated for the calculation of frequent itemsets
at each concept level, starting from level1 and working
downward in the hierarchy for more specific concept
levels until no frequent itemsets may be used.
The variations are :
Uniform minimum support for all levels
Using reduced minimum support at lower levels

Data Mining: Concepts and Techniques October 27, 2020 64

The same [Link] is used when mining at each level of
abstraction.
Example:

Data Mining: Concepts and Techniques October 27, 2020 65

 Advantages:

- The search procedure is simplified

- Users are only required to specify min. support threshold.
- Apriori like optimization technique can be applied.
- No need to examine itemsets containing any item whose ancestors do not
have minimum support.

 Disadvantages:
- Unlikely that items at lower levels of abstraction will occur as frequently as
those at higher levels of abstraction.
- If min. Sup. is too high : It could miss some meaningful associations
occurring at low abstraction levels.
- If min. Sup. is too low : It may generate uninteresting associations occurring
at high abstraction levels.

Data Mining: Concepts and Techniques October 27, 2020 66

Each level of abstraction has its own minimum support threshold.
The deeper the level of abstraction , the smaller the corresponding
threshold.

Data Mining: Concepts and Techniques October 27, 2020 67

 Single dimensional or Inter-dimensional AR : It contains a single
predicate (i.e. buys) with multiple occurrences.
 Ex: buys(X, “digital camera”) => buys(X, “HP Printer”)
 Such rules are generally used for transactional data.
 Such data can be stored in relational database or data warehouse
(which is multidimensional by definition)
 Each database attribute or warehouse dimension can be referred as
predicate.
 So we, mine AR containing multiple predicates:
 Ex: age(X, “20….24”) ^ occupation(X, “student”)=> buys(X, “laptop”)
 Multidimensional AR: ARs that involve two or more dimensions or
predicates ({ age, occupation, buys})

68
Each of which occurs only once in the rule , it has no
repeated predicates : Inter-dimensional AR
Hybrid dimensional AR: Multidimensional AR with
repeated predicates.
Ex: age(X, “20….29”) ^ buys(X, “laptop”)=> buys (X, “HP Printer”)
 Database attributes can be:
 Categorical (finite no. of values with no ordering among
the values, occupation, brand, color), are also called
nominal attributes.
 Quantitative (numeric and have implicit ordering among
values ,(ex: age , income, price)

Data Mining: Concepts and Techniques October 27, 2020 69

Techniques for mining multidimensional ARs for
quantitative attributes are :
(a)Discretized using predefined concept hierarchy

Ex: income attribute may be discretized as:

“0…...20k”, “21…..30k”, “31…..40k” and so on.

The discretization occurs before mining hence known as static
discretization.
Referred as mining multidimensional AR using static
discretization of quantitative attributes.

Data Mining: Concepts and Techniques October 27, 2020 70

(b) Discretized using bins

Bins may be further combined during mining process

The process is dynamic
Strategy treats the numeric attribute values as quantities
rather that ranges or categories
Referred to as Dynamic quantitative ARs.

Data Mining: Concepts and Techniques October 27, 2020 71

 Discretized prior to mining using
concept hierarchy.
 Numeric values are replaced by
ranges.
 In relational database, finding all
frequent k-predicate sets will
require k or k+1 table scans.
 Data cube is well suited for
mining.
 The cells of an n-dimensional
cuboid correspond to the
predicate sets.
 Mining from data cubes can be
much faster.

Data Mining: Concepts and Techniques October 27, 2020 72

 Association rule mining
 Mining single-dimensional Boolean association rules
from transactional databases
 Mining multilevel association rules from transactional
databases
 Mining multidimensional association rules from
transactional databases and data warehouse
 From association mining to correlation analysis
 Constraint-based association mining
 Summary
Data Mining: Concepts and Techniques October 27, 2020 73
Two popular measurements:
 support; and
 Confidence

Ex: If A=> B is a rule , then

Support=P(A U B)
Confidence = P(A U B)/ P (B/A)

Data Mining: Concepts and Techniques October 27, 2020 74

 Example 1: (Aggarwal & Yu, PODS98)
 Among 5000 students
 3000 play basketball
 3750 eat cereal
 2000 both play basket ball and eat cereal
 play basketball  eat cereal [40%, 66.7%] is misleading because the
overall percentage of students eating cereal is 75% which is higher
than 66.7%.
 play basketball  not eat cereal [20%, 33.3%] is far more accurate,
although with lower support and confidence

basketball not basketball sum(row)

cereal 2000 1750 3750
not cereal 1000 250 1250
sum(col.) 3000 2000 5000
Data Mining: Concepts and Techniques October 27, 2020 75
Example 2: Of 10,000 transactions analyzed , the data show 6,000
transactions included Computer Games , while 7,500 included Videos,
and 4,000 included both Computer Games and Videos. (Min. Sup= 30
% and Min. Conf= 60%). Rule is :
buys(X, “Computer Games”) => buys (X, “Videos”) [40 %, 66%]
Misleading:
•Because probability of purchasing Videos is 75% which is larger
than 66%.
•Computer Games and Videos are negatively associated because ,
the purchase of one item actually decreases the likelihood of
purchasing the other.
•It does not measure the real strength of correlation and
implication between A and B.

This may lead to unwise business decision.

Data Mining: Concepts and Techniques October 27, 2020 76
To tackle the weakness , a correlation measure can be used :
Correlation Rules
A => B [ Support, Confidence, Correlation]

Various correlation measures are there :

-Lift measure
-Chi-square correlation analysis
-All-confidence
-Cosine measure

P ( A B )
corrA, B 
P ( A) P ( B )

Data Mining: Concepts and Techniques October 27, 2020 77

 The occurrence of itemset A is independent of the
occurrence of itemset B , if
P(A U B) = P(A). P(B)
Otherwise, itemsets A and B are dependent and correlated as
events.
P( A B)
The lift between A and B can be measured as : lift A, B 
P( A) P( B)
If value < 1 : The occurrence of A and B are –vely correlated
If value > 1 : The occurrence of A and B are +vely correlated
If value = 1 : The occurrence of A and B are independent
and no correlation exists between them.

Data Mining: Concepts and Techniques October 27, 2020 78

 P( A B ) Is equivalent to :
lift A, B  P(B/A)/ P(B)
P( A) P( B)
or
confidence (A=> B)/ Support(B)

In other words, it asses the degree to which the occurrence

of one lifts the occurrence of other.

Example:
If A=Computer Games & B= Videos then,
Given the market conditions , the sale of games is said to
increase or lift the likelihood of the sale of videos by a factor
of the value returned by the equation.

Data Mining: Concepts and Techniques October 27, 2020 79

From the table :
P( {game})=0.60
P({video})=0.75
P({game, video})=0.40
Lift (game, video)=P({ game, video})/P( {game}). P({video})
= 0.40/(0.60 * 0.75) = 0.89
o.89 < 1 , -ve correlation between occurrence of {game} and {video}
The numerator => likelihood of a customer purchasing both while,
denominator => what the likelihood have been if the two purchases are completely
independent.
Such negative correlations can not be found using support and confidence framework.

80
 Because Chi-square value > 1 and the observed value
of the slot ( game, video)=4,000, which is less than
the expected value 4,500, buying game and buying
video are negatively correlated.

Data Mining: Concepts and Techniques October 27, 2020 81

 Interactive, exploratory mining giga-bytes of data?
 Could it be real? — Making good use of constraints!
 What kinds of constraints can be used in mining?
 Knowledge type constraint: classification, association, etc.
 Data constraint: Specify the task relevant data, SQL-like
queries
 Dimension/level constraints: Specify the desired
dimension of data.
 in relevance to region, price, brand, customer category.
 Rule constraints: Specify the form of rules to be mined
 small sales (price < $10) triggers big sales (sum > $200).
 Interestingness constraints: Specify thresholds or
statistical measures
 strong rules (min_support  3%, min_confidence  60%).

Data Mining: Concepts and Techniques October 27, 2020 82

 R. Agarwal, C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent
itemsets. In Journal of Parallel and Distributed Computing (Special Issue on High Performance Data
Mining), 2000.
 R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large
databases. SIGMOD'93, 207-216, Washington, D.C.
 R. Agrawal and R. Srikant. Fast algorithms for mining association rules. VLDB'94 487-499, Santiago,
Chile.
 R. Agrawal and R. Srikant. Mining sequential patterns. ICDE'95, 3-14, Taipei, Taiwan.
 R. J. Bayardo. Efficiently mining long patterns from databases. SIGMOD'98, 85-93, Seattle, Washington.
 S. Brin, R. Motwani, and C. Silverstein. Beyond market basket: Generalizing association rules to
correlations. SIGMOD'97, 265-276, Tucson, Arizona.
 S. Brin, R. Motwani, J. D. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market
basket analysis. SIGMOD'97, 255-264, Tucson, Arizona, May 1997.
 K. Beyer and R. Ramakrishnan. Bottom-up computation of sparse and iceberg cubes. SIGMOD'99, 359-
370, Philadelphia, PA, June 1999.
 D.W. Cheung, J. Han, V. Ng, and C.Y. Wong. Maintenance of discovered association rules in large
databases: An incremental updating technique. ICDE'96, 106-114, New Orleans, LA.
 M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. D. Ullman. Computing iceberg queries
efficiently. VLDB'98, 299-310, New York, NY, Aug. 1998.

Data Mining: Concepts and Techniques October 27, 2020 83

 G. Grahne, L. Lakshmanan, and X. Wang. Efficient mining of constrained correlated sets. ICDE'00, 512-521,
San Diego, CA, Feb. 2000.
 Y. Fu and J. Han. Meta-rule-guided mining of association rules in relational databases. KDOOD'95, 39-46,
Singapore, Dec. 1995.
 T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama. Data mining using two-dimensional optimized
association rules: Scheme, algorithms, and visualization. SIGMOD'96, 13-23, Montreal, Canada.
 E.-H. Han, G. Karypis, and V. Kumar. Scalable parallel data mining for association rules. SIGMOD'97, 277-
288, Tucson, Arizona.
 J. Han, G. Dong, and Y. Yin. Efficient mining of partial periodic patterns in time series database. ICDE'99,
Sydney, Australia.
 J. Han and Y. Fu. Discovery of multiple-level association rules from large databases. VLDB'95, 420-431,
Zurich, Switzerland.
 J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. SIGMOD'00, 1-12, Dallas,
TX, May 2000.
 T. Imielinski and H. Mannila. A database perspective on knowledge discovery. Communications of ACM,
39:58-64, 1996.
 M. Kamber, J. Han, and J. Y. Chiang. Metarule-guided mining of multi-dimensional association rules using
data cubes. KDD'97, 207-210, Newport Beach, California.
 M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A.I. Verkamo. Finding interesting rules from
large sets of discovered association rules. CIKM'94, 401-408, Gaithersburg, Maryland.

Data Mining: Concepts and Techniques October 27, 2020 84

 F. Korn, A. Labrinidis, Y. Kotidis, and C. Faloutsos. Ratio rules: A new paradigm for fast, quantifiable
data mining. VLDB'98, 582-593, New York, NY.
 B. Lent, A. Swami, and J. Widom. Clustering association rules. ICDE'97, 220-231, Birmingham, England.

 H. Lu, J. Han, and L. Feng. Stock movement and n-dimensional inter-transaction association rules.
SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'98), 12:1-12:7,
Seattle, Washington.
 H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules.
KDD'94, 181-192, Seattle, WA, July 1994.
 H. Mannila, H Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. Data
Mining and Knowledge Discovery, 1:259-289, 1997.
 R. Meo, G. Psaila, and S. Ceri. A new SQL-like operator for mining association rules. VLDB'96, 122-133,
Bombay, India.
 R.J. Miller and Y. Yang. Association rules over interval data. SIGMOD'97, 452-461, Tucson, Arizona.

 R. Ng, L. V. S. Lakshmanan, J. Han, and A. Pang. Exploratory mining and pruning optimizations of
constrained associations rules. SIGMOD'98, 13-24, Seattle, Washington.
 N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequent closed itemsets for association
rules. ICDT'99, 398-416, Jerusalem, Israel, Jan. 1999.

Data Mining: Concepts and Techniques October 27, 2020 85

 J.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD'95, 175-
186, San Jose, CA, May 1995.
 J. Pei, J. Han, and R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets. DMKD'00,
Dallas, TX, 11-20, May 2000.
 J. Pei and J. Han. Can We Push More Constraints into Frequent Pattern Mining? KDD'00. Boston, MA. Aug.
2000.
 G. Piatetsky-Shapiro. Discovery, analysis, and presentation of strong rules. In G. Piatetsky-Shapiro and W. J.
Frawley, editors, Knowledge Discovery in Databases, 229-238. AAAI/MIT Press, 1991.
 B. Ozden, S. Ramaswamy, and A. Silberschatz. Cyclic association rules. ICDE'98, 412-421, Orlando, FL.
 J.S. Park, M.S. Chen, and P.S. Yu. An effective hash-based algorithm for mining association rules. SIGMOD'95, 175-
186, San Jose, CA.
 S. Ramaswamy, S. Mahajan, and A. Silberschatz. On the discovery of interesting patterns in association rules.
VLDB'98, 368-379, New York, NY..
 S. Sarawagi, S. Thomas, and R. Agrawal. Integrating association rule mining with relational database systems:
Alternatives and implications. SIGMOD'98, 343-354, Seattle, WA.
 A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases.
VLDB'95, 432-443, Zurich, Switzerland.
 A. Savasere, E. Omiecinski, and S. Navathe. Mining for strong negative associations in a large database of
customer transactions. ICDE'98, 494-502, Orlando, FL, Feb. 1998.

Data Mining: Concepts and Techniques October 27, 2020 86

 C. Silverstein, S. Brin, R. Motwani, and J. Ullman. Scalable techniques for mining causal structures.
VLDB'98, 594-605, New York, NY.
 R. Srikant and R. Agrawal. Mining generalized association rules. VLDB'95, 407-419, Zurich, Switzerland,
Sept. 1995.
 R. Srikant and R. Agrawal. Mining quantitative association rules in large relational tables. SIGMOD'96, 1-12,
Montreal, Canada.
 R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. KDD'97, 67-73, Newport
Beach, California.
 H. Toivonen. Sampling large databases for association rules. VLDB'96, 134-145, Bombay, India, Sept. 1996.

 D. Tsur, J. D. Ullman, S. Abitboul, C. Clifton, R. Motwani, and S. Nestorov. Query flocks: A generalization
of association-rule mining. SIGMOD'98, 1-12, Seattle, Washington.
 K. Yoda, T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama. Computing optimized rectilinear regions
for association rules. KDD'97, 96-103, Newport Beach, CA, Aug. 1997.
 M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. Parallel algorithm for discovery of association rules.
Data Mining and Knowledge Discovery, 1:343-374, 1997.
 M. Zaki. Generating Non-Redundant Association Rules. KDD'00. Boston, MA. Aug. 2000.

 O. R. Zaiane, J. Han, and H. Zhu. Mining Recurrent Items in Multimedia with Progressive Resolution
Refinement. ICDE'00, 461-470, San Diego, CA, Feb. 2000.

Data Mining: Concepts and Techniques October 27, 2020 87

Thank you !!!
Data Mining: Concepts and Techniques October 27, 2020 88