Bài giảng Chương 4 - Khai phá luật kết hợp

Dưới đây là bài giảng Chương 4 - Khai phá luật kết hợp. Mời các bạn tham khảo bài giảng để hiểu rõ hơn về khai phá luật kết hợp; các thuật toán khai phá vô hướng luật kết hợp (giá trị lôgic đơn chiều) trong CSDL giao dịch; khai phá kiểu đa dạng luật kết hợp/tương quan; khai phá kết hợp dựa theo ràng buộc; khai phá mẫu dãy.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 4 - Khai phá luật kết hợp Chương4: Khaipháluậtkếthợp Dựatheo“DataMining:ConceptsandTechniques” Chapter6.MiningAssociationRulesinLargeDatabases ©JiaweiHanandMichelineKamber www.cs.uiuc.edu/~hanjSeptember21,2015 1 Chương4:Khaipháluậtkếthợp  Khaipháluậtkếthợp(Associationrule)  Cácthuậttoánkhaiphávôhướngluậtkếthợp(giátrị lôgicđơnchiều)trongCSDLgiaodịch  Khaiphákiểuđadạngluậtkếthợp/tươngquan  Khaiphákếthợpdựatheoràngbuộc  KhaiphámẫudãySeptember21,2015 2Kháiniệmcơsở:Tậpphổbiếnvàluậtkếthợp Mộtsốvídụvề“luậtkếthợp”(associaterule) •“98%kháchhàngmàmuatạpchíthểthao thìđều mua các tạp chí về ôtô”  sự kết hợp giữa “tạp chí thể thao”với“tạpchívềôtô” •“60% khách hàng mà mua bia tại siêu thị thì đều mua bỉmtrẻem”sựkếthợpgiữa“bia”với“bỉmtrẻem” •“Cótới70%ngườitruynhậpWebvàođịachỉUrl1thì cũngvàođịachỉUrl2trongmộtphiêntruynhậpweb”  sự kếthợp giữa “Url1”với “Url2”.Khaiphádữliệu sửdụngWeb(Dữliệutừfilelogcủacácsite,chẳnghạn đượcMScungcấp). •Các Url có gắn với nhãn “lớp” là các đặc trưng thì có luậtkếthợpliênquangiữacáclớpUrlnày.September21,2015 3Kháiniệmcơsở:Tậpphổbiếnvàluậtkếthợp [IV06] RenátaIváncsy,IstvánVajk(2006).FrequentPatternMininginWebLogData, ActaPolytechnicaHungarica,3(1):7790,2006September21,2015 4 Kháiniệmcơsở:TậpphổbiếnvàluậtkếthợpCơsởdữliệugiaodịch(transactiondatabase) • Giaodịch:danhsáchcácmặthàng(mục:item)trongmộtphiếumuahàng củakháchhàng.GiaodịchTlàmộttậpmục. • TậptoànbộcácmụcI={i1,i2,…,ik}“tấtcảcácmặthàng”.Mộtgiaodịch TlàmộttậpconcủaI:T I.MỗigiaodịchTcómộtđịnhdanhlàTID. • AlàmộttậpmụcA IvàTlàmộtgiaodịch:GọiTchứaAnếuA T. • ĐộhỗtrợcủaA(s(A))làxácsuấtxuấthiệnAtrongD:s(A)=|T D,T A} • minsup>0(độhỗtrợtốithiểu),Alà“phổbiến”((frequent)):s(A) minsup• Luậtkếthợp • GọiA Blàmột“luậtkếthợp”nếuA I,B IvàA B= . • LuậtkếthợpA Bcóđộhỗtrợ(support): s(A B)=s(AB),A Blàphổ biến nếuABphổbiến.LuậtkếthợpA Bcóđộtincậy(confidence) c trong CSDL D nếu trong D có c% các giao dịch T A T B: xác suất P(B|A). • Support(A B) =P(A B) :1 s(A B) 0 • Confidence(A B)=P(B|A) :1 c(A B) 0 • September21,2015 5Kháiniệmcơbản:Mẫuphổbiếnvàluậtkếthợp  Tập mục I={i1, …, ik}. CSDL giao dịch D = {d I}Transactionid Itemsbought  A, B I, A B= : A B là luật kết hợp 10 A,B,C  Bài toán tìm luật kết hợp. 20 A,C Cho trước độ hỗ trợ tối thiểu s>0, độ 30 A,D tin cậy tối thiếu c>0. Hãy tìm mọi luật 40 B,E,F kết hợp mạnh XY. Customer Giảsửmin_support=50%, Customer buysboth buysdiaper min_conf=50%: AC(50%,66.7%) CA(50%,100%)  Hãy trình bày các nhận xét về khái niệm luật kết hợp với khái niệm phụ Customer thuộc hàm. buysbeer  Các tính chất Armstrong ở đây.September21,2015 6 Mộtvídụtìmluậtkếthợp Transactionid Itemsbought Min.support50% 10 A,B,C Min.confidence50% 20 A,C Frequentpattern Support 30 A,D {A} 75% 40 B,E,F ...