1
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ú
4

≥
≥≥
≥
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

Item frequency head
f 4
c 4
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

a 3
b 3
m 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
4
13
THIẾT LẬP CÂY FP (B0)

m:1
b:1
14
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
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

nào ?
16
Qui định trình bày bài nộp
Bài tập nộp theo nhóm
 Ngày nộp :
 Tên nhóm : ( chỉ ghi tên các thành
viên có mặt)
– Thành viên 1:
– Thành viên 2:
– …
– Thành viên 12:
 Nội dung :
5
17
ĐÁP ÁN
18
THUẬT TOÁN FP-GROWTH (B1)
 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 (VD hạng mục 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 (của p)
Conditional pattern bases
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

20
THUẬT TOÁN FP-GROWTH (B2)
Ví dụ : m-conditional pattern base: fca:2, fcab:1
{}
f:3
c:3
a:3
m-conditional FP-tree



{}
f:4 c:1
b:1
p:1
b:1c:3
a:3
b:1m:2
p:2 m:1
Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
 Xây dựng cây FP-điều kiện
– Vi mi cơ s mu :
• Đếm số lượng mỗi mẫu trong cơ sở mẫu