Tài liệu Luận văn thạc sĩ lý thuyết tập mờ và ứng dụng trong phân lớp dữ liệu

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