›
›

Bài giảng Khai phá dữ liệu - Chương 2: Luật kết hợp

pdf 52 trang ngocly 30
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Khai phá dữ liệu - Chương 2: Luật kết hợp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_khai_pha_du_lieu_chuong_2_luat_ket_hop.pdf

Nội dung text: Bài giảng Khai phá dữ liệu - Chương 2: Luật kết hợp

  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ử {1} 2 Tập Độ ủng hộ 100 1 3 4 {1} 2 {2} 3 200 2 3 5 Duyệt D {2} 3 {3} 3 300 1 2 3 5 {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} 3 {2 5} {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ụ 100 30 {a1, a2, , a100}, cần tạo 2 10 ứ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
  21. Thuật toán Apriori Hạn chế của thuật toán Apriori . Thực tế: . Đối với tiếp cận Apriori căn bản thì số lượng thuộc tính trên dòng thường khó hơn nhiều so với số lượng dòng giao tác. . Ví dụ: • 50 thuộc tính mỗi cái có 1-3 giá trị, 100.000 dòng (không quá tệ) • 50 thuộc tính mỗi cái có 10-100 giá trị, 100.000 dòng (hơi tệ) • 10.000 thuộc tính mỗi cái có 5-10 giá trị, 100 dòng (quá tệ ) . Lưu ý: • Một thuộc tính có thể có một vài giá trị khác nhau • Các thuật toán luật kết hợp có đặc trưng là xem một cặp thuộc tính-giá trị là một thuộc tính (2 thuộc tính mỗi cái có 5 giá trị => "10 thuộc tính") . Cách khắc phục vấn đề ?
  22. Thuật toán FP-Tree . Ý tưởng: Dùng đệ quy để gia tăng độ dài của mẫu phổ biến dựa trên cây FFP và các mẫu được phân hoạch . Phương pháp thực hiện: . Với mỗi item phổ biến trong Header Table, xây dựng cơ sở điều kiện và cây điều kiện của nó . Lặp lại tiến trình trên với mỗi cây điều kiện mới được tạo ra . Cho tới khi cây điều kiện được tạo ra là cây rỗng hoặc chỉ bao gồm một đường đi đơn thì ngừng. Mỗi tổ hợp con các item trên đường đi đơn được tạo ra sẽ là một tập phổ biến
  23. Thuật toán FP-Tree Các bước xây dựng cây FP-Tree . Bước 1: Duyệt CSDL, xác định tập F các item phổ biến một phần tử, sau đó loại bỏ các Item không thoả ngưỡng minsup. Sắp xếp các item trong tập F theo thứ tự giảm dần của độ phổ biến, ta được tập kết quả là L. . Bước 2: Tạo nút gốc cho cây T, và tên của nút gốc sẽ là Null. Sau đó duyệt CSDL lần thứ hai. Ứng với mỗi giao tác trong CSDL ta thực hiện 2 công việc sau: . Chọn các item phổ biến trong các giao tác và sắp xếp chúng theo thứ tự giảm dần độ phổ biến trong tập L . Gọi hàm Insert_tree([p|P],T) để đưa các item vào trong cây T
  24. Thuật toán FP-Tree Xây dựng cây FP-Tree
  25. Thuật toán FP-Tree null Thêm TID=1 vào cây: B:1 TID Items 1 {A,B} 2 {B,C,D} A:1 3 {A,C,D,E} 4 {A,D,E} Thêm TID=2 vào cây: 5 {A,B,C} null 6 {A,B,C,D} 7 {B,C} B:2 8 {A,B,C} C:1 9 {A,B,D} A:1 10 {B,C,E} D:1
  26. Thuật toán FP-Tree TID Items Transaction 1 {A,B} Database null 2 {B,C,D} 3 {A,C,D,E} B:8 A:2 4 {A,D,E} 5 {A,B,C} 6 {A,B,C,D} A:5 C:3 C:1 D:1 7 {B,C} 8 {A,B,C} 9 {A,B,D} C:3 D:1 D:1 E:1 D:1 E:1 10 {B,C,E} Header table D:1 E:1 B 8 A 7 C 7 Sau khi thêm các giao tác vào, ta được cây như hình trên D 5 Dựa trên cây, ta lập bảng header để tạo liên kết E 3 giữa các node có cùng item
  27. Thuật toán FP-Tree null B:8 A:2 A:5 C:3 C:1 D:1 C:3 D:1 D:1 E:1 D:1 E:1 null D:1 E:1 B:1 A:2 C:1 C:1 D:1 E:1 D:1 E:1 Những giao tác có bao gồm item E E:1
  28. Thuật toán FP-Tree null (New) Header table Cây điều kiện A 2 cho item E B:1 A:2 C 2 D 2 C:1 C:1 D:1 null Item B bị loại C:1 A:2 E:1 D:1 E:1 bỏ do support(B)=1 nhỏ hơn C:1 D:1 E:1 minsup=2. Với mỗi nhánh cây bao gồm E. D:1 • Loại bỏ E • Thêm vào cây mới • Xây dựng lại bảng Header cho cây Tiếp tục thực hiện đệ quy các mới thao tác cho đến khi trên cây chỉ còn một đường đi đơn Item phổ biến: E(3)
  29. Thuật toán FP-Tree (New) Header table null Cây điều kiện cho A 2 tập item DE A:2 null C:1 D:1 A:2 D:1 Các tập phổ biến sau khi kết thúc tiến trình đệ quy do cây chỉ còn một đường đi Tập các đường đi bắt đầu với E và kết thúc với D. Tập phổ biến: DE(2), ADE(2) Lần lượt thêm từng đường dẫn vào cây mới sau khi đã loại bỏ D
  30. Thuật toán FP-Tree null (New) Header table C:1 A:1 C:1 null D:1 Kết thúc quá trình đệ quy do cây rỗng. Tập phổ biến: CE(2) Tập các đường dẫn bắt đầu từ E và kết thúc với C. Thêm lần lượt từng nhánh vào cây mới (sau khi đã loại bỏ C)
  31. Thuật toán FP-Tree (New) Header table null null A:2 Quá trình đệ quy kết thúc do cây rỗng. Tập phổ biến: AE(2) Tập các đường đi bắt đầu từ E và kết thúc với A. Thêm lần lượt từng đường đi vào cây mới (sau khi loại bỏ A).
  32. Thuật toán FP-Tree Procedure FFP-growth(Tree, α) { (1) Nếu Tree có chứa một đường đi đơn P (2) Thì với mỗi cách kết hợp  của các nút trong đường đi P thực hiện (3) phát sinh tập mẫu Uα, support = min(support của các nút trong ); (4) ngược lại ứng với mỗi Ai trong thành phần của Tree thực hiện { (5) - phát sinh tập mẫu β=AiUα với độ phổ biến support = Ai.support; (6) - xây dựng cơ sở điều kiện cho β và sau đó xây dựng cây FP Treeβ theo điều kiện của β; (7) - Nếu Treeβ ≠  (8) thì gọi lại hàm FFP-growth(Treeβ, β) } }
  33. Tạo luật kết hợp từ tập phổ biến . Mã giả: for mỗi tập phổ biến l tạo tất cả các tập con khác rỗng s of l for mỗi tập con khác rỗng s of l cho ra luật "s (l-s)" nếu support(l)/support(s) min_conf", trong đó min_conf là ngưỡng độ tin cậy tối thiểu • Ví dụ: tập phổ biến l = {abc}, subsets s = {a, b, c, ab, ac, bc) – a b, a c, b c – a bc, b ac, c ab – ab c, ac b, bc a
  34. Tạo luật kết hợp từ tập phổ biến . Ghi nhớ 1: . Tạo các tập phổ biến thì chậm (đặc biệt là các tập kích thước 2) . Tạo các luật kết hợp từ các tập phổ biến thì nhanh . Ghi nhớ 2: . Khi tạo các tập phổ biến, ngưỡng độ ủng hộ được sử dụng . Khi tạo luật kết hợp, ngưỡng độ tin cậy được sử dụng . Thực tế, việc tạo các tập phổ biến và tạo các luật kết hợp thật sự chiếm thời gian bao lâu? . Xét một ví dụ nhỏ trong thực tế . Các thử nghiệm được thực hiện với Pentium IV 2GHz, có bộ nhớ chính 512 MB & Windows Server 2003
  35. Tối ưu tập luật Chọn những luật tốt nhất . Tập kết quả thường rất lớn, cần chọn ra những luật tốt nhất dựa trên: . Các độ đo khách quan: Hai các đo phổ biến:  support; và confidence . Các độ đo chủ quan (Silberschatz & Tuzhilin, KDD95) Một luật (mẫu) là tốt nếu  gây bất ngờ (gây ngạc nhiên cho user); và/hoặc có thể hoạt động (user có thể dùng nó để làm gì đó) . Những kết quả này sẽ được dùng trong các quá trình khám phá tri thức (KDD)
  36. Một số dạng luật kết hợp Luật kết hợp Boolean và định lượng . Luật kết hợp Boolean so với định lượng (tùy vào loại giá trị được dùng) . Boolean: Luật liên quan đến mối kết hợp giữa sự có xuất hiện và không xuất hiện của các phần tử (ví dụ “có mua A" hoặc “không có mua A") mua=SQLServer, mua=DMBook mua=DBMiner [2%,60%] mua(x, "SQLServer") ^ mua(x, "DMBook") mua(x, "DBMiner") [0.2%, 60%] . Định lượng: Luật liên quan đến mối kết hợp giữa các phần tử hay thuộc tính định lượng tuổi=30 39, thu nhập=42 48K mua=PC [1%, 75%] tuổi(x, "30 39") ^ thu nhập(x, "42 48K")  mua(x, "PC") [1%, 75%]
  37. Một số dạng luật kết hợp Luật kết hợp Boolean và định lượng • Các thuộc tính định lượng: ví dụ: tuổi, thu nhập, chiều cao, cân nặng • Các thuộc tính phân loại: ví dụ: màu sắc của xe CID chieu cao can nang thu nhap 1 168 75,4 30,5 2 175 80,0 20,3 3 174 70,3 25,8 4 170 65,2 27,0 Vấn đề: có quá nhiều giá trị khác nhau cho các thuộc tính định lượng Giải pháp: chuyển các thuộc tính định lượng sang các thuộc tính phân loại (chuyển qua không gian rời rạc)
  38. Một số dạng luật kết hợp Luật kết hợp nhiều chiều . Các mối kết hợp một chiều và nhiều chiều . Một chiều: Các thuộc tính hoặc tập thuộc tính trong luật chỉ quy về một đại lượng (ví dụ, quy về “mua") Bia, khoai tây chiên bánh mì [0.4%, 52%] mua(x, “Bia") ^ mua(x, “Khoai tây chiên")  mua(x, “Bánh mì") [0.4%, 52%] . Nhiều chiều: Các thuộc tính hoặc thuộc tính trong luật được quy về hai hay nhiều đại lượng (ví dụ: “mua", “thời gian giao dịch", “loại khách hàng") Trong ví dụ sau là: quốc gia, tuổi, thu nhập
  39. Một số dạng luật kết hợp Luật kết hợp nhiều chiều CID quoc gia tuoi thu nhap 1 Ý 50 thap 2 Pháp 40 cao 3 Pháp 30 cao 4 Ý 50 trung bình 5 Ý 45 cao 6 Pháp 35 cao CÁC LUẬT: quốc gia = Pháp thu nhập = cao [50%, 100%] thu nhập = cao quốc gia = Pháp [50%, 75%] tuổi = 50 quốc gia = Ý [33%, 100%]
  40. Một số dạng luật kết hợp Luật kết hợp nhiều cấp . Các mối kết hợp một cấp và nhiều cấp . Một cấp: Mối kết hợp giữa các phần tử hay thuộc tính của cùng một cấp khái niệm (ví dụ cùng một cấp của hệ thống phân cấp) Bia, Khoai tây chiên Bánh mì [0.4%, 52%] . Nhiều cấp: Mối kết hợp giữa các phần tử hay thuộc tính của nhiều cấp khái niệm khác nhau (ví dụ nhiều cấp của hệ thống phân cấp) Bia:Karjala, Khoai tây chiên:Estrella:Barbeque Bánh mì [0.1%, 74%]
  41. Một số dạng luật kết hợp Luật kết hợp nhiều cấp . Khó tìm những mẫu tốt ở cấp quá gần gốc . độ ủng hộ cao = quá ít luật . độ ủng hộ thấp = quá nhiều luật, không tốt nhất . Tiếp cận: suy luận ở cấp khái niệm phù hợp . Một dạng phổ biến của tri thức nền là một thuộc tính có thể được tổng quát hóa hay chi tiết hóa dựa vào cây khái niệm . Các luật kết hợp nhiều cấp: những luật phối hợp các mối kết hợp với cây các khái niệm
  42. Một số dạng luật kết hợp Luật kết hợp nhiều cấp . Các phần tử thường tạo thành các cây phân cấp . Các phần tử ở cấp thấp Thực phẩm hơn được cho là có độ ủng hộ thấp hơn sữa bánh mì . Các luật về các tập ở các cấp thích hợp sẽ sữa không béo 2% lúa mì trắng khá hữu ích . CSDL giao tác có thể Vinamilk Yomost được mã hóa dựa trên các chiều và các cấp
  43. Một số dạng luật kết hợp Luật kết hợp nhiều cấp ID giao tác Mat hang T1 {111, 121, 211, 221} Thực phẩm T2 {111, 211, 222, 323} 1 2 T3 {112, 122, 221, 411} T4 {111, 121} sữa bánh mì T5 {111, 122, 211, 221, 1 2 1 2 413} sữa không béo 2% lúa mì trắng 1 2 Vinamilk Yomost 121= sữa - 2% - Vinamilk
  44. Một số dạng luật kết hợp Luật kết hợp nhiều cấp . Tiếp cận trên-xuống, tiến theo chiều sâu: . Trước tiên tìm những luật mạnh ở cấp cao: sữa bánh mì [20%, 60%] . Sau đó tìm những luật “yếu hơn” ở cấp thấp hơn của chúng: sữa 2% bánh mì lúa mì [6%, 50%] . Khai thác thay đổi trên các luật kết hợp nhiều cấp: . Các luật kết hợp trên nhiều cấp khác nhau: sữa bánh mì lúa mì . Các luật kết hợp với nhiều cây khái niệm: sữa bánh mì Wonder
  45. Một số dạng luật kết hợp Luật kết hợp nhiều cấp . Tổng quát hóa/chuyên biệt hóa giá trị của các thuộc tính . từ chuyên biệt sang tổng quát: support của các luật tăng (có thêm những luật mới hợp lệ) . từ tổng quát sang chuyên biệt: support của các luật giảm (có những luật trở thành không hợp lệ, độ ủng hộ của chúng giảm xuống nhỏ hơn ngưỡng qui định) . Bậc quá thấp => quá nhiều luật và quá thô sơ Pepsi light 0.5l bottle Taffel Barbeque Chips 200gr . Bậc quá cao => các luật không hay Food Clothes
  46. Tối ưu tập luật Lọc bỏ luật thừa . Có những luật có thể là dư thừa do đã có các mối quan hệ “tổ tiên” giữa các phần tử . Ví dụ (sữa có 4 lớp con): . sữa bánh mì lúa mì [support= 8%, conf = 70%] . sữa 2% bánh mì lúa mì [support = 2%, conf = 72%] . Ta nói luật thứ nhất là tổ tiên của luật thứ hai . Một luật là dư thừa nếu độ ủng hộ của nó gần với giá trị “mong đợi”, dựa trên tổ tiên của luật . Luật thứ hai ở trên có thể là dư thừa
  47. Tối ưu tập luật Khai phá luật dựa trên ràng buộc . Khai thác cả giga-byte dữ liệu theo cách thăm dò, có tương tác? . Điều này có khả thi không? - Bằng cách sử dụng tốt các ràng buộc! . Các loại ràng buộc nào có thể dùng trong khai thác dữ liệu? . Ràng buộc dạng tri thức: phân lớp, kết hợp, . . Ràng buộc dữ liệu: những câu truy vấn dạng SQL • Tìm những cặp sản phẩm được bán chung tại VanCouver tháng 12/98 . Những ràng buộc về kích thước/cấp bậc: • Có liên quan về vùng, giá, nhãn hiệu, loại khách hàng . Những ràng buộc về sự hấp dẫn: • Những luật mạnh (min_support 3%, min_confidence 60%)
  48. Tối ưu tập luật Ràng buộc luật . Có hai loại ràng buộc luật: . Ràng buộc dạng luật: khai thác theo siêu luật (meta-rule) • Metarule: P(X, Y) ^ Q(X, W) lấy(X, "database systems") • Luật đối sánh: tuổi(X, "30 39") ^ thu nhập(X, "41K 60K") lấy(X, "database systems"). . Ràng buộc trên nội dung luật: tạo câu truy vấn dựa trên ràng buộc (Ng, et al., SIGMOD’98) • sum(LHS) 20 ^ count(LHS) > 3 ^ sum(RHS) > 1000
  49. Tối ưu tập luật Ràng buộc luật . Ràng buộc 1-biến và ràng buộc 2-biến (Lakshmanan, et al. SIGMOD’99): . 1-biến: Ràng buộc chỉ hạn chế trên một bên (L/R) của luật, ví dụ; • sum(LHS) 20 ^ count(LHS) > 3 ^ sum(RHS) > 1000 . 2-biến: Ràng buộc hạn chế trên cả hai bên (L và R) của luật. • sum(LHS) < min(RHS) ^ max(RHS) < 5* sum(LHS)
  50. Tối ưu tập luật Tóm tắt . Khai thác luật kết hợp: . Quan trọng nhất trong KDD . Khái niệm khá đơn giản nhưng ý tưởng của nó cung cấp cơ sở cho những mở rộng và những phương pháp khác . Nhiều bài báo đã được công bố về đề tài này . Đã có nhiều kết quả hấp dẫn . Hướng nghiên cứu lý thú: . Phân tích mối kết hợp trong các dạng dữ liệu khác: dữ liệu không gian, dữ liệu đa phương tiện, dữ liệu thời gian thực,
  51. Tối ưu tập luật Bài tập lý thuyết TID Items 100 ACEG 200 ABCDH 300 ABCD 400 ACDE 500 ABCF 600 ADEH 700 ABCDF 800 CDEG 900 ACDF . Sử dụng thuật toán Apriori . Tìm các tập phổ biến có ngưỡng MinSup=30% . Tìm các luật kết hợp có ngưỡng MinSup=30% và MinConf >= 70%
  52. Tối ưu tập luật Bài tập lý thuyết TID Items 100 f,a,b,d,g,i,m,p 200 a,b,c,f,l,m,o 300 a,c,h,j,o 400 b,c,k,s,p 500 a,f,b,c,l,p,m,n . Sử dụng thuật toán FP-TREE . Tìm các tập phổ biến có ngưỡng MinSup=3 . Tìm các luật kết hợp có ngưỡng MinSup=3 và MinConf >= 70%