Giáo trình Khai thác dữ liệu và ứng dung - Bài 4: Khai thác chuỗi tuần tự - Nguyễn Hoàng Tú Anh

Nội dung text: Giáo trình Khai thác dữ liệu và ứng dung - Bài 4: Khai thác chuỗi tuần tự - Nguyễn Hoàng Tú Anh

1. KHAI THÁC DỮ LI ỆU & ỨNG D ỤNG (DATA MINING) GV : NGUY ỄN HOÀNG TÚ ANH 1 BBBÀBÀÀÀII 4I 4 KHAI THÁC CHU I TU N T 2 1
2. NỘI DUNG 1. Gi i thi u 2. Khái ni m cơ bn 3. Thu t toán GSP khai thác chu i tu n t 3 GI I THI U
   Th t (theo th i gian): quan tr ng CSDL chu i th i gian (time-series DB) , CSDL chu i (sequence DB) Tp (mu) ph bi n → Mu tu n t ph bi n (sequental pattern)
   ng dng ca khai thác mu tu n t Chu i mt hàng : Mua máy tính, sau ó mua CD-ROM, sau ó mua máy camera k thu t s trong vòng 3 tháng Ch m sóc bnh nhân, ti ha t nhiên (ng t), qui trình k thu t, th tr ưng và ti p th , Cu c gi in tho i, Weblog Chu i DNA và cu trúc gen 4 2
3. VÍ D D LI U CHU I CSDL Chu i Ph n t S ki n chu i (giao d ch) (h ng m c) Khách hàng Quá trình mua hàng c a Tp các m t hàng ưc Sách, s tay, CD, khách hàng khách hàng mua vào th i im t D li u Web Ho t ng duy t web c a Tp các file ã xem ( Trang ch , trang ng ưi s dng sau khi nh p chu t ) index , thông tin liên lc, Chu i gen Chu i DNA Ph n t ca chu i DNA T hp c a A,T,G,C ao 5 NỘI DUNG 1. Gi i thi u 2. Khái ni m cơ bn 3. Thu t toán GSP khai thác chu i tu n t 6 3
4. KHÁI NI ỆM C Ơ B ẢN 1. CHU I (Sequence) Chu i là danh sách các ph n t ( giao d ch) có th t. Mi ph n t ca chu i : tp các s ki n (h ng mc) Các s ki n trong m t ph n t không có th t (thưng vi t theo b ng ch cái) Ký hi u : Chu i s = vi sj là tp các s ki n. sj - gi là ph n t ca chu i s và có dng (x 1x2 xm ) vi xj là mt s ki n (h ng m c) VD : là mt chu i có chi u dài =5 và có 3 ph n t 7 KHÁI NI ỆM C Ơ B ẢN  CHU I (tt)
   Chu i si = là chu i con ca chu i sj = nu :
   n ≤≤≤ m
   ∃∃∃ các s nguyên i 1 Có Không Có 8 4
5. KHÁI NI ỆM C Ơ B ẢN 2. Mã Mã hàng Ngày CSDL CHU I KH mua Cho CSDL D 100 a 10 Ví d : 100 a, b, c 15 100 a, c 20 100 d 25 100 c, f 30 200 a, d 15 SID Sequence 200 c 20 100 200 b, c 25 200 200 a, e 30 300 300 e, f 20 400 400 e, g 10 9 KHÁI NI ỆM C Ơ B ẢN 2. CSDL CHU I (tt) Cho CSDL chu i D ={ d 1, d 2, , dn} ph bi n ca chu i s trên CSDL D là t l gi a s chu i ch a s trên tng s chu i trong D Supp( s)= |{ di ∈ D | s là chu i con ca di }| / | D| Ví d : s = Supp(s) = 2/4 = 50% SID Sequence s1 = 100 s2 = 200 s3 = 300 Supp(s 1) =? 400 Supp(s 2) =? 10 Supp(s 3) =? 5
6. KHÁI NI ỆM C Ơ B ẢN 3. BÀI TOÁN KHAI THÁC CHU I TU N T Cho CSDL chu i vàưng minsupp, c n tìm toàn b các chu i con ph bi n th a mãn minsupp ã cho. Ví d : CSDL chu i D và minsupp = 50% = 2/4 SID Sequence • Chu i con s = là 100 chu i tu n t ph bi n 200 • Các chu i s 1 = , 300 s2 = , s 3 = có 400 ph i là chu i ph bi n ? 11 KHÁI NI ỆM C Ơ B ẢN 4. THÁCH TH C Tn ti mt s lưng ln chu i tu n t ph bi n b du trong CSDL Thu t toán khai thác cn Tìm toàn b các mu th a mãn ng ưng minsupp Hi u qu , co dãn, s ln duy t CSDL nh Có th kt hp vi nhi u lo i ràng bu c ca ng ưi dùng. 12 6
7. KHÁI NI ỆM C Ơ B ẢN 5. NGHIÊN C U nh ngh a khái ni m và thu t toán gi ng thu t toán Apriori ( Apriori-All) - 1995. GSP – Ph ươ ng pháp khai thác da trên tính ch t Apriori - 1996 Ph ươ ng pháp phát tri n m u : PrefixSpan - 2001 13 KHÁI NI ỆM C Ơ B ẢN 6. Tính ch t cơ bn ca chu i tu n t Tính ch t Apriori : Nu S là chu i không ph bi n thì không có chu i bao (super-sequence) nào ca S là ph bi n Ví dụ : Trong CSDL d ưới, n ếu là chu ỗi không ph ổ bi ến →→→ , và cũng không ph ổ bi ến Seq. ID Sequence 10 20 30 40 14 50 7
8. NỘI DUNG 1. Gi i thi u 2. Khái ni m cơ bn 3. Thu t toán GSP khai thác chu i tu n t 15 THU ẬT TOÁN GSP 1. BN CH T GSP : Generalized Sequential Pattern- Agrawal & Srikant, EDBT’96 Duy t CSDL tìm các chu i ph bi n có dài 1. For mi cp ( chu i có dài k) To các chu i ng viên có dài (k+1) t các chu i ph bi n chi u dài k (s dng Apriori) Duy t CSDL m ph bi n ca tng chu i ng viên và lo i các ng viên không th a mãn ng ưng minsupp Lp li n khi không còn chu i ph bi n ho c không còn ng viên S dng tính ch t Apriori ct bt ng viên 16 8
9. VÍ DỤ THU ẬT TOÁN GSP C1 Cand Sup
   Các ng viên u tiên C1 : 3 , , , , , , , 5
   Duy t CSDL tính ph bi n ca tng 4 ng viên và tìm F1 3 -> F1 = , , , , , 3 2 Seq. ID Sequence 1 10 20 1 30 40 50 17 VÍ DỤ THU ẬT TOÁN GSP
   To các ng viên C2 : = phép kt
   Các chu i chi u dài = 2 và có 2 ph n t 18 9
10. VÍ DỤ THU ẬT TOÁN GSP
    To các ng viên C2 (tt)
    Các chu i chi u dài = 2 và có 1 ph n t
    Tng cng có 51 chu i ng viên chi u dài =2 19 VÍ DỤ THU ẬT TOÁN GSP
    Xác nh tp chu i ph bi n F2
    Duy t CSDL và xác nh ph bi n ca tng chu i ng viên chi u dài = 2
    Có 19 ng viên có ph bi n ≥ minsupp (=2)
    > Tp chu i ph bi n F2 gm có 19 chu i 20 10
11. VÍ DỤ THU ẬT TOÁN GSP Supp=2 2 1 1 1 1 21 VÍ DỤ THU ẬT TOÁN GSP Supp=0 1 1 1 0 0 2 1 2 22 11
12. VÍ DỤ THU ẬT TOÁN GSP
    To tp ng viên C3
    Dùng phép kt : F 2 vi F2
    Ví d : , và : chu i ph bi n chi u dài = 2  , , , , - ng viên chi u dài = 3
    , và chu i ph bi n chi u dài=2  , , , , - ng viên chi u dài = 3
    Phép lo i b : da trên tính ch t Apriori
    Có 46 ng viên chi u dài = 3 23 VÍ DỤ THU ẬT TOÁN GSP
    Tìm tp chu i ph bi n F3
    Duy t CSDL và xác nh ph bi n ca tng chu i ng viên chi u dài = 3
    Có 19 ng viên có ph bi n ≥ minsupp
    > Tp chu i ph bi n F3 gm 19 chu i 24 12
