KHAI THÁC LUẬTKẾTHỢP
1
DD
ẪẪ
NN
NHNH
ẬẬ
PP
DD
ẪẪ
NN
NHNH
ẬẬ
PP
Xét CSDL khảo sát tiện nghi sử dụng ở các hộ
gia đình nh
ư
sau:
gia đình nh
ư
sau:
Hộ Tiện nghi sở hữu
1
Ti i
Má Vití h
1
Ti
v
i
,
MáyVití

ẾẾ
TT
HH
ỢỢ
PP
LL
UU
ẬẬ
TT
KK
ẾẾ
TT
HH
ỢỢ
PP
 LuLuậậttkkếếtthhợợpplàlà phépphép kéokéo theotheo cócó ddạạngng::
 Tivi  Máyvitính [50%, 57%] hay
sử dụng:Tivi  sử dụng:Máyvitính [50%, 57%]
Nghĩa là: “57% hộ gia đình sử dụng Tivi thì cũng sử dụng
Máyvitính. Tivi và Máyvitính xuấthiện chung trong 50%
dòng
d
ữ
li
ệ
u
"
dòng
d
ữ

Association Rules)
Association

Rules)
.
4
KKHAIHAI THÁCTHÁC LULUẬẬTTKKẾẾTTHHỢỢPP
ế
CSDL
giao tác
Khai thác luật k
ế
t hợp được chia làm hai giai đoạn:
1. Khai thác t
ập

p
h
ổ
bi
ế
n
(
FIs
–
Fre
q
uent Itemsets
)
.

n
1
.
Tìm T
ậ
p ph
ổ
bi
ế
n
2
Tìm lu
ậ
t k
ế
t h
ợ
p
2
.
Tìm lu
ậ
t k
ế
t h
ợ
p
6
TTÌMÌM TTẬẬPPPHPHỔỔ BIBIẾẾNN
 Được đề xuất bởi Agrawal năm 1993.

p
đ
ư
ợ
cp
há
t
triểnnhư:
Ph
há A i i (A l)

Ph
ương

p
há
p
A
pr
i
or
i (A
grawa
l)
 Phương pháp IT-tree (M. Zaki)

Ph
ươ
ng pháp FP
-

ChoCSDLgiaodịch D và tậpdữ liệu
X
I.
Độ phổ biếncủa X trong D, kí hiệu (X),
đ
ượ
c
đ
ị
nh
nghĩa
là
s
ố
giao
d
ị
ch
mà
X
xu
ấ
t
đ
ượ
c
đ
ị
nh
nghĩa

p
g
p
(
X
)minSup (với minSup là giá trị do
người dùng chỉ định).
9
2121 DecDec 1010
TTÍNHÍNH CHCHẤẤTT AAPRIORIPRIORI
1. Mọi tập con của tập phổ biến đều phổ biến, nghĩa
là XY, nếu

(Y)  minSup thì (X)  minSup

2. Mọi tập cha của tập không phổ biến đều không phổ
bi
ế
n
nghĩa là

Y

X n
ế
u

(X)
<
minSup

 Đầu ra: FIs chứa tất cả các tập phổ biến của D
 Mã giả:
G
ọ
i C
k
: T
ậ
p
các
ứ
n
g
viên có kích thước k
ọ
k
ậ
p
g
L
k
: Các tập phổ biến có kích thước k
L
1
= { i  I: (i)  minSup}
for (k = 2; L
k-1
!=; k++) do
C
k

1
}
for each t  D do
if C
k

t then C
k
.count++
L
k
= {C
k
|C
k
.count  minSup}
FIs
=

L
;
FIs
=

k
L
k
;
11
CCÁCHÁCH TTẠẠOO ỨỨNGNG VIÊNVIÊN CCỦỦAA AAPRIORIPRIORI

i t
ậ
p con c
ủ
a t
ậ
p ph
ổ
bi
ế
n
cũng phổ biến
 Giả sử ta có L
3

= {abc, abd, acd, ace, bcd}
 Xét việc kết để tao ra các ứng viên C
4
: L
3
*L
3
abcd được tạo từ abc và abd
d
đ
t
t
ừ
d
à

lo
ạ
i vì
ade
không có trong
L
3
C
4
= {abcd}
12
VV
ÍÍ
DD
ỤỤ
MINHMINH
HH
ỌỌ
AA
VV
ÍÍ
DD
ỤỤ
MINHMINH
HH
ỌỌ
AA
Bảng 1: Xét CSDL mẫu
MãMã giaogiao
dịchdịch

WT
,
W
66 CC, , DD, , TT

(T)

4
(W) = 5
13
Với minSup = 50% (50*6/100 = 3), ta có:
VVÍÍDDỤỤ ((TTTT))
Database
(
D
)
L1
()
TID Nội dung Danh
mục
Độ
phổ biến
1
AA, , CC, , TT, , WW
A4
2
CC, , DD, , WW
C6
AA
CC

WT
,
W
W
5
6
CC, , DD, , TT
14
TIDTID ItemsItems
11 AA, , CC, , TT, , WW
22
CC
, , DD, ,
WW
VVÍÍDDỤỤ ((TTTT))
C2
L2
33 AA, , CC, , TT, , WW
44 AA, , CC, , DD, , WW
55
AA
,

,

CC
,

,
DD

,,
,,
,,
66 CC, , DD, , TT
ụ
ụ
AC 4 AC 4
AD 2 AT 3
AT 3 AW 4
AW 4 CD 4
CD 4 CT 4
CT 4 CW 5
CW 5 DW 3
DT 2 TW 3
DW
3
15
DW
3
TW 3
TIDTID ItemsItems
11 AA, , CC, , TT, , WW
VVÍÍDDỤỤ ((TTTT))
22
CC
, , DD, ,
WW
33 AA, , CC, , TT, , WW
44 AA, , CC, , DD, , WW
C3 L3

16
TIDTID ItemsItems
11 AA, , CC, , TT, , WW
22
CC
DD
WW
VVÍÍDDỤỤ ((TTTT))
C4 L4
22
CC
, ,
DD
, ,
WW
33 AA, , CC, , TT, , WW
44 AA, , CC, , DD, , WW
55
AA
CC
DD
TWTW
Danh
mục
Độ phổ
biến
Danh
mục
Độ phổ
biến

PHPH
ƯƠƯƠ
NG PHÁP FPNG PHÁP FP

TREETREE
PHPH
ƯƠƯƠ
NG PHÁP FPNG PHÁP FP
TREETREE
 Quét DB lầnthứ nhất để tìm tấtcả các
item đơnphổ biến (single item pattern)
 Sắpxếp các item theo thứ tự giảmcủa độ
phổ biến  f-list
Qét
DB
l
ầ
2
Xâ
d
FP
t

Q
u
ét
DB
l
ầ
n

TREETREE
XÂYXÂY
DD
ỰỰ
NGNG
CÂYCÂY
22
CC
, ,
DD
, ,
WW
33 AA, , CC, , TT, , WW
44 AA, , CC, , DD, , WW
55
AA
CC
DD
TWTW
55
AA
, ,
CC
, ,
DD
, ,
T
,
WT
,

T

65444
19
2121 DecDec 1010
FPFP

TREETREE
––
XÂYXÂY
DD
ỰỰ
NGNG
CÂYCÂY
TIDTID ItemsItems
11 AA, , CC, , TT, , WW
22
CC
DD
WW
AA, , CC, , TT, , WW
CC
DD
WW
FPFP
TREETREE
XÂYXÂY
DD
ỰỰ
NGNG

AA
, ,
CC
, ,
DD
, ,
T
,
WT
,
W
66 CC, , DD, , TT
C6
W
5
C:1C:2C:3C:4
AA
, ,
CC
, ,
D
,
T
,
D
,
T
,
WW
C:5

20
2121 DecDec 1010

6
5
4
4
4
T:1
FP-tree trên CSDL ở bảng 1 với minSup = 50%
CCHIHIẾẾUU TRÊNTRÊN FPFP TREETREE –– TT FPTT FP GGROWTHROWTH
Item

Link
{}
Chiếu trên nút T: ta có CSDL
cụcbộ như sau:
C6
W5
C:1C:2C:3C:4C:5C:6
cục

bộ

như

sau:
{CWA:2, CWAD:1, CD:1}
A4
D4

hổ
biế
hỉ
đ
iả
là
sau:
Item

Link
{}
c
á
c
tậ
p
phổ
biế
nc
hỉ
đ
ơng
iả
n
là
tìm các tập con củatập{C,W,
A}. Ta có các tập con:
Item

Link

,
TAW
:
3
,
TAC
:
3
,
TWC:3, TAWC:3}.
22
2121 DecDec 1010
CWAD:1 CWA:1
CD:1  C:1
CCHIHI
ẾẾ
UU TRÊNTRÊN D:4D:4
D
{CWA:2, CW:1, C:1} Cây cục bộ như sau:
{}
Item

Link
C4
{}
C:2C:3C:4
Đường đi đơn  Các tập con:
{, W:3,C:4, WC:3}
W3
W:2

ư
ờ
ng
đi
đ
ơn 
Cá
c
tậ
p con:
{, W:4,C:4, WC:4}
W4
W:4
ChiếutrênA sinh ra các tậpphổ biến
là:{A:4, AW:4, AC:4, AWC:4}.
24
2121 DecDec 1010
CCHIHIẾẾUU TRÊNTRÊN W,CW,C
C
W
W:5 {C:5} Cây cục bộ như sau:
{}
Đường đi đơn  Các tập con:
Item

Link
C5
C:5
{,C:5}
Chi

C
:

6

ta

được

{

}


tập

phổ

biến:{
C
:6}
.