1
KHAI THÁC
DỮ LIỆU &
ỨNG DỤNG
(DATA MINING)
GV : NGUYỄN HOÀNG TÚ ANH
2
B
BB
BÀ
ÀÀ
ÀI 3
I 3 I 3
I 3 -
--
- PH
PHPH
PHẦN 2
N 2N 2
N 2
KHAI THÁC
TẬP PHỔ BIẾN &
LUẬT KẾT HỢP
3
NỘI DUNG
1.Gii thiu
2. Bài toán khai thác tập phổ
biến
3. Độ đo tính lý thú của LKH
4
GIỚI THIỆU

≥
minsupp
Cách giải quyết : dựa trên tính chất của tập phổ
biến
Tìm kiếm theo chiều rộng : Thuật toán Apriori
(1994)
Phát triển mẫu : Thuật toán FP-Growth
(2000)
Tìm kiếm trên CSDL hàng dọc : Thuật toán
Charm (2002)
6
GIỚI THIỆU
 Các hạn chế của Thuật toán Apriori
Phải duyệt CSDL nhiều lần
Khi khai thác các mẫu dài cần duyệt CSDL
nhiều lần và tạo lượng lớn tập ứng viên
Ví dụ : Để tìm tập phổ biến i1 i2… i100 :
• Số lần duyệt CSDL : 100
• Số lượng ứng viên : 2
100
-1 = 1.27*10
30
!
Vấn đề : tạo ứng viên và kiểm tra
 Có thể tránh việc tạo ứng viên hay không ?
7
NỘI DUNG
1. Giới thiệu
2. Bài toán khai thác tp
ph bin

a 3
b 3
m 3
p 3
minsupp = 60%
TID Items bought (ordered) frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o, w} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
1. Tìm tập phổ biến 1- hạng
mục (duyệt CSDL 1 lần)
2. Sắp xếp tập phổ biến giảm
dần vào trong F-list
3. Sắp xếp CSDL theo F-
list. Duyệt CSDL lần
nữa và thiết lập cây FP
F-list=f-c-a-b-m-p
11
THIẾT LẬP CÂY FP (B0)
Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
minsupp = 3

p 3
minsupp = 3
TID Items bought (ordered) frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o, w} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
1. Tìm tập phổ biến 1-
hạng mục (duyệt CSDL 1
lần)
2. Sắp xếp tập phổ biến
giảm dần vào trong F-
list
3. Duyệt CSDL lần nữa và
thiết lập cây FP
F-list=f-c-a-b-m-p
{}
f:2
c:2
a:2
b:1m:1
p:1
m:1
13
THIẾT LẬP CÂY FP (B0)
Header Table
Item frequency head
f 4
c 4

Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
minsupp = 3
1. Tìm tập phổ biến 1-
hạng mục (duyệt CSDL 1
lần)
2. Sắp xếp tập phổ biến
giảm dần vào trong F-
list
3. Duyệt CSDL lần nữa
và thiết lập cây FP
F-list=f-c-a-b-m-p
{}
f:4 c:1
b:1
p:1
b:1c:3
a:3
b:1m:2
p:2
m:1
TID Items bought (ordered) frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}

 Tên nhóm : ( chỉ ghi tên các thành
viên tham gia)
– Thành viên 1:
– Thành viên 2:
– Thành viên 3:
– …
– Thành viên 7:
 Nội dung :
17
B1 : Thiết lập cơ sở mẫu điều kiện
 Xây dng cơ s mu điu kin
(Conditional pattern base)
–Bắt đầu từ mẫu phổ biến cuối bảng
của cây FP
–Duyệt cây FP theo kết nối của mỗi
hạng mục phổ biến.
–Gom tất cả đường dẫn tiền tố biến
đổi (transformed prefix) của hạng
mục để tạo cơ sở mẫu điều kiện
18
VÍ DỤ 1: Thiết lập cơ sở mẫu điều
kiện
 Xây dng cơ s mu điu kin (Conditional pattern base)
– Bắt đầu từ mẫu phổ biến cuối bảng của cây FP: hạng mục p
– Duyệt cây FP theo kết nối của mỗi hng mc ph bin p.
– Gom tất cả đường dẫn tiền tố biến đổi (transformed prefix) của hạng
mục p để tạo cơ sở mẫu điều kiện cho p
Cơ sở mẫu điều kiện
item cond. pattern base
p fcam:2, cb:1

Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
Cơ sở mẫu điều kiện
item cond. pattern base
m fca:2, fcab:1
p fcam:2, cb:1
VÍ DỤ 1: Thiết lập cơ sở mẫu điều
kiện
20
 Xây dng cơ s mu điu kin (Conditional
pattern base)
– Tiếp tục với các mẫu phổ biến còn lại của cây
FP
Cơ sở mẫu điều kiện
item cond. pattern base
c f:3
a fc:3
b fca:1, f:1, c:1
m fca:2, fcab:1
p fcam:2, cb:1
{}
f:4 c:1
b:1
p:1