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

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áckhá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.

Nội dung trích xuất từ tài liệu:
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ÁCCHUỖ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 tDữ 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ẢN2. 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ẢN2. CSDL CHUỖI (tt) Cho CSDL chuỗi D ={ d1, d2, …, dn} Đ ph bin ca chui s trên CSDL D là t l gia 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ẢN3. 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/4SID Sequence • Chuỗi con s = là100 chuỗi tuần tự phổ biến200 • Các chuỗi s1 = ,300 s2 = , s3 = có400 ...