Đăng ký Đăng nhập
Trang chủ Phát hiện luật theo tiếp cận tập thô...

Tài liệu Phát hiện luật theo tiếp cận tập thô

.PDF
88
101
142

Mô tả:

 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 -

Tài liệu liên quan