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, đồ 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
–Mở rộng sang quảng cáo, thiết kế catalog, phân tích chiến
dịch bán hàng, Web log, chuỗi DNA, …
3
5
GIỚI THIỆU
Bài toán khai thác tập phổ biến là bài toán
rất quan trọng lĩnh vực KTDL : vạch ra tính
chất ẩn, quan trọng của tập DL
Là nền tảng cho nhiều nhiệm vụ KTDL khác :
–Phân tích luật kết hợp, mối tương quan
– Mẫu tuần tự, cấu trúc ( Vd :đồ thị con)
–Phân tích DL không gian, đa phương tiện, phụ
thuộc thời gian
–Phân loại :phân loại dựa trên luật kết hợp
–Phân tích nhóm: gom nhóm dựa trên mẫu phổ biến
– ….
6
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
7
KHÁI NIỆM CƠ BẢN
1. CSDL GIAO DỊCH
(Transaction DB)
VD giỏ mua hàng:
oGiỏ 1: {Bánh mì,
Trứng, Sữa}
oGiỏ 2: {Bánh mì,
Đường}
…
oGiỏ 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
1
1
1
0
2
0
1
0
3
0
1
1
4
1
1
0
5
1
0
1
6
0
1
1
7
1
0
1
8
1
1
1
9
1
1
1
TID
Products
1
A, B, E
2
B, D
3
B, C
4
A, B, D
5
A, C
6
B, C
7
A, C
8
A, B, C, E
9
A, B, C
ITEMS:
A = milk
B= bread
C= cereal
D= sugar
E= eggs
Biến đổi CSDL về
dạng nhị phân
5
9
1. CSDL GIAO DỊCH (tt)
Định nghĩa :
oHạng mục (Item) : mặt hàng trong giỏ hay một thuộc tính
oTập các hạng mục (itemset) I= {i1,i2,…,im} :
VD : I = {sữa, bánh mì, ngũ cốc, sữa chua}
Tập k hạng mục (k-itemset)
oGiao 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)
oGiao dịch t:tập các hạng mục sao cho t
I
oVD : t = { bánh mì, sữa chua, ngũ cốc}
oCSDL giao dịch :tập các giao dịch
oCSDL D={t1,t2,…, tn}, ti={ii1,ii2,…, iik}với iij 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 tchứa X nếu X là tập các hạng mục trong I
và X t
VD : X = { bánh mì, sữa chua}
Độ phổ biến (supp) của tập các hạng mục
Xtrong CSDL Dlà tỷ lệ giữa số các giao
dịch chứa X trên tổng số các giao dịch
trong D
Supp(X) = count(X) / | D |
Tập các hạng mục phổ biến Shay tập phổ biến
(frequent itemsets) là tập các hạng mục có độ phổ
biến thỏa mãn độ phổ biến tối thiểu minsupp (do
người dùng xác định)
Nếu supp(S) minsupp thì S -tập phổ biến .
KHÁI NIỆM CƠ BẢN