Bài giảng Bài 4: Khai thác chuỗi tuần tự

11 KHAI THÁC DỮ LIỆU & ỨNG DỤNG (DATA MINING) GV : NGUYỄN HOÀNG TÚ ANH 2 BÀI 4 KHAI THÁC CHUỖI TUẦN TỰ 23 NỘI DUNG 1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác chuỗi tuần tự 4 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) Tập (mẫu) phổ biến → Mẫu tuần tự phổ biến (sequental pattern)
Ứng dụng của khai thác mẫu tuần tự Chuỗi mặt 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 bệnh nhân, tại họa tự nhiên (động đất), qui trình kỹ thuật, thị trường và tiếp thị, Cuộc gọi điện thoại, Weblog Chuỗi DNA và cấu trúc gen 35 Tổ hợp của A,T,G,CPhần tử của chuỗi DNAChuỗi DNAChuỗi gen Trang chủ, trang index , thông tin liên lạc, Tập các file đã xem ( sau khi nhắp chuột ) Hoạt động duyệt web của người sử dụng Dữ liệu Web Sách, sổ tay, CD, Tập các mặt hàng được khách hàng mua vào thời điểm t Quá trình mua hàng của khách hàng Khách hàng Sự kiện (hạng mục) Phần tử (giao dịch) ChuỗiCSDL chuỗi Chuỗi E1 E2 E1 E3 E2 E3 E4E2 Phần tử (Giao dịch) Sự kiện (Hạng mục) VÍ DỤ DỮ LIỆU CHUỖI 6 NỘI DUNG 1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác chuỗi tuần tự 47 1. CHUỖI (Sequence) Chuỗi là danh sách các phần tử ( giao dịch) có thứ tự. Mỗi phần tử của chuỗi : tập các sự kiện (hạng mục) 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 = với sj là tập các sự kiện. sj - gọi là phần tử của chuỗi s và có dạng (x1x2 xm ) với xj là một sự kiện (hạng mục) VD : là một chuỗi có chiều dài =5 và có 3 phần tử KHÁI NIỆM CƠ BẢN 8 KHÁI NIỆM CƠ BẢN  CHUỖI (tt)
Chuỗi si = là chuỗi con của chuỗi sj = nếu :
n ≤ m
∃ các số nguyên i1 < i2 < <in sao cho a1 ⊆ bi1 , a2 ⊆ bi2 , , an ⊆ bin Chuỗi dữ liệu Có Không Có Thuộc ?Chuỗi con 5910e, g 400 20e, f 300 15 20 25 30 a, d c b, c a, e 200 200 200 200 10 15 20 25 30 a a, b, c a, c d c, f 100 100 100 100 100 Ngày mua Mã hàngMã KH2. CSDL CHUỖI Cho CSDL D Ví dụ : KHÁI NIỆM CƠ BẢN 400 300 200 100 SequenceSID 10 2. CSDL CHUỖI (tt) Cho CSDL chuỗi D ={ d1, d2, , dn} Đ ph bin ca chui s trên CSDL D là t l gi a s chui cha s trên tng s chui trong D Supp(s)= |{di ∈ D | s là chui con ca di }| / |D| Ví dụ : s = Supp(s) = 2/4 = 50% s1 = s2 = s3 = Supp(s1) =? Supp(s2) =? Supp(s3) =? KHÁI NIỆM CƠ BẢN 400 300 200 100 SequenceSID 611 3. BÀI TOÁN KHAI THÁC CHUỖI TUẦN TỰ Cho CSDL chuỗi và ngưỡ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 KHÁI NIỆM CƠ BẢN • Chuỗi con s = là chuỗi tuần tự phổ biến • Các chuỗi s1 = , s2 = , s3 = có phải là chuỗi phổ biến ?400 300 200 100 SequenceSID 12 4. THÁCH THỨC Tồn tại một số lượng lớn chuỗi tuần tự phổ biến bị dấu trong CSDL Thuật toán khai thác cần Tìm toàn bộ các mẫu thỏa mãn ngưỡng minsupp Hiệu quả, co dãn, số lần duyệt CSDL nhỏ Có thể kết hợp với nhiều loại ràng buộc của người dùng. KHÁI NIỆM CƠ BẢN 713 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 dựa trên tính chất Apriori - 1996 Phương pháp phát triển mẫu : PrefixSpan - 2001 KHÁI NIỆM CƠ BẢN 14 6. Tính chất cơ bản của chuỗi tuần tự Tính cht Apriori : Nếu S là chuỗi không phổ biến thì không có chuỗi bao (super-sequence) nào của 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 KHÁI NIỆM CƠ BẢN 50 40 30 20 10 SequenceSeq. ID minsupp = 2 815 NỘI DUNG 1. Giới thiệu 2. Khái niệm cơ bản 3. Thuật toán GSP khai thác chuỗi tuần tự 16 1. BẢN 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 mỗi cấp ( chuỗi có độ dài k) Tạo 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ử dụng Apriori) Duyệt CSDL để đếm độ phổ biến của từng chuỗi ứng viên và loại các ứng viên không thỏa mãn ngưỡng minsupp Lặp lại đế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 THUẬT TOÁN GSP 917 VÍ DỤ THUẬT TOÁN GSP
Các ng viên đu tiên C1 : , , , , , , ,
Duyệt CSDL để tính độ phổ biến của từng ứng viên và tìm F1 -> F1 = , , , , , 50 40 30 20 10 SequenceSeq. ID minsupp =2 1 1 2 3 3 4 5 3 SupCandC1 18 VÍ DỤ THUẬT TOÁN GSP
To các ng viên C2 : = phép kết
Các chuỗi chiều dài = 2 và có 2 phần tử 10 19 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ử
Tổng cộng có 51 chuỗi ứng viên chiều dài =2 20 VÍ DỤ THUẬT TOÁN GSP
Xác đnh tp chui ph bin F2
Duyệt CSDL và xác định độ phổ biến của từng chuỗi ứng viên chiều dài = 2
Có 19 ứng viên có độ phổ biến ≥ minsupp (=2)
> Tập chuỗi phổ biến F2 gồm có 19 chuỗi 11 21 VÍ DỤ THUẬT TOÁN GSP 1 1 1 1 2 Supp=2 22 VÍ DỤ THUẬT TOÁN GSP 2 1 2 0 0 1 1 1 Supp=0 12 23 VÍ DỤ THUẬT TOÁN GSP
To tp ng viên C3
Dùng phép kết : F2 với 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ỏ : dựa trên tính chất Apriori
Có 46 ứng viên chiều dài = 3 24 VÍ DỤ THUẬT TOÁN GSP
Tìm tp chui ph bin F3
Duyệt CSDL và xác định độ phổ biến của từng chuỗi ứng viên chiều dài = 3
Có 19 ứng viên có độ phổ biến ≥ minsupp
> Tập chuỗi phổ biến F3 gồm 19 chuỗi 13 25 VÍ DỤ THUẬT TOÁN GSP 1st scan: 8 cand. 6 length-1 seq. pat. 2nd scan: 51 cand. 19 length-2 seq. pat. 10 cand. not in DB at all 3rd scan: 46 cand. 19 length-3 seq. pat. 20 cand. not in DB at all 4th scan: 8 cand. 6 length-4 seq. pat. 5th scan: 1 cand. 1 length-5 seq. pat. 50 40 30 20 10 SequenceSeq. ID minsupp =2 Supp(Cand.)< minsupp Cand. ∉ CSDL 26 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 : Tập chuỗi ứng viên chiều dài k Fk : Tập 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ó dạng for (k = 1; Fk ≠∅; k++) { Ck+1 = apriori_gen(Lk); // Tạo tập 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 } } } return F = ∪k Fk; 14 27 THUẬT TOÁN GSP 3. Tạo tập chuỗi ứng viên chiều dài (k+1) Hàm apriori_gen nhận Fk và trả về tập chuỗi ứng viên chiều dài (k+1). Gm 2 bưc : kt và ct b Bưc kt : Chui s1 kt vi chui s2 nu Chui s1 sau khi b bt đi 1 hng mc đu tiên thì gi ng như Chui s2 b bt 1 hng mc cu i cùng Kt qu phép kt = chuỗi s1 mở rộng thêm 1 hạng mục cuối cùng của chuỗi s2 . Hng mc thêm này có th to thành mt phn t mi trong s1 nu nó là phn t riêng bit thuc s2, ngưc li là mt thành viên ca phn t cu i cùng ca s1 Bưc ct b : loi các chui ng viên có cha các chui con không ph bin 28 VÍ DỤ TẠO TẬP CHUỖI ỨNG VIÊN
Giả sử F3 = {, , , , , }
Sau bước kết :
C4 = {, }
không kết được với chuỗi nào khác vì không tồn tại chuỗi có dạng hoặc
Sau bước loại bớt :
C4 = {} vì ∉ F3 nên bị loại 15 29 BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN • Thời gian : 7’ • Giả sử F3 là tập gồm 7 chuỗi • Xác định tập ứng viên C4 • Trình bày kết quả trước lớp F3 30 ĐÁP ÁN BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN F3 16 31 HẠN CHẾ CỦA GSP
Số lượng khổng lồ tập 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 hiu qu khi khai thác các chui dài -> Mt trong các cách gii quyt : PrefixSpan (t đc trong tài liu tham kho) 32 BÀI TẬP TẠI LỚP
Thời gian : 10’
Cho CSDL chuỗi và minsupp = 4
Tìm các tp ng viên và tp chui ph bin 50 40 30 20 10 SequenceSeq. ID 17 33 ĐÁP ÁN BÀI TẬP TẠI LỚP 34 BÀI TẬP 1. Cho CSDL chuỗi D và minsupp = 50%. Xác định tập chuỗi phổ biến trên D . 2. Có thể áp dụng ý tưởng thuật toán FP-Growth vào bài toán tìm chuỗi phổ biến không và như thế nào ? 1020 25 d,g,h b,f a,g,h 40 40 40 10a,b, f30 15 20 a, b,f e 20 20 10 15 20 25 a, d a, b, c a, b,f a,c,d,f 10 10 10 10 Ngày mua Mã hàngMã KH 18 35 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ơ bản của các bài toán trong khai thác dữ liệu 36 Q & A