Ph n III: Khai m d li u và khám phá tri th c ứ ỏ ữ ệ ầ
Ch
ng 7:
ươ
Khai m d li u
ỏ ữ ệ
Tham kh o thêm: ả
ọ ơ ở ọ ế ả
[1] GS.TSKH Hoàng Ki m. Bài gi ng cao h c môn h c c s tri th c và ng d ng. ĐHKHTN-TPHCM. ứ ứ ụ
[2] Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. for Knowledge Discovery. Kluwer Data Mining Methods Academic Publishers, 1998
[3] Citeseer - Scientific Literature Digital Library. Artificial Intelligence-http://citeseer.nj.nec.com/ArtificialIntelligence/ - 2003
I. M t s bài toán đi n hình v data mining ể ộ ố ề
Bài toán khám phá lu t k t h p ậ ế ợ
Bài toán phân lo i d li u ạ ữ ệ
Bài toán gom nhóm d li u ữ ệ
Bài toán l p mô hình ậ
Bài toán d báoự
…
I. M t s bài toán đi n hình v data mining (tt) ộ ố ể ề
a. Phát hi n lu t k t h p (association rules) ậ ế ợ ệ
ng mô t ng ệ ữ ườ ữ đ i t ả ố ượ
Tìm ra nh ng m i liên h gi a các tr ố trong CSDL và xây d ng thành các lu t c th . ậ ụ ể ự
ế ợ ề ẩ ứ ọ ấ
Lu t k t h p là tri th c quan tr ng nh t ti m n trong ậ CSDL.
c các ượ
Ví d :ụ Sau khi phân tích m t CSDL bán hàng ta tìm ra đ ộ lu tậ
(1): N u khách hàng mua món A cũng s mua món B. ế ẽ
(2): N u khách hàng mua món C thì tháng sau s mua món D. ẽ ế
…
I. M t s bài toán đi n hình v data mining (tt) ộ ố ể ề
b. Phân l p (classification) ớ
Phân nh ng đ i ữ ố ng d li u t ữ ệ ượ có đ c tr ng ư ặ c a l p C vào ủ ớ l p Cớ
Lớp C
Lớp A
Lớp B
I. M t s bài toán đi n hình v data mining (tt) ộ ố ể ề
c. Gom nhóm (Clustering)
ng
vào ự
Gom nh ng ữ đ i t ố ượ d li u ữ ệ ng t t ươ 1 nhóm
Nhoùm 3 Nhoùm 1 Nhoùm 2
Tham kh o thêm: ả
[1] Krzysztof J. Cios, Witold Pedrycz, Roman W. Swiniarski. Data Mining Methods for Knowledge Discovery. Kluwer Academic Publishers, 1998
[2] Citeseer - Scientific Literature Digital Library. Artificial Intelligence- http://citeseer.nj.nec.com/ArtificialIntelligence/ - 2003
II. Lu t k t h p ậ ế ợ
1. M t s khái ni m: ộ ố ệ
ng g i là items ậ ợ ườ ọ Cho I = {i1, i2, i3, …, in} là t p h p các tr
D: t p các giao tác có các giao tác T I ậ
i mà Ti ˝
˝ T ch a X n u X T (X là t p có các ph n t I). ứ ế ậ ầ ử ˝
M i giao tác T ỗ ỉ
i có ch danh là TID.
ậ ế ợ ệ ề ữ ộ ố ệ ậ
(cid:222) (cid:204) ụ ữ ệ Y. Chúng ta có lu t k t h p X I, Y (cid:204) Lu t k t h p là m t m i liên h đi u ki n gi a hai t p các h ng m c d li u X và Y theo d ng sau: N u X thì Y, và ký hi u ệ ạ ạ là X (cid:222) I và X ậ ế ợ ế Y, n u X ế
˙ Y = ˘
(cid:222) Y có đ support là s n u có s% s giao tác trong D có ố ế
¨ ộ Y. Hay là : Lu t X ậ ch a X ứ
support (X(cid:222) Y) = s% = Card(X¨ Y)/ Card(D) %
II. Lu t k t h p (tt) ậ ế ợ
ộ ố ế
Lu t Xậ (cid:222) Y có đ tin c y là c (confidence) n u có c% s giao tác ¨ Y so v i s giao tác trong D ch a X, khi đó ta có : trong D ch a Xứ ậ ớ ố ứ
c = Card(X¨ Y)/Card(X) %
ạ ậ ộ
ụ ữ ệ ị ưỡ
T p các h ng m c d li u g i là ItemSet có đ support l n ọ ớ h n hay b ng giá tr ng c g i ng nh nh t (g i là minsupp) đ ượ ọ ọ ỏ ấ ằ ơ c g i là các Small ItemSet i đ là Large ItemSet. Các ItemSet còn l ạ ượ ọ
ộ ậ ỗ
ữ ủ ủ ớ ầ
ỏ ấ ọ ậ
(cid:222) ộ (L\A). V i m i m t Large ItemSet - L, và A là m t t p con khác r ng ớ ỗ ộ ph n trăm gi a support c a L so v i support c a c a L, n u t l ế ỉ ệ ủ A l n h n hay b ng đ tin c y nh nh t. (g i là minconf) thì ta có ằ ớ ơ lu t k t h p A ậ ế ợ
II. Lu t k t h p (tt) ậ ế ợ
ng Ví d :ụ (minh h a 2 đ i l ạ ượ minsupp và minconf) ọ
TID Age Married NumCars
100 23 No 1
200 25 Yes 1
300 29 No 0
400 34 Yes 2
500 38 Yes 2
Ng i ta đ a ra minsupp = 40% và mincon f = 50 %. ườ ư
Tìm ra đ c 2 lu t k t h p th a mãn minsupp và minconf ượ ậ ế ợ ỏ
(1): Age (30..39) and (Married: Yes) (cid:222) NumCars = 2 (s = 40%, c = 100%)
(2): NumCars(0..1) (cid:222) Married = No (s = 40%, c = 66,6%).
II. Lu t k t h p (tt) ậ ế ợ
2. Bi n đ i CSDL ế ổ
ữ ộ
ị ủ ế ả ươ ỗ ớ ộ ả ị
Phân chia giá tr c a thu c tính thành nh ng kho ng và ng ứ ng đ d v i m i kho ng liên k t nó v i m t giá tr nguyên d ể ễ ớ dàng thao tác trên các thu c tính. ộ
Thu c tính trong CSDL ộ
Thu c tính không ị
ng ộ đ nh l ị ượ Thu c tính đ nh ộ ngượ l
Ví d : thu c tính Age ộ ụ
Ví d : Thu c tính ộ ụ Married
II. Lu t k t h p (tt) ậ ế ợ
fi 20 ị ừ ộ ậ
50. Ta có th ể 50 thành 4 kho ng: 10..19; 20..29; 30..39; 40..49. Xem m i ỗ
t là: 1, 2, 3, 4. Ví d :ụ CSDL có thu c tính Age nh n giá tr t chia 20 fi mi n này nh là m t thu c tính riêng l n l ề ầ ượ ả ộ ư ộ
TID Thu c tính ộ TID Age
100 3 100 32
bi n đ i thành ế ổ 200 4 200 48
300 2 300 21
400 3 400 34
500 1 500 15
II. Lu t k t h p (tt) ậ ế ợ
3. Tìm lu t k t h p ậ ế ợ
Đ rút ra đ c lu t trong CSDL c n ti n hành 5 b c sau: ể ượ ế ậ ầ ướ
ủ ộ ỗ ầ ả ị
B1: Xác đ nh kho ng phân chia c a m i thu c tính khi c n phân tích.
ế ợ ộ ỗ
ệ ậ b c B1 ở ướ c nhanh, d ễ
B2: K t h p m i kho ng thu c tính đã phân chia ả v i m t s nguyên đ th c hi n các thu t toán đ ượ ể ự ớ ộ ố dàng.
ạ ậ ủ ớ
B3: So sánh các support c a các item v i minsupp, t o t p Largeitemset.
B4: ABCD và AB là Large itemset ta rút ra đ ượ c lu t ậ
AB (cid:222) CD khi support(ABCD)/support(AB) >= minconf
B5: Xác đ nh ch n nh ng lu t phù h p ợ ữ ọ ậ ị
II. Lu t k t h p (tt) ậ ế ợ
ụ ề ồ ơ trên chia kho ng trên thu c ả ộ
Ví d :ụ Dùng ví d v h s nhân s tính AGE (gi ự ở s chia thành 4 kho ng). ả ử ả
Minsupp = 40% = 2 records
Minconf = 50%
TID Age Married NumCars
100 23 No 1
200 25 Yes 1
300 29 No 0
400 34 Yes 2
500 38 Yes 2
II. Lu t k t h p (tt) ậ ế ợ
Các kho ng chia Age ả
Age
Married
NumCars
TID
Interval
100
20 .. 24
No
1
20 .. 24
200
25 .. 29
Yes
1
25 .. 29
300
25 .. 29
No
0
30 .. 34
400
30 .. 34
Yes
2
35 .. 39
500
35 .. 39
Yes
2
K t h p thu c tính Age và Married v i m t s nguyên ớ ộ ố ế ợ ộ
Interval
Integer
Value
Integer
20 .. 24
1
Yes
1
25 .. 29
2
No
2
30 .. 34
3
35 .. 39
4
II. Lu t k t h p (tt) ậ ế ợ
B ng k t qu sau khi bi n đ i ế ổ ế ả ả
TID Age Married NumCars
100 1 2 1
200 2 1 1
300 2 2 0
400 3 1 2
500 4 1 2
II. Lu t k t h p (tt) ậ ế ợ
T p Large itemset tìm đ ậ c nh sau: ư
ượ Itemset Support
{(Age: 20 .. 29)} 3
{(Age: 30 .. 39)} 2
{(Married: Yes)} 3
{(Married: No)} 2
{(Numcars: 0 .. 1)} 3
2 {(Age: 30 .. 39), (Married: Yes)}}
Rút ra đ ượ c các lu t sau: ậ
Rule S C
(Numcars: 2) 40% 100%
(Age: 30..39) and (Married:Yes) (cid:222) (Age: 20..29) (cid:222) (Numcars: 0..1) 60% 66,6%
II. Lu t k t h p (tt) ậ ế ợ
Ví d : Bài toán tìm lu t k t h p ậ ế ợ ụ
Cho CSDL sau: Tìm các lu t k t h p n u cho ậ ế ợ ế
minsupp = 0.5(50%) và minconf = 1(100%)
Hóa đ nơ Các m t hàng ặ
1 Bánh mì, n ướ c ng t, s a ọ ữ
2 Bia, bánh mì
3 Bia, n ướ c ng t, khăn gi y, s a ấ ữ
4 ọ Bia, bánh mì, khăn gi y, s a
5 ấ ữ N c ng t, khăn gi y, s a ấ ữ ướ ọ
II. Lu t k t h p (tt) ậ ế ợ
Ta có:
c ng t”) = 3/5; ướ ọ
sp(“bánh mì”) = 3/5; sp(“bia”) = 3/5; sp(“n sp(“s a”) = 4/5; sp(“khăn gi y”) = 3/5; ữ ấ
(cid:222) F1 = {“bánh mì”, “bia”, “n c ng t”, “s a”, “khăn gi y”} ướ ữ ọ ấ
(cid:222) C2 = { {“bánh mì”,“bia”}, {“bánh mì”,“n c ng t”}, ọ
ữ ấ
ữ ấ {“bánh ướ {“bia”,“nu c ng t”}, ọ ớ {“nu c ng t”,”s a”}, ữ ọ ớ
mì”,“s a”}, {“bánh mì”,“khăn gi y”}, {“bia”,”s a”}, {“bia”,”khăn gi y”}, {“nu c ng t”,”khăn gi y”}, {“s a”,”khăn gi y”} } ọ ớ ấ ữ ấ
II. Lu t k t h p (tt) ậ ế ợ
Tìm F2 t C2: ừ
sp({“bánh mì”, “bia”}) = 2/5 (lo i)ạ
sp({“bánh mì”,”nu c ng t”}) = 1/5 (lo i) ớ ọ ạ
sp({“bánh mì”,”s a”}) = 2/5 (lo i) ữ ạ
…
sp({“nu c ng t”, “s a”}) = 3/5 ữ ọ ớ
…
sp({“s a”,”khăn gi y”}) = 3/5 ữ ấ
(cid:222) F2 = {{“n ướ c ng t”,”s a”}, {“s a”,”khăn gi y”}} ữ ữ ọ ấ
(cid:222) C3 = {{“nu c ng t”,”s a”,”khăn gi y”}} ữ ớ ọ ấ
II. Lu t k t h p (tt) ậ ế ợ
Tìm F3 t C3: ừ
sp({“nu c ng t”,”s a”,”khăn gi y”}) = 2/5 (lo i) ữ ọ ớ ạ ấ
(cid:222) F3 = {}
(cid:222) C4 = {}
V y t p ph bi n là {{“n c ng t”,”s a”}} ổ ế ậ ậ ướ ữ ọ
Ta xây d ng 2 lu t ậ ự
(R1) “n “n ướ ọ fi c ng t” ữ fi “s a”; (R2) “s a” ữ ướ c ng t” ọ
conf(R1) = sp(R1)/sp(“n c ng t”) = 3/5 : 3/5 = 1 (100%) ướ ọ
conf(R2) = sp(R1)/sp(s a) = 3/5 : 4/5 = ¾ (75%) (lo i) ữ ạ
II. Lu t k t h p (tt) ậ ế ợ
V y tìm đ ậ ượ ọ fi c 1 lu t: “nu c ng t” ớ ậ “s a”ữ
v i minsupp = 50% minconf = 100% ớ
Khách hàng mua “n c ng t” thì cũng s mua “s a” ướ ữ ọ ẽ
4. Thu t toán tìm lu t k t h p ậ ế ợ ậ
R : X fi P \ X
Bö ô ù c 1 : Lie ä t ke â t a á t c a û c a ù c t a ä p c o n P c u û a I s a o c h o (cid:231) P (cid:247) > 1 . Bö ô ù c 2 : Vô ù i m o ã i t a ä p c o n P , lie ä t ke â t a á t c a û c a ù c t a ä p c o n X kh a ù c t ro á n g c u û a P . Lu a ä t R ñ ö ô ïc h ìn h t h a ø n h b ô û i : Thu t toán APRIORITID ậ
ả cao h c môn h c c s tri th c và ng ọ ơ ở ứ ứ ọ ả
(Tham kh o thêm bài gi ng ế ) d ng. ĐHKHTN-TPHCM c a GS.TSKH Hoàng Ki m ủ ụ
