Phụ thuộc hàm xấp xỉ và phần tử ngoại lai đối với phụ thuộc hàm

Ta. p ch´ı Tin ho. c va` Die`ˆu khieˆ’n ho. c, T.23, S.1 (2007), 80—85
PHU. THUOˆ. C HA`M XAˆ´P XI
’ VA` PHA`ˆN TU
.’ NGOA. I LAI
DOˆ´I VO´
.
I PHU. THUOˆ. C HA`M
VU˜ DU´
.
C THI1, PHA. M HA. THUY
’ 2
1Vieˆ. n Coˆng ngheˆ. thoˆng tin, Vieˆ. n Khoa ho. c va` Coˆng ngheˆ. Vieˆ. t Nam
2Trung taˆm Khoa ho. c va` BDCB - Kieˆ’m toa´n Nha` nu
.´o.c
Abstract. The aim of this paper is to present the concepts about Type 2 Approximate Functional
Dependency - AFD 2 (relating to the correlation between atributes of the relational file) and the
outliers with functional dependency. The paper also gives some properties of ADF 2 and algorithms
for finding the outliers with functional dependency.
To´m ta˘´t. Ba`i ba´o gio´.i thieˆ.u ve`ˆ phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2 (loa. i phu. thuoˆ.c ha`m xaˆ´p xı’ lieˆn quan
deˆ´n su.. tu
.o.ng quan giu˜.a ca´c thuoˆ. c t´ınh cu’a moˆ.t quan heˆ.) va` pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c
ha`m. Ba`i ba´o cu˜ng tr`ınh ba`y moˆ.t soˆ´ t´ınh chaˆ´t cu’a phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i 2 va` thuaˆ. t toa´n xa´c
di.nh pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m.
GIO´
.
I THIEˆ. U
Kha´i nieˆ.m phu. thuoˆ.c ha`m xaˆ´p xı’ (Approximate functional dependency) 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 deˆ´n va` du
.o.. c u´
.ng du.ng
trong nhie`ˆu ba`i toa´n phaˆn lo´.p cu’a data mining ([1, 2]). Nhu˜.ng phu. thuoˆ.c nhu
. vaˆ.y bieˆ’u die˜ˆn
su.. phu. thuoˆ.c tu
.
. nhieˆn giu˜
.a ca´c thuoˆ.c t´ınh trong moˆ.t quan heˆ. nhu
.ng co´ chu´.a moˆ.t va`i ha`ng
co´ sai so´t hoa˘.c khoˆng tho’a luaˆ. t (go. i la` phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 1). Moˆ.t tru
.`o.ng ho.. p phu.
thuoˆ.c xaˆ´p xı’ kha´c la` co´ nhu˜
.ng nho´m thuoˆ.c t´ınh ma˘.c du` giu˜
.a chu´ng khoˆng co´ su.. phu. thuoˆ.c
ha`m theo kieˆ’u ba`˘ng nhau tuyeˆ.t doˆ´i (theo ca´ch di.nh ngh˜ıa phu. thuoˆ.c ha`m thoˆng thu
.`o.ng) ma`
co´ su.. phu. thuoˆ.c xaˆ´p xı’ theo kieˆ’u tu
.o.ng quan ha`m soˆ´ (tuyeˆ´n t´ınh hoa˘.c phi tuyeˆ´n), (go. i la` phu.
thuoˆ.c ha`m xaˆ´p xı’ loa. i 2). Tru
.`o.ng ho.. p na`y xa’y ra kha´ nhie`ˆu va` lieˆn quan deˆ´n nhie`ˆu ba`i toa´n
thu.. c teˆ´. V´ı du. trong ba’ng quan heˆ. ghi la. i t`ınh h`ınh mua va`o ca´c loa. i ha`ng ho´a cu’a moˆ.t doanh
nghieˆ.p ta thaˆ´y quan heˆ. giu˜
.a khoˆ´i lu.o.. ng ha`ng mua va`o va` chi ph´ı deˆ’ mua la` phu. thuoˆ.c ha`m
xaˆ´p xı’ loa. i 2. Neˆ´u su
.
. cheˆnh leˆ.ch giu˜
.a khoˆ´i lu.o.. ng ha`ng mua va`o nho’ ho
.n moˆ.t mu´
.c na`o do´
th`ı cu˜ng ke´o theo su.. cheˆnh leˆ.ch cu’a chi ph´ı hai do
.
. t mua cu˜ng nho’ (gia´ tri. cu’a hai ba’n ghi ta. i
ca´c thuoˆ.c t´ınh na`y du
.o.. c phe´p co´ su
.
. cheˆnh leˆ.ch tu
.o.ng u´.ng). Cu˜ng vaˆ.y doˆ´i vo´
.i chı’ tieˆu doanh
thu va` chi ph´ı trong ba’ng keˆ ve`ˆ tinh h`ınh kinh doanh... Vieˆ.c kha’o sa´t loa. i phu. thuoˆ.c ha`m
xaˆ´p xı’ na`y co´ u´.ng du.ng thu
.
. c tie˜ˆn trong vieˆ.c pha´t hieˆ.n nhu˜
.ng hieˆ.n tu
.o.. ng baˆ´t thu
.`o.ng (ngoa. i
lai) trong sa’n xuaˆ´t kinh doanh, phu. c vu. cho hoa.t doˆ.ng kieˆ’m toa´n va` qua’n ly´ kinh teˆ´. Vieˆ.c
quyeˆ´t di.nh mu´
.c cheˆnh leˆ.ch cho phe´p (vu
.o.. t qua´ mu´
.c do´ la` hieˆ.n tu
.o.. ng baˆ´t thu
.`o.ng) thu.`o.ng
du.o.. c xa´c di.nh theo hu
.´o.ng hoˆ˜ tro.. quyeˆ´t di.nh ([3]) co´ ngh˜ıa la` co`n tu`y thuoˆ.c theˆm ca´c yeˆ´u toˆ´
ve`ˆ yeˆu ca`ˆu va` kinh nghieˆ.m cu’a ca´c chuyeˆn gia trong ca´c l˜ınh vu
.
. c thu
.
. c teˆ´.
PHU. THUOˆ. C HA`M XA´ˆP XI
’ VA` PHA`ˆN TU
.’ NGOA. I LAI 81
Du.´o.i daˆy la` kha´i nieˆ.m cu’a phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2 va` kha’o sa´t moˆ. t soˆ´ t´ınh chaˆ´t cu’a
no´. Doˆ`ng tho`.i, moˆ.t soˆ´ kha´i nieˆ.m, di.nh ngh˜ıa ve`ˆ pha`ˆn tu
.’ ngoa. i lai theo phu. thuoˆ.c ha`m va`
ca´c meˆ.nh de`ˆ la`m co
. so.’ cho vieˆ.c xaˆy du
.
. ng thuaˆ. t toa´n xa´c di.nh pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i phu.
thuoˆ.c ha`m cu˜ng du
.o.. c tr`ınh ba`y.
1. KHA´I NIEˆ.M PHU. THUOˆ. C HA`M XA´ˆP XI
’ LOA. I 2
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` ca´c thuoˆ.c t´ınh di.nh danh(categorical), ro`
.i ra.c hoa˘.c lieˆn tu. c (tru
.`o.ng soˆ´).
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 1.1. (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 k´ı 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, 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ˆ´ va`
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))
De˜ˆ da`ng chu´.ng minh di.nh ngh˜ıa khoa’ng ca´ch ρ(t1(X), t2(X)) tho’a ma˜n ca´c t´ınh chaˆ´t cu’a
ha`m khoa’ng ca´ch ∀t1, t2, t3 ∈ r, ∀X, Y ⊆ R, ta co´:
a1) ρ(t1(X), t2(X)) 
 0
a2) ρ(t1(X), t2(X)) = 0↔ t1(X) = t2(X)
a3) ρ(t1(X), t2(X))  ρ(t1(X), t3(X)) + ρ(t3(X), t2(X))
Va` ngoa`i ra cu˜ng de˜ˆ chu´.ng minh ca´c t´ınh chaˆ´t sau:
a4) Neˆ´u X ⊆ Y th`ı ρ(t1(X), t2(X))  ρ(t1(Y ), t2(Y ))
a5) ρ(t1(XY ), t2(XY )) = max(ρ(t1(X), t2(X)), ρ(t1(Y ), t2(Y )))
Di.nh ngh˜ıa 1.2. (phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2 - Type 2 Approcimate Functional Depen-
dency). Gia’ su.’ X, Y ⊆ R va` vo´.i moˆ.t soˆ´ δ cho tru
.´o.c, 0  δ < 1, ta no´i ra`˘ng X xa´c di.nh ha`m
Y mu´.c δ (hoa˘.c giu˜
.a X,Y co´ phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2 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))  δ th`ı ta cu˜ng co´ ρ(t1(Y ), t2(Y ))  δ.
Vı´ du. 1. Xe´t ba’ng quan heˆ. sau:
A B C D E
2.5 18 160 25 12
2.51 18 160.5 15 13
3.6 20 320 30 16
3.65 20 323 45 28
4.25 25 641 60 19
4.26 25 643 70 57
82 VU˜ DU´.C THI, PHA. M HA. THUY’
Ta thaˆ´y giu˜.a ca´c coˆ. t A, B co´ moˆ´i tu
.o.ng quan vo´.i coˆ. t C. Vo´
.i δ = 0.05 ta kieˆ’m tra die`ˆu
kieˆ.n phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2: AB →0.05 C.
Vo´.i ca˘.p ha`ng 1, 2, ta co´
ρ(t1(AB),t2(AB))
= max(|t1(A)− t2(A)|/max(|t1(A)|, |t2(A)|), |t1(B)− t2(B)|/max(|t1(B)|, |t2(B)|)
= 0.00394 < 0.05.
Ta cu˜ng t´ınh du.o.. c: ρ(t1(C), t2(C)) = 0.00311 < 0.05.
Tu.o.ng tu.. ta cu˜ng se˜ kieˆ’m tra de˜ˆ da`ng vo´
.i ca˘.p ha`ng 3, 4 va` ca˘.p ha`ng 5, 6 cu˜ng nhu
. ca´c
ca˘.p ha`ng kha´c.
Vaˆ.y ta co´: AB ≈>0.05 C (AB xa´c di.nh ha`m C mu´
.c 0.05).
2. MOˆ. T SOˆ´ TI´NH CHAˆ´T CU
’A PHU. THUOˆ. C HA`M XA´ˆP XI
’ LOA. I 2
T´ınh chaˆ´t 1. Cho r la` moˆ. t quan heˆ. treˆn taˆ. p thuoˆ. c t´ınh R. Moˆ. t phu. thuoˆ. c ha`m du´ng treˆn r
cu˜ng la` phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i 2 vo´
.i mu´.c δ tu`y y´ (0  δ < 1) du´ng treˆn r.
T´ınh chaˆ´t na`y de˜ˆ da`ng suy theo Di.nh ngh˜ıa 1.2.
T´ınh chaˆ´t 2. Cho r la` moˆ. t quan heˆ. treˆn R;X, Y ⊆ R; δ1, δ2 la` hai soˆ´ sao cho 0  δ1 < δ2 < 1.
Kı´ hieˆ. u X ≈>δ1 Y va` X ≈>δ2 Y la` hai phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i 2 mu´
.c δ1 va` mu´.c δ2 giu˜.a
X va` Y treˆn r, khi do´ neˆ´u X ≈>δ1 Y du´ng treˆn r th`ı X ≈>δ2 Y cu˜ng du´ng treˆn r.
Hay vieˆ´t moˆ. t ca´ch h`ınh thu´
.c: X ≈>δ1 Y ⇒ X ≈>δ2 Y.
Thaˆ.t vaˆ.y, da˘. t e = δ2 − δ1.
Gia’ su.’ X ≈>δ1 Y du´ng treˆn r, tu´
.c la` vo´.i mo. i ca˘.p t1, t2 ∈ r neˆ´u ρ(t1(X), t2(X))  δ1 th`ı
ta cu˜ng co´ ρ(t1(Y ), t2(Y ))  δ1.
Do vaˆ.y vo´
.i mo. i ca˘.p boˆ. t1, t2 ∈ r, neˆ´u ρ(t1(X), t2(X))  δ1+e th`ı ρ(t1(Y ), t2(Y ))  δ1+e.
Tu´.c la` neˆ´u ρ(t1(Y ), t2(Y ))  δ2 th`ı ρ(t1(Y ), t2(Y ))  δ2.
Suy ra X ≈>δ2 Y du´ng treˆn r.
T´ınh chaˆ´t 3. (t´ınh pha’n xa.) Neˆ´u Y ⊆ X khi do´ X ≈>δ Y la` phu. thuoˆ. c ha`m xaˆ´p xı’ loa. i 2
vo´.i mu´.c δ tu`y y´ (0  δ < 1).
Thaˆ.t vaˆ.y, neˆ´u Y ⊆ X th`ı X → Y la` phu. thuoˆ.c ha`m du´ng treˆn r th`ı theo T´ınh chaˆ´t 1 no´
cu˜ng la` phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2 vo´
.i mu´.c δ tu`y y´ (0  δ < 1).
T´ınh chaˆ´t 4. (t´ınh ba˘´c ca`ˆu) Neˆ´u X ≈>δ Y va` Y ≈>δ Z th`ı X ≈>δ Z.
Thaˆ.t vaˆ.y:
Neˆ´uX ≈>δ Y th`ı vo´
.i mo.i boˆ. t1, t2 ∈ r. Neˆ´u ρ(t1(X), t2(X))  δ, ta co´ ρ(t1(Y ), t2(Y ))  δ.
Cu˜ng do Y ≈>δ Z neˆn tu`
. ρ(t1(Y ), t2(Y ))  δ suy ra ρ(t1(Z), t2(Z))  δ, co´ ngh˜ıa la`
X ≈>δ Z. Die`ˆu pha’i chu´
.ng minh.
T´ınh chaˆ´t 5. (t´ınh gia ta˘ng) Vo´.i mo. i X, Y,Z ⊆ R va` mu´
.c δ na`o do´, neˆ´u X ≈>δ Y th`ı
XZ ≈>δ Y Z.
Thaˆ.t vaˆ.y, vo´
.i mo.i ca˘.p boˆ. t1, t2 ∈ r ma` ta co´ ρ(t1(XZ), t2(XZ))  δ th`ı do
ρ(t1(X), t2(X))  ρ(t1(XZ), t2(XZ))
neˆn ta co´
ρ(t1(X), t2(X))  δ.
PHU. THUOˆ. C HA`M XA´ˆP XI
’ VA` PHA`ˆN TU
.’ NGOA. I LAI 83
Ma˘.t kha´c, do X ≈>δ Y neˆn ta co´ ρ(t1(Y ), t2(Y ))  δ, va`
ρ(t1(Z), t2(Z))  ρ(t1(XZ), t2(XZ))  δ,
tu`. do´
ρ(t1(Y Z), t2(Y Z)) = max(ρ(t1(Z), t2(Z)), ρ(t1(Y ), t2(Y )))  δ.
Suy ra die`ˆu pha’i chu´.ng minh. 

3. PHA`ˆN TU
.’ NGOA. I LAI DOˆ´I VO´
.
I PHU. THUOˆ. C HA`M
Trong moˆ.t quan heˆ., phu. thuoˆ.c ha`m moˆ ta’ su
.
. phu. thuoˆ.c du˜
. lieˆ.u ma` trong do´ gia´ tri. cu’a
moˆ.t taˆ.p thuoˆ.c t´ınh na`y xa´c di.nh gia´ tri. cu’a taˆ.p thuoˆ.c t´ınh kia. V´ı du. thu nhaˆ.p cu’a coˆng chu´
.c
trong moˆ.t do
.n vi. do
.n thua`ˆn chı’ phu. thuoˆ.c va`o mu´
.c lu.o.ng va` phu. caˆ´p. Trong ba’ng keˆ ve`ˆ thu
nhaˆ.p, ta co´ phu. thuoˆ.c ha`m pha’n a´nh nho´m thuoˆ.c t´ınh heˆ. soˆ´ lu
.o.ng, heˆ. soˆ´ phu. caˆ´p xa´c di.nh
thu nhaˆ.p cu’a tu`
.ng ngu.`o.i. V`ı vaˆ.y neˆ´u co´ nhu˜
.ng ba’n ghi co´ gia´ tri. heˆ. soˆ´ lu
.o.ng, heˆ. soˆ´ phu.
caˆ´p nhu. nhau nhu.ng gia´ tri. thu nhaˆ.p kha´c nhau th`ı la` moˆ. t hieˆ.n tu
.o.. ng baˆ´t thu
.`o.ng, la`m cho
phu. thuoˆ.c ha`m na`y khoˆng du´ng. Daˆy la` hieˆ.n tu
.o.. ng ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m. Nhu˜
.ng
hieˆ.n tu
.o.. ng na`y thu
.`o.ng xa’y ra trong thu.. c teˆ´ khi caˆ.p nhaˆ. t hoa˘.c sao che´p nhu˜
.ng taˆ.p du˜
. lieˆ.u.
Nguyeˆn nhaˆn co´ theˆ’ do sai so´t hoa˘.c gian laˆ.n. Vieˆ.c pha´t hieˆ.n nhu˜
.ng hieˆ.n tu
.o.. ng no´i treˆn ca`ˆn
thieˆ´t trong vieˆ.c kieˆ’m tra va` la`m sa.ch du˜
. lieˆ.u. Noˆ. i dung du
.´o.i daˆy chu´ng toˆi tr`ınh ba`y kha´i
nieˆ.m va` phu
.o.ng pha´p pha´t hieˆ.n tru
.`o.ng ho.. p ngoa. i lai na`y.
Di.nh ngh˜ıa 3.1. (Pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m) Gia’ su
.’ X → Y la` moˆ.t phu.
thuoˆ.c ha`m du
.o.. c gia’ thieˆ´t du´ng treˆn quan heˆ. r. Khi do´ ca˘.p pha`ˆn tu
.’ (t1, t2) vo´.i t1, t2 ∈ r la`
ca˘.p pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m X → Y neˆ´u t1(X) = t2(X) va` t1(Y ) = t2(Y ).
Trong noˆ. i dung du
.´o.i daˆy chu´ng toˆi su.’ du. ng kha´i nieˆ.m ve`ˆ heˆ. ba`˘ng nhau du
.o.. c tr`ınh ba`y
trong [4].
Gia’ su.’ r = {t1, t2, ..., tm} la` ba’ng du˜. lieˆ.u du
.o.. c gia’ thieˆ´t la` moˆ. t quan heˆ.. K´ı hieˆ.u Er la` heˆ.
ba`˘ng nhau cu’a r du.o.. c xa´c di.nh nhu
. sau:
Er = {Ei,j : 1  i  j  m va` Ei,j = {a ∈ R; ti(a) = tj(a)}}.
Di.nh ly´ 3.1. (Nhaˆ.n bieˆ´t ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m) Cho r la` moˆ. t ba’ng du˜
. lieˆ. u
du.o.. c gia’ thieˆ´t la` moˆ. t quan heˆ. treˆn taˆ. p thuoˆ. c t´ınh R,Er la` heˆ. ba˘`ng nhau cu’a r, X → Y la`
moˆ. t phu. thuoˆ. c ha`m du
.o.. c gia’ thieˆ´t du´ng treˆn r. Ca˘. p pha`ˆn tu
.’ (ti, tj) vo´
.i ti, tj ∈ r la` ngoa. i lai
doˆ´i vo´.i phu. thuoˆ. c ha`m X → Y khi va` chı’ khi Ei,j ∈ Er ma` X ⊆ Ei,j nhu
.ng Y ⊂ Ei,j .
Chu´.ng minh. Thaˆ.t vaˆ.y, gia’ su
.’ (ti, tj) la` ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m X → Y , co´
ngh˜ıa la` ta co´ ti(X) = tj(X) nhu.ng ti(Y ) = tj(Y ). Tu`. di.nh ngh˜ıa Ei,j ta co´ X ⊆ Ei,j va`
Y ⊂ Ei,j .
Ngu.o.. c la. i, neˆ´u co´ Ei,j ∈ Er(Ei,j xa´c di.nh theo ti, tj) ma` X ⊆ Ei,j va` Y ⊂ Ei,j th`ı cu˜ng
theo ca´ch xa´c di.nh Ei,j ta co´ ti(a) = tj(a) vo´
.i a ∈ Ei,j . Do X ⊆ Ei,j neˆn ti(X) = tj(X).
Cu˜ng do Y ⊂ Ei,j neˆn toˆ`n ta. i b ∈ Y ma` ti(b) = tj(b) hay la` ti(Y ) = tj(Y ). Theo Di.nh ngh˜ıa
2.1 th`ı (ti, tj) la` ca˘.p ngoa. i lai. Die`ˆu pha’i chu´
.ng minh. 

Tu`. di.nh ly´ treˆn ta co´ thuaˆ. t toa´n xa´c di.nh ca´c ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m nhu
.
sau.
Thuaˆ.t toa´n 1. (Xa´c di.nh ca´c ca˘.p ngoa. i lai doˆ´i vo´
.i taˆ.p ca´c phu. thuoˆ.c ha`m)
Input: Taˆ.p thuoˆ.c t´ınh R = {a1, a2, ..., an), ba’ng du˜
. lieˆ.u r = {t1, t2, ..., tm} treˆn R
84 VU˜ DU´.C THI, PHA. M HA. THUY’
Taˆ.p ca´c phu. thuoˆ.c ha`m F = {X1 → Y1;X2 → Y2, ...,Xm → Ys}
Output: OUTLI - taˆ.p ca´c ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m
Ba˘´t da`ˆu
Bu.´o.c 1: T´ınh heˆ. ba`˘ng nhau cu’a r:
Er = {Ei,j|1  i < j  m, Ei,j = {a ∈ R; ti(a) = tj(a)}}.
Bu.´o.c 2: Vo´.i moˆ˜i phu. thuoˆ.c ha`m Xi → Yi ∈ F va` mo. i Ek,j ∈ Er, kieˆ’m tra die`ˆu kieˆ.n
Xi ⊆ Ek,j and Yi ⊂ Ek,j. Neˆ´u du´ng, lu
.u ca˘.p (tk, tj) va`o taˆ.p OUTLI. Neˆ´u khoˆng, kieˆ’m tra
tieˆ´p ca´c phu. thuoˆ.c ha`m kha´c.
Keˆ´t thu´c
Taˆ.p OUTLI la` taˆ.p ca´c ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c ha`m cu’a r.
T´ınh du´ng da˘´n cu’a Thuaˆ. t toa´n 1 du
.o.. c suy ra tu`
. Di.nh ly´ 3.1.
4. PHA`ˆN TU
.’ NGOA. I LAI DOˆ´I VO´
.
I KHO´A
Trong moˆ.t quan heˆ., kho´a la` taˆ.p thuoˆ.c t´ınh xa´c di.nh t´ınh duy nhaˆ´t cu’a moˆ˜i ba’n ghi (pha`ˆn
tu.’ ) cu’a quan heˆ.. Do vaˆ.y trong quan heˆ. khoˆng theˆ’ co´ 2 ba’n ghi co´ gia´ tri. tru`ng nhau treˆn
kho´a. Tuy nhieˆn trong thu.. c teˆ´, trong moˆ.t taˆ.p du˜
. lieˆ.u, vieˆ.c co´ nhu˜
.ng ca˘.p ba’n ghi co´ gia´ tri.
tru`ng nhau treˆn kho´a la` co´ theˆ’ xa’y ra (do caˆ.p nhaˆ. t du˜
. lieˆ.u sai, hoa˘.c co´ su
.
. gian laˆ.n coˆ´ t`ınh
nhaˆ.p nhie`ˆu la`ˆn cu`ng moˆ.t ba’n ghi va`o moˆ.t ba’ng du˜
. lieˆ.u). Ca˘.p ba’n ghi na`y go. i la` ngoa. i lai doˆ´i
vo´.i kho´a va` ca`ˆn pha´t hieˆ.n deˆ’ xu
.’ ly´. Noˆ. i dung du
.´o.i daˆy se˜ tr`ınh ba`y kha´i nieˆ.m va` phu
.o.ng
pha´p pha´t hieˆ.n ngoa. i lai doˆ´i vo´
.i tru.`o.ng ho.. p na`y.
Di.nh ngh˜ıa 4.1. (Pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i kho´a) Cho ba’ng du˜. lieˆ.u r du
.o.. c gia’ thieˆ´t la` moˆ. t
quan heˆ. treˆn taˆ.p thuoˆ.c t´ınh R, B du
.o.. c gia’ thieˆ´t la` la` taˆ.p ca´c kho´a toˆ´i tieˆ’u cu’a r. Ca˘.p pha`ˆn
tu.’ (ti, tj) vo´.i ti, tj ∈ r (i = j) la` moˆ. t ca˘.p ngoa. i lai doˆ´i vo´
.i kho´a neˆ´u nhu. vo´.i moˆ. t kho´a na`o
do´ K ∈ B ma` ta co´ ti(K) = tj(K).
Theo qui di.nh, th`ı trong moˆ.t quan heˆ. khoˆng co´ su
.
. tru`ng nhau ve`ˆ gia´ tri. cu’a ca´c ba’n ghi
treˆn kho´a. Do vaˆ.y su
.
. tru`ng nhau ve`ˆ gia´ tri. treˆn kho´a la` hieˆ.n tu
.o.. ng ngoa. i lai ca`ˆn du
.o.. c xu
.’ ly´.
Tru.`o.ng ho.. p neˆ´u ti(K) = tj(K) va` ti(R\K) = tj(R\K) tu´
.c chu´ng tru`ng nhau hoa`n toa`n
ve`ˆ gia´ tri. treˆn ca´c thuoˆ.c t´ınh, co´ ngh˜ıa la` ta co´ ti(R) = tj(R) th`ı ca˘.p (ti, tj) du
.o.. c go. i la` ca˘.p
ngoa. i lai ta`ˆm thu
.`o.ng (theo qui u.´o.c th`ı trong moˆ.t quan heˆ. khoˆng du
.o.. c co´ 2 boˆ. tru`ng nhau
hoa`n toa`n). Co`n neˆ´u ti(K) = tj(K) nhu.ng ti(R\K) = tj(R\K) th`ı ta co´ ca˘.p ngoa. i lai theo
phu. thuoˆ.c ha`m K → R.
Meˆ.nh de`ˆ sau la`m co
. so.’ cho vieˆ.c pha´t hieˆ.n ca´c ca˘.p ngoa. i lai doˆ´i vo´
.i kho´a cu’a quan heˆ..
Meˆ.nh de`ˆ 2.1. (Nhaˆ.n bieˆ´t ca˘.p ngoa. i lai theo kho´a) Cho ba’ng du˜
. lieˆ. u r du
.o.. c gia’ thieˆ´t la` moˆ. t
quan heˆ. treˆn taˆ. p thuoˆ. c t´ınh R, B la` taˆ. p ca´c kho´a toˆ´i tieˆ’u cu’a r, Er la` heˆ. ba˘`ng nhau cu’a r.
Khi do´ neˆ´u ta co´ Ei,j ∈ Er chu´.a moˆ. t kho´a K na`o do´ (tu´
.c la` K ⊆ Ei,j) th`ı ca˘. p pha`ˆn tu
.’ (ti, tj)
vo´.i ti, tj ∈ r (tu.o.ng u´.ng vo´.i Ei,j) la` moˆ. t ca˘. p ngoa. i lai doˆ´i vo´
.i kho´a.
Chu´.ng minh. Theo di.nh ngh˜ıa kho´a cu’a moˆ.t quan heˆ., neˆ´u K la` moˆ.t kho´a th`ı ta co´ K → R.
Gia’ su.’ K ⊆ Ei,j, theo ca´ch xa´c di.nh heˆ. ba`˘ng nhau, ta co´ ti(K) = tj(K). Ma˘. t kha´c do
K → R neˆn ta pha’i co´ ti(R) = tj(R). V`ı vaˆ.y:
- Neˆ´u ti(R) = tj(R) ta co´ moˆ. t ca˘.p ngoa. i lai ta`ˆm thu
.`o.ng (hai ba’n ghi tru`ng nhau hoa`n
toa`n, vi pha.m die`ˆu kieˆ.n r la` moˆ. t quan heˆ.) .
PHU. THUOˆ. C HA`M XA´ˆP XI
’ VA` PHA`ˆN TU
.’ NGOA. I LAI 85
- Neˆ´u ti(K) = tj(K) va` ti(R\K) = tj(R\K) ta se˜ co´ moˆ. t ca˘.p ngoa. i lai doˆ´i vo´
.i phu. thuoˆ.c
ha`m K → R (theo di.nh ngh˜ıa cu’a kho´a). Meˆ.nh de`ˆ du
.o.. c chu´
.ng minh.
Ta co´ thuaˆ. t toa´n sau deˆ’ xa´c di.nh ca´c ca˘.p ngoa. i lai theo kho´a cu’a moˆ.t quan heˆ..
Thuaˆ.t toa´n 2. (Xa´c di.nh pha`ˆn tu
.’ ngoa. i lai doˆ´i vo´
.i kho´a cu’a quan heˆ.)
Input: Ba’ng du˜. lieˆ.u r = {t1, t2, ..., tm} treˆn taˆ.p thuoˆ.c t´ınh R = (a1, a2, ..., an).
B taˆ.p ca´c kho´a cu’a r.
Output: taˆ.p ca´c ca˘.p ngoa. i lai theo kho´a OUTLI2
Ba˘´t da`ˆu
Bu.´o.c 1: T´ınh heˆ. ba`˘ng nhau Er = {Ei,j|1  i < j  m va` Ei,j = {a ∈ R; ti(a) = tj(a)}}.
Bu.´o.c 2: Vo´.i moˆ˜i kho´a K ∈ B va` vo´.i moˆ˜i taˆ.p Ei,j ∈ Er, ta kieˆ’m tra die`ˆu kieˆ.n K ⊆ Ei,j.
Neˆ´u du´ng lu.u ca˘.p (ti, tj) va`o OUTLI2.
Keˆ´t thu´c
Taˆ.p OUTLI2 la` taˆ.p ca´c pha`ˆn tu
.’ ngoa. i lai theo kho´a.
Treˆn daˆy la` moˆ. t soˆ´ keˆ´t qua’ nghieˆn cu´
.u ve`ˆ phu. thuoˆ.c ha`m xaˆ´p xı’ loa. i 2, pha`ˆn tu
.’ ngoa. i
lai doˆ´i vo´.i phu. thuoˆ.c ha`m. Daˆy la` nhu˜
.ng vaˆ´n de`ˆ mo´.i dang du.o.. c chu´ng toˆi nghieˆn cu´
.u. Ca´c
keˆ´t qua’ nghieˆn cu´.u kha´c 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ˆ´ (v´ı du. trong l˜ınh vu
.
. c kieˆ’m toa´n) se˜ du
.o.. c chu´ng toˆi gio´
.i thieˆ.u trong ca´c noˆ. i dung
kha´c.
TA`I LIEˆ. U THAM KHA
’O
[1] 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 (1998) 392—401.
[2] B. Liu, W. Hsu, and Y.Ma, Integrating classification and association mining, Proc. Int.
Conf. Knowledge Discovery and Data Mining (KDD’98), New York (1998) 80—86.
[3] E. Turban, Decision Support and Expert Systems Management Support Systems, Prentice
Hall, 1995.
[4] Vu˜ Du´.c Thi, Co. so.’ du˜. lieˆ. u- kieˆ´n thu´
.c va` thu.. c ha`nh, NXB Thoˆ´ng keˆ, Ha` Noˆ. i, 1997.
Nhaˆ. n ba`i nga`y 3 - 11 - 2005
Nhaˆ. n la. i sau su
.’ a nga`y 1 - 3 -2007