’<br />
Tap ch´ Tin hoc v` Diˆu khiˆ n hoc, T.23, S.1 (2007), 80—85<br />
ı<br />
e<br />
e<br />
.<br />
. a `<br />
.<br />
<br />
’.<br />
´<br />
’ `<br />
ˆ<br />
`<br />
ˆ<br />
ˆ<br />
PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI<br />
A<br />
.<br />
.<br />
.<br />
.<br />
´<br />
ˆ<br />
`<br />
ˆ<br />
´<br />
DOI VO I PHU THUOC HAM<br />
.<br />
.<br />
’<br />
˜ ´.<br />
VU DU C THI1 , PHAM HA THUY2<br />
.<br />
.<br />
1 Viˆn<br />
e<br />
<br />
.<br />
<br />
Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nam<br />
o<br />
e o<br />
e<br />
e e<br />
.<br />
.<br />
. a o<br />
.<br />
.<br />
’m to´n Nh` nu.´.c<br />
o<br />
tˆm Khoa hoc v` BDCB - Kiˆ<br />
a<br />
e<br />
a<br />
a<br />
. a<br />
<br />
2 Trung<br />
<br />
Abstract. The aim of this paper is to present the concepts about Type 2 Approximate Functional<br />
Dependency - AFD 2 (relating to the correlation between atributes of the relational file) and the<br />
outliers with functional dependency. The paper also gives some properties of ADF 2 and algorithms<br />
for finding the outliers with functional dependency.<br />
´<br />
´<br />
´<br />
T´m t˘t. B`i b´o gi´.i thiˆu vˆ phu thuˆc h`m xˆ p xı loai 2 (loai phu thuˆc h`m xˆ p xı liˆn quan<br />
o<br />
a<br />
a a<br />
o<br />
e `<br />
e<br />
o a<br />
a ’ .<br />
o a<br />
a ’ e<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
`<br />
´n su. tu.o.ng quan gi˜.a c´c thuˆc t´ cua mˆt quan hˆ) v` phˆn tu. ngoai lai dˆi v´.i phu thuˆc<br />
´ o<br />
’<br />
’<br />
u a<br />
o ınh<br />
o<br />
e a a<br />
o<br />
dˆ<br />
e<br />
o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
´<br />
´<br />
h`m. B`i b´o c˜ng tr` b`y mˆt sˆ t´ chˆ t cua phu thuˆc h`m xˆ p xı loai 2 v` thuˆt to´n x´c<br />
a<br />
a a u<br />
ınh a<br />
o o ınh a ’<br />
o a<br />
a ’ .<br />
a<br />
a<br />
a a<br />
.<br />
.<br />
.<br />
.<br />
`<br />
´<br />
o a<br />
dinh phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m.<br />
a ’<br />
o o<br />
.<br />
.<br />
.<br />
.<br />
<br />
´.<br />
ˆ<br />
GIO I THIEU<br />
.<br />
´<br />
a<br />
Kh´i niˆm phu thuˆc h`m xˆ p xı (Approximate functional dependency) v` phu.o.ng ph´p<br />
a e<br />
o a<br />
a ’<br />
a<br />
.<br />
.<br />
.<br />
´<br />
´p xı d˜ du.o.c nhiˆu t´c gia dˆ cˆp dˆn v` du.o.c u.ng dung<br />
` a<br />
’ a<br />
’ ` a e a<br />
e .<br />
ph´t hiˆn c´c phu thuˆc h`m xˆ<br />
a<br />
e a<br />
o a<br />
a<br />
e<br />
.<br />
.<br />
.<br />
.<br />
. ´<br />
.<br />
’<br />
˜<br />
`<br />
’<br />
u<br />
o<br />
a<br />
e<br />
e<br />
trong nhiˆu b`i to´n phˆn l´.p cua data mining ([1, 2]). Nh˜.ng phu thuˆc nhu. vˆy biˆ u diˆn<br />
e a a<br />
a o<br />
.<br />
.<br />
.<br />
. phu thuˆc tu. nhiˆn gi˜.a c´c thuˆc t´ trong mˆt quan hˆ nhu.ng c´ ch´.a mˆt v`i h`ng<br />
o .<br />
e<br />
u a<br />
o ınh<br />
o<br />
e<br />
o u<br />
o a a<br />
su<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
’<br />
o<br />
c´ sai s´t ho˘c khˆng thoa luˆt (goi l` phu thuˆc h`m xˆ p xı loai 1). Mˆt tru.`.ng ho.p phu<br />
o<br />
o<br />
a<br />
o<br />
a<br />
a<br />
o a<br />
a ’ .<br />
o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
o<br />
o<br />
o ınh a u u<br />
u<br />
o<br />
o .<br />
thuˆc xˆ p xı kh´c l` c´ nh˜.ng nh´m thuˆc t´ m˘c d` gi˜.a ch´ng khˆng c´ su. phu thuˆc<br />
o a ’ a a o u<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’ a<br />
o<br />
a<br />
a<br />
ıa<br />
o a<br />
o<br />
h`m theo kiˆu b˘ ng nhau tuyˆt dˆi (theo c´ch dinh ngh˜ phu thuˆc h`m thˆng thu.`.ng) m`<br />
a<br />
e `<br />
e o<br />
.<br />
.<br />
.<br />
. ´<br />
. phu thuˆc xˆ p xı theo kiˆu tu.o.ng quan h`m sˆ (tuyˆn t´ ho˘c phi tuyˆn), (goi l` phu<br />
’<br />
´<br />
´<br />
´<br />
c´ su<br />
o .<br />
o a ’<br />
e<br />
a o<br />
e ınh a<br />
e<br />
.<br />
. ´<br />
.<br />
. a<br />
.<br />
´<br />
´<br />
`<br />
o<br />
a ’<br />
a `<br />
e a e<br />
thuˆc h`m xˆ p xı loai 2). Tru.`.ng ho.p n`y xay ra kh´ nhiˆu v` liˆn quan dˆn nhiˆu b`i to´n<br />
o a<br />
a ’ .<br />
e<br />
e a a<br />
.<br />
.<br />
´<br />
’<br />
e<br />
a a<br />
o ’<br />
o<br />
thu.c tˆ. V´ du trong bang quan hˆ ghi lai t` h` mua v`o c´c loai h`ng h´a cua mˆt doanh<br />
. e ı .<br />
.<br />
. ınh ınh<br />
. a<br />
.<br />
’<br />
´<br />
´<br />
o<br />
a<br />
a a<br />
ı e<br />
a<br />
o a<br />
nghiˆp ta thˆ y quan hˆ gi˜.a khˆi lu.o.ng h`ng mua v`o v` chi ph´ dˆ mua l` phu thuˆc h`m<br />
e<br />
a<br />
e u<br />
.<br />
.<br />
.<br />
.<br />
.<br />
. chˆnh lˆch gi˜.a khˆi lu.o.ng h`ng mua v`o nho ho.n mˆt m´.c n`o d´<br />
´<br />
´<br />
´<br />
’<br />
o<br />
o<br />
u a o<br />
e<br />
u<br />
a<br />
a<br />
xˆ p xı loai 2. Nˆu su e<br />
a ’ .<br />
e .<br />
.<br />
.<br />
.<br />
’<br />
’<br />
’<br />
e<br />
ı<br />
u<br />
a . ’<br />
th` c˜ng k´o theo su. chˆnh lˆch cua chi ph´ hai do.t mua c˜ng nho (gi´ tri cua hai ban ghi tai<br />
ı u<br />
e<br />
. e<br />
.<br />
.<br />
.<br />
.o.c ph´p c´ su. chˆnh lˆch tu.o.ng u.ng). C˜ ng vˆy dˆi v´.i chı tiˆu doanh<br />
´<br />
’ e<br />
c´c thuˆc t´ n`y du .<br />
a<br />
o ınh a<br />
e o . e<br />
e<br />
´<br />
u<br />
a o o<br />
.<br />
.<br />
.<br />
’<br />
’ a<br />
thu v` chi ph´ trong bang kˆ vˆ tinh h` kinh doanh... Viˆc khao s´t loai phu thuˆc h`m<br />
a<br />
ı<br />
e `<br />
e<br />
ınh<br />
e<br />
o a<br />
.<br />
.<br />
.<br />
.<br />
˜<br />
´<br />
´<br />
e<br />
e<br />
a<br />
e<br />
u<br />
e<br />
a<br />
o<br />
xˆ p xı n`y c´ u.ng dung thu.c tiˆn trong viˆc ph´t hiˆn nh˜.ng hiˆn tu.o.ng bˆ t thu.`.ng (ngoai<br />
a ’ a o´<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’<br />
´<br />
´<br />
’ y<br />
’<br />
e<br />
a a<br />
e<br />
e<br />
lai) trong san xuˆ t kinh doanh, phuc vu cho hoat dˆng kiˆm to´n v` quan l´ kinh tˆ. Viˆc<br />
a<br />
.<br />
.<br />
.<br />
.<br />
. o<br />
´<br />
´<br />
e<br />
e<br />
e<br />
a u o a e<br />
a<br />
o<br />
o<br />
u<br />
quyˆt dinh m´.c chˆnh lˆch cho ph´p (vu.o.t qu´ m´.c d´ l` hiˆn tu.o.ng bˆ t thu.`.ng) thu.`.ng<br />
e .<br />
.<br />
.<br />
.<br />
.<br />
.o.c x´c dinh theo hu.´.ng hˆ tro. quyˆt dinh ([3]) c´ ngh˜ l` c`n t`y thuˆc thˆm c´c yˆu tˆ<br />
˜ .<br />
´<br />
´ ´<br />
o<br />
o<br />
e .<br />
du . a .<br />
o<br />
ıa a o u<br />
o<br />
e<br />
a e o<br />
.<br />
` e `<br />
´<br />
’ a<br />
vˆ yˆu cˆu v` kinh nghiˆm cua c´c chuyˆn gia trong c´c l˜ vu.c thu.c tˆ.<br />
e<br />
a a<br />
e<br />
e<br />
a ınh .<br />
e<br />
.<br />
.<br />
<br />
´<br />
’ `<br />
’.<br />
ˆ<br />
`<br />
ˆ<br />
ˆ<br />
PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI<br />
A<br />
.<br />
.<br />
.<br />
<br />
81<br />
<br />
´<br />
´<br />
’<br />
o a a a e<br />
Du.´.i dˆy l` kh´i niˆm cua phu thuˆc h`m xˆ p xı loai 2 v` khao s´t mˆt sˆ t´ chˆ t cua<br />
o a<br />
a ’ .<br />
a ’ a o o ınh a ’<br />
.<br />
.<br />
.<br />
. ´<br />
.i, mˆt sˆ kh´i niˆm, dinh ngh˜ vˆ phˆn tu. ngoai lai theo phu thuˆc h`m v`<br />
`<br />
o o a e<br />
o a<br />
a<br />
o<br />
o<br />
ıa ` `<br />
e a ’<br />
n´. Dˆ ng th`<br />
o<br />
. ´<br />
.<br />
.<br />
.<br />
.<br />
.<br />
` l`m co. so. cho viˆc xˆy du.ng thuˆt to´n x´c dinh phˆn tu. ngoai lai dˆi v´.i phu<br />
`<br />
´ o<br />
’<br />
e a<br />
a<br />
a a .<br />
e<br />
a ’<br />
o<br />
c´c mˆnh dˆ a<br />
a<br />
e<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
ınh a<br />
thuˆc h`m c˜ ng du.o.c tr` b`y.<br />
o a<br />
u<br />
.<br />
.<br />
´<br />
’<br />
´<br />
ˆ<br />
ˆ<br />
`<br />
ˆ<br />
1. KHAI NIEM PHU THUOC HAM XAP XI LOAI 2<br />
.<br />
.<br />
.<br />
.<br />
Cho r l` mˆt quan hˆ trˆn tˆp thuˆc t´ R = {a1 , a2 , ..., an } trong d´ c´c thuˆc t´<br />
a o<br />
e e a<br />
o ınh<br />
o a<br />
o ınh<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’ l` c´c thuˆc t´ dinh danh(categorical), r`.i rac ho˘c liˆn tuc (tru.`.ng sˆ).<br />
´<br />
a e .<br />
o<br />
o<br />
a1 , a2 , ..., an c´ thˆ a a<br />
o e<br />
o ınh .<br />
o .<br />
.<br />
.<br />
.i nh˜.ng thuˆc t´ dinh danh, ta tiˆn h`nh thu.c hiˆn ´nh xa tˆ t ca c´c gi´ tri c´ thˆ<br />
’<br />
´<br />
´<br />
´<br />
Dˆi v´<br />
o o<br />
e a<br />
u<br />
o ınh .<br />
e a<br />
a . o e<br />
.<br />
.<br />
.<br />
. a ’ a<br />
.i mˆt tˆp c´c sˆ nguyˆn du.o.ng liˆn kˆ.<br />
´<br />
` `<br />
e<br />
e e<br />
t´ o a a o<br />
o<br />
. .<br />
.a 2 bˆ gi´ tri trˆn tˆp thuˆc t´<br />
’<br />
o a . e a<br />
o ınh).<br />
Dinh ngh˜ 1.1. (khoang c´ch gi˜<br />
ıa<br />
a<br />
u<br />
.<br />
.<br />
.<br />
.<br />
.i 2 bˆ t1 , t2 ∈ r , ta k´ hiˆu ρ(t1 (X), t2 (X)) l` khoang c´ch gi˜.a t1 v` t2 trˆn tˆp thuˆc<br />
’<br />
o<br />
ı e<br />
a<br />
a<br />
u<br />
a<br />
e a<br />
o<br />
V´<br />
o<br />
.<br />
.<br />
.<br />
.<br />
a .<br />
t´ X ⊆ R, du.o.c x´c dinh nhu. sau:<br />
ınh<br />
.<br />
(|t1 (ai ) − t2 (ai )|<br />
, ai ∈ X,<br />
ρ(t1 (X), t2 (X)) = max<br />
max(|t1 (ai )|, |t2 (ai )|)<br />
´<br />
´<br />
´<br />
a<br />
o<br />
h`m max(x, y) l` h`m chon ra sˆ l´.n nhˆ t trong 2 sˆ x, y .<br />
a<br />
a a<br />
o o<br />
.<br />
.`.ng ho.p max(|t1 (ai )|, |t2 (ai )|) = 0, ta qui u.´.c:<br />
o<br />
Tru o<br />
.<br />
|t1 (ai ) − t2 (ai )|/ max(|t1 (ai )|, |t2 (ai )|) = 0.<br />
’<br />
´<br />
´ ´<br />
’<br />
o a . e a<br />
o ınh o e<br />
a a<br />
o ’ a o o a<br />
Khoang c´ch gi˜.a 2 bˆ gi´ tri trˆn tˆp thuˆc t´ c´ thˆ coi l` h`m sˆ cua c´c dˆi sˆ v`<br />
a<br />
u<br />
.<br />
.<br />
.<br />
’ a quan hˆ v` tˆp c´c thuˆc t´<br />
l` c´c bˆ gi´ tri cu<br />
a a o a .<br />
e a a a<br />
o ınh.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
’<br />
Mˆt sˆ t´nh chˆ t cua h`m khoa ng c´ch ρ(t1 (X), t2 (X))<br />
o o ı<br />
a ’ a<br />
a<br />
. ´<br />
.ng minh dinh ngh˜ khoang c´ch ρ(t1 (X), t2 (X)) thoa m˜n c´c t´ chˆt cua<br />
˜ a<br />
´<br />
’<br />
’<br />
Dˆ d`ng ch´<br />
e<br />
u<br />
ıa<br />
a<br />
a a ınh a ’<br />
.<br />
’<br />
o<br />
h`m khoang c´ch ∀t1 , t2 , t3 ∈ r, ∀X, Y ⊆ R, ta c´:<br />
a<br />
a<br />
ρ(t1 (X), t2 (X)) 0<br />
a1)<br />
a2)<br />
ρ(t1 (X), t2 (X)) = 0 ↔ t1 (X) = t2 (X)<br />
a3)<br />
ρ(t1 (X), t2 (X)) ρ(t1 (X), t3 (X)) + ρ(t3 (X), t2 (X))<br />
˜ u<br />
´<br />
a ınh a<br />
V` ngo`i ra c˜ng dˆ ch´.ng minh c´c t´ chˆ t sau:<br />
a<br />
a<br />
u<br />
e<br />
´u X ⊆ Y th` ρ(t1 (X), t2 (X)) ρ(t1 (Y ), t2 (Y ))<br />
ı<br />
a4)<br />
Nˆ<br />
e<br />
a5)<br />
ρ(t1 (XY ), t2 (XY )) = max(ρ(t1 (X), t2 (X)), ρ(t1 (Y ), t2 (Y )))<br />
´<br />
Dinh ngh˜ 1.2. (phu thuˆc h`m xˆ p xı loai 2 - Type 2 Approcimate Functional Depenıa<br />
o a<br />
a ’ .<br />
.<br />
.<br />
.<br />
’ ’<br />
a o o o<br />
o `<br />
a<br />
a .<br />
a<br />
o<br />
dency). Gia su. X, Y ⊆ R v` v´.i mˆt sˆ δ cho tru.´.c, 0 δ < 1, ta n´i r˘ ng X x´c dinh h`m<br />
. ´<br />
.c δ (ho˘c gi˜.a X, Y c´ phu thuˆc h`m xˆ p xı loai 2 m´.c δ ), k´ hiˆu l` X ≈ Y nˆu<br />
´<br />
´<br />
Y m´<br />
u<br />
a<br />
u<br />
o<br />
o a<br />
a ’ .<br />
u<br />
y e a<br />
>δ<br />
e<br />
.<br />
.<br />
.<br />
.<br />
.i moi c˘p bˆ t , t ∈ r , m` ρ(t (X), t (X)) δ th` ta c˜ng c´ ρ(t (Y ), t (Y )) δ.<br />
a<br />
ı<br />
u<br />
o<br />
v´<br />
o<br />
1<br />
2<br />
1<br />
2<br />
. a o 1 2<br />
.<br />
.<br />
V´ du 1. X´t bang quan hˆ sau:<br />
ı .<br />
e ’<br />
e<br />
.<br />
A<br />
2.5<br />
2.51<br />
3.6<br />
3.65<br />
4.25<br />
4.26<br />
<br />
B<br />
18<br />
18<br />
20<br />
20<br />
25<br />
25<br />
<br />
C<br />
160<br />
160.5<br />
320<br />
323<br />
641<br />
643<br />
<br />
D<br />
25<br />
15<br />
30<br />
45<br />
60<br />
70<br />
<br />
E<br />
12<br />
13<br />
16<br />
28<br />
19<br />
57<br />
<br />
’<br />
˜ ´.<br />
VU DU C THI, PHAM HA THUY<br />
.<br />
.<br />
<br />
82<br />
<br />
’<br />
´<br />
´<br />
`<br />
o o<br />
o o<br />
o<br />
Ta thˆ y gi˜.a c´c cˆt A, B c´ mˆi tu.o.ng quan v´.i cˆt C. V´.i δ = 0.05 ta kiˆm tra diˆu<br />
a<br />
u a o<br />
e<br />
e<br />
.<br />
.<br />
´<br />
kiˆn phu thuˆc h`m xˆ p xı loai 2: AB →0.05 C.<br />
e<br />
o a<br />
a ’ .<br />
.<br />
.<br />
.<br />
o<br />
V´.i c˘p h`ng 1, 2, ta c´<br />
o a a<br />
.<br />
ρ(t1 (AB),t2 (AB))<br />
= max(|t1 (A) − t2 (A)|/ max(|t1 (A)|, |t2 (A)|), |t1 (B) − t2 (B)|/ max(|t1 (B)|, |t2 (B)|)<br />
= 0.00394 < 0.05.<br />
Ta c˜ ng t´ du.o.c: ρ(t1 (C), t2 (C)) = 0.00311 < 0.05.<br />
u<br />
ınh<br />
.<br />
.o.ng tu. ta c˜ng s˜ kiˆm tra dˆ d`ng v´.i c˘p h`ng 3, 4 v` c˘p h`ng 5, 6 c˜ ng nhu. c´c<br />
’<br />
˜ a<br />
Tu<br />
u<br />
e e<br />
e<br />
o a a<br />
a a a<br />
u<br />
a<br />
.<br />
.<br />
.<br />
c˘p h`ng kh´c.<br />
a a<br />
a<br />
.<br />
><br />
a .<br />
a<br />
u<br />
Vˆy ta c´: AB ≈ 0.05 C (AB x´c dinh h`m C m´.c 0.05).<br />
a<br />
o<br />
.<br />
<br />
´<br />
´<br />
’<br />
´<br />
’<br />
ˆ<br />
ˆ INH CHAT CUA PHU THUOC HAM XAP XI LOAI 2<br />
ˆ<br />
ˆ<br />
`<br />
ˆ<br />
2. MOT SO T´<br />
.<br />
.<br />
.<br />
.<br />
´<br />
T´ chˆt 1. Cho r l` mˆt quan hˆ trˆn tˆp thuˆc t´nh R. Mˆt phu thuˆc h`m d´ng trˆn r<br />
ınh a<br />
a o<br />
e e a<br />
o ı<br />
o<br />
o a<br />
u<br />
e<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
u<br />
u y<br />
u<br />
e<br />
c˜ng l` phu thuˆc h`m xˆ p xı loai 2 v´.i m´.c δ t`y ´ (0 δ < 1) d´ng trˆn r.<br />
u<br />
a .<br />
o a<br />
a ’ .<br />
o<br />
.<br />
´t n`y dˆ d`ng suy theo Dinh ngh˜a 1.2.<br />
T´ chˆ a ˜ a<br />
ınh a<br />
e<br />
ı<br />
.<br />
´<br />
´<br />
a o<br />
e e<br />
a<br />
o<br />
T´ chˆt 2. Cho r l` mˆt quan hˆ trˆn R; X, Y ⊆ R; δ1 , δ2 l` hai sˆ sao cho 0 δ1 < δ2 < 1.<br />
ınh a<br />
.<br />
.<br />
´<br />
K´ hiˆu X ≈ δ1 Y v` X ≈ δ2 Y l` hai phu thuˆc h`m xˆ p xı loai 2 m´.c δ1 v` m´.c δ2 gi˜.a<br />
ı e<br />
><br />
a<br />
><br />
a<br />
o a<br />
a ’ .<br />
u<br />
a u<br />
u<br />
.<br />
.<br />
.<br />
´<br />
X v` Y trˆn r , khi d´ nˆu X ≈ δ1 Y d´ng trˆn r th` X ≈ δ2 Y c˜ng d´ng trˆn r.<br />
a<br />
e<br />
o e<br />
><br />
u<br />
e<br />
ı<br />
><br />
u<br />
u<br />
e<br />
´ o a<br />
Hay viˆt mˆt c´ch h` th´.c: X ≈ δ1 Y ⇒ X ≈ δ2 Y.<br />
e<br />
ınh u<br />
><br />
><br />
.<br />
Thˆt vˆy, d˘t e = δ2 − δ1 .<br />
a a<br />
a<br />
. .<br />
.<br />
´<br />
’ ’<br />
Gia su. X ≈ δ1 Y d´ng trˆn r , t´.c l` v´.i moi c˘p t1 , t2 ∈ r nˆu ρ(t1 (X), t2 (X)) δ1 th`<br />
><br />
u<br />
e<br />
u a o<br />
e<br />
ı<br />
. a<br />
.<br />
ta c˜ng c´ ρ(t1 (Y ), t2 (Y )) δ1 .<br />
u<br />
o<br />
´<br />
Do vˆy v´.i moi c˘p bˆ t1 , t2 ∈ r , nˆu ρ(t1 (X), t2 (X)) δ1 + e th` ρ(t1 (Y ), t2 (Y )) δ1 + e.<br />
a o<br />
e<br />
ı<br />
. a o<br />
.<br />
.<br />
.<br />
.c l` nˆu ρ(t1 (Y ), t2 (Y )) δ2 th` ρ(t1 (Y ), t2 (Y )) δ2 .<br />
´<br />
T´ a e<br />
u<br />
ı<br />
Suy ra X ≈ δ2 Y d´ng trˆn r.<br />
><br />
u<br />
e<br />
´<br />
´<br />
´<br />
’<br />
T´<br />
ınh chˆt 3. (t´ phan xa) Nˆu Y ⊆ X khi d´ X ≈ δ Y l` phu thuˆc h`m xˆp xı loai 2<br />
a<br />
ınh<br />
e<br />
o<br />
><br />
a .<br />
o a<br />
a ’ .<br />
.<br />
.<br />
u<br />
u y<br />
v´.i m´.c δ t`y ´ (0 δ < 1).<br />
o<br />
´<br />
´<br />
Thˆt vˆy, nˆu Y ⊆ X th` X → Y l` phu thuˆc h`m d´ng trˆn r th` theo T´ chˆ t 1 n´<br />
a a<br />
e<br />
ı<br />
a<br />
o a<br />
u<br />
e<br />
ı<br />
ınh a<br />
o<br />
. .<br />
.<br />
.<br />
´p xı loai 2 v´.i m´.c δ t` y y (0 δ < 1).<br />
’ .<br />
u ´<br />
c˜ng l` phu thuˆc h`m xˆ<br />
u<br />
a<br />
o a<br />
a<br />
o u<br />
.<br />
.<br />
´ a<br />
´<br />
´<br />
T´ chˆt 4. (t´ b˘ c cˆu) Nˆu X ≈ δ Y v` Y ≈ δ Z th` X ≈ δ Z.<br />
ınh a<br />
ınh a `<br />
e<br />
><br />
a<br />
><br />
ı<br />
><br />
Thˆt vˆy:<br />
a a<br />
. .<br />
´<br />
´<br />
><br />
ı o<br />
e<br />
o<br />
Nˆu X ≈ δ Y th` v´.i moi bˆ t1 , t2 ∈ r. Nˆu ρ(t1 (X), t2 (X)) δ , ta c´ ρ(t1 (Y ), t2 (Y )) δ.<br />
e<br />
. o<br />
.<br />
. ρ(t (Y ), t (Y ))<br />
><br />
e u<br />
δ suy ra ρ(t1 (Z), t2 (Z))<br />
δ, c´ ngh˜ l`<br />
o<br />
ıa a<br />
C˜ng do Y ≈ δ Z nˆn t`<br />
u<br />
1<br />
2<br />
`<br />
’<br />
X ≈ δ Z. Diˆu phai ch´.ng minh.<br />
><br />
e<br />
u<br />
´<br />
´<br />
T´<br />
ınh chˆt 5. (t´ gia t˘ng) V´.i moi X, Y, Z ⊆ R v` m´.c δ n`o d´, nˆu X ≈ δ Y th`<br />
a<br />
ınh<br />
a<br />
o<br />
a u<br />
a o e<br />
><br />
ı<br />
.<br />
XZ ≈ δ Y Z .<br />
><br />
Thˆt vˆy, v´.i moi c˘p bˆ t1 , t2 ∈ r m` ta c´ ρ(t1 (XZ), t2 (XZ)) δ th` do<br />
a a<br />
o<br />
a<br />
o<br />
ı<br />
. .<br />
. a o<br />
.<br />
.<br />
ρ(t1 (X), t2 (X)) ρ(t1 (XZ), t2 (XZ))<br />
nˆn ta c´<br />
e<br />
o<br />
ρ(t1 (X), t2 (X))<br />
<br />
δ.<br />
<br />
´<br />
’ `<br />
’.<br />
ˆ<br />
`<br />
ˆ<br />
ˆ<br />
PHU THUOC HAM XAP XI VA PH` N TU NGOAI LAI<br />
A<br />
.<br />
.<br />
.<br />
<br />
M˘t kh´c, do X ≈ δ Y nˆn ta c´ ρ(t1 (Y ), t2 (Y )) δ , v`<br />
a<br />
a<br />
><br />
e<br />
o<br />
a<br />
.<br />
ρ(t1 (Z), t2 (Z)) ρ(t1 (XZ), t2 (XZ)) δ,<br />
t`. d´<br />
u o<br />
ρ(t1 (Y Z), t2 (Y Z)) = max(ρ(t1 (Z), t2 (Z)), ρ(t1 (Y ), t2 (Y )))<br />
`<br />
’<br />
Suy ra diˆu phai ch´.ng minh.<br />
e<br />
u<br />
<br />
83<br />
<br />
δ.<br />
<br />
’.<br />
´<br />
ˆ<br />
`<br />
ˆ<br />
ˆ<br />
´.<br />
3. PH` N TU NGOAI LAI DOI VO I PHU THUOC HAM<br />
A<br />
.<br />
.<br />
.<br />
o a . ’<br />
Trong mˆt quan hˆ, phu thuˆc h`m mˆ ta su. phu thuˆc d˜. liˆu m` trong d´ gi´ tri cua<br />
o<br />
e<br />
o a<br />
o ’ .<br />
o u e<br />
a<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
mˆt tˆp thuˆc t´ n`y x´c dinh gi´ tri cua tˆp thuˆc t´nh kia. V´ du thu nhˆp cua cˆng ch´.c<br />
o a<br />
o ınh a a .<br />
a . ’ a<br />
o ı<br />
ı .<br />
a ’ o<br />
u<br />
. .<br />
.<br />
.<br />
.<br />
.<br />
`<br />
´<br />
’<br />
’<br />
a<br />
o a<br />
u<br />
a<br />
a<br />
e `<br />
e<br />
trong mˆt do.n vi do.n thuˆn chı phu thuˆc v`o m´.c lu.o.ng v` phu cˆ p. Trong bang kˆ vˆ thu<br />
o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
´<br />
’ a<br />
e o<br />
nhˆp, ta c´ phu thuˆc h`m phan ´nh nh´m thuˆc t´ hˆ sˆ lu.o.ng, hˆ sˆ phu cˆ p x´c dinh<br />
a<br />
o<br />
o a<br />
o<br />
o ınh e o<br />
. ´ . a a .<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
´<br />
’<br />
’ u<br />
o<br />
ı a e o u<br />
o a . e o<br />
e o<br />
thu nhˆp cua t`.ng ngu.`.i. V` vˆy nˆu c´ nh˜.ng ban ghi c´ gi´ tri hˆ sˆ lu.o.ng, hˆ sˆ phu<br />
a<br />
.<br />
.<br />
. ´<br />
.<br />
.<br />
. nhau nhu.ng gi´ tri thu nhˆp kh´c nhau th` l` mˆt hiˆn tu.o.ng bˆ t thu.`.ng, l`m cho<br />
´<br />
´<br />
a .<br />
a<br />
a<br />
ı a o<br />
e<br />
a<br />
o<br />
a<br />
cˆ p nhu<br />
a<br />
.<br />
.<br />
.<br />
.<br />
´<br />
u<br />
a a e<br />
o o<br />
phu thuˆc h`m n`y khˆng d´ ng. Dˆy l` hiˆn tu.o.ng ngoai lai dˆi v´.i phu thuˆc h`m. Nh˜.ng<br />
o a<br />
a<br />
o<br />
o a<br />
u<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
’<br />
a<br />
e<br />
a<br />
a<br />
a<br />
e<br />
u<br />
o<br />
a u e<br />
hiˆn tu.o.ng n`y thu.`.ng xay ra trong thu.c tˆ khi cˆp nhˆt ho˘c sao ch´p nh˜.ng tˆp d˜. liˆu.<br />
e<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’<br />
o e `<br />
a<br />
e<br />
Nguyˆn nhˆn c´ thˆ do sai s´t ho˘c gian lˆn. Viˆc ph´t hiˆn nh˜.ng hiˆn tu.o.ng n´i trˆn cˆn<br />
e<br />
a o e<br />
o<br />
a<br />
a<br />
e<br />
a<br />
e<br />
u<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’<br />
´<br />
o<br />
o a<br />
u<br />
o ınh a<br />
a<br />
thiˆt trong viˆc kiˆm tra v` l`m sach d˜. liˆu. Nˆi dung du.´.i dˆy ch´ng tˆi tr` b`y kh´i<br />
e<br />
e<br />
e<br />
a a<br />
u e<br />
.<br />
.<br />
.<br />
.<br />
.o.ng ph´p ph´t hiˆn tru.`.ng ho.p ngoai lai n`y.<br />
a<br />
a<br />
e<br />
o<br />
a<br />
niˆm v` phu<br />
e<br />
a<br />
.<br />
.<br />
.<br />
.<br />
`<br />
´<br />
’ ’<br />
o a<br />
Dinh ngh˜ 3.1. (Phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m) Gia su. X → Y l` mˆt phu<br />
ıa<br />
a ’<br />
o o<br />
a o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.o.c gia thiˆt d´ng trˆn quan hˆ r . Khi d´ c˘p phˆn tu. (t1 , t2 ) v´.i t1 , t2 ∈ r l`<br />
`<br />
´<br />
’<br />
e<br />
e<br />
o a<br />
a ’<br />
o<br />
a<br />
thuˆc h`m du .<br />
o a<br />
e u<br />
.<br />
.<br />
.<br />
`<br />
´<br />
´<br />
c˘p phˆn tu. ngoai lai dˆi v´.i phu thuˆc h`m X → Y nˆu t1 (X) = t2 (X) v` t1 (Y ) = t2 (Y ).<br />
a<br />
a ’<br />
o a<br />
o o<br />
e<br />
a<br />
.<br />
.<br />
.<br />
.<br />
` e `<br />
o a<br />
a e<br />
e . a<br />
ınh a<br />
Trong nˆi dung du.´.i dˆy ch´ng tˆi su. dung kh´i niˆm vˆ hˆ b˘ ng nhau du.o.c tr` b`y<br />
o<br />
u<br />
o ’ .<br />
.<br />
.<br />
.<br />
trong [4].<br />
´<br />
’<br />
’ ’<br />
e a o<br />
e ı e<br />
a ’<br />
u e<br />
a e<br />
Gia su. r = {t1 , t2 , ..., tm } l` bang d˜. liˆu du.o.c gia thiˆt l` mˆt quan hˆ. K´ hiˆu Er l` hˆ<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
` ng nhau cua r du.o.c x´c dinh nhu. sau:<br />
’<br />
b˘<br />
a<br />
. a .<br />
Er = {Ei,j : 1<br />
<br />
i<br />
<br />
j<br />
<br />
m v` Ei,j = {a ∈ R; ti (a) = tj (a)}}.<br />
a<br />
<br />
´ .<br />
´<br />
o a<br />
Dinh l´ 3.1. (Nhˆn biˆt c˘p ngoai lai dˆi v´.i phu thuˆc h`m) Cho r l` mˆt ba ng d˜. liˆu<br />
y<br />
a<br />
e a<br />
o o<br />
a o ’<br />
u e<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.o.c gia thiˆt l` mˆt quan hˆ trˆn tˆp thuˆc t´nh R, Er l` hˆ b˘ ng nhau cua r, X → Y l`<br />
`<br />
´<br />
’<br />
’<br />
e a o<br />
e e a<br />
o ı<br />
du .<br />
a e a<br />
a<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.o.c gia thiˆt d´ng trˆn r . C˘p phˆn tu. (t , t ) v´.i t , t ∈ r l` ngoai lai<br />
´<br />
`<br />
’<br />
e u<br />
e<br />
a<br />
a ’ i j o i j<br />
a<br />
mˆt phu thuˆc h`m du .<br />
o<br />
o a<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´<br />
o a<br />
dˆi v´.i phu thuˆc h`m X → Y khi v` chı khi Ei,j ∈ Er m` X ⊆ Ei,j nhu.ng Y ⊂ Ei,j .<br />
o o<br />
a ’<br />
a<br />
.<br />
.<br />
.ng minh. Thˆt vˆy, gia su. (ti , tj ) l` c˘p ngoai lai dˆi v´.i phu thuˆc h`m X → Y , c´<br />
´<br />
’ ’<br />
a a<br />
o a<br />
Ch´<br />
u<br />
a a<br />
o o<br />
o<br />
. .<br />
.<br />
.<br />
.<br />
.<br />
.ng ti (Y ) = tj (Y ). T`. dinh ngh˜ Ei,j ta c´ X ⊆ Ei,j v`<br />
u .<br />
ıa<br />
o<br />
a<br />
ngh˜ l` ta c´ ti (X) = tj (X) nhu<br />
ıa a<br />
o<br />
Y ⊂ Ei,j .<br />
´<br />
e o<br />
Ngu.o.c lai, nˆu c´ Ei,j ∈ Er (Ei,j x´c dinh theo ti , tj ) m` X ⊆ Ei,j v` Y ⊂ Ei,j th` c˜ng<br />
a .<br />
a<br />
a<br />
ı u<br />
. .<br />
.i a ∈ Ei,j . Do X ⊆ Ei,j nˆn ti (X) = tj (X).<br />
o<br />
o<br />
e<br />
theo c´ch x´c dinh Ei,j ta c´ ti (a) = tj (a) v´<br />
a<br />
a .<br />
`<br />
C˜ng do Y ⊂ Ei,j nˆn tˆ n tai b ∈ Y m` ti (b) = tj (b) hay l` ti (Y ) = tj (Y ). Theo Dinh ngh˜<br />
u<br />
e o .<br />
a<br />
a<br />
ıa<br />
.<br />
.ng minh.<br />
`<br />
’<br />
a a<br />
e<br />
u<br />
2.1 th` (ti , tj ) l` c˘p ngoai lai. Diˆu phai ch´<br />
ı<br />
.<br />
.<br />
´<br />
o a<br />
T`. dinh l´ trˆn ta c´ thuˆt to´n x´c dinh c´c c˘p ngoai lai dˆi v´.i phu thuˆc h`m nhu.<br />
u .<br />
y e<br />
o<br />
a<br />
a a .<br />
a a<br />
o o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
sau.<br />
´<br />
o a<br />
a a<br />
o o a a<br />
Thuˆt to´n 1. (X´c dinh c´c c˘p ngoai lai dˆi v´.i tˆp c´c phu thuˆc h`m)<br />
a<br />
a<br />
a .<br />
.<br />
.<br />
.<br />
.<br />
.<br />
.<br />
’<br />
u e<br />
e<br />
Input: Tˆp thuˆc t´ R = {a1 , a2 , ..., an ), bang d˜. liˆu r = {t1 , t2 , ..., tm } trˆn R<br />
a<br />
o ınh<br />
.<br />
.<br />
.<br />
<br />
’<br />
˜ ´.<br />
VU DU C THI, PHAM HA THUY<br />
.<br />
.<br />
<br />
84<br />
<br />
Tˆp c´c phu thuˆc h`m F = {X1 → Y1 ; X2 → Y2 , ..., Xm → Ys }<br />
a a<br />
o a<br />
.<br />
.<br />
.<br />
´<br />
o a<br />
Output: OUTLI - tˆp c´c c˘p ngoai lai dˆi v´.i phu thuˆc h`m<br />
a a a<br />
o o<br />
.<br />
.<br />
.<br />
.<br />
.<br />
´ a<br />
B˘t dˆu<br />
a `<br />
’<br />
o<br />
ı<br />
e `<br />
Bu.´.c 1: T´nh hˆ b˘ ng nhau cua r:<br />
. a<br />
Er = {Ei,j |1<br />
<br />
i