13. VÍ DỤ THU ẬT TOÁN GSP aae a a ea aae eaaoa a aae eaaoa a Seq. ID Sequence aae 10 ea 20 30 40 50 25 THU ẬT TOÁN GSP 2. Pseudo-Code Input : CSDL chu i D, minsupp Output : F - các chu i tu n t ph bi n trong D Ck : Tp chu i ng viên chi u dài k Fk : Tp chu i ph bi n chi u dài k F1 = Tìm_chu i_ph _bi n_chi u dài 1( D); // có dng for (k = 1; Fk ≠∅ ; k++) { Ck+1 = apriori_gen (L k); // To tp chu i ng viên chi u dài (k+1) if Ck+1 ≠∅ then { Duy t CSDL tính Fk+1 = { s ∈ Ck+1 | supp(s)≥ minsupp } } } 26 return F = ∪k Fk; 13
14. THU ẬT TOÁN GSP 3. To tp chu i ng viên chi u dài (k+1) Hàm apriori_gen nh n Fk và tr v tp chu i ng viên chi u dài (k+1) . Gm 2 bưc : kt và ct b Bưc kt : Chu i s1 kt vi chu i s2 nu Chu i s1 sau khi b bt i 1 hng mc u tiên thì gi ng nh ư Chu i s2 b bt 1 hng mc cu i cùng Kt qu phép kt = chu i s1 m rng thêm 1 hng mc cu i cùng ca chu i s2 . Hng mc thêm này có th to thành mt ph n t mi trong s1 nu nó là ph n t riêng bi t thu c s2, ng ưc li là mt thành viên ca ph n t cu i cùng ca s1 Bưc ct b : lo i các chu i ng viên có ch a các chu i con không ph bi n 27 VÍ DỤ TẠO T ẬP CHU ỖI ỨNG VIÊN
    Gi s F3 = { , , , , , }
    Sau bưc kt :
    C4 = { , }
    không kt ưc vi chu i nào khác vì không tn ti chu i có dng ho c
    Sau bưc lo i bt :
    C4 = { } vì ∉ F3 nên b lo i 28 14
15. BÀI T ẬP XD TẬP CHU ỖI ỨNG VIÊN • Th i gian : 7’ F3 • Gi s F3 là tp g m 7 chu i • Xác nh t p ng viên C 4 • Trình bày k t qu c l p 29 ĐÁP ÁN BÀI T ẬP XD TẬP CHU ỖI ỨNG VIÊN F3 30 15
16. HẠN CH Ế CỦA GSP
    S ng kh ng l tp chu i ng viên (c bi t chu i có chi u dài = 2)
    Duy t CSDL nhi u l n
    Không hi u qu khi khai thác các chu i dài -> M t trong các cách gi i quy t : PrefixSpan (t c trong tài li u tham kh o) 31 BÀI T ẬP TẠI L ỚP
    Th i gian : 10’
    Cho CSDL chu i và minsupp = 4
    Tìm các t p ng viên và tp chu i ph bi n Seq. ID Sequence 10 20 30 40 50 32 16
17. ĐÁP ÁN BÀI TẬP TẠI L ỚP 33 BÀI T P 1. Cho CSDL chu i D Mã Mã hàng Ngày và minsupp = 50%. KH mua Xác nh tp chu i 10 a, d 10 ph bi n trên D . 10 a, b, c 15 10 a, b,f 20 2. Có th áp dng ý tưng thu t toán 10 a,c,d,f 25 FP-Growth vào bài 20 a, b,f 15 20 e 20 toán tìm chu i ph bi n không và nh ư 30 a,b, f 10 th nào ? 40 d,g,h 10 40 b,f 20 40 a,g,h 25 34 17
18. TÀI LI U THAM KH O 1. R. Srikant, R. Agrawal . Mining sequential patterns : Generalizations and perfomance improvements . EDBT’96. 2. J. Han J. Pei. Pattern Growth Methods for Sequential Pattern Mining : Principles and Extensions , ACM SIGKDD 2001, USA . 3. : Demo m t s thu t toán tìm t p ph bi n và chu i ph bi n 4. users.cs.umn.edu/~kumar/dmbook/resources.htm Ch ươ ng trình m t s thu t toán và ph n m m c ơ bn c a các bài toán trong khai thác d li u 35 Q & A 36 18