Lecture No - 4,5,6

Bismita Barik
Dept of CSE
Dronacharya Group of Institution
Data Mining: Concepts and Techniques
August 18, 2015
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
August 18, 2015
Proposed by Agrawal et al in 1993.

It is an important data mining model studied
extensively by the database and data

mining community.
Assume all data are categorical.
No good algorithm for numeric data.
Initially used for Market Basket Analysis to
find how items purchased by customers are
related.
Bread Milk [sup = 5%, conf = 100%]
August 18, 2015
I = {i1, i2, , im}: a set of items.

Transaction t :
t a set of items, and t I.

Transaction Database T: a set of transactions
T = {t1, t2, , tn}.
August 18, 2015
Market basket transactions:
t1: {bread, cheese, milk}

t2: {apple, eggs, salt, yogurt}
tn: {biscuit, eggs, milk}

Concepts:
An item: an item/article in a basket
I: the set of all items sold in the store
A transaction: items purchased in a basket; it
may have TID (transaction ID)

A transactional dataset: A set of transactions
August 18, 2015
A text document data set. Each
document is treated as a bag of

keywords
doc1:
doc2:
doc3:
doc4:
doc5:
doc6:
doc7:
Student, Teach, School

Student, School
Teach, School, City, Game
Baseball, Basketball
Basketball, Player, Spectator
Baseball, Coach, Game, Team
Basketball, Team, City, Game
August 18, 2015
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%]
August 18, 2015
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
August 18, 2015
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 = 2630) (Cars =1, 2) [Support 3%,
confidence = 36%]
August 18, 2015
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?
August 18, 2015
10
A transaction t contains X, a set of items
(itemset) in I, if X t.
An association rule is an implication of the
form:
X Y, where X, Y I, and X Y =
An itemset is a set of items.
E.g., X = {milk, bread, cereal} is an itemset.
A k-itemset is an itemset with k items.

E.g., {milk, bread, cereal} is a 3-itemset
August 18, 2015
11
The support of an association pattern is the

percentage of task-relevant data transactions for
which the pattern is true.
IF A B
August 18, 2015
12
Confidence is defined as the measure of

certainty or
trustworthiness associated with each discovered
pattern.
IF A B
August 18, 2015
13
Support: The rule holds with support sup in T
(the transaction data set) if sup% of

transactions contain X Y.
sup = Pr(X Y).
Confidence: The rule holds in T with
confidence conf if conf% of transactions that

contain X also contain Y.
conf = Pr(Y | X)
An association rule is a pattern that states
when X occurs, Y occurs with certain

probability.
August 18, 2015
14
Support count: The support count of an
itemset X, denoted by X.count, in a data set T

is the number of transactions in T that contain
X. Assume T has n transactions.
Then,
( X Y ).count
support
n
( X Y ).count
confidence
X .count
August 18, 2015
15
Goal: Find all rules that satisfy the user-
specified minimum support (minsup) and

minimum confidence (minconf).
Key Features
Completeness: find all rules.
No target item(s) on the right-hand-side
Mining with data on hard disk (not in memory)
August 18, 2015
16
t1: Beef, Chicken, Milk

t2: Beef, Cheese
t3: Cheese, Boots
t4: Beef, Chicken, Cheese
t5: Beef, Chicken, Clothes, Cheese,
Milk
t6: Chicken, Clothes, Milk
t7: Chicken, Milk, Clothes
Transaction data
Assume:
minsup = 30%
minconf = 80%
An example frequent itemset:
{Chicken, Clothes, Milk}
[sup = 3/7]
Association rules from the itemset:
Clothes Milk, Chicken [sup = 3/7, conf = 3/3]
Clothes, Chicken Milk,

[sup = 3/7, conf =
3/3]
August 18, 2015
17
A simplistic view of shopping baskets,

Some important information not considered.
E.g,
the quantity of each item purchased and
the price paid.
August 18, 2015
18
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)
August 18, 2015
19
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.
August 18, 2015
20
Rules that satisfy both a minimum support

threshold
and
a
minimum
confidence
threshold are called strong.
August 18, 2015
21
Find all frequent itemsets

