Khai phá dữ liệu - Chương 2 LUẬT KẾT HỢP

Phân tích việc mua hàng của khách hàng bằng cách tìm ra những “mối kết hợp” giữa những mặt hàng mà khách đã mua. Bài toán được Agrawal thuộc nhóm nghiên cứu của IBM đưa ra vào năm 1994. Khai phá luật kết hợp: Tìm tần số mẫu, mối kết hợp, sự tương quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác. Tính hiểu được: dễ hiểu Tính sử dụng được: Cung cấp thông tin thiết thực Tính hiệu quả: Đã có...
Nội dung trích xuất từ tài liệu:
Khai phá dữ liệu - Chương 2 LUẬT KẾT HỢP Chương 2 LUẬT KẾT HỢP (Association Rules) 1 Bài toán phân tích giỏ hàng • Phân tích việc mua hàng của khách hàng bằng cách tìm ra những “mối kết hợp” giữa những mặt hàng mà khách đã mua. • Bài toán được Agrawal thuộc nhóm nghiên cứu của IBM đưa ra vào năm 1994. 2 01/18/13 www.lhu.edu.vn Luật kết hợp: Cơ sở Khai phá luật kết hợp: – Tìm tần số mẫu, mối kết hợp, sự tương quan, hay các cấu trúc nhân quả giữa các tập đối tượng trong các cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ, và những kho thông tin khác. Tính hiểu được: dễ hiểu Tính sử dụng được: Cung cấp thông tin thiết thực Tính hiệu quả: Đã có những thuật toán khai thác hiệu quả Các ứng dụng: – Phân tích bán hàng trong siêu thị, cross-marketing, thi ết k ế catalog, loss-leader analysis, gom cụm, phân lớp, ... 3 Luật kết hợp: Cơ sở Định dạng thể hiện đặc trưng cho các luật kết hợp: – khăn ⇒ bia [0.5%, 60%] – mua:khăn ⇒ mua:bia [0.5%, 60%] – “Nếu mua khăn thì mua bia trong 60% trường hợp. Khăn và bia được mua chung trong 0.5% dòng dữ liệu. Các biểu diễn khác: – mua(x, “khăn) ⇒ mua(x, “bia) [0.5%, 60%] – khoa(x, CS) ^ học(x, DB) ⇒ điểm(x, A) [1%, 75%] 4 Luật kết hợp: Cơ sở khăn ⇒ bia [0.5%, 60%] “NẾU mua khăn THÌ mua bia 1 2 3 4 trong 60% trường hợp trên 0.5% dòng dữ liệu Tiền đề, ề vế trái luật Mệnh đề kết quả, ả vế phải luật Support độ hỗ trợ/ủng hộ (“trong bao nhiêu phần trăm dữ Support, liệu thì những điều ở vế trái và vế phải cùng xảy ra) Confidence độ mạnh (“nếu vế trái xảy ra thì có bao nhiêu Confidence, khả năng vế phải xảy ra) 5 2.1 C¸c kh¸I niÖm Cho I = {I1 , I2 , . . . , Im }lµ tËp c¸c ®¬n vÞ dỮ liÖu. Cho D lµ tËp c¸c giao t¸c, mçi giao t¸c T lµ tËp c¸c ®¬n vÞ d dữ liÖu sao cho T ⊆ I ÑÞnh nghÜa 1: Ta gäi giao t¸c T chøa X, víi X lµ tËp c¸c ®¬n vÞ dữ liÖu cña I, nÕu X ⊆ T ÑÞnh nghÜa 2: Mét luËt kÕt hîp lµ mét phÐp suy diÔn cã d¹ng X → Y, trong ®ã X ⊂ I, Y ⊂ I vµ X∩Y =∅ ÑÞnh nghÜa 3: Ta gäi luËt X → Y cã møc x¸c nhËn(support) lµ s trong tËp giao t¸c D, nÕu cã s% giao t¸c trong D chøa X∪Y. Ký hiÖu: Supp(X → Y) =s 6 2.1 C¸c kh¸I niÖm (Tieáp) ÑÞnh nghÜa 4:Ta gäi luËt X → Y lµ cã ®é tin cËy c (Confidence) trªn tËp giao t¸c D, Ký hiÖu: c=Conf(X → Y) =Supp(X →Y)/Supp(X) NhËn xÐt: C¸c x¸c nhËn vµ ®é tin cËy chÝnh lµ c¸c x¸c suÊt sau: Supp(X → Y)=P(X∪Y) : X¸c suÊt cña X∪Y trong D Conf(X → Y) =P(Y/X): X¸c suÊt cã ®iÒu kiÖn ÑÞnh nghÜa 5: Cho tr­íc Min_Supp=s0 vµ Min_Conf=c0 Ta gäi luËt X → Y lµ xaû ra nÕu tháa: 7 Ví dụ 1: Xét CSDL sau Ngµy T_ID C¸c ®¬n vÞ d­ liÖu D1 t1 A     D E   t2 A         F t3 A B   D E   D2 t4 A B C   E   t5       D   F t6 A   C D E   D3 t7   B   D E   t8 A     D   F t9   B C   E   D4 t10   B C   E F t11   B C     F t12 A     D     8 Ta cã: Supp(A→D)=5/12=41.66%, Conf(A→D)=5/7 Supp(B → D)=2/12=17%, Conf(B → D )=2/6=33.3% Supp(D → F) =2/12 vµ Conf(D → F) =2/7=28.5% Supp(F→D)=2/12 vµ Conf(F→D)=2/5 Supp(AC→E)=17% Conf(AC→E)=100% Supp(E→AC)=17% Conf(E→AC)=2/7=28.5% 9 2.1 Thuật toán Apriori Nhận xét 1: * Hai bước chính của bài toán khai thác dữ liệu dựa trên các luật kết hợp: 1. Tạo ra tất cả tập đơn vị dữ liệu thường xuyên xảy ra (thoả ngưỡng là Min_Sup). 2. Từ tập các đơn vị dữ liệu thường xuyên xảy ra Y = {I1, I2, . . ., Ik } với k >= 2, sinh ra các luật tạo ra từ các đơn vị dữ liệu này bằng cách tỡm các tập con của mỗi tập đơn vị dữ liệu và tính các độ tin cậy của chúng như trên. 10 2.1 Thuật toán Apriori Cách tiếp cận của thuật toán Apriori dựa trên nhận xét sau: Nếu bất kỳ tập k-đvdl nào là không phổ biến thì bất kỳ tập (k+1)-đvdl chứa chúng cũng sẽ không phổ biến, và ngược lại: Nếu bất kỳ tập k-đvdl nào là phổ biến thì mọi tập con của nó là phổ biến. 11 2.1 Thuật toán Apriori Ký hiệu: - Ta gọi số đơn vị dữ liệu trong một tập hợp là số các phần tử của chúng và tập có k phần tử là k- đơn vị dữ liệu - Gọi Lk: Tập hợp các tập phổ biến gồm các k-đvdl. Mỗi phần tử gồm 2 trường: i) các đơn vị dữ liệu và ii) đếm số lần xuất hiện. - Ck : Tập hợp các tập ứng viên k- đơn vị dữ liệu. Mỗi phần tử gồm 2 trường: i) các đơn v ...