Chương 1: Luật kết hợp. Trong chương này tôi đã trình bày những nét khái quát nhất về khai phá dữ liệu bằng luật kết hợp thông qua việc đưa ra các khái niệm, định nghĩa và bài toán tìm luật kết hợp. Những thuật toán điển hình của luật kết hợp như thuật toán Apriori và một vài thuật toán khác cũng được đề cập để giải quyết bài toán. Chương 2: Luật kết hợp mờ với toán tử có ngưỡng.
Ở phần đầu của chương tôi trình bày các khái niệm liên quan đến tập mờ để từ đó làm cơ sở đưa vào bài toán khai phá luật kết hợp. Với các bài toán có thuộc tính số và hạng mục thì việc rời rạc hóa dữ 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu liệu có thể xảy ra một vài nhược điểm như vấn đề “điểm biên gãy”. Vì thế luật kết hợp mờ là một giải pháp rất hiệu quả. Phần cuối chương là các khái niệm về các toán tử có ngưỡng và đưa ra bài toán xây dựng luật kết hợp mờ với các toán tử có ngưỡng.
Chương 3: Cài đặt thử nghiệm: Là phần cài đặt thử nghiệm chương trình dùng dữ liệu về việc sử dụng internet. Kết luận: Phần này nêu lại những việc đã thực hiện và kết quả đạt được của luận văn, vấn đề còn chưa được giải quyết thấu đáo và một số hướng nghiên cứu trong tương lai. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu 1. CHƢƠNG 1 - LUẬT KẾT HỢP Luật kết hợp là một lĩnh vực quan trọng trong khai phá dữ liệu và vì thế kỹ thuật khai phá luật kết hợp ngày càng được quan tâm và phát triển mạnh trong những năm trở lại đây, trở thành một hướng nghiên cứu lớn.
Trong chương này, chúng ta cùng tìm hiểu các khái niệm cơ sở và các thuật toán kinh điển của luật kết hợp. Ý NGHĨA THỰC TIỄN CỦA LUẬT KẾT HỢP Luật kết hợp là những luật có dạng: X Y Trong lĩnh vực bán hàng ta có thể có luật: “40% khách hàng mua cafe thì mua thêm bánh quy, 3% khách hàng mua cả cafe và bánh quy” Ở ví dụ này diễn tả mối quan hệ giữa cafe và bánh quy hay ta có luật X Y tương đương với cafe bánh quy. Cafe là tiền đề của luật và bánh quy là kết quả của luật. Các hệ số 40% và 3% là các độ đo của luật - 40% là độ tin cậy của luật: trong những khách hàng mua cafe có 40% mua thêm bánh quy - 3% là độ hỗ trợ của luật: trong tất cả khách hàng mua ở cửa hàng có 3% mua cả 2 mặt hàng là cafe và bánh quy.
Các số này ta sẽ định nghĩa cụ thể ở các phần dưới 1. MÔ HÌNH HÌNH THỨC CỦA VẤN ĐỀ PHÁT HIỆN LUẬT 1. Thuộc tính và CSDL - I = {I1, I2, …,In} là tập tất cả các mục (Item) hay được gọi là tập tất cả các thuộc tính (attributes) mỗi một thuộc tính Ii với i = 1, n được gọi là 1 mục dữ liệu - X = {Ix1, Ix2,…,Ixp} I là 1 tập thuộc tính (Itemset) - D = (T1, T2, …, Tm) là cơ sở dữ liệu trên I, là tập tất cả các tác vụ (transaction) hay được gọi là tập các bản ghi. Mỗi bản ghi Tk với k = 1, m đều có định danh (TID- Transaction Identification) và nó là một tập các thuộc tính Tk I với k = 1, m Ta có Tk(Iv) xác định giá trị của thuộc tính Iv.
Ví dụ: nếu xét thuộc tính phân, Tk(Iv) = 1 nghĩa là khách hàng Tk chọn mua mặt hàng 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu Iv, Tk(Iv) = 0 nếu khách hàng Tk không chọn mua hàng Iv). - Một luật kết hợp có dạng X Y Trong đó: + X I là tiền đề của luật + Y I là hệ quả của luật, +XY= biểu thị mối quan hệ giữa tập thuộc tính X và tập thuộc tính Y. Vì vậy có thể nói luật kết hợp biểu thị mối quan hệ giữa các tập con của I Độ hỗ trợ và độ tin cậy là 2 thước đo của 1 luật kết hợp 1. Độ hỗ trợ của một tập thuộc tính Cho một tập thuộc tính X I, cơ sở dữ liệu D Độ hỗ trợ (support) của tập thuộc tính X trong cơ sở dữ liệu D (Ký hiệu supp(X)) là tỷ lệ % giữa số bản ghi trong cơ sở dữ liệu D chứa tập thuộc tính X với tổng số các bản ghi trong cơ sở dữ liệu D.
| {Tk D \ X Tk | Supp( X ) <1. Tập phổ biến (Frequent Itemset): Cho một tập thuộc tính X I trong cơ sở dữ liệu D và ngưỡng hỗ trợ tối thiểu minsupp (0,1] (minsupp - Minimum Support) được xác định bởi người sử dụng. Một tập thuộc tính X được gọi là tập phổ biến theo ngưỡng minsupp khi và chỉ khi độ hỗ trợ của nó lớn hơn hoặc bằng ngưỡng minsupp X I là tập phổ biến supp(X) minsupp Ký hiệu: FX(D, minsupp) là tập hợp các tập phổ biến theo ngưỡng minsupp FX( D, minsupp) = {X I \supp(X) minsupp} 1. Độ hỗ trợ của luật r = X Y Độ hỗ trợ của luật được tính bằng công thức: Supp (r) = supp(XY) <1.
Độ tin cậy của luật: r = X Y Độ tin cậy của luật r trong cơ sở dữ liệu D (Ký hiệu là conf(r)) là tỷ lệ % giữa số bản ghi trong D chứa tập thuộc tính X thì cũng chứa tập thuộc tính Y. Về mặt xác suất độ tin cậy của luật r là xác suất có điều kiện xảy ra Y với điều kiện đã xảy ra X 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu Tk D \ X Tk , Y Tk conf (r ) Tk D \ X Tk Tk D \ X Y Tk <1.3> Tk D \ X Tk Tk D \ X Y Tk D D Tk D \ X Tk supp( X Y ) supp( X ) 1. Luật kết hợp mạnh: Luật r = X Y được gọi là luật kết hợp mạnh theo ngưỡng độ hỗ trợ tối thiểu minsupp (0,1] và độ tin cậy tối thiểu minconf (0,1] (Minimum Confidence) khi và chỉ khi độ hỗ trợ của luật lớn hơn hoặc bằng độ hỗ trợ tối thiểu và độ tin cậy của luật lớn hơn hoặc bằng độ tin cậy tối thiểu. Bài toán luật kết hợp Người ta chỉ quan tâm đến luật kết hợp mạnh theo ngưỡng minsupp và minconf cho trước.
Chính vì vậy bài toán khai phá luật kết hợp thường chia làm 2 pha: 1- Tìm tất cả các tập phổ biến (FX) trong cơ sở dữ liệu, nghĩa là tìm tất cả các tập thuộc tính X sao cho supp(X) minsupp 2- Sinh ra các luật kết hợp mạnh từ các tập phổ biến tìm thấy ở pha 1- Ví dụ 1.1: Bài toán khai phá luật kết hợp Thực hiện bài toán khai phá luật kết hợp ở trên đối với đầu vào: Cho CSDL D = {T1, T2, T3, T4, T5, T6} trên I = {A, B, C, D, E, F} TID Các thuộc tính T1 A, C, E, F T2 B, C, E T3 A, B, D, E 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu T4 A, B, C, E T5 D, F T6 A, C, D Bảng 1.1 CSDL giao dịch (Ví dụ 1.1) Ta lần lượt tìm độ hỗ trợ của các tập thuộc tính. Bắt đầu từ tập có 1 thuộc tính rồi đến 2,3…. Độ hỗ trợ của tập có 1 thuộc tính được tính trong bảng sau theo cách Thuộc tính A có mặt trong 4 bản ghi (T1, T3, T4, T6) của D nên supp (A) = 4/6 = 67,7% Thuộc tính Số bản ghi Độ hỗ trợ supp(X) A 4 67,7% B 3 50,0% C 4 67,7% D 3 50% E 4 67,7% F 2 33,3% Bảng 1.2 Độ hỗ trợ của các thuộc tính (Ví dụ 1.1) Nếu ta chọn độ hỗ trợ tối thiểu minsupp = 50% thì với cách tính tương tự trong bảng 1 ta có danh sách các tập phổ biến Số thuộc tính Danh sách các tập phổ biến 1 {A}, {B}, {C}, {D}, {E} 2 {AC}, {AE}, {BE}, {CE} Bảng 1.3 Danh sách các tập mục phổ biến (Ví dụ 1.1) Từ danh sách tập phổ biến đó các luật kết hợp được đưa ra trong bảng sau: Luật kết hợp Độ tin cậy A→C 75% A→E 75% B→E 100 % C→E 75% Bảng 1.4 Độ tin cậy của các luật sinh từ tập phổ biến (Ví dụ 1.1) Nếu ta chọn độ tin cậy tối thiểu minconf = 80% thì chỉ có luật B → E là luật kết hợp 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Lê Thị Thanh Hải Vấn đề về luật kết hợp mờ và các toán tử có ngưỡng trong khai phá dữ liệu mạnh. Một số tính chất của tập phổ biến và luật kết hợp Với tập phổ biến ta có 3 tính chất sau: Tính chất 1 (độ hỗ trợ của tập con): Nếu A B với A, B là các tập thuộc tính thì supp (A) ≥ supp (B) Điều này là rõ ràng vì tất cả các bản ghi trong D chứa B thì cũng chứa A.
Tính chất 2: Một tập chứa một tập không phổ biến thì cũng là tập không phổ biến Nếu tập A không đủ độ hỗ trợ cực tiểu tức là supp(A) < minsupp thì tập B A cũng không phổ biến vì supp (B) ≤ supp (A) < minsupp (áp dụng tính chất 1) Tính chất 3: Các tập con của tập phổ biến cũng là tập phổ biến Nếu tập B là tập phổ biến trong D, tức là supp (B) ≥ minsupp, mọi tập con A của B cũng là phổ biến trong D, bởi vì supp (A) ≥ supp(B) ≥ minsupp theo tính chất 1. Với luật kết hợp ta có 4 tính chất sau: Tính chất 4. Không hợp các luật kết hợp Nếu có X Z và Y Z trong D thì không nhất thiết X Y Z là đúng.