1
1
KHAI THÁC
DỮ LIỆU &
ỨNG DỤNG
(DATA MINING)
GV : NGUYỄN HOÀNG TÚ ANH
2
BÀI 3- PHẦN 1
KHAI THÁC
TẬP PHỔ BIẾN &
LUẬT KẾT HỢP
3
NỘI DUNG
1. Gii thiu
2. Các khái niệm cơ bản
3. Bài toán khai thác tập phổ biến
4
GIỚI THIỆU
 Mẫu phổ biến : là mẫu (tập các hạng mục, chuỗi con, cấu
trúc con, đồ thị con, …) xuất hiện thường xuyên trong tập
DL
– Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ
biến và luật kết hợp
 Mục đích : Tìm các hiện tượng thường xuyên xảy ra
trong DL
– Những sản phẩm nào thường được mua chung ? Bia và tã lót
– Người ta thường mua gi tiếp theo sau khi mua máy PC ?
– Dạng DNA nào có phản ứng với công thức thuốc mới ?
– Làm thế nào đề phân loại tự động văn bản Web ?
 Ứng dụng :

Đường}
…
o Giỏ n: {Bánh qui, ngũ
cốc, sữa}
TID Produces
1 MILK, BREAD, EGGS
2 BREAD, SUGAR
3 BREAD, CEREAL
4 MILK, BREAD, SUGAR
5 MILK, CEREAL
6 BREAD, CEREAL
7 MILK, CEREAL
8
MILK, BREAD, CEREAL,
EGGS
9 MILK, BREAD, CEREAL

8
KHÁI NIỆM CƠ BẢN
TID A B C D E
1 1 1 0 0 1
2 0 1 0 1 0
3 0 1 1 0 0
4 1 1 0 1 0
5 1 0 1 0 0
6 0 1 1 0 0
7 1 0 1 0 0
8 1 1 1 0 1
9 1 1 1 0 0


} :
VD : I = {sữa, bánh mì, ngũ cốc, sữa chua}
Tập k hạng mục (k-itemset)
o Giao dịch (Transation) : tập các hạng mục được mua trong
một giỏ ( có TID – mã giao dịch) : (Tid, tập hạng mục)
o Giao dịch t : tập các hạng mục sao cho t
⊆
I
o VD : t = { bánh mì, sữa chua, ngũ cốc}
o CSDL giao dịch : tập các giao dịch
o CSDL D = {t
1
,t
2
, …, t
n
} , t
i
={i
i1
,i
i2
, …, i
ik
} với i
ij
∈ I : CSDL
giao dịch
KHÁI NIỆM CƠ BẢN
10

→→
→ supp(X) = 60%→
→→
→ X- tập phổ biến
X
2
= {Bread} →
→→
→ supp(X
2
) = ?
X
3
= {PeanutButter} →
→→
→ supp(X
3
) = ?; X
2
và X
3
có phổ biến ?
X
3
= {Milk}, X
4
={Milk, Bread} →
→→
→ X
3

Tp ph bin & không tn ti
tp nào bao nó có cùng đ
ph bin nh nó. (Pasquier,
ICDT’99)
Tp bao ph bin là trng hp
nén các tp ph bin (có mt
thông tin)
{A, B}, {A, B, D}, {A,B, C} - tập
bao phổ biến
{A, B} - không phải tập phổ
biến tối đại
Minsupp=2
c, e, f50
a, b, d, 40
a, b, d30
a, b, c20
a, b, c 10
ItemsTID
16
6. LUẬT KẾT HỢP( Association rule)
LKH có dng :
X ⇒
⇒⇒
⇒ Y, với X, Y ⊂
⊂⊂
⊂ I, và X ∩
∩∩
∩Y ={}
Ý nghĩa : khi X có mặt thì Y cũng có mặt ( với xác
suất nào đó)

Cho độ phổ biến tối thiểu (minsupp) và độ tin
cậy tối thiểu (minconf) do người dùng xác định.
Cho tập các hạng mục I={i
1
,i
2
,…,i
m
} và CSDL
giao dịch D={t
1
,t
2
, …, t
n
}, với t
i
={i
i1
,i
i2
, …, i
ik
} và i
ij
∈ I.
Bài toán khai thác LKH là bài toán tìm tt c
các luật dạng X ⇒
⇒⇒
⇒ Y (X, Y ⊂ I và X ∩Y = {})

B, C10
Items boughtTrs-id
Bài tập theo nhóm
20
KHÁI NIỆM CƠ BẢN
8. QUI TRÌNH KHAI THÁC LKH
B1 : Tìm tất cả các tập phổ biến ( theo ngưỡng
minsupp)
B2 : Tạo ra các luật từ các tập phổ biến
Đối với mỗi tập phổ biến S, tạo ra tất cả các tập
con khác rỗng của S
Đối với mỗi tập con khác rỗng A của S,
o Luật A ⇒
⇒⇒
⇒ (S - A) là LKH cần tìm nếu :
 conf (A ⇒
⇒⇒
⇒ (S - A)) = supp(S) / supp(A) ≥
≥≥
≥ minconf
 T bài toán khai thác LKH chuyn thành
bài toán khai thác tp ph bin : độ phức
tạp tính toán cao.