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

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:57

Thêm vào BST

Báo xấu

167
lượt xem 50
download

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

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ó...

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 - 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ị dữ liệu và ii) đếm số lần xuất hiện. 12
Thuật toán Apriori dựa trên các thủ tục sau Procedure 1: Tạo ra các tập phổ biến Begin L1 = {tập phổ biến1-đvdl}; for ( k = 2; Lk-1 ≠ ∅; k++ ) do begin Ck = Tạo ra tập ứng viên từ(Lk-1); for mỗi giao tác t ∈ D do begin Ct = Tập con của (Ck) chứa t for mỗi c ∈ Ct do c.count++; end Lk = {c ∈ Ck | c.count ≥ Min_Supp*|D|} end Return (∪ k Lk); 13
Thuật toán Apriori dựa trên các thủ tục sau Procedure 2: Tìm ra tất cả các luật kết hợp begin Result = ∅ for mỗi tập xảy ra thường xuyên X∈L do begin for mỗi a ⊂ X sao cho a ≠ ∅ do if(Mức xác nhận(X)/Mức xác nhận(a)>=Min_Conf) then Result = Result ∪{a → (X-a)} end return Ressult end 14
Trong ví dụ 1, với Min_Conf=c0=70% và Min_Supp =s0=40% - Ta có tập L gồm các tập đơn vị dữ liệu xảy ra thường xuyên như sau: L = {{A}, {B}, {C}, {D}, {E}, {F}, {AD}, {BE}, {CE}, {DE}} Có các luật kết hợp như sau: A→D với c=71.42% và s=41.66% D→A với c=71.42% và s=41.66% B→E với c=83.33% và s=41.66% E→B với c=71.42% và s=41.66% 15
Luật kết hợp: Cơ sở Mức xác nhận tối thiểu σ / S0 : (minsupp) – Cao ⇒ ít tập phần tử (itemset) phổ biến ⇒ ít luật hợp lệ rất thường xuất hiện – Thấp ⇒ nhiều luật hợp lệ hiếm xuất hiện Độ tin cậy tối thiểu γ / C0 : (minconf) – Cao ⇒ ít luật nhưng tất cả “gần như đúng" – Thấp ⇒ nhiều luật, phần lớn rất “không chắc chắn" Giá trị tiêu biểu: σ = 2 -10 %, γ = 70 - 90 % 16
Luật kết hợp: Cơ sở Giao tác: – Dạng quan hệ Dạng kết Item và itemsets: phần tử đơn lẻ và tập phần tử Support của tập I: số lượng giao tác có chứa I Min Support σ: ngưỡng cho support Tập phần tử phổ biến: có độ ủng hộ (support) ≥ σ 17
Luật kết hợp: Cơ sở Cho: (1) CSDL các giao tác, (2) mỗi giao tác là một danh sách mặt hàng được mua (trong một lượt mua của khách hàng)Frequent item sets ID của giao tác Hàng mua Tập phổ biến support 100 A,B,C {A} 3 or 75% 200 A,C {B} và {C} 2 or 50% 400 A,D {D}, {E} và {F} 1 or 25% 500 B,E,F {A,C} 2 or 50% Các cặp khác max 25% Tìm: tất cả luật có support >= minsupport • If min. support 50% and min. confidence 50%, then A ⇒ C [50%, 66.6%], C ⇒ A [50%, 100%] 18
Tạo ứng viên Apriori Nguyên tắc Apriori: Những tập con của tập phổ biến cũng phải phổ biến L3={abc, abd, acd, ace, bcd} Tự kết: L3*L3 – abcd từ abc và abd – acde từ acd và ace Rút gọn: – acde bị loại vì ade không có trong L3 C4={abcd} 19
Ví dụ về Apriori (1/6) Database D C1 L1 Tập Độ ủng hộ ID giao tác Phần tử Tập Độ ủng hộ {1} 2 100 134 {1} 2 {2} 3 200 2 3 5 Duyệt D {2} 3 {3} 3 300 1235 {3} 3 {4} 1 400 25 {5} 3 {5} 3 20