Khai Phá Dữ Liệu-Phát hiện các luật kết hợp

Chia sẻ: Trần Ngọc Phương | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

161
lượt xem 42
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với một tập các giao dịch transactions) cho trước, cần ộ ập g ị ( ) , n tìm các luật dự đoán khả năng xuất hiện trong một giao dịch của các mục (items) này dựa trên việc xuất hiện của các mục khác

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khai Phá Dữ Liệu-Phát hiện các luật kết hợp

Khai Phá Dữ Liệu Nguyễn Nhật Quang quangnn-fit@mail.hut.edu.vn Viện Công nghệ Thông tin và Truyền thông Trường Đại học Bách Khoa Hà Nội Năm học 2010-2011
Nội dung môn học: Giới thiệu về Khai phá dữ liệu Giới thiệu về công cụ WEKA Tiền xử lý dữ liệu Phát hiện các luật kết hợp Các kỹ thuật phân lớp và dự đoán thu phân và Các kỹ thuật phân nhóm Khai Phá Dữ Liệu 2
Phát hiện các luật kết hợp – Giới thiệu Bài toán phát hiện luật kết hợp (Association rule mining) Với một tập các giao dịch (transactions) cho trước, cần tìm các luật dự đoán khả năng xuất hiện trong một giao dịch của các mục (items) này dựa trên việc xuất hiện của các mục khác Các ví dụ của luật kết hợp: TID Items 1 Bread, Milk {Diaper} → {Beer} 2 Bread, Diaper, Beer, Eggs {Milk, Bread} → {Eggs, Coke} 3 Milk, Diaper, Beer, Coke {Beer, Bread} → {Milk} 4 Bread, Milk, Diaper Beer Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Khai Phá Dữ Liệu 3
Các định nghĩa cơ bản (1) Tập mục (Itemset) Một tập hợp gồm một hoặc nhiều mục Ví dụ: {Milk, Bread, Diaper} TID Items Tập mục mức k (k-itemset) 1 Bread, Milk Một tập mục gồm k mục 2 Bread Diaper Beer Eggs Bread, Diaper, Beer, Eggs Tổng số hỗ trợ (Support count) σ (S 3 Milk, Diaper, Beer, Coke Số lần xuất hiện của một tập mục 4 Bread, Milk, Diaper, Beer Ví dụ: σ({Milk, Bread, Diaper}) = 2 5 Bread Milk Diaper Coke Bread, Milk, Diaper, Coke Độ hỗ trợ (Support) s Tỷ lệ các giao dịch chứa một tập mục Ví dụ: s({Milk, Bread, Diaper}) = 2/5 Tập mục thường xuyên (Frequent/large itemset) Một tập mục mà độ hỗ trợ lớn hơn hoặc bằng một giá trị ngưỡng minsup Khai Phá Dữ Liệu 4
Các định nghĩa cơ bản (2) Luật kết hợp (Association TID Items rule) 1 Bread, Milk Một biểu thức kéo theo có 2 Bread, Diaper, Beer, Eggs dạng: X → Y, trong đó X và Y 3 Milk, Diaper, Beer, Coke là các tập mục 4 Bread, Milk, Diaper, Beer Ví dụ: {Milk, Diaper} → {Beer} {Milk Diaper} 5 Bread, Milk, Diaper, Coke Các độ đo đánh giá luật Độ hỗ trợ (Support) s {Milk , Diaper} → Beer Tỷ lệ các giao dịch chứa cả X và Y đối với tất cả các σ ( Milk , Diaper, Beer ) 2 s= = = 0 .4 giao dịch |T| 5 Độ tin cậy (Confidence) c σ (Milk, Diaper, Beer) 2 Tỷ lệ các giao dịch chứa cả c= = = 0.67 X và Y đối với các giao dịch σ (Milk, Diaper) 3 chứa X ch Khai Phá Dữ Liệu 5
Phát hiện các luật kết hợp Với một tập các giao dịch T, mục đích của bài toán phát hiện luật kết hợp là tìm ra tất cả các luật có: hi lu là tìm ra các lu có: độ hỗ trợ ≥ giá trị ngưỡng minsup, và độ tin cậy ≥ giá trị ngưỡng minconf Cách tiếp cận vét cạn (Brute-force) Liệt kê tất cả các luật kết hợp có thể Tính toán độ hỗ trợ và độ tin cậy cho mỗi luật độ độ ti Tí Loại bỏ đi các luật có độ hỗ trợ nhỏ hơn minsup hoặc có độ tin cậy nhỏ hơn minconf ⇒ Phương pháp vét cạn này có chi phí tính toán quá lớn, không áp dụng được trong thực tế! Khai Phá Dữ Liệu 6
Phát hiện luật kết hợp Các luật kết hợp: TID Items 1 Bread, Milk {Milk, Diaper} → {Beer} (s=0.4, c=0.67) {Milk, Beer} → {Diaper} 2 Bread, Diaper, Beer, Eggs Di (s=0.4, c=1.0) {Diaper, Beer} → {Milk} (s=0.4, c=0.67) 3 Milk, Diaper, Beer, Coke {Beer} → {Milk, Diaper} (s=0.4, c=0.67) 4 Bread, Milk, Diaper, Beer {Diaper} → {Milk, Beer} Beer} (s=0.4, c=0.5) (s 5 Bread, Milk, Diaper, Coke {Milk} → {Diaper, Beer} (s=0.4, c=0.5) Tất cả các luật trên đều là sự phân tách (thành 2 tập con) của cùng tập mục : {Milk, Diaper, Beer} Các luật sinh ra từ cùng một tập múc sẽ có cùng độ hỗ trợ, nhưng có thể khác về độ tin cậy độ tin nh có th khác Do đó, trong quá trình phát hiện luật kết hợp, chúng ta có thể tách riêng 2 yêu cầu về độ hỗ trợ và độ tin cậy Khai Phá Dữ Liệu 7
Phát hiện luật kết hợp Quá trình phát hiện luật kết hợp sẽ gồm 2 bước (2 giai đoạn) quan trọng: quan tr Sinh ra các tập mục thường xuyên (frequent/large itemsets) Sinh ra tất cả các tập mục có độ hỗ trợ ≥ minsup Sinh ra các luật kết hợp Từ mỗi tập mục thường xuyên (thu được ở bước trên), sinh ra tất cả các luật có độ tin cậy cao (≥ minconf) các lu có độ tin cao Mỗi luật là một phân tách nhị phân (phân tách thành 2 phần) của một tập mục thường xuyên Bước sinh ra các tập mục thường xuyên (bước thứ 1) vẫn có chi phí tính toán quá cao! Khai Phá Dữ Liệu 8
Lattice biểu diễn các tập mục cần xét null Với d mục, thì A B C D E phải xét đế đến 2d AB AC AD AE BC BD BE CD CE DE các tập mục có thể! th ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE Khai Phá Dữ Liệu 9
Sinh ra các tập mục thường xuyên TID Items 1 Bread, Milk Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Phương pháp vét cạn (Brute-force) Ph pháp vét (Brute Mỗi tập mục trong lattice đều được xét Tính độ hỗ trợ của mỗi tập mục, bằng cách duyệt qua tất cả các giao dịch Với mỗi giao dịch, so sánh nó với mỗi tập mục được xét Độ phức tạp ~ O(N.M.w) Với M = 2d, thì độ phức tạp này là quá lớn! Khai Phá Dữ Liệu 10
Các chiến lược sinh tập mục thường xuyên Giảm bớt số lượng các tập mục cần xét (M) Tìm kiếm (xét) đầy đủ: M=2d Sử dụng các kỹ thuật cắt tỉa (pruning) để giảm giá trị M Giảm bớt số lượng các giao dịch cần xét (N) Giảm giá trị N, khi kích thước (số lượng các mục) của tập mục tăng lên Giảm bớt số lượng các so sánh (matchings/comparisons) giữa các tập mục và các giao dịch (N.M) Sử dụng các cấu trúc dữ liệu phù hợp (hiệu quả) để lưu các tập mục cần xét hoặc các giao dịch Không cần phải so sánh mỗi tập mục với mỗi giao dịch ph so sánh giao Khai Phá Dữ Liệu 11
Giảm bớt số lượng các tập mục cần xét Nguyên tắc của giải thuật Apriori – Loại bỏ (prunning) dựa trên độ hỗ trợ trên độ tr Nếu một tập mục là thường xuyên, thì tất cả các tập con (subsets) của nó đều là các tập mục thường xuyên Nếu một tập mục là không thường xuyên (not frequent), thì tất cả là không th xuyên (not frequent) thì các tập cha (supersets) của nó đều là các tập mục không thường xuyên Nguyên tắc của giải thuật Apriori dựa trên đặc tính không đơn điệu (anti-monotone) của độ hỗ trợ ∀X , Y : ( X ⊆ Y ) ⇒ s( X ) ≥ s(Y ) Độ hỗ trợ của một tập mục nhỏ hơn độ hỗ trợ của các tập con của nó Khai Phá Dữ Liệu 12
Apriori: Loại bỏ dựa trên độ hỗ trợ Tập mục không không thường xuyên Các tập cha của tập mục đó (AB) bị loại bỏ (AB) lo Khai Phá Dữ Liệu 13
Apriori: Loại bỏ dựa trên độ hỗ trợ Các tập mục mức 1 (1-itemsets) Item Count Bread 4 Coke 2 Các tập mục mức 2 (2- Milk 4 Itemset Count itemsets) Beer 3 {Bread,Milk} 3 Diaper 4 {Bread,Beer} 2 (Không cần xét các tập xét các Eggs 1 {Bread,Diaper} 3 mục có chứa mục Coke {Milk,Beer} 2 hoặc Eggs) {Milk,Diaper} 3 {Beer,Diaper} 3 minsup = 3 Các tập mục mức 3 (3-itemsets) •Nếu xét tất cả các tập mục có thể: Ite m s e t C ount 6C + 6C + 6C = 41 1 2 3 { B r e a d ,M ilk ,D ia p e r } 3 •Với cơ chế loại bỏ dựa trên độ hỗ trợ: 6 + 6 + 1 = 13 Khai Phá Dữ Liệu 14
Giải thuật Apriori Sinh ra tất cả các tập mục thường xuyên mức 1 (frequent 1-itemsets): các tập mục thường xuyên chỉ chứa 1 mục các th xuyên ch ch Gán k = 1 Lặp lại, cho đến khi không có thêm bất kỳ tập mục thường xuyên nào mới Từ các tập mục thường xuyên mức k (chứa k mục), sinh ra các tập mục mức mức (k+1) cần xét (k xét Loại bỏ các tập mục mức (k+1) chứa các tập con là các tập mục không thường xuyên mức k Tính độ hỗ trợ của mỗi tập mục mức (k+1), bằng cách duyệt qua độ tr (k+1) cách duy qua tất cả các giao dịch Loại bỏ các tập mục không thường xuyên mức (k+1) Thu đượ các Thu được các tập mục thường xuyên mức (k+1) th xuyên (k+1) Khai Phá Dữ Liệu 15
Giảm bớt số lượng các so sánh Các so sánh (matchings/comparisons) giữa các tập mục cần xét và các giao dịch Cần phải duyệt qua tất cả các giao dịch, để tính độ hỗ trợ của mỗi tập mục cần xét Để giảm bớt số lượng các so sánh, cần sử dụng cấu trúc băm (hash structure) để lưu các tập mục cần xét Thay vì phải so sánh mỗi giao dịch với mỗi tập mục cần xét, thì chỉ cần so sánh nó với các tập mục chứa trong các ô (hashed buckets) TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Khai Phá Dữ Liệu 16
Sinh ra cây băm (hash tree) Giả sử chúng ta có 15 tập mục mức 3 cần xét: {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8} 5} {3 6} {3 7} {6 9} {3 7} {3 8} Sinh ra cây băm (Hash tree): Hàm băm (Hash function) – Ví dụ: h(p) = p mod 3 Kích thước tối đa của nút lá (Max leaf size): Số lượng tối đã các tập mục được lưu ở một nút lá (Nếu số lượng các tập mục vượt quá giá trị này, nút đó sẽ tiếp tục bị phân chia) – Ví dụ: Max leaf size = 3 234 (Hàm băm) 567 3,6,9 1,4,7 367 145 356 345 136 368 357 2,5,8 689 124 125 159 457 458 Khai Phá Dữ Liệu 17
Phát hiện luật kết hợp bằng cây băm (1) (Hàm băm) Cây băm lưu các tập mục cần xét 1,4,7 3,6,9 2,5,8 234 567 145 136 Băm 345 356 367 (hash) 357 368 đố đối với 689 1, 4, 124 159 125 hoặc 7 457 458 Khai Phá Dữ Liệu 18
Phát hiện luật kết hợp bằng cây băm (2) (Hàm băm) Cây băm lưu các tập mục cần xét 1,4,7 3,6,9 2,5,8 234 567 145 136 345 356 367 Băm 357 368 (h (hash) 689 đối với 124 159 125 2, 5, 457 458 hoặc 8 ho Khai Phá Dữ Liệu 19
Phát hiện luật kết hợp bằng cây băm (3) (Hàm băm) Cây băm lưu các tập mục cần xét 1,4,7 3,6,9 2,5,8 234 567 145 136 345 356 367 Băm 357 368 (hash) (hash) đối với 689 124 159 125 3, 6, 457 hoặc 9 458 Khai Phá Dữ Liệu 20