Báo cáo nghiên cứu khoa học: Xây dựng cây quyết định đa trị dựa trên tập thô.

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 tác giả. 8. Nguyễn Thị Minh Tâm, Xây dựng cây quyết định đa trị dựa trên tập thô..Toán học là môn khoa học nghiên cứu về các số, cấu trúc, không gian và các phép biến đổi. Nói một cách khác, người ta cho rằng đó là môn học về "hình và số." Theo quan điểm chính thống, nó là môn học nghiên cứu về các cấu trúc trừu tượng định nghĩa từ các tiên đề, bằng cách sử dụng Luận lý học (lôgic)...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: "Xây dựng cây quyết định đa trị dựa trên tập thô." §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 4A-2007 X¢Y DùNG C¢Y QUYÕT §ÞNH §A TRÞ DùA TR£N TËP TH¤ NguyÔn ThÞ Minh T©m (a) Tãm t¾t. Bµi b¸o nµy giíi thiÖu mét c¸ch tiÕp cËn ®Ó x©y dùng c©y quyÕt ®Þnh ®a trÞ cã kh¶ n¨ng chÞu lçi dùa trªn m« h×nh tËp th« cã ®é chÝnh x¸c thay ®æi. Mét kh¸i niÖm míi vÒ quan hÖ t−¬ng ®−¬ng víi ®é chÝnh x¸c β ®−îc ®−a ra trong lý thuyÕt tËp th« cã ®é chÝnh x¸c thay ®æi vµ ®−îc ¸p dông ®Ó x©y dùng c©y quyÕt ®Þnh ®a trÞ. I. GIíI THIÖU HiÖn nay, c¸c ph−¬ng ph¸p ph©n líp ®ang ®−îc quan t©m nghiªn cøu trong nhiÒu lÜnh vùc: khai ph¸ d÷ liÖu, thèng kª, häc m¸y,... Môc ®Ých ph©n líp lµ ph©n lo¹i c¸c ®èi t−îng dùa trªn gi¸ trÞ cña c¸c thuéc tÝnh ban ®Çu vµ thuéc tÝnh nh·n. Trong bµi b¸o nµy chóng t«i ®−a ra mét trong nh÷ng c¸ch tiÕp cËn míi ®Ó lùa chän thuéc tÝnh lµ x©y dùng c©y quyÕt ®Þnh dùa trªn lý thuyÕt tËp th«. Lý thuyÕt tËp th« ®−îc Pawlak ®Ò xuÊt, ®· trë thµnh mét c«ng cô to¸n häc ®Ó gi¶i quyÕt víi nh÷ng th«ng tin mê, kh«ng ch¾c ch¾n. Lý thuyÕt tËp th« tæ hîp c¸c quan hÖ kh«ng ph©n biÖt (quan hÖ t−¬ng ®−¬ng) thµnh c¸c tËp xÊp xØ cña c¸c ®èi t−îng dùa trªn tËp xÊp xØ trªn vµ xÊp xØ d−íi ([8]). Mét trong nh÷ng vÊn ®Ò cña lý thuyÕt tËp th« lµ ph©n líp, nh−ng c¸c líp trong lý thuyÕt tËp th« ph¶i lµ chÝnh x¸c vµ ch¾c ch¾n. Trong thùc tÕ, hai ®iÓm l©n cËn cã thÓ kh«ng gièng nhau vÒ c¬ b¶n do thiÕu c¸c ®Æc tr−ng dÉn ®Õn viÖc ph©n líp kh«ng ch¾c ch¾n. B»ng c¸ch tæ hîp x¸c suÊt c¸c luËt quyÕt ®Þnh, m« h×nh tËp th« cã ®é chÝnh x¸c thay ®æi cho phÐp ph©n líp tõng phÇn. Khi mét ®èi t−îng ®−îc ph©n líp b»ng lý thuyÕt tËp th«, nÕu th«ng tin vÒ ®èi t−îng ®Çy ®ñ vµ ch¾c ch¾n th× ®ã lµ ph©n líp ®óng, cßn m« h×nh tËp th« cã ®é chÝnh x¸c thay ®æi ph©n líp ®èi t−îng víi mét ®é chÝnh x¸c β nµo ®ã ([11]). II. Lý THUYÕT TËP TH¤ ë ®©y ta chØ xÐt m« h×nh tËp th« gåm tËp c¸c ®èi t−îng U cña hÖ th«ng tin, c¸c kÕt qu¶ thu ®−îc tõ m« h×nh nµy chØ cã thÓ ¸p dông ®−îc cho tËp ®èi t−îng thuéc m« h×nh ®ã. Gi¶ sö ta cã tËp ®èi t−îng cã c¸c nh·n líp ®Ó chØ ra líp mµ mçi ®èi t−îng thuéc vµo líp ®ã. Ta gäi nh·n líp lµ thuéc tÝnh quyÕt ®Þnh vµ c¸c thuéc tÝnh cßn l¹i lµ thuéc tÝnh ®iÒu kiÖn. §Þnh nghÜa 1. NÕu S = (U, A ∪ {d}) lµ b¶ng quyÕt ®Þnh, trong ®ã A lµ tËp thuéc tÝnh ®iÒu kiÖn, d lµ tËp thuéc tÝnh quyÕt ®Þnh, ta x¸c ®Þnh hµm: δA(u) = {i: tån t¹i u’ IND(A)u vµ d(u) = i} (u’ IND(A)u tøc lµ u’ kh«ng ph©n biÖt ®−îc víi u theo tËp thuéc tÝnh A). B¶ng quyÕt ®Þnh S lµ nhÊt qu¸n nÕu card(δA(u)=1 víi mäi u∈U, ng−îc l¹i th× S lµ kh«ng nhÊt qu¸n. NhËn bµi ngµy 14/9/2007. Söa ch÷a xong 27/11/2007. 57 NguyÔn ThÞ Minh T©m ... C¢Y QUYÕT §ÞNH §A TRÞ DùA TR£N TËP TH¤, tr. 57-64 T−¬ng tù ta ®Þnh nghÜa: γA(u,i) = {u’∈ U}: u’ IND(A)u & d(u’) = i trong ®ã u∈ U & i ∈ δA(u) card (γ A (u , i )) λ A (u, i ) = u∈ U & i ∈ δA(u) ∑ card (γ A (u, i )) j∈δ A (u ) σA(u) = {i: λA(u,i) ≥ β } u∈ U. B¶ng quyÕt ®Þnh S lµ nhÊt qu¸n víi ®é chÝnh x¸c β nÕu card(σA(u) = 1 ∀u ∈ U, ng−îc l¹i th× S lµ kh«ng nhÊt qu¸n víi ®é chÝnh x¸c β . β β §Þnh nghÜa 2. NÕu Y ⊇ X ⇔ X ⊆ Y ⇔ Pr(Y | X) ≥ β , th× ta nãi X ®−îc chøa víi ®é chÝnh x¸c β trong Y hay Y chøa X víi ®é chÝnh x¸c β (0≤β≤1). §Þnh nghÜa 3. Cho (U, R) lµ mét kh«ng gian xÊp xØ, trong ®ã U lµ tËp ®èi t−îng kh¸c rçng, R lµ hä quan hÖ t−¬ng ®−¬ng trªn U. U/R = {E1, E2, ...., En} lµ c¸c líp t−¬ng ®−¬ng cña R, víi mäi X ⊆ U, c¸c xÊp xØ trªn vµ xÊp xØ d−íi víi ®é chÝnh x¸c β ®−îc ®Þnh nghÜa nh− sau: i) TËp xÊp xØ trªn cña X theo quan hÖ R víi ®é chÝnh x¸c β :   β Υ{E i ∈ X }. β = POS R ( X ) = Υ  E ∈ U / R | X ⊇ E  = Rβ X   Pr ( X | Ei )≥ β ii) TËp xÊp xØ d−íi theo quan hÖ R cña X víi ®é chÝnh x¸c β :   1− β Υ{E i ∈ X } . β R β X = NONNEG R ( X ) = Υ  E ∈ U / R | X ⊇ E  =   Pr ( ...