intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

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

Thêm vào BST
Báo xấu
148
lượt xem 31
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

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 phá dữ liệu: Chương 2 - Phan Mạnh Thường

  1. 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
  2. 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
  3. 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
  4. 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%]
  5. 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")
  6. 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})
  7. 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 %
  8. 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)  
  9. 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%]
  10. 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
  11. 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 ;
  12. 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}
  13. Thuật toán Apriori Ví dụ Database D C1 L1 Tập Độ ủng hộ ID giao tác Phần tử Tập Độ ủng hộ {1} 2 100 1 34 {1} 2 200 2 35 Duyệt D {2} 3 {2} 3 {3} 3 300 1 235 {3} 3 {4} 1 400 2 5 {5} 3 {5} 3
  14. Thuật toán Apriori Ví dụ C2 C2 L2 Tập Tập Độ ủng hộ {1 2} {1 2} 1 Tập Độ ủng hộ {1 3} {1 3} 2 {1 3} 2 Duyệt D {1 5} {1 5} 1 {2 3} 2 {2 3} {2 3} 2 {2 5} 3 {2 5} {2 5} 3 {3 5} 2 {3 5} {3 5} 2
  15. Thuật toán Apriori Ví dụ C3 L3 Tập Duyệt D Tập Độ ủng hộ {2 3 5} {2 3 5} 2
  16. Thuật toán Apriori Ví dụ Không gian tìm 12345 kiếm của CSDL D 1234 1235 1245 1345 2345 123 124 125 134 135 145 234 235 245 345 12 13 14 15 23 24 25 34 35 45 1 2 3 4 5
  17. Thuật toán Apriori Ví dụ Áp dụng mẹo 12345 Apriori trên Cấp 1 1234 1235 1245 1345 2345 123 124 125 134 135 145 234 235 245 345 12 13 14 15 23 24 25 34 35 45 1 2 3 4 5
  18. Thuật toán Apriori Ví dụ Áp dụng mẹo 12345 Apriori trên Cấp 2 1234 1235 1245 1345 2345 123 124 125 134 135 145 234 235 245 345 12 13 14 15 23 24 25 34 35 45 1 2 3 4 5
  19. Tập phổ biến tối đại ( maximal frequent sets).  Tập phổ biến (frequent sets)  Tập phổ biến tối đại ( maximal frequent sets).  Định nghĩa: M là tập phổ biến tối đại nếu M là tập phổ biến và không tồn tại tập phổ biến S khác M mà M  S
  20. Thuật toán Apriori  Phần cốt lõi của thuật toán Apriori: FP tree  Dùng các tập phổ biến kích thước (k – 1) để tạo các tập phổ biến kích thước k ứng viên  Duyệt CSDL và đối sánh mẫu để đếm số lần xuất hiện của các tập ứng viên trong các giao tác  Tình trạng nghẽn cổ chai của thuật toán Apriori: việc tạo ứng viên  Các tập ứng viên đồ sộ: • 104 tập phổ biến kích thước 1 sẽ tạo ra 107 tập ứng viên kích thước 2 • Để phát hiện một mẫu phổ biến kích thước 100, ví dụ {a1, a2, …, a100}, cần tạo 2100  1030 ứng viên.  Duyệt CSDL nhiều lần: • Cần duyệt (n +1 ) lần, n là chiều dài của mẫu dài nhất
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2