Lecture Note
Mining Frequent Patterns, Associations and Correlations, Part 2
-
University:
California State University, Northridge -
Course:
ME 595A-Z | Experimental Topics Courses in Mechanical Engineering Academic year:
2011
-
Views:
230
Pages:
22
Author:
Kaeden Marsh
Mining Frequent Patterns,
Associations and Correlations
Week 3
Part 1
1 Advanced Methods for Mining
Frequent Itemsets
• Mining frequent itemsets without candidate
generation
– Frequent‐pattern
Frequent pattern growth (FP‐growth—Han,
(FP growth—Han Pei &
Yin @SIGMOD’00)
• Mining frequent itemsets using vertical data
format
– Vertical data format approach (ECLAT
(ECLAT—Zaki
Zaki
@IEEE‐TKDE’00) Mining Various Kinds of
Association Rules
• Mining multilevel association rules
• Miningg multidimensional association rules Mining Multilevel Association Rules (1)
• Data mining systems should provide
capabilities for mining association rules at
multiple levels of abstraction
• Exploration of shared multi‐level mining
(
(Agrawal
l & SSrikant@VLB’95,
ik @
’9 Han &
Fu@VLDB’95)
8 Mining Multilevel Association Rules (2)
• For each level,
level any algorithm for discovering
frequent itemsets may be used, such as
Apriori or its variations
– Using uniform minimum support for all levels
(referred to as uniform support)
– Using reduced minimum support at lower levels
((referred
e e ed to
o as reduced
educed support)
suppo )
– Using item or group‐based minimum support
((referred to as ggroup_based
p_
support)
pp )
9 Table 5.6 Task‐relevant data D.
10 Figure 5.10 A concept hierarchy for AllElectronics computer items.
11 Figure 5.11 Multilevel mining with uniform support.
12 Figure 5.12 Multilevel mining with reduced support.
13 Multilevel mining with group-based support.
14 Mining Multilevel Association Rules (3)
• Side effect
– The generation of many redundant rules across
multiple levels of abstractions due to the ancestor
relationships among items
– buys(X, “laptop computer”) buys(X, “HP
printer”)
[support = 8%, confidence = 70%]
– buys(X,
buys(X “IBM
IBM laptop computer”)
computer )
printer”)
[support = 2%, confidence = 72%]
15
buys(X “HP
buys(X,
HP Mining Multidimensional Association
Rules
l
• Single‐dimensional
Si l di
i
l rules:
l
buys(X, “milk”) ⇒ buys(X, “bread”)
• M
Multi‐dimensional
l i di
i
l rules:
l ≥ 2 dimensions
di
i
or
predicates
– Inter‐dimension assoc. rules (no repeated
predicates)
age(X,”19-25”) ∧ occupation(X,“student”) ⇒
buys(X, “coke”)
– hybrid‐dimension
hybrid dimension assoc
assoc. rules (repeated predicates)
age(X,”19-25”) ∧ buys(X, “popcorn”) ⇒ buys(X,
16
“coke”) Mining Quantitative Association Rules
• ARCS (Association Rule Clustering System): Cluster adjacent rules to
form general association rules using a 2‐D grid
– age(X,”34‐35”) ∧ income(X,”31‐50K”) ⇒ buys(X,”high resolution
TV”)
– Proposed by Lent, Swami and Widom ICDE’97
17 Figure
g
5.14 A 2-D g
grid for tuples
p
representing
p
g customers who p
purchase
high-definition TVs.
age(X,34) ∧ income(X,”31‐40K”) ⇒ buys(X,”high resolution TV”)
age(X,35) ∧ income(X,”31‐40K”) ⇒ buys(X,”high resolution TV”)
age(X,34) ∧ income(X,”41‐50K”) ⇒ buys(X,”high resolution TV”)
age(X,35) ∧ income(X,”40‐50K”) ⇒ buys(X,”high resolution TV”)
age(X,”34‐35”) ∧ income(X,”31‐50K”) ⇒ buys(X,”high resolution TV”)
18 Strong Rules Are Not Necessarily
Interesting (1)
( )
• Suppose
pp
we are interested in analyzing
y g transaction in
AllElectronics with respect to the purchase of computer
games and videos. Let game refer to the transactions
containing computer games, and video refer to those
containing videos. Of the 10,000 transactions analyzed, the
data show that 6,000
6 000 of the customer transactions included
computer games, while 7,500 included videos, and 4,000
included both computer games and videos.
19 Strong Rules Are Not Necessarily
Interesting (2)
( )
• Suppose that a data mining program for discovering
association rules is run on the data, using a minimum
support of, say, 30% and a minimum confidence of
60%. Is the following association rule is strong?
buys(X ”computer
computer games”)
games ) ⇒ buys(X,
buys(X ”videos”)
videos )
• buys(X,
20 Strong Rules Are Not Necessarily
Interesting (3)
( )
• The rule above is misleading because the
probability of purchasing videos is 75%.
• It does not measure the real string of the
correlation and implication computer games
and videos.
• How can we tell which strong association rules
are really interesting?
21 Correlation Analysis
• Correlation measure
A ⇒ B {support, confidence, correlation}
• Correlation
C
l i metrics
i
– lift
– chi‐square
– all_confidence
– cosine measure
22 Correlation Analysis Using Lift
p
u
s
P( A ∪ B ) P( B | A) conf ( A ⇒ B )
lf =
lift
=
=
P( A) P (value
B ) is greater
P( B ) than 1, then(AB and
) B are
• If the resulting
positively correlated,
correlated meaning that the occurrence of one
implies the occurrence of the other
• If the resultingg value is equal
q to 1,, then A and B are
independent and there is no correlation between them
• If the resulting value is less than 1, then the occurrence
of A is negatively correlated with the occurrence of B
23 Correlation Analysis Using Lift
Table 5.7 A 2 X 2 contingency table summarizing the transactions with respect to
game and
d video
id purchases.
h
P( A ∪ B ) P ( B | A) conf ( A ⇒ B )
=
=
P ( A) P( B )
P( B )
( B)
p
u
s
lift =
P({game}) =
P({video}) =
P({game,video}) =
24 Correlation Analysis Using Chi
Chi‐square
square
2
(
−
)
Observed
Expected
χ2 = ∑
Expected
(oij − eij )2
χ 2 = ∑∑
eij
i =1 j =1
c
r
count ( A = ai ) × count ( B = bj )
eij =
N
• The larger the Χ2 value, the more likely the variables are related.
• If the observed value of the cell is less than the expected value
value, two variables associated
with the cell is negatively correlated.
25 Correlation Analysis Using Chi
Chi‐square
square
Table 5.8 The above contingency table, now shown with the expected value.
(Observed − Expected ) 2
χ =∑
=
Expected
2
26
Mining Frequent Patterns, Associations and Correlations, Part 2
of 22
Recommended Documents
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document