Bài giảng Khai phá dữ liệu: Chương 2 - Phan Mạnh Thường

Mục tiêu cơ bản của chương 2 Luật kết hợp (Association Rules) thuộc bài giảng Khai phá dữ liệu trình bày về khái niệm cơ bản về luật kết hợp, thuật toán Apriori, tìm tập phổ biến tối đại với FP-Tree, phân loại luật kết hợp và tối ưu tập luật.
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá dữ liệu: Chương 2 - Phan Mạnh Thường Chương 2 LUẬT KẾT HỢP (Association Rules) Nội dung 1 Khái niệm cơ bản 2 Thuật toán Apriori 3 Tìm tập phổ biến tối đại với FP-Tree 4 Phân loại luật kết hợp 5 Tối ưu tập luật Các khái niệm cơ bản Bài toán phân tích giỏ hàng  Phân tích thói quen mua hàng của khách hàng bằng cách tìm ra những “mối kết hợp” giữa những mặt hàng mà khách đã mua  Mục tiêu giúp gia tăng doanh số, tạo thuận lợi cho khách khi mua hàng trong siêu thị  Bài toán được Agrawal thuộc nhóm nghiên cứu của IBM đưa ra vào năm 1994 7/12/2014 www.lhu.edu.vn Các khái niệm cơ bản Luật kết hợp  Khai phá luật kết hợp:  Tìm tần số mẫu, mối kết hợp, sự tương quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác.  Tính hiểu được: dễ hiểu  Tính sử dụng được: Cung cấp thông tin thiết thực  Tính hiệu quả: Đã có những thuật toán khai thác hiệu quả  Các ứng dụng:  Phân tích bán hàng trong siêu thị, cross-marketing, thiết kế catalog, loss-leader analysis, gom cụm, phân lớp, ... 7/12/2014 www.lhu.edu.vn Các khái niệm cơ bản Luật kết hợp  Định dạng thể hiện đặc trưng cho các luật kết hợp:  khăn  bia [0.5%, 60%]  mua:khăn  mua:bia [0.5%, 60%]  “Nếu mua khăn thì mua bia trong 60% trường hợp. Khăn và bia được mua chung trong 0.5% dòng dữ liệu.  Các biểu diễn khác:  mua(x, “khăn)  mua(x, “bia) [0.5%, 60%]  khoa(x, CS) ^ học(x, DB)  điểm(x, A) [1%, 75%] Các khái niệm cơ bản Luật kết hợp khăn  bia [0.5%, 60%] “NẾU mua khăn THÌ mua bia trong 60% trường hợp 1 2 3 4 trên 0.5% số dòng dữ liệu 1 Tiền đề, vế trái luật 2 Mệnh đề kết quả, vế phải luật 3 Support, tần số, độ hỗ trợ (“trong bao nhiêu phần trăm dữ liệu thì những điều ở vế trái và vế phải cùng xảy ra) 4 Confidence, độ mạnh, độ tin cậy (“nếu vế trái xảy ra thì có bao nhiêu khả năng vế phải xảy ra) Các khái niệm cơ bản Luật kết hợp • Độ ủng hộ: biểu thị tần số luật có trong các giao tác. support(A  B [ s, c ]) = p(AB) = support ({A,B}) • Độ tin cậy: biểu thị số phần trăm giao tác có chứa luôn B trong số những giao tác có chứa A. confidence(A  B [ s, c ]) = p(B|A) = p(AB) / p(A) = support({A,B}) / support({A}) Các khái niệm cơ bản Luật kết hợp  Độ hỗ trợ tối thiểu  : (minsupp)  Cao  ít tập phần tử (itemset) phổ biến  ít luật hợp lệ rất thường xuất hiện  Thấp  nhiều luật hợp lệ hiếm xuất hiện  Độ tin cậy tối thiểu  : (minconf)  Cao  ít luật nhưng tất cả “gần như đúng  Thấp  nhiều luật, phần lớn rất “không chắc chắn  Giá trị tiêu biểu:  = 2 -10 %,  = 70 - 90 % Các khái niệm cơ bản Luật kết hợp  Giao tác:  Dạng quan hệ Dạng kết  Item và itemsets: phần tử đơn lẻ và tập phần tử  Support của tập I: số lượng giao tác có chứa I  Min Support : ngưỡng cho support  Tập phần tử phổ biến: có độ ủng hộ (support)   Các khái niệm cơ bản Ví dụ  Cho: (1) CSDL các giao tác, (2) mỗi giao tác là một danh sách mặt hàng được mua (trong một lượt mua của khách hàng) Frequent item sets ID của giao tác Hàng mua Tập phổ biến support 100 A,B,C {A} 3 or 75% 200 A,C {B} và {C} 2 or 50% 400 A,D {D}, {E} và {F} 1 or 25% 500 B,E,F {A,C} 2 or 50% Các cặp khác max 25%  Tìm: tất cả luật có support >= minsupport  If min. support 50% and min. confidence 50%, then A  C [50%, 66.6%], C  A [50%, 100%] Khai phá luật kết hợp  Quá trình hai buớc để khai phá luật kết hợp: BƯỚC 1: Tìm các tập phổ biến: các tập các phần tử có độ support tối thiểu.  Mẹo Apriori: Tập con của tập phổ biến cũng là một tập phổ biến: • ví dụ, nếu {AB} là một tập phổ biến thì cả {A} và {B} đều là những tập phổ biến  Lặp việc tìm tập phổ biến với kích thước từ 1 đến k (tập có kích thước k) BƯỚC 2: Dùng các tập phổ biến để tạo các luật kết hợp.Rakesh Agrawal, 1993 Thuật toán Apriori  Bước kết hợp: Ck được tạo bằng cách kết Lk -1 với chính nó  Bước rút gọn: Những tập kích thước (k-1) không phổ biến không thể là tập con của tập phổ biến kích thước k  Mã giả: Ck : Tập ứng viên có kích thước k; Lk : Tập phổ biến có kích thước k L1 = {các phần tử phổ biến}; for (k = 1; Lk !=; k++) do begin Ck +1 = {các ứng viên được tạo từ Lk }; for each giao tác t trong database do tăng số đếm của tất cả các ứng viên trong Ck+1 mà được chứa trong t Lk +1 = {các ứng viên trong Ck +1 có độ ủng hộ tối tiểu} end return k Lk ; Thuật toán Apriori  Nguyên tắc Apriori: Những tập con của tập phổ biến cũng phải phổ biến  L3={abc, abd, acd, ace, bcd}  Tự kết: L3*L3  abcd từ abc và abd  acde từ acd và ace  Rút gọn:  acde bị loại vì ade không có trong L3  C4={abcd} Thuật toán Apriori Ví dụ Database D C1 L1 ...