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
2
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, …) 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 :

Sữa}
o Giỏ 2: {Bánh mì, Đường}
o …
o Giỏ n: {Bánh qui, ngũ cốc,
sữa}
TID Produce
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

Định nghĩa :
o Hạng mục (Item) : mặt hàng trong giỏ hay một thuộc tính
o Tập các hạng mục (itemset) I = {i
1
, i
2
, …, i
m
} :
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

Tại sao ?
Nu tp con không ph bin thì tp
bao nó (tp cha) có ph bin hay
không ?
KHÁI NIỆM CƠ BẢN
12
I = { Beer, Bread, Jelly, Milk, PeanutButter}
X= {Bread,PeanutButter} ; Count(X) = 3 và |D| = 5
→
→→
→ 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

A,C,D,F30
B,C,D,E,20
A,B,C,D,E10
ItemsTid
Minsupp=2