December 27, 2012 1
Chương 4:
Khai phá luật kết hợp
Dựa theo “Data Mining: Concepts and Techniques”
Chapter 6. Mining Association Rules in Large Databases
©Jiawei Han and Micheline Kamber
www.cs.uiuc.edu/~hanj
December 27, 2012 2
Chương 4: Khai phá luật kết hợp
Khai phá luật kết hợp (Association rule)
Các thuật toán khai phá vô hướng luật kết hợp (giá trị
lôgic đơn chiều) trong CSDL giao dịch
Khai phá kiểu đa dạng luật kết hợp/tương quan
Khai phá kết hợp dựa theo ràng buộc
Khai phá mẫu dãy
Ứng dụng/mở rộng khai phá mẫu phổ biến
December 27, 2012 3
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
M t s ví d v ộ ố ụ ề “lu t k t h p” (associate rule)ậ ế ợ
•“98% khách hàng mà mua t p chí th thaoạ ể thì đ u ềmua
các t p chí v ôtôạ ề ”
s ựk t h pế ợ gi a ữ“t p chí th thaoạ ể ”
v i ớ“t p chí v ôtôạ ề ”
•“60% khách hàng mà mua bia t i siêu thạ ị thì đ u ềmua b m ỉ
tr em” ẻ
s ựk t h pế ợ gi a ữ“bia” v i ớ“b m tr emỉ ẻ ”
•“Có t i 70% ng i truy nh p Web vào đ a ch Url 1 thì ớ ườ ậ ị ỉ
cũng vào đ a ch Url 2 trong m t phiên truy nh p web” ị ỉ ộ ậ
s ựk t h pế ợ gi a ữ“Url 1” v i ớ“Url 2”. Khai phá d li u s ữ ệ ử
d ng Web (D li u t file log c a các site, ch ng h n ụ ữ ệ ừ ủ ẳ ạ
đ c MS cung c p). ượ ấ
•Các Url có g n v i nhãn “l p” là các đ c tr ng thì có lu t ắ ớ ớ ặ ư ậ
k t h p liên quan gi a các l p Url này.ế ợ ữ ớ
December 27, 2012 4
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
[IV06] Renáta Iváncsy, István Vajk (2006). Frequent Pattern Mining in Web Log Data,
Acta Polytechnica Hungarica, 3(1):77-90, 2006
December 27, 2012 5
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
C s d li u giao d ch (transaction database)ơ ở ữ ệ ị
•Giao d chị: danh sách các m t hàng (m c: item) trong m t phi u mua hàng ặ ụ ộ ế
c a khách hàng. Giao d ch T là m t t p m c.ủ ị ộ ậ ụ
•T p toàn b các m c I = {iậ ộ ụ 1, i2, …, ik} “t t c các m t hàng”. M t giao d ch ấ ả ặ ộ ị
T là m t t p con c a I: T ộ ậ ủ ⊆ I. M i giao d ch T có m t đ nh danh là Tỗ ị ộ ị ID.
• A là m t t p m c A ộ ậ ụ ⊆ I và T là m t giao d ch: G i T ch a A n u A ộ ị ọ ứ ế ⊆ T.
•Lu t k t h pậ ế ợ
•G i A ọ→ B là m t “lu t k t h p” n u A ộ ậ ế ợ ế ⊆ I, B ⊆ I và A∩B=∅.
•Lu t k t h p A ậ ế ợ → B có đ h tr (support) ộ ỗ ợ s trong CSDL giao d ch D n u ị ế
trong D có s% các giao d ch T ch a AB: chính là xác su t P(AB). T p m c ị ứ ấ ậ ụ
A có P(A) ≥ s>0 (v i s cho tr c) đ c g i là ớ ướ ượ ọ t p ph bi n (frequent set)ậ ổ ế .
Lu t k t h p A ậ ế ợ → B có đ tin c y (confidence) ộ ậ c trong CSDL D n u nh ế ư
trong D có c% các giao d ch T ch a A thì cũng ch a B: chính là xác su t ị ứ ứ ấ
P(B|A).
•Support (A → B) = P(A∪B) : 1 ≥ s (A → B) ≥ 0
•Confidence (A → B) = P(B|A) : 1 ≥ c (A → B) ≥ 0
•Lu t A ậ→ B đ c g i là đ m b o đ h tr s trong D n u s(A ượ ọ ả ả ộ ỗ ợ ế → B) ≥ s.
Lu t Aậ→B đ c g i là đ m b o đ tin c y c trong D n u c(A ượ ọ ả ả ộ ậ ế → B) ≥ c.