Luận văn Phát hiện luật theo tiếp cận tập thô

 Luận văn tốt nghiệp Phát hiện luật theo tiếp cận tập thô -1- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù Mô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 ................................................................................... 29 Ch−¬ng II. Kh¸m ph¸ luËt theo tiÕp cËn tËp th« vµ ®èi -2- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù s¸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 -3- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù III.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 -4- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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 -5- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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 ý -6- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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. -7- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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ý. -8- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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. -9- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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. Tíi n−íc N¬i sinh T«n gi¸o x1 Mü Hµ néi Cã x2 Mü H¶i phßng Cã x3 Ph¸p Sµi gßn Kh«ng x4 Ph¸p Sµi gßn Kh«ng x5 §øc §µ n½ng Cã x6 Mü §µ n½ng Kh«ng x7 Ph¸p §µ n½ng Kh«ng B¶ng 1. Mét vÝ dô vÒ hÖ th«ng tin -10- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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 Tíi n−íc N¬i sinh T«n gi¸o Xem xÐt x1 Mü Hµ néi Cã CÊm x2 Mü H¶i phßng Cã Kh«ng x3 Ph¸p Sµi gßn Kh«ng Kh«ng x4 Ph¸p Sµi gßn Kh«ng CÊm x5 §øc §µ n½ng Cã Kh«ng x6 Mü §µ n½ng Kh«ng CÊm x7 Ph¸p §µ n½ng Kh«ng Kh«ng B¶ng 2. CXN - Mét b¶ng quyÕt ®Þnh -11- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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. -12- Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù 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