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

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST

Báo xấu

74
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sự phát triển mạnh mẽ của công nghệ phần cứng đã tạo nên các máy tính có bộ xử lý tốc độ cao, bộ nhớ dung l−ợng lớn vμ cùng với điều đó, lμ sự phát triển không ngừng các hệ thống mạng viễn thông. Từ các kết quả đó, nhiều hệ thống thông tin phục vụ việc tự động hóa mọi hoạt động

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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- 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 HÖ th«ng tin vµ tËp th«............................................................................ 9 I.1. 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 20 I.2. Kh¸m ph¸ tri thøc theo tiÕp cËn tËp th« .............................................. 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 29 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ù
-2- 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 Khai ph¸ luËt theo tiÕp cËn tËp th« Tiªu ThÞ Dù
-3- 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 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¶ HÖ th«ng tin hay b¶ng quyÕt ®Þnh A 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. Tíi n−íc N¬i sinh T«n gi¸o Mü Hµ néi Cã x1 Mü H¶i phßng Cã x2 Ph¸p Sµi gßn Kh«ng x3 Ph¸p Sµi gßn Kh«ng x4 §øc §µ n½ng Cã x5 Mü §µ n½ng Kh«ng x6 Ph¸p §µ n½ng Kh«ng x7 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 Tíi n−íc N¬i sinh T«n gi¸o Xem xÐt Mü Hµ néi Cã CÊm x1 Mü H¶i phßng Cã Kh«ng x2 Ph¸p Sµi gßn Kh«ng Kh«ng x3 Ph¸p Sµi gßn Kh«ng CÊm x4 §øc §µ n½ng Cã Kh«ng x5 Mü §µ n½ng Kh«ng CÊm x6 Ph¸p §µ n½ng Kh«ng Kh«ng x7 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. 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× 1 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), B ( B (X)) = B ( B (X)) = B (X), (10) B ( B (X)) = B ( B (X)) = B (X), (11) 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 )
-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: [x]B ∩ X µ X : U → [0,1] vµ ®−îc x¸c ®Þnh µ X ( x) = B B [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: 1 ⎜⎥ ⎝2 ⎦ { } B π X = x µ X ( x) ≥ π B B π X = {x µ X ( x)〉1 − π } B 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ù