Bài giảng Khai phá dữ liệu (Data mining) - Chương 3: Khai phá luật kết hợp

Chương 3: Khai phá luật kết hợp 1 Nội dung  Tổng quan về khai phá luật kết hợp  Các khái niệm cơ bản  Bài toán khai phá luật kết hợp  Phân tích tương quan  Tóm tắt 2 Nội dung  Tổng quan về khai phá luật kết hợp  Các khái niệm cơ bản  Bài toán khai phá luật kết hợp  Phân tích tương quan  Tóm tắt 3 Tình huống 1 – Market basket analysis 4 Tình huống 2 - Tiếp thị chéo 5 Tình huống 2 - Tiếp thị chéo 6 Tình huống  Phân tích dữ liệu giỏ hàng (basket data analysis)  Tiếp thị chéo (cross-marketing)  Thiết kế catalog (catalog design)  Phân loại dữ liệu (classification) và gom cụm dữ liệu (clustering) với các mẫu phổ biến  7 Tổng quan về khai phá luật kết hợp  Quá trình khai phá luật kết hợp 8 Raw Data Items of Interest Relationship s among Items (Rules) User Pre- processing Mining Post- processing Tổng quan về khai phá luật kết hợp  Quá trình khai phá luật kết hợp 9 Bài toán phân tích giỏ thị trường Association Rules Items Transactional/ Relational Data Raw Data Items of Interest Relationship s among Items (Rules) User Pre- processing Mining Post- processing Transaction Items_bought --------------------------------- 2000 A, B, C 1000 A, C 4000 A, D 5000 B, E, F A, B, C, D, F, A  C (50%, 66.6%) Khai phá tập phổ biến(FIs – Frequent Itemsets). Sinh luật từ các tập phổ biến(ARs – Association Rules). Nội dung  Tổng quan về khai phá luật kết hợp  Các khái niệm cơ bản  Bài toán khai phá luật kết hợp  Phân tích tương quan  Tóm tắt 10  Dữ liệu mẫu của AllElectronics (sau quá trình tiền xử lý) 11 Các khái niệm cơ bản Các khái niệm cơ bản  Các khái niệm cơ bản - Item (phần tử) - Itemset (tập phần tử) - Transaction (giao dịch) - Association (sự kết hợp) và association rule (luật kết hợp) - Support (độ hỗ trợ) - Confidence (độ tin cậy) - Frequent itemset (tập phần tử phổ biến/thường xuyên) - Strong association rule (luật kết hợp mạnh) 12  Dữ liệu mẫu của AllElectronics (sau quá trình tiền xử lý) 13 Item: I4 Itemsets: {I1, I2, I5}, {I2}, Transaction: T800 Các khái niệm cơ bản  Các khái niệm cơ bản - Item (phần tử)  Các phần tử, mẫu, đối tượng đang được quan tâm.  J = {I1, I2, , Im}: tập tất cả m phần tử có thể có trong tập dữ liệu - Itemset (tập phần tử)  Tập hợp các items  Một itemset có k items gọi là k-itemset. - Transaction (giao dịch)  Lần thực hiện tương tác với hệ thống (ví dụ: giao dịch “khách hàng mua hàng”)  Liên hệ với một tập T gồm các phần tử được giao dịch 14 Các khái niệm cơ bản  Các khái niệm cơ bản - Association (sự kết hợp) và association rule (luật kết hợp)  Sự kết hợp: các phần tử cùng xuất hiện với nhau trong một hay nhiều giao dịch.  Thể hiện mối liên hệ giữa các phần tử/các tập phần tử  Luật kết hợp: qui tắc kết hợp có điều kiện giữa các tập phần tử.  Thể hiện mối liên hệ (có điều kiện) giữa các tập phần tử  Cho A và B là các tập phần tử, luật kết hợp giữa A và B là A  B.  B xuất hiện trong điều kiện A xuất hiện. 15 Các khái niệm cơ bản  Các khái niệm cơ bản - Support (độ hỗ trợ)  Độ đo đo tần số xuất hiện của các phần tử/tập phần tử.  Minimum support threshold (ngưỡng hỗ trợ tối thiểu)  Giá trị support nhỏ nhất được chỉ định bởi người dùng. - Confidence (độ tin cậy)  Độ đo đo tần số xuất hiện của một tập phần tử trong điều kiện xuất hiện của một tập phần tử khác.  Minimum confidence threshold (ngưỡng tin cậy tối thiểu)  Giá trị confidence nhỏ nhất được chỉ định bởi người dùng. 16 Các khái niệm cơ bản Customer buys diaper Customer buys both Customer buys beer Nuts, Eggs, Milk 40 Nuts, Coffee, Diaper, Eggs, Milk 50 Beer, Diaper, Eggs 30 Beer, Coffee, Diaper 20 Beer, Nuts, Diaper 10 Items bought Tid Giải: Freq. Pat.: Beer:3, Nuts:3, Diaper:4, Eggs:3, {Beer, Diaper}:3 Beer  Diaper support = support({Beer}{Diaper}) = 3/5=60% confidence = support({Beer}{Diaper})/support ({Beer}) = (3/5) / (3/5) = 100% Tính độ hộ trợ và độ tin cậy của luật sau? Beer  Diaper Các khái niệm cơ bản Tính độ hộ trợ và độ tin cậy của luật sau? Diaper Beer For rule A  C: support = support({A}{C}) = 50% confidence = support({A}{C})/support({A}) = 66.6% Tìm luật kết hợp Min. support 50% Min. confidence 50% Transaction-id Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F Frequent pattern Support {A} 75% {B} 50% {C} 50% {A, C} 50% Các khái niệm cơ bản  Các khái niệm cơ bản - Frequent itemset (tập phần tử phổ biến)  Tập phần tử có support thỏa minimum support threshold.  Cho A là một itemset  A là frequent itemset iff support(A) >= minimum support threshold. - Strong association rule (luật kết hợp mạnh)  Luật kết hợp có support và confidence thỏa minimum support threshold và minimum confidence threshold.  Cho luật kết hợp AB giữa A và B, A và B là itemsets  AB là strong association rule iff support(AB) >= minimum support threshold và confidence(AB) >= minimum confidence threshold. 19 Các khái niệm cơ bản 20  Phân loại luật kết hợp - Boolean association rule (luật kết hợp luận lý)/quantitative association rule (luật kết hợp lượng số) - Single-dimensional association rule (luật kết hợp đơn chiều)/multidimensional association rule (luật kết hợp đa chiều) - Single-level association rule (luật kết hợp đơn mức)/multilevel association rule (luật kết hợp đa mức) - Association rule (luật kết hợp)/correlation rule (luật tương quan thống kê) Phân loại luật kết hợp 21 Phân loại luật kết hợp  Phân loại luật kết hợp - Boolean association rule (luật kết hợp luận lý)/quantitative association rule (luật kết hợp lượng số)  Boolean association rule: luật mô tả sự kết hợp giữa sự hiện diện/vắng mặt của các phần tử.  Computer  Financial_management_software [support=2%, confidence=60%]  Quantitative association rule: luật mô tả sự kết hợp giữa các phần tử/thuộc tính định lượng.  Age(X, “30..39”)  Income(X, “42K..48K”)  buys(X, high resolution TV) 22 Phân loại luật kết hợp  Phân loại luật kết hợp - Single-dimensional association rule (luật kết hợp đơn chiều)/multidimensional association rule (luật kết hợp đa chiều)  Single-dimensional association rule: luật chỉ liên quan đến các phần tử/thuộc tính của một chiều dữ liệu.  Buys(X, “computer”)  Buys(X, “financial_management_software”)  Multidimensional association rule: luật liên quan đến các phần tử/thuộc tính của nhiều hơn một chiều.( 2 chiều / thuộc tính)  Age(X, “30..39”)  Buys(X, “computer”) 23 Phân loại luật kết hợp  Phân loại luật kết hợp - Single-level association rule (luật kết hợp đơn mức) /multilevel association rule (luật kết hợp đa mức)  Single-level association rule: luật chỉ liên quan đến các phần tử/thuộc tính ở một mức trừu tượng.  Age(X, “30..39”)  Buys(X, “computer”)  Age(X, “18..29”)  Buys(X, “camera”)  Multilevel association rule: luật liên quan đến các phần tử/thuộc tính ở các mức trừu tượng khác nhau.  Age(X, “30..39”)  Buys(X, “laptop computer”)  Age(X, “30..39”)  Buys(X, “computer”) 24 Phân loại luật kết hợp  Phân loại luật kết hợp - Association rule (luật kết hợp)/correlation rule (luật tương quan thống kê)  Association rule: strong association rules AB (association rules đáp ứng yêu cầu minimum support threshold và minimum confidence threshold).  Correlation rule: strong association rules A  B đáp ứng yêu cầu về sự tương quan thống kê giữa A và B. 25 Biểu diễn luật kết hợp  Dạng luật: AB [support, confidence] - Cho trước minimum support threshold (min_sup), minimum confidence threshold (min_conf) - A và B là các itemsets  Frequent itemsets/subsequences/substructures  Closed frequent itemsets  Maximal frequent itemsets  Constrained frequent itemsets  Approximate frequent itemsets  Top-k frequent itemsets 26 Biểu diễn luật kết hợp  Frequent itemsets/subsequences/substructures - Itemset/subsequence/substructure X là frequent nếu support(X) >= min_sup.  Itemsets: tập các items  Subsequences: chuỗi tuần tự các events/items  Substructures: các tiểu cấu trúc (graph, lattice, tree, sequence, set, )  Tập phổ biến tối đại (Maximal frequent itemsets) - Là tập phổ biến mà không tồn tại tập nào bao nó là phổ biến 27 null AB AC AD AE BC BD BE CD CE DE A B C D E ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCD E Border Infrequent Itemsets Maximal Itemsets Biểu diễn luật kết hợp  Tập phổ biến đóng (Frequent closed itemsets): - Là tập phổ biến và không tồn tại tập nào bao nó có cùng độ phổ biến như nó 28 TID Items 1 {A,B} 2 {B,C,D} 3 {A,B,C,D} 4 {A,B,D} 5 {A,B,C,D} Itemset Support {A} 4 {B} 5 {C} 3 {D} 4 {A,B} 4 {A,C} 2 {A,D} 3 {B,C} 3 {B,D} 4 {C,D} 3 Itemset Support {A,B,C} 2 {A,B,D} 3 {A,C,D} 2 {B,C,D} 3 {A,B,C,D} 2 Biểu diễn luật kết hợp Phân biệt tập phổ biến tối đại với tập phổ biến đóng TID Items 1 ABC 2 ABCD 3 BCE 4 ACDE 5 DE null AB AC AD AE BC BD BE CD CE DE A B C D E ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE 124 123 1234 245 345 12 124 24 4 123 2 3 24 34 45 12 2 24 4 4 2 3 4 2 4 Transaction Ids Not supported by any transactions Phân biệt tập phổ biến tối đại với tập phổ biến đóng null AB AC AD AE BC BD BE CD CE DE A B C D E ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE 124 123 1234 245 345 12 124 24 4 123 2 3 24 34 45 12 2 24 4 4 2 3 4 2 4 Minimum support = 2 # Closed = 9 # Maximal = 4 Closed and maximal Closed but not maximal 31 Biểu diễn luật kết hợp  Constrained frequent itemsets - Frequent itemsets thỏa các ràng buộc do người dùng định nghĩa.  Approximate frequent itemsets - Frequent itemsets dẫn ra support (xấp xỉ) cho các frequent itemsets sẽ được khai phá.  Top-k frequent itemsets - Frequent itemsets có nhiều nhất k phần tử với k do người dùng chỉ định. 32 Biểu diễn luật kết hợp  Luật kết hợp luận lý, đơn mức, đơn chiều giữa các tập phần tử phổ biến: AB [support, confidence] - A và B là các frequent itemsets  single-dimensional  single-level  Boolean - Support(AB) = Support(A U B) >= min_sup - Confidence(AB) = Support(A U B)/Support(A) = P(B|A) >= min_conf Nội dung  Tổng quan về khai phá luật kết hợp  Các khái niệm cơ bản  Bài toán khai phá luật kết hợp  Phân tích tương quan  Tóm tắt 33 Bài toán khai phá luật kết hợp 34 Bài toán khai phá luật kết hợp Cho trước một tập các mục I, một cơ sở dữ liệu D, ngưỡng hỗ trợ minsup và ngưỡng tin cậy minconf. Tìm tất cả các tập luật kết hợp X  Y trên D thỏa mãn: sup(X  Y) >= minsup và conf(X  Y) >= minconf Bài toán có thể phát biểu như sau: - Dữ liệu vào: I, D, minsup, minconf. - Dữ liệu ra: Các luật kết hợp thỏa mãn minsup và minconf. Bài toán khai phá luật kết hợp 35 Association Rules Items Transactional/ Relational Data Raw Data Items of Interest Relationship s among Items (Rules) User Pre- processing Mining Post- processing Transaction Items_bought --------------------------------- 2000 A, B, C 1000 A, C 4000 A, D 5000 B, E, F A, B, C, D, F, A  C (50%, 66.6%) Sinh luật từ các tập phổ biến(ARs – Association Rules). Khai phá tập phổ biến(FIs – Frequent Itemsets).  Quá trình khai phá luật kết hợp Bài toán khai phá luật kết hợp 36 Thuật toán thực hiện qua hai pha: Pha 1: Tìm tất cả các tập mục phổ biến (large itemsets) từ cơ sở dữ liệu D tức là tìm tất cả các tập mục có độ hỗ trợ lớn hơn hoặc bằng minsup. (Bài toán khai phá tập phổ biến) Pha 2: Sinh các luật kết hợp từ các tập phổ biến đã tìm thấy ở pha 1 sao cho độ tin cậy của luật lớn hơn hoặc bằng minconf. Bài toán khai phá tập phổ biến 37 Thuật toán thực hiện qua hai pha: Pha 1: Tìm tất cả các tập mục phổ biến (large itemsets) từ cơ sở dữ liệu D tức là tìm tất cả các tập mục có độ hỗ trợ lớn hơn hoặc bằng minsup. (Bài toán khai phá tập phổ biến) Pha 2: Sinh các luật kết hợp từ các tập phổ biến đã tìm thấy ở pha 1 sao cho độ tin cậy của luật lớn hơn hoặc bằng minconf.  Thuật toán Apriori: khai phá tập phổ biến - R. Agrawal, R. Srikant. Fast algorithms for mining association rules. In VLDB 1994, pp. 487-499.  Thuật toán FP-Growth: khai phá tập phổ biến với FP- tree - J. Han, J. Pei, Y. Yin. Mining frequent patterns without candidate generation. In MOD 2000, pp. 1-12. 38 Bài toán khai phá tập phổ biến 39 Thuật toán Apriori  Thuật toán Apriori:  k k kk t kt k-k k-1 ;L Answer minsup}|c.countC { c L c.count Cc ,t)(C C Dt )(L C ); k 2; L( k itemsets} {large 1- L          end end end ; do candidates forall subset begin do ons transactiforall ;genapriori- begin do For 1 1  Count item occurrences Generate new k-itemsets candidates Find the support of all the candidates Take only those with support over minsup 40 Thuật toán Apriori  Ví dụ: L3 = { {1 2 3}, {1 2 4}, {1 3 4}, {1 3 5}, {2 3 4} } After joining { {1 2 3 4}, {1 3 4 5} } After pruning {1 2 3 4} {1 4 5} and {3 4 5} Are not in L3 41 Ví dụ thuật toán Apriori Database TDB 1st scan C1 L1 L2 C2 C2 2nd scan C3 L3 3rd scan Tid Items 10 A, C, D 20 B, C, E 30 A, B, C, E 40 B, E Itemset sup {A} 2 {B} 3 {C} 3 {D} 1 {E} 3 Itemset sup {A} 2 {B} 3 {C} 3 {E} 3 Itemset {A, B} {A, C} {A, E} {B, C} {B, E} {C, E} Itemset sup {A, B} 1 {A, C} 2 {A, E} 1 {B, C} 2 {B, E} 3 {C, E} 2 Itemset sup {A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2 Itemset {B, C, E} Itemset sup {B, C, E} 2 Supmin = 2  Dữ liệu mẫu của AllElectronics (sau quá trình tiền xử lý) 42 Ví dụ thuật toán Apriori 43 min_sup = 2/9 minimum support count = 2 Ví dụ thuật toán Apriori Bài toán khai phá tập phổ biến  Thuật toán Apriori - Đặc điểm  Tạo ra nhiều tập dự tuyển  104 frequent 1-itemsets  nhiều hơn 107 (≈104(104-1)/2) 2-itemsets dự tuyển  Một k-itemset cần ít nhất 2k -1 itemsets dự tuyển trước đó.  Kiểm tra tập dữ liệu nhiều lần  Chi phí lớn khi kích thước các itemsets tăng lên dần.  Nếu k-itemsets được khám phá thì cần kiểm tra tập dữ liệu k+1 lần. 44 Bài toán khai phá tập phổ biến  Thuật toán Apriori - Các cải tiến của thuật toán Apriori  Kỹ thuật dựa trên bảng băm (hash-based technique)  Một k-itemset ứng với hashing bucket count nhỏ hơn minimum support threshold không là một frequent itemset.  Giảm giao dịch (transaction reduction)  Một giao dịch không chứa frequent k-itemset nào thì không cần được kiểm tra ở các lần sau (cho k+1-itemset).  Phân hoạch (partitioning)  Một itemset phải frequent trong ít nhất một phân hoạch thì mới có thể frequent trong toàn bộ tập dữ liệu.  Lấy mẫu (sampling)  Khai phá chỉ tập con dữ liệu cho trước với một trị support threshold nhỏ hơn và cần một phương pháp để xác định tính toàn diện (completeness).  Đếm itemset động (dynamic itemset counting)  Chỉ thêm các itemsets dự tuyển khi tất cả các tập con của chúng được dự đoán là frequent. 45 Bài toán khai phá tập phổ biến  Thuật toán FP-Growth - Nén tập dữ liệu vào cấu trúc cây (Frequent Pattern tree, FP- tree)  Giảm chi phí cho toàn tập dữ liệu dùng trong quá trình khai phá  Infrequent items bị loại bỏ sớm.  Đảm bảo kết quả khai phá không bị ảnh hưởng - Phương pháp chia-để-trị (divide-and-conquer)  Quá trình khai phá được chia thành các công tác nhỏ.  1. Xây dựng FP-tree  2. Khám phá frequent itemsets với FP-tree - Tránh tạo ra các tập dự tuyển  Mỗi lần kiểm tra một phần tập dữ liệu 46 Bài toán khai phá tập phổ biến  Thuật toán FP-Growth - 1. Xây dựng FP-tree  1.1. Kiểm tra tập dữ liệu, tìm frequent 1-itemsets  1.2. Sắp thứ tự frequent 1-itemsets theo sự giảm dần của support count (frequency, tần số xuất hiện)  1.3. Kiểm tra tập dữ liệu, tạo FP-tree  Tạo root của FP-tree, được gán nhãn “null” {}  Mỗi giao dịch tương ứng một nhánh của FP-tree.  Mỗi node trên một nhánh tương ứng một item của giao dịch.  Các item của một giao dịch được sắp theo giảm dần.  Mỗi node kết hợp với support count của item tương ứng.  Các giao dịch có chung items tạo thành các nhánh có prefix chung. 47 Bài toán khai phá tập phổ biến  Thuật toán FP-Growth 48 Bài toán khai phá tập phổ biến 49 Bài toán khai phá tập phổ biến  Thuật toán FP-Growth - 2. Khám phá frequent itemsets với FP-tree  2.1. Tạo conditional pattern base cho mỗi node của FP-tree  Tích luỹ các prefix paths with frequency của node đó  2.2. Tạo conditional FP-tree từ mỗi conditional pattern base  Tích lũy frequency cho mỗi item trong mỗi base  Xây dựng conditional FP-tree cho frequent items của base đó  2.3. Khám phá conditional FP-tree và phát triển frequent itemsets một cách đệ qui  Nếu conditional FP-tree có một path đơn thì liệt kê tất cả các itemsets. 50 Bài toán khai phá tập phổ biến  Thuật toán FP-Growth 51 Bài toán khai phá tập phổ biến 52 52 Example: FP-growth  The first scan of data is the same as Apriori  Derive the set of frequent 1- itemsets  Let min-sup=2  Generate a set of ordered items TID List of item IDS T100 I1,I2,I5 T200 I2,I4 T300 I2,I3 T400 I1,I2,I4 T500 I1,I3 T600 I2,I3 T700 I1,I3 T800 I1,I2,I3,I5 T900 I1,I2,I3 Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null - Create a branch for each transaction - Items in each transaction are processed in order 1- Order the items T100: {I2,I1,I5} 2- Construct the first branch: , , TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I2:1 I1:1 I5:1 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null - Create a branch for each transaction - Items in each transaction are processed in order 1- Order the items T200: {I2,I4} 2- Construct the second branch: , TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I2:1 I1:1 I5:1 I4:1 2 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null - Create a branch for each transaction - Items in each transaction are processed in order 1- Order the items T300: {I2,I3} 2- Construct the third branch: , TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I2:2 I1:1 I5:1 I4:1 I3:1 3 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null - Create a branch for each transaction - Items in each transaction are processed in order 1- Order the items T400: {I2,I1,I4} 2- Construct the fourth branch: , , TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I1:1 I5:1 I4:1 I3:1 I2:3 I4:1 2 4 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null - Create a branch for each transaction - Items in each transaction are processed in order 1- Order the items T400: {I1,I3} 2- Construct the fifth branch: , TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I1:2 I5:1 I4:1 I3:1 I2:4 I4:1 I1:1 I3:1 Construct the FP-Tree Transactional Database Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null TID Items TID Items TID Items T100 I1,I2,I5 T400 I1,I2,I4 T700 I1,I3 T200 I2,I4 T500 I1,I3 T800 I1,I2,I3,I5 T300 I2,I3 T600 I2,I3 T900 I1,I2,I3 I1:4 I5:1 I4:1 I3:2 I2:7 I4:1 I1:2 I3:2 I3:2 I5:1 When a branch of a transaction is added, the count for each node along a common prefix is incremented by 1 Construct the FP-Tree Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null I1:4 I5:1 I4:1 I3:2 I2:7 I4:1 I1:2 I3:2 I3:2 I5:1 The problem of mining frequent patterns in databases is transformed to that of mining the FP-tree Construct the FP-Tree -Occurrences of I5: and -Two prefix Paths and -Conditional FP tree contains only , I3 is not considered because its support count of 1 is less than the minimum support count. -Frequent patterns {I2,I5:2}, {I1,I5:2},{I2,I1,I5:2} Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null I1:4 I5:1 I4:1 I3:2 I2:7 I4:1 I1:2 I3:2 I3:2 I5:1 Construct the FP-Tree Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null I1:4 I5:1 I4:1 I3:2 I2:7 I4:1 I1:2 I3:2 I3:2 I5:1 TID Conditional Pattern Base Conditional FP-tree I5 {{I2,I1:1},{I2,I1,I3:1}} I4 {{I2,I1:1},{I2,1}} I3 {{I2,I1:2},{I2:2}, {I1:2}} , I1 {I2,4} Construct the FP-Tree Item ID Support count I2 7 I1 6 I3 6 I4 2 I5 2 null I1:4 I5:1 I4:1 I3:2 I2:7 I4:1 I1:2 I3:2 I3:2 I5:1 TID Conditional FP-tree Frequent Patterns Generated I5 {I2,I5:2}, {I1,I5:2},{I2,I1,I5:2} I4 {I2,I4:2} I3 , {I2,I3:4},{I1,I3:4},{I2,I1,I3:2} I1 {I2,I1:4} Bài toán khai phá tập phổ biến  Thuật toán FP-Growth - Đặc điểm  Không tạo tập itemsets dự tuyển  Không kiểm tra xem liệu itemsets dự tuyển có thực là frequent itemsets  Sử dụng cấu trúc dữ liệu nén dữ liệu từ tập dữ liệu  Giảm chi phí kiểm tra tập dữ liệu  Chi phí chủ yếu là đếm và xây dựng cây FP-tree lúc đầu  Hiệu quả và co giãn tốt cho việc khám phá các frequent itemsets dài lẫn ngắn 64 Bài toán khai phá tập phổ biến  So sánh giữa thuật toán Apriori và thuật toán FP-Growth 65 Co giãn với support threshold Bài toán khai phá tập phổ biến  So sánh giữa thuật toán Apriori và thuật toán FP-Growth 66 Co giãn tuyến tính với số giao dịch Bài toán khai phá luật kết hợp 67 Thuật toán thực hiện qua hai pha: Pha 1: Tìm tất cả các tập mục phổ biến (large itemsets) từ cơ sở dữ liệu D tức là tìm tất cả các tập mục có độ hỗ trợ lớn hơn hoặc bằng minsup. (Bài toán khai phá tập phổ biến) Pha 2: Sinh các luật kết hợp từ các tập phổ biến đã tìm thấy ở pha 1 sao cho độ tin cậy của luật lớn hơn hoặc bằng minconf. Sinh các luật kết hợp từ các tập phổ biến (Pha 2) 68  Việc phát hiện các tập mục phổ biến là rất tốn kém về mặt tính toán. Tuy nhiên, ngay khi tìm được tất cả các tập mục phổ biến (l Є L), ta có thể sinh ra các luật kết hợp: - Tìm tất cả các tập con không rỗng a, của tập mục lớn l Є L. - Với mỗi tập con a tìm được, ta xuất ra luật dạng a  (l - a) nếu tỷ số: Sup(l)/Sup(a) >= mincof ( %). Ví dụ: ABCD=>{ } BCD=>A ACD=>B ABD=>C ABC=>D BC=>ADBD=>ACCD=>AB AD=>BC AC=>BD AB=>CD D=>ABC C=>ABD B=>ACD A=>BCD Lattice of rules Pruned Rules Low Confidence Rule Sinh các luật kết hợp từ các tập phổ biến (Pha 2) 70 Min_conf = 50% I1  I2  I5 I1  I5  I2 I2  I5  I1 I5  I1  I2 Nội dung  Tổng quan về khai phá luật kết hợp  Các khái niệm cơ bản  Bài toán khai phá luật kết hợp  Phân tích tương quan  Tóm tắt 71 Các luật được quan tâm  Hầu như các thuật toán khai phá luật kết hợp sử dụng support– confidence  Mặc dù ngưỡng support–confidence tối thiểu giúp ta loại bỏ các luật không được quan tâm, nhiều luật được sinh ra thỏa support–confidence tối thiểu nhưng vẫn không được quan tâm bởi người dùng.  Điều này đặc biệt đúng khi khai phá ở ngưỡng hỗ trợ thấp hay khai phá với long patterns.  Chúng ta cần đề cập đến các vấn đề sau: - Luật kết hợp mạnh nào không được quan tâm và lạc hướng? - Support–confidence có thể bổ sung cho các độ đo quan tâm dựa vào phân tích tương quan như thế nào - Các độ đo đánh giá mẫu - Các độ đo đánh giá mẫu ảnh hưởng đến việc khai phá các luật được quan tâm 72 Luật kết hợp mạnh không được quan tâm  Ví dụ cho luật sau: - buys (X, “computer games”)  buys (X, “videos”) - [support = 40%, confidence = 66%]. (Cho min_sup =30%, min_ conf=60%)  Luật trên là luật kết hợp mạnh vì có support= 40%> min_sup(30%) và confidence=66.7> min_conf (60%)  Tuy nhiên luật trên bị lạc hướng vì - Tổng % buy video là 75% > 66.7%.  buys ( X, “computer games” )  không buys (X, “videos”) [20%, 33.3%] thì đúng hơn mặc dù nó có support và confidence thấp hơn 73 Luật kết hợp mạnh không được quan tâm  Từ ví dụ trên cho thấy confidence của luật AB có thể đánh lừa người dùng. Nó không đo sự tương quan giữa A và B. Do vậy cần các độ đo khác về support– confidence trong việc khai phá mối liên hệ về dữ liệu được quan tâm. 74 Từ phân tích sự kết hợp đến phân tích sự tương quan  Luật tương quan (correlation rules): - A  B [support, confidence, correlation]  Luật tương quan không chỉ được đo bởi độ hỗ trợ và độ tin cậy mà còn được đo bởi sự tương quan giữa A và B  Có nhiều độ đo về correlation, chúng ta học 1 số độ đo về sự tương quan để xác định độ đo nào tốt trong việc khai phá tập dữ liệu lớn. 75  Độ đo lift của luật A  B :  Lift(A, B) = 1: A và B độc lập nhau, không có tương quan  Lift(A, B) < 1: A tương quan nghịch với B: 1 sự có mặt của 1 item có khả năng dẫn đến sự vắng mặt của item khác  Lift(A, B) > 1: A tương quan thuận với B: 1 sự có mặt của 1 item có khả năng dẫn đến sự có mặt của item khác 76 )()( )( BPAP BAP lift   Từ phân tích sự kết hợp đến phân tích sự tương quan 89.0 5000/3750*5000/3000 5000/2000 ),( CBlift Basketball Not basketball Sum (row) Cereal 2000 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 2000 5000 33.1 5000/1250*5000/3000 5000/1000 ),( CBlift play basketball  eat cereal [40%, 66.7%]  Phân tích sự tương quan sử dụng lift: để giúp việc lọc ra các luật kết hợp mạnh bị lạc hướng như ví dụ trên dạng A  B từ ví dụ trên ta tìm hiểu 2 itemset A và B liên quan với nhau như thế nào 77 Từ phân tích sự kết hợp đến phân tích sự tương quan )sup( )conf(A )( A)|P(B )()( )( B B BPBPAP BAP lift      Ví dụ: - buys (X, “computer games”)  buys (X, “videos”) - [support = 40%, confidence = 66%]. - P(game)=0.60, P(video)=0.75 - P(game,video)= 0.4 78 Từ phân tích sự kết hợp đến phân tích sự tương quan  Lift của luật trên được tính như sau:  Vì lift <1 nên có sự tương quan nghịch giữa sự có mặt giữa game và video. Sự tương quan nghịch như thế này không thể được xác định bởi support– confidence 79 Từ phân tích sự kết hợp đến phân tích sự tương quan  Độ đo 2 (Chi-square): kiểm tra sự độc lập giữa A và B dựa trên giá trị mong đợi và giá trị quan sát được  all_confidence: kiểm tra luật dựa trên trị support cực đại  cosine: giống lift tuy nhiên loại bỏ sự phụ thuộc vào tổng số giao dịch hiện có. all_confidence và cosine tốt cho tập dữ liệu, không phụ thuộc các giao dịch mà không chứa bất kỳ itemsets đang kiểm tra (null-transactions) all_confidence và cosine là các độ đo null-invariant 80 Từ phân tích sự kết hợp đến phân tích sự tương quan  Khai phá luật kết hợp - Được xem như là một trong những đóng góp quan trọng nhất từ cộng đồng cơ sở dữ liệu trong việc khám phá tri thức  Các dạng luật: luật kết hợp luận lý/luật kết hợp lượng số, luật kết hợp đơn chiều/luật kết hợp đa chiều, luật kết hợp đơn mức/luật kết hợp đa mức, luật kết hợp/luật tương quan thống kê  Các dạng phần tử (item)/mẫu (pattern): Frequent itemsets/subsequences/substructures, Closed frequent itemsets, Maximal frequent itemsets, Constrained frequent itemsets, Approximate frequent itemsets, Top-k frequent itemsets  Khám phá các frequent itemsets: giải thuật Apriori và giải thuật FP-Growth dùng FP-tree 81 Tóm tắt