Bài giảng Nhập môn khai phá dữ liệu - Chương 4: Khai phá luật kết hợp - Hà Quang Thụy
BÀI GIẢNG NHẬP MÔN KHAI PHÁ DỮ LIỆU
CHƯƠNG 4. KHAI PHÁ LUẬT KẾT HỢP
PGS. TS. Hà Quang ThụyHÀ NỘI, 08-2018
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI
1
Chương 4: Khai phá luật kết hợp
◼ Khai phá luật kết hợp (Association rule)
◼ 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
July 12, 2021
2
Bán chéo và bán tăng cường
◼ Bán chéo
▪ cross-selling
▪ Bán chéo: bán các sản phẩm bổ sung cho khách
hàng hiện tại.
▪ Sản phẩm thường được mua cùng nhau
▪ Bán tăng cường
▪ up-selling (deep-selling: bán sâu)
▪ bán các sản phẩm số lượng nhiều hơn hoặc giá cao
hơn cho khách hàng hiện tại
3
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
Một số ví dụ về “luật kết hợp” (associate rule)
• “98% khá ch hàng mà mua tạp chí 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ạp chí về ô tô ”
• “60% khá ch hàng mà mua bia tại siêu thị thì đều
mua bỉm trẻ em” sự kết hợp giữa “bia” với “bỉm
trẻ em”
• “Có tới 70% người truy nhập Web vào địa chỉ Url 1
thì cũng vào địa chỉ Url 2 trong một phiên truy nhập
web” sự kết hợp giữa “Url 1” với “Url 2”. Khai
phá dữ liệu sử dụng Web (Dữ liệu từ file log của
cá c site, chẳng hạn được MS cung cấp).
• Xuất hiện từ: Tri thức must-links và Cannot-Links
trong học mô hì nh suổt đời.
July 12, 2021
4
Khái niệm cơ sở: Tập phổ biến và luật kết hợp
Cơ sở dữ liệu giao dịch (transaction database)
• Giao dịch: danh sách các mục (mục: item, mặt hàng) trong một phiếu mua
hàng. Giao dịch T là một tập mục.
• Tập toàn bộ các mục I = {i1, i2, …, ik} “tất cả các mặt hàng”. Một giao dịch T
là một tập con của I: T I. Mỗi giao dịch T có một định danh là TID.
• A là một tập mục A I và T là một giao dịch: Gọi T chứa A nếu A T.
• Luật kết hợp
• Gọi A → B là một “luật kết hợp” nếu A I, B I và AB=.
• Luật kết hợp A → B có độ hỗ trợ (support) s trong CSDL giao dịch D nếu
trong D có s% các giao dịch T chứa AB: chính là xác suất P(AB). Tập mục A
có P(A) s>0 (với s cho trước) được gọi là tập phổ biến (frequent set). Luật
kết hợp A → B có độ tin cậy (confidence) c trong CSDL D nếu như trong D
có c% các giao dịch T chứa A thì cũng chứa B: chính là xác suất P(B|A).
• Support (A → B) = P(AB)
• Confidence (A → B) = P(B|A)
: 1 s (A → B) 0
: 1 c (A → B) 0
• Luật A → B được gọi là đảm bảo độ hỗ trợ s trong D nếu s(A → B) s. Luật
A→B được gọi là đảm bảo độ tin cậy c trong D nếu c(A → B) c. Tập mạnh.
July 12, 2021
5
Khái niệm cơ bản: Mẫu phổ biến và luật kết hợp
◼ Tập mục I={i1, …, ik}. CSDL giao dịch
D = {d I}
◼ A, B I, AB=: A→ B là luật kết hợp
◼ Bài toán tìm luật kết hợp.
Transaction-id
Items bought
A, B, C
A, C
10
20
30
40
Cho trước độ hỗ trợ tối thiểu s>0, độ
tin cậy tối thiếu c>0. Hãy tìm mọi luật
kết hợp mạnh X→Y.
A, D
B, E, F
Giả sử min_support = 50%,
min_conf = 50%:
Customer
buys both
Customer
buys diaper
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ụ
thuộc hàm.
Customer
buys beer
◼ Các tính chất Armstrong ở đây.
July 12, 2021
6
Một ví dụ tìm luật kết hợp
Min. support 50%
Min. confidence 50%
Transaction-id
Items bought
A, B, C
A, C
10
20
30
40
Frequent pattern
Support
75%
A, D
{A}
{B}
B, E, F
50%
{C}
50%
For rule A C:
{A, C}
50%
support = support({A}{C}) = 50%
confidence = support({A}{C})/support({A}) =
66.6%
July 12, 2021
7
Khai niệm khai phá kết hợp
July 12, 2021
8
Khái niệm khai phá luật kết hợp
◼ Khai phá luật kết hợp:
◼ Tìm tất cả mẫu phổ biến, kết hợp, tương quan, hoặc cấu
trú nhan-quả trong tập các mục hoặc đối tượng trong
CSDL quan hệ hoặc các kho chứa thông tin khác.
◼
Mẫu phổ biến (Frequent pattern): là mẫu (tập mục, dãy
mục…) mà xuất hiện phổ biến trong 1 CSDL [AIS93]
◼ Động lực: tìm mẫu chính quy (regularities pattern) trong DL
◼
Các mặt hàng nào được mua cùng nhau? — Bia và bỉm
(diapers)?!
◼
◼
◼
Mặt hàng nào sẽ được mua sau khi mua một PC ?
Kiểu DNA nào nhạy cảm với thuộc mới này?
Có khả năng tự động phân lớp Web hay không ?
July 12, 2021
9
Mẫu phổ biến và khai phá luật kết hợp là
một bài toán bản chất của khai phá DL
◼ Nền tảng của nhiều bài toán KPDL bản chất
◼
Kết hợp, tương quan, nhân quả
◼
Mẫu tuần tự, kết hợp thời gian hoặc vòng, chu kỳ bộ
phận, kết hợp không gian và đa phương tiện
◼
Phân lớp kết hợp, phân tích cụm, khối tảng băng, tích
tụ (nén dữ liệu ngữ nghĩa)
◼ Ứng dụng rộng rãi
◼ Ví dụ: Phân tích DL bóng rổ, tiếp thị chéo (cross-
marketing), thiết kế catalog, phân tích chiến dịch bán
hàng
◼ Phân tích Web log (click stream), Phân tích chuỗi DNA v.v.
July 12, 2021
10
Apriori: Một tiếp cận sinh ứng viên và kiểm tra
◼ Khái quát: Khai phá luật kết hợp gồm hai bước:
◼
Tìm mọi tập mục phổ biến: theo min-sup
◼
Sinh luật mạnh từ tập mục phổ biến
◼ Mọi tập con của tập mục phổ biến cũng là tập mục phổ biến
◼
Nếu {bia, bỉm, hạnh nhân} là phổ biến thì {bia, bỉm} cũng vậy: Mọi
giao dịch chứa {bia, bỉm, hạnh nhân} cũng chứa {bia, bỉm}.
◼ Nguyên lý tỉa Apriori: Với tập mục không phổ biến thì không cần phải
sinh ra/kiểm tra mọi tập bao nó!
◼ Phương pháp:
◼
Sinh các tập mục ứng viên dài (k+1) từ các tập mục 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
◼ Các nghiên cứu hiệu năng chứng tỏ tính hiệu quả và khả năng mở rộng
của thuật toán
◼ Agrawal & Srikant 1994, Mannila, và cộng sự 1994
July 12, 2021
11
Thuật toán Apriori
Trên cơ sở tí nh chất (nguyên lý tỉa) Apriori, thuật
toá n hoạt động theo quy 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 mục phổ biến có độ dài i với
1 i k,
• đi tì m tập Fk+1 gồm mọi tập mục phổ biến có
độ dài k+1.
Trong thuật toá n, cá c tên mục i1, i2, … in (n = |I|)
được sắp xếp theo một thứ tự cố định (thường
được đánh chỉ số 1, 2, ..., n).
July 12, 2021
12
Thuật toán Apriori
July 12, 2021
13
Thuật toán Apriori: Thủ tục con Apriori-gen
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: tư tưởng
July 12, 2021
14
Thủ tục con Apriori-gen
July 12, 2021
15
Một ví dụ thuật toán Apriori (s=0.5)
Itemset sup
Database TDB
F1
{A}
{B}
{C}
{E}
2
3
3
3
Tid
10
20
30
40
Items
A, C, D
B, C, E
A, B, C, E
B, E
Itemset sup
C2
C2
2nd scan
Itemset
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
1
2
1
2
3
2
July 12, 2021
16
Một ví dụ thuật toán Apriori (s=0.5)
Itemset sup
Itemset sup
Database TDB
{A}
{B}
{C}
{D}
{E}
2
3
3
1
3
F1
{A}
{B}
{C}
{E}
2
3
3
3
Tid
10
20
30
40
Items
A, C, D
B, C, E
A, B, C, E
B, E
C1
1st scan
Itemset sup
C2
C2
2nd scan
Itemset
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
{A, B}
{A, C}
{A, E}
{B, C}
{B, E}
{C, E}
1
2
1
2
3
2
Itemset sup
F2
{A, C}
{B, C}
{B, E}
{C, E}
2
2
3
2
Itemset
3rd scan
F3
C3
Itemset sup
{B, C, E}
{B, C, E}
2
July 12, 2021
17
Chi tiết quan trọng của Apriori
◼ Cách thức sinh các ứng viên:
◼
Bước 1: Tự kết nối Fk
◼
Step 2: Cắt tỉa
◼ Cách thức đếm hỗ trợ cho mỗi ứng viên.
◼ Ví dụ thủ tục con sinh ứng viên
◼
F3={abc, abd, acd, ace, bcd}
◼
Tự kết nối: F3*F3
◼
abcd từ abc và abd
acde từ acd và ace
◼
◼
◼
Tỉa:
◼
acde là bỏ đi vì ade không thuộc F3
C4={abcd}
July 12, 2021
18
Ví dụ: D, min_sup*|D| = 2 (C4 = )
F1
F2
F1
F3
F2
July 12, 2021
19
Sinh luật kết hợp
Việc sinh luật kết hợp gồm hai bước
◼ Với mỗi tập phổ biến X tìm được hãy sinh ra mọi tập
con thực sự Y khác rỗng của nó.
◼ Với mỗi tập phố biến X và tập con Y khác rỗng thực sự
của nó: sinh luật Y → (X – Y) nếu P(X-Y|Y) co.
Như ví dụ đã nêu có L3 = {{I1, I2, I3}, {I1, I2, I5}}
Với độ tin cậy tối thiểu 0.7 (70%), xét tập mục phổ biến
X={I1, I2, I5} có 3 luật mạnh sau đây:
July 12, 2021
20
Tải về để xem bản đầy đủ
75 trang
12620
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn khai phá dữ liệu - Chương 4: Khai phá luật kết hợp - Hà Quang Thụy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_khai_pha_du_lieu_chuong_4_khai_pha_luat_k.pdf
