›
›

Lập trình hướng đối tượng - Chương 4: Khai phá luật kết hợp

ppt 73 trang vanle 2010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Lập trình hướng đối tượng - Chương 4: Khai phá 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:

  • pptlap_trinh_huong_doi_tuong_chuong_4_khai_pha_luat_ket_hop.ppt

Nội dung text: Lập trình hướng đối tượng - Chương 4: Khai phá luật kết hợp

  1. Chương 4: Khai phá luật kết hợp Dựa theo “Data Mining: Concepts and Techniques” Chapter 6. Mining Association Rules in Large Databases ©Jiawei Han and Micheline Kamber www.cs.uiuc.edu/~hanj June 20, 2021 1
  2. Chương 4: Khai phá luật kết hợp ◼ Khai phá luật kết hợp (Association rule) ◼ Các thuật tốn khai phá vơ hướng luật kết hợp (giá trị lơgic đơn chiều) trong CSDL giao dịch ◼ Khai phá kiểu đa dạng luật kết hợp/tương quan ◼ Khai phá kết hợp dựa theo ràng buộc ◼ Khai phá mẫu dãy June 20, 2021 2
  3. Khái niệm cơ sở: Tập phổ biến và luật kết hợp Một số ví dụ về “luật kết hợp” (associate rule) • “98% khách hàng mà mua tạp chí thể thao thì đều mua các tạp chí về ơtơ”  sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ơtơ” • “60% khách hàng mà mua bia tại siêu thị thì đều mua bỉm trẻ em”  sự kết hợp giữa “bia” với “bỉm trẻ em” • “Cĩ tới 70% người truy nhập Web vào địa chỉ Url 1 thì cũng vào địa chỉ Url 2 trong một phiên truy nhập web”  sự kết hợp giữa “Url 1” với “Url 2”. Khai phá dữ liệu sử dụng Web (Dữ liệu từ file log của các site, chẳng hạn được MS cung cấp). • Các Url cĩ gắn với nhãn “lớp” là các đặc trưng thì cĩ luật kết hợp liên quan giữa các lớp Url này. June 20, 2021 3
  4. Khái niệm cơ sở: Tập phổ biến và luật kết hợp [IV06] Renáta Iváncsy, István Vajk (2006). Frequent Pattern Mining in Web Log Data, Acta Polytechnica Hungarica, 3(1):77-90, 2006 June 20, 2021 4
  5. Khái niệm cơ sở: Tập phổ biến và luật kết hợp Cơ sở dữ liệu giao dịch (transaction database) • Giao dịch: danh sách các mặt hàng (mục: item) trong một phiếu mua hàng của khách hàng. Giao dịch T là một tập mục. • Tập tồn bộ các mục I = {i1, i2, , ik} “tất cả các mặt hàng”. Một giao dịch T là một tập con của I: T  I. Mỗi giao dịch T cĩ một định danh là TID. • A là một tập mục A  I và T là một giao dịch: Gọi T chứa A nếu A  T. • Độ hỗ trợ của A (s(A)) là xác suất xuất hiện A trong D: s(A)=|T D, T  A} • minsup>0 (độ hỗ trợ tối thiểu), A là “phổ biến” ((frequent)): s(A) minsup • Luật kết hợp • Gọi A → B là một “luật kết hợp” nếu A  I, B  I và AB=. • Luật kết hợp A→B cĩ độ hỗ trợ (support): s (A→B) = s(AB), A→B là phổ biến nếu AB phổ biến. Luật kết hợp A → B cĩ độ tin cậy (confidence) c trong CSDL D nếu trong D cĩ c% các giao dịch T  A TB: xác suất P(B|A). • Support (A → B) = P(AB) : 1 s (A → B) 0 • Confidence (A → B) = P(B|A) : 1 c (A → B) 0 • Luật A → B được gọi là đảm bảo độ hỗ trợ s trong D nếu s(A → B) s. Luật A→B được gọi là đảm bảo độ tin cậy c trong D nếu c(A → B) c. Tập mạnh. June 20, 2021 5
  6. Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp ◼ Tập mục I={i1, , ik}. CSDL giao dịch D = {d  I} Transaction-id Items bought ◼ A, B  I, AB=: A→ B là luật kết hợp 10 A, B, C ◼ Bài tốn tìm luật kết hợp. 20 A, C Cho trước độ hỗ trợ tối thiểu s>0, độ 30 A, D tin cậy tối thiếu c>0. Hãy tìm mọi luật 40 B, E, F kết hợp mạnh X→Y. Giả sử min_support = 50%, Customer Customer buys both buys diaper min_conf = 50%: A → C (50%, 66.7%) C → A (50%, 100%) ◼ Hãy trình bày các nhận xét về khái niệm luật kết hợp với khái niệm phụ Customer thuộc hàm. buys beer ◼ Các tính chất Armstrong ở đây. June 20, 2021 6
  7. Một ví dụ tìm luật kết hợp Transaction-id Items bought Min. support 50% 10 A, B, C Min. confidence 50% 20 A, C Frequent pattern Support 30 A, D {A} 75% 40 B, E, F {B} 50% {C} 50% For rule A C: {A, C} 50% support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) = 66.6% June 20, 2021 7
  8. Khai niệm khai phá kết hợp June 20, 2021 8
  9. Khái niệm khai phá luật kết hợp ◼ Khai phá luật kết hợp: ◼ Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu trú nhan-quả trong tập các mục hoặc đối tượng trong CSDL quan hệ hoặc các kho chứa thơng tin khác. ◼ Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy mục ) mà xuất hiện phổ biến trong 1 CSDL [AIS93] ◼ Động lực: tìm mẫu chính quy (regularities pattern) trong DL ◼ Các mặt hàng nào được mua cùng nhau? — Bia và bỉm (diapers)?! ◼ Mặt hàng nào sẽ được mua sau khi mua một PC ? ◼ Kiểu DNA nào nhạy cảm với thuộc mới này? ◼ Cĩ khả năng tự động phân lớp Web hay khơng ? June 20, 2021 9
  10. Mẫu phổ biến và khai phá luật kết hợp là một bài tốn bản chất của khai phá DL ◼ Nền tảng của nhiều bài tốn KPDL bản chất ◼ Kết hợp, tương quan, nhân quả ◼ Mẫu tuần tự, kết hợp thời gian hoặc vịng, chu kỳ bộ phận, kết hợp khơng gian và đa phương tiện ◼ Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích tụ (nén dữ liệu ngữ nghĩa) ◼ Ứng dụng rộng rãi ◼ Phân tích DL bĩng rổ, tiếp thị chéo (cross-marketing), thiết kế catalog, phân tích chiến dịch bán hàng ◼ Phân tích Web log (click stream), Phân tích chuỗi DNA v.v. June 20, 2021 10
  11. Chương 4: Khai phá luật kết hợp ◼ Khai phá luật kết hợp (Association rule) ◼ Các thuật tốn khai phá vơ hướng luật kết hợp (giá trị lơgic đơn chiều) trong CSDL giao dịch ◼ Khai phá kiểu đa dạng luật kết hợp/tương quan ◼ Khai phá kết hợp dựa theo ràng buộc ◼ Khai phá mẫu dãy June 20, 2021 11
  12. Apriori: Một tiếp cận sinh ứng viên và kiểm tra ◼ Khái quát: Khai phá luật kết hợp gồm hai bước: ◼ Tìm mọi tập mục phổ biến: theo min-sup ◼ Sinh luật mạnh từ tập mục phổ biến ◼ Mọi tập con của tập mục phổ biến cũng là tập mục phổ biến ◼ Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi giao dịch chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}. ◼ Nguyên lý tỉa Apriori: Với mọi tập mục khơng phổ biến thì mọi tập bao khơng cần phải sinh ra/kiểm tra! ◼ Phương pháp: ◼ Sinh các tập mục ứng viên dài (k+1) từ các tập mục phổ biến cĩ độ dài k (Độ dài tập mục là số phần tử của nĩ), ◼ Kiểm tra các tập ứng viên theo CSDL ◼ Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng của thuật tốn ◼ Agrawal & Srikant 1994, Mannila, và cộng sự 1994 June 20, 2021 12
  13. Thuật tốn Apriori Trên cơ sở tính chất (nguyên lý tỉa) Apriori, thuật tốn hoạt động theo quy tắc quy hoạch động • Từ các tập Fi = {ci| ci tập phổ biến, |ci| = i} gồm mọi tập mục phổ biến cĩ độ dài i với 1 i k, • đi tìm tập Fk+1 gồm mọi tập mục phổ biến cĩ độ dài k+1. Trong thuật tốn, các tên mục i1, i2, in (n = |I|) được sắp xếp theo một thứ tự cố định (thường được đánh chỉ số 1, 2, , n). June 20, 2021 13
  14. Thuật tốn Apriori June 20, 2021 14
  15. Thuật tốn Apriori: Thủ tục con Apriori-gen Trong mỗi bước k, thuật tốn Apriori đều phải duyệt CSDL D. Khởi động, duyệt D để cĩ được F1. Các bước k sau đĩ, duyệt D để tính số lượng giao dịch t thoả từng ứng viên c của Ck+1: mỗi giao dịch t chỉ xem xét một lần cho mọi ứng viên c thuộc Ck+1. Thủ tục con Apriori-gen sinh tập phổ biến: tư tưởng June 20, 2021 15
  16. Thủ tục con Apriori-gen June 20, 2021 16
  17. Một ví dụ thuật tốn Apriori (s=0.5) Itemset sup Itemset sup Database TDB {A} 2 L {A} 2 Tid Items C {B} 3 1 1 {B} 3 10 A, C, D {C} 3 st {C} 3 20 B, C, E 1 scan {D} 1 {E} 3 30 A, B, C, E {E} 3 40 B, E C Itemset sup 2 C2 Itemset {A, B} 1 L Itemset sup nd 2 {A, C} 2 2 scan {A, B} {A, C} 2 {A, E} 1 {A, C} {B, C} 2 {B, C} 2 {A, E} {B, E} 3 {B, E} 3 {B, C} {C, E} 2 {C, E} 2 {B, E} {C, E} Itemset C3 3rd scan L3 Itemset sup {B, C, E} {B, C, E} 2 June 20, 2021 17
  18. Chi tiết quan trọng của Apriori ◼ Cách thức sinh các ứng viên: ◼ Bước 1: Tự kết nối Lk ◼ Step 2: Cắt tỉa ◼ Cách thức đếm hỗ trợ cho mỗi ứng viên. ◼ Ví dụ thủ tục con sinh ứng viên ◼ L3={abc, abd, acd, ace, bcd} ◼ Tự kết nối: L3*L3 ◼ abcd từ abc và abd ◼ acde từ acd và ace ◼ Tỉa: ◼ acde là bỏ đi vì ade khơng thuộc L3 ◼ C4={abcd} June 20, 2021 18
  19. Ví dụ: D, min_sup*|D| = 2 (C4 = ) June 20, 2021 19
  20. Sinh luật kết hợp Việc sinh luật kết hợp gồm hai bước ◼ Với mỗi tập phổ biến W tìm được hãy sinh ra mọi tập con thực sự X khác rỗng của nĩ. ◼ Với mỗi tập phố biến W và tập con X khác rỗng thực sự của nĩ: sinh luật X → (W – X) nếu P(W-X|X) c. Như ví dụ đã nêu cĩ L3 = {{I1, I2, I3}, {I1, I2, I5}} Với độ tin cậy tối thiểu 70%, xét tập mục phổ biến {I1, I2, I5} cĩ 3 luật như dưới đây: June 20, 2021 20
  21. Cách thức tính độ hỗ trợ của ứng viên ◼ Tính độ hỗ trợ ứng viên: vấn đề cần quan tâm ◼ Số lượng ứng viên là rất lớn ◼ Một giao dịch chứa nhiều ứng viên ◼ Phương pháp: ◼ Tập mục ứng viên được chứa trong một cây-băm (hash-tree) ◼ Lá của cây băm chứa một danh sách các tập mục và bộ đếm ◼ Nút trong chứa bảng băm ◼ Hàm tập con: tìm ứng viên trong tập ứng viên June 20, 2021 21
  22. Tính độ hỗ trợ của ứng viên ◼ Tập các ứng viên Ck được lưu trữ trong một cây-băm. ◼ Gốc của cây băm ở độ sâu 1. Lá chứa một danh sách tập mục thuộc Ck. ◼ Nút trong chứa một bảng băm (chắng hạn mod N): mỗi ơ trỏ tới một nút khác (Nút ở độ sâu d trỏ tới các nút ở độ sâu d+1). ◼ Khi khởi tạo: gơc là nút lá với danh sách rỗng. ◼ Xây dựng cây băm - thêm một tập mục c: ◼ bắt đầu từ gốc đi xuống theo cây cho đến khi gặp một lá. ◼ Tại một nút trong độ sâu d: ◼ quyết định theo nhánh nào: áp dụng hàm băm tới mục thứ d của tập mục này. ◼ Khi số lượng tập mục tại một lá vượt quá ngưỡng quy định, lá được chuyển thành một nút trong và phân chia danh sách các tập mục như hàm băm. ◼ Tính độ hỗ trợ: tìm tất cả các ứng viên thuộc giao dịch t: ◼ Nếu ở nút gốc: băm vào mỗi mục trong t. ◼ Nếu ở một lá: tìm các tập mục ở lá này thuộc t và bổ sung chỉ dẫn các tập mục này tới tập trả lời. ◼ Nếu ở nút trong và đã đạt được nĩ bằng cách băm mục i, trên từng mục đứng sau i trong t và áp dụng đệ quy thủ tục này sang nút trong thùng tương ứng. June 20, 2021 22
  23. Ví dụ: Tính hỗ trợ các ứng viên Hàm tập con Cĩ các tập ứng viên độ dài 3 là 124, 125, 136, 3,6,9 145, 159, 234, 345, 356, 357, 367, 368, 457, 1,4,7 458, 567, 689 2,5,8 124 Thêm 145 vượt qua 1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 125 ngưỡng, đưa 4 tập này 3, 6, 9 đi sang phải sang nút con trái. Vì 4 tập 136 này đều vượt qua ngưỡng nên tách thành 145; 124, Thêm 159 bổ sung vào nút 125; 136 giữa cây con trái Thêm 234 bổ sung vào nút 2 3 4 giữa cây mẹ 5 6 7 1 4 5 3 4 5 3 5 6 3 6 7 Thêm 345 bổ sung vào nút 1 3 6 phải cây mẹ; sau đĩ tách 3 5 7 3 6 8 cây con phải 345; 356, 357; 1 2 4 6 8 9 367, 368 4 5 7 1 2 5 1 5 9 4 5 8 June 20, 2021 23
  24. Ví dụ: Tính hỗ trợ các ứng viên Hàm tập con 3,6,9 1,4,7 Giao dịch t=1 2 3 5 6 2,5,8 1, 4, 7 đi sang trái; 2, 5, 8 dừng ở giữa; 3, 6, 9 đi sang phải 1 + 2 3 5 6 1 3 + 5 6 2 3 4 5 6 7 1 4 5 3 4 5 3 5 6 3 6 7 1 3 6 3 5 7 3 6 8 1 2 + 3 5 6 6 8 9 1 2 4 4 5 7 1 2 5 1 5 9 4 5 8 12356 sang trái; 2356 ở giữa; 356 sang phải Trái: 12356 trái; 2356 ở giữa; 356 sang phải; bộ đếm của 125, 136, 356 được tăngJune 20, 2021 24
  25. Thi hành hiệu quả thuật tốn Apriori trong SQL ◼ Khĩ cĩ thể cĩ một hiệu quả tốt nếu chỉ tiếp cận thuần SQL (SQL-92) ◼ Sử dụng các mở rộng quan hệ - đối tượng như UDFs, BLOBs, hàm bảng v.v. ◼ Nhận được các thứ tự tăng quan trọng ◼ Xem bài: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating association rule mining with relational database systems: Alternatives and implications. In SIGMOD’98 June 20, 2021 25
  26. Thách thức khai phá mẫu phổ biến ◼ Thách thức ◼ Duyệt nhiều lần CSDL giao dịch ◼ Lượng các ứng viên rất lớn ◼ Tẻ nhạt việc tính tốn độ hỗ trợ ◼ Cải tiến Apriori: tư tưởng chung ◼ Giảm số lần duyệt CSDL giao dịch ◼ Rút gọn số lượng các ứng viên ◼ Giảm nhẹ tính độ hỗ trợ của các ứng viên June 20, 2021 26
  27. DIC (Đếm tập mục động): Rút số lượng duyệt CSDL ◼ Xây dựng dàn tập mục ABCD ◼ Khi mà A và D được xác định là phổ biến thì việc tính tốn cho AD được bắt đầu ABC ABD ACD BCD ◼ Khi mọi tập con độ dài 2 của BCD được xác định là phổ biến: việc tính tốn cho BCD được bắt đầu. AB AC BC AD BD CD Transactions 1-itemsets A B C D Apriori 2-itemsets {} Itemset lattice 1-itemsets S. Brin R. Motwani, J. Ullman, 2-items and S. Tsur. Dynamic itemset DIC 3-items counting and implication rules for market basket data. In SIGMOD’97 June 20, 2021 27
  28. Giải pháp Phân hoạch (Partition): Duyệt CSDL chỉ hai lần ◼ Mọi tập mục là phổ biến tiềm năng trong CSDL bắt buộc phải phổ biến ít nhất một vùng của DB ◼ Scan 1: Phân chia CSDL và tìm các mẫu cục bộ ◼ Scan 2: Hợp nhất các mẫu phổ biến tổng thể ◼ A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95 June 20, 2021 28
  29. Ví dụ về mẫu phổ biến ◼ Chọn một mẫu của CSDL gốc, khai phá mẫu phổ biến nội bộ mẫu khi dùng Apriori ◼ Duyệt CSDL một lần để kiểm tra các tập mục phổ biến tìm thấy trong ví dụ, chỉ cĩ bao (borders ) đĩng của các mẫu phổ biến được kiểm tra ◼ Ví dụ: kiểm tra abcd thay cho ab, ac, , v.v. ◼ Duyệt CSDL một lần nữa để tìm các mẫu phổ biến bị mất (bỏ qua) H. Toivonen. Sampling large databases for association rules. In VLDB’96 June 20, 2021 29
  30. DHP: Rút gọn số lượng các ứng viên ◼ Một k-tập mục mà bộ đếm trong lơ băm tương ứng dưới ngưỡng thì khơng thể là tập mục phổ biến ◼ Ứng viên: a, b, c, d, e ◼ Điểm vào băm: {ab, ad, ae} {bd, be, de} ◼ 1-tập mục phổ biến: a, b, d, e ◼ ab khơng là một ứng viên 2-tập mục nếu tống bộ đếm của {ab, ad, ae} là dưới ngưỡng hỗ trợ J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining association rules. In SIGMOD’95 June 20, 2021 30
  31. Eclat/MaxEclat và VIPER: Thăm dị dạng dữ liệu theo chiều ngang ◼ Dùng danh sách tid của giáo dịch trong một tập mục ◼ Nén danh sách tid ◼ Tập mục A: t1, t2, t3, sup(A)=3 ◼ Tập mục B: t2, t3, t4, sup(B)=3 ◼ Tập mục AB: t2, t3, sup(AB)=2 ◼ Thao tác chính: lấy giao của các danh sách tid ◼ M. Zaki et al. New algorithms for fast discovery of association rules. In KDD’97 ◼ P. Shenoy et al. Turbo-charging vertical mining of large databases. In SIGMOD’00 June 20, 2021 31
  32. Thắt cổ chai của khai phá mẫu phổ biến ◼ Duyệt CSDL nhiều là tốn kém ◼ KP mẫu dài cần nhiều bước để duyệt và sinh nhiều ứng viên ◼ Để tìm các tập mục phổ biến i1i2 i100 ◼ # duyệt: 100 1 2 1 0 0 100 ◼ # ứng viên: (100 ) + (100 ) + + (1 0 0 ) = 2 -1 = 1.27*1030 ! ◼ Thắt cổ chai: sinh ứng viên và kiểm tra ◼ Tránh sinh ứng viên? June 20, 2021 32
  33. KP mẫu phổ biến khơng cần sinh ƯV ◼ Dùng các mục phổ biến để tăng độ dài mẫu từ các mẫu ngắn hơn ◼ “abc” là một mẫu phổ biến ◼ Nhận mọi giao dịch cĩ “abc”: DB|abc (DB đã luơn cĩ abc: “cĩ điều kiện”) ◼ “d” là một mục phổ biến trong DB|abc → abcd là một mẫu phổ biến June 20, 2021 33
  34. Xây dựng cây FP từ một CSDL giao dịch TID Items bought (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o, w} {f, b} 400 {b, c, k, s, p} {c, b, p} min_support = 3 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 1. Duyệt CSDL một lần, tìm các 1-tập mục phổ biến (mẫu mục {} đơn). Loại các mục cĩ độ hỗ Header Table trợ < minsup. Xếp các mục phổ biến theo thứ tự giảm dần f:4 c:1 về độ hỗ trợ (bậc): Tạo f-list. Item frequency head Tạo cây FP với gốc nhãn {} f 4 2. Duyệt CSDL lần nữa: Với mỗi c 4 c:3 b:1 b:1 giao dịch t: xâu các mục phổ a 3 biến theo thứ tự như 2 và biểu b 3 a:3 p:1 diễn dưới dạng [p|P] với p là m 3 mục đầu, cịn P là xâu mục cịn p 3 lại; Gọi insert_tree ([p|P]), T) m:2 b:1 3. Tìm tập phổ biến trên cây FP F-list=f-c-a-b-m-p p:2 m:1 June 20, 2021 34
  35. Xây dựng cây FP June 20, 2021 35
  36. Xây dựng cây FP: chèn một xâu vào cây June 20, 2021 36
  37. Lợi ích của cấu trúc FP-tree ◼ Tính đầy đủ ◼ Duy trì tính đầy đủ thơng tin để khai phá mẫu phổ biến ◼ Khơng phá vỡ mẫu dài bới bất kỳ giao dich ◼ Tính cơ đọng ◼ Giảm các thơng tin khơng liên quan: mục khơng phổ biến bỏ đi ◼ Sắp mục theo tần số giảm: xuất hiện càng nhiều thì cành hiệu quả ◼ Khơng lớn hơn so với CSDL thơng thường June 20, 2021 37
  38. Tìm tập phổ biến từ cấu trúc FP-tree June 20, 2021 38
  39. Mẫu cực đại (Max-patterns) 1 2 ◼ Mẫu phổ biến {a1, , a100} → (100 ) + (100 ) + 1 0 0 100 30 + (1 0 0 ) = 2 -1 = 1.27*10 frequent sub- patterns! ◼ Mẫu cực đại: Mẫu phổ biến mà khơng là tập con thực sự của mẫu phổ biến khác ◼ BCDE, ACD là mẫu cực đại Tid Items ◼ BCD khơng là mẫu cực đại 10 A,B,C,D,E 20 B,C,D,E, Min_sup=2 30 A,C,D,F
  40. Tập mục phổ biến cực đại Một tập mục cực đại (Maximal Intemset) là tập mục phổ biến khơng là tập con thực sự của một tập mục phổ biến khác Maximal null Itemsets A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE Infrequent Itemsets Border ABCD E
  41. Tập mục đĩng ◼ Tập mục đĩng là tập mục mà khơng là tập con thực sự của một tập mục cĩ cùng độ hỗ trợ ◼ X đĩng: Y  X s(Y) < s(X) Itemset Support {A} 4 TID Items {B} 5 Itemset Support 1 {A,B} {C} 3 {A,B,C} 2 2 {B,C,D} {D} 4 {A,B,D} 3 3 {A,B,C,D} {A,B} 4 {A,C,D} 2 4 {A,B,D} {A,C} 2 {B,C,D} 3 5 {A,B,C,D} {A,D} 3 {A,B,C,D} 2 {B,C} 3 {B,D} 4 {C,D} 3
  42. Phân biệt tập mục cực đại với tập mục đĩng Transaction Ids null TID Items 124 123 1234 245 345 1 ABC A B C D E 2 ABCD 3 BCE 12 124 24 4 123 2 3 24 34 45 4 ACDE AB AC AD AE BC BD BE CD CE DE 5 DE 12 2 24 4 4 2 3 4 ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 2 4 ABCD ABCE ABDE ACDE BCDE Not supported by any transactions ABCDE
  43. Tập mục cực đại với tập phổ biến đĩng Closed but Minimum support = 2 null not maximal 124 123 1234 245 345 A B C D E Closed and maximal 12 124 24 4 123 2 3 24 34 45 AB AC AD AE BC BD BE CD CE DE 12 2 24 4 4 2 3 4 ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 2 4 ABCD ABCE ABDE ACDE BCDE # Closed = 9 # Maximal = 4 ABCDE
  44. Tập mục cực đại với tập mục đĩng
  45. Tập mục cực đại với tập mục đĩng June 20, 2021 45
  46. Tập mục cực đại với tập mục đĩng R. Bayardo. Efficiently mining long patterns from databases. SIGMOD’98 J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets", DMKD'00 Mohammed Javeed Zaki, Ching-Jiu Hsiao: CHARM: An Efficient Algorithm for Closed Itemset Mining. SDM 2002 June 20, 2021 46
  47. Chương 4: Khai phá luật kết hợp ◼ Khai phá luật kết hợp (Association rule) ◼ Các thuật tốn khai phá vơ hướng luật kết hợp (giá trị lơgic đơn chiều) trong CSDL giao dịch ◼ Khai phá kiểu đa dạng luật kết hợp/tương quan ◼ Khai phá kết hợp dựa theo ràng buộc ◼ Khai phá mẫu dãy June 20, 2021 47
  48. Luật kết hợp đa mức ◼ Các mục cĩ thể phân cấp ◼ Đặt hỗ trợ linh hoạt: Mục cấp thấp hơn là kỳ vọng cĩ độ hỗ trợ thấp hơn. ◼ CSDL giao dịch cĩ thể được mã hĩa theo chiều và mức ◼ Thăm dị KP đa mức chia sẻ uniform support reduced support Level 1 Milk Level 1 min_sup = 5% [support = 10%] min_sup = 5% Level 2 2% Milk Skim Milk Level 2 min_sup = 5% [support = 6%] [support = 4%] min_sup = 3% June 20, 2021 48
  49. Kết hợp đa chiều ◼ Luật đơn chiều (viết theo dạng quan hệ (đối tượng, giá trị)): buys(X, “milk”) buys(X, “bread”) ◼ Luật đa chiều: 2 chiều / thuộc tính ◼ Luật kết hợp liên chiều (khơng cĩ thuộc tính lặp) age(X,”19-25”)  occupation(X,“student”) buys(X,“coke”) ◼ Luật KH chiều-kết hợp (lai/hybrid) (lặp thuộc tính) age(X,”19-25”)  buys(X, “popcorn”) buys(X, “coke”) ◼ Thuộc tính phân lớp ◼ Tìm số lượng các giá trị khả năng khơng được sắp ◼ Thuộc tính định lượng ◼ Số, thứ tự ngầm định trong miền giá trị June 20, 2021 49
  50. Kết hợp đa mức: Rút gọn lọc ◼ Trong luật phân cấp, một luật cĩ thể dư thừa do đã cĩ quan hệ giữa “tổ tiên” của các mục. ◼ Ví dụ ◼ milk wheat bread [support = 8%, confidence = 70%] ◼ 2% milk wheat bread [support = 2%, confidence = 72%] ◼ Nĩi rằng: luật đầu tiên là tổ tiên luật thứ hai. ◼ Một luật là dư thừa nếu độ hỗ trợ của nĩ là khít với giá trị “mong muốn”, dựa theo tổ tiên của luật. June 20, 2021 50
  51. Luật kết hợp định lượng ◼ Thuộc tính số là sự rời rạc hĩa động d ◼ Độ tin cậy hoặc độ cơ đọng của luật là cực đại ◼ Luật kết hợp định lượng 2-D: Aquan1  Aquan2 Acat ◼ Phân cụm các luật kết hợp Liền kề nhau từ các luật Tổng quát dựa trên Lưới 2-D ◼ Ví dụ age(X,”30-34”)  income(X,”24K - 48K”) buys(X,”high resolution TV”) June 20, 2021 Data Mining: Concepts and Techniques 51
  52. Khai phá luật KH dựa theo khoảng cách ◼ Phương pháp đĩng thùng khơng nắm bắt được ngữ nghĩa của dữ liệu khoảng Equi-width Equi-depth Distance- Price($) (width $10) (depth 2) based 7 [0,10] [7,20] [7,7] 20 [11,20] [22,50] [20,22] 22 [21,30] [51,53] [50,53] 50 [31,40] 51 [41,50] 53 [51,60] ◼ Phân vùng dựa trên khoảng cách, rời rạc cĩ ý nghĩa hơn khi xem xét : ◼ Mật độ/ số điểm trong một khoảng ◼ Tính “gần gũi” của các điểm trong một khoảng June 20, 2021 52
  53. Độ đo hấp dẫn: Tương quan (nâng cao) ◼ play basketball eat cereal [40%, 66.7%] là lạc ◼ Phần trăm chung của sinh viên ăn ngũ cốc là 75% cao hơn so với 66.7%. ◼ play basketball not eat cereal [20%, 33.3%] là chính xác hơn, do độ hỗ trợ và tin cậy thấp hơn ◼ Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao) Basketball Not basketball Sum (row) P(A B) Cereal 2000 1750 3750 Not cereal 1000 250 1250 corrA,B = P(A)P(B) Sum(col.) 3000 2000 5000 June 20, 2021 53
  54. Chương 4: Khai phá luật kết hợp ◼ Khai phá luật kết hợp (Association rule) ◼ Các thuật tốn khai phá vơ hướng luật kết hợp (giá trị lơgic đơn chiều) trong CSDL giao dịch ◼ Khai phá kiểu đa dạng luật kết hợp/tương quan ◼ Khai phá kết hợp dựa theo ràng buộc ◼ Khai phá mẫu dãy June 20, 2021 54
  55. KPDL dựa trên ràng buộc ◼ Tìm tất cả các mẫu trong CSDL tự động? — phi hiện thực! ◼ Mẫu cĩ thể quá nhiều mà khơng mục đích! ◼ KPDL nên là quá trình tương tác ◼ Người dùng trực tiếp xác định KPDL gì khi dùng ngơn ngữ hỏi KPDL (hoặc giao diện đồ họa) ◼ KP dựa theo ràng buộc ◼ Linh hoạt người dùng: cung cấp ràng buộc trên cái mà KP ◼ Tối ưu hệ thống: thăm dị các ràng buộc để hiệu quả KP: KP dựa theo ràng buộc June 20, 2021 55
  56. Ràng buộc trong KPDL ◼ Ràng buộc kiểu tri thức: ◼ classification, association, etc. ◼ Ràng buộc dữ liệu — dùng câu hỏi kiếu SQL ◼ Tìm các cặp sản phẩn mua cùngnhau trong Vancouver vào Dec.’00 ◼ Ràng buộc chiều/cấp ◼ Liên quan tới vùng, giá, loại hàng, lớp khách hàng ◼ Ràng buộc luật (mẫu) ◼ Mua hàng nhỏ (price $200) ◼ Ràng buộc hấp dẫn ◼ Luật mạng: min_support 3%, min_confidence 60% June 20, 2021 56
  57. KP ràng buộc tìm/lập luận dựa theo ràng buộc ◼ Cả hai hướng tới rút gọn khơng gian tìm kiếm ◼ Tìm mọi mẫu bảm đảm ràng buộc tìm kiếm heuristic ◼ Tích hợp hai cái cho một bài tốn tìm kiếm thú vị ◼ KP ràng buộc <> quá trình hỏi trong hệ CSDL quan hệ ◼ Quá trình hỏi trong CSDL quan hệ địi hỏi tìm tất cả ◼ KP mẫu ràng buộc chung một triết lý tương tựng như cố gắng chọn về chiều sâu của câu hỏi June 20, 2021 57
  58. KP mấu phổ biến ràng buộc: vấn đề tố ưu hĩa câu hỏi ◼ Cho một câu hỏi KP Mấu phổ biến với một tập ràng buộc C, thì thuật tốn nên là ◼ Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C ◼ đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C ◼ Giải pháp “thơ ngây/hồn nhiên” (nạve) ◼ Tìm tất cát tập PB sau đĩ kiểm tra ràng buộc ◼ Tiếp cận hiệu quả hơn ◼ Phân tích tính chất các ràng buộc một cách tồn diện ◼ Khai thác chúng sâu sắc cĩ thể nhất trong tính tốn mẫu PB. June 20, 2021 58
  59. Khơng đơn điêu trong KP theo ràng buộc TDB (min_sup=2) ◼ Chống đơn điệu (Anti-monotonicity) TID Transaction ◼ Một tập mục S vi phạm ràng buộc, 10 a, b, c, d, f mọi tập lớn hơn nĩ cũng vi phạm 20 b, c, d, f, g, h 30 a, c, d, e, f ◼ sum(S.Price) v là chống đơn điệu 40 c, e, f, g ◼ sum(S.Price) v là khơng chống đơn Item Profit điệu a 40 ◼ Ví dụ. C: range(S.profit) 15 là chống b 0 đơn điệu c -20 d 10 ◼ Tập mục ab vi phạm C e -30 f 30 ◼ Cũng vậy mọi tập chưa ab g 20 h -10 June 20, 2021 59
  60. Ràng buộc nào là chống đơn điệu Ràng buộc Chống đơn điệu v S No S  V no S  V yes min(S) v no min(S) v yes max(S) v yes max(S) v no count(S) v yes count(S) v no sum(S) v ( a S, a 0 ) yes sum(S) v ( a S, a 0 ) no range(S) v yes range(S) v no avg(S)  v,  { =, , } convertible support(S)  yes support(S)  no June 20, 2021 60
  61. Tính đơn điệu trong KP luật dựa theo ràng buộc TDB (min_sup=2) ◼ Tính đơn điệu TID Transaction ◼ Khi một tập mục S thỏa mãn ràng 10 a, b, c, d, f buộc, thì mọi tập lớn hơn của nĩ 20 b, c, d, f, g, h 30 a, c, d, e, f cũng thỏa mãn 40 c, e, f, g ◼ sum(S.Price) v là đơn điệu Item Profit a 40 ◼ min(S.Price) v là đơn điệu b 0 ◼ Ví dụ. C: range(S.profit) 15 c -20 d 10 ◼ Tập mục ab đảm bảo C e -30 f 30 ◼ Cũng vậy mọi tập chứa ab g 20 h -10 June 20, 2021 61
  62. Ràng buộc đơn điệu Ràng buộc Đơn điệu v S yes S  V yes S  V no min(S) v yes min(S) v no max(S) v no max(S) v yes count(S) v no count(S) v yes sum(S) v ( a S, a 0 ) no sum(S) v ( a S, a 0 ) yes range(S) v no range(S) v yes avg(S)  v,  { =, , } convertible support(S)  no support(S)  yes June 20, 2021 62
  63. Tính cơ đọng ◼ Tính cơ đọng: ◼ Cho A1, là tập mục bảo đảm một ràng buộc cơ đọng C, thì mọi S bảm đảm C là dựa trên A1 , chằng hạn., S chứa một tập con thuộc A1 ◼ Tư tưởng: Bỏ qua xem xét CSDL giao dịch, cĩ chăng một tập mục S bảo đảm ràng buộc C cĩ thể được xác định dựa theo việc chọn các mục ◼ min(S.Price) v là cơ đọng ◼ sum(S.Price) v khơng cơ đọng ◼ Tối ưu hĩa: Nếu C là cơ đọng cĩ thể đẩy đếm trước June 20, 2021 63
  64. Ràng buộc cơ đọng Ràng buộc Cơ đọng v S yes S  V yes S  V yes min(S) v yes min(S) v yes max(S) v yes max(S) v yes count(S) v weakly count(S) v weakly sum(S) v ( a S, a 0 ) no sum(S) v ( a S, a 0 ) no range(S) v no range(S) v no avg(S)  v,  { =, , } no support(S)  no support(S)  no June 20, 2021 64
  65. Thuật tốn Apriori— Ví dụ Database D itemset sup. itemset sup. L1 TID Items C1 {1} 2 {1} 2 100 1 3 4 {2} 3 Scan D {2} 3 200 2 3 5 {3} 3 {3} 3 300 1 2 3 5 {4} 1 {5} 3 400 2 5 {5} 3 C itemset 2 itemset sup C2 {1 2} L2 itemset sup {1 2} 1 Scan D {1 3} 2 {1 3} 2 {1 3} {2 3} 2 {1 5} 1 {1 5} {2 5} 3 {2 3} 2 {2 3} {2 5} {3 5} 2 {2 5} 3 {3 5} 2 {3 5} C3 itemset Scan D L3 itemset sup {2 3 5} {2 3 5} 2 June 20, 2021 65
  66. Thuật tốn Nạve: Apriori +ràng buộc Database D itemset sup. itemset sup. L1 TID Items C1 {1} 2 {1} 2 100 1 3 4 {2} 3 Scan D {2} 3 200 2 3 5 {3} 3 {3} 3 300 1 2 3 5 {4} 1 {5} 3 400 2 5 {5} 3 C itemset 2 itemset sup C2 {1 2} L2 itemset sup {1 2} 1 Scan D {1 3} 2 {1 3} 2 {1 3} {2 3} 2 {1 5} 1 {1 5} {2 5} 3 {2 3} 2 {2 3} {2 5} {3 5} 2 {2 5} 3 {3 5} 2 {3 5} C3 itemset Scan D L3 itemset sup Constraint: {2 3 5} {2 3 5} 2 Sum{S.price < 5} June 20, 2021 66
  67. Thuật tốn Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu Database D itemset sup. itemset sup. L1 TID Items C1 {1} 2 {1} 2 100 1 3 4 {2} 3 Scan D {2} 3 200 2 3 5 {3} 3 {3} 3 300 1 2 3 5 {4} 1 {5} 3 400 2 5 {5} 3 C itemset 2 itemset sup C2 {1 2} L2 itemset sup {1 2} 1 Scan D {1 3} 2 {1 3} 2 {1 3} {2 3} 2 {1 5} 1 {1 5} {2 5} 3 {2 3} 2 {2 3} {2 5} {3 5} 2 {2 5} 3 {3 5} 2 {3 5} C3 itemset Scan D L3 itemset sup Constraint: {2 3 5} {2 3 5} 2 Sum{S.price < 5} June 20, 2021 67
  68. Thuật tốn Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu Database D itemset sup. itemset sup. L1 TID Items C1 {1} 2 {1} 2 100 1 3 4 {2} 3 Scan D {2} 3 200 2 3 5 {3} 3 {3} 3 300 1 2 3 5 {4} 1 {5} 3 400 2 5 {5} 3 C itemset 2 itemset sup C2 {1 2} L2 itemset sup {1 2} 1 Scan D {1 3} 2 {1 3} 2 {1 3} {2 3} 2 {1 5} 1 {1 5} {2 3} {2 5} 3 {2 3} 2 {2 5} {3 5} 2 {2 5} 3 {3 5} 2 {3 5} C3 itemset Scan D L3 itemset sup Constraint: {2 3 5} {2 3 5} 2 min{S.price <= 1 } June 20, 2021 68
  69. Chương 4: Khai phá luật kết hợp ◼ Khai phá luật kết hợp (Association rule) ◼ Các thuật tốn khai phá vơ hướng luật kết hợp (giá trị lơgic đơn chiều) trong CSDL giao dịch ◼ Khai phá kiểu đa dạng luật kết hợp/tương quan ◼ Khai phá kết hợp dựa theo ràng buộc ◼ Khai phá mẫu dãy June 20, 2021 69
  70. CSDL tuần tự và Phân tích mẫu tuần tự Phần mềm phân tích chuỗi thời gian EidoSearch: Trợ giúp đánh dấu mẫu dữ liệu hấp dẫn và EidoSearch đi tìm mọi mẫu tương tự từ quá khứ và hiện tại, phân tích kết quả tìm kiếm này, và chỉ ra xu hướng gì sẽ xảy ra. Gait-CAD Matlab toolbox: trực quan hĩa và phân tích chuỗi thời gian, bao gồm phân lớp, hồi quy, và phân cụm. Giấy phép GNU-GPL. Miningco: chương trình mã nguồn mở tự động tìm ra mẫu và quan hệ trong weblogs và các bộ dữ liệu khác. SAS Enterprise Miner XAffinity (TM): xác định mối quan hệ thân hoặc mẫu trong giao dịch và dịng dữ liệu nháy phím June 20, 2021 70
  71. CSDL TT và PT MTT (2) ◼ CSDL giao dịch, CSDL chuỗi thời gian mấu TT (PB) ◼ Ứng dụng của KP Mấu TT ◼ Tuần tự mua của khách hàng: ◼ Đầu tiên mua máy tính, sau đĩ CD-ROM, và sau đĩ là máy ảnh số, trong vịng 3 tháng. ◼ Phẫu thuật y tế, thảm họa tự nhiên (động đất ), quá trình KH và kỹ nghệ, chứng khốn và thị trường . ◼ Mẫu gọi điện thoại, dịng click tại Weblogs ◼ Dãy DNA và cấu trúc gene June 20, 2021 71
  72. Khái niệm KP mấu TT ◼ Cho một tập các dãy, tìm tập đầy đủ các dãy con phổ biến dãy TT : CSDL dãy TT SID sequence Một phần tử chứa một tập mục. 10 Tập mục trong một phần tử là khơng thứ tự , và viết chúng theo ABC. 20 30 là dãy con của 40 Cho độ hỗ trợ min_sup =2, là mẫu tuần tự sequential pattern June 20, 2021 72
  73. Một số chủ đề khai phá dữ liệu nĩng June 20, 2021 73