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 ?

Trứng, Sữa}
o Giỏ 2: {Bánh mì,
Đườ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

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

5
9
1. CSDL GIAO DỊCH (tt)
Đị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

biến đều là tập phổ biến
Thảo luận :
Tại sao ? Chứng minh.
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
có phổ biến ?
X
4
= {Milk}, X
5
={Milk, Bread}  X

5. TẬP PHỔ BIẾN ĐÓNG (Closed
Pattern)
Tập phổ biến & không tồn tại tập
nào bao nó có cùng độ phổ biến
như nó. (Pasquier, ICDT’99)
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)
Ví dụ : {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
Mối quan hệ giữa tập phổ biến
đóng và tập phổ biến tối đại
ntn?
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  Y)
supp (X  Y ) = supp(X

={i
i1
,i
i2
, …, i
ik
} và i
ij
 I.
Bài toán khai thác LKH là bài toán tìm tất cả
các luật dạng X  Y (X, Y  I và X Y = {})
thỏa mãn độ phổ biến và độ tin cậy tối thiểu
supp (X  Y )  minsupp
conf (X  Y )  minconf
KHÁI NIỆM CƠ BẢN
10
19
 Thời gian : 8’
 Trình bày ý tưởng
(không yêu cầu giải BT)
giải quyết vần đề trước
lớp trong vòng 3’
 Tình huống :
– Cho CSDL bên với các
giá trị minsupp =50 % và
minconf = 100%
– Cần tìm tất cả các luật
kết hợp thỏa mãn
minsupp và minconf.
– Nhận xét ?

Minsupp = 50%
Minconf = 80%
Transaction-id Items bought
10 A, B, C
20 A, C
30 A, D
40 B, E, F
Frequent Itemsets Support
{A} 75%
{B} 50%
{C} 50%
{A, C} 50%
VÍ DỤ
22
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
 Thuật toán Apriori
12
23
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
Bài toán khai thác tập phổ biến là bài toán tìm tất
cả các tập các hạng mục S (hay tập phổ biến S)
có độ phổ biến thỏa mãn độ phổ biến tối thiểu
minsupp
supp(S)

C
1
L
1
L
2
C
2
C
2
2
nd
scan
C
3
L
3
3
rd
scan
Tid Items
10 A, C, D
20 B, C, E
30 A, B, C, E
40 B, E
Itemset sup
{A} 2
{B} 3
{C} 3
{D} 1

THUẬT TOÁN APRIORI
2. Pseudo-Code
Input : CSDL D, minsupp
Output : L : các tập phổ biến trong D
C
k
: Tập ứng viên kích thước k
L
k
: Tập phổ biến kích thước k
L
1
= Tìm_tập_phổ_biến_1_hạng mục(D);
for (k = 1; L
k
; k++) {
C
k+1
= apriori_gen(L
k
); // Tạo tập ứng viên (k+1) hạng mục
for mỗi giao tác t  D { // Duyệt CSDL để tính support
C
t
= subset(C
k+1
, t); // Lấy ra tập con của t là ứng viên
for mỗi ứng viên c  C
t
c.count ++

for mỗi itemset l
2
 L
k
if (l
1
[1] = l
2
[1])  (l
1
[2] = l
2
[2])  … (l
1
[k-1] = l
2
[k-1]) 
(l
1
[k] < l
2
[k]) then
{ c = l
1
 l
2
; // Bước 1 :kết L
k
với chính nó
if has_infrequent_subset (c, L

3
= {{1, 2, 3}, {1, 2, 4}, {1, 3, 4},
{1, 3, 5}, {2, 3, 4}}
 Sau bước kết :
– C
4
= {{1, 2, 3, 4}, {1, 3, 4, 5}}
 Sau bước loại bỏ, còn :
– C
4
= {{1, 2, 3, 4}}
vì {1, 4, 5}  L
3
nên {1, 3, 4, 5} bị loại
30
CÁC THÁCH THỨC CỦA TT APRIORI
Thách thức :
Phải duyệt CSDL nhiều lần
Số lượng tập ứng viên rất lớn
Thực hiện việc tính độ phổ biến nhiều, đơn
điệu
Cải tiến Apriori : ý tưởng chung
Giảm số lần duyệt CSDL
Giảm số lượng tập ứng viên
Qui trình tính độ phổ biến thuận tiện hơn
16
31
CÁC KỸ THUẬT CẢI TIẾN
THUẬT TOÁN APRIORI
Tự tìm hiểu trong tài liệu tham khảo

hạng mục từ các mẫu tin của CSDL mà xây dựng cấu
trúc lưu trữ mới C
k
cho CSDL ban đầu .
Mỗi mẫu tin trong C
k
có dạng <Tid, {X
k
}> với X
k
là tập phổ biến
k- hạng mục xuất hiện trong giao dịch có mã Tid.
Nếu một giao dịch không chứa bất kỳ một tập phổ biến k hạng
mục thì giao dịch này không được đưa vào C
k
.
17
33
BÀI TẬP (cá nhân)
 Thời gian : 25’
 Chỉ trình bày kết quả câu 1
(không cần ghi chi tiết các
bước của câu 1) và chi tiết câu
2, câu 3 vào giấy nộp cho GV.
Cho CSDL giao dịch bên
1. Sử dụng thuật toán Apriori để tìm
các tập phổ biến với minsupp = 22
%
2. Liệt kê các tập phổ biến tối đại và
tập phổ biến đóng.

2. Chuẩn bị bài 3 : Khai thác tập phổ biến và
luật kết hợp – P2
– Xem nội dung bài 3 – Phần 2.
– Chuẩn bị BT nhóm Bài 3 – Phần 2
– Cách thực hiện :
• Đọc slide, xem các ví dụ
• Tham khảo trên Internet và tài liệu tham
khảo
36
BÀI TẬP PHẦN 1
1. Hãy tìm hiểu trong tài liệu tham khảo [2], [3]
và trình bày chi tiết một phương pháp cải tiến
quá trình tìm luật kết hợp từ tập phổ biến
(Bước 2 trong qui trình khai thác luật kết
hợp)? Giải thích vì sao nó hiệu quả hơn.
2. Tìm hiểu các phương pháp cải tiến thuật
toán Apriori. Trình bày chi tiết MỘT cải tiến
( ý tưởng, mã giả )
3. Áp dụng một trong các phương pháp cải
tiến đó vào bài tập 4.a. Nêu rõ đã cải tiến ở
phần nào .
19
37
BÀI TẬP PHẦN 1
4. Cho CSDL sau và minsupp=50%, minconf=80%
a) Sử dụng thuật toán Apriori để tìm tất cả các tập phổ
biến, tập phổ biến tối đại, tập phổ biến đóng.
b) Tìm tất cả LKH thỏa mãn ngưỡng minconf đã cho
c) Ứng dụng cải tiến của câu 1 vào việc tìm các LKH
thỏa mãn ngưỡng minconf. So sánh hiệu quả về

http://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf
20
39
Q & A