Luận văn tốt nghiệp
Phát hiện luật theo tiếp cận tập thô
-1Môc lôc
PhÇn më ®Çu.................................................................................................. 5
Ch−¬ng I. Tæng quan vÒ kh¸m ph¸ tri thøc theo tiÕp cËn
tËp th«............................................................................................................. 9
I.1.
HÖ th«ng tin vµ tËp th«............................................................................ 9
I.1.1. Mét sè kh¸i niÖm ................................................................................... 9
I.1.1.1. Kh¸i niÖm vÒ hÖ th«ng tin .......................................................................
9
I.1.1.2. Kh¸i niÖm vÒ b¶ng quyÕt ®Þnh ................................................................. 10
I.1.1.3. Quan hÖ kh«ng ph©n biÖt ®−îc trong hÖ th«ng tin ..................................
11
I.1.1.4. TËp m« t¶ ®−îc vµ ng«n ng÷ m« t¶ tËp .................................................... 13
I.1.2. TËp th« trong kh«ng gian xÊp xØ ............................................................ 14
I.1.2.1. TËp xÊp xØ trªn, xÊp xØ d−íi vµ miÒn biªn ...............................................
14
I.1.2.2. Hµm th« vµ mét sè ®é ®o phô thuéc cã thuéc tÝnh liªn quan .................. 19
I.2.
Kh¸m ph¸ tri thøc theo tiÕp cËn tËp th« ..............................................
20
I.2.1. TÝnh phô thuéc thuéc tÝnh trong hÖ th«ng tin ........................................ 20
I.2.1.1. TÝnh phô thuéc thuéc tÝnh ........................................................................ 20
I.2.1.2. TËp thuéc tÝnh rót gän vµ tËp thuéc tÝnh nh©n ......................................... 21
I.2.1.3. Ma trËn ph©n biÖt ®−îc vµ hµm ph©n biÖt ®−îc ....................................... 23
I.2.2. Qu¸ tr×nh kh¸m ph¸ tri thøc theo tiÕp cËn tËp th« .................................. 24
I.2.2.1. Sù rêi r¹c ho¸ dùa trªn tËp th« vµ lËp luËn logic ...................................... 25
I.2.2.2. Lùa chän thuéc tÝnh dùa trªn tËp th« víi ph−¬ng ph¸p ®¸nh gi¸ kinh
nghiÖm ....................................................................................................... 25
I.2.2.3. Kh¸m ph¸ luËt bëi b¶ng ph©n bè tæng qu¸t dùa trªn tËp th« ................... 27
I.2.3. Kh¸m ph¸ mÉu trong hÖ th«ng tin ......................................................... 27
I.3.
KÕt luËn ch−¬ng I ...................................................................................
Ch−¬ng II. Kh¸m ph¸ luËt theo tiÕp cËn tËp th« vµ ®èi
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
29
-2s¸nh víi kh¸m ph¸ luËt kÕt hîp ...................................................... 30
II.1. Kh¸m ph¸ luËt kÕt hîp, néi dung c¬ b¶n cña kh¸m ph¸ tri thøc
trong c¬ së d÷ liÖu ............................................................................................. 30
II.1.1. LuËt kÕt hîp .......................................................................................... 30
II.1.2. Mét sè c¬ së to¸n häc khai ph¸ luËt kÕt hîp ........................................ 32
II.1.2.1. TËp phæ biÕn .......................................................................................... 32
II.1.2.2. Khai ph¸ luËt kÕt hîp dùa trªn tËp phæ biÕn .......................................... 33
II.2. Qu¸ tr×nh kh¸m ph¸ tri thøc theo tiÕp cËn t©p th« ............................. 35
II.2.1. Qu¸ tr×nh kh¸m ph¸ luËt trong b¶ng quyÕt ®Þnh ................................... 35
II.2.1.1. LuËt trong b¶ng quyÕt ®Þnh ................................................................... 35
II.2.1.2. Hai ®Æc tr−ng cña luËt: §é m¹nh vµ ®é nhiÔu cña luËt .........................
35
II.2.1.3. Qu¸ tr×nh kh¸m ph¸ luËt ........................................................................ 36
II.2.1.4. ThuËt to¸n tèi −u ho¸ c¸c luËt ............................................................... 45
II.2.1.5. ThuËt to¸n gi¶i ph¸p gÇn tèi −u ho¸ c¸c luËt ......................................... 45
II.2.1.6. Tiªu chuÈn lùa chän luËt trong tËp th« .................................................. 46
II.2.2. Qu¸ tr×nh kh¸m ph¸ mÉu trong b¶ng quyÕt ®Þnh .................................. 46
II.2.2.1. Kh¸i niÖm mÉu ...................................................................................... 46
II.2.2.2. Hai bµi to¸n mÉu c¬ b¶n ........................................................................ 47
II.2.2.3. C¸c ph−¬ng ph¸p sinh mÉu ...................................................................
51
II.2.3. Mèi liªn hÖ gi÷a mÉu vµ luËt theo tiÕp cËn tËp th« .............................. 58
II.3. So s¸nh luËt theo tiÕp cËn tËp th« vµ luËt kÕt hîp ............................... 60
II.4. KÕt luËn ch−¬ng II .................................................................................. 62
Ch−¬ng III. øng dông cña mÉu vµ thö nghiÖm qu¸ tr×nh
kh¸m ph¸ luËt theo tiÕp cËn tËp th« ............................................. 63
III.1. øng dông cña mÉu .................................................................................. 63
III.1.1. MÉu vµ qu¸ tr×nh ph©n lo¹i ban ®Çu .................................................... 63
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-3III.1.2. M« t¶ c¸c líp quyÕt ®Þnh ..................................................................... 65
III.1.3. MÉu vµ bµi to¸n ph©n t¸ch b¶ng d÷ liÖu lín ........................................ 66
III.1.4. MÉu vµ bµi to¸n ph©n líp .................................................................... 67
III.2. Thö nghiÖm qu¸ tr×nh kh¸m ph¸ luËt theo tiÕp cËn tËp th« trªn bµi
to¸n qu¶n lý th«ng tin kh¸ch XuÊt nhËp c¶nh qua cöa khÈu ....................... 69
III.2.1. Bµi to¸n qu¶n lý th«ng tin kh¸ch XuÊt nhËp c¶nh qua cöa khÈu ........
69
III.2.1.1. M« t¶ bµi to¸n XNC ............................................................................... 69
III.2.1.2. TËp th« trong bµi to¸n qu¶n lý th«ng tin kh¸ch XuÊt nhËp c¶nh ........... 71
III.2.2. §Ò xuÊt gi¶i quyÕt tËp th« trong bµi to¸n ............................................ 71
III.2.2.1. M« t¶ d÷ liÖu .......................................................................................... 71
III.2.2.2. Qu¸ tr×nh ph¸t hiÖn luËt .........................................................................
74
III.2.2.3. §Ò xuÊt øng dông luËt t×m ®−îc trong bµi to¸n thùc tÕ .......................... 81
III.3. KÕt luËn ch−¬ng III ................................................................................ 82
KÕt luËn ........................................................................................................ 84
Tµi liÖu tham kh¶o................................................................................. 86
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-4-
C¸c ký hiÖu vµ côm tõ viÕt t¾t sö dông trong luËn v¨n
Ký hiÖu
M« t¶
A
HÖ th«ng tin hay b¶ng quyÕt ®Þnh
A, B
TËp c¸c thuéc tÝnh trong hÖ th«ng tin
D
TËp thuéc tÝnh quyÕt ®Þnh trong hÖ th«ng tin
a
Mét thuéc tÝnh ®iÒu kiÖn trong tËp thuéc tÝnh ®iÒu kiÖn cña hÖ th«ng
tin
Va
TËp gi¸ trÞ cña thuéc tÝnh ®iÒu kiÖn
U
TËp ®èi t−îng (tËp tæng thÓ) trong hÖ th«ng tin
RED
TËp rót gän
∅
Rçng
⊆
BÞ chøa trong
∈
Thuéc (lµ phÇn tö cña)
≥
Lín h¬n hoÆc b»ng
≤
Nhá h¬n hoÆc b»ng
≠
Kh¸c
∪, ∩
PhÐp hîp, giao cña mét tËp hîp
ViÕt t¾t
M« t¶
CSDL
C¬ së d÷ liÖu
KDD
Knowledge Discovery in Database
RS
Rough Set
GDT
Generalization Distribution Table
ILP
Inductive Logic Programming
GrC
Granular Computing
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-5-
PhÇn më ®Çu
Lý thuyÕt tËp th« do Z.Pawlak ®Ò xuÊt vµo ®Çu nh÷ng n¨m 80 cña thËp kØ
XX ®· ®−îc ¸p dông ngµy cµng réng r·i trong lÜnh vùc kh¸m ph¸ tri thøc trong
c¸c c¬ së d÷ liÖu. Trong nh÷ng n¨m gÇn ®©y, lý thuyÕt tËp th« ®−îc nhiÒu nhãm
nghiªn cøu ho¹t ®éng trong lÜnh vùc tin häc nãi chung vµ khai ph¸ tri thøc tõ c¬
së d÷ liÖu nãi riªng nghiªn cøu vµ ¸p dông trong thùc tÕ [1,4,6,9,10]. Lý thuyÕt
tËp th« ®−îc ph¸t triÓn trªn nÒn t¶ng c¬ së to¸n häc v÷ng ch¾c gióp cung cÊp
nh÷ng c«ng cô h÷u Ých ®Ó gi¶i quyÕt nh÷ng bµi to¸n ph©n líp d÷ liÖu, ph¸t hiÖn
luËt ... Nh÷ng ph−¬ng ph¸p dùa trªn lý thuyÕt tËp th« ®Æc biÖt h÷u Ých ®èi víi
nh÷ng bµi to¸n víi d÷ liÖu m¬ hå, kh«ng ch¾c ch¾n. Ngoµi ra, lý thuyÕt tËp th«
cho phÐp tr×nh diÔn mét m« h×nh h×nh thøc vÒ tri thøc. M« h×nh nµy ®−îc x¸c
®Þnh nh− hä c¸c mèi quan hÖ "kh«ng ph©n biÖt ®−îc", nhê ®ã tri thøc ®−îc ®Þnh
nghÜa mét c¸ch râ rµng theo nghÜa to¸n häc vµ cã thÓ ®−îc ph©n tÝch vµ xö lý
b»ng nh÷ng c«ng cô to¸n häc.
Trong lý thuyÕt tËp th«, d÷ liÖu ®−îc biÓu diÔn th«ng qua hÖ th«ng tin, hay
b¶ng quyÕt ®Þnh; ý t−ëng chÝnh trong viÖc ph©n tÝch d÷ liÖu theo tiÕp cËn tËp th«
xuÊt ph¸t tõ nh÷ng kh¸i niÖm vÒ sù xÊp xØ tËp, vÒ quan hÖ "kh«ng ph©n biÖt
®−îc". Tõ nh÷ng b¶ng d÷ liÖu lín víi d÷ liÖu d− thõa, kh«ng hoµn h¶o, d÷ liÖu
liªn tôc, hay d÷ liÖu biÓu diÔn d−íi d¹ng ký hiÖu, lý thuyÕt tËp th« cho phÐp khai
ph¸ tri thøc tõ nh÷ng lo¹i d÷ liÖu nh− vËy nh»m ph¸t hiÖn ra nh÷ng quy luËt tiÒm
Èn tõ khèi d÷ liÖu nµy. Tri thøc ®−îc biÓu diÔn d−íi d¹ng c¸c luËt, mÉu m« t¶
mèi quan hÖ bÞ che dÊu trong d÷ liÖu. Trong lý thuyÕt tËp th«, chÊt l−îng cña
th«ng tin ®−îc ®o b»ng c¸ch sö dông kh¸i niÖm tËp xÊp xØ trªn vµ xÊp xØ duíi.
Nh»m thu hÑp nhiÒu nhÊt chÝnh x¸c th«ng tin, ý t−ëng “rót gän” ®−îc sö dông ®Ó
cho phÐp lo¹i bá nh÷ng th«ng tin d− thõa, kh«ng cÇn thiÕt mµ vÉn gi÷ ®−îc ý
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-6-
nghÜa. Sau khi t×m ®−îc nh÷ng quy luËt chung nhÊt biÓu diÔn d÷ liÖu, ng−êi ta cã
thÓ tÝnh to¸n ®é m¹nh, ®é phô thuéc gi÷a c¸c thuéc tÝnh trong hÖ th«ng tin.
Theo Skowron vµ NingZong [9], c¸ch tiÕp cËn lý thuyÕt tËp th« ®Ó ph©n tÝch d÷
liÖu cã rÊt nhiÒu lîi ®iÓm quan träng nh−:
- Cho phÐp xö lý hiÖu qu¶ b¶ng d÷ liÖu lín, lo¹i bá d÷ liÖu d− thõa, d÷ liÖu
kh«ng hoµn h¶o, d÷ liÖu liªn tôc,
- HiÖu qu¶ trong viÖc t×m kiÕm nh÷ng mÉu tiÒm Èn trong d÷ liÖu,
- Sö dông ®−îc tri thøc kinh nghiÖm,
- NhËn ra c¸c mèi quan hÖ mµ khi sö dông c¸c ph−¬ng ph¸p thèng kª kh¸c
kh«ng ph¸t hiÖn ®−îc,
- Sö dông quan hÖ thø lçi trong qu¸ tr×nh ph¸t hiÖn mÉu,
- Lµm viÖc hiÖu qu¶ trªn tËp d÷ liÖu rót gän,
- C¸ch gi¶i thÝch râ rµng vµ dÔ hiÓu.
Víi nh÷ng lîi ®iÓm quan träng trªn cña lý thuyÕt tËp th«, chóng t«i ®· giµnh
thêi gian ®Ó nghiªn cøu vµ t×m hiÓu vÒ lý thuyÕt nµy. ý t−ëng “Ph¸t hiÖn luËt
theo tiÕp cËn tËp th«” ®−îc chän lµm ®Ò tµi nghiªn cøu khoa häc ®Ó lµm luËn v¨n
th¹c sÜ. LuËn v¨n ®i s©u t×m hiÓu ý t−ëng vµ cë së to¸n häc cña lý thuyÕt tËp th«,
tõ nh÷ng hiÓu biÕt vÒ lý thuyÕt còng nh− øng dông thùc tÕ cña tËp th« trong lÜnh
vùc khai ph¸ d÷ liÖu, chóng t«i ®−a ra nh÷ng nhËn xÐt ®èi s¸nh gi÷a ph¸t hiÖn
luËt theo tiÕp cËn tËp th« vµ ph¸t hiÖn luËt kÕt hîp. Th«ng qua t×m hiÓu vµ khai
th¸c bé c«ng cô ROSETTA (do Aleksander ∅hrn vµ céng sù thuéc nhãm nghiªn
cøu tri thøc thuéc khoa Khoa häc m¸y tÝnh vµ th«ng tin cña tr−êng ®¹i häc
Norwegian, Trondheim, Na-uy cïng nhãm Logic thuéc §HTH Warsaw, Ba-lan
x©y dùng), luËn v¨n còng ®−a ra mét sè ®Ò xuÊt øng dông thö nghiÖm lý thuyÕt
tËp th« vµo viÖc hç trî quyÕt ®Þnh bµi to¸n xuÊt nhËp c¶nh t¹i s©n bay Néi Bµi.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-7-
Ph−¬ng ph¸p nghiªn cøu chñ yÕu cña luËn v¨n lµ kh¶o s¸t, ph©n tÝch néi
dung c¸c bµi b¸o khoa häc vÒ lý thuyÕt tËp th« vµ øng dông ®−îc c«ng bè vµo
nh÷ng n¨m gÇn ®©y. Tõ c¸c kÕt qu¶ nghiªn cøu lý thuyÕt kÕt hîp víi nh÷ng vÊn
®Ò ®Æt ra trong bµi to¸n thùc tÕ, luËn v¨n còng ®Ò xuÊt ph−¬ng ph¸p thö nghiÖm
gi¶i quyÕt vÊn ®Ò kh¸m ph¸ luËt trong thùc tÕ.
LuËn v¨n ®−îc tr×nh bµy gåm cã phÇn më ®Çu, ba ch−¬ng vµ phÇn kÕt luËn.
Trong ch−¬ng mét, chóng t«i tËp trung chñ yÕu vµo giíi thiÖu tæng quan vÒ qu¸
tr×nh kh¸m ph¸ tri thøc theo tiÕp cËn tËp th«. C¸c kh¸i niÖm c¬ b¶n trong lý
thuyÕt tËp th« nh−: hÖ th«ng tin, b¶ng quyÕt ®Þnh, kh¸i niÖm kh«ng ph©n biÖt
®−îc, tËp xØ trªn tËp xØ d−íi vµ miÒn biªn ... ®−îc tr×nh bµy. Néi dung cña
ch−¬ng nµy ®−îc tæng hîp tõ c¸c tµi liÖu [1,4,9,10].
Trong ch−¬ng hai, luËn v¨n tËp trung giíi thiÖu vÒ kh¸m ph¸ luËt kÕt hîp
theo c¸ch tiÕp cËn th«ng th−êng vµ kh¸m ph¸ luËt theo tiÕp cËn tËp th« ®Ó tõ ®ã
®−a ra nh÷ng nhËn xÐt ®èi s¸nh vÒ sù t−¬ng ®ång hoÆc kh¸c biÖt nhau trong c¸c
tÝnh chÊt c¬ b¶n cña hai c¸ch tiÕp cËn. Môc II.2.3 ®−a ra mèi liªn hÖ gi÷a mÉu vµ
luËt theo tiÕp cËn tËp th« [5], dùa trªn nh÷ng mèi quan hÖ ®ã, chóng t«i ®−a ra
mét sè nhËn xÐt ®èi s¸nh gi÷a kh¸m ph¸ luËt kÕt hîp vµ kh¸m ph¸ luËt theo tiÕp
cËn tËp th«. KÕt qu¶ ®¸ng chó ý lµ mèi t−¬ng ®ång gi÷a ®é m¹nh trong luËt theo
tiÕp cËn tËp th« vµ ®é hç trî cña luËt kÕt hîp.
Trong ch−¬ng ba, luËn v¨n ®−a ra mét sè m« h×nh øng dông cña mÉu ®−îc
ph¸t hiÖn tõ d÷ liÖu theo tiÕp cËn tËp th« [5]. Tõ kÕt qu¶ nghiªn cøu tr×nh bµy
trong ch−¬ng mét vµ ch−¬ng hai, th«ng qua c«ng cô ROSETTA, chóng t«i ®Ò
xuÊt viÖc øng dông luËt kÕt hîp theo tiÕp cËn tËp th« vµo thùc tÕ trong bµi to¸n
qu¶n lý th«ng tin kh¸ch xuÊt nhËp c¶nh t¹i cöa khÈu vµ nhËn ®−îc mét sè luËt
t−¬ng ®èi hîp lý.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-8-
LuËn v¨n ®−îc thùc hiÖn d−íi sù h−íng dÉn cña TiÕn sÜ Hµ Quang Thuþ Bé m«n C¸c HÖ thèng Th«ng tin, Khoa C«ng nghÖ. Em xin bµy tá lßng biÕt ¬n
s©u s¾c tíi ThÇy ®· h−íng dÉn vµ cã ý kiÕn chØ dÉn quý b¸u trong qu¸ tr×nh em
lµm luËn v¨n. Em xin ch©n thµnh c¶m ¬n PGS. NguyÔn Quèc To¶n, PGS. TS. Hå
ThuÇn ®· cho nhiÒu ý kiÕn quý b¸u ®Ó b¶n luËn v¨n ®−îc hoµn thiÖn h¬n. Em xin
c¶m ¬n c¸c thÇy gi¸o trong bé m«n C¸c HÖ thèng Th«ng tin, nhãm seminar
“Data mining vµ KDD”. Em còng xin c¶m ¬n c¸c thÇy c« gi¸o trong Khoa, c¸n
bé thuéc phßng Khoa häc vµ §µo t¹o sau §¹i häc, Khoa C«ng nghÖ ®· t¹o ®iÒu
kiÖn trong qu¸ tr×nh häc tËp vµ nghiªn cøu t¹i Khoa. Cuèi cïng xin bµy tá lßng
c¶m ¬n tíi nh÷ng ng−êi th©n trong gia ®×nh, b¹n bÌ ®· ®éng viªn vµ gióp ®ì ®Ó
t«i hoµn thµnh b¶n luËn v¨n nµy.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-9-
Ch−¬ng 1. Tæng quan vÒ kh¸m ph¸ tri thøc theo tiÕp
cËn tËp th«
I.1. HÖ th«ng tin vµ tËp th«
I.1.1. Mét sè kh¸i niÖm
I.1.1.1. Kh¸i niÖm vÒ hÖ th«ng tin
Trong ho¹t ®éng hµng ngµy, ®Æc biÖt khi thu thËp d÷ liÖu vµo c¸c kho d÷
liÖu (datawarehousing), ta th−êng gÆp c¸c tËp hîp d÷ liÖu ®−îc miªu t¶ bëi mét
b¶ng, trong ®ã hµng biÓu diÔn "b¶n ghi" (mét phÇn tö, mét tr−êng hîp, mét sù
kiÖn hay ®¬n gi¶n lµ biÓu diÔn mét ®èi t−îng), cßn c¸c cét biÓu diÔn mét thuéc
tÝnh (mét biÕn, mét quan s¸t, mét tÝnh chÊt ... ). Tõ nh÷ng n¨m ®Çu cña thËp kû
1980, Pawlak h×nh thøc hãa b¶ng kiÓu nµy thµnh kh¸i niÖm hÖ th«ng tin
(information system) [1,5, 9, 10].
§Þnh nghÜa 1.1. HÖ th«ng tin lµ cÆp A = (U,A) trong ®ã U lµ mét tËp h÷u h¹n
kh¸c rçng c¸c ®èi t−îng vµ A lµ mét tËp h÷u h¹n kh¸c rçng c¸c thuéc tÝnh, trong
®ã
a: U → Va víi mäi a ∈ A. TËp Va ®−îc gäi lµ tËp gi¸ trÞ cña a.
• VÝ dô: Cã mét hÖ th«ng tin thÓ hiÖn nh− trong b¶ng 1. Cã 7 ®èi t−îng (Mçi
®èi t−îng ë ®©y lµ mét kh¸ch XuÊt NhËp C¶nh) vµ 3 thuéc tÝnh: Tíi n−íc, N¬i
sinh, T«n gi¸o.
x1
x2
x3
x4
x5
x6
x7
Tíi n−íc
Mü
Mü
Ph¸p
Ph¸p
§øc
Mü
Ph¸p
N¬i sinh
Hµ néi
H¶i phßng
Sµi gßn
Sµi gßn
§µ n½ng
§µ n½ng
§µ n½ng
T«n gi¸o
Cã
Cã
Kh«ng
Kh«ng
Cã
Kh«ng
Kh«ng
B¶ng 1. Mét vÝ dô vÒ hÖ th«ng tin
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-10-
Chóng ta nhËn thÊy tr−êng hîp c¸c ®èi t−îng kh¸c nhau x3 vµ x4, l¹i cã c¸c gi¸
trÞ thuéc tÝnh gièng nhau: ®©y lµ tr−êng hîp kh«ng ph©n biÖt ®−îc c¸c ®èi t−îng
nÕu chØ sö dông th«ng tin tõ c¸c thuéc tÝnh ®· cho. TÝnh kh«ng ph©n biÖt ®−îc lµ
mét trong nh÷ng yÕu tè cña sù mËp mê. Cã thÓ nhËn thÊy tÝnh mËp mê tõ viÖc
kh«ng ph©n biÖt ®−îc: nÕu chØ xem xÐt c¸c thuéc tÝnh trªn ®©y th× hai ®èi t−îng
x3 vµ x4 lµ hoµn toµn gièng nhau, tuy nhiªn nh− sau nµy chóng ta thÊy, x3 khi
xuÊt c¶nh cÇn ph¶i xem xÐt trong khi ®ã víi x4 th× kh«ng cÇn lµm ®iÒu ®ã.
I.1.1.2. Kh¸i niÖm b¶ng quyÕt ®Þnh
Trong nhiÒu øng dông, ng−êi ta ®· biÕt néi dung kÕt qu¶ cña viÖc ph©n líp lµ
quyÕt ®Þnh ph©n líp. Tri thøc (chØ dÉn quyÕt ®Þnh) ph©n líp ®−îc thÓ hiÖn b»ng
mét thuéc tÝnh riªng biÖt ®−îc gäi lµ thuéc tÝnh quyÕt ®Þnh trong hÖ th«ng tin.
Trong tr−êng hîp ®ã, hÖ th«ng tin ®−îc gäi lµ hÖ quyÕt ®Þnh [1,5,9,10].
§Þnh nghÜa 1.2.
B¶ng (hÖ) quyÕt ®Þnh lµ hÖ th«ng tin bÊt kú cã d¹ng
A = (U, A∪{d}) (hay A = (U, A,{d})), víi d ∉ A lµ thuéc tÝnh quyÕt ®Þnh. C¸c
thuéc tÝnh thuéc A ®−îc gäi lµ thuéc tÝnh ®iÒu kiÖn hay ®iÒu kiÖn.
Thuéc tÝnh quyÕt ®Þnh cã thÓ cã nhiÒu h¬n hai gi¸ trÞ, tuy nhiªn th«ng dông lµ
kiÓu gi¸ trÞ nhÞ ph©n. Qu¸ tr×nh kh¸m ph¸ ra mèi quan hÖ gi÷a thuéc tÝnh quyÕt
®Þnh theo thuéc tÝnh ®iÒu kiÖn trong b¶ng quyÕt ®Þnh thuéc vµo lo¹i häc m¸y cã
h−íng dÉn, trong ®ã thÓ hiÖn diÓn h×nh nhÊt lµ "häc qua vÝ dô".
U
x1
x2
x3
x4
x5
x6
x7
Tíi n−íc
Mü
Mü
Ph¸p
Ph¸p
§øc
Mü
Ph¸p
N¬i sinh
Hµ néi
H¶i phßng
Sµi gßn
Sµi gßn
§µ n½ng
§µ n½ng
§µ n½ng
T«n gi¸o
Cã
Cã
Kh«ng
Kh«ng
Cã
Kh«ng
Kh«ng
Xem xÐt
CÊm
Kh«ng
Kh«ng
CÊm
Kh«ng
CÊm
Kh«ng
B¶ng 2. CXN - Mét b¶ng quyÕt ®Þnh
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-11-
VÝ dô. B¶ng 2 m« t¶ mét b¶ng quyÕt ®Þnh bao gåm 7 ®èi t−îng (tr−êng hîp), mét
thuéc tÝnh quyÕt ®Þnh lµ Xem xÐt vµ 3 thuéc tÝnh Tíi n−íc, N¬i sinh, T«n gi¸o.
Chóng ta tiÕp tôc quan s¸t tr−êng hîp cÆp hai ®èi t−îng lµ x3 vµ x4 vÉn lµ cÆp cã
c¸c gi¸ trÞ gièng nhau theo thuéc tÝnh ®iÒu kiÖn, nh−ng kÕt qu¶ quyÕt ®Þnh ®èi víi
hai ®èi t−îng lµ kh¸c nhau.
Nh− vËy mét tri thøc ®−îc tæng hîp tõ b¶ng quyÕt ®Þnh trªn ®©y sÏ lµ luËt cã
d¹ng “NÕu cã Tíi n−íc lµ Mü, N¬i sinh lµ Hµ néi vµ cã t«n gi¸o th× Xem xÐt lµ
CÊm” tøc lµ NÕu mét kh¸ch XuÊt NhËp C¶nh xuÊt c¶nh ®Õn Mü, N¬i sinh lµ Hµ
néi vµ cã t«n gi¸o th× sÏ bÞ cÊm XuÊt NhËp c¶nh ViÖt Nam. Trong nh÷ng thuéc
tÝnh cã thÓ cña tËp c¸c luËt ®−îc x©y dùng, sù cùc tiÓu ho¸ (minimality- ®é dµi
gi¶ thiÕt cña luËt lµ cùc tiÓu) lµ mét trong nh÷ng vÊn ®Ò quan träng [5].
Chó ý. Tæng qu¸t, cã thÓ cã nhiÒu thuéc tÝnh quyÕt ®Þnh vµ khi ®ã b¶ng quyÕt
®Þnh cã d¹ng A = (U, Con∪Dec), víi Con lµ tËp c¸c thuéc tÝnh ®iÒu kiÖn hay
®iÒu kiÖn cßn Dec lµ tËp c¸c thuéc tÝnh quyÕt ®Þnh (trong ®ã Con∩Dec = ∅) [1].
I.1.1.3. Quan hÖ kh«ng ph©n biÖt ®−îc trong hÖ th«ng tin
Mét trong nh÷ng c¬ së to¸n häc cña lý thuyÕt tËp th« lµ quan hÖ kh«ng
ph©n biÖt ®−îc (mét quan hÖ t−¬ng ®−¬ng) trong hÖ th«ng tin.
Cho U lµ tËp c¸c ®èi t−îng, mét quan hÖ nhÞ ph©n R ⊆ U × U trªn U ®−îc gäi lµ:
- Ph¶n x¹ nÕu mäi ®èi t−îng ®Òu cã quan hÖ víi chÝnh nã xRx,
- §èi xøng nÕu xRy th× yRx,
- B¾c cÇu nÕu xRy vµ yRz th× xRz
Mét quan hÖ R cã c¶ ba tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu ®−îc gäi lµ mét
quan hÖ t−¬ng ®−¬ng. Quan hÖ t−¬ng ®−¬ng R sÏ chia (ph©n ho¹ch) tËp tæng thÓ
U thµnh c¸c líp t−¬ng ®−¬ng. Líp t−¬ng ®−¬ng cña phÇn tö x ∈ U, kÝ hiÖu lµ [x],
chøa tÊt c¶ c¸c ®èi t−îng y ∈ U mµ xRy.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-12-
Nh− ®· ®−îc ®Ò cËp trong phÇn tr−íc, lý thuyÕt tËp th« quan t©m ®Õn quan hÖ
kh«ng ph©n biÖt ®−îc [5, 9, 10]. Cho hÖ th«ng tin A = (U, A), quan hÖ kh«ng
ph©n biÖt ®−îc ®−îc tr×nh bµy nh− d−íi ®©y.
§Þnh nghÜa 1.3. Víi tËp con bÊt kú B ⊆ A, tån t¹i mét quan hÖ t−¬ng ®−¬ng (kÝ
hiÖu lµ INDA(B)) ®−îc x¸c ®Þnh nh− sau:
INDA(B)={(x,x’) ∈ U2 ⏐∀a ∈ B: a(x) = a(x’)}
INDA(B) ®−îc gäi lµ quan hÖ kh«ng ph©n biÖt ®−îc theo nghÜa nÕu nh− hai ®èi
t−îng x, x' mµ (x,x’) ∈ INDA(B) th× x vµ x’ lµ kh«ng ph©n biÖt ®−îc lÉn nhau bëi
c¸c thuéc tÝnh trong B.
TÝnh chÊt t−¬ng ®−¬ng cña INDA(B) lµ dÔ dµng kiÓm tra theo ®Þnh nghÜa. Trong
nhiÒu tr−êng hîp khi hÖ th«ng tin ®· hoµn toµn x¸c ®Þnh, ta dïng c¸ch viÕt
IND(B) hay IND thay cho c¸ch viÕt INDA(B) vµ còng dïng c¸ch nãi lµ tÝnh
kh«ng ph©n biÖt ®−îc theo B.
Líp t−¬ng ®−¬ng theo quan hÖ kh«ng ph©n biÖt ®−îc B ®−îc biÓu diÕn lµ [x]B. Ký
tù A trong quan hÖ kh«ng ph©n biÖt ®−îc th−êng bÞ bá qua nÕu nã ®· râ rµng
trong hÖ th«ng tin.
• VÝ dô. XÐt b¶ng 2 minh ho¹ cho mét quan hÖ kh«ng ph©n biÖt ®−îc. NÕu
kh«ng xem xÐt thuéc tÝnh t«n gi¸o th× c¸c tËp con kh¸c rçng cña c¸c thuéc
tÝnh ®iÒu kiÖn lµ {Tíi n−íc}, {N¬i sinh} vµ {Tíi n−íc, N¬i sinh}. Xem xÐt
thuéc tÝnh {Tíi n−íc}, c¸c ®èi t−îng x3 vµ x4 thuéc vµo cïng mét líp t−¬ng
®−¬ng vµ kh«ng cã kh¶ n¨ng ph©n biÖt ®−îc. Ba quan hÖ IND x¸c ®Þnh ph©n
ho¹ch thµnh tõng phÇn tËp tæng thÓ.
IND({Tíi n−íc}) = {{x1,x2,x6},{x3,x4,x7},{x5 }}
IND({N¬i sinh}) = {{x1},{x2},{x3,x4},{x5,x6,x7}}
IND({Tíi n−íc, N¬i sinh}) = {{x1},{x2},{x3,x4},{x5},{ x6},{x7}}
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-13-
I.1.1.4. TËp m« t¶ ®−îc vµ ng«n ng÷ m« t¶ tËp
Z. Pawlak ®· ®−a ra kh¸i niÖm tËp m« t¶ ®−îc [1] trong hÖ th«ng tin
A = (U, A). XÐt R lµ quan hÖ kh«ng ph©n biÖt ®−îc víi tr−êng hîp ®Æc biÖt khi
B = A gåm tÊt c¶ c¸c thuéc tÝnh. Líp t−¬ng ®−¬ng theo quan hÖ R ®−îc gäi lµ tËp
s¬ cÊp [1,9] vµ gäi E lµ tËp hîp c¸c tËp s¬ cÊp. T−¬ng øng víi quan hÖ R, Pawlak
®−a ra kh¸i niÖm h¹ng thøc (term) trong ng«n ng÷ L dïng ®Ó m« t¶ c¸c tËp trong
hÖ th«ng tin [1]. Ng«n ng÷ L bao gåm hai néi dung: h¹ng thøc (term) trong ng«n
ng÷ ®ã vµ ng÷ nghÜa cña mét h¹ng thøc ®−îc x¸c ®Þnh nh− d−íi ®©y.
§Þnh nghÜa 1.4. [1, 9] H¹ng thøc thuéc L ®−îc ®Þnh nghÜa ®Ö quy nh− sau:
(1) 0 vµ 1 lµ c¸c h¹ng thøc (h¹ng thøc h»ng),
(2) NÕu a ∈ A vµ v ∈ Va th× (a,v) lµ mét h¹ng thøc,
(3) NÕu t, t1, t2 lµ c¸c h¹ng thøc th× t , t1∨t2, t1 ∧ t1 còng lµ c¸c h¹ng thøc.
§Þnh nghÜa 1.5. [1, 9] H¹ng thøc t cã ng÷ nghÜa σ (t) th«ng qua ¸nh x¹ σ tõ L
vµo 2U (tËp c¸c tËp con cña U) ®−îc x¸c ®Þnh nh− sau:
(1) σ (0) = ∅ vµ σ (1) = U
(2) σ ((a,v)) = { x ∈ U : a(x)=v}
(3) σ ( t ) = U - σ (t) ; σ (t1∨t2) = σ (t1) ∪ σ (t2) ; σ (t1∧t2) = σ (t1) ∩ σ (t2)
H¹ng thøc d¹ng t =/\a∈A(a,va) ®−îc gäi lµ h¹ng thøc d¹ng chuÈn. Tån t¹i c¸c
h¹ng thøc d¹ng chuÈn nh−ng cã ng÷ nghÜa rçng. Gäi LNF lµ tËp hîp c¸c h¹ng
thøc d¹ng chuÈn cã ng÷ nghÜa kh¸c rçng. C¸c kÕt qu¶ sau ®©y ®· ®−îc kh¼ng
®Þnh trong [1].
MÖnh ®Ò 1.1. Tån t¹i sù t−¬ng øng 1-1 gi÷a tËp E c¸c tËp s¬ cÊp víi tËp c¸c h¹ng
thøc d¹ng chuÈn cã ng÷ nghÜa kh¸c rçng LNF theo nghÜa d−íi ®©y:
(1) Víi bÊt kú e ∈ E, tån t¹i duy nhÊt h¹ng thøc t ∈ LNF sao cho σ (t) = e,
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-14-
(2) Víi bÊt kú h¹ng thøc t trong LNF th× e =σ (t) lµ tËp s¬ cÊp.
Th«ng qua hÖ th«ng tin vµ ng«n ng÷ L chóng ta cã thÓ "m« t¶" ®−îc c¸c tËp con
c¸c ®èi t−îng. Pawlak ®· ®−a ra kh¸i niÖm vÒ tËp m« t¶ ®−îc trong hÖ th«ng tin
nh− ®Þnh nghÜa d−íi ®©y.
§Þnh nghÜa 1.6. Mét tËp con X kh¸c rçng c¸c ®èi t−îng ®−îc gäi lµ tËp m« t¶
®−îc khi vµ chØ khi X lµ hîp cña c¸c tËp s¬ cÊp trong hÖ th«ng tin (Tr−êng hîp
®Æc biÖt lµ tËp rçng còng ®−îc coi lµ mét tËp m« t¶ ®−îc).
MÖnh ®Ò d−íi ®©y lµ kÕt qu¶ suy suy diÔn tõ mÖnh ®Ò 1.1. vµ ®Þnh nghÜa 1.6.
MÖnh ®Ò 1.2. TËp X lµ m« t¶ ®−îc khi vµ chØ khi tån t¹i mét h¹ng thøc t trong L
®Ó cho σ(t) = X.
MÖnh ®Ò 1.2 cho thÊy ý nghÜa cña kh¸i niÖm "m« t¶ ®−îc" cña tËp X lµ chóng ta
cã thÓ dïng mét h¹ng thøc trong ng«n ng÷ L ®Ó "m« t¶" tËp X ®ã.
Theo c¸c ®Þnh nghÜa vµ mÖnh ®Ò trªn ®©y th× kh«ng ph¶i tËp con nµo cña U còng
lµ tËp m« t¶ ®−îc, cã nghÜa lµ tån t¹i c¸c tËp con c¸c ®èi t−îng kh«ng lµ tËp m«
t¶ ®−îc. Kh¸i niÖm tËp th« ®−îc Pawlak ®Ò xuÊt ®−îc dïng ®Ó chØ dÉn ®Õn c¸c
tËp nh− thÕ vµ ®· më ra mét m« h×nh øng dông rÊt réng r·i trong lÜnh vùc khai
ph¸ d÷ liÖu vµ kh¸m ph¸ tri thøc trong c¬ së d÷ liÖu [1,4,5,9,10].
I.1.2. TËp th« trong kh«ng gian xÊp xØ
I.1.2.1. TËp xÊp xØ trªn, xÊp xØ d−íi vµ miÒn biªn
Mét quan hÖ t−¬ng ®−¬ng cho mét c¸ch ph©n ho¹ch tËp c¸c ®èi t−îng (tËp
tæng thÓ), trong ®ã mçi líp t−¬ng ®−¬ng ®−îc gäi lµ mét tËp s¬ cÊp vµ theo ®Þnh
nghÜa 1.6, chóng ta cã c¸c tËp m« t¶ ®−îc. VÊn ®Ò ®Æt ra lµ h·y t×m ph−¬ng ph¸p
sö dông ph©n ho¹ch ®· cho tõ mét quan hÖ t−¬ng ®−¬ng ®Ó "m« t¶" c¸c tËp con
®èi t−îng mµ kh«ng ph¶i lµ tËp m« t¶ ®−îc.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-15-
§èi s¸nh víi b¶ng quyÕt ®Þnh, chóng ta chó ý tíi quan hÖ kh«ng ph©n biÖt
®−îc INDA(B) t−¬ng øng víi tËp c¸c thuéc tÝnh ®iÒu kiÖn B (B ⊆ A), quan hÖ nµy
ph©n ho¹ch tËp ®èi t−îng thµnh c¸c líp t−¬ng ®−¬ng [x]B. Gäi X lµ tËp conc¸c
®èi t−îng cã cïng gi¸ trÞ t¹i thuéc tÝnh quyÕt ®Þnh d. Trong nhiÒu tr−êng hîp, tËp
X nh− vËy kh«ng lµ m« t¶ ®−îc bëi v× tån t¹i c¸c líp t−¬ng ®−¬ng [x]B bao gåm
c¶ c¸c phÇn tö thuéc X vµ c¶ c¸c phÇn tö kh«ng thuéc X.
VÝ dô, cho b¶ng quyÕt ®Þnh trong b¶ng 2 vµ lÊy tËp B lµ tËp c¸c thuéc tÝnh ®iÒu
kiÖn, tËp X bao gåm c¸c ®èi t−îng cÇn xem xÐt khi cho xuÊt, nhËp c¶nh. XÐt líp
t−¬ng ®−¬ng ®−¬ng chøa hai ®èi t−îng x3 vµ x4, chóng cã cïng gi¸ trÞ trªn tËp
thuéc tÝnh ®iÒu kiÖn nh−ng gi¸ trÞ trªn thuéc tÝnh quyÕt ®Þnh l¹i kh¸c nhau, cã
nghÜa lµ tËp X ®ang xÐt kh«ng ph¶i lµ tËp m« t¶ ®−îc.
Trong ®Þnh nghÜa 1.6 vÒ tËp m« t¶ ®−îc chóng ta xem xÐt tËp X víi c¸c líp t−¬ng
®−¬ng sinh ra do quan hÖ INDA(B). Ph¸t triÓn viÖc ®èi s¸nh ®ã, ý t−ëng vÒ tËp
th« ®· ®−îc n¶y sinh. Tuy r»ng, chóng ta kh«ng thÓ x¸c ®Þnh tÝnh chÊt ®Ó m« t¶
tËp X (nh÷ng kh¸ch cÇn xem xÐt khi XuÊt NhËp C¶nh) mét c¸ch chÝnh x¸c vµ râ
rµng (kh«ng m« t¶ ®−îc tËp nµy), nh−ng l¹i cã thÓ "m« t¶" ®−îc tËp c¸c kh¸ch
ch¾c ch¾n cÇn ph¶i xem xÐt (tËp {x1, x6}) hoÆc tËp c¸c kh¸ch XuÊt NhËp C¶nh
cã kh¶ n¨ng cÇn ph¶i xem xÐt (tËp {x1, x3, x4, x6}) vµ cuèi cïng lµ tËp c¸c
kh¸ch XuÊt NhËp C¶nh thuéc vïng ranh giíi gi÷a c¸c tr−êng hîp ch¾c ch¾n vµ
kh¶ n¨ng (tËp {x3, x4}). NÕu vïng biªn nµy kh«ng rçng th× tËp nµy ®−îc gäi lµ
tËp th«. H×nh thøc hãa ý t−ëng nµy ®−îc diÔn t¶ nh− d−íi ®©y.
§Þnh nghÜa 1.7. Gi¶ sö A = (U, A) lµ mét hÖ th«ng tin vµ B ⊆ A vµ X ⊆ U. C¸c
tËp xÊp xØ cña X theo th«ng tin cã tõ B, ®−îc x¸c ®Þnh nh− d−íi ®©y:
(1) TËp B-xÊp xØ d−íi cña X, kÝ hiÖu lµ B X , lµ tËp B X = {x | [x]B ⊆ X}
(2) TËp B-xÊp xØ trªn cña X, kÝ hiÖu lµ B X , lµ tËp B X = {x | [x]B ∩ X ≠ ∅}.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-16-
§èi t−îng trong B X ch¾c ch¾n ®−îc ph©n líp lµ thµnh viªn cña X theo tri thøc c¬
së tõ B (tËp B X cã thÓ ®−îc gäi lµ tËp ch¾c ch¾n), trong khi ®èi t−îng trong
B X chØ cã kh¶ n¨ng ®−îc ph©n líp lµ thµnh viªn cña X theo tri thøc c¬ së trong B
(tËp B X cã thÓ ®−îc gäi lµ tËp kh¶ n¨ng). TËp BNB(X) = B X - B X ®−îc gäi lµ
B-vïng biªn cña X, do vËy chóng ta kh«ng thÓ ph©n lo¹i (vµ còng kh«ng thÓ lo¹i
bá) c¸c ®èi t−îng trong tËp ®ã vµo trong X trªn tri thøc c¬ së trong B. TËp U -
B X ®−îc gäi lµ B-vïng ngoµi cña X bao gåm c¸c ®èi t−îng ch¾c ch¾n kh«ng
thuéc X (trªn tri thøc c¬ së cã ®−îc tõ B1). Mét tËp ®−îc gäi lµ th« hoµn toµn nÕu
vïng biªn cña nã lµ kh«ng rçng.
a) VÝ dô
Tr−êng hîp chung nhÊt lµ ®Ó tæng hîp x¸c ®Þnh kÕt qu¶ (hay líp quyÕt ®Þnh)
trong c¸c thuéc tÝnh ®iÒu kiÖn. Gi¶ sö W={x | Xem xÐt(x) = CÊm} nh− vÝ dô minh
{{x2}, {x5, x7}}
{{x3, x4}
CÊm
{{x1}, {x6}}
CÊm/Kh«ng
Kh«ng
H×nh 1. XÊp xØ tËp kh¸ch cÇn xem xÐt khi XuÊt NhËp C¶nh, sö dông 2 thuéc
tÝnh ®iÒu kiÖn Tíi n−íc vµ N¬i sinh.
1
Ký tù B ®−îc xem lµ tËp con B cña c¸c thuéc tÝnh trong A. NÕu mét tËp con kh¸c ®−îc chän vÝ dô nh− F ⊆ A th×
còng cã c¸c kh¸i niÖm nh−: F-vïng biªn, F-xÊp xØ trªn vµ F-xÊp xØ d−íi.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-17-
ho¹ trªn b¶ng 2. Ta thu ®−îc vïng xÊp xØ d−íi AW = {x1,x6}, xÊp xØ trªn AW =
{x1,x3,x4,x6}, vïng biªn BNA(W)={ x3,x4} vµ vïng biªn ngoµi U - AW = {x2,x5,x7}.
Do ®ã mµ tËp kÕt qu¶ Xem xÐt lµ th« v× vïng biªn lµ kh«ng rçng.
b) C¸c tÝnh chÊt cña sù xÊp xØ.
Trong [9, 10] ®· tr×nh bµy c¸c tÝnh chÊt sau ®©y vÒ tËp xÊp xØ:
(1) B X ⊆ X ⊆ B X ,
(2) B (∅) = B (∅), B (U) = B (U) = U,
(3) B (X ∪ Y) = B (X) ∪ B (Y),
(4) B ( X ∩ Y) = B (X) ∩ B (Y),
(5) NÕu X ⊆Y th× B (X) ⊆ B (Y) vµ B (X) ⊆ B (Y),
(6) B ( X ∪ Y) ⊇ B (X) ∪ B (Y),
(7) B (X ∩Y) ⊆ B (X) ∩ B (Y),
(8) B (-X) = - B (X),
(9) B (-X) = - B (X),
(10)
B ( B (X)) = B ( B (X)) = B (X),
(11)
B ( B (X)) = B ( B (X)) = B (X),
Trong ®ã ký hiÖu -X biÓu thÞ cho U-X.
Cã thÓ nhËn thÊy lµ tËp xÊp xØ trªn vµ xÊp xØ d−íi cña mét tËp cã vÎ ngoµi t−¬ng
®ång víi phÇn trong vµ bao ®ãng cña tËp hîp trong t«p« h×nh häc ®−îc sinh ra
bëi quan hÖ kh«ng ph©n biÖt ®−îc.
c) Bèn lo¹i tËp th« c¬ b¶n
Ng−êi ta ph©n tËp th« thµnh 4 lo¹i [9]:
• X x¸c ®Þnh th« thùc sù theo B nÕu B X ≠ ∅ vµ B X ≠ U,
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-18-
• X lµ kh«ng x¸c ®Þnh bªn trong theo B nÕu B X = ∅ vµ B X ≠ U,
• X lµ kh«ng x¸c ®Þnh bªn ngoµi theo B nÕu B X ≠ ∅ vµ B X = U,
• X lµ kh«ng x¸c ®Þnh thùc sù theo B nÕu B X = ∅ vµ B X = U.
Gi¶i thÝch b»ng trùc gi¸c th× sù ph©n líp nµy cã nghÜa nh− sau:
• NÕu X x¸c ®Þnh th« thùc sù theo B nghÜa lµ chóng ta cã thÓ quyÕt ®Þnh r»ng
mét sè thµnh phÇn cña U mµ chóng thuéc X vµ cho mét sè phÇn tö cña U mµ
chóng thuéc -X, sö dông B.
• NÕu X lµ kh«ng x¸c ®Þnh néi t¹i bªn trong theo B cã nghÜa lµ chóng ta cã thÓ
quyÕt ®Þnh r»ng mét sè phÇn tö cña U mµ chóng thuéc -X nh−ng kh«ng thÓ
quyÕt ®Þnh cho bÊt kú phÇn tö cña U nµo cã thuéc X kh«ng, sö dông B.
• NÕu X lµ kh«ng x¸c ®Þnh bªn ngoµi theo B cã nghÜa lµ chóng ta cã thÓ quyÕt
®Þnh r»ng mét sè phÇn tö cña U mµ chóng thuéc X nh−ng kh«ng thÓ quyÕt
®Þnh cho bÊt kú phÇn tö cña U nµo cã thuéc X kh«ng, sö dông B.
• NÕu X lµ kh«ng x¸c ®Þnh thùc sù theo B cã nghÜa lµ chóng ta quyÕt ®Þnh r»ng
bÊt kú phÇn tö cña U cã thuéc X hay -X kh«ng, sö dông B.
d) §é ®o liªn quan biªn xÊp xØ
TËp th« ®−îc chØ sè ho¸ bëi hÖ sè sau:
α B (X ) =
B( X )
,
B( X )
α B (X ) ®−îc gäi lµ ®é ®o liªn quan biªn xÊp xØ cña X, víi X biÓu diÔn lùc l−îng
cña X ≠ ∅. Cã thÓ thÊy ®−îc 0 ≤ α B ( X ) ≤ 1 . NÕu α B ( X ) =1 th× X ®óng hoµn toµn
®èi víi B, ng−îc l¹i nÕu α B ( X ) <1 th× X lµ th« ®èi víi B.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
-19-
I.1.2.2. Hµm th« vµ mét sè ®é ®o phô thuéc cã liªn quan
Trong lý thuyÕt tËp hîp cæ ®iÓn, mçi thµnh viªn thuéc mét tËp hîp hoÆc
kh«ng. Hµm thµnh viªn (hµm thuéc) lµ hµm ®Æc tr−ng cña tËp hîp nhËn mét
trong hai gi¸ trÞ 0 vµ 1. Trong tËp th«, ý t−ëng cña hµm thµnh viªn th× kh¸c. Hµm
thµnh viªn th« x¸c ®Þnh møc ®é giao nhau liªn quan gi÷a tËp X vµ líp t−¬ng
®−¬ng [x]B chøa x, nã ®−îc ®Þnh nghÜa nh− sau:
µ XB : U → [0,1] vµ ®−îc x¸c ®Þnh µ XB ( x) =
[x]B ∩ X
[x]B
Hµm th« cã thÓ ®−îc hiÓu nh− mét sù −íc l−îng tÇn sè c¬ b¶n cña Pr(x ∈ X ⏐x,
B) (x¸c xuÊt ®iÒu kiÖn mµ ®èi t−îng x thuéc tËp X), víi líp t−¬ng ®−¬ng IND(B).
C¸c c«ng thøc cho tËp xÊp xØ trªn vµ xÊp xØ d−íi cã thÓ ®−îc suy ra tõ hµm th«
víi møc chÝnh x¸c tuú ý π ∈ ⎛⎜ ,1⎤⎥ [10] nh− sau:
⎝2 ⎦
1
{
}
B π X = {x µ XB ( x)〉1 − π }
B π X = x µ XB ( x) ≥ π
Tr−êng hîp ®Æc biÖt π = 1.0
C¸c kh¸i niÖm vÒ sù xÊp xØ ®−îc x©y dùng dùa trªn tri thøc nÒn c¬ b¶n. Cã
thÓ thÊy r»ng c¸c kh¸i niÖm nµy liªn quan ®Õn c¸c ®èi t−îng (Èn) kh«ng nh×n
thÊy. Do ®ã nã rÊt h÷u Ých ®Ó x¸c ®Þnh sù xÊp xØ biÓu hiÖn b»ng tham sè víi c¸c
tham sè phï hîp trong qu¸ tr×nh t×m kiÕm cho c¸c kh¸i niÖm tõ sù xÊp xØ tËp. ý
t−ëng nµy lµ chñ ®¹o cho viÖc x©y dùng c¸c kh¸i niÖm vÒ sù xÊp xØ sö dông
ph−¬ng ph¸p tËp th«.
Khai ph¸ luËt theo tiÕp cËn tËp th«
Tiªu ThÞ Dù
- Xem thêm -