167
TP CHÍ KHOA HC, ði hc Hu, S 65, 2011
MT THUT TOÁN KHAI PHÁ TP M#C L%I ÍCH CAO
TRONG CƠ S) D+ LI,U
Nguyn Phúc Xuân Quỳnh
Trưng ði hc Sư Phm, ði hc Hu
TÓM T.T
Khai phá t"p m#c l%i ích cao (high)utility itemset) là m.t m/ r.ng c0a bài toán khai
phá t"p m#c ph3 bin, ñã ñư%c nhi6u tác gi7 quan tâm v:i m#c ñích ñánh giá ý nghĩa c0a các
t"p m#c trong khai phá lu"t kt h%p. Thu"t toán hai pha (Two)Phase) là m.t trong các thu"t
toán khai phá t"p m#c l%i ích cao. Bài báo này ñ6 xuAt m.t c7i tin c0a thu"t toán Two)Phase.
ViCc c7i tin ñư%c thDc hiCn thông qua chin lư%c tFa hiCu qu7 hơn các t"p m#c Hng cI, c7i tin
bư:c sinh t"p Hng viên, nh ñó gi7m b:t ñư%c thi gian thDc hiCn thu"t toán khai phá.
1. ð0t v3n ñ6
Khai phá tri thc t d liu là mt trong nhng vn ñ nhn ñư!c nhiu s# quan
tâm c&a các nhà nghiên cu. Trong lĩnh v#c này, bài toán khai phá lut k/t h!p ñư!c
nghiên cu rng rãi. Mt hư2ng m3 rng bài toán là quan tâm ñ/n các tp m4c ñem l6i
l!i ích cao, quan tâm ñ/n mc ñ quan tr8ng khác nhau c&a các m4c d liu.
Mô hình khai phá tp m4c l!i ích cao ñã ñư!c Yao và cng s# ñ xut [7]), t ñó
ñã có mt s@ thut toán khai phá tp m4c l!i ích cao ñư!c ñưa ra trong [1, 2, 5, 6].
Y.Liu, Liao, Choudhary, 2005 [5] ñã ñưa ra khái nim l!i ích c&a giao tác và l!i
ích c&a tp m4c tính theo l!i ích c&a giao tác cha nó (l!i ích twu), tñó ñ xut thut
toán Two)Phase [5] khai phá tt cE các tp m4c l!i ích cao, tuy nhiên mt nhiu thFi
gian trong vic sinh ng viên v2i cơ s3 d liu l2n.
Vn ñ c&a các thut toán khai phá tp m4c l!i ích cao là giEm thiIu kích thư2c
c&a tp ng viên và ñơn giEn hóa quá trình tính toán l!i ích các tp m4c. NhKm giEm s@
lư!ng ng viên cho tp m4c l!i ích cao, giEm thFi gian khai phá, bài báo ñ xut thut
toán Im)Two)Phase trên cơ s3 cEi ti/n bư2c sinh tp ng viên và tính giá trL twu.
2. Các khái ni9m và ñ<nh nghĩa cơ bBn
PhNn này trình bày các ñLnh nghĩa, tính cht cơ bEn v tp m4c l!i ích cao t [5,
6, 7].
ð<nh nghĩa 2.1: Giá tr< khách quan cFa mGc ti mHt giao tác
MOi m4c i
p
trong giao tác T
q
, ñư!c ñPt tương ng v2i mt giá trL ñư!c g8i là giá
trL khách quan (objective value) c&a m4c i
p
t6i giao tác T
q
, ký hiu o(i
p
, T
q
). ChSng h6n,
168
giá trL khách quan c&a m4c i
p
trong giao tác T
q
có thI ly là s@ ñơn vL m4c i
p
bán ñư!c
trong giao tác T
q
(Giá trL xác ñLnh b3i ct cha m4c i
p
và hàng T
q
trong CSDL giao tác).
BBng 1. CSDL giao tác
A B C D E F G
T1 0 0 0 4 1 0 0
T2 0 5 0 5 1 0 0
T3 1 0 0 6 0 8 0
T4 10 0 5 0 1 0 0
T5 0 4 17 5 1 1 0
T6 0 0 0 0 0 0 72
ð<nh nghĩa 2.2: Giá tr< chF quan cFa mHt mGc
MOi m4c i
p
trong CSDL ñư!c ñPt tương ng v2i mt giá trL, ñư!c g8i là giá trL
ch& quan (subjective value) c&a m4c ñó, ký hiu s(i
p
). Giá trL này ñư!c cho trong mt
bEng kèm theo v2i CSDL giao tác g8i là bEng l!i ích. ChSng h6n, giá trL ch& quan c&a
m4c i
p
d#a trên ñánh giá l!i nhun c&a mOi ñơn vL m4c d liu ñem l6i.
BBng 2. B7ng l%i ích
MGc A B C D E F G
LMi nhuNn ($/ñơn v<) 1 3 1 4 7 2 1
L!i ích c&a mt tp m4c ñư!c ñánh giá qua hàm 2 bi/n như sau:
ð<nh nghĩa 2.3: Hàm lMi ích
G8i x là giá trL khách quan c&a mt m4c trong mt giao tác và y là giá trL ch&
quan c&a mt m4c. Mt hàm 2 bi/n
),( yxf
= R x R R ñơn ñiu tăng theo x và y g8i
là hàm l!i ích, thông thưFng hàm l!i ích ñư!c xác ñLnh yxyxf
×
=
),( .
ð<nh nghĩa 2.4: LMi ích cFa mHt mGc ti mHt giao tác
Cho hàm l!i ích ),( yxf . L!i ích c&a m4c
p
i
t6i giao tác
q
T
, ký hiu u(
p
i
,
q
T
)
là giá trL c&a hàm ),( yxf t6i
),(
qp
Tio
và
)(
p
is
, tc là:
),(
qp
Tiu
= f (
),(
qp
Tio
,
)(
p
is
).
ð<nh nghĩa 2.5: LMi ích cFa mHt tNp mGc ti giao tác
Cho tp m4c X
⊆
q
T
. L!i ích c&a tp m4c X t6i giao tác
q
T
, ký hiu
),(
q
TXu
,
là teng l!i ích c&a tt cE các m4c
p
i
thuc X t6i giao tác
q
T
:
),(),(
∑
∈
=
Xi
qpq
p
TiuTXu
v2i
X
⊆
q
T
.
169
Ký hiu
{
}
DBTTXTdb
qqqX
∈⊆= ,|
là tp các giao tác cha tp m4c X trong
CSDL DB.
ð<nh nghĩa 2.6: LMi ích cFa mHt tNp mGc trong CSDL
L!i ích (hay còn g8i là l!i ích th#c s#) c&a tp m4c X trong CSDL DB, ký hiu
u(X), là teng l!i ích c&a tp m4c X t6i các giao tác thuc
x
db :
∈ ∈∈
=
=
Xq pXq
dbT Xi qp
dbT qTiuTXuXu ),(),()(
ð<nh nghĩa 2.7: LMi ích cFa mHt giao tác
L!i ích c&a giao tác
q
T
, ký hiu tu(
q
T
), là teng l!i ích c&a tt cE các m4c d liu
trong giao tác: tu(
q
T
)=
),(
∈
qp
Ti qp
Tiu
.
ð<nh nghĩa 2.8: Giá tr< lMi ích ti thiZu
Giá trL l!i ích t@i thiIu (minutil) là tích c&a ngưing l!i ích t@i thiIu
δ
v2i teng
l!i ích c&a toàn b CSDL.
ð<nh nghĩa 2.9: TNp mGc lMi ích cao
Tp m4c X là tp m4c l!i ích cao n/u u(X)
≥
minutil (minutil>0).
ð<nh nghĩa 2.10: Bài toán khai phá tNp mGc lMi ích cao
Bài toán khai phá tp m4c l!i ích cao là bài toán tìm tp tt cE các tp m4c l!i
ích cao HU =
{
}
utilXuIXX min)(,|
≥
⊆
v2i CSDL giao tác DB và ràng buc
minutil cho trư2c.
ð<nh nghĩa 2.11: LMi ích kéo theo cFa tNp mGc
(Transaction Weighted Utility – TWU)
Cho tp m4c X và db
X
là tp tt cE các giao tác cha X. Ta g8i teng l!i ích c&a tt
cE các giao tác trong db
X
là l!i ích kéo theo (l%i ích twu) c&a X.
Ký hiu l!i ích kéo theo c&a X là twu(X), ta có:
twu(X)=tu(db
X
)=
)(
∑
∈
Xq
dbT q
Ttu
=
∑
∑
∈ ∈
Xq qp
dbT Ti qp
Tiu ),(
Ví d#: Trong ví d4 3 bEng 2.1 và bEng 2.2, X={B, D, E}. Có 2 giao tác cha X là
T
2
và T
5
.
twu(BDE)= tu(T
2
)+tu(T
5
)=
(o(B,T
2
)*s(B,T
2
)+o(D,T
2
)*s(D,T
2
)+o(E,T
2
)*s(E,T
2
))+
(o(B,T
5
)*s(B,T
5
)+o(C,T
5
)*s(C,T
5
)+o(D,T
5
)*s(D,T
5
)+o(E,T
5
)*s(E,T
5
))+o(F,T
5
)*s
170
(F,T
5
)) = (5.3+5.4+1.7)+(4.3+17.1+5.4+1.7+1.2)=42+58=100.
ð<nh nghĩa 2.12: TNp mGc có lMi ích kéo theo cao
Cho giá trL l!i ích t@i thiIu minutil>0, tp m4c X là tp m4c có l!i ích kéo theo
cao (hay còn gi là kéo theo cao) n/u twu(X)
≥
minutil.
ð<nh lý 2.1: Tính ch3t phBn ñơn ñi9u cFa lMi ích kéo theo
Cho X
k
là mt kmtp m4c, X
k)1
là mt (km1)mtp m4c con c&a X
k
(X
k)1
⊂
X
k
). N/u
X
k
có l!i ích kéo theo cao thì X
k)1
cũng có l!i ích kéo theo cao.
ChHng minh:
Vì X
k)1
⊂
X
k
, nên db
Xk
⊆
db
Xk)1
. Theo công thc tính twu 3 ñLnh nghĩa 2.11:
twu(X
k)1
)=
)(
1
∑
−
∈
k
Xq
dbT q
Ttu
≥
)(
∑
∈
k
Xq
dbT q
Ttu
=twu(X
k
)
Do ñó n/u twu(X
k
)
≥
minutil thì twu(X
k)1
)
≥
minutil.
Nh"n xét: Tính cht phEn ñơn ñiu c&a l!i ích kéo theo có nghĩa là n/u mt km
tp m4c X
k
có cha tp m4c con X
k)1
mà X
k)1
là tp m4c có l!i ích kéo theo thp thì X
k
cũng là tp m4c có l!i ích kéo theo thp. Các ng viên kmtp m4c l!i ích kéo theo cao
cho có thI có ñư!c t các k/t n@i c&a các (km1)mtp m4c có l!i ích kéo theo cao. D#a vào
nhn xét này, có thI sp d4ng các phương pháp khai phá tp m4c phe bi/n ñI tìm các tp
m4c l!i ích twu cao.
ð<nh lý 2.2: N/u X là tp m4c l!i ích cao thì X cũng là tp m4c có l!i ích kéo
theo cao.
ChHng minh:
Vì u(X, T
q
)
≤
tu(T
q
) nên u(X) =
),(
∈
Xq
dbT q
TXu
≤
)(
∑
∈
Xq
dbT q
Ttu
= twu(X)
Vy, n/u u(X)
≥
minutil thì twu(X)
≥
minutil.
3. ThuNt toán Im`Two`Phase
3.1. Cơ s lý thuyt
Trong thut toán Two)Phase [5], giá trL twu ñư!c so v2i minutil ñI sinh tp ng
viên cho tp m4c l!i ích cao. Tuy nhiên, trong bư2c tìm ra các 1mtp m4c có l!i ích twu
cao, nhn xét rKng các 1mtp m4c có l!i ích twu thp không tham gia vào quá trình sinh
tp ng viên cho tp m4c l!i ích cao (theo ñfnh lý 2.1 và 2.2) nên có thI bq ñi các 1mtp
m4c này trong tng giao tác. T ñó, giá trL tu sr tr ñi các giá trL l!i ích c&a 1mtp m4c
l!i ích thp, làm giá trL twu giEm ñi so v2i giá trL twu ban ñNu, thu g8n các ng viên hơn
khi so v2i minutil.
C4 thI, sau khi ñã có tp WHU
1
như trong thut toán Two)Phase, sau khi ñã có
171
tp WHU
1
, duyt CSDL lNn na ñI bq ñi các 1mtp m4c l!i ích thp trong tng giao tác
và cp nht l!i ích tu c&a tng giao tác:
for mOi giao tác T
∈
DB
Bq ñi các m4c X
∈
T \WHU
1
;
Cp nht l!i ích tu(T):=tu(T) )
∑
∈WHUTX
TXu
\
1
),(
;
Thut toán gi l6i các câu lnh còn l6i như c&a thut toán Two)Phase, tuy nhiên
cEi ti/n bư2c n@i trong quá trình sinh ng viên cho tp C
k
t tp WHU
k)1
:
Thay vì n@i
hai (km1)mtp m4c trong WHU
k)1
v2i
nhau ñI t6o ng viên cho tp C
k
như trong thut
toán Two)Phase, thì thut toán Im)Two)Phase sr n@i mt (km1)mtp m4c trong WHU
k)1
v2i 1mtp m4c trong WHU
1
giúp
thFi gian th#c hin c&a thut bư2c n@i ñư!c giEm
xu@ng.
Mnh ñ 2.1: ð phc t6p c&a bư2c n@i trong bư2c sinh ng viên C
k
trong thut
toán Two)Phase là O(
21
)(
−k
m
Ck ).
ChHng minh:
Trong thut toán Two)Phase, n@i hai (k)1))tp m4c trong WHU
km1
: s@ tp m4c
trong WHU
km1
t@i ña là
1−k
m
C
, v2i m là s@ m4c. S@ khE năng ch8n 2 tp m4c ra t
WHU
km1
là
2
1−k
m
C
C
. Khi xét hai (k)1))tp m4c này cNn t@i ña (k)1) phép so sánh, do ñó
teng s@ phép tính là: (km1)
2
1−k
m
C
C
. Ta có:
(km1).
2
1−k
m
C
C
= (km1). )!2(!2
!
1
1
−
−
−
k
m
k
m
C
C= (km1).
2
)1( 11 −
−− k
m
k
mCC
21
).(
−
≈
k
m
Ck
Mnh ñ 2.2: ð phc t6p c&a bư2c n@i c&a hàm Im_Gen_Ck trong thut toán
Im)Two)Phase là O(m.
1−k
m
C
).
ChHng minh:
Trong thut toán Im)Two)Phase, n@i mt (k)1))tp m4c trong WHU
km1
v2i 1mtp
m4c trong WHU
1
: WHU
1
có t@i ña m tp m4c, WHU
km1
có t@i ña
1−k
m
C
phNn tp, thut
toán ch8n mt (k)1))tp m4c trong WHU
km1
v2i 1mtp m4c trong WHU
1
, khi n@i cNn 1
phép so sánh, nên teng s@ phép tính: 1.m.
1−k
m
C, do ñó ñ phc t6p c&a thut toán này
là: O(m.
1−k
m
C
).
Như vy, thut toán Im)Two)Phase ñã giEm thFi gian bư2c n@i sinh tp ng viên