ọ ọ
ậ ậ
Khoa Khoa H c & K Thu t Máy Tính Khoa Khoa H c & K Thu t Máy Tính
ạ ọ ạ ọ
ồ ồ
ườ ườ
ỹ ỹ ng Đ i H c Bách Khoa Tp. H Chí Minh ng Đ i H c Bách Khoa Tp. H Chí Minh
Tr Tr
ươ ươ
ậ ế ợ ậ ế ợ
Ch Ch
ng 6: Khai phá lu t k t h p ng 6: Khai phá lu t k t h p
ữ ệ
Khai phá d li u
(Data mining)
1
ọ
ỳ
H c k 1 – 20092010
ộ
N i dung
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ể
6.2. Bi u di n lu t k t h p ễ
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ậ ế ợ ừ
ẫ
ườ
6.4. Khám phá các lu t k t h p t
các m u th
ng
xuyên
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu c ộ ậ ế ợ
ươ
6.6. Phân tích t
ng quan
6.7. Tóm t
tắ
2
ệ
ả
Tài li u tham kh o
[1] Jiawei Han, Micheline Kamber, “Data Mining: Concepts and Techniques”, Second Edition, Morgan Kaufmann Publishers, 2006.
[2] David Hand, Heikki Mannila, Padhraic Smyth, “Principles of
[3] David L. Olson, Dursun Delen, “Advanced Data Mining
Data Mining”, MIT Press, 2001.
Techniques”, SpringerVerlag, 2008.
[4] Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, Methodology, Techniques, and Applications”, SpringerVerlag, 2006.
[5] ZhaoHui Tang, Jamie MacLennan, “Data Mining with SQL
[6] Oracle, “Data Mining Concepts”, B2812901, 2008.
[7] Oracle, “Data Mining Application Developer’s Guide”, B2813101,
Server 2005”, Wiley Publishing, 2005.
3
2008.
ố
6.0. Tình hu ng 1 – Market basket analysis
4
ế
ố
ị
6.0. Tình hu ng 2 Ti p th chéo
5
ế
ố
ị
6.0. Tình hu ng 2 Ti p th chéo
6
6.0. Tình hu ng …ố
ữ ệ
ỏ
Phân tích d li u gi
hàng (basket data analysis)
ế
ị
Ti p th chéo (crossmarketing)
ế ế
Thi
t k catalog (catalog design)
ạ ữ ệ
ụ
Phân lo i d li u (classification) và gom c m d ữ
ổ ế
ẫ
ớ ệ li u (clustering) v i các m u ph bi n
…
7
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
Quá trình khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
ậ ế ợ
ạ
Phân lo i lu t k t h p
8
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
Quá trình khai phá lu t k t h p
Pre processing
Post processing
Mining
Raw Data
Items of Interest
User
Relationships among Items (Rules)
9
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
Quá trình khai phá lu t k t h p
Pre processing
Post processing
Mining
Raw Data
Items of Interest
User
Relationships among Items (Rules)
Items
Transactional/ Relational Data
Association Rules
A, B, C, D, F, …
A (cid:0) C (50%, 66.6%) …
Transaction Items_bought A, B, C 2000 A, C 1000 A, D 4000 B, E, F 5000 …
10
Bài toán phân tích gi Bài toán phân tích gi ỏ ị ườ ỏ ị ườ th tr th tr ng ng
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ủ
ẫ
D li u m u c a AllElectronics (sau quá trình
ữ ệ ử ề
ti n x lý)
11
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
Item (ph n t ) ầ ử
Itemset (t p ph n t ) ầ ử ậ
ị
Transaction (giao d ch)
ậ ế ợ
ự ế ợ
Association (s k t h p) và association rule (lu t k t h p)
Support (đ h tr ) ộ ỗ ợ
ậ
ộ
Confidence (đ tin c y)
ầ ử
ậ
ườ
Frequent itemset (t p ph n t
ổ ế ph bi n/th
ng xuyên)
ậ ế ợ
ạ
Strong association rule (lu t k t h p m nh)
12
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ủ
ẫ
D li u m u c a AllElectronics (sau quá trình
ữ ệ ử ề
ti n x lý)
Item: I4
Itemsets: {I1, I2, I5}, {I2}, …
Transaction: T800
13
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
Item (ph n t ) ầ ử
Các ph n t
ầ ử ố ượ ẫ ượ , m u, đ i t ng đang đ c quan tâm.
J = {I1, I2, …, Im}: t p t
ậ ấ ả ầ ử ể ậ t c m ph n t ữ có th có trong t p d
Itemset (t p ph n t ) ầ ử ậ ợ
li uệ
T p h p các items
ậ
M t itemset có k items g i là kitemset.
ị
Transaction (giao d ch)
ọ ộ
ầ ớ ệ ố ụ ị ự L n th c hi n t ng tác v i h th ng (ví d : giao d ch “khách
ệ ươ hàng mua hàng”)
Liên h v i m t t p T g m các ph n t
ộ ậ ệ ớ ầ ử ượ ồ ị đ
c giao d ch 14
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
ự ế ợ
ậ ế
Association (s k t h p) và association rule (lu t k t
h p)ợ
ự ế ợ ầ ử ệ ấ ộ ớ cùng xu t hi n v i nhau trong m t
S k t h p: các ph n t hay nhi u giao d ch.
ệ ữ
ể ệ
ầ ử
ố
ầ ử
ậ
Th hi n m i liên h gi a các ph n t
/các t p ph n t
ề ị
Lu t k t h p: qui t c k t h p có đi u ki n gi a các t p ph n
ậ ế ợ ế ợ ữ ệ ề ầ ậ ắ
ể ệ
ầ ử
ữ
ệ
ệ
ậ
ố
Th hi n m i liên h (có đi u ki n) gi a các t p ph n t ề
ầ ử
ậ
ậ ế ợ
Cho A và B là các t p ph n t
ữ , lu t k t h p gi a A và B là A
B.
ệ
ề
ệ
ệ
ấ
ấ
B xu t hi n trong đi u ki n A xu t hi n.
15
t .ử
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
Support (đ h tr ) ộ ỗ ợ
ầ ử ậ ầ ử ủ ệ ầ ộ ố ấ Đ đo đo t n s xu t hi n c a các ph n t /t p ph n t .
Minimum support threshold (ng
ấ ượ
ỏ
ị
ở
ỉ
ị
ườ
Giá tr support nh nh t đ
c ch đ nh b i ng
i dùng.
ậ
ộ
Confidence (đ tin c y)
ưỡ ỗ ợ ố ng h tr t ể i thi u)
Đ đo đo t n s xu t hi n c a m t t p ph n t
ộ ậ ầ ử ủ ầ ấ ố ề trong đi u
ầ ử ệ ấ ệ ộ ậ ộ ệ ủ ki n xu t hi n c a m t t p ph n t khác.
Minimum confidence threshold (ng
ấ ượ
ỏ
ị
ở
ỉ
ị
ườ
Giá tr confidence nh nh t đ
c ch đ nh b i ng
i dùng.
16
ưỡ ậ ố ng tin c y t ể i thi u)
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ơ ả
ệ
Các khái ni m c b n
ầ ử
ậ
Frequent itemset (t p ph n t
ổ ế ph bi n)
T p ph n t
ầ ử ậ ỏ có support th a minimum support threshold.
Cho A là m t itemset
A là frequent itemset iff support(A) >= minimum support threshold.
ậ ế ợ
ạ
Strong association rule (lu t k t h p m nh)
ộ
Lu t k t h p có support và confidence th a minimum support
ậ ế ợ ỏ
threshold và minimum confidence threshold.
Cho lu t k t h p A
ữ
support threshold và confidence(AB) >= minimum confidence threshold.
17
ậ ế ợ B gi a A và B, A và B là itemsets AB là strong association rule iff support(AB) >= minimum
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ạ
Phân lo i lu t k t h p
ậ ế ợ
ậ
Boolean association rule (lu t k t h p lu n lý)/quantitative
ậ ế ợ ượ
association rule (lu t k t h p l
ố ng s )
ậ ế ợ
Singledimensional association rule (lu t k t h p đ n
ơ ậ ế ợ
ề chi u)/multidimensional association rule (lu t k t h p đa chi u)ề
ậ ế ợ
Singlelevel association rule (lu t k t h p đ n
ứ
ứ
ơ ậ ế ợ
m c)/multilevel association rule (lu t k t h p đa m c)
ậ ế ợ
ậ ươ
Association rule (lu t k t h p)/correlation rule (lu t t
ng
ố quan th ng kê)
18
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ạ
Phân lo i lu t k t h p
ậ ế ợ
Boolean association rule (lu t k t h p lu n
ậ ậ ế ợ ượ
lý)/quantitative association rule (lu t k t h p l
ố ng s )
Boolean association rule: lu t mô t
ả ự ế ợ ự ệ ữ s k t h p gi a s hi n
Computer Financial_management_software [support=2%,
confidence=60%]
ệ ắ ậ ầ ử ặ ủ di n/v ng m t c a các ph n t .
Quantitative association rule: lu t mô t
ậ ả ự ế ợ ữ s k t h p gi a các
Age(X, “30..39”) (cid:0) Income(X, “42K..48K”) buys(X, high
resolution TV)
19
ầ ử ộ ị ượ ph n t /thu c tính đ nh l ng.
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ạ
Phân lo i lu t k t h p
ậ ế ợ
Singledimensional association rule (lu t k t h p đ n
ơ ậ ế ợ
ề chi u)/multidimensional association rule (lu t k t h p đa chi u)ề
Singledimensional association rule: lu t ch liên quan đ n các ề
ế ỉ
Buys(X, “computer”) Buys(X, “financial_management_software”)
ậ ữ ệ ầ ử ủ ộ ộ /thu c tính c a m t chi u d li u. ph n t
Multidimensional association rule: lu t liên quan đ n các ph n ộ
ế ầ
Age(X, “30..39”) Buys(X, “computer”)
20
ủ ơ ộ ậ ề ề /thu c tính c a nhi u h n m t chi u. ử t
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ạ
Phân lo i lu t k t h p
ậ ế ợ
ơ
ậ ế ợ
ứ
Singlelevel association rule (lu t k t h p đ n m c) ứ /multilevel association rule (lu t k t h p đa m c)
ế ầ
Age(X, “30..39”) Buys(X, “computer”)
Age(X, “18..29”) Buys(X, “camera”)
ậ Singlelevel association rule: lu t ch liên quan đ n các ph n ừ ượ ở ộ ử ộ ứ m t m c tr u t /thu c tính ỉ ng. t
Multilevel association rule: lu t liên quan đ n các ph n t
ầ ử ế ậ ộ /thu c
Age(X, “30..39”) Buys(X, “laptop computer”)
Age(X, “30..39”) Buys(X, “computer”)
21
ở ừ ượ tính ứ các m c tr u t ng khác nhau.
ậ ế ợ
ề
ổ
6.1. T ng quan v khai phá lu t k t h p
ậ ế ợ
ạ
Phân lo i lu t k t h p
ậ ế ợ
ậ ươ
Association rule (lu t k t h p)/correlation rule (lu t t
ng
ố quan th ng kê)
Association rule: strong association rules AB (association rules
ứ ầ
đáp ng yêu c u minimum support threshold và minimum confidence threshold).
Correlation rule: strong association rules A B đáp ng yêu c u
ứ ầ
22
ề ự ươ ữ ố v s t ng quan th ng kê gi a A và B.
ậ ế ợ
ễ
ể
6.2. Bi u di n lu t k t h p
ạ
D ng lu t: A
ậ B [support, confidence]
ướ
Cho tr
c minimum support threshold (min_sup),
minimum confidence threshold (min_conf)
A và B là các itemsets
Frequent itemsets/subsequences/substructures
Closed frequent itemsets
Maximal frequent itemsets
Constrained frequent itemsets
Approximate frequent itemsets
Topk frequent itemsets
23
ậ ế ợ
ễ
ể
6.2. Bi u di n lu t k t h p
Frequent itemsets/subsequences/substructures
Itemset/subsequence/substructure X là frequent n u ế
support(X) >= min_sup.
ậ Itemsets: t p các items
Subsequences: chu i tu n t
ầ ự ỗ các events/items
Substructures: các ti u c u trúc (graph, lattice, tree, sequence,
ể ấ
24
set, …)
ậ ế ợ
ễ
ể
6.2. Bi u di n lu t k t h p
Closed frequent itemsets
ế
ồ ạ ậ
M t itemset X closed trong
i t p cha
th c s Y nào trong
ộ ự X (cid:0)
ự J, X closed iff (cid:0)
J n u không t n t J có cùng support v i X.ớ Y (cid:0)
ế
X là closed frequent itemset trong J n u X là frequent
itemset và closed trong J.
Maximal frequent itemsets
ộ
M t itemset X là maximal frequent itemset trong
J n u ế
ự
ự
i t p cha th c s Y nào trong
J là m t ộ
ồ ạ ậ không t n t frequent itemset.
X (cid:0)
J và X (cid:0) Y: support(Y) <> support (X).
J, X là maximal frequent itemset iff (cid:0) Y (cid:0) J và X (cid:0) Y: Y
25
ả ộ không ph i là m t frequent itemset.
ậ ế ợ
ễ
ể
6.2. Bi u di n lu t k t h p
Constrained frequent itemsets
ộ
ườ
Frequent itemsets th a các ràng bu c do ng ỏ
i dùng
ị
đ nh nghĩa.
Approximate frequent itemsets
ấ
ỉ
Frequent itemsets d n ra support (x p x ) cho các
ẫ ẽ ượ frequent itemsets s đ
c khai phá.
Topk frequent itemsets
ầ ử ớ
ề
ấ
Frequent itemsets có nhi u nh t k ph n t
v i k do
ườ
ị
ỉ
ng
i dùng ch đ nh.
26
ậ ế ợ
ễ
ể
6.2. Bi u di n lu t k t h p
ữ
ứ
ề
ơ
Lu t k t h p lu n lý, đ n m c, đ n chi u gi a các
ậ ế ợ ầ ử
ơ ph bi n: A
ậ ổ ế B [support, confidence]
ậ t p ph n t
A và B là các frequent itemsets
singledimensional
singlelevel
Boolean
Support(AB) = Support(A U B) >= min_sup
Confidence(AB) = Support(A U B)/Support(A) = P(B|A)
>= min_conf
27
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ẫ
ườ
Gi
ng
i thu t Apriori: khám phá các m u th ể
ậ ớ ậ
ự
xuyên v i t p d tuy n
R. Agrawal, R. Srikant. Fast algorithms for mining association rules. In VLDB 1994, pp. 487499.
ẫ
ườ
ả
i thu t FPGrowth: khám phá các m u th
ng
Gi
ậ ớ xuyên v i FPtree
J. Han, J. Pei, Y. Yin. Mining frequent patterns without
candidate generation. In MOD 2000, pp. 112.
28
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t Apriori
ề ặ
ủ
ể
Dùng tri th c bi
c (prior knowledge) v đ c đi m c a
ế ướ ứ t tr các frequent itemsets
ế
ớ
Ti p c n l p v i quá trình tìm ki m các frequent itemsets
ở
ậ ặ ứ
ộ
ế ừ t ng m c m t (levelwise search)
k+1itemsets đ
ượ ạ ừ c t o ra t kitemsets.
ể ả
ế
Apriori property đ gi m không gian tìm ki m: All nonempty
subsets of a frequent itemset must also be frequent.
Ở ỗ ộ ữ ệ ứ ế ề ượ ể m i m c tìm ki m, toàn b d li u đ u đ c ki m tra.
Ch ng minh???
Antimonotone: if a set cannot pass a test, all of its supersets will fail
ứ
29
the same test as well.
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
Gi
30
ả ậ i thu t Apriori
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t Apriori
31
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ủ
ẫ
D li u m u c a AllElectronics (sau quá trình
ữ ệ ử ề
ti n x lý)
32
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
min_sup = 2/9
minimum support count = 2
33
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t Apriori
ể
ặ
Đ c đi m
ề
ơ
104 frequent 1itemsets nhi u h n 10
7 ( 10≈ 4(1041)/2) 2itemsets
ự
ể
d tuy n
ầ
ộ
ự
ể
ướ
M t kitemset c n ít nh t 2
ấ k 1 itemsets d tuy n tr
c đó.
ự ể ạ ề ậ T o ra nhi u t p d tuy n
Ki m tra t p d li u nhi u l n
ướ
ầ
Chi phí l n khi kích th ớ
c các itemsets tăng lên d n.
ế
ượ
ữ ệ
ể
ầ
ậ
ầ
N u kitemsets đ
c khám phá thì c n ki m tra t p d li u k+1 l n.
34
ề ầ ữ ệ ể ậ
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
Gi
ậ i thu t Apriori Các c i ti n c a gi ả ế
ủ ả ậ
ậ ự
K thu t d a trên b ng băm (hashbased technique)
ỏ ơ
ộ
ứ
ỹ M t kitemset ng v i hashing bucket count nh h n minimum support
ớ ộ threshold không là m t frequent itemset.
ị
Gi m giao d ch (transaction reduction)
ầ
ứ
ị
ượ
ể
ả M t giao d ch không ch a frequent kitemset nào thì không c n đ
c ki m tra
ầ
ở
ộ các l n sau (cho k+1itemset).
ạ
Phân ho ch (partitioning)
ạ
ả
ấ
ộ
ộ
ớ
M t itemset ph i frequent trong ít nh t m t phân ho ch thì m i có th ể
ữ ệ
ộ ậ
frequent trong toàn b t p d li u.
ẫ
L y m u (sampling)
ữ ệ
ỏ ơ
ộ ị
ớ
c v i m t tr support threshold nh h n
ấ Khai phá ch t p con d li u cho tr ươ
ể
ầ
ộ
ướ ị
ệ
ỉ ậ và c n m t ph
ng pháp đ xác đ nh tính toàn di n (completeness).
ộ
Đ m itemset đ ng (dynamic itemset counting)
ấ ả
ự
ể
ỉ
ủ
ậ
ượ
ế Ch thêm các itemsets d tuy n khi t
t c các t p con c a chúng đ
ự c d
đoán là frequent.
35
i thu t Apriori ả
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t FPGrowth ấ ữ ệ
ậ
Nén t p d li u vào c u trúc cây (Frequent Pattern tree,
FPtree)
ị ạ ỏ ớ
ậ
ả ữ ệ Gi m chi phí cho toàn t p d li u dùng trong quá trình khai phá Infrequent items b lo i b s m.
Đ m b o k t qu khai phá không b nh h
ươ
ể ị
Ph
ng pháp chiađ tr (divideandconquer)
Quá trình khai phá đ
ị ả ế ả ả ả ưở ng
ớ
ỏ c chia thành các công tác nh .
ự
ể
ậ
ạ
Tránh t o ra các t p d tuy n
ượ 1. Xây d ng FPtree ự 2. Khám phá frequent itemsets v i FPtree
M i l n ki m tra m t ph n t p d li u
36
ầ ậ ữ ệ ỗ ầ ể ộ
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t FPGrowth
1. Xây d ng FPtree ự
1.1. Ki m tra t p d li u, tìm frequent 1itemsets
ữ ệ ể ậ
ứ ự ự ả ủ ầ ắ 1.2. S p th t frequent 1itemsets theo s gi m d n c a support
ệ ầ ấ ố count (frequency, t n s xu t hi n)
1.3. Ki m tra t p d li u, t o FPtree
ạ
ượ
c gán nhãn “null” {}
ươ
ứ
ỗ
ị
ủ
ộ
ng ng m t nhánh c a FPtree.
ỗ
ộ
ươ
ủ
ứ
ộ
ị
T o root c a FPtree, đ ủ M i giao d ch t M i node trên m t nhánh t
ng ng m t item c a giao d ch.
ủ
ộ
ị
ượ
ắ
ả
ầ
Các item c a m t giao d ch đ
c s p theo gi m d n.
ế ợ
ủ
ớ
ỗ
ươ
M i node k t h p v i support count c a item t
ứ ng ng.
ị
Các giao d ch có chung items t o thành các nhánh có prefix chung. ạ
37
ữ ệ ể ậ ạ
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
Gi
38
ả ậ i thu t FPGrowth
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
39
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t FPGrowth
ớ
2. Khám phá frequent itemsets v i FPtree
2.1. T o conditional pattern base cho m i node c a FPtree
ủ
ỹ
Tích lu các prefix paths with frequency c a node đó
ủ ạ ỗ
2.2. T o conditional FPtree t
ỗ
ỗ
ủ
ự
Tích lũy frequency cho m i item trong m i base Xây d ng conditional FPtree cho frequent items c a base đó
ạ ừ ỗ m i conditional pattern base
2.3. Khám phá conditional FPtree và phát tri n frequent itemsets
ể
ế
ộ
ơ
ệ
ấ ả
N u conditional FPtree có m t path đ n thì li
t kê t
t c các
itemsets.
40
ệ ộ m t cách đ qui
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t FPGrowth
41
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
42
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ả
ậ
Gi
i thu t FPGrowth
ể
ặ
Đ c đi m
Không t o t p itemsets d tuy n
ự
ự
ể
ệ
ể
Không ki m tra xem li u itemsets d tuy n có th c là frequent
itemsets
ạ ậ ự ể
S d ng c u trúc d li u nén d li u t
ữ ệ ừ ậ ử ụ ữ ệ ữ ệ ấ t p d li u
ữ ệ ả ậ ể Gi m chi phí ki m tra t p d li u
Chi phí ch y u là đ m và xây d ng cây FPtree lúc đ u
ủ ế ự ế ầ
ệ ố ệ t cho vi c khám phá các frequent
43
ẫ ắ Hi u qu và co giãn t ả itemsets dài l n ng n
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ữ
ả
ậ
ả
ậ
So sánh gi a gi
i thu t Apriori và gi
i thu t FPGrowth
ớ
Co giãn v i support threshold
44
ẫ
ườ
6.3. Khám phá các m u th
ng xuyên
ữ
ả
ậ
ả
ậ
So sánh gi a gi
i thu t Apriori và gi
i thu t FPGrowth
ớ ố
ế
ị
Co giãn tuy n tính v i s giao d ch
45
ậ ế ợ ừ
ẫ
các m u
ườ
6.4. Khám phá các lu t k t h p t th
ng xuyên
Strong association rules AB
Support(AB) = Support(A U B) >= min_sup
Confidence(AB) = Support(A U B)/Support(A) = P(B|
A) >= min_conf
Support(AB) = Support_count(A U B) >= min_sup
Confidence(AB) = P(B|A) =
Support_count(AUB)/Support_count(A) >= min_conf
46
ậ ế ợ ừ
ẫ
các m u
ườ
6.4. Khám phá các lu t k t h p t th
ng xuyên
ừ ậ
Quá trình t o các strong association rules t
t p
ạ các frequent itemsets
ỗ
ạ
ậ
ỗ
Cho m i frequent itemset
l, t o các t p con không r ng
c a ủ l.
Support_count(l) >= min_sup
ỗ ậ
ỗ
Cho m i t p con không r ng
ế
s)” n u Support_count(
ậ s (l ạ s c a ủ l, t o ra lu t “ l)/Support_count(s) >= min_conf
47
ậ ế ợ ừ
ẫ
các m u
ườ
6.4. Khám phá các lu t k t h p t th
ng xuyên
I5
Min_conf = 50%
I2
I1 (cid:0) I2 (cid:0) I1 (cid:0) I5 (cid:0) I2 (cid:0) I5 (cid:0) I5 (cid:0)
I1 I1 (cid:0) I2
48
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ộ
Ràng bu c (constraints)
ậ
ẫ
ẫ
H ng d n quá trình khai phá m u (patterns) và lu t
ướ (rules)
ữ ệ
ế
i h n không gian tìm ki m d li u trong quá trình
Gi
ớ ạ khai phá
ạ
Các d ng ràng bu c ộ
Ràng bu c ki u tri th c (knowledge type constraints)
ứ ể ộ
Ràng bu c d li u (data constraints)
ữ ệ ộ
Ràng bu c m c/chi u (level/dimension constraints)
ứ ề ộ
Ràng bu c liên quan đ n đ đo (interestingness constraints)
ế ộ ộ
49
ậ ộ ế Ràng bu c liên quan đ n lu t (rule constraints)
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ứ
ể
ộ
Ràng bu c ki u tri th c (knowledge type constraints)
Lu t k t h p/t
ữ ệ
ộ
Ràng bu c d li u (data constraints)
Taskrelevant data (association rule mining)
ứ
ề
ộ
Ràng bu c m c/chi u (level/dimension constraints)
ậ ế ợ ươ ng quan
Chi u (thu c tính) d li u hay m c tr u t
ế
ộ
Ràng bu c liên quan đ n đ đo (interestingness constraints) ộ
ữ ệ ừ ượ ứ ề ộ ệ ng/ý ni m
Ng
ậ
ộ
Ràng bu c liên quan đ n lu t (rule constraints) ế
ưỡ ủ ộ ng c a các đ đo (thresholds)
D ng lu t s đ
50
ậ ẽ ượ ạ c khám phá
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
Khám phá lu t d a trên ràng bu c ộ ậ ự
ữ ệ ố ơ
ả ơ
Quá trình khai phá d li u t
ệ t h n và hi u qu h n
(more effective and efficient).
ự ủ ầ ộ c khám phá d a trên các yêu c u (ràng bu c) c a
Lu t đ ng
More effective
ậ ượ ườ ử ụ i s d ng.
B t
ể ượ ể i u hóa (optimizer) có th đ c dùng đ khai thác các
More efficient
51
ủ ườ ử ụ ộ ố ư ộ ràng bu c c a ng i s d ng.
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ậ ự
ế
ộ
Khám phá lu t d a trên ràng bu c liên quan đ n
ậ
lu t (rule constraints)
ạ
ậ
D ng lu t (metarule guided mining)
Metarules: ch đ nh d ng lu t (v cú pháp – syntactic) mong
ề ậ ỉ
ộ
N i dung lu t (rule content) ậ
ượ ố mu n đ ạ ị c khám phá
Ràng bu c gi a các bi n trong A và/ho c B trong lu t A
ệ ậ
ợ
Quan h t p h p cha/con
ị
Mi n trề
ế ợ
Các hàm k t h p (aggregate functions)
52
ữ ế ặ ộ ậ B
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
Metarules
ề
ậ
ố
ị
Ch đ nh d ng lu t (v cú pháp – syntactic) mong mu n
ỉ ượ
ạ c khám phá
đ
ủ
ự
ự
ệ
ợ
D a trên kinh nghi m, mong đ i và tr c giác c a nhà
ữ ệ
phân tích d li u
ạ
ả
ố
T o nên gi
ệ thuy t (hypothesis) v các m i quan h
ườ
ậ
ề ế (relationships) trong các lu t mà ng
i dùng quan tâm
ế
Quá trình khám phá lu t k t h p + quá trình tìm ki m
ậ
ớ
lu t trùng v i metarules cho tr
ậ ế ợ ướ c
53
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
Metarules
ẫ
ậ
M u lu t (rule template): P
1 (cid:0) P2 (cid:0) … (cid:0) Pl (cid:0) ị ừ ụ ể
Q1 (cid:0) Q2 (cid:0) … (cid:0) Qr c th (instantiated predicates)
P1, P2, …, Pl, Q1, Q2, …, Qr: v t
ị ừ ế hay bi n v t (predicate variables)
Th
ụ ủ
Ví d c a metarules
Metarule
ườ ề ế ề ộ ng liên quan đ n nhi u chi u/thu c tính
buys(X, “office software”) P1(X, Y) (cid:0) P2(X, W) (cid:0)
ậ
ỏ Lu t th a metarule age(X, “30..39”) (cid:0) income(X, “41k..60k”) (cid:0) buys(X,
54
“office software”)
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ữ
ộ
Ràng bu c gi a các bi n S1, S2, … trong A
ặ
ế ậ B và/ho c B trong lu t A
ệ ậ
Quan h t p h p cha/con: S1 ợ
/(cid:0)
S2
Mi n trề
(cid:0)
{=, <>, <, <=, >, >=}
/(cid:0)
ị S1 (cid:0) value, (cid:0) (cid:0) value (cid:0) S1 ValueSet (cid:0) S1 ho c S1
ế ợ
Các hàm k t h p (aggregate functions)
Agg(S1) (cid:0) value, Agg() (cid:0)
ặ (cid:0) ValueSet, (cid:0) (cid:0) {=, <>, (cid:0) , (cid:0) , (cid:0) }
{min, max, sum, count, avg}, (cid:0) (cid:0) {=,
55
<>, <, <=, >, >=}
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ấ ủ
Tính ch t c a các ràng bu c ộ
Antimonotone
Monotone
Succinctness
Convertible
56
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ấ ủ
Tính ch t c a các ràng bu c ộ
Antimonotone
“A constraint Ca is antimonotone
antimonotone iff. for any pattern S not
satisfying Ca, none of the superpatterns of S can satisfy Ca”.
Ví d : sum(S.Price) <= value
Monotone
“A constraint Cm is monotone
ụ
monotone iff. for any pattern S satisfying Cm,
every superpattern of S also satisfies it”.
Ví d : sum(S.Price) >= value
57
ụ
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ấ ủ
Tính ch t c a các ràng bu c ộ
Succinctness
“A subset of item Is is a succinct set
succinct set, if it can be expressed as
p(I) for some selection predicate p, where (cid:0) operator”.
(cid:0) is a selection
“SP(cid:0) 2I is a succinct power set
power set, if there is a fixed number of
(cid:0) I, s.t. SP can be expressed in terms of the
“A constraint Cs is succinct
succinct set I1, …, Ik strict power sets of I1, …, Ik using union and minus”.
succinct provided SATCs(I) is a succinct
power set”.
ể ạ ườ ậ ỏ ng minh và chính xác các t p th a succinct
Có th t o t constraints.
Ví d : min(S.Price) <= value
58
ụ
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ấ ủ
Tính ch t c a các ràng bu c ộ
Convertible
Các ràng bu c không có các tính ch t antimonotone,
ấ
ộ monotone, và succinctness
ế ặ ặ
Ví d : ụ
ầ ử ắ
ứ ự
ế
ầ
N u các ph n t
s p theo th t
tăng d n thì avg(I.price) <= 100
ộ
là m t convertible antimonotone constraint.
ầ ử ắ
ế
ứ ự ả
ầ
N u các ph n t
s p theo th t
gi m d n thì avg(I.price) <= 100
ộ
là m t convertible monotone constraint.
59
ầ ử ứ ự ể ộ Các ràng bu c ho c là antimonotone ho c là monotone n u trong itemset đang ki m tra có th t các ph n t .
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
60
ậ ế ợ
ự
6.5. Khám phá các lu t k t h p d a trên ràng bu cộ
ầ ử
ậ
ậ
Khám phá lu t (rules)/t p ph n t
ỏ
ổ ế ph bi n ộ (frequent itemsets) th a các ràng bu c
ự
ế
ế
ậ
Cách ti p c n tr c ti p
Áp d ng các gi
ụ ả ề ậ ố i thu t truy n th ng
ả ề ế
ế
ả
ỏ
ộ
N u th a ràng bu c thì tr v k t qu sau cùng.
ấ ủ
ự
ế
ậ
Cách ti p c n d a trên tính ch t c a các ràng bu c ộ
ả ạ ượ ừ ế ể ộ Ki m tra các ràng bu c cho t ng k t qu đ t đ c
ấ ủ ệ ộ Phân tích toàn di n các tính ch t c a các ràng bu c
Ki m tra các ràng bu c càng s m càng t
ể ớ ộ ố t trong quá trình khám
ượ
ẹ
ớ
Không gian d li u đ
c thu h p càng s m càng t
ữ ệ
ố t. 61
phá rules/frequent itemsets
ươ
6.6. Phân tích t
ng quan
B
Strong association rules A (cid:0) ủ ầ
ự
ệ
ố
D a trên t n s xu t hi n c a A và B ( ấ
min_sup)
ố ớ
ự
ủ
ề
ệ
ấ
D a trên xác su t có đi u ki n c a B đ i v i A
(min_conf)
ự
ự
ủ
support và confidence d a vào s ch quan
Các đ đo ộ ườ ử ụ ủ c a ng
i s d ng
L
ố
ị
Trong s 10,000 giao d ch, 6,000 giao d ch cho ị
ượ ấ ớ ể ượ ậ ế ợ ng r t l n lu t k t h p có th đ ả ề c tr v .
computer games, 7,500 cho videos, và 4,000 cho c ả computer games và videos Buys(X, “computer games”) (cid:0) 40%, confidence = 66%]
62
Buys (X, “videos”) [support =
ươ
6.6. Phân tích t
ng quan
ươ
ậ ế ợ
Phân tích t
ng quan cho lu t k t h p A
B
ự ươ
ộ ẫ
ụ
ữ
Ki m tra s t
ng quan và ph thu c l n nhau gi a A
ể và B
ề ữ ệ
ự
ố
D a vào th ng kê v d li u
ụ
ộ
ộ
Các đ đo khách quan, không ph thu c vào ng
ườ ử i s
d ngụ
ố
ị
Trong s 10,000 giao d ch, 6,000 giao d ch cho ị
(cid:0)
computer games, 7,500 cho videos, và 4,000 cho c ả computer games và videos Buys(X, “computer games”) (cid:0) 40%, confidence = 66%]
Buys (X, “videos”) [support =
P(“videos”) = 75% > 66%: “computer games” và “videos” t
ươ ng
ớ
63
ị quan ngh ch v i nhau.
ươ
6.6. Phân tích t
ng quan
ậ ươ
Lu t t
ng quan (correlation rules): A
B [support,
confidence, correlation]
(cid:0)
correlation: đ đo đo s t
ộ
Các đ đo correlation:
lift, (cid:0) 2 (Chisquare), all_confidence, cosine
ể
ộ ậ
ự
ự
ệ
ả
ấ
ấ
ự ộ ậ
ự
ữ
ợ
ị
lift: ki m tra s xu t hi n đ c l p gi a A và B d a trên xác su t (kh năng) ữ (cid:0) 2 (Chisquare): ki m tra s đ c l p gi a A và B d a trên giá tr mong đ i và
ị
giá tr quan sát đ
ể ượ c
ậ ự
ự
ể
ị
all_confidence: ki m tra lu t d a trên tr support c c đ i ạ
ạ ỏ ự
ụ
ệ
ổ
ố
ị
cosine: gi ng ố
ộ lift tuy nhiên lo i b s ph thu c vào t ng s giao d ch hi n có
ụ
ộ
ố
all_confidence và cosine t
t cho t p d li u l n, không ph thu c các giao
ữ ệ ớ ể
ứ
ấ
ị
ậ d ch mà không ch a b t kì itemsets đang ki m tra (nulltransactions).
ộ
all_confidence và consine là các đ đo nullinvariant.
64
ự ươ ộ ữ ng quan gi a A và B.
ươ
6.6. Phân tích t
ng quan
ươ
lift
Đ đo t ộ
ng quan
lift(A, B) < 1: A t
ươ ớ ị ng quan ngh ch v i B
lift(A, B) > 1: A t
ươ ậ ớ ng quan thu n v i B
lift(A, B) = 1: A và B đ c l p nhau, không có t
ộ ậ ươ ng quan
lift
BPABP
A
B
supp
(
BA ,
)
/)
(
(
|
)
confidence (
/)
Bort (
)
BAP ( ) BPAP ( ) ) (
ươ
ị
lift({game}=>{video}) = 0.89 < 1 {game} và {video} t
ng quan ngh ch.
65
(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
6.7. Tóm t
tắ
Khai phá luật kết hợp
Được xem như là một trong những đóng góp quan trọng nhất từ cộng
ậ
ậ ế ợ ượ
Các d ng lu t: lu t k t h p lu n lý/lu t k t h p l
ố ậ ế ợ
ề
ậ ế ợ ề ơ ậ ế ợ
ậ ế ợ
ậ ươ
ứ
ng quan
ậ ạ ng s , ậ ế ợ ậ ế ợ lu t k t h p đ n chi u/lu t k t h p đa chi u, lu t k t h p ứ ơ đ n m c/lu t k t h p đa m c, lu t k t h p/lu t t ố th ng kê
ầ ử
ẫ
Các d ng ph n t ạ
(item)/m u (pattern): Frequent
itemsets/subsequences/substructures, Closed frequent itemsets, Maximal frequent itemsets, Constrained frequent itemsets, Approximate frequent itemsets, Topk frequent itemsets
ả
ậ
Khám phá các frequent itemsets: giải thuật Apriori và gi
i thu t
66
FPGrowth dùng FPtree
đồng cơ sở dữ liệu trong việc khám phá tri thức
ỏ
ỏH i & Đáp … H i & Đáp …
67
