Bài giảng Khai thác dữ liệu: Chương 3 - ThS. Dương Phi Long

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST

Báo xấu

2
lượt xem 1
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: Chương 3 - Tập phổ biến & Luật kết hợp" được biên soạn gồm các nội dung chính sau: Các khái niệm cơ bản; Thuật toán Apriori; Thuật toán FP-Growth; Độ đo tính lý thú của luật kết hợp. Mời các bạn cùng tham khảo!

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: Chương 3 - ThS. Dương Phi Long

TRƯỜNG ÐẠI HỌC CÔNG NGHỆ THÔNG TIN KHOA HỆ THỐNG THÔNG TIN Tài liệu bài giảng: KHAI THÁC DỮ LIỆU – IS252 Chương 3: TẬP PHỔ BIẾN & LUẬT KẾT HỢP ThS. Dương Phi Long – Email: longdp@uit.edu.vn
NỘI DUNG BÀI HỌC 01 Các khái niệm cơ bản 02 Thuật toán Apriori 03 Thuật toán FP-Growth 04 Độ đo tính lý thú của luật kết hợp 2
1. Mẫu phổ biến 2. CSDL giao dịch 3. Độ phổ biến và tập phổ biến Các khái niệm 4. Tập phổ biến tối đại 5. Tập phổ biến đóng cơ bản 6. Luật kết hợp 7. Bài toán khám phá Luật kết hợp 3
Đặt vấn đề Which items are frequently purchased together by customers? 4
Đặt vấn đề Which items are frequently purchased together by customers? Customer 1 Customer 2 Customer 3 100% of people who purchased milk also purchased bread ??? Customer n 5
1. Mẫu phổ biến (Frequent Pattern) - Mẫu phổ biến: là mẫu (tập các item, chuỗi con, cấu trúc con, đồ thị con, ….) xuất hiện thường xuyên trong tập dữ liệu [Agrawal, 1993]’ - Mục đích: Tìm các hiện tượng thường Customer 1 Customer 2 Customer 3 xuyên xảy ra trong dữ liệu - Ứng dụng: • Phân tích CSDL bán hàng Customer n • Quảng cáo, thiết kế catalog, phân tích chiến dịch bán hàng, Web log, chuỗi DNA, … 6
1. Mẫu phổ biến (Frequent Pattern) - Bài toán khai thác tập phổ biến: bài toán quan trọng trong KTDL: tìm ra tính chất ẩn, quan trọng của tập dữ liệu - Là nền tảng cho nhiều nhiệm vụ KTDL khác: • Phân tích luật kết hợp, mối tương quan • Mẫu tuần tự, cấu trúc. VD: đồ thị con • Phân tích dữ liệu không gian, đa phương tiện, phụ thuộc thời gian • Phân lớp dựa trên luật kết hợp • Gom cụm dựa trên mẫu phổ biến • … 7
2. CSDL giao dịch (Transaction database) Tid Items bought - Hạng mục (Item): mặt hàng, thuộc 10 Beer, Nuts, Diaper tính 20 Beer, Coffee, Diaper - Tập các hạng mục (itemset) 30 Beer, Diaper, Eggs 𝐼 = 𝑖! , 𝑖" , … , 𝑖# 40 Nuts, Eggs, Milk Nuts, Coffee, Diaper, - Tập k hạng mục (k-itemset) 50 Eggs, Milk 𝑋 = 𝑥! , 𝑥" , … , 𝑥$ 8
2. CSDL giao dịch (Transaction database) Tid Items bought - Giao dịch (transaction): tập các 10 Beer, Nuts, Diaper item mua trong 1 giỏ. 20 Beer, Coffee, Diaper - Giao dịch t: tập các item, t ⊆ 𝐼 30 Beer, Diaper, Eggs - CSDL giao dịch: tập các t 40 Nuts, Eggs, Milk Nuts, Coffee, Diaper, 𝐷 = 𝑡! , 𝑡" , … , 𝑡% 50 Eggs, Milk 𝑡& = 𝑖&! , 𝑖&" , … , 𝑖&$ 𝑣ới 𝑖&' ∈ 𝐼 9
2. CSDL giao dịch (Transaction database) Tid Items bought Tid A B C D E 1 Milk, Bread, Eggs 1 1 1 0 0 1 2 Bread, Sugar 2 0 1 0 1 0 3 Bread, Cereal Biến đổi CSDL về 3 0 1 1 0 0 dạng nhị phân 4 Milk, Bread, Sugar 4 1 1 0 1 0 5 Milk, Cereal 5 1 0 1 0 0 Items: 6 Bread, Cereal A = Milk 6 0 1 1 0 0 B = Bread 7 Milk, Cereal C = Cereal 7 1 0 1 0 0 8 Milk, Bread, Cereal, Eggs D = Sugar 8 1 1 1 0 1 E = Eggs 9 Milk, Bread, Cereal 9 1 1 1 0 0 10
3. Độ phổ biến và tập phổ biến - Độ phổ biến (supp) của tập các item X trong CSDL D: 𝐶𝑜𝑢𝑛𝑡 𝑋 𝐶𝑜𝑢𝑛𝑡 𝑋 : số các giao dịch chứa X 𝑆𝑢𝑝𝑝 𝑋 = (1) 𝐷 𝐷 : tổng số các giao dịch có trong D - Tập phổ biến S: tập các item có 𝑠𝑢𝑝𝑝 𝑆 ≥ 𝑚𝑖𝑛𝑠𝑢𝑝𝑝 𝑚𝑖𝑛𝑠𝑢𝑝𝑝: độ phổ biến tối thiểu (do người dùng xác định) - Tính chất tập phổ biến: Tất cả các tập con của tập phổ biến đều là tập phổ biến 11
3. Độ phổ biến và tập phổ biến VD1: I = {Beer, Bread, Jelly, Milk, Butter}, Minsupp = 60% Tính độ phổ biến và xác định các tập sau có phải là tập phổ biến? - X1 = {Bread, Butter} Count (X1) = 3, |D|= 5 Tid Items → supp(X) = 60% ≥ minsupp t1 Bread, Jelly, Butter → X1 là tập phổ biến t2 Bread, Butter - X2 = {Bread} t3 Bread, Milk, Butter - X3 = {Butter} t4 Beer, Bread - X4 = {Milk} t5 Beer, Jelly - X5 = {Milk Bread} 12
4. Tập phổ biến tối đại (Max-Pattern) - X là tập phổ biến tối đại: • X là tập phổ biến • Và không tồn tại tập phổ biến nào bao nó - VD2: Minsupp = 2 Tid Items t1 A, B, C, D, E • {B, C, D, E}: tập phổ biến tối đại t2 B, C, D, E • {A, C, D}: tập phổ biến tối đại t3 A, C, D, F • {B, C, D}: không là tập phổ biến tối đại (Bayardo – SIGMOD’98) 13
5. Tập phổ biến đóng (Close-Pattern) - X là tập phổ biến đóng: • X là tập phổ biến • Và không tồn tại tập nào bao nó cùng độ phổ biến với nó - VD3: Minsupp = 2 Tid Items t1 A, B, C • {A, B}: tập phổ biến đóng t2 A, B, C • {A, B, D}: tập phổ biến đóng t3 A, B, D • {A, B, C}: tập phổ biến đóng t4 A, B, D Pasquier, ICDT’99 t5 C, E, F 14
6. Luật kết hợp (Association Rules) - Có dạng: X → Y với X, Y ⊂ I và X ∩ Y = {} - Được đánh giá dựa trên 2 độ đo: • Độ phổ biến (support) 𝑠𝑢𝑝𝑝 𝑋 → 𝑌 = 𝑃 𝑋 ∪ 𝑌 = 𝑠𝑢𝑝𝑝(𝑋 ∪ 𝑌) (2) • Độ tin cậy (confidence) 𝑃 𝑋∪ 𝑌 𝑠𝑢𝑝𝑝(𝑋 ∪ 𝑌) 𝑐𝑜𝑛𝑓 𝑋 → 𝑌 = 𝑃 𝑌 | 𝑋 = = (3) 𝑃 𝑋 𝑠𝑢𝑝𝑝 𝑋 - VD: Bread → Butter (supp = 60%, conf = 75%) 15
7. Bài toán khám phá Luật kết hợp - Cho minsupp và minconf (do người dùng xác định) - Cho tập items 𝐼 = 𝑖! , 𝑖" , … , 𝑖# và CSDL 𝐷 = 𝑡! , 𝑡" , … , 𝑡% với 𝑡& = 𝑖&! , 𝑖&" , … , 𝑖&$ và 𝑖&' ∈ 𝐼 - Bài toán khám phá Luật kết hợp: tìm tất cả các luật X → Y (X, Y ⊂ I và X ∩ Y = {}) thỏa mãn cả 2: • supp (X → Y) ≥ minsupp • conf (X → Y) ≥ minconf 16
7. Bài toán khám phá Luật kết hợp Các bước khám phá Luật kết hợp: - B1: Tìm tất cả các tập phổ biến (thỏa minsupp) - B2: Xây dựng luật từ các tập phổ biến • Với mỗi tập phổ biến S: tìm tập con khác rỗng của S • Với mỗi tập tập con khác rỗng A của S: Luật A → (S – A) là luật kết hợp khi: 𝑠𝑢𝑝𝑝 𝑆 𝑐𝑜𝑛𝑓 𝐴 → 𝑆 – 𝐴 = ≥ 𝑚𝑖𝑛𝑐𝑜𝑛𝑓 𝑠𝑢𝑝𝑝 𝐴 17
7. Bài toán khám phá Luật kết hợp VD4: Tid Items Minsupp = 50%, Minconf = 80% t1 A, B, C Tập phổ biến Supp t2 A, C A 75% t3 A, D B 50% t4 B, E, F C 50% - Luật A → C: A, C 50% supp (A → C) = supp ({A} ∪ {C}) = 50% conf (A → C) = supp ({A} ∪ {C}) / supp ({A}) = 66.6% (Loại) - Luật C → A: supp (C → A) = supp ({C} ∪ {A}) = 50% conf (C → A) = supp ({C} ∪ {A}) / supp ({C}) = 100% (Thỏa) 18
7. Bài toán khám phá Luật kết hợp - Đưa về bài toán tìm tập phổ biến. - Độ phức tạp tính toán cao - Một số thuật toán: • Tìm kiếm theo chiều rộng: Thuật toán Apriori (Agrawal & Srikant @VLDB’94) • Phát triển mẫu: FP-Growth (Han, Pei & Yin @SIGMOD’00) • Tìm kiếm theo dạng dữ liệu dọc: Thuật toán Charm (Zaki & Hsiao @SDM’02) , ECLAT (Zaki et al. @KDD’97) 19
1. Cách tiếp cận 2. Các bước thực hiện Thuật toán Apriori 3. Mã giả 4. Thách thức và cải tiến 20