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 1
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 2
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
ộ ố
ụ ề “lu t k t h p” (associate rule)
ể
ậ ế ợ ạ
ạ
ề
” s ự k t h p
thì đ u ề mua ” ể
ế ợ gi a ữ “t p chí th thao ạ
”
ạ
i siêu th
ỉ
”
ạ ế ợ gi a ữ “bia” v i ớ “b m tr em
ị thì đ u ề mua b m ỉ
ẻ
ườ
ậ
ị
ỉ
ẻ s ự k t h p i 70% ng ỉ
ậ
i truy nh p Web vào đ a ch Url 1 thì ộ ế ợ gi a ữ “Url 1” v i ớ “Url 2”. Khai phá d li u s ữ ệ ử file log c a các site, ch ng h n ạ ẳ
ữ ệ ừ
ủ
ấ
c MS cung c p). ắ
ư
ặ
M t s ví d v •“98% khách hàng mà mua t p chí th thao các t p chí v ôtô v i ớ “t p chí v ôtô ề •“60% khách hàng mà mua bia t tr em” •“Có t ớ cũng vào đ a ch Url 2 trong m t phiên truy nh p web” ị s ự k t h p d ng Web (D li u t ụ đ ượ •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 3
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
Renáta Iváncsy, István Vajk (2006). Frequent Pattern Mining in Web Log Data,
[IV06] Acta Polytechnica Hungarica, 3(1):7790, 2006
December 27, 2012 4
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 c các m t hàng”. M t giao d ch ấ ả ậ ị
ặ ộ ị
ụ ủ
ID.
˝
•
1, i2, …, ik} “t I. M i giao d ch T có m t đ nh danh là T ỗ I và T là m t giao d ch: G i T ch a A n u A
T.
ứ
ế
ộ
ọ
ị
ụ
˝ ˝
B là m t “lu t k t h p” n u A
I, B ˝
ậ ế ợ
ế
I và A˙ B=˘
.
fi ˝
B có đ h tr (support)
• T p toàn b các m c I = {i ộ T là m t t p con c a I: T ộ ậ A là m t t p m c A ộ ậ • Lu t k t h p ậ ế ợ • G i A ọ ộ • Lu t k t h p A ậ ế ợ
ị
ị
ậ
ướ
c g i là ọ
ấ ổ ế
fi
ộ
ế
ứ
ị
= P(A¨ B)
B)
B) ‡ B) ‡
0 0
fi
ượ
ả
ọ
fi fi
s (A fi : 1 ‡ : 1 ‡ c (A fi B) = P(B|A) c g i là đ m b o đ h tr s trong D n u s(A ộ ỗ ợ ả c g i là đ m b o đ tin c y c trong D n u c(A
B) ‡ B) ‡
s. c.
ế ế
ượ
ả
ả
ậ
ộ
ọ
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) ‡ . t p ph bi n (frequent set) s>0 (v i s cho tr c) đ ậ ượ ớ B có đ tin c y (confidence) Lu t k t h p A 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 fi • Confidence (A fi • Lu t A B đ ậ fi B đ December 27, 2012 Lu t Aậ T p m nh. ạ
ậ
5 fi
Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp
ị
1, …, ik}. CSDL giao d ch
ụ ậ D = {d ˝
T p m c I={i
Transactionid
Items bought
: A B là lu t k t h p
ậ ế ợ
10
A, B, C
I} I, A˙ B=˘ A, B ˝ Bài toán tìm lu t k t h p.
20
A, C
ể
30
A, D
ọ
XY.
ậ ế ợ Cho tr ộ ỗ ợ ố ướ tin c y t ế ậ ố k t h p m nh ế ợ
i thi u s>0, đ c đ h tr t ộ i thi u c>0. Hãy tìm m i lu t ậ ạ
40
B, E, F
s min_support = 50%,
ả ử
Customer buys both
Gi min_conf = 50%:
Customer buys diaper
A C (50%, 66.7%) C A (50%, 100%)
ậ
ậ ế ợ
ề ệ
ệ
ớ
ộ
Hãy trình bày các nh n xét v khái ni m lu t k t h p v i khái ni m ph ụ thu c hàm.
Customer buys beer
đây.
ở
Các tính ch t Armstrong ấ
December 27, 2012 6
Một ví dụ tìm luật kết hợp
Transactionid
Items bought
Min. support 50% Min. confidence 50%
10
A, B, C
20
A, C
Frequent pattern
Support
30
A, D
{A}
75%
40
B, E, F
{B}
50%
{C}
50%
For rule A (cid:222)
50%
{A, C} {C}) = 50%
C: support = support({A}¨ confidence = support({A}¨
{C})/support({A}) =
66.6%
December 27, 2012 7
Khai niệm khai phá kết hợp
December 27, 2012 8
Khái niệm khai phá luật kết hợp
Khai phá luệt kết hợp:
Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu trú nhanquả trong tập các mục hoặc đối tượng trong CSDL quan hệ hoặc các kho chứa thông tin khác.
Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy mục…) mà xuất hiện phổ biến trong 1 CSDL [AIS93] Động lực: tìm mẫu chính quy (regularities pattern) trong DL Các mặt hàng nào được mua cùng nhau? — Bia và bỉm
(diapers)?!
Mặt hàng nào sẽ được mua sau khi mua một PC ? Kiểu DNA nào nhạy cảm với thuộc mới này? Có khả năng tự động phân lớp Web hay không ?
December 27, 2012 9
Mẫu phổ biến và khai phá luật kết hợp là một bài toán bản chất của khai phá DL
Nền tảng của nhiều bài toán KPDL bản chất
Kết hợp, tương quan, nhân quả
Mẫu tuần tự, kết hợp thời gian hoặc vòng, chu kỳ bộ
phận, kết hợp không gian và đa phương tiện
Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích tụ
(nén dữ liệu ngữ nghĩa)
Ứng dụng rộng rãi
Phân tích DL bóng rổ, tiếp thị chéo (crossmarketing),
thiết kế catalog, phân tích chiến dịch bán hàng Phân tích Web log (click stream), Phân tích chuỗi DNA v.v.
December 27, 2012 10
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 11
Apriori: Một tiếp cận sinh ứng viên và kiểm tra
Khái quát: Khai phá luật kết hợp gồm hài bước: Tìm mọi tập mục phổ biến: theo minsup Sinh luật mạnh từ tập mục phổ biến
Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi
giao dịch chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}. Nguyên lý tỉa Apriori: Với mọi tập mục không phổ biến thì mọi tập bao
không cần phải sinh ra/kiểm tra!
Mọi tập con của tập mục phổ biến cũng là tập mục phổ biến
Sinh các tập mục ứng viên dài (k+1) từ các tập mục phổ biến có độ
dài k (Độ dài tập mục là số phần tử của nó),
Kiểm tra các tập ứng viên theo CSDL
Phương pháp:
của thuật toán
Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng
Agrawal & Srikant 1994, Mannila, và cộng sự 1994
December 27, 2012 12
Thuật toán Apriori
ấ
ậ
Trên c s tính ch t (nguyên lý t a) Apriori, thu t ắ
• T các t p F
toán ho t đ ng theo quy t c quy ho ch đ ng i = {ci| ci t p ph bi n, |c
ỉ ộ ạ ổ ế ộ
ậ ổ ế
ụ
ơ ở ạ ộ i| = i} ừ g m m i t p m c ph bi n có đ dài i v i ớ ồ 1 £
ậ ọ ậ k,
ổ ế
ọ ậ
ụ
ồ
k+1 g m m i t p m c ph bi n có
ộ
ụ 1, i2, … in (n = |I|) ng
c đ nh
(th
ộ
ứ ự ố ị
ườ
i £ • đi tìm t p Fậ đ dài k+1. ậ ế
ắ
đ đ
Trong thu t toán, các tên m c i c s p x p theo m t th t ượ c đánh ch s 1, 2, ..., n). ỉ ố ượ
December 27, 2012 13
Thuật toán Apriori
December 27, 2012 14
Thuật toán Apriori: Thủ tục con Apriorigen
.
ề
ả duy t CSDL D
ệ
ỗ ướ
c k, thu t toán Apriori đ u ph i ệ
ậ ể
ượ
1.
c F ể
c k sau đó, duy t D đ tính s l ệ ủ
ị ộ ầ
ả ừ ọ ứ
ỉ
ị
ỗ
ng giao d ch t tho t ng ố ượ k+1: m i giao d ch t ch xem xét m t l n cho m i ng
Trong m i b Kh i đ ng, duy t D đ có đ ở ộ Các b ướ ng viên c c a C k+1. Th t c con
ứ viên c thu c Cộ ủ ụ
Apriorigen sinh tập phổ biến: tư tưởng
December 27, 2012 15
Thủ tục con Apriorigen
December 27, 2012 16
Một ví dụ thuật toán Apriori (s=0.5)
Itemset
sup
Itemset
sup
Database TDB
{A}
2
L1
{A}
2
C1
Tid
Items
{B}
3
{B}
3
10
A, C, D
{C}
3
{C}
3
1st scan
20
B, C, E
{D}
1
{E}
3
30
A, B, C, E
{E}
3
40
B, E
C2
C2
Itemset
2nd scan
L2
{A, B}
{A, C}
{A, E}
{B, C}
Itemset {A, C} {B, C} {B, E} {C, E}
sup 2 2 3 2
{B, E}
Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E}
sup 1 2 1 2 3 2
{C, E}
Itemset
L3
C3
3rd scan
{B, C, E}
Itemset {B, C, E}
sup 2
December 27, 2012 17
Chi tiết quan trọng của Apriori
Bước 1: Tự kết nối Lk
Step 2: Cắt tỉa
Cách thức sinh các ứng viên:
Cách thức đếm hỗ trợ cho mỗi ứng viên.
L3={abc, abd, acd, ace, bcd}
Tự kết nối: L3*L3 abcd từ abc
và abd
acde từ acd và ace
Tỉa:
acde là bỏ đi vì ade không thuộc L3
C4={abcd}
Ví dụ thủ tục con sinh ứng viên
December 27, 2012 18
)
Ví dụ: D, min_sup*|D| = 2 (C4 = ˘
December 27, 2012 19
Sinh luật kết hợp
Việc sinh luật kết hợp gồm hai bước
con thực sự X khác rỗng của nó.
Với mỗi tập phổ biến W tìm được hãy sinh ra mọi tập
(W – X) nếu P(WX|X) ‡
sự của nó: sinh luật X fi
Như ví dụ đã nêu có L3 = {{I1, I2, I3}, {I1, I2, I5}}
Với độ tin cậy tối thiểu 70%, xét tập mục phổ biến {I1, I2,
I5} có 3 luật như dưới đây:
Với mỗi tập phố biến W và tập con X khác rỗng thực c.
December 27, 2012 20
Cách thức tính độ hỗ trợ của ứng viên
Tính độ hỗ trợ ứng viên là vấn đề cần quan tâm
Số lượng ứng viên là rất lớn
Một giao dịch chứa nhiều ứng viên
Phương pháp:
Tập mục ứng viên được chứa trong một câybăm
(hashtree)
Lá của cây băm chứa một danh sách các tập mục và
bộ đếm
Nút trong chứa bảng băm
Hàm tập con: tìm tất cả các ứng viên
December 27, 2012 21
Cách thức tính độ hỗ trợ của ứng viên
ượ ư
ộ
ữ ứ
ố
i m t nút khác (Nút
c l u tr trong m t cây-băm. k đ đ sâu 1. Lá ch a m t danh sách t p m c ở ộ ụ ộ ộ ộ ả
ủ
ả
đ ở ộ
ỗ đ sâu d+1).
ở ộ t c các nút là lá.
ứ i các nút ấ ả
sâu d tr t ỏ ớ Khi kh i t o, t ở ạ Khi thêm m t t p m c c:
ộ ậ g c đi xu ng theo cây cho đ n khi g p m t lá.
ế
ặ
ộ
ụ ố ộ
b t đ u t ắ ầ ừ ố T i m t nút trong đ sâu d: ộ ạ quy t đ nh theo nhánh nào b ng cách áp d ng hàm băm t
ụ
ằ
ớ
i m c th d c a ứ
ụ
ủ
ng t p m c t
t quá ng
ng quy đ nh, nút lá đ
c
Khi s l
ụ ạ
i m t lá v ộ
ượ
ưỡ
ị
ượ
chuy n thành m t nút trong.
ế ị t p m c này. ụ ậ ố ượ ể
ậ ộ
T p các ng viên C ứ ậ G c c a cây băm ậ ủ Nút trong ch a m t b ng băm: m i thùng c a b ng tr t ỏ ớ
Nếu ở nút gốc: băm vào mỗi mục trong t. Nếu ở một lá: tìm các tập mục ở lá này thuộc t và bổ sung chỉ dẫn tới các tập mục
này tới tập trả lời.
Nếu ở nút trong và đã đạt được nó bằng cách băm mục i, trên từng mục đứng sau i
trong t và áp dụng đệ quy thủ tục này sang nút trong thùng tương ứng.
Bắt đầu từ gốc, tìm tất cả các ứng viên thuộc giao dịch t:
December 27, 2012 22
Ví dụ: Tính hỗ trợ các ứng viên
Hàm t p con ậ
Transaction: 1 2 3 5 6
3,6,9
1,4,7
2,5,8
1 + 2 3 5 6
1 3 + 5 6
2 3 4 5 6 7
1 4 5
3 4 5
1 3 6
3 6 7 3 6 8
1 2 + 3 5 6
3 5 6 3 5 7 6 8 9
1 5 9
1 2 4 4 5 7
1 2 5 4 5 8
December 27, 2012 23
Thi hành hiệu quả thuật toán Apriori trong SQL
Khó để có thể có một hiệu quả tốt nếu chỉ tiếp cận
thuần SQL (SQL92)
Sử dụng các mở rộng quan hệ đối tượng như UDFs,
BLOBs, hàm bảng v.v.
Nhận được các thứ tự tăng quan trọng Xem bải: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating
association rule mining with relational database systems: Alternatives and implications. In SIGMOD’98
December 27, 2012 24
Thách thức khai phá mẫu phổ biến
Thách thức
Duyệt phức CSDL giao dịch
Lượng rất lớn các ứng viên
Tẻ nhạt việc tính toán độ hỗ trợ
Cải tiến Apriori: tư tưởng chung
Giảm số lần duyệt CSDL giao dịch
Rút số lượng các ứng viên
Giảm nhẹ tính độ hỗ trợ của các ứng viên
December 27, 2012 25
DIC (Đếm tập mục động): Rút số lượng duyệt CSDL
ABCD
ABC ABD ACD BCD
Mỗi khi A và D được xác định là phổ biến thì việc tính toán cho AD được bắt đầu Mỗi khi mọi tập con độ dài 2 của BCD
được xác định là phổ biến: việc tính toán cho BCD được bắt đầu.
AB AC BC AD BD CD
Transactions
C D
A B
Apriori
1-itemsets 2-itemsets …
{} Itemset lattice
1-itemsets 2-items
DIC
3-items
S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD’97
December 27, 2012 26
Giải pháp Phân hoạch (Partition): Duyệt CSDL chỉ hai lần
Mọi tập mục là phổ biến tiềm năng trong CSDL bắt buộc phải phổ biến ít nhất một vùng của DB Scan 1: Phân chia CSDL và tìm các mẫu cục
bộ
Scan 2: Hợp nhất các mẫu phổ biến tổng thể A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95
December 27, 2012 27
Ví dụ về mẫu phổ biến
Chọn một mẫu của CSDL gốc, khai phá mẫu phổ biến nội
bộ mẫu khi dùng Apriori
Duyệt CSDL một lần để kiểm tra các tập mục phổ biến tìm thấy trong ví dụ, chỉ có bao (borders ) đóng của các mẫu phổ biến được kiểm tra Ví dụ: kiểm tra abcd thay cho ab, ac, …, v.v.
Duyệt CSDL một lần nữa để tìm các mẫu phổ biến bị mất
(bỏ qua)
H. Toivonen. Sampling large databases for association rules. In
VLDB’96
December 27, 2012 28
DHP: Rút gọn số lượng các ứng viên
Một ktập mục mà bộ đếm trong lô băm tương ứng dưới
ngưỡng thì không thể là tập mục phổ biến Ứng viên: a, b, c, d, e Điểm vào băm: {ab, ad, ae} {bd, be, de} … 1tập mục phổ biến: a, b, d, e ab không là một ứng viên 2tập mục nếu tống bộ đếm
của {ab, ad, ae} là dưới ngưỡng hỗ trợ
J. Park, M. Chen, and P. Yu.
An effective hashbased algorithm for mining association rules. In SIGMOD’95
December 27, 2012 29
Eclat/MaxEclat và VIPER: Thăm dò dạng dữ liệu theo chiều ngang
Dùng danh sách tid của giáo dịch trong một tập mục
Nén danh sách tid
Tập mục A: t1, t2, t3, sup(A)=3
Tập mục B: t2, t3, t4, sup(B)=3
Tập mục AB: t2, t3, sup(AB)=2
Thao tác chính: lấy giáo của các danh sách tid M. Zaki et al. New algorithms for fast discovery of association rules. In KDD’97
P. Shenoy et al. Turbocharging vertical mining of large databases. In
SIGMOD’00
December 27, 2012 30
Thắt cơ chai của khai phá mẫu phổ biến
Duyệt CSDL nhiều là tốn kém KP mẫu dài cần nhiều bước để duyệt và sinh
nhiều ứng viên Để tìm các tập mục phổ biến i1i2…i100
1
0
0) = 21001 =
1) + (100
2) + … + (1
0
0
1.27*1030 !
Thắt cổ chai: sinh ứng viên và kiểm tra Tránh sinh ứng viên?
# duyệt: 100 # ứng viên: (100
December 27, 2012 31
KP mẫu phổ biến không cần sinh ƯV
Dùng các mục phổ biến để tăng độ dài mẫu từ các
mẫu ngắn hơn
“abc” là một mẫu phổ biến
Nhận mọi giao dịch có “abc”: DB|abc
“d” là một mục phổ biến trong DB|abc abcd là
một mẫu phổ biến
December 27, 2012 32
Xây dựng cây FP từ một CSDL giao dịch
(ordered) frequent items
min_support = 3
TID 100 200 300 400 500
Items bought {f, a, c, d, g, i, m, p} {a, b, c, f, l, m, o} {b, f, h, j, o, w} {b, c, k, s, p} {a, f, c, e, l, p, m, n}
{f, c, a, m, p} {f, c, a, b, m} {f, b} {c, b, p} {f, c, a, m, p}
{}
Header Table
1. Duyết CSDL một lần,
f:4
c:1
tìm các 1tập mục phổ biến (mẫu mục đơn)
c:3
b:1
b:1
a:3
p:1
2. Sắp xếp các mục phổ biến theo thứ tự giảm dần về bậc, flist
Item frequency head f c a b m p
4 4 3 3 3 3
m:2
b:1
3. Duyệt CSDL lần nữa, xây dựng FPtree
p:2 m:1
Flist=fcabmp
December 27, 2012 33
Lợi ích của cấu trúc FPtree
Tính đầy đủ
Duy trì tính đầy đủ thông tin để khai phá mẫu phổ biến Không phá vỡ mẫu dài bới bất kỳ giao dich
Tính cô đọng
Giảm các thông tin không liên quan: mục không phổ
biến bỏ đi
Sắp mục theo tần số giảm: xuất hiện càng nhiều thì
cành hiệu quả
Không lớn hơn so với CSDL thông thường
December 27, 2012 34
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 35
Luật kết hợp đa mức
Các mục có thể đa phân cấp Đặt hỗ trợ linh hoạt: Mục cấp thấp hơn là kỳ vọng hỗ trợ
thấp hơn.
CSDL giao dịch có thể được mã hóa theo chiều và mức Thăm dò KP đa mức chia sẻ
uniform support
reduced support
Level 1 min_sup = 5%
Level 1 min_sup = 5%
Milk [support = 10%]
Level 2 min_sup = 3%
2% Milk [support = 6%]
Skim Milk [support = 4%]
Level 2 min_sup = 5%
December 27, 2012 36
Kết hợp đa chiều
Luật đơn chiều:
buys(X, “milk”) (cid:222)
buys(X, “bread”)
Luật đa chiều: ‡
2 chiều hoặc thuộc tính
Luật kết hợp liên chiều (không có thuộc tính lặp) age(X,”1925”) (cid:217) occupation(X,“student”) (cid:222)
buys(X,“coke”)
Luật KH chiềukết hợp (lai/hybrid) (lặp thuộc tính)
age(X,”1925”) (cid:217) buys(X, “popcorn”) (cid:222)
buys(X, “coke”)
Thuộc tính phân lớp
Tìm số lượng các giá trị khả năng không được sắp
Thuộc tính định lượng
Số, thứ tự ngầm định trong miền giá trị
December 27, 2012 37
Kết hợp đa mức: Rút gọn lọc
Một vài luật có thể dư thừa do có quan hệ “tổ tiên” giữa
các mục.
Ví dụ
wheat bread [support = 8%, confidence = 70%]
milk (cid:222) 2% milk (cid:222)
wheat bread [support = 2%, confidence = 72%]
Nói rằng: luật đầu tiên là tổ tiên luật thứ hai.
Một luật là dư thừa nếu độ hỗ trợ của nó là khít với giá trị
“mong muốn”, dựa theo tổ tiên của luật.
December 27, 2012 38
Luật kết hợp định lượng
Numeric attributes are dynamically discretized
Such that the confidence or compactness of the rules
mined is maximized
Acat
(cid:222)
2D quantitative association rules: Aquan1 (cid:217) Aquan2 Cluster “adjacent” association rules to form general rules using a 2D grid Example age(X,”30-34”) (cid:217) income(X,”24K - 48K”) (cid:222)
buys(X,”high resolution TV”)
December 27, 2012 39 Data Mining: Concepts and Techniques
Khai phá luật KH dựa theo khoảng cách
Binning methods do not capture the semantics of interval
data
Equi-depth (depth 2) [7,20] [22,50] [51,53]
Distance- based [7,7] [20,22] [50,53]
Price($) 7 20 22 50 51 53
Equi-width (width $10) [0,10] [11,20] [21,30] [31,40] [41,50] [51,60]
Distancebased partitioning, more meaningful discretization
considering: density/number of points in an interval “closeness” of points in an interval
December 27, 2012 40
Độ đo hấp dẫn: Tương quan (nâng cao)
eat cereal [40%, 66.7%] là lạc
Phần trăm chung của sinh viên ăn ngũ cố là 75% cao hơn so với
66.7%. play basketball (cid:222)
not eat cereal [20%, 33.3%] là chính xác hơn, do
độ hỗ trợ và tin cậy thâos hơn
play basketball (cid:222)
Basketball
Not basketball
Sum (row)
Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao)
=
Cereal
2000
1750
3750
corr BA ,
BAP ( ) ( BPAP ) ) (
Not cereal
1000
250
1250
Sum(col.)
3000
2000
5000
¨
December 27, 2012 41
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 42
KPDL dựa trên ràng buộc
Tìm tất cả các mẫu trong CSDL tự động? — phi hiện thực!
Mẫu có thể quá nhiều mà không mục đích!
KPDL nên là quá trình tương tác
Người dùng trực tiếp xác định KPDL gì khi dùng ngôn
ngữ hỏi KPDL (hoặc giao diện đồ họa)
KP dựa theo ràng buộc
Linh hoạt người dùng: cung cấp ràng buộc trên cái mà
KP
Tối ưu hệ thống: thăm dò các ràng buộc để hiệu quả
KP: KP dựa theo ràng buộc
December 27, 2012 43
Ràng buộc trong KPDL
classification, association, etc. Ràng buộc dữ liệu — dùng câu hỏi kiếu SQL
Tìm các cặp sản phẩn mua cùngnhau trong Vancouver
vào Dec.’00
Ràng buộc kiểu tri thức:
Liên quan tới vùng, giá, loại hàng, lớp khách hàng
Ràng buộc chiều/cấp
Mua hàng nhỏ (price < $10) nhanh hơn mua hàng lớn
(sum > $200) Ràng buộc hấp dẫn
Luật mạng: min_support ‡
3%, min_confidence ‡
60%
Ràng buộc luật (mẫu)
December 27, 2012 44
KP ràng buộc <> tìm kiếm dựa theo ràng buộc
Cả hai hướng tới rút gọn không gian tìm kiếm Tìm mọi mẫu bảm đảm ràng buộc <> tìm một vài (một_ câu trả lời của tìm dựa theo ràng buộc trong AI (TTNT)
Cố tìm theo ràng buộc <> tìm kiếm heuristic Tích hợp hai cái cho một bài toán tìm kiếm thú vịi
KP ràng buộc <> tìm/lập luận dựa theo ràng buộc
Quá trình hỏi trong CSDL quan hệ đòi hỏi tìm tất cả KP mẫu ràng buộc chung một triết lý tương tựng như cố
gắng chọn về chiều sâu của câu hỏi
KP ràng buộc <> quá trình hỏi trong hệ CSDL quan hệ
December 27, 2012 45
KP mấu phổ biến ràng buộc: vấn đề tố ưu hóa câu hỏi
toán nên là Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C
Cho một câu hỏi KP Mấu phổ biến với một tập ràng buộc C, thì thuật
Tìm tất cát tập PB sau đó kiểm tra ràng buộc
Giải pháp “thơ ngây/hồn nhiên” (naïve)
Phân tích tính chất các ràng buộc một cách toàn diện Khai thác chúng sâu sắc có thể nhất trong tính toán mẫu
PB.
Tiếp cận hiệu quả hơn
December 27, 2012 46
Chống đơn điêu trong KP theo ràng buộc
TDB (min_sup=2)
Chống đon điệu (Antimonotonicity)
TID
Transaction
10
a, b, c, d, f
20
b, c, d, f, g, h
Một tập mục S vi phạm ràng buộc, mọi tập lớn hơn nó cũng vi phạm
30
a, c, d, e, f
v là chống đơn điệu
40
c, e, f, g
sum(S.Price) £ sum(S.Price) ‡
v là không chống đơn
Item
Profit
điệu
a
40
b
0
Ví dụ. C: range(S.profit) £
15 là chống
c
20
đơn điệu
d
10
Tập mục ab vi phạm C
e
30
f
30
Cũng vậy mọi tập chưa ab
g
20
h
10
December 27, 2012 47
Ràng buộc nào là chống đơn điệu
Ràng buộc Chống đơn điệu
S No
v ˛ S ˚ V no
yes
S ˝ V min(S) £ v no
v yes
min(S) ‡ max(S) £ v yes
v no
max(S) ‡ count(S) £ v yes
count(S) ‡ v no
0 ) yes
sum(S) £ sum(S) ‡ v ( a ˛ v ( a ˛ S, a ‡ S, a ‡ 0 ) no
v yes
range(S) £ range(S) ‡ v no
avg(S) q v, q ˛ , ‡ } convertible
{ = , £ x support(S) ‡ yes
support(S) £ x no
December 27, 2012 48
Tính đơn điệu trong KP dựa theo ràng buộc
TDB (min_sup=2)
TID
Transaction
Tính đơn điệu
10
a, b, c, d, f
20
b, c, d, f, g, h
30
a, c, d, e, f
40
c, e, f, g
Item Profit
v là đơn điệu
a
40
Khi một tập mục S thỏa mãn ràng buộc, thì mọi tập lơn hơn của nó cung thỏa mãn sum(S.Price) ‡ min(S.Price) £
v là đơn điệu
b
0
c
20
Ví dụ. C: range(S.profit) ‡
15
d
10
Tập mục ab đảm bảo C
e
30
f
30
Cúng vậy mọi tập chứa ab
g
20
h
10
December 27, 2012 49
Ràng buộc đơn điệu
Ràng buộc Đơn điệu
S yes
v ˛ S ˚ V yes
no
S ˝ V min(S) £ v yes
v no
min(S) ‡ max(S) £ v no
v yes
max(S) ‡ count(S) £ v no
count(S) ‡ v yes
0 ) no
sum(S) £ sum(S) ‡ v ( a ˛ v ( a ˛ S, a ‡ S, a ‡ 0 ) yes
v no
range(S) £ range(S) ‡ v yes
avg(S) q v, q ˛ , ‡ } convertible
{ = , £ x support(S) ‡ no
support(S) £ x yes
December 27, 2012 50
Tính cô đọng
Cho A1, là tập mục bảo đảm một ràng buộc cô đọng C, thì mọi S bảm đảm C là dựa trên A1 , chằng hạn., S chưa một tập con thuộc A1
Tư tưởng: Bỏ qua xem xét CSDL giao dịch, có chăng một tập mục S bảo đảm ràng buộc C có thể được xác định dựa theo việc chọn các mục
v là cô đọng
min(S.Price) £ sum(S.Price) ‡
v không cô đọng
Tính cô đọng:
Tối ưu hóa: Nếu C là cô đọng có thể đẩy đếm trước
December 27, 2012 51
Ràng buộc cô đọng
Ràng buộc Cô đọng
S yes
v ˛ S ˚ V yes
yes
S ˝ V min(S) £ v yes
v yes
min(S) ‡ max(S) £ v yes
v yes
max(S) ‡ count(S) £ v weakly
count(S) ‡ v weakly
0 ) no
sum(S) £ sum(S) ‡ v ( a ˛ v ( a ˛ S, a ‡ S, a ‡ 0 ) no
v no
range(S) £ range(S) ‡ v no
avg(S) q v, q ˛ , ‡ } no
{ = , £ x support(S) ‡ no
support(S) £ x no
December 27, 2012 52
Thuật toán Apriori— Ví dụ
itemset sup.
itemset sup.
L1
C1
Scan D
{1} {2} {3} {5}
2 3 3 3
{1} {2} {3} {4} {5}
2 3 3 1 3
Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
C2
itemset sup
C2
itemset sup
Scan D
L2
{1 3} {2 3} {2 5} {3 5}
2 2 3 2
itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
1 2 1 2 3 2
L3
C3
Scan D
itemset {2 3 5}
itemset sup 2 {2 3 5}
December 27, 2012 53
Thuật toán Naïve: Apriori +ràng buộc
itemset sup.
itemset sup.
L1
C1
Scan D
{1} {2} {3} {5}
2 3 3 3
{1} {2} {3} {4} {5}
2 3 3 1 3
Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
C2
itemset sup
C2
itemset sup
Scan D
L2
{1 3} {2 3} {2 5} {3 5}
2 2 3 2
itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
1 2 1 2 3 2
Constraint:
L3
C3
Scan D
itemset {2 3 5}
itemset sup 2 {2 3 5}
Sum{S.price < 5}
December 27, 2012 54
Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu
itemset sup.
itemset sup.
L1
C1
Scan D
{1} {2} {3} {5}
2 3 3 3
{1} {2} {3} {4} {5}
2 3 3 1 3
Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
C2
itemset sup
C2
itemset sup
Scan D
L2
{1 3} {2 3} {2 5} {3 5}
2 2 3 2
itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
1 2 1 2 3 2
Constraint:
L3
C3
Scan D
itemset {2 3 5}
itemset sup 2 {2 3 5}
Sum{S.price < 5}
December 27, 2012 55
The Constrained Apriori Algorithm: Push a Succinct Constraint Deep
itemset sup.
itemset sup.
L1
C1
Scan D
{1} {2} {3} {5}
2 3 3 3
{1} {2} {3} {4} {5}
2 3 3 1 3
Database D TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5
C2
itemset sup
C2
itemset sup
Scan D
L2
{1 3} {2 3} {2 5} {3 5}
2 2 3 2
itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
{1 2} {1 3} {1 5} {2 3} {2 5} {3 5}
1 2 1 2 3 2
Constraint:
L3
C3
Scan D
itemset {2 3 5}
itemset sup 2 {2 3 5}
min{S.price <= 1 }
December 27, 2012 56
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 57
CSDL tuần tự và Phân tích mẫu tuần tự
December 27, 2012 58
CSDL TT và PT MTT (2)
CSDL giao dịch, CSDL chuỗi thời gian <> CSDL tuần tự
Mấu PB <> mấu TT (PB)
Tuần tự mua của khách hàng:
Đầu tiên mua máy tính, sau đó CDROM, và sau đó là máy
ảnh số, trong vòng 3 tháng.
Phẫu thuật y tế, thảm họa tự nhiên (động đất…), quá trình KH
và kỹ nghệ, chứng khoán và thị trường….
Mẫu gọ điện thoại, dòng click tại Weblogs
Dãy DNA và cấu trúc gene
Ứng dụng của KP Mấu TT
December 27, 2012 59
Khái niệm KP mấu TT
Cho một tập các dãy, tìm tập đầy đủ các dãy con
phổ biến
dãy TT : < (ef) (ab) (df) c b >
CSDL dãy TT
SID
sequence
10
Một phần tử chứa một tập mục. Tập mục trong một phần tử là không thứ tự , và viết chúng theo ABC.
20
<(ad)c(bc)(ae)>
30
<(ef)(ab)(df)cb>
40
Cho độ hỗ trợ min_sup =2, <(ab)c> là mẫu tuần tự sequential pattern
December 27, 2012 60
