I HÅC THI NGUYN
TR×ÍNG I HÅC KHOA HÅC
HONG THÀ KHUYN
LÞ THUYT TP MÍ
V
ÙNG DÖNG TRONG PH
N LÎP DÚ LIU
LUN VN THC S TON HÅC
th¡i nguy¶n - N«m 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
I HÅC THI NGUYN
TR×ÍNG I HÅC KHOA HÅC
HONG THÀ KHUYN
LÞ THUYT TP MÍ
V
ÙNG DÖNG TRONG PH
N LÎP DÚ LIU
Chuy¶n ng nh: TON ÙNG DÖNG
M¢ sè : 60.46.36
LUN VN THC S TON HÅC
NG×ÍI H×ÎNG DN KHOA HÅC
TS. VÔ MNH XU
N
th¡i nguy¶n - N«m 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i
Möc löc
Mð ¦u
1
1 Tªp mí v quan h» mí
3
1.1 Tªp mí . . . . . . . . . . . . . . .
1.2 C¡c ph²p to¡n tr¶n tªp mí . . . .
1.2.1 Giao cõa hai tªp mí . . . .
1.2.2 Hñp cõa hai tªp mí . . . .
1.2.3 Ph¦n bò cõa mët tªp mí .
1.2.4 T½ch · c¡c cõa hai tªp mí
1.3 Quan h» mí . . . . . . . . . . . .
1.3.1 Kh¡i ni»m quan h» mí . .
1.3.2 Hñp th nh c¡c quan h» mí
1.3.3 C¡c t½nh ch§t . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2 Ph¥n lîp dú li»u düa tr¶n quan h» mí
2.1
2.2
2.3
2.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B i to¡n ph¥n lîp . . . . . . . . . . . . . . .
Ph¥n lîp nhí quan h» t÷ìng ÷ìng kinh iºn
Ph¥n lîp dú li»u sû döng lþ thuy¸t tªp mí .
Mët sè b i to¡n . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
K¸t luªn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
8
8
10
11
12
14
14
16
17
21
21
22
23
29
37
http://www.lrc-tnu.edu.vn
ii
T i li»u tham kh£o
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
http://www.lrc-tnu.edu.vn
1
Mð ¦u
Trong nhúng n«m g¦n ¥y, ph¡t hi»n tri thùc tø cì sð dú li»u ¢ trð
th nh mët trong nhúng h÷îng nghi¶n cùu lîn nh§t cõa l¾nh vüc khoa håc
m¡y t½nh v cæng ngh» tri thùc. Khai ph¡ dú li»u l mët kh¥u quan trång
trong qu¡ tr¼nh ph¡t hi»n tri thùc tø cì sð dú li»u. Khai ph¡ dú li»u gçm
nhi·u h÷îng ti¸p cªn, c¡c kÿ thuªt ch½nh ph¦n lîn ÷ñc k¸ thøa tø c¡c
l¾nh vüc cì sð dú li»u, m¡y håc (machine learning), tr½ tu» nh¥n t¤o (artificialintellgence), lþ thuy¸t thæng tin (information theory), x¡c su§t thèng
k¶ (probability & statics) v c¡c kÿ thuªt t½nh to¡n m·m. C¡c b i to¡n
chõ y¸u trong khai th¡c dú li»u l khai th¡c chuéi, khai th¡c wed, ph¡t
hi»n luªt k¸t hñp, v§n · gom cöm, ph¥n lîp (classification) dú li»u.
Vîi sü ra íi v ph¡t triºn cõa lþ thuy¸t tªp mí, tin håc ¢ câ c¡i nh¼n g¦n
vîi thüc ti¹n hìn, c¡c cæng cö cõa logic mí cho ph²p sû lþ nhúng thæng tin
khæng ¦y õ, khæng ch½nh x¡c, ch¯ng h¤n vi»c t¼m tái èi t÷ñng "gièng
nhau" chù khæng ph£i "b¬ng nhau" nh÷ vîi c¡ch t¼m ki¸m thæng th÷íng.
Ch½nh v¼ nhúng þ ngh¾a â m em ¢ lüa chån · t i "Lþ thuy¸t tªp mí
v ùng döng trong ph¥n lîp dú li»u" l m · t i cho luªn v«n cõa m¼nh.
Möc ½ch cõa · t i
Möc ½ch cõa · t i n y nh¬m nghi¶n cùu lþ thuy¸t tªp mí, quan h» mí,
so s¡nh vîi lþ thuy¸t tªp hñp kinh iºn. Nghi¶n cùu mët sè ph÷ìng ph¡p
ph¥n lîp dú li»u v t¼m c¡ch ùng döng tªp mí v quan h» mí trong b i
to¡n ph¥n lîp dú li»u çng thíi minh håa tr¶n mët sè b i to¡n cö thº.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
Nëi dung ch½nh cõa luªn v«n gçm hai ch÷ìng
Ch÷ìng I: Tªp mí v quan h» mí.
Ch÷ìng n y tr¼nh b y kh¡i ni¶m tªp mí, c¡c ph²p to¡n tr¶n tªp mí v
quan h» mí còng nhúng t½nh ch§t cì b£n cõa quan h» mí.
Ch÷ìng II: Ùng döng trong ph¥n lîp dú li»u.
Ch÷ìng 2 tr¼nh b y kh¡i qu¡t v· b i to¡n ph¥n lîp, c¡ch ph¥n lîp thæng
th÷íng düa tr¶n quan h» t÷ìng ÷ìng v c¡ch ph¥n lîp düa tr¶n quan h»
mí.
th¡i nguy¶n, 1 th¡ng 10 n«m 2011.
Ng÷íi thüc hi»n
Ho ng Thà Khuy¶n
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
Ch֓ng 1
Tªp mí v quan h» mí
Ch÷ìng n y giîi thi»u kh¡i n»m tªp mí, c¡c ph²p to¡n tr¶n tªp mí,
quan h» mí v mët sè t½nh ch§t cõa quan h» mí
1.1 Tªp mí
Lþ thuy¸t tªp hñp vèn ÷ñc xem l n·n t£ng cõa to¡n håc. Trong â
tªp hñp l kh¡i ni»m cì b£n khæng ành ngh¾a cán t÷ìng quan cì b£n l
t÷ìng quan li¶n thuëc. Cho mët tªp hñp tùc l ch¿ ra mët d§u hi»u °c
tr÷ng º câ thº x¡c ành ÷ñc mët ph¦n tû câ thuëc mët tªp hñp hay
khæng?
V½ dö 1.1.
X²t X l tªp hñp c¡c håc sinh tr÷íng THPT Ba Bº.
A l tªp hñp c¡c håc sinh lîp 10A1. Nh÷ vªy vîi mët håc sinh b§t ký cõa
tr÷íng th¼ câ thº kh¯ng ành håc sinh â câ thuëc A hay khæng.
Ta th§y méi tªp hñp câ thº °t t÷ìng ùng h m mët h m °c tr÷ng:
µA :X −→ {0; 1}
(
1 n¸u x ∈ A
x 7−→
0 n¸u x ∈
/A
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
Ng÷ñc l¤i n¸u cho h m °c tr÷ng tr¶n mët tªp hñp X tùc l h m:
µ : X −→ {0; 1}, A = {x ∈ X|µ(x) = 1} l x¡c ành duy nh§t.
Tuy nhi¶n trong cuëc sèng ng÷íi ta v¨n dòng nhúng kh¡i ni»m m°c dò
khæng rã r ng nh÷ng v¨n hiºu ÷ñc. Ch¯ng h¤n nâi "mët håc sinh cao".
M°c dò khæng bi¸t ½ch x¡c em håc sinh â cao l bao nhi¶u ng÷íi ta ·u
h¼nh dung ÷ñc håc sinh cao l g¼? Tø â, n¸u ta x²t tªp A= {c¡c håc
sinh cao} th¸ th¼ mët håc sinh l thuëc v o tªp A vîi mët mùc ë n o â.
Ch¯ng h¤n n¸u håc sinh â cao 1,8m th¼ câ thº nâi håc sinh â ch«c chn
thuëc A, cán mët håc sinh cao 1,65m th¼ 60% l thuëc A. Nâi c¡ch kh¡c
ta câ thº x¡c ành mët h m:
µA :X −→ [0; 1]
x 7−→ µA (x)
µA (x) ÷ñc gåi l ë phö thuëc x v o tªp A. Tªp A x¡c ành nh÷ tr¶n gåi
l tªp con mí cõa X.
Vªy ta câ thº ành ngh¾a tªp con mí cõa mët tªp X l :
ành ngh¾a 1.1. Cho X l mët tªp hñp, tªp con A ÷ñc gåi l mët tªp
con mí trong X, n¸u nâ câ thº biºu di¹n d÷îi d¤ng:
A = {(x, µA(x))/x ∈ X } trong â µA l h m:
µA :X −→ [0; 1]
x 7−→ µA (x)
H m µA ÷ñc gåi l h m thuëc cõa A cán µA(x) gåi l ë phö thuëc cõa
x v o A.
Biºu di¹n tªp mí.
- Khi X = {x1, x2, .., xn} th¼ tªp con mí A câ thº ÷ñc biºu di¹n b¬ng
c¡ch li»t k¶ A = {(x1, µA(x1)),(x2, µA(x2)),...,(xn, µA(xn))}.
- N¸u X l mët tªp li¶n töc th¼ h m thuëc cõa A th÷íng ÷ñc biºu di¹n
b¬ng ç thà. Ng÷íi ta th÷íng chån c¡c h m thuëc câ h¼nh tam gi¡c, h¼nh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
thang, h¼nh bªc thang hay h¼nh chuæng...
H¼nh 1.1: H m tam gi¡c
H¼nh 1.2: H m h¼nh thang
V½ dö 1.2.
Cho tªp hñp X = {x1, x2}. Th¼ A = { (x1, 1), ( x2, 0.7)}l mët tªp
con mí tr¶n X.
V½ dö 1.3.
Cho X l tªp c¡c håc sinh tr÷íng THPT Ba Bº, A l tªp c¡c håc sinh
cao. Khi â h m thuëc cõa A ÷ñc x¡c ành bði h¼nh v³ sau:
H¼nh 1.3: H m thuëc cõa A
N¸u µA(x) = 0 th¼ câ thº nâi x ch«c chn khæng thuëc A.
N¸u µA(x) = 1 th¼ câ thº nâi x chc chn thuëc A.
º cho ti»n v· sau ta s³ quy ÷îc ch¿ nâi tªp mí thay cho tªp con mí.
Ta x²t mët sè kh¡i ni»m li¶n quan ¸n tªp mí nh÷ sau:
ành ngh¾a 1.2. Gi¡ cõa tªp mí A, kþ hi»u supp(A), l mët bë phªn cõa
X tr¶n â h m thuëc cõa A kh¡c khæng: supp(A) = { x ∈ X|µA(x) 6= 0}.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
V½ dö 1.4.
Cho X = { 2, 3, 4, 5} l mët tªp hñp
V A = {(2, 1), (3, 0.5), (4, 0), (5, 0.2)} l mët tªp mí tr¶n X khi â:
supp(A) ={2, 3, 5} l gi¡ cõa tªp mí.
ành ngh¾a 1.3. ë cao cõa tªp mí A, k½ hi»u h(A), l gi¡ trà lîn nh§t
m h m thuëc câ thº l§y ÷ñc: h(A) = sup {µA(x)|x ∈ X}.
V½ dö 1.5.
Cho X = { 2, 3, 4, 5} l mët tªp hñp
V A = {(2, 1), ( 3, 0.5), (4, 0), (5, 0.2)} l mët tªp mí tr¶n X khi â ë
cao cõa tªp mí A l h(A) = 1.
ành ngh¾a 1.4. Tªp con mí cõa A l chu©n hâa n¸u chi·u cao h(A) =
1.
V½ dö 1.6.
V½ dö tªp con mí 1.5 l chu©n ho¡.
ành ngh¾a 1.5. H¤t nh¥n cõa A kþ hi»u l ker(A), l tªp c¡c ph¦n tû cõa
X m t¤i â h m thuëc cõa A câ gi¡ trà 1: Ker(A) = {x ∈ X |µA(x) = 1}.
V½ dö 1.7.
Cho X = { 2, 3, 4, 5} l mët tªp hñp
V A = {(2, 1), ( 3, 0.5), (4, 0), (5, 0.2)} l mët tªp mí tr¶n X khi â h¤t
nh¥n cõa A l Ker(A) = {2}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
V½ dö 1.8.
H¼nh 1.4: H m thuëc cõa tªp mí
A
H¼nh 1.5: H¤t nh¥n cõa tªp mí A
Khi mët tªp X húu h¤n, ta cán °c tr÷ng tªp con mí A cõa X bði lüc
l÷ñng cõa nâ.
P
* Lüc l÷ñng cõa tªp mí A ÷ñc x¡c ành |A| = µA(x).
x∈X
ành ngh¾a 1.6. Hai tªp con mí A v B cõa X l b¬ng nhau n¸u c¡c h m
thuëc cõa chóng l§y còng gi¡ trà vîi måi ph¦n tû cõa X: ∀x ∈ X|µA(x) =
µB (x).
ành ngh¾a 1.7. Cho hai tªp con mí A v B cõa X, ta nâi r¬ng A bao
h m trong B, kþ hi»u A ⊆ B , n¸u c¡c h m thuëc cõa chóng thäa m¢n i·u
ki»n: ∀x ∈ X|µA(x) ≤ µB (x).
V½ dö 1.9.
Gi£ sû cho hai tªp mí tr¶n tªp n·n X = {2, 3, 4, 5}.
A = {(2, 0.1), (3, 0.5), (4, 0.3), (5, 0.2)}
B = {(2, 1), (3, 0.8), (4, 0.5), (5, 0.7)}
Th¸ th¼ A l tªp con cõa B.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
1.2 C¡c ph²p to¡n tr¶n tªp mí
T÷ìng tü nh÷ èi vîi tªp hñp kinh iºn, èi vîi tªp mí ta công x²t
c¡c ph²p to¡n Hñp, Giao, Ph¦n bò v t½ch · -c¡c. Ng÷íi ta cè gng chån
c¡ch biºu di¹n h m thuëc èi vîi c¡c ph²p to¡n â sao cho tªp c¡c t½nh
ch§t cõa tªp hñp kinh iºn ÷ñc duy tr¼ c ng nhi·u c ng tèt.
1.2.1 Giao cõa hai tªp mí
Giao cõa hai tªp mí A v B l mët tªp mí kþ hi»u l A ∩ B câ h m
thuëc tho£ m¢n c¡c t½nh ch§t sau:
* µA∩B ch¿ phö thuëc v o µA(x) v µB (x).
* N¸u µB (x) = 1 ∀x ∈ X th¼ µA∩B = µA(x).
*µ(A∩B)∩C (x) = µA∩(B∩C)(x).
* µA∩B = µB∩A(x) måi x ∈ X .
* N¸u A1 ⊆ A2 th¼ A1 ∩ B ⊆ A2 ∩ B . (µA (x) ≤ µA th¼ µA ∩B ≤ µA2∩B ).
Câ nhi·u cæng thùc tho£ m¢n c¡c t½nh ch§t tr¶n, c«n cù v o thüc t¸ ng÷íi
ta th÷íng dòng mët sè cæng thùc sau:
1. µA∩B (x) = (min {µA(x), µB (x)}.
2. µA∩B (x) = min(µA(x), µB (x)) n¸u max(µA(x), µB (x)) = 1.
0
trong c¡c tr÷íng hñp cán l¤i.
3. µA∩B (x) = max(0, µA(x) + µB (x) − 1).
4. µA∩B (x) = µA(x)*µB (x).
5. µA∩B (x) = 2 − µ (x) +µAµ(x)(x)∗ µ−Bµ(x)(x) ∗ µ (x) .
A
B
A
B
D¹ kiºm tra c¡c cæng thùc n y ·u tho£ m¢n c¡c t½nh ch§t cõa ành ngh¾a.
Ng÷íi ta th§y r¬ng trong c¡c cæng thùc tr¶n th¼ cæng thùc min (1) l ìn
gi£n nh§t v duy tr¼ ÷ñc nhi·u t½nh ch§t cõa ph²p giao èi vîi tªp hñp
kinh iºn. N¸u khæng câ chó th½ch g¼ th¶m th¼ cæng thùc t½nh h m thuëc
cõa giao hai tªp mí ÷ñc ng¦m hiºu l cæng thùc min.
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
1
http://www.lrc-tnu.edu.vn
9
V½ dö 1.10.
Gi£ sû cho hai tªp mí tr¶n tªp n·n X = {2, 3, 4, 5}.
A = {(2, 1), (3, 0.5), (4, 0.3), (5, 0.2)}
B = {(2, 0.5), (3, 0.7), (4, 0.2), (5, 0.4)}
Khi â:
A ∩ B = {(2, 0.5), (3, 0.5), (4, 0.2), (5, 0.2)}
V½ dö 1.11.
Cho hai tªp mí A v B tr¶n n·n X câ h m thuëc cho bði ç thà h¼nh
sau:
H¼nh 1.6: H m thuëc cõa tªp con mí A v B
Th¸ th¼ h m thuëc cõa A ∩B ÷ñc biºu di¹n bði h¼nh sau:
H¼nh 1.7: H m thuëc cõa A ∩B
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
1.2.2 Hñp cõa hai tªp mí
Hñp cõa hai tªp mí A v B l mët tªp mí kþ hi»u l A ∪ B câ h m
thuëc tho£ m¢n c¡c t½nh ch§t sau:
* µA∪B (x) ch¿ phö thuëc v o µA(x) ho°c µB (x).
* N¸u µB (x) = 0 måi x ∈ X th¼ µA∪B (x) = µA(x).
* µA∪B = µB∪A(x) måi x ∈ X .
*µ(A∪B)∪C (x) = µA∪(B∪C)(x).
* N¸u A1 ⊆ A2 th¼ A1 ∪ B ⊆ A2 ∪ B . (µA (x) ≤ µA th¼ µA ∩B ≤ µA2∩B ).
Câ nhi·u cæng thùc tho£ m¢n c¡c t½nh ch§t tr¶n, c«n cù v o thüc t¸ ng÷íi
ta th÷íng dòng mët sè cæng thùc sau:
1. µA∪B = max{
( µA (x), µB (x)}.
2. µA∪B (x) = max(µA(x), µB (x)) n¸u min(µA(x), µB (x)) = 0.
1
trong c¡c tr÷íng hñp cán l¤i.
3. µA∪B (x) = min(1, µA(x) + µB (x)).
4. µA∪B (x) = µA(x) + µB (x) - µA(x)*µB (x).
+ µB (X)
.
5. µA∪B (x) = 1 µ+Aµ(x)(x)
+ µB (x)
A
D¹ kiºm tra c¡c cæng thùc n y ·u tho£ m¢n c¡c t½nh ch§t cõa ành ngh¾a.
Ng÷íi ta th§y r¬ng trong c¡c cæng thùc tr¶n th¼ cæng thùc max (1) l ìn
gi£n nh§t v duy tr¼ ÷ñc nhi·u t½nh ch§t cõa ph²p hñp èi vîi tªp hñp
kinh iºn.
1
2
1
V½ dö 1.12.
Gi£ sû cho hai tªp mí tr¶n tªp n·n X = { 2, 3, 4, 5}.
A = {(2, 1), (3, 0.5), (4, 0.3), (5, 0.2)}
B = {(2, 0.5), (3, 0.7), (4, 0.2), (5, 0.4)}
Khi â:
A ∪ B = {(2, 1), (3, 0.7), (4, 0.3), (5, 0.4)}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
V½ dö 1.13.
Cho hai tªp mí A v B tr¶n n·n X câ h m thuëc cho bði h¼nh sau:
H¼nh 1.8: H m thuëc cõa A v B
Th¸ th¼ h m thuëc cõa A ∪B ÷ñc biºu di¹n bði h¼nh sau:
H¼nh 1.9: H m thuëc cõa A ∪B
1.2.3 Ph¦n bò cõa mët tªp mí
ành ngh¾a 1.8. Ph¦n bò Ac cõa tªp con mí A cõa X ÷ñc ành ngh¾a
l tªp con mí cõa X vîi h m thuëc: ∀x ∈ X|µA (x) = 1 − µA(x).
c
Ph¦n bò Ac cõa tªp con mí A cõa X l mët tªp con mí sao cho mët
ph¦n tû x cõa X c ng thuëc nhi·u v o Ac chøng n o nâ c ng ½t thuëc v o A.
V½ dö 1.14.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
Gi£ sû cho tªp con mí tr¶n tªp n·n X = { 2, 3, 4, 5}.
A = {(2, 1), (3, 0.5), (4, 0.3), (5, 0.2)}
Ac = {(1, 1), (2, 0), (3, 0.5), (4, 0.7), (5, 0.8)}
V½ dö 1.15.
Cho tªp con mí A tr¶n tªp n·n X câ h m thuëc cho bði h¼nh sau:
H¼nh 1.10: H m thuëc cõa A
Th¸ th¼ h m thuëc cõa Ac ÷ñc biºu di¹n bði h¼nh sau:
H¼nh 1.11: H m thuëc cõa Ac
1.2.4 T½ch · c¡c cõa hai tªp mí
ành ngh¾a 1.9. Cho X l mët tªp hñp, A v B l hai tªp con mí trong
X câ h m thuëc l¦n l÷ñt l µA, µB . T½ch e-cac cõa A v B, kþ hi»u l
A × B l mët tªp con mí ÷ñc x¡c ành nh÷ sau:
µA×B (x, y) = min{µA (x), µB (x)}.
V½ dö 1.16.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
Gi£ sû cho hai tªp mí tr¶n tªp n·n X = {a, b, c}.
A = {(a, 1), (b, 0.5), (c, 0.2)}
B = {(a, 0.5), (b, 0.7), (c, 0.2)}
Th¸ th¼
= {((a,a), 0.5), ((a,b), 0.7), ((a,c), 0.2), ((b,a), 0.5), ((b,b), 0.5),
((b, c), 0.2), ((c,a), 0.2), ((c,b), 0.2), ((c,c), 0.2)}
Nhªn x²t: Vîi c¡ch chån h m thuëc cho c¡c ph²p to¡n tr¶n câ thº th§y
l¤i c¡c t½nh ch§t t÷ìng tü nh÷ vîi tªp kinh iºn ÷ñc giú nguy¶n. Ch¯ng
h¤n:
- T½nh giao ho¡n, hñp, giao.
- T½nh k¸t hñp.
- (Ac)c = A.
Tuy nhi¶n câ t½nh ch§t khæng ÷ñc b£o to n ch¯ng h¤n:
- Ac ∩ A 6= ∅.
- Ac ∪ A 6= X .
A×B
V½ dö 1.17.
Cho tªp mí A v Ac tr¶n n·n X câ h m thuëc cho bði h¼nh sau:
H¼nh 1.12: H m thuëc cõa A v Ac
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
Th¸ th¼ h m thuëc cõa A ∪Ac ÷ñc biºu di¹n bði h¼nh sau:
H¼nh 1.13: H m thuëc cõa A ∪Ac
H m thuëc cõa A ∩Ac ÷ñc biºu di¹n bði h¼nh sau:
H¼nh 1.14: H m thuëc cõa A ∩Ac
1.3 Quan h» mí
T÷ìng tü nh÷ quan h» tr¶n c¡c tªp hñp t÷ìng ÷ìng kinh iºn èi vîi
tªp mí ta công x²t quan h» mí vîi c¡c t½nh ch§t cõa chóng.
1.3.1 Kh¡i ni»m quan h» mí
Quan h» mí âng vai trá quan trång trong logic mí v lªp luªn x§p
x¿. Kh¡i ni»m quan h» mí l sü têng qu¡t hâa trüc ti¸p cõa kh¡i ni»m
quan h» (quan h» rã). Tr÷îc h¸t ta nhc l¤i kh¡i ni»m quan h».
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
15
Gi£ sû U v V l hai tªp. Mët quan h» R tø U ¸n V (s³ ÷ñc gåi l
quan h» hai ngæi, ho°c quan h» nhà nguy¶n) l mët tªp con cõa t½ch ·
c¡c U × V . Trong tr÷íng hñp U = V, ta nâi R l quan h» tr¶n U. Ch¯ng
h¤n, tªp R bao gçm t§t c£ c¡c c°p ng÷íi (a,b) trong â a l chçng cõa b,
x¡c ành quan h» "vñ -chçng"tr¶n tªp n o â.
Khi U v V l c¡c tªp húu h¤n, chóng ta s³ biºu di¹n quan h» R tø U ¸n
V bði ma trªn, trong â c¡c dáng ÷ñc ¡nh d§u bði c¡c ph¦n tû x ∈ U
v c¡c cët ÷ñc ¡nh d§u bði c¡c ph¦n tû y ∈ V . Ph¦n tû cõa ma trªn
n¬m ð dáng x, cët y l λR(x, y)
(
1
λR (x, y) =
0
V½ dö 1.18.
n¸u(x, y) ∈ X,
n¸u(x, y) ∈/ X
Gi£ sû U = {1,2,3} v V = {a,b,c,d} gi£ sû R l quan h» tø U ¸n V
nh÷ sau:
R = {(1,a), (1,d), (2,a), (2,b), (3,c), (3,d)}
Chóng ta biºu di¹n quan h» R bði ma trªn sau:
1 0 0 1
R = 1 1 0 0
0 0 1 1
B¥y gií ta x²t quan h» "anh em hå g¦n"tr¶n mët tªp ng÷íi U n o â.
Quan h» n y khæng thº °c tr÷ng bði tªp rã cõa t½ch U × U . Mët c¡ch
hñp lþ nh§t l x¡c ành quan h» n y bði mët tªp mí tr¶n U × U .
Ch¯ng h¤n µR(a, b) = 1 n¸u a l anh ruët cõa b; µR(a, b) = 0,9 n¸u a l
anh con chó con b¡c cõa b; µR(a, b) = 0,75 n¸u a l anh em ch¡u cæ, ch¡u
cªu cõa b;..
Mët quan h» mí tø U ¸n V l mët tªp mí tr¶n t½ch · c¡c U × V .
Têng qu¡t, mët quan h» n ngæi l mët tªp R trong khæng gian t½ch · c¡c
cõa n khæng gian U1 × U2 × ... × Un.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
16
ành ngh¾a 1.10. Cho X v Y l hai tªp hñp. Mët quan h» hai ngæi mí
tø X −→ Y l mët tªp con mí cu£ t½ch · c¡c X × Y .
V½ dö 1.19.
Gi£ sû cho t¥p mí A = {(a, 0.2), (b, 0.5), (c, 1)} tr¶n tªp n·n X =
{a, b, c} v tªp mí B = {(u, 0.3), (v, 0.9)} tr¶n tªp n·n Y = {u, v}.
Khi â R = {((a,u), 0.2), ((a,v), 0.2), ((b,u), 0.3), ((b,v), 0.5), ((c,u), 0.3),
((c,v), 0.9)} l mët quan h» mí.
Quan h» mí t÷ìng ÷ìng kinh iºn th¼ hai ph¦n tû ho°c l câ quan
h» vîi nhau ho°c l khæng nh÷ng trong quan h» mí th¼ hai ph¦n tû b§t
ký luæn câ quan h» vîi nhau ð mët mùc ë n o â.
N¸u X = Y, ta nâi R l quan h» tr¶n X.
1.3.2 Hñp th nh c¡c quan h» mí
ành ngh¾a 1.11. Hñp th nh max - min
Gi£ sû R l quan h» mí tø U ¸n V v S l quan h» mí tø V ¸n W. Hñp
thanh max - min c¡c quan h» mí R v S l quan h» mí R ◦ S tø U ¸n
W vîi h m thuëc ÷ñc x¡c ành nh÷ sau:
µR◦S (u, w) = max {min{µR (u, v), µS (v, w)∀v ∈ V }}. (1)
Nh¥n x²t: Cæng thùc tr¶n gåi l hñp th nh max - min. Ng÷íi ta cán
dòng cæng thùc hñp th nh max - t½ch nh÷ sau:
µR◦S = max {µR (u, v).µS (v, w)|∀v ∈ V }. (2)
V½ dö 1.20.
Cho c¡c quan h» mí R1(x, y), R2(y, z) ÷ñc x¡c ành bði c¡c ma trªn
sau:
0, 3 1 0 0, 5
R1 (x, y) = 0, 7 0, 1 1 0
0 0, 6 1 0, 3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -