Xây dựng cây quyết định sủ dụng phụ thuộc hàm xấp xỉ

Ta.p ch´ı Tin ho. c va` Die`ˆu khieˆ’n ho. c, T.23, S.2 (2007), 179–186
XAˆY DU
.
. NG CAˆY QUYEˆ´T DI.NH SU
.’ DU. NG PHU. THUOˆ. C HA`M XAˆ´P XI
’
VU˜ DU´
.
C THI, TRA`ˆN QUANG DIEˆ. U
Vieˆ.n Coˆng ngheˆ. thoˆng tin, Vieˆ.n Khoa ho. c va` Coˆng ngheˆ. Vieˆ. t Nam
Abstract. In this paper, we introduce in brief on the concepts of Approximate Functional Depen-
dency (AFD), of Approximate Functionally Cross-Characteristic Dependency known as type II AFD
and describe an adoption of AFD to a constructing method of decisson tree for databases mining
purposes.
To´m ta˘´t. Trong ba`i ba´o na`y, chu´ng toˆi gio´.i thieˆ.u so
. lu.o.. c ve`ˆ kha´i nieˆ.m phu. thuoˆ.c ha`m xaˆ´p xı’, phu.
thuoˆ.c ha`m xaˆ´p xı’ lieˆn quan deˆ´n tu
.o.ng quan ha`m soˆ´ giu˜.a ca´c thuoˆ.c t´ınh cu’a moˆ.t quan heˆ. (Phu. thuoˆ.c
ha`m xaˆ´p xı’ loa.i hai) va` u´
.ng du.ng phu. thuoˆ.c ha`m xaˆ´p xı’ nha`˘m xaˆy du
.
. ng caˆy quyeˆ´t di.nh trong khai
pha´ du˜. lieˆ.u.
1. GIO´
.
I THIEˆ. U
Phu. thuoˆ.c ha`m xaˆ´p xı’ (Approximate Functional Dependency AFD) va` phu
.o.ng pha´p pha´t
hieˆ.n ca´c phu. thuoˆ.c ha`m xaˆ´p xı’ da˜ du
.o.. c nhie`ˆu ta´c gia’ de`ˆ caˆ.p va` u´
.ng du. ng trong nhie`ˆu ba`i
toa´n khai pha´ du˜. lieˆ.u ([1,3]). Phu. thuoˆ.c ha`m xaˆ´p xı’ la` moˆ. t phu. thuoˆ.c ha`m co´ t´ınh chaˆ´t ga`ˆn
du´ng doˆ´i vo´.i moˆ. t quan heˆ. r va` du
.o.. c di.nh ngh˜ıa nhu
. sau.
Di.nh ngh˜ıa 1. Phu. thuoˆ.c ha`m xaˆ´p xı’ (Approximate Functional Dependency - AFD)
Cho ε, 0 6 ε 6 1, X → Y la` phu. thuoˆ. c ha`m xaˆ´p xı’ neˆ´u: approx(X → Y ) 6 ε, vo´
.i
approx(X → Y ) = 1 (max {|s|, s la` taˆ.p con cu’a r va` X → Y du´ng treˆn s}/|r|).
O
.’ daˆy, |s|, |r| la` soˆ´ pha`ˆn tu.’ cu’a s va` r.
Trong ca´c ba`i toa´n qua’n ly´ thu.. c teˆ´, thu
.`o.ng xa’y ra ca´c nho´m thuoˆ. c t´ınh co´ su
.
. lieˆn quan
du.´o.i da.ng ha`m soˆ´ vo´
.i nhau (tuyeˆ´n t´ınh hoa˘.c phi tuyeˆ´n). Doˆ´i vo´
.i ca´c tru.`o.ng ho.. p na`y, ta
xe´t deˆ´n phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai - phu. thuoˆ. c ha`m xaˆ´p xı’ lieˆn quan deˆ´n tu
.o.ng quan
ha`m soˆ´ giu˜.a ca´c thuoˆ. c t´ınh cu’a moˆ. t quan heˆ..
Vieˆ.c xaˆy du
.
. ng caˆy quyeˆ´t di.nh trong khai pha´ du˜
. lieˆ.u da˜ du
.o.. c nhie`ˆu ta´c gia’ de`ˆ caˆ.p deˆ´n
trong ca´c phu.o.ng pha´p khai pha´ du˜. lieˆ.u nha`˘m keˆ´t xuaˆ´t ca´c thoˆng tin hu˜
.u ı´ch tie`ˆm aˆ’n trong
ca´c co. so.’ du˜. lieˆ.u lo´
.n. Caˆy quyeˆ´t di.nh la` moˆ.t kieˆ’u moˆ h`ınh du
.
. ba´o (predictive model), ngh˜ıa
la` moˆ. t a´nh xa. tu`
. ca´c quan sa´t ve`ˆ moˆ. t su
.
. vaˆ. t/hieˆ.n tu
.o.. ng to´
.i ca´c keˆ´t luaˆ.n ve`ˆ gia´ tri. mu. c tieˆu
cu’a su.. vaˆ.t/hieˆ.n tu
.o.. ng. Caˆy quyeˆ´t di.nh co´ caˆ´u tru´c h`ınh caˆy va` la` moˆ. t su
.
. tu
.o.. ng tru
.ng cu’a
moˆ. t phu
.o.ng thu´.c quyeˆ´t di.nh cho vieˆ.c xa´c di.nh lo´
.p ca´c su.. kieˆ.n da˜ cho. Moˆ˜i nu´t cu’a caˆy chı’
ra moˆ. t teˆn lo´
.p hoa˘. c moˆ.t phe´p thu
.’ cu. theˆ’, phe´p thu
.’ na`y chia khoˆng gian ca´c du˜. lieˆ.u ta.i nu´t
do´ tha`nh ca´c keˆ´t qua’ co´ theˆ’ da. t du
.o.. c cu’a phe´p thu
.’ . Moˆ˜i taˆ.p con du
.o.. c chia ra la` khoˆng
gian con cu’a ca´c du˜. lieˆ.u du
.o.. c tu
.o.ng u´.ng vo´.i vaˆ´n de`ˆ con cu’a su.. phaˆn lo´
.p. Su.. phaˆn chia na`y
180 VU˜ DU´.C THI, TRA`ˆN QUANG DIEˆ. U
thoˆng qua moˆ. t caˆy con tu
.o.ng u´.ng. Qua´ tr`ınh xaˆy du.. ng caˆy quyeˆ´t di.nh co´ theˆ’ xem nhu
. la`
moˆ. t chieˆ´n thuaˆ.t chia deˆ’ tri. cho su
.
. phaˆn lo´
.p doˆ´i tu.o.. ng ([4–6]). Moˆ.t caˆy quyeˆ´t di.nh co´ theˆ’
moˆ ta’ ba`˘ng ca´c kha´i nieˆ.m nu´t va` du
.`o.ng noˆ´i ca´c nu´t trong caˆy. Vieˆ.c nghieˆn cu´
.u xaˆy du.. ng
caˆy quyeˆ´t di.nh mang la. i hieˆ.u qua’ toˆ´t cho vieˆ.c la`m trong sa.ch du˜
. lieˆ.u, pha´t hieˆ.n sai so´t va`
du.a ra quyeˆ´t di.nh phu` ho
.
. p trong tu`
.ng hoa`n ca’nh va` chieˆ´n lu.o.. c cu. theˆ’ cu’a ba`i toa´n qua’n
ly´.
Phu. thuoˆ. c ha`m (FDs) da˜ du
.o.. c nghieˆn cu´
.u raˆ´t nhie`ˆu trong khi phaˆn t´ıch, thieˆ´t keˆ´ co. so.’
du˜. lieˆ.u. Phu. thuoˆ.c ha`m giu˜
.a ca´c thuoˆ. c t´ınh quan heˆ. cho phe´p xa´c di.nh ch´ınh xa´c ca´c moˆ´i
quan heˆ. trong co
. so.’ du˜. lieˆ.u ([2]). Ca´c ra`ng buoˆ. c do phu. thuoˆ.c ha`m quy di.nh trong so
. doˆ`
quan heˆ. tu
.o.ng doˆ´i doˆ. c laˆ.p vo´
.i du˜. lieˆ.u. Vieˆ.c xaˆy du
.
. ng caˆy quyeˆ´t di.nh su
.’ du.ng phu. thuoˆ. c
ha`m se˜ mang la. i hieˆ.u qua’ toˆ´t do ca´c t´ınh chaˆ´t ra`ng buoˆ. c cha˘. t cu’a phu. thuoˆ.c ha`m.
Trong ba`i ba´o na`y, chu´ng toˆi tr`ınh ba`y ve`ˆ kha´i nieˆ.m phu. thuoˆ. c ha`m xaˆ´p xı’, phu. thuoˆ. c
ha`m xaˆ´p xı’ loa.i hai, moˆ. t soˆ´ t´ınh chaˆ´t cu’a phu. thuoˆ. c ha`m xaˆ´p xı’ va` u´
.ng du.ng va`o vieˆ.c xaˆy
du.. ng caˆy quyeˆ´t di.nh trong khai pha´ du˜
. lieˆ.u.
2. PHU. THUOˆ. C HA`M XA´ˆP XI
’ LOA. I HAI
Cho r la` moˆ.t quan heˆ. treˆn taˆ.p thuoˆ.c t´ınh R = {A1, A2, ...An} trong do´ ca´c thuoˆ.c t´ınh
A1,A2, ...An co´ theˆ’ la` thuoˆ.c t´ınh di.nh danh, ro`
.i ra.c hoa˘. c lieˆn tu. c. Doˆ´i vo´
.i nhu˜.ng thuoˆ. c t´ınh
di.nh danh, ta tieˆ´n ha`nh thu
.
. c hieˆ.n a´nh xa. taˆ´t ca’ ca´c gia´ tri. co´ theˆ’ to´
.i moˆ.t taˆ.p ca´c soˆ´ nguyeˆn
du.o.ng lie`ˆn ke`ˆ.
Di.nh ngh˜ıa 2. (Khoa’ng ca´ch giu˜
.a 2 boˆ. gia´ tri. treˆn taˆ.p thuoˆ. c t´ınh)
Vo´.i 2 boˆ. t1, t2 ∈ r, ta ky´ hieˆ.u ρ(t1(X), t2(X)) la` khoa’ng ca´ch giu˜
.a t1 va` t2 treˆn taˆ.p thuoˆ. c
t´ınh X ⊆ R, du.o.. c xa´c di.nh nhu
. sau
ρ(t1(X), t2(X)) = max(|t1(Ai)− t2(Ai)|)/max(|t1(Ai), t2(Ai)|), Ai ∈ X).
Ha`m max(x, y) la` ha`m cho.n ra soˆ´ lo´
.n nhaˆ´t trong 2 soˆ´ x,y.
Tru.`o.ng ho.. p max(|t1(Ai)|, |t2(Ai)|) = 0, tu´
.c t1(Ai) = t2(Ai) = 0 th`ı ta qui u.´o.c
|t1(Ai)− t2(Ai)|/max(|t1(Ai)|, |t2(Ai)|) = 0.
Khoa’ng ca´ch giu˜.a 2 boˆ. gia´ tri. treˆn taˆ.p thuoˆ.c t´ınh co´ theˆ’ coi la` ha`m soˆ´ cu’a ca´c doˆ´i soˆ´ la`
ca´c boˆ. gia´ tri. cu’a quan heˆ. va` taˆ.p ca´c thuoˆ.c t´ınh.
Moˆ.t soˆ´ t´ınh chaˆ´t cu’a ha`m khoa’ng ca´ch ρ(t1(X), t2(X)).
Di.nh ngh˜ıa khoa’ng ca´ch ρ(t1(X), t2(X)) neˆu treˆn tho’a ma˜n ca´c t´ınh chaˆ´t cu’a ha`m khoa’ng
ca´ch:
1. ρ(t1(X), t2(X)) > 0 vo´
.i t1, t2, X tu`y y´
2. ρ(t1(X), t2(X)) = 0⇔ t1(X) = t2(X)
3. ρ(t1(X), t2(X)) > ρ(t1(X), t3(X)) + ρ(t3(X), t2(X))
4. Neˆ´u X ⊆ Y th`ı ρ(t1(X), t2(X))> ρ(t1(Y ), t2(Y ))
5. ρ(t1(XY ), t2(XY )) = max(ρ(t1(X), t2(X)), ρ(t1(Y ), t2(Y ))).
XAˆY DU.
.
NG CAˆY QUYE´ˆT DI.NH SU
.’ DU. NG PHU. THUOˆ. C HA`M XA´ˆP XI
’ 181
Di.nh ngh˜ıa 3. (Phu. thuoˆ.c ha`m xaˆ´p xı’ loa.i hai - Type II Approximate Functional Depen-
dency)
Gia’ su.’ X, Y ⊆ R va` vo´.i moˆ. t soˆ´ δ cho tru
.´o.c, 0 6 δ < 1, ta no´i ra˘`ng X xa´c di.nh ha`m Y
mu´.c δ (hoa˘.c no´i ra˘`ng X , Y co´ phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai mu´
.c δ), ky´ hieˆ.u la` X ≈>δ Y
neˆ´u vo´.i mo.i ca˘.p boˆ. t1, t2 ∈ r, ma` ρ(t1(X), t2(X)) 6 ε th`ı ta cu˜ng co´ ρ(t1(Y ), t2(Y )) 6 ε.
Meˆ.nh de`ˆ 1. (Die`ˆu kieˆ.n deˆ’ phu. thuoˆ.c ha`m xaˆ´p xı’ la` phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai)
Gia’ su.’ approx(X → Y ) la` moˆ. t phu. thuoˆ. c ha`m xaˆ´p xı’ vo´
.i doˆ. xaˆ´p xı’ ε. Phu. thuoˆ. c ha`m
xaˆ´p xı’ approx(X → Y ) la` phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i hai mu´
.c δ = ε(X ≈>δ Y ) khi va` chı’ khi
u´.ng vo´.i ε vo´.i mo. i ca˘. p boˆ. t1, t2 ∈ r, ma` ρ(t1(X), t2(X)) 6 ε.
Ta thaˆ´y meˆ.nh de`ˆ treˆn hoa`n toa`n du´ng vo´
.i theo di.nh ngh˜ıa va` ca´c t´ınh chaˆ´t cu’a phu.
thuoˆ. c ha`m xaˆ´p xı’ loa.i hai.
Thuaˆ. t toa´n 1. Kieˆ’m tra phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai
Bu.´o.c 1: Xaˆy du.. ng heˆ. xaˆ´p xı’ mu´
.c δ cu’a r: Erδ.
Bu.´o.c 2: Vo´.i moˆ˜i E(δ)i,j ∈ Erδ (vo´.i 1 6 i < j 6 m) la`ˆn lu.o.. t kieˆ’m tra die`ˆu kieˆ.n
X ⊆ E(δ)i,j)⇒ (Y ⊆ E(δ)i,j).
+ Neˆ´u co´ toˆ`n ta. i X ⊆ E(δ)i,j va` Y * E(δ)i,j th`ı du`.ng vieˆ.c kieˆ’m tra va` keˆ´t luaˆ.n r khoˆng
tho’a phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i hai mu´
.c δ.
+ Neˆ´u vo´.i mo. i E(δ)i,j ∈ Erδ tho’a ma˜n die`ˆu kieˆ.n (X ⊆ E(δ)i,j)⇔ (Y ⊆ E(δ)i,j) th`ı keˆ´t
luaˆ.n r tho’a phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai mu´
.c δ.
Thuaˆ. t toa´n 2. Xaˆy du
.
. ng caˆy quyeˆ´t di.nh su
.’ du.ng phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai
Da`ˆu va`o: Maˆ˜u thu.’ (Examples) va` xa´c di.nh ca´c phu. thuoˆ.c ha`m xaˆ´p xı’ loa.i hai du
.o.. c t´ınh
treˆn taˆ.p du˜
. lieˆ.u maˆ˜u.
Da`ˆu ra: Caˆy quyeˆ´t di.nh du
.
. a treˆn phu. thuoˆ.c ha`m.
Bu.´o.c 1. Xa´c di.nh nhie˜ˆu cu’a maˆ˜u thu
.’ (MajorityClass(Examplesi)).
Bu.´o.c 2. Cho.n ca´c phu. thuoˆ. c ha`m xaˆ´p xı’ co´ mu´
.c doˆ. nhie˜ˆu trong mu´
.c xaˆ´p xı’ δ,
approx(X → Y ) 6 δ.
Bu.´o.c 3. Kieˆ’m tra phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai cho taˆ.p phu. thuoˆ. c ha`m xaˆ´p xı’ t`ım du
.o.. c o
.’
Bu.´o.c 2 (X ≈>δ Y ).
+ Cho.n phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai co´ mu´
.c xaˆ´p xı’ nho’ nhaˆ´t (X ≈>min(δ) Y )
+ Ta.o caˆy quyeˆ´t di.nh vo´
.i goˆ´c la` phu. thuoˆ. c ha`m xaˆ´p xı’ vu`
.a cho.n
DT = BuildDecisionTree(Examplei, X ≈>min(δ) Y,MajorityClass(examples)).
+ Vo´.i moˆ˜i gia´ tri. vi cu’a taˆ.p phu. thuoˆ.c ha`m xaˆ´p xı’, t´ınh
• Maˆ˜u thu.’ Examplei = {Ki ⊆ Example vo´
.i X ≈>minδ Y = vi}
• Subtree = BuildDecisionTree(Examplei, X ≈>minδ Y,MajorityClass(examples))
• Theˆm moˆ. t nha´nh Subtree va`o caˆy vo´
.i nha˜n la` vi
Vı´ du. 1. Gia’ su
.’ ta co´ taˆ.p huaˆ´n luyeˆ.n nhu
. sau (Ba’ng 1)
Chu´ng ta co´ theˆ’ xaˆy du.. ng ca´c phu. thuoˆ. c ha`m xı’ loa.i hai vo´
.i mu´.c xaˆ´p xı’ δ = 0.05 nhu.
sau.
182 VU˜ DU´.C THI, TRA`ˆN QUANG DIEˆ. U
Ta thaˆ´y giu˜.a thuoˆ.c t´ınh Tuoˆ’i, Heˆ. soˆ´ lu
.o.ng co´ moˆ´i tu.o.ng quan vo´.i chu´.c danh. Vo´.i
δ = 0.05 ta kieˆ’m tra die`ˆu kieˆ.n doˆ´i vo´
.i phu. thuoˆ. c ha`m xaˆ´p xı’:
Ba’ng 1
STT Tuoˆ’i HSL Nga.ch CC HV Hoa`n tha`nh
coˆng vieˆ.c
1 >40 Cao Nghieˆn cu´.u vieˆn ch´ınh Tieˆ´n s˜ı khoa ho.c Co´
2 >40 Cao Nghieˆn cu´.u vieˆn ch´ınh Tieˆ´n s˜ı Co´
3 >40 Trung b`ınh Nghieˆn cu´.u vieˆn Tieˆ´n s˜ı Co´
4 >40 Trung b`ınh Nghieˆn cu´.u vieˆn Tha.c s˜ı Khoˆng
5 30-40 Trung b`ınh Nghieˆn cu´.u vieˆn ch´ınh Tieˆ´n s˜ı Co´
6 30-40 Thaˆ´p Nghieˆn cu´.u vieˆn Tha.c s˜ı Khoˆng
7 <30 Trung b`ınh Nghieˆn cu´.u vieˆn Tieˆ´n s˜ı Co´
8 <30 Thaˆ´p Nghieˆn cu´.u vieˆn Tha.c s˜ı Khoˆng
9 30-40 Thaˆ´p Nghieˆn cu´.u vieˆn Tha.c s˜ı Khoˆng
Vo´.i ca˘.p ha`ng 1, 2 ta co´ ρ(t1 (Tuoˆ’i, Heˆ. soˆ´ lu
.o.ng), t2 (Tuoˆ’i, Heˆ. soˆ´ lu
.o.ng)) = 0 < 0.05.
Ta cu˜ng t´ınh du.o.. c ρ(t1 (Co´ theˆ’ giao nhieˆ.m vu. ), t2(Co´ theˆ’ giao nhieˆ.m vu. )) = 0 < 0.05.
Tu.o.ng tu.. ta cu˜ng kieˆ’m tra de˜ˆ da`ng vo´
.i ca´c coˆ. t co`n la. i, vaˆ.y ta co´ phu. thuoˆ.c ha`m Tuoˆ’i,
heˆ. soˆ´ lu
.o.ng ≈>0.05 Co´ theˆ’ giao nhieˆ.m vu. .
Sau khi t`ım taˆ´t ca’ ca´c phu. thuoˆ.c ha`m xaˆ´p xı’ phu` ho
.
. p vo´
.i qua´ tr`ınh xaˆy du.. ng caˆy quyeˆ´t
di.nh, ta co´ theˆ’ xaˆy du
.
. ng du
.o.. c caˆy quyeˆ´t di.nh nhu
. sau (Hı`nh 1).
H`ınh 1. Caˆy quyeˆ´t di.nh
Thu.’ nghieˆ.m so sa´nh treˆn taˆ.p du˜
. lieˆ.u huaˆ´n luyeˆ.n cu’a ho
.n 5000 ca´n boˆ. coˆng chu´
.c cu’a
Vieˆ.n Khoa ho.c va` Coˆng ngheˆ. Vieˆ.t Nam du`ng moˆ. t soˆ´ phu
.o.ng pha´p xaˆy du.. ng caˆy quyeˆ´t di.nh
nhu. ID3, C4.5 th`ı thaˆ´y ra`˘ng su.’ du. ng thuaˆ. t toa´n xaˆy du
.
. ng caˆy quyeˆ´t di.nh su
.’ du.ng phu.
thuoˆ. c ha`m xaˆ´p xı’ loa.i hai co´ tho`
.i gian xu.’ ly´ nhanh ho.n va` doˆ. ch´ınh xa´c tu
.o.ng u´.ng.
Vaˆ´n de`ˆ co. so.’ du˜. lieˆ.u da˜ du
.o.. c nghieˆn cu´
.u tu`. raˆ´t so´.m trong qua´ tr`ınh pha´t trieˆ’n cu’a
coˆng ngheˆ. thoˆng tin, ca´c kha´i nieˆ.m, t´ınh chaˆ´t cu’a co
. so.’ du˜. lieˆ.u da˘. c bieˆ.t la` phu. thuoˆ. c ha`m
trong co. so.’ du˜. lieˆ.u quan heˆ. da˜ du
.o.. c chu´
.ng minh moˆ. t ca´ch cha˘. t che˜. Kha´c vo´
.i vieˆ.c lu
.
. a cho.n
kha´ ca’m t´ınh trong ca´c phu.o.ng pha´p lu.. a cho.n thuoˆ.c t´ınh deˆ’ pha´t trieˆ’n kha´c, tuy nhieˆn, vo´
.i
di.nh ngh˜ıa cha˘. t nhu
. phu. thuoˆ. c ha`m da˜ du
.o.. c neˆu o
.’ treˆn th`ı khi ga˘.p moˆ. t co
. so.’ du˜. lieˆ.u lo´
.n
XAˆY DU.
.
NG CAˆY QUYE´ˆT DI.NH SU
.’ DU. NG PHU. THUOˆ. C HA`M XA´ˆP XI
’ 183
va` phu´.c ta.p, vieˆ.c xa´c di.nh ca´c phu. thuoˆ. c ha`m raˆ´t kho´ kha˘n, ch´ınh v`ı theˆ´ phu
.o.ng pha´p xaˆy
du.. ng caˆy quyeˆ´t dinh du
.
. a treˆn phu. thuoˆ. c ha`m xaˆ´p xı’ loa.i hai da˜ pha`ˆn na`o gia’ i quyeˆ´t ca´c
vaˆ´n de`ˆ treˆn.
Treˆn daˆy la` moˆ. t soˆ´ keˆ´t qua’ nghieˆn cu´
.u ve`ˆ phu. thuoˆ. c ha`m xaˆ´p xı’, phu. thuoˆ. c ha`m xaˆ´p
xı’ loa.i hai va` u´
.ng du.ng trong xaˆy du
.
. ng caˆy quyeˆ´t di.nh su
.’ du. ng phu. thuoˆ.c ha`m trong khai
pha´ du˜. lieˆ.u. Ca´c keˆ´t qua’ nghieˆn cu´
.u ve`ˆ nhu˜.ng vaˆ´n de`ˆ na`y co´ y´ ngh˜ıa trong vieˆ.c gia’ i quyeˆ´t
moˆ. t soˆ´ ba`i toa´n thu
.
. c teˆ´ khi khai pha´ du˜
. lieˆ.u vo´
.i co. so.’ du˜. lieˆ.u lo´
.n nha`˘m du.a ra ca´c quyeˆ´t
di.nh phu` ho
.
. p vo´
.i ba`i toa´n thu.. c teˆ´ nhu
. qua’n ly´ kinh teˆ´, khai pha´ tri thu´.c, heˆ. chuyeˆn gia...
TA`I LIEˆ. U THAM KHA
’O
[1] B. Liu, W. Hsu, and Y. Ma, Integrating classification and association mining, Proc.
1998 Int. Conf. Knowledge Discovery and Data mining (KDD’98), New York (80–86).
[2] Vu˜ Du´.c Thi, Co. so.’ du˜. lieˆ.u- kieˆ´n thu´
.c va` thu.. c ha`nh, Nha` xuaˆ´t ba’n Thoˆ´ng keˆ, 1997.
[3] Yka, Huhtala, Juha Kahkkainen, Pasi Porkka, Hannu Toivonen, An efficient algorithm
for discovering functional and approximate dependencies, Proc.14th Int, Conf. on Data
Engineering (ICDE ’98), IEEE. Computer Society Press (392–401).
[4] Ho Tu Bao, Knowledge discovery and data mining techniques and practice,
˜ao/
[5] P.E. Utgoff, Incremental induction of decision trees,
www.cs.umass.edu/u˜tgoff/papers/mlj-id5r.pdf 1989.
[6] Tutorial: Decision Tree: ID3, Monhash University, 2003,
[7] Ullas Nambiar, Subbarao Kambhampati, Mining approximate functional dependencies
and concept similarities to answer imprecise queries, Seventh International Workshop on
the Web and Database, Paris, France, June 17-18, 2004.
[8] Lopes Stepane, Pettit, Jean-Marc, and Lakhal, Lotfi, Efficient discovery of functional
dependencies and armstrong relations, Proceeding of ECDT 2000, Lecture Notes in Com-
puter Science, Vol 1777.
[9] N. Novelli, R. Ciccbetti, Fun: and efficient algorithm for mining functional and embed-
ded dependencies, Lecture Notes in Computer Science ICDT 2001 (189–203).
[10] Kwok-Wa Lam, Victor C. S. Lee, Building decision trees using functional dependen-
cies, Proceedings of the International Conference on Information Technology: Coding
and Computing (ITCC 2004) (470–473).
Nhaˆ. n ba`i nga`y 4 - 4 - 2007
Nhaˆ. n la. i sau su
.’ a nga`y 6 - 5 - 2007