Slide bài giảng môn Phân tích dữ liệu lớn về nội dung "Khai phá luật kết hợp"

lOMoARcPSD| 36667950 NỘI DUNG
• Giới thiệu bài toán phân tích giỏ hàng • Luật kết hợp • Một số ộ
• Tập mục thường xuyên
• Tổng quan về bài toán khai phá luật kết hợp • Thuật toán Apriori • Sinh luật kết hợp • Nội dung mở rộng
• Hướng dẫn thực hành
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950
BÀI TOÁN PHÂN TÍCH GIỎ HÀNG
•Những mặt hàng nào thường ược khách hàng mua cùng
nhau trong cùng 1 lần mua hàng?
•Nhà quản trị có thể làm gì? – Thiết kế gian hàng
– Lên kế hoạch bán giảm giá cho mặt hàng/nhóm hàng
– Lên kế hoạch tiếp thị/các chiến lược quảng cáo
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 LUẬT KẾT HỢP •Một số ví dụ
– 98% khách hàng mua tạp chí thể thao ều mua các tạp chí về ôtô
• Sự kết hợp giữa “tạp chí thể thao” với “tạp chí về ôtô”
– 60% khách hàng mua bia tại siêu thị ều mua bơ
• Sự kết hợp giữa “bia” và “bơ”
– 70% người dùng vào ịa chỉ ABC cũng vào ịa chỉ XYZ trong một phiên truy nhập web
• Sự kết hợp giữa “ABC” và “XYZ”
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam LUẬT KẾT HỢP
•Khái niệm (association rule)
– Cho 𝐼={𝐼1, 𝐼2, …, 𝐼𝐼} là một tập các mục (mặt hàng)
– Cho D là một tập các giao dịch mà mỗi giao dịch T làmột tập các
mục, 𝐼⊆𝐼 (tập hóa ơn mua hàng)
• Mỗi giao dịch có một mã
ịnh danh riêng gọi là TID
– Cho A là một tập các mục (mặt hàng). Một giao dịch Tược gọi là
chứa A khi và chỉ khi 𝐼⊆𝐼
– Một luật kết hợp ược diễn ạt dưới hình thức 𝐼 ⇒𝐼, với 𝐼⊂𝐼, 𝐼⊂𝐼, và
𝐼∩𝐼=∅ (nếu mua A thì mua B)
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 LUẬT KẾT HỢP •Tiêu chí o lường
– Luật 𝐼⇒𝐼 trong tập D có ộ hỗ trợ (support, s), với s là phần trăm số
giao dịch trong D chứa 𝐼∪𝐼, (cả A và B)
support(𝐼⇒𝐼) = P(𝐼∪𝐼)
– Luật 𝐼⇒𝐼 trong tập D có ộ tin cậy (confidence, c), với c là phần trăm
giao dịch trong D có chứa A thì cũng chứa B
confidence(𝐼⇒𝐼) = P(B|A)
Những luật kết hợp thỏa mãn ộ hỗ trợ tối thiểu (min_sup) và ộ tin
cậy tối thiểu (min_conf) ược gọi là các luật mạnh
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam TẬP MỤC THƯỜNG XUYÊN
• Khái niệm (Frequent itemset)
– Một tập hợp chứa k mục ược gọi là một k-itemset – Ví dụ:
• {computer, antivirus_software} là một 2-itemset
• {banana, milk, bread} là một 3-itemset
– Tần suất xuất hiện của một tập mục là số giao dịch chứa tậpmục ó
(frequency, support count, count)
– Nếu ộ hỗ trợ (support) của một tập mục I lớn hơn hoặc bằng ộ hỗ trợ tối
thiểu (min_sup) thì I ươc gọi là một tập mục thường xuyên.
– Tập hợp các k-itemset thường xuyên
ược ký hiệu là 𝐼_𝐼.
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950
BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP •Phát biểu
– Nếu xem tập chứa tất cả các mục (hay các mặt hàng)tương tự
như một nhà kho hay cửa hàng thì mỗi mục (mặt hàng) sẽ có một
biến kiểu logic (Boolean) thể hiện sự có hàng hay hết hàng của chính mặt hàng ó
– Khi ó mỗi giỏ hàng (basket) có thể ược biểu diễn bằng một vector
giá trị logic, thể hiện sự hiện diện của mặt hàng ó trong giỏ hàng (có/không)
– Các vector này có thể ược phân tích ể tìm ra các mẫu hành vi mua
hàng phản ánh những mặt hàng nào thường ược mua cùng nhau
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam TID A B C D E 10 1 1 1 0 0 11 1 0 1 0 0 12 1 0 1 1 0 TID Items 13 0 1 1 0 1 10 A,B,C 14 1 0 1 0 1 11 A,C 12 A,C,D 13 B,C,E 14 A,C,E
BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP lOMoARcPSD| 36667950
1. Tìm tất cả các tập mục thường gặp (thường xuyên): Mỗi
itemset ược gọi là tập mục thường xuyên nếu ộ hỗ trợ của nó lớn hơn hoặc bằng min_sup
2. Tạo các luật kết hợp mạnh từ các tập mục thường xuyên: Luật
kết hợp mạnh phải có ộ hỗ trợ và ộ tin cậy lớn hơn min_sup và min_conf tương ứng.
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam
BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP Tid Items bought Tập mục I={i1, …, ik}. CSDL giao dịch D = {d I} 10 Beer, Nuts, Diaper
A, B I, A B= : A B là luật kết hợp Bài 20 Beer, Coffee, Diaper
toán tìm luật kết hợp: 30 Beer, Diaper, Eggs
Cho trước ộ hỗ trợ tối thiểu s>0, ộ tin cậy tối 40 Nuts, Eggs, Milk
thiếu c>0. Hãy tìm mọi luật kết hợp mạnh 50
Nuts, Coffee, Diaper, Eggs, Milk X Y. Customer
Giả sử min_support = 50%, min_conf = 50%:
Freq. Pat.: Beer:3, Nuts:3, Diaper:4, Eggs:3, {Beer, Diaper}:3 Beer Diaper (60%, 100%) Diaper Beer (60%, 75%) buys diaper
Chỉ ra các luật kết hợp còn lại
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 Min. support 50% Min. confidence 50% Transaction-id Items bought 10 A, B, C 20 A, C 30 A, D 40 B, E, F Frequent pattern Support {A} 75% {B} 50% {C} 50% {A, C} 50%
BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP •Với luật A C
– support = support({A,C}) = 50% lOMoARcPSD| 36667950
– confidence = support({A,C})/support({A}) = 66.6%
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam THUẬT TOÁN APRIORI •Tổng quan
– Do R. Agrawal và R. Srikant giới thiệu năm 1994
– Khai phá các tập mục thường xuyên cho các luật kếthợp dạng Boolean.
– Chiến lược lặp: các k-itemset ược sử dụng ể khảo sát các (k + 1)- itemset
•Khai phá luật kết hợp gồm hai bước
– Tìm mọi tập phổ biến: theo min-sup
– Sinh luật mạnh từ tập phổ biến
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 THUẬT TOÁN APRIORI • Nguyên lý
– Mọi tập con của tập phổ biến cũng là tập phổ biến
– Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} hay giaodịch
chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}
– Với mọi tập mục không phổ biến thì mọi tập bao không cầnphải sinh ra/kiểm tra! • Phương pháp:
– Sinh các tập mục ứng viên dài (k+1) từ các tập phổ biến cóộ dài k
(Độ dài tập mục là số phần tử của nó),
– Kiểm tra các tập ứng viên theo CSDL
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam THUẬT TOÁN APRIORI •Nguyên tắc quy hoạch ộng
– Từ các tập Fi = {ci| ci tập phổ biến, |ci| = i} gồm mọi tập phổ biến
có ộ dài i với 1 ≤ i ≤ k,
– Tìm tập Fk+1 gồm mọi tập phổ biến có ộ dài k+1.
•Trong thuật toán, các tên mục i1, i2, … in ược sắp xếp theo
một thứ tự cố ịnh (thường ược ánh chỉ số 1, 2, ..., n)
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 THUẬT TOÁN APRIORI
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam THUẬT TOÁN APRIORI •Giải thích
– Trong mỗi bước k, thuật toán Apriori ều phải duyệt CSDL D
– Khởi ộng, duyệt D ể có ược F1.
– Các bước k sau ó, duyệt D ể tính số lượng giao dịch t thoả từng
ứng viên c của Ck+1: mỗi giao dịch t chỉ xem xét một lần cho mọi ứng viên c thuộc Ck+1.
– Thủ tục con Apriori-gen sinh tập phổ biến
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 THUẬT TOÁN APRIORI
•Thủ tục con Apriori-gen sinh tập phổ biến
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 THUẬT TOÁN APRIORI • Chú ý
– Cách thức sinh các ứng viên:
• Bước 1: Tự kết nối Lk • Bước 2: Cắt tỉa – Cách thức
– Ví dụ thủ tục con sinh ứng viên
• L3={abc, abd, acd, ace, bcd} • Tự kết nối: L3*L3 – abcd từ abc và abd – acde từ acd và ace • Tỉa – acde là bỏ • C4={abcd}
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam THUẬT TOÁN APRIORI •Ví dụ (min_sup*|D|=2)
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 THUẬT TOÁN APRIORI •Sinh luật kết hợp
ược hãy sinh ra mọi tập con thực
sự X khác rỗng của nó.
• Với mỗi tập phố biến W và tập con X khác rỗng thực sự của nó:
• Sinh luật X (W – X) nếu P(W-X|X) c.
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam THUẬT TOÁN APRIORI •L3 = {{I1, I2, I3}, {I1, I2, I5}}
min_conf=70%, tập phổ biến ây:
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 SỬ DỤNG WEKA EXPLORER
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam SỬ DỤNG WEKA EXPLORER
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 SỬ DỤNG WEKA EXPLORER
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam SỬ DỤNG WEKA EXPLORER
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam lOMoARcPSD| 36667950 SỬ DỤNG WEKA EXPLORER
… những bước chập chững vào thế giới Dữ liệu lớn … TS. Trịnh Hoàng Nam