Generate strong association rules from the
frequent
itemsets
August 18, 2015
22
There are a large number of them!!

They use different strategies and data
structures.
Their resulting sets of rules are all the same.
Given a transaction data set T, and a minimum
support and a minimum confident, the set of

association rules existing in T is uniquely determined.
Any algorithm should find the same set of rules
although their computational efficiencies and

memory requirements may be different.
We study only one: the Apriori Algorithm
August 18, 2015
23
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 kData Mining: Concepts and Techniques
August 18, 2015
24
itemsets is
Reducing the search space to avoid finding of

each Lk 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.,IA) cannot occur more
frequently than I. Therefore, I A is not
frequent either, that is, P (I A) < min_sup.
August 18, 2015
25
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.
August 18, 2015
26
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.
Data Mining: Concepts
andconfidence.
Techniques
August 18, 2015
27
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.
August 18, 2015
28
August 18, 2015
29
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.
August 18, 2015
30
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.
31
August 18, 2015
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.
Whats Next ?
These frequent itemsets will be used to generate
strong association rules (where strong association
rules satisfy both minimum support & minimum
confidence).
August 18, 2015
32
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.
August 18, 2015
33
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}
August 18, 2015
34
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
R2 is Selected.
R3: I2 ^ I5 ->I1
R3 is Selected.
35
August 18, 2015
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.
August 18, 2015
36
Dataset T
TID
minsup=0.5
T100 1, 3, 4
Items
T200 2, 3, 5
T300 1, 2, 3, 5
T400 2, 5
August 18, 2015
37
August 18, 2015
38
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;
August 18, 2015
39
Seems to be very expensive

Level-wise search
K = the size of the largest itemset
It makes at most K passes over data
In practice, K is bounded (10).
The algorithm is very fast. Under some
conditions, all rules can be found in linear
time.
Scale up to large data sets
August 18, 2015
40
Advantages
Uses large itemset property

Easily parallelized
Easy to implement
Disadvantages
Assumes transaction database is
memory resident.
Requires many database scans.
August 18, 2015
41
Clearly the space of all association rules is
exponential, O(2m), where m is the number of

items in I.
The mining exploits sparseness of data, and
high minimum support and high minimum
confidence values.
Still, it always produces a huge number of
rules, thousands, tens of thousands,
millions, ...
August 18, 2015
42
An example with a transactional data D contents

a list of 5 transactions in a supermarket.
August 18, 2015
43
Step 1 min_sup = 40% (2/5)

C1
L1
August 18, 2015
44
Step 2
C2
Step 3
L2
August 18, 2015
45
Step 4: L2 is not Null, so repeat Step2
C3 =Null
August 18, 2015
46
Step 5
min_sup=40% min_conf=70%
August 18, 2015
47
August 18, 2015
48
Step 6
min_sup = 40% min_conf = 70%
August 18, 2015
49
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.
August 18, 2015
50



Summary
August 18, 2015
51
Hash-based
itemset
counting:
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

August 18, 2015
52
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:
August 18, 2015
53
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.
August 18, 2015
54
DHP
Apriori
Generate candidate set
Generate candidate set
Count support
Count support
Make new hash table
August 18, 2015
55
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.
August 18, 2015
56
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 )
August 18, 2015
57
TID
Items
100
ACD
200
BCE
300
ABCE
400
BE
August 18, 2015
58
Itemset
Sup
{A}
{B}
{C}
{D}
{E}
Itemset
Sup
{A}
{B}
{C}
{E}
C1
L1
August 18, 2015
59
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}
August 18, 2015
60
Hash function
h({x y}) = ((order of x)*10+(order of y)) % 7

Hash table
{C E}
{C E}
{A D}
bucket 0
{A E}
1
1
{B C}
{B C}
{B E}
{B E}
{B E}
{A B} {A C}
{C D}
{A C}
August 18, 2015
61
L1*L1
# in the
bucket
{A B}
{A C}
{A E}
{B C}
{B E}
3
1
2
3
{C E}
C2 of
Apriori
Resulted
C2
{A C}
{B C}
{B E}
{C E}
{A B}
{A C}
{A E}
{B C}
{B E}
{C E}
August 18, 2015
62
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!
August 18, 2015
63
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.
August 18, 2015
64
August 18, 2015
65
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
August 18, 2015
66
August 18, 2015
67
August 18, 2015
68
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}
August 18, 2015
69
TID-list
August 18, 2015
70
Determine support of any k-itemset by intersecting tid-
lists of two of its (k-1) subsets.

A
1
4
5
6
7
8
9
B
1
2
5
7
8
10
AB
1
5
7
8
3 traversal approaches:
top-down, bottom-up and hybrid
Advantage: very fast support counting
Disadvantage: intermediate tid-lists may become too
large for memory
August 18, 2015
71
August 18, 2015
72
August 18, 2015
73
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)
August 18, 2015
74


Mining
multilevel association
rules
from

Summary
August 18, 2015
75
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.
76
August 18, 2015
77
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
August 18, 2015
78
The same min.support is used when mining at each
level of abstraction.
Example:
August 18, 2015
79
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.
August 18, 2015
80
Each level of abstraction has its own minimum support
threshold.
The deeper the level of abstraction , the smaller the
corresponding threshold.
August 18, 2015
81
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})
82
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)
August 18, 2015
83
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.
August 18, 2015
84
(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.
August 18, 2015
85
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.
August 18, 2015
86



Summary
August 18, 2015
87
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)
August 18, 2015
88
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
August 18, 2015
89
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.
Mining:
and Techniques
August 18,
2015
This may Data
lead
toConcepts
unwise
business
decision.
90
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
corrA, B
August 18, 2015
P ( A B )
P ( A) P ( B )
91
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.
August 18, 2015
92
Is equivalent to :
lift A, B
P(B/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.
P( A B )
P( A) P( B)
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.
August 18, 2015
93
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.
94
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.
August 18, 2015
95
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, SQLlike 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%).
August 18, 2015
96
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.

August 18, 2015
97
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.
August 18, 2015
98
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.

August 18, 2015
99
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.
August 18, 2015
100
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:
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.
August 18, 2015
101
Thank you !!!

August 18, 2015
102

Lecture No - 4,5,6

Uploaded by

Copyright:

Available Formats

Lecture No - 4,5,6

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture No - 4,5,6

Uploaded by

Copyright:

Available Formats

Bismita Barik

Data Mining: Concepts and Techniques

August 18, 2015

Association rule mining

rules from transactional databases

transactional databases and data warehouse

August 18, 2015

Proposed by Agrawal et al in 1993.

extensively by the database and data

August 18, 2015

I = {i1, i2, , im}: a set of items.

t a set of items, and t I.

T = {t1, t2, , tn}.

Data Mining: Concepts and Techniques

August 18, 2015

Market basket transactions:

t1: {bread, cheese, milk}

tn: {biscuit, eggs, milk}

may have TID (transaction ID)

August 18, 2015

A text document data set. Each

document is treated as a bag of

Student, Teach, School

August 18, 2015

August 18, 2015

Given: (1) database of transactions, (2) each

transaction is a list of items (purchased by a

August 18, 2015

Based on the types of values, the association rules

August 18, 2015

vs. quantitative associations

August 18, 2015

A transaction t contains X, a set of items

A k-itemset is an itemset with k items.

Data Mining: Concepts and Techniques

August 18, 2015

The support of an association pattern is the

Data Mining: Concepts and Techniques

August 18, 2015

Confidence is defined as the measure of

Data Mining: Concepts and Techniques

August 18, 2015

Support: The rule holds with support sup in T

(the transaction data set) if sup% of

Confidence: The rule holds in T with

confidence conf if conf% of transactions that

An association rule is a pattern that states

when X occurs, Y occurs with certain

August 18, 2015

Support count: The support count of an

itemset X, denoted by X.count, in a data set T

August 18, 2015

Goal: Find all rules that satisfy the user-

specified minimum support (minsup) and

Data Mining: Concepts and Techniques

August 18, 2015

t1: Beef, Chicken, Milk

Clothes Milk, Chicken [sup = 3/7, conf = 3/3]

Clothes, Chicken Milk,