Bài giảng Khai thác dữ liệu & ứng dụng (data mining) - Bài 4: Khai thác chuỗi tuần tự - Nguyễn Hoàng Tú Oanh

Chia sẻ: An Pham | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

259
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Khai thác dữ liệu & ứng dụng (data mining) - Bài 4: Khai thác chuỗi tuần tự có nội dung giới thiệu về chuỗi tuần tự, các khái niệm cơ bản, thuật toán GSP khai thác chuỗi tuần tự. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai thác dữ liệu & ứng dụng (data mining) - Bài 4: Khai thác chuỗi tuần tự - Nguyễn Hoàng Tú Oanh

KHAI THÁC DỮ LIỆU & ỨNG DỤNG (DATA MINING) GV : NGUYỄN HOÀNG TÚ ANH 1 BÀ I 4 KHAI THÁC CHUỖI TUẦN TỰ 2 1
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ự 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) 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 4 2
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 Tập 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 điểm t Dữ liệu Web Hoạt động duyệt web của Tập các file đã xem ( Trang chủ, trang người sử dụng sau khi nhắp chuột ) index , thông tin liên lạc, … Chuỗi gen Chuỗi DNA Phần tử của chuỗi DNA Tổ hợp của A,T,G,C Phần tử Sự kiện (Giao dịch) E1 E1 E3 (Hạng E2 E2 E2 E3 E4 mục) Chuỗi 5 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ự 6 3
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ự. 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 = < s1 s2 … sn > 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 : < C (M,P) (S,T) > là một 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 = < a1 a2 … an > là chuỗi con của chuỗi sj = < b1 b2 … bm > nếu : n≤m ∃ các số nguyên i1 < i2 Có < {1,2} {3,4} > < {1} {2} > Không < {2,4} {2,4} {2,5} > < {2} {4} > Có 8 4
KHÁI NIỆM CƠ BẢN 2. CSDL CHUỖI Mã KH Mã hàng Ngày mua Cho CSDL D 100 a 10 100 a, b, c 15 Ví dụ : 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 e, f 20 300 … 400 400 e, g 10 9 … KHÁI NIỆM CƠ BẢN 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% SID Sequence s1 = 100 s2 = 200 s3 = 300 Supp(s1) =? 400 Supp(s2) =? 10 Supp(s3) =? 5
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ưỡ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 s1 = , 300 s2 = , s3 = có 400 phải là chuỗi phổ biến ? 11 KHÁI NIỆM CƠ BẢN 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. 12 6
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 dựa 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ơ 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 Seq. ID Sequence 10 20 minsupp = 2 30 40 14 50 7
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ự 15 THUẬT TOÁN GSP 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 16 8
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 của từng 4 ứng viên và tìm F1 3 -> F1 = , , , , , 3 2 Seq. ID Sequence 1 10 20 1 30 40 50 minsupp =2 17 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ử 18 9
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 19 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 20 10
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
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 23 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 24 12
VÍ DỤ THUẬT TOÁN GSP 5th scan: 1 cand. 1 length-5 Supp(Cand.)< < minsupp seq. pat. 4th scan: 8 cand. 6 length-4 … Cand. ∉ CSDL seq. pat. … 3rd scan: 46 cand. 19 length-3 seq. pat. 20 cand. not in DB at all … … … 2nd scan: 51 cand. 19 length-2 seq. pat. 10 cand. not in DB at all Seq. ID Sequence 1st scan: 8 cand. 6 length-1 10 seq. pat. 20 30 minsupp =2 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 : 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; 26 13
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 27 không ph bin 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 28 14
BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN • Thời gian : 7’ F3 • Giả sử F3 là tập gồm 7 < {1} {2} {3} > chuỗi < {1} {2 5} > < {1} {5} {3} > • Xác định tập ứng viên C4 < {2} {3} {4} > < {2 5} {3} > • Trình bày kết quả trước lớp < {3} {4} {5} > < {5} {3 4} > 29 ĐÁP ÁN BÀI TẬP XD TẬP CHUỖI ỨNG VIÊN F3 < {1} {2} {3} > < {1} {2 5} > < {1} {5} {3} > < {2} {3} {4} > < {2 5} {3} > < {3} {4} {5} > < {5} {3 4} > 30 15
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) 31 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 Seq. ID Sequence 10 20 30 40 50 32 16
ĐÁ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 tập 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 dụng ý 10 a,c,d,f 25 tưởng thuật toán 20 a, b,f 15 FP-Growth vào bài 20 e 20 toán tìm chuỗi phổ 30 a,b, f 10 biến không và như 40 d,g,h 10 thế nào ? 40 b,f 20 40 a,g,h 25 34 17
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. http://illimine.cs.uiuc.edu/demo/ : Demo một số thuật toán tìm tập phổ biến và chuỗi phổ biến 4. http://www- 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 35 Q&A 36 18