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

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
Nội dung trích xuất từ tài liệu:
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ề độ ti ...