intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Báo cáo nghiên cứu khoa học: "Một số phép toán trên hệ biểu diễn tri thức dựa theo triết lý tập thô.."

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:7

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

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của trường đại học vinh năm 2008 tác giả: 9.Cao Thanh Sơn, Phan Anh Phong, Nguyễn Quang Khanh, Một số phép toán trên hệ biểu diễn tri thức dựa theo triết lý tập thô... Khoa học (trong tiếng Latin scientia, có nghĩa là "kiến thức" hoặc "hiểu biết") là các nỗ lực thực hiện phát minh, và tăng lượng tri thức hiểu biết của con người về cách thức hoạt động của thế giới vật chất xung quanh. Thông qua các phương pháp kiểm soát, nhà khoa học sử...

Chủ đề:
Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Một số phép toán trên hệ biểu diễn tri thức dựa theo triết lý tập thô.."

  1. T¹p chÝ khoa häc, tËp XXXVII, sè 1A-2008 §¹i häc Vinh Mét sè phÐp to¸n trªn hÖ biÓu diÔn tri thøc Dùa theo triÕt lý TËP TH¤ Cao Thanh S¬n (a), Phan Anh Phong , NguyÔn Quang Khanh (a) (b) Tãm t¾t. Trong bµi b¸o nµy, chóng t«i giíi thiÖu ph−¬ng ph¸p biÓu diÔn tri thøc cña mét nhãm t¸c nh©n t vÒ mét tËp c¸c ®èi t−îng, mét sè to¸n tö tri thøc cïng víi c¸c tÝnh chÊt cña chóng vµ x©y dùng mét sè phÐp to¸n trªn hÖ tri thøc biÓu diÔn theo triÕt lý tËp th«. I. më ®Çu Lý thuyÕt tËp th« lÇn ®Çu tiªn ®−îc ®Ò xuÊt bëi Gi¸o s− ng−êi Ba Lan Z.Pawlak vµo ®Çu thËp niªn 1980 vµ nhanh chãng trë thµnh mét c¸ch tiÕp cËn nh»m xö lý th«ng tin m¬ hå, th«ng tin kh«ng ch¾c ch¾n. Nã cung cÊp c«ng cô ®Ó ph©n tÝch, suy diÔn trªn d÷ liÖu kh«ng chÝnh x¸c vµ ph¸t hiÖn ra mèi quan hÖ gi÷a c¸c ®èi t−îng, tri thøc tiÒm Èn trong d÷ liÖu ([5, 6]). Môc tiªu chÝnh cña biÓu diÔn tri thøc trong m¸y tÝnh lµ phôc vô cho viÖc thu nhËn tri thøc vµo m¸y tÝnh, truy xuÊt chóng vµ thùc hiÖn c¸c phÐp suy luËn dùa trªn nh÷ng tri thøc ®· l−u tr÷. HiÖn ®· cã nhiÒu ph−¬ng ph¸p biÓu diÔn tri thøc nh−: sö dông logic h×nh thøc, luËt dÉn xuÊt, m¹ng ng÷ nghÜa, biÓu diÔn b»ng frame, b»ng script ([1]), biÓu diÔn theo tiÕp cËn tËp th« ([3]). Mçi ph−¬ng ph¸p trªn ®Òu cã nh÷ng −u ®iÓm, nh−îc ®iÓm riªng. Bµi b¸o nµy, chóng t«i dùa theo c¸ch biÓu diÔn tri thøc trong ([3]) ®Ó ®−a ra mét sè phÐp to¸n trªn hÖ tri thøc. Sau phÇn më ®Çu, phÇn 2 tr×nh bµy c¸c kiÕn thøc c¬ b¶n vÒ lý thuyÕt tËp th«. PhÇn 3 giíi thiÖu s¬ l−îc ph−¬ng ph¸p biÓu diÔn tri thøc theo lý thuyÕt tËp th« vµ mét sè tÝnh chÊt cña c¸c to¸n tö tri thøc It, Kt. Trong phÇn 4, chóng t«i x©y dùng mét sè phÐp to¸n míi, phÐp hîp, phÐp giao vµ phÐp so s¸nh trªn hÖ tri thøc ®−îc biÓu diÔn theo ([3]) vµ cuèi cïng lµ kÕt luËn cña bµi b¸o. II. Lý thuyÕt tËp th« Cho U lµ mét tËp bÊt kú, R lµ quan hÖ t−¬ng ®−¬ng trªn U. Khi ®ã U/R lµ ph©n ho¹ch c¸c líp t−¬ng ®−¬ng. Gi¶ sö X ⊆ U. 2.1. §Þnh nghÜa ([4]). §Þnh nghÜa xÊp xØ cña tËp X trong kh«ng gian U. XÊp xØ trªn cña X t−¬ng øng víi R trong kh«ng gian U, ký hiÖu XR (hoÆc X R ) lµ XR = ∪ {Ei ∈ U/R: Ei ∩ X ≠ ∅}. XÊp xØ d−íi cña X t−¬ng øng víi R trong kh«ng gian U, ký hiÖu XR (hoÆc XR) lµ XR = ∪ {Ei ∈ U/R: Ei ⊆ X}. Gäi BN(R, X) = XR − XR lµ vïng biªn cña X øng víi R. Gäi α R = card(XR)/card(XR) lµ ®é chÝnh x¸c cña xÊp xØ X øng víi R, víi card(X) lµ sè X phÇn tö trong X. NhËn bµi ngµy 19/12/2007. Söa ch÷a xong 07/3/2008. 57
  2. C. T. S¬n, P. A. Phong, N. Q. Khanh Mét sè ... theo triÕt lý TËP TH¤, tr. 57-63 2.2. §Þnh nghÜa ([5]). §Þnh nghÜa tËp th« TËp X ®−îc gäi lµ th« t−¬ng øng víi quan hÖ R nÕu BN(R, X) ≠ ∅. TËp X ®−îc gäi lµ râ t−¬ng øng víi quan hÖ R nÕu BN(R, X) = ∅. Nãi c¸ch kh¸c: TËp X ®−îc gäi lµ th« t−¬ng øng víi quan hÖ R nÕu XR ≠ XR. TËp X ®−îc gäi lµ râ t−¬ng øng víi quan hÖ R nÕu XR = XR. HoÆc: TËp X ®−îc gäi lµ th« t−¬ng øng víi quan hÖ R nÕu α R < 1 . X TËp X ®−îc gäi lµ râ t−¬ng øng víi quan hÖ R nÕu α R = 1 . X 2.3. NhËn xÐt. Kh¸i niÖm tËp th« lu«n g¾n víi ph©n ho¹ch cña tËp U. Cïng mét kh«ng gian U nÕu thay ®æi ph©n ho¹ch th× X cã thÓ th« t−¬ng øng víi ph©n ho¹ch nµy nh−ng l¹i râ t−¬ng øng víi ph©n ho¹ch kh¸c. 2.4. VÝ dô. 1 5 9 a b c 2 6 10 k m d 3 7 11 i n e 4 8 12 h g f H×nh 1. H×nh minh häa tËp xÊp xØ Gi¶ sö quan hÖ t−¬ng ®−¬ng R ph©n ho¹ch U thµnh 24 líp vµ X ⊆ U ®−îc minh ho¹ theo h×nh Elips (xem h×nh 1). Khi ®ã: XÊp xØ d−íi: XR = m ∪ n (2 h×nh t« ®Ëm trong Elips). XÊp xØ trªn: XR = hîp cña c¸c líp a, b, c, d, e, f, g, h, i, k vµ XR, tøc lµ: X R = a ∪ b ∪ c ∪ d ∪ e ∪ f ∪ g ∪ h ∪ i ∪ k ∪ X R, BN(R, X) = XR − XR, α R = card(XR)/card(XR) = 2/12 = 1/6. X Theo ®Þnh nghÜa 2.2 th× X lµ tËp th« t−¬ng øng víi quan hÖ R. 2.5. §Þnh nghÜa ([3]). HÖ tin lµ cÆp S = (U, A), trong ®ã: U lµ tËp h÷u h¹n kh¸c rçng c¸c ®èi t−îng, A lµ tËp h÷u h¹n kh¸c rçng c¸c thuéc tÝnh sao cho víi mçi thuéc tÝnh a ∈ A, a cã miÒn gi¸ trÞ Va. Ký hiÖu: a:U → Va, ∀a ∈ A. HÖ quyÕt ®Þnh lµ hÖ tin bÊt kú cã d¹ng: S = (U, A ∪ {d}), trong ®ã: A lµ tËp thuéc tÝnh ®iÒu kiÖn, d ∉ A lµ tËp thuéc tÝnh quyÕt ®Þnh. 2.6. §Þnh nghÜa ([3]). Cho hÖ tin S = (U, A) vµ 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: 58
  3. T¹p chÝ khoa häc, tËp XXXVII, sè 1A-2008 §¹i häc Vinh indA(B) = {(x, y) ∈ U × U: ∀a ∈ B, a(x) = a(y)} indA(B) hoÆc cã thÓ ký hiÖu ind(B) ®−îc gäi lµ quan hÖ kh«ng ph©n biÖt ®−îc, nghÜa lµ nÕu cã hai ®èi t−îng x vµ y mµ (x, y) ∈ ind(B) th× x vµ y kh«ng thÓ ph©n biÖt ®−îc bëi c¸c thuéc tÝnh trong B. Ký hiÖu [x]B lµ líp t−¬ng ®−¬ng theo quan hÖ ind(B). III. BiÓu diÔn tri thøc theo triÕt lý tËp th« Tri thøc cña mét ng−êi hay mét nhãm ng−êi t (gäi lµ t¸c nh©n t) vÒ mét tËp ®èi t−îng U={o1,o2,…,om} lµ c¸c th«ng tin mµ t biÕt vÒ U, t cµng biÕt nhiÒu vÒ U th× cµng cã kh¶ n¨ng ph©n biÖt c¸c ®èi t−îng trong U. NÕu lÊy hai ®èi t−îng bÊt kú oi, oj cña U mµ t kh«ng thÓ ph©n biÖt ®−îc chóng (dï lµ mét chi tiÕt nhá − thuéc tÝnh) th× t coi nh− cã tri thøc kÐm vÒ U. VËy cã thÓ nãi t biÕt tèt vÒ U nÕu t cã thÓ ph©n lo¹i chi tiÕt vÒ c¸c ®èi t−îng trong U. Coi mét ph©n ho¹ch cña U lµ mét tri thøc cña mét t¸c nh©n t nµo ®ã trªn tËp ®èi t−îng U. Tri thøc cña t vÒ U (hay tri thøc cña t trªn U), ký hiÖu Kt(U) lµ mét ph©n ho¹ch cña U: Kt(U) = {E1t, E2t, …, Emt}. Hai ph©n ho¹ch kh¸c nhau cña U ®−îc coi lµ hai tri thøc kh¸c nhau cña hai t¸c nh©n t vµ s ph©n biÖt. Nh− vËy Kt(U) = {E1t,E2t, …,Emt} vµ Ks(U)={E1s,E2s,…,Ems} lµ hai tri thøc kh¸c nhau cña t vµ s. Mét t¸c nh©n t kh«ng thÓ cã hai tri thøc kh¸c nhau trªn tËp U. Hä ε c¸c ph©n ho¹ch cña U lµ mét hÖ tri thøc trªn U. Ta cã thÓ x©y dùng c¸c phÐp to¸n kh¸c nhau trªn ε ®Ó nhËn ®−îc c¸c cÊu tróc kh¸c nhau. Th«ng th−êng, mét c¸ch tù nhiªn ®Ó nhËn biÕt vÒ tËp ®èi t−îng U ta th−êng xÐt chóng trong mét tËp c¸c tham sè (thuéc tÝnh) A = {A1, A2, …, An}. Nh− vËy mét tri thøc cña t¸c nh©n t vÒ tËp ®èi t−îng U lµ hÖ tin: St = (U, At) d¹ng b¶ng: … U A1 A2 An o1 . . . om Giao cña oi vµ Aj lµ gi¸ trÞ cho biÕt th«ng tin cña oi vÒ thuéc tÝnh Aj. Nh− vËy, tri thøc cña t vÒ U lµ Kt(U) = U/ind(At). L−u ý r»ng cø cã hÖ tin St=(U,At) th× x¸c ®Þnh ®−îc Kt(U)=U/ind(At) nªn cã thÓ nãi St=(U, At) lµ hÖ tri thøc cña t vÒ U. 3.1. §Þnh nghÜa ([3]). §Þnh nghÜa c¬ së tri thøc. Víi mçi B ⊆ At, hä c¸c líp t−¬ng ®−¬ng cña quan hÖ ind(B) lµ mét ph©n ho¹ch cña U. Ph©n ho¹ch ®−îc x¸c ®Þnh bëi tËp tÊt c¶ c¸c thuéc tÝnh At, khi ®ã hä 59
  4. C. T. S¬n, P. A. Phong, N. Q. Khanh Mét sè ... theo triÕt lý TËP TH¤, tr. 57-63 ε t = {[o1 ] At , [o2 ] At ,..., [on ] At } ®−îc gäi lµ c¬ së tri thøc cña t¸c nh©n t trªn vò trô U x¸c ®Þnh bëi St. 3.2. §Þnh nghÜa ([3]). §Þnh nghÜa tri thøc, tri thøc bé phËn. ∀X ⊆ U th× tËp It(X) ®−îc ®Þnh nghÜa nh− sau: Υ[o] It ( X ) = At [ o ] At ⊆ X It(X) ®−îc gäi lµ tri thøc bé phËn cña t¸c nh©n t vÒ X x¸c ®Þnh bëi St. Theo lý thuyÕt tËp th« th× It(X) lµ tËp xÊp xØ d−íi cña X. [6] Gäi −X lµ phÇn bï cña tËp X trong kh«ng gian nÒn U. It(−X) lµ tri thøc bé phËn cña t vÒ −X x¸c ®Þnh bëi St. Khi ®ã tri thøc cña t¸c nh©n t vÒ X cho bëi St, ký hiÖu Kt(X) lµ: Kt(X) = It(X) ∪ It(−X) 3.3. Mét sè tÝnh chÊt cña to¸n tö tri thøc It vµ Kt Gi¶ sö s vµ t lµ c¸c t¸c nh©n, s ≠ t. Ss vµ St lµ c¸c hÖ biÓu diÔn tri thøc t−¬ng øng vµ X ⊆ U, khi ®ã ta cã: (1). At ⊆ As It(X) ⊆ Is(X) ⇒ (2). IsIt(X) ⊆ Is(X) vµ IsIt(X) ⊆ It(X) (3). IsIt(X) ⊆ Is(X) ∩ It(X) (4). ItIs(X) = It(X) At ⊆ As ⇒ (5). Kt(X) ⊆ Ks(X) At ⊆ As ⇒ (6). Kt(X) = Kt(−X) (7). ItKt(X) = Kt(X) (8). KtKt(X) = U (9). Kt∅ = U (10). KtU = U (11). KtIt(X) = U (12). Kt(X) = U ⇔ It(X) = X IV. C¸c phÐp to¸n trªn hÖ tri thøc Sau ®©y, chóng t«i x©y dùng mét sè phÐp to¸n trªn c¸c hÖ tri thøc: phÐp hîp, phÐp giao vµ phÐp so s¸nh. 4.1. PhÐp hîp Cho hai hÖ tri thøc St vµ Ss t−¬ng øng víi c¸c t¸c nh©n t vµ s trªn tËp ®èi t−îng U = {o1,o2,…,on}, St=(U,At), Ss = (U,As). NÕu At ∩ As = B ≠ ∅ th× ∀a∈B, ∀o∈U, a(o) cã gi¸ trÞ nh− nhau trong St vµ Ss. PhÐp hîp hai hÖ tri thøc St vµ Ss ®−îc ký hiÖu St ∪ Ss lµ mét hÖ tri thøc ®−îc x¸c ®Þnh nh− sau: St ∪ Ss = (U, At ∪ As). Trong ®ã At ∪ As = {a: a ∈ At hoÆc a ∈ As}. 60
  5. T¹p chÝ khoa häc, tËp XXXVII, sè 1A-2008 §¹i häc Vinh KÕt qu¶ cña phÐp hîp gi÷a St vµ Ss ®−îc xem nh− lµ tri thøc kÕt nèi cña chóng. H¬n n÷a nã lµ mét ph©n ho¹ch cña U vµ cã thÓ ph©n biÖt tËp ®èi t−îng trong U tèt h¬n mçi t¸c nh©n. 4.2. VÝ dô. Cho 2 t¸c nh©n t, s nhËn U = {o1, o2, o3, o4, o5} nh− sau: U a b c U c d e 1 2 3 3 0 2 o1 o1 0 1 3 3 0 2 o2 o2 St= S s= 0 1 3 3 1 0 o3 o3 2 1 2 2 4 1 o4 o4 1 3 2 2 4 1 o5 o5 Tõ b¶ng trªn, ta cã: εt = {{o1}, {o2, o3}, {o4}, {o5}} vµ εs = {{o1, o2}, {o3}, {o4, o5}} Khi ®ã, St ∪ Ss ®−îc m« t¶ nh− sau: U a b c d e 1 2 3 0 2 o1 0 1 3 0 2 o2 St ∪ Ss= 0 1 3 1 0 o3 2 1 2 4 1 o4 1 3 2 4 1 o5 C¬ së tri thøc cña St ∪ Ss lµ mét ph©n ho¹ch ε = {{o1}, {o2}, {o3}, {o4}, {o5}} Nh− vËy, phÐp hîp hai tri thøc St ∪ Ss cña hai t¸c nh©n t vµ s cã thÓ nhËn ra c¸c ®èi t−îng trong U tèt h¬n mçi t¸c nh©n. Tr−êng hîp tæng qu¸t: S1 ∪ S2 ∪ … ∪ Sm = (U, A1 ∪ A2 ∪ … ∪ An) 4.3. PhÐp giao Cho hai hÖ tri thøc St vµ Ss t−¬ng øng víi c¸c t¸c nh©n t vµ s nh− trong môc 4.1. PhÐp giao hai tri thøc St vµ Ss ®−îc ký hiÖu St ∩ Ss lµ mét hÖ tri thøc ®−îc x¸c ®Þnh nh− sau: St ∩ Ss = (U, At ∩ As). Trong ®ã At ∩ As = {a: a ∈ At vµ a ∈ As}, At∩As≠∅. KÕt qu¶ cña phÐp giao ta ®−îc tri thøc chung cña St vµ Ss, lµ mét ph©n ho¹ch cña U. 4.4. VÝ dô. Cho 2 t¸c nh©n t, s nhËn U = {o1, o2, o3, o4, o5} nh− vÝ dô 4.2. Khi ®ã, St∩Ss ®−îc m« t¶ nh− sau: U c 3 o1 3 o2 St ∩ Ss= 3 o3 2 o4 2 o5 61
  6. C. T. S¬n, P. A. Phong, N. Q. Khanh Mét sè ... theo triÕt lý TËP TH¤, tr. 57-63 C¬ së tri thøc cña St ∩ Ss lµ mét ph©n ho¹ch gåm 2 líp ε = {[o1], [o4]} 4.5. PhÐp so s¸nh ∀s, t ∈ T, ®Ó so s¸nh tri thøc cña t¸c nh©n t vµ s, chóng ta x©y dùng phÐp to¸n (m¹nh h¬n) trªn tËp c¬ së tri thøc. Gi¶ sö εt vµ εs lµ hai c¬ së tri thøc t−¬ng øng cña hai hÖ tin St vµ Ss, khi ®ã phÐp to¸n ®−îc x¸c ®Þnh: εt εs ⇔ ∀[x]t ∃[y]s: [x]t ⊆ [y]s 4.6. VÝ dô. Cho hai t¸c nh©n t, s øng víi hai hÖ tri thøc St = (U, At) vµ Ss=(U,As), x¸c ®Þnh trªn kh«ng gian U = {o1, o2, o3, o4, o5} nh− sau: U a b c U c d e 1 2 3 3 1 2 o1 o1 0 1 3 3 0 2 o2 o2 St= Ss= 0 1 3 3 0 2 o3 o3 2 1 2 2 3 3 o4 o4 1 3 2 2 3 3 o5 o5 Dùa vµo c¸c b¶ng trªn, ta cã c¬ së tri thøc cña t¸c nh©n t vµ s t−¬ng øng: εt = {{o1}, {o2, o3}, {o4}, {o5}} εs = {{o1}, {o2, o3}, {o4, o5}} Tõ εt vµ εs, chóng ta thÊy ∀[x]t ∃[y]s: [x]t ⊆ [y]s nªn cã thÓ kÕt luËn r»ng sù ph©n lo¹i c¸c ®èi t−îng trong U bëi t¸c nh©n t tèt h¬n sù ph©n lo¹i c¸c ®èi t−îng trong U bëi t¸c nh©n s, hay chóng ta nãi r»ng tri thøc cña t¸c nh©n t m¹nh h¬n tri thøc cña t¸c nh©n s. V. KÕt luËn BiÓu diÔn tri thøc vµ khai ph¸ d÷ liÖu lµ nh÷ng lÜnh vùc ®· vµ ®ang ®−îc nghiªn cøu, øng dông nhiÒu trong tin häc ([2, 7]). 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 biÓu diÔn chóng nh»m n¾m b¾t nh÷ng ®Æc tr−ng chñ yÕu cña vÊn ®Ò vµ lµm cho nh÷ng th«ng tin ®ã trë nªn dÔ dµng thao t¸c. ViÖc ®−a ra c¸c phÐp to¸n trªn hÖ tri thøc cã thÓ t×m ra tËp c¸c thuéc tÝnh nhá nhÊt nh»m lo¹i bá nh÷ng th«ng tin d− thõa, kh«ng cÇn thiÕt mµ vÉn gi÷ ®−îc ý nghÜa. Sau ®ã, dùa vµo tËp thuéc tÝnh nhá nhÊt nµy ng−êi ta cã thÓ t×m ra c¸c quy luËt chung nhÊt hoÆc c¸c mÉu (patterns) ®Ó biÓu diÔn tri thøc. T I LIÖU THAM KH¶O [1] B¹ch H−ng Khang, Hoµng KiÕm, TrÝ tuÖ nh©n t¹o - C¸c ph−¬ng ph¸p vµ øng dông, Nhµ xuÊt b¶n Khoa häc Kü thuËt, Hµ Néi, 1989. 62
  7. T¹p chÝ khoa häc, tËp XXXVII, sè 1A-2008 §¹i häc Vinh [2] NguyÔn B¸ T−êng, NhËp m«n c¬ së d÷ liÖu ph©n t¸n, Nhµ xuÊt b¶n Khoa häc Kü thuËt, Hµ Néi, 2005. [3] M. Rauszer Cecylia, Knowledge Representation Systems for Groups of Agents, ICS Research Report, 1992. [4] R. Parikh, Proceeding of the Conference Theoretical Aspects of Reasoning about Knowledge, Morgan Kaufmann, 1990. [5] Z. Pawlak, Rough sets, International Journal of Computer and Information Sciences, Vol. 11, 1982, pp. 341-346. [6] Z. Pawlak, Rough Sets - The Theoretical Aspects of Reasoning about Data, Kluwer, 1991. [7] Weiru Liu, Reasonning about Knowledge using Rough sets, Springer-Verlag London, Vol. 2143, 2001, pp. 385-397. SUMMARY Some operators on knowledge representation systems based on rough set theory This paper presents knowledge representation method for group of agents t about a set of objects by rough set, introduces some knowledge operators and some basic properties of those, constructs some operators based on knowledge system. (a) Khoa C«ng nghÖ th«ng tin, §¹i häc Vinh. (b) Phßng C«ng nghÖ th«ng tin, Côc V26 - Bé c«ng an. 63
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2