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 :
– Áp dụng trong phân tích CSDL bán hà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

TID Products
1 A, B, E

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
2. ĐỘ PHỔ BIẾN VÀ TẬP PHỔ BIẾN
Giao dịch t chứa X nếu X là tập các hạng mục
trong I và X ⊆ t

→ 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
4
= {Milk}, X
5
={Milk, Bread} →
→→
→ X
4
và X
5
có phổ biến ?

Tp ph bin ĐÓNG 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
phổ biến đóng.
{A, B} - không phải tập phổ
biến tối đại
Minsupp=2
TID Items
10 a, b, c
20 a, b, c
30 a, b, d
40 a, b, d,
50 c, e, f
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 đó)
LKH thng được đánh giá dựa trên 2 độ đo:
Độ phổ biến (support) : supp (X ⇒
⇒⇒
⇒ Y ) =P (X ∪