Đề tài Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu lớn

ã ý nghÜa trong c¸c d÷ liÖu nghiÖp vô cho phÐp hiÓu tèt h¬n vµ dù b¸o hµnh vi cña kh¸ch hµng. H×nh 8.1 Mµn h×nh øng dông Oracle Darwin Víi Oracle Darwin, ng­êi dïng cã thÓ ®Ò ra quyÕt ®Þnh vÒ: Ch¨m sãc nh÷ng kh¸ch hµng ®· cã N¾m b¾t nh÷ng kh¸ch hµng míi Ph¸t hiÖn sù gian lËn T×m ra nh÷ng kh¸ch hµng sép Qu¶n lý kh¸ch hµng víi ®é chÝnh x¸c cao h¬n Oracle Darwin ¸p dông c¸c kü thuËt khai ph¸ d÷ liÖu vµo c¸c øng dông thùc tÕ nghiÖp vô. Giao diÖn theo kiÓu c¸c cöa sæ lµm viÖc nèi tiÕp nhau (wizards) dÔ dïng gióp cho ng­êi ph©n tÝch ®iÒu khiÓn qu¸ tr×nh khai ph¸ d÷ liÖu cña m×nh th«ng qua c¸c tuú chän vµ tham sè. Darwin lµ s¶n phÈm khai ph¸ d÷ liÖu th­¬ng m¹i hoµn chØnh tÝch hîp chÆt chÏ víi CSDL Oracle vµ ®· trë thµnh sù chän lùa tù nhiªn cña c¸c tæ chøc ®ang t×m kiÕm sù thu håi vèn nhanh chãng tõ c¸c ®Çu t­. Trong ch­¬ng nµy, ta sÏ kh¶o nghiÖm s¶n phÈm nh×n tõ gãc ®é ¸p dông c¸c gi¶i ph¸p khai ph¸ d÷ liÖu vµo thµnh mét s¶n phÈm th­¬ng m¹i ¸p dông vµo thùc tÕ. Cô thÓ, ta t×m hiÓu viÖc ¸p dông c¸c kü thuËt c©y quyÕt ®Þnh, m¹ng n¬ron vµ thuËt to¸n k ng­êi l¸ng giÒng gÇn nhÊt vµo viÖc khai ph¸ d÷ liÖu. Bëi v× khai ph¸ d÷ liÖu lµ mét b­íc quan träng cña qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL (KDD) vµ c¸c b­íc ph¸t hiÖn tri thøc trong CSDL l¹i cã liªn quan chÆt chÏ ®Õn viÖc chuÈn bÞ d÷ liÖu vµ c¸c nÒn t¶ng cho phÐp c¸c c«ng cô khai ph¸ d÷ liÖu thùc hiÖn. Do vËy, tr­íc khi t×m hiÓu vÒ Oracle Darwin, ta ®iÓm qua nÒn t¶ng d÷ liÖu bao gåm hÖ qu¶n trÞ CSDL Oracle8i vµ Oracle Data Warehouse dïng cho viÖc khai ph¸ d÷ liÖu. Vµi nÐt vÒ HÖ Qu¶n trÞ CSDL Oracle8i vµ Oracle Data Warehouse C¸c øng dông khai ph¸ d÷ liÖu ®ßi hái mét sè kü thuËt xö lý kh¸c biÖt so víi c¸c øng dông t¸c nghiÖp trùc tuyÕn do c¸c truy vÊn phøc t¹p vµ kh«ng ®Þnh tr­íc (ad hoc) trªn mét kho d÷ liÖu khæng lå. §Ó h­íng ®Õn c¸c yªu cÇu ®ã, Oracle8i ®· ®i tr­íc mét b­íc trong viÖc cung cÊp hµng lo¹t c¸c kü thuËt xö lý c©u hái, tèi ­u viÖc chän ®­êng truy xuÊt d÷ liÖu hiÖu qu¶ nhÊt còng nh­ khai th¸c triÖt ®Ó c¸c cÊu tróc phÇn cøng song song. Trong thùc tÕ, Oracle ®· chøng tá hiÖu n¨ng cao cÊp cho nhiÒu øng dông víi c¸c c¬ së d÷ liÖu cã kÝch th­íc ®Õn hµng terabyte. Mét øng dông cã thÓ cã mét b¶ng d÷ liÖu cã sè b¶n ghi rÊt lín. NhiÒu ng­êi dïng sÏ ®ång thêi truy cËp vµ thao t¸c trªn c¸c b¶n ghi cña nã. NÕu kü thuËt kho¸ ®Õn møc trang hoÆc ®Õn møc b¶n ghi cña hÖ qu¶n trÞ CSDL kh«ng tèt còng nh­ h¹n chÕ vÒ phÇn cøng, ch¾c ch¾n hiÖu n¨ng øng dông sÏ bÞ gi¶m ®¸ng kÓ. Oracle8i gi¶i quyÕt ®­îc “cæ chai” ®ã cña hiÖu n¨ng nhê kü thuËt ph©n ho¹ch b¶ng hay “chia ®Ó trÞ”. C¸c b¶ng vµ chØ sè khæng lå ®­îc chia thµnh c¸c phÇn nhá h¬n ®­îc qu¶n lý, l­u tr÷ vµ xö lý t¸ch biÖt còng nh­ cã thÓ thùc hiÖn song song. KiÕn tróc xö lý c©u hái song song cña Oracle8i tËn dông kh¶ n¨ng phÇn cøng gióp t¨ng hiÖu n¨ng cña c¸c c©u hái truy vÊn vµ cËp nhËt b»ng c¸ch chia linh ho¹t c¸c thao t¸c ®ã ra thµnh c¸c t¸c vô t¸ch biÖt vµ ph©n phèi chóng cho c¸c bé vi xö lý vµ c©n b»ng t¶i cho c¸c nót nèi côm. KiÕn tróc nµy lµm viÖc hiÖu qu¶ vµ th«ng minh víi hÇu hÕt c¸c hÖ thèng phÇn cøng song song hiÖn nay. Oracle Warehouse mang ®Õn mét hä c¸c s¶n phÈm cho viÖc thiÕt kÕ, triÓn khai vµ qu¶n lý mét kho d÷ liÖu hiÖu qu¶. Mçi s¶n phÈm ®­îc thiÕt kÕ ®Ó tÝch hîp víi mäi s¶n phÈm kh¸c. Mét ®Æc tr­ng cña Oracle Warehouse lµ dùa trªn nÒn t¶ng c«ng nghÖ m¹nh, c«ng cô ph©n tÝch thiÕt kÕ vµ c¸c øng dông nghiÖp vô th«ng minh. Oracle Warehouse bao gåm Warehouse Builder. §©y lµ mét c«ng cô hoµn chØnh cho thiÕt kÕ, triÓn khai vµ qu¶n lý c¸c kho d÷ liÖu xÝ nghiÖp vµ c¸c øng dông th«ng minh th­¬ng m¹i ®iÖn tö. §ã lµ m«i tr­êng cho phÐp m« h×nh ho¸, thiÕt kÕ, kÕt xuÊt d÷ liÖu, truyÒn vµ t¶i, thu n¹p, qu¶n lý siªu d÷ liÖu, tÝch hîp c¸c c«ng cô ph©n tÝch vµ qu¶n trÞ kho. Nã còng cho phÐp tÝch hîp c¸c thµnh phÇn hÖ qu¶n trÞ CSDL, hÖ ®a chiÒu vµ c«ng cô truy vÊn cña ng­êi dïng. 8.2 C©y quyÕt ®Þnh Darwin 8.2.1 Giíi thiÖu c¸c c©y C©y quyÕt ®Þnh ®­îc t¹o ra bëi Darwin chÝnh lµ c©y ph©n líp vµ håi qui (classification and regression trees – C&RT). C©y Darwin cã thÓ thùc hiÖn ph©n líp vµ dù b¸o nhiÒu líp. Ta m« t¶ c©y Darwin b»ng mét bµi to¸n ph©n líp ®¬n gi¶n. Gi¶ sö ta cÇn ph©n biÖt ng­êi, khØ, chim, mÌo, c¸ voi vµ c¸ (theo thuËt ng÷ khai ph¸ d÷ liÖu, ta cÇn ph©n líp mçi b¶n ghi míi xem nã thuéc vÒ líp ®éng vËt nµo kÓ trªn). Chóng ta chØ cã d÷ liÖu nh­ sau: Ng­êi cã 2 tay, 2 ch©n, kh«ng cã l«ng mao, l«ng vò hoÆc v¶y sèng trªn mÆt ®Êt KhØ cã 2 tay, 2 ch©n, cã l«ng mao sèng trªn c©y Chim cã hai c¸nh, hai ch©n vµ ®u«i cã l«ng vò sèng trªn c©y MÌo cã 4 ch©n vµ ®u«i cã l«ng mao sèng trªn mÆt ®Êt C¸ voi cã ®u«i hai thuú kh«ng cã l«ng mao, l«ng vò hoÆc v¶y sèng d­íi n­íc C¸ cã v©y vµ ®u«i cã v¶y sèng d­íi n­íc D­íi ®©y lµ mét c©y mµ ta cã thÓ t¹o ra tõ d÷ liÖu trªn nã cã sèng d­íi n­íc kh«ng? cã kh«ng 2a. nã cã v¶y kh«ng? 2b. nã cã tay kh«ng? cã kh«ng cã kh«ng C¸ C¸ voi 3a. L«ng mao? 3b. L«ng vò? cã kh«ng cã kh«ng KhØ Ng­êi Chim MÌo - T×m kiÕm c©u tr¶ lêi cô thÓ Bµi to¸n ph©n líp cña ta lµ x¸c ®Þnh mçi b¶n ghi trong tËp d÷ liÖu t­ëng t­îng thuéc vÒ líp ®éng vËt nµo trong 6 líp. NÕu chØ ®Ò cËp ®Õn mét líp, ch¼ng h¹n “nã cã ph¶i lµ chim kh«ng?”, ta chØ cÇn x©y dùng mét c©y cã hai nh¸nh gièng nh­ nh¸nh 3b. Kh«ng cÇn ph¶i ph©n líp mäi b¶n ghi mµ chØ cÇn ph©n biÖt gi÷a chim vµ kh«ng chim. Mäi c©u hái ®èi víi c¸c líp kh¸c còng t­¬ng tù nh­ sau: Nã lµ c¸? = (1) Nã cã v¶y? Nã lµ mÌo? = (1) Nã cã l«ng mao? (2) Nã cã tay? hoÆc chØ cÇn mét c©u hái míi Nã cã 4 ch©n? Nã lµ c¸ voi? = (1) Sèng d­íi n­íc? (2) Nã cã v¶y? hoÆc tèt h¬n Nã cã ®u«i 2 thuú? - Sö dông c©y ®Ó dù b¸o Dù b¸o sÏ cÇn thiÕt khi cã mét tËp d÷ liÖu nh­ng kh«ng ph¶i lóc nµo còng cã thÓ ®­a ra ®­îc c¸c c©u tr¶ lêi. Gi¶ thiÕt r»ng ta thay ®æi tËp d÷ liÖu sao cho chØ cã mét tr­êng m« t¶ ®éng vËt cã l«ng vò, l«ng mao, v¶y hay lµ kh«ng cã nh÷ng thø ®ã. NÕu ta nãi: “con nµy cã l«ng vò” th× cã thÓ tr¶ lêi ch¾c ch¾n r»ng ®ã lµ chim. NÕu nãi: “Con nµy cã l«ng mao” th× cã thÓ tr¶ lêi ®ã cã thÓ lµ con khØ hoÆc mÌo. Kh¶ n¨ng lµ con nµy hay con kia phu thuéc vµo mét sè yÕu tè. Ch¼ng h¹n, nÕu nãi: “ nã cã l«ng mao vµ lµ vËt nu«i yªu thÝch”, th× cã thÓ xem xÐt nhËn thøc t­¬ng ®èi xem con mÌo hay con khØ ®­îc xem lµ con vËt nu«i ­a thÝch vµ tr¶ lêi “Nã cã thÓ lµ con mÌo”. Râ rµng lµ ch­a ch¾c ch¾n tuyÖt ®èi. Cã thÓ göi cho ng­êi chñ cña con vËt (cã thÓ lµ mÌo) nµy mét catal« vÒ c¸c s¶n phÈm mÌo hay kh«ng? Nã lµ mÌo víi ®é ch¾c ch¾n bao nhiªu? VÊn ®Ò ®Æt ra lµ: ViÖc göi mét catal« tèn kÐm bao nhiªu? Catal« nµy cã nh÷ng thø ®Ó dïng cho mét con khØ nu«i hay kh«ng? Víi mét tÝnh to¸n nµo ®ã, c©y Darwin cã thÓ tr¶ lêi c¸c c©u hái thø hai vµ thø t­. C©u tr¶ lêi thø 3 ph¶i tõ ng­êi dïng. C©y Darwin chÊp nhËn (nh­ng kh«ng yªu cÇu) th«ng tin liªn quan ®Õn chi phÝ cho viÖc dù b¸o ®óng/sai vµ tham sè cho c¸c tÝnh to¸n. H×nh 8.2 Mµn h×nh c©y Darwin 8.2.2 T¹o c©y T¹i nót cña c©y, d÷ liÖu chØ lµ mét mí hçn ®én. Tõ d÷ liÖu, c©y ph¸t sinh ra mét lo¹t c¸c luËt hay cßn gäi lµ kiÓm tra logic hay c©u hái. Mçi khi ®i qua mét luËt nh­ vËy, c¸c b¶n ghi sÏ lÇn l­ît ®i vµo c¸c nhãm riªng biÖt vµ nhá h¬n. Mçi lÇn t¸ch, ta sÏ t¹o ra c¸c nh¸nh cña c©y. ViÖc t¸ch nh¸nh cã hai môc ®Ých: t¹o ra sù ph©n nhãm ®ång nhÊt h¬n Ýt nhÊt liªn quan ®Õn tr­êng ®Ých vµ t¹o ra c¸c t¸ch biÖt h¬n n÷a khi qu¸ tr×nh tiÕp tôc. Qu¸ tr×nh t¸ch tiÕp tôc cho ®Õn khi hoÆc lµ tËp c¸c b¶n ghi trong mçi nh¸nh lµ ®· ®ång nhÊt tøc lµ kh«ng cßn viÖc t¸ch nµo cÇn thiÕt n÷a, hoÆc lµ mét ng­ìng mËt ®é (cho tr­íc) ®¹t ®­îc hoÆc lµ sè nót tèi ®a (cho tr­íc) t×m ®­îc. C¸c nót t¹i cuèi mçi nh¸nh (®· t¸ch xong) ®­îc gäi lµ nót l¸ hay l¸. Qu¸ tr×nh t¸ch tiÕp tôc cho ®Õn khi tÊt c¶ c¸c nh¸nh ®Òu kÕt thóc ë l¸. Khi c©y ®· ®­îc t¹o ra, mçi nót l¸ chøa tÊt c¶ hoÆc hÇu hÕt c¸c b¶n ghi thuéc vÒ mét líp. Ta nãi r»ng mçi nót l¸ cã liªn kÕt víi mét líp cô thÓ. Mét líp cã thÓ cã nhiÒu l¸. C©y ®­îc t¹o ra ph¶i cã tÇn suÊt lçi nhá nhÊt víi sè nót Ýt nhÊt bëi v× c©y cµng lín th× tµi nguyªn vµ chi phÝ tÝnh to¸n cµng lín vµ tÇn suÊt lçi cµng cao th× kÕt qu¶ cµng kÐm chÝnh x¸c. C¸ch c¬ cÊu c©u hái nghiÖp vô cã ¶nh h­ëng nhiÒu ®Õn kÝch th­íc vµ hiÖu n¨ng cña c©y. C¸ch tØa c©y, bá l¸ vµ nh¸nh ®Ó t¹o ra sù kÕt hîp tèt nhÊt vÒ kÝch th­íc vµ tÇn suÊt lçi, còng cã thÓ cã ¶nh h­ëng quan träng ®Õn kÝch th­íc vµ hiÖu n¨ng. 8.2.2.1 TØa c©y NÕu tËp mÉu häc ®­îc chän lµ ®iÓn h×nh cho toµn thÓ d÷ liÖu, c©y ®Çy ®ñ sÏ cã tÇn suÊt lçi thÊp nhÊt, tøc lµ thÊp h¬n bÊt kú c©y con bÞ tØa nµo. Tuy nhiªn, hÇu nh­ kh«ng bao giê cã tr­êng hîp nh­ vËy. C¸c mÉu d÷ liÖu ®Òu cã thÓ bao gåm c¸c thÓ hiÖn riªng cô thÓ. Khi c©y tiÕp tôc qu¸ tr×nh t¸ch cµng ngµy cµng nhá h¬n, th× nã còng kh«ng tr¸nh ®­îc ph¶n ¸nh c¶ nh÷ng biÓu hiÖn riªng cña tËp d÷ liÖu häc vµ nh­ vËy g©y ra tÇn suÊt sai sè cao h¬n khi ¸p dông cho mét d÷ liÖu míi. §Ó ®¶m b¶o tÇn suÊt lçi thÊp nhÊt, thuËt to¸n cho phÐp tiÕn hµnh tØa c©y, nghÜa lµ lo¹i bá mét vµi phÇn t¸ch t¹i cuèi mçi nh¸nh. KÕt qu¶ sÏ lµ mét lo¹t c¸c c©y con, mçi trong chóng lµ mét phiªn b¶n cña c©y ®Çy ®ñ bÞ tØa bít ®i. Khi kiÓm tra hoÆc ®¸nh gi¸ mét c©y, nã b¸o c¸o tÇn suÊt lçi vµ sè nót ®èi víi tõng c©y con. Ng­êi dïng sau ®ã quyÕt ®Þnh c©y con nµo ®­îc dïng ®Ó dù b¸o hoÆc ph©n líp c¸c d÷ liÖu míi. HiÓn nhiªn, ta sÏ chän c©y con víi tÇn suÊt lçi thÊp nhÊt vµ sè nót Ýt nhÊt. Sè nót cµng Ýt, m« h×nh cµng hiÖu qu¶ (cµng nhanh). TØa l¹i TØa l¹i c©y cho phÐp thö nghiÖm mét c¸ch tØa kh¸c. PhÐp thùc hiÖn nµy ¶nh h­ëng ®Õn tæ chøc cña c©y con, nh­ng kh«ng ¶nh h­ëng cÊu tróc cña c©y ®Çy ®ñ (tøc lµ kh«ng ¶nh h­ëng ®Õn c¸c luËt t¹o c©y). Cã hai chøc n¨ng tØa c©y lµ cost vµ gini. NgÇm ®Þnh cho t¹o c©y lµ cost, cho tØa c©y lµ gini. LuËt c©y Mét trong c¸c thuËn lîi cña c©y lµ s¶n sinh ra mét tËp dÔ ®äc c¸c luËt ®Ó t¸ch. Ng­êi dïng sÏ quyÕt ®Þnh dïng mét c©y con cô thÓ øng víi luËt nµo ta muèn dïng. NÕu ta kh«ng chØ ra c©y con th× c©y ®Çy ®ñ sÏ ®­îc sö dông. Mçi mét nót h×nh thµnh ®iÓm quyÕt ®Þnh hiÓn thÞ sö dông khu«n d¹ng sau: Dßng ®Çu tiªn chØ ra sè nót cã d¹ng [ TREE NODE N Dßng thø hai chØ ra tæng sè b¶n ghi t¹i nót nµy gåm c¶ sè l­îng thùc tÕ vµ tû lÖ b¶n ghi trong tËp mÉu häc d­íi d¹ng sau: Total records: r1 (d1) trong ®ã r1 = sè b¶n ghi t¹i nót N d2 = (sè b¶n ghi t¹i nót N)/(sè b¶n ghi trong tËp mÉu häc) Dßng thø ba chØ ra sè b¶n ghi víi gi¸ trÞ ®Ých cô thÓ (®Çu tiªn lµ sè l­îng thùc tÕ vµ tiÕp sau lµ tû lÖ biÓu diÔn sè l­îng nµy víi gi¸ trÞ trong tËp mÉu häc. Cô thÓ: Target records: r2 (d2) ] trong ®ã: r2 = Sè b¶n ghi t¹i nót N víi ph©n líp ®óng d2 = (sè b¶n ghi trong N víi líp = j)/(sè b¶n ghi trong tËp mÉu häc víi líp =j) Dßng thø 4 trë ®i m« t¶ luËt ®­a mét b¶n ghi vµo líp c¸c b¶n ghi cã cïng gi¸ trÞ ®Ých nh­ sau: IF c¸c tr­êng cã gi¸ trÞ tho¶ m·n THEN gi¸ trÞ tr­êng ®Ých = mét gi¸ trÞ WITH chi phÝ ph©n líp sai = C Dßng cuèi cïng chØ ra chi phÝ x¸c suÊt ph©n líp sai cho b¶n ghi nÕu viÖc dù b¸o ®­îc lµm t¹i nót nµy. NÕu ta cung cÊp chi phÝ cho dù b¸o sai trong khi t¹o c©y th× c¸c chi phÝ ®ã cïng víi kh¶ n¨ng sai t¹o nªn chi phÝ ph©n líp sai ®­îc thÓ hiÖn ë ®©y. NÕu ta kh«ng cung cÊp chi phÝ th× chi phÝ ph©n líp sai ®­îc dù b¸o chØ ®¬n thuÇn lµ kh¶ n¨ng sai. Sau ®©y lµ luËt vÝ dô. Tr­êng a10 lµ tr­êng ®Ých. [TREE NODE 41 Total records: 10 (0.057) Target records: 9 (0.0628445) ] IF a1 <= 11 AND a4 in {40 41 42 44 49} AND a13 > 200 AND a17 = 512 THEN a10 = 1 WITH misclassification cost = 0.1 C©u lÖnh a4 in { ... } nghÜa lµ gi¸ trÞ t¹i tr­êng a4 cã thÓ lµ mét trong c¸c gi¸ trÞ n»m trong ngoÆc. Chi phÝ 0 chØ ra tÊt c¶ c¸c b¶n ghi t¹i nót nµy ®Òu r¬i vµo cïng mét vïng. Chi phÝ 0 nh­ vËy t­¬ng øng víi gi¸ trÞ conf lµ 1. NÕu gi¸ trÞ ®Ých phøc t¹p th× chi phÝ cao h¬n vµ conf thÊp h¬n. Ch¼ng h¹n, nÕu Total records = 10 and target records = 9, chi phÝ sÏ lµ 0.1 vµ conf sÏ lµ 0.9 hoÆc 90%. 8.2.3 C¸c tuú chän thªm: ®iÒu khiÓn kÝch th­íc c©y Cã ba tham sè ¶nh h­ëng ®Õn kÝch th­íc cña c©y. Hai tham sè ®Çu, ng­ìng mËt ®é vµ sè nót lín nhÊt cã gi¸ trÞ ngÇm ®Þnh s½n vµ cã thÓ ¸p dông cho mäi tr­êng hîp ®­îc x¸c ®Þnh tr­íc trong Darwin. ViÖc ®iÒu chØnh c¸c gi¸ trÞ nµy ®­îc thùc hiÖn dÔ dµng trong c¸c giai ®o¹n lµm viÖc trªn mét m« h×nh. Tham sè thø ba lµ kÝch th­íc tËp mÉu cã thÓ ®­îc thay ®æi cïng víi ®iÒu chØnh gi¸ trÞ mËt ®é. 8.2.3.1 Ng­ìng mËt ®é MËt ®é chØ ra sè b¶n ghi víi mçi gi¸ trÞ tr­êng ®Ých ®Ó dõng viÖc t¸ch. Gi¸ trÞ mËt ®é n»m gi÷a 0 vµ 1 biÓu thÞ tû lÖ c¸c b¶n ghi dõng viÖc t¸ch. Sè b¶n ghi tèi thiÓu mµ mét nót cã thÓ bao gåm ®­îc tÝnh s¬ bé tõ tÝch n*d, trong ®ã, n sè b¶n ghi cã gi¸ trÞ ®Ých xuÊt hiÖn Ýt nhÊt trong tËp d÷ liÖu mÉu, cßn d lµ ng­ìng mËt ®é do ng­êi sö dông ®­a vµo hay lÊy gi¸ trÞ ngÇm ®Þnh. 8.2.3.2 Sè nót lín nhÊt Ta cã thÓ ®Æt ra h¹n chÕ sè nót cña c©y. Khi c©y ®¹t tíi kÝch th­íc nµy th× sù më réng c©y lµ dõng l¹i. C¸c c©y bÞ dõng l¹i trong qu¸ tr×nh ph¸t triÓn sÏ cã d¹ng xiªn xiªn. Do vËy, tuú chän nµy chØ sö dông trong c¸c giai ®o¹n ban ®Çu cña x©y dùng m« h×nh. Darwin kh«ng cã gi¸ trÞ ngÇm ®Þnh cho tham sè nµy. 8.2.3.3 KÝch th­íc tËp mÉu KÝch th­íc c©y cã xu h­íng t¨ng theo kÝch th­íc tËp mÉu. NÕu tËp mÉu rÊt lín, cã thÓ t¹o ra c¸c c©y ban ®Çu dùa trªn mét sè l­îng b¶n ghi t­¬ng ®èi nhá hoÆc ®Æt gi¸ trÞ mËt ®é lín vµ chØ sö dông sè b¶n ghi lín h¬n khi ta ®· ch¾c ch¾n cã mét m« h×nh tèt. Ch¼ng h¹n, nÕu cã 1000000 b¶n ghi lµm mÉu häc cho m« h×nh c©y, ta chØ cã thÓ sö dông 10000 b¶n ghi cho lÇn thö nghiÖm ®Çu tiªn vµ t¨ng dÇn sè l­îng cho ®Õn khi ta ch¾c ch¾n ®· t¹o ra ®­îc mét m« h×nh h÷u dông. Kh«ng nªn xo¸ bá c¸c tr­êng tõ tËp mÉu khi t¹o mét c©y trõ phi ta ch¾c ch¾n chóng kh«ng cÇn thiÕt. Nãi chung, tèt nhÊt h·y ®Ó cho Darwin quyÕt ®Þnh tr­êng nµo liªn quan tíi m« h×nh. 8.2.4 Tèi ­u ph¸t triÓn c©y Cã mét sè tham sè dïng cho viÖc tèi ­u ph¸t triÓn c©y. Chóng ®Òu cã s½n gi¸ trÞ ngÇm ®Þnh thÝch hîp cho mäi tr­êng hîp. PhÇn nµy ta sÏ xem xÐt c¸c t×nh h­èng ®Ó ®Æt c¸c gi¸ trÞ tham sè kh¸c víi gi¸ trÞ ngÇm ®Þnh. Hép tho¹i Advanced Options trong Darwin dïng cho viÖc nµy. 8.2.4.1 Hµm gi¶m (Decrease Function) C¸c c©y Darwin cã hai hµm gi¶m ®­îc tÝch hîp dïng ®Ó ®o møc ®é pha trén trong mét lÇn t¸ch. Darwin sö dông hµm gi¶m gini ngÇm ®Þnh. Khi ta ph¸t triÓn hay tØa l¹i c©y, ta cã thÓ chän hµm gi¶m entropy thay thÕ. C¬ së to¸n häc cña hµm gi¶m entropy ®­îc tr×nh bµy trong ch­¬ng 5. §Ó t¹o ra mét c©y, thuËt to¸n Darwin b¾t ®Çu víi nót gèc bao gåm toµn bé tËp mÉu vµ t×m kiÕm viÖc t¸ch “tèt nhÊt”. ViÖc t¸ch ®Çu tiªn nµy ph©n ho¹ch tËp mÉu thµnh hai nót míi. T¹i mçi mét nót nót míi, Darwin lÆp l¹i qu¸ tr×nh t×m c¸ch t¸ch tèt nhÊt. NÕu kh«ng cßn phÐp t¸ch “tèt” nµo t¹i mét nót th× nót ®ã kh«ng t¸ch n÷a vµ trë thµnh l¸. Qu¸ tr×nh t¸ch tiÕp tôc cho ®Õn khi tÊt c¶ c¸c nót ®Òu lµ l¸. C¸c hµm gi¶m trong thuËt to¸n Darwin chØ ra cã t¸ch hay kh«ng vµ t¸ch nh­ thÕ nµo t¹i mét nót th«ng qua tÝnh to¸n l­îng kh¸c biÖt ®­îc gi¶m t¹i mçi lÇn t¸ch cã thÓ. PhÐp t¸ch tèt nhÊt sÏ t­¬ng øng víi l­îng gi¶m d­¬ng lín nhÊt. NÕu l­îng gi¶m nhá h¬n hay b»ng kh«ng cho tÊt c¶ c¸c lÇn t¸ch cã thÓ, nót trë thµnh l¸. Ta cã thÓ thay ®æi ng­ìng nµy ®Ó kÐo dµi hay dõng qu¸ tr×nh t¸ch. C¸c hµm entropy vµ gini tÝnh to¸n l­îng gi¶m sù kh¸c biÖt trong mçi lÇn t¸ch b»ng c¸ch so s¸nh chØ sè kh¸c biÖt cña c¸c b¶n ghi t¹i mét nót ch­a t¸ch víi chØ sè kh¸c biÖt cña chÝnh tËp b¶n ghi sau khi t¸ch. ChØ sè kh¸c biÖt lµ ®é ®o vÒ ®é xiªn (hoÆc kh«ng xiªn) cña c¸c gi¸ trÞ ®Ých bªn trong mét tËp c¸c b¶n ghi. ChØ sè kh¸c biÖt cao h¬n ph¶n ¸nh mét c¸ch t­¬ng ®èi tû lÖ cña c¸c gi¸ trÞ ®Ých. Môc tiªu cña ph¸t triÓn c©y lµ gi¶m chØ sè ph©n biÖt. C©y cã l¸ víi c¸c chØ sè kh¸c biÖt thÊp sÏ cho ta c¸c luËt ph©n líp, cã thÓ dù b¸o c¸c gi¸ trÞ ®Ých víi ®é tin cËy cao. §èi víi mçi lÇn t¸ch S, c¸c hµm entropy vµ gini tÝnh to¸n chØ sè gi¶m nh­ sau: ChØ sè gi¶m = chØ_sè_gi¶m (sè b¶n ghi t¹i nót ch­a t¸ch) – chØ_sè_gi¶m (sè b¶n ghi sau khi t¸ch S) = chØ_sè_gi¶m (sè b¶n ghi t¹i nót ch­a t¸ch) - (PL*chØ_sè_gi¶m [sè b¶n ghi t¹i nót tr¸i sau t¸ch S] + PR*chØ_sè_gi¶m [sè b¶n ghi t¹i nót ph¶i sau t¸ch S]) ë ®©y PL vµ PR lµ c¸c c¸c tû lÖ b¶n ghi r¬i vµo nót tr¸i vµ ph¶i t­¬ng øng sau t¸ch. C¸c hµm entropy vµ gini kh¸c nhau ë chç chóng x¸c ®Þnh chØ sè gi¶m nh­ thÕ nµo. Gi¶ thiÕt ta cã hai gi¸ trÞ ®Ých, ký hiÖu bëi + vµ -, vµ P+ vµ P- lµ tû lÖ c¸c b¶n ghi víi gi¸ trÞ ®Ých + vµ - t­¬ng øng trong tËp c¸c b¶n ghi ®ang xem xÐt. Th×: §èi víi entropy: -(P+logP+ + P-logP- ) §èi víi gini: 2 P- P+ 8.2.4.2 C¸c hµm tØa C¸c hµm tØa thùc hiÖn viÖc tØa (t¸ch) mét c©y thµnh c¸c c©y con. Mçi mét l¸ cña mét c©y ®­îc g¸n mét líp vµ mét x¸c suÊt ph©n líp sai. Ta gi¶ thiÕt nÕu + vµ - ký hiÖu lµ hai líp vµ mét l¸ ®­îc g¸n líp + th× P- ký hiÖu x¸c suÊt mét b¶n ghi t¹i l¸ bÞ ph©n líp sai (thùc tÕ thuéc vÒ líp -) vµ P+ = (1 - P- ) lµ x¸c suÊt ph©n líp ®óng. TÇn suÊt lçi cña mét l¸ ®­îc x¸c ®Þnh tõ P+ vµ P- phô thuéc vµo hµm tØa ®­îc chän khi t¹o c©y. Hai hµm tØa dïng cho viÖc nµy lµ cost (ngÇm ®Þnh) vµ gini. Chóng x¸c ®Þnh tÇn suÊt lçi cña mét l¸ nh­ chØ ra d­íi ®©y, ë ®©y C+ - lµ chi phÝ g¸n mét b¶n ghi vµo líp + khi trªn thùc tÕ nã thuéc líp -. §èi víi cost: P- C+ - §èi víi gini: 2P- P+ Víi hµm tØa cost, qu¸ tr×nh tØa x¸c ®Þnh c¶ x¸c suÊt ph©n líp sai vµ chi phÝ cho viÖc ®ã. Theo truyÒn thèng, hµm tØa gini ®­îc sö dông khi nhÊn m¹nh dù b¸o ph©n líp kÐm chÝnh x¸c h¬n dù b¸o x¸c suÊt. Trong tr­êng hîp nµy, lý thuyÕt ph©n líp nãi r»ng chiÕn l­îc tèt nhÊt lµ t¹o ra mét c©y sö dông hµm gi¶m gini vµ tØa nã còng sö dông gini. 8.2.4.3 §Þnh h­íng (priors) M« h×nh c©y Darwin lµm viÖc tèt nhÊt khi cã mét sè thÝch hîp gi¸ trÞ ph©n líp trong tËp mÉu häc. Thùc tÕ kh«ng ph¶i lu«n lu«n ®óng nh­ vËy. Ch¼ng h¹n, mét CSDL cã thÓ ph¶n ¸nh thùc tÕ chÝnh x¸c cã 90% “d­¬ng” trong ph©n líp ®Ých vµ chØ cã 10% “©m” nh­ng trong tËp mÉu c¸c b¶n ghi l¹i kh«ng ph¶n ¸nh tû lÖ nh­ vËy. §Ó gi¶i quyÕt vÊn ®Ò nµy, ta cã thÓ t¹o mét tËp mÉu mµ c¸c phÇn tö d­¬ng vµ ©m t­¬ng ®èi c©n b»ng vµ sau ®ã, cung cÊp th«ng tin ®Þnh h­íng cho Darwin vÒ sù c©n b»ng thùc sù lµ g×. T­¬ng tù, nÕu c¶ kh«ng gian d÷ liÖu cña ta bÞ lÖch khi ph©n líp, ta cã thÓ thÊy r»ng kh«ng gian ch­a ®­îc ph©n líp, khi cã mét sù xiªn lÖch kh¸c, ta cã thÓ xÐt tíi sù xiªn lÖch ®ã d­íi d¹ng th«ng tin ®Þnh h­íng. Th«ng tin ®Þnh h­íng chØ ra trong mét tÖp bao gåm mét danh s¸ch c¸c ph©n líp cã thÓ. Mçi dßng bao gåm mét ph©n líp (nghÜa lµ mét gi¸ trÞ ®Ých) céng víi x¸c suÊt mét b¶n ghi thuéc vÒ ph©n líp ®ã. Mäi gi¸ trÞ xuÊt hiÖn trong d÷ liÖu cÇn ph¶i cã. D¹ng thÓ hiÖn lµ: DARWIN(tm) TREE PRIORS target–value–1 prior–1 target–value–2 prior–2 ... target–value–n prior–n END TREE PRIORS Nguyªn t¾c cho c¸c tÖp ®Þnh h­íng lµ nh­ sau: Dßng ®Çu tiªn vµ cuèi cïng cña tÖp cÇn bao gåm ®óng c¸c c©u ch÷ nh­ ®· chØ ra. mçi prior-n cÇn lín h¬n hoÆcb»ng 0 vµ nhá h¬n hoÆc b»ng 1 Tæng tÊt c¶ c¸c prior-n ph¶i b»ng 1. Ch¼ng h¹n, DARWIN(tm) TREE PRIORS (Thinking Machines Corporation) good–risk .88 poor–risk .12 END TREE PRIORS Nh÷ng ®Þnh h­íng nµy cung cÊp cho Darwin th«ng tin ®Ó ®iÒu chØnh c¸c mÉu theo tû lÖ ®ã. 8.2.4.4 Chi phÝ Ta cã thÓ chØ ra chi phÝ liªn quan ®Õn viÖc quyÕt ®Þnh sai. Lµm nh­ vËy sÏ rÊt h÷u Ých khi chi phÝ cho c¸c ph©n líp sai kh¸c nhau còng kh¸c nhau ®¸ng kÓ. Chi phÝ ®­îc chØ ra nh­ mét ma trËn trong ®ã hµng (i) lµ c¸c gi¸ trÞ ®­îc dù b¸o cßn cét (j) lµ c¸c gi¸ trÞ thùc. Mét chi phÝ lµ chi phÝ dù b¸o gi¸ trÞ i khi gi¸ trÞ thùc lµ j. NÕu chi phÝ kh«ng ®­îc cung cÊp, Darwin sö dông gi¸ trÞ 0 cho tÊt c¶ c¸c dù b¸o ®óng vµ 1 cho tÊt c¶ c¸c dù b¸o sai. Nh­ vËy, ma trËn ngÇm ®Þnh cho mét ®Ých cã/kh«ng ®¬n gi¶n cã thÓ t¹o ra mét tÖp chi phÝ: DARWIN(tm) TREE COSTS Yes No Yes 0 1 No 1 0 END TREE COSTS Nguyªn t¾c cho tÖp chi phÝ lµ nh­ sau: Dßng ®Çu tiªn vµ cuèi cña tÖp gièng nh­ nªu trong vÝ dô trªn. C¸c ®Çu hµng vµ ®Çu cét cÇn ph¶i liÖt kª theo thø tù nh­ sau: 1 2 3 1 2 3 1 3 2 2 1 Tr­êng hîp ®Çu lµ ®óng, cßn sau lµ sai. - Chi phÝ cho c¸c dù b¸o ®óng cÇn ph¶i lµ 0. Chi phÝ cho c¸c c¸c dù b¸o ®óng cÇn ph¶i lín h¬n 0. 8.2.5 Qóa tr×nh x©y dùng m« h×nh Ta xem xÐt qu¸ tr×nh c¬ b¶n sö dông Darwin ®Ó x©y dùng m« h×nh c©y. 8.2.5.1 Tr­íc khi b¾t ®Çu §Ó x©y dùng mét m« h×nh c©y, ta b¾t ®Çu víi: C©u hái cÇn tr¶ lêi ®­îc ph©n thµnh c¸c mÖnh ®Ò sao cho c©u tr¶ lêi cã thÓ cã ®­îc b»ng viÖc ph©n líp c¸c b¶n ghi t­¬ng øng víi gi¸ trÞ cña tr­êng ®Ých trong mçi b¶n ghi d÷ liÖu. Nguån d÷ liÖu lÞch sö (nghÜa lµ d÷ liÖu mµ gi¸ trÞ tr­êng ®Ých ®· cã råi ®Ó t¹o ra mét tËp mÉu Darwin). Chia tËp mÉu thµnh ba tËp con dïng cho häc, kiÓm tra/®¸nh gi¸ vµ dù b¸o. C¸c tËp mÉu con cã thÓ ®Æt tªn lµ demo.train, demo.test, vµ demo.pred. Tªn cña tr­êng ®Ých cho c©y nµy: nghÜa lµ tªn cña tr­êng mµ gi¸ trÞ cña nã ta muèn dù b¸o, ch¼ng h¹n, Book_buyer_p. Th«ng tin vÒ chi phÝ cã thÓ cã hoÆc kh«ng. Chó ý lµ cã hai kiÓu tr­êng cã thÓ lµm chËm qu¸ tr×nh häc cña c¸c m« h×nh c©y vµ kh«ng thÓ cung cÊp d÷ liÖu h÷u Ých: KiÓu ®Çu tiªn lµ c¸c tr­êng cã gi¸ trÞ duy nhÊt t¹i mçi b¶n ghi, sao cho sè c¸c gi¸ trÞ b»ng sè b¶n ghi, ch¼ng h¹n, sè thÎ b¶o hiÓm x· héi hay sè ID cña b¶n ghi. KiÓu thø hai lµ c¸c tr­êng cã cïng gi¸ trÞ trong tÊt c¶ c¸c b¶n ghi, nh­ng ®«i khi ®­îc xem lµ c¸c tr­êng h»ng. Bá ®i c¶ hai kiÓu tr­êng nµy nÕu cã thÓ tr­íc khi dïng tËp d÷ liÖu mÉu ®Ó cho mét c©y häc. Muèn vËy, §Çu tiªn, sö dông lÖnh Sumarize cña thùc ®¬n Analysis ®Ó nh×n vµo c¸c gi¸ trÞ tr­êng. C¸c tr­êng h»ng dÔ dµng nhËn biÕt bëi v× chóng cã ®é lÖch chuÈn (STD dev) lµ 0 (ngo¹i trõ c¸c x©u cã ®é lÖch chuÈn lµ 0 nh­ng l¹i kh«ng ph¶i lµ h»ng). Sau ®ã sö dông lÖnh Project/Dataset Transform ®Ó lo¹i bá c¸c tr­êng h»ng tõ tËp d÷ liÖu mÉu. Tãm l¹i ®Ó x©y dùng mét m« h×nh c©y, ta cÇn tiÕn hµnh theo c¸c b­íc sau: Häc (gi¸m s¸t): Sö dông tËp d÷ liÖu häc ®Ó t¹o ra c©y ph©n líp ®Çy ®ñ (m« h×nh) KiÓm tra/®¸nh gi¸: Sö dông tËp d÷ liÖu mÉu cho ®¸nh gi¸ ®Ó kiÓm tra ®¸nh gi¸ l¹i c©y vµ t×m ra th«ng tin vÒ tÇn suÊt lçi cña c¸c c©y con bÞ tØa. Dù b¸o: Víi c©y con ®· tØa vµ tËp d÷ liÖu cÇn dù b¸o, ta ®­a ra tËp d÷ liÖu ®· dù b¸o vµ chuyÓn sang b­íc ph©n tÝch. Ph©n tÝch: Ph©n tÝch c¸c kÕt qu¶ dïng cho quyÕt ®Þnh vµ ®­a ra th«ng tin vÒ hiÖu n¨ng cña c¸c c©y con ®­îc chän. 8.3 M¹ng n¬ron Darwin Trong môc nµy ta ®Ò cËp ®Õn kh¸i nhiÖm chung vÒ m¹ng n¬ron vµ kh¶o nghiÖm Darwin Net. 8.3.1 Giíi thiÖu chung vÒ m¹ng n¬ron §Ó h×nh dung mét c¸ch trùc gi¸c, ta xem xÐt viÖc nhí mét ng­êi quen nh­ thÕ nµo. TrÝ ãc cña ta l­u gi÷ mét l­îng d÷ liÖu lín vÒ ®­êng nÐt, mµu s¾c, sù chuyÓn ®éng, biÓu c¶m vµ nhiÒu thø kh¸c cña ®èi t­îng ®Ó nhËn d¹ng. Mét sè yÕu tè lµ râ rµng, nh­ng mét sè kh¸c l¹i bÞ mê, kh«ng nhËn thøc râ ®­îc vÒ chóng. Kh¶ n¨ng nhËn d¹ng phøc t¹p nµy liªn quan ®Õn c¸c liªn kÕt rÊt lín cña c¸c n¬ron trong n·o bé. Kh¸i niÖm vÒ c¸c liªn kÕt lín mµ ta gäi lµ nh©n tè nhËn biÕt vµ ®­êng ®i d÷ liÖu t¹o nªn c¬ së lý thuyÕt cho m¹ng n¬ron nh©n t¹o. Víi n·o bé, ch­a ai biÕt chÝnh x¸c m¹ng n¬ron ®¹t ®­îc kÕt qu¶ nh­ thÕ nµo, nh­ng cã thÓ biÕt r»ng chóng cã nh÷ng thµnh c«ng tuyÖt vêi trong ph¸t triÓn sù ph©n líp vµ dù b¸o c¸c m« h×nh trªn c¸c tËp d÷ liÖu lín. M¹ng n¬ron lµm viÖc víi c¸c côm vµ mÉu sù kiÖn th­êng theo c¸ch cã liªn kÕt phøc t¹p. Chóng th­êng gäi lµ c¸c c«ng cô “hép ®en”: D÷ liÖu ®i vµo mét ®Çu vµ dù b¸o ®­a ë ®Çu kia vµ toµn bé qu¸ tr×nh x¶y ra kh«ng cÇn hiÓu biÕt nhiÒu tÝnh to¸n phøc t¹p x¶y ra bªn trong. M¹ng n¬ron bao gåm c¸c ®¬n vÞ xö lý n¬ron vµ c¸c liªn kÕt kÕt nèi c¸c ®¬n vÞ nµy l¹i. C¸ch c¸c ®¬n vÞ xö lý tr¶ lêi c¸c th«ng tin nhËn ®­îc ®­îc x¸c ®Þnh bëi c¸c hµm kÝch ho¹t (activation function). Søc m¹nh cña c¸c liªn kÕt gi÷a hai ®¬n vÞ ®­îc x¸c ®Þnh b»ng träng sè. Sè ®¬n vÞ xö lý, lo¹i liªn kÕt, kiÓu hµm kÝch ho¹t vµ c¸c träng sè trong m¹ng n¬ron lµ thÓ hiÖn c¸c ®Æc tr­ng trong xö lý th«ng tin cña chóng. M¹ng n¬ron Darwin cã thÓ xö lý c¶ c¸c bµi to¸n ph©n líp nhÞ ph©n vµ ph©n líp nhiÒu líp. Chóng còng cã thÓ xö lý c¸c bµi to¸n håi qui hoÆc dù b¸o mµ trong ®ã gi¸ trÞ ®Ých lµ “liªn tôc” (ch¼ng h¹n, gi¸ trÞ cã thÓ lµ mét sè bÊt kú ë trong kho¶ng 1vµ 1000000). 8.3.1.1 C¬ së vÒ m¹ng n¬ron Darwin triÓn khai mét cÊu tróc m¹ng n¬ron, trong ®ã c¸c ®¬n vÞ ®­îc cÊu tróc theo tõng líp nh­ sau: Líp ®Çu tiªn lµ líp ®Çu vµo. Nã bao gåm mét nót (hoÆc mét ®¬n vÞ) cho mçi tr­êng ®éc lËp trong b¶n ghi. Líp cuèi cïng lµ líp ®Çu ra, cã thÓ bao gåm nhiÒu nót ra. Trong bµi to¸n håi qui, ®iÒu nµy nghÜa lµ mét nót ®Çu ra ®¬n dù b¸o gi¸ trÞ cña mét tr­êng ®Ých. Bµi to¸n ph©n líp nhÞ ph©n sö dông mét nót ra ®Ó ph©n biÖt gi÷a hai gi¸ trÞ (0 vµ1 hay d­¬ng vµ ©m) cña mét tr­êng ®Ých ®­îc ph©n t¸ch. C¸c tr­êng ®­îc ph©n t¸ch víi nhiÒu gi¸ trÞ ®ßi hái mét nót cho gi¸ trÞ cÇn ®­îc dù b¸o vµ m¹ng n¬ron Darwin t¸ch c¸c tr­êng ®a gi¸ trÞ thµnh c¸c tr­êng nhÞ ph©n, mçi tr­êng øng víi mét gi¸ trÞ cÇn ®­îc dù b¸o. C¸c líp n»m gi÷a líp vµo vµ líp ra gäi lµ líp Èn. §©y lµ n¬i c¸c c«ng viÖc nhËn d¹ng, ph©n líp vµ dù b¸o diÔn ra. C¸c hµm kÝch ho¹t liªn kÕt víi tõng ®¬n vÞ xö lý bªn trong c¸c líp Èn vµ líp ®Çu ra. C¸c líp ®­îc kÕt nèi ®Çy ®ñ víi nhau, nghÜa lµ, mçi mét nót trong líp 1 nèi tíi mäi nót trong líp 2, mçi nót trong líp 2 nèi tíi mäi nót trong líp 3 vµ vv. X©y dùng mét m« h×nh m¹ng n¬ron liªn quan ®Õn viÖc t¹o ra mét cÊu tróc m¹ng ban ®Çu, cho m¹ng häc dùa trªn tËp d÷ liÖu häc vµ kiÓm tra/®¸nh gi¸ hiÖu n¨ng dùa trªn mét tËp d÷ liÖu kh¸c. X©y dùng m¹ng lµ mét qu¸ tr×nh lÆp tõng b­íc. Khi ®· x©y dùng ®­îc m« h×nh, Darwin ®Æt c¸c b¶n ghi míi vµo líp ®Çu vµo vµ lµm dù b¸o cho líp d÷ liÖu míi th«ng qua c¸c tÝnh to¸n bªn trong cña m¹ng. 8.3.2 Tuú chän: X©y dùng mét m« h×nh m¹ng X©y dùng mét m« h×nh m¹ng nghÜa lµ thiÕt kÕ t«p« (h×nh d¸ng vµ kÝch th­íc) cña nã. C¸c tham sè liªn quan ®Õn x©y dùng m¹ng lµ sè líp Èn vµ kÝch th­íc (sè nót t¹i mçi líp), c¸c hµm kÝch ho¹t vµ träng sè. Trªn giao diÖn ng­êi dïng cña Darwin, c¸c tham sè nµy n»m trong hép tho¹i Advanced Options, Net Build. 8.3.2.1 C¸c líp M« h×nh m¹ng cã mét líp ®Çu vµo, mét líp ®Çu ra vµ th«ng th­êng cã mét (cã thÓ nhiÒu h¬n) líp Èn. §èi víi mçi mét líp, ta cÇn ph¶i chØ ra sè ®¬n vÞ. Líp vµo: Sè ®¬n vÞ t¹i líp ®Çu vµo lµ sè biÕn ®éc lËp trong tËp d÷ liÖu. Líp Èn: Sè ®¬n vÞ trong líp Èn ngÇm ®Þnh lµ cïng sè víi líp ®Çu vµo. Darwin cho phÐp tù ®éng chän kÝch th­íc tèi ­u cho líp Èn. Líp ®Çu ra: Líp ®Çu ra t­¬ng øng víi c¸c tr­êng ®Ých. Sè ®¬n vÞ trong líp ®Çu ra cÇn ph¶i b»ng sè c¸c tr­êng ®Ých. Sè ®¬n vÞ ®Çu vµo céng víi sè ®¬n vÞ ®Çu ra cÇn ph¶i b»ng sè tr­êng trong tËp d÷ liÖu. 8.3.2.2 Hµm kÝch ho¹t Darwin cã ba hµm kÝch ho¹t: xÝch ma (sigmoid), siªu tiÕp tuyÕn (hypertangent) vµ tuyÕn tÝnh. C¸c hµm kÝch ho¹t dïng cho c¸c líp Èn vµ líp ®Çu ra. Mét nguyªn t¾c tuy th« s¬ nh­ng kh¸ tèt dïng cho c¸c bµi to¸n håi qui lµ sö dông hµm tuyÕn tÝnh cho líp ®Çu ra vµ hµm xÝch ma cho c¸c líp Èn. §èi víi bµi to¸n ph©n líp, ta sö dông hµm xÝch ma cho c¶ líp Èn, lÉn líp ®Çu ra. Líp ®Çu ra: Hµm xÝch ma lµ ngÇm ®Þnh. Sö dông hµm xÝch ma hay siªu tiÕp tuyÕn cho c¸c bµi to¸n ph©n líp, sö dông tuyÕn tÝnh cho c¸c bµi to¸n håi qui tuyÕn tÝnh; sö dông bÊt kú hµm nµo cho c¸c bµi to¸n håi qui phi tuyÕn. Líp Èn: Hµm xÝch ma lµ ngÇm ®Þnh. §èi víi m« h×nh phi tuyÕn, viÖc chän hµm kÝch ho¹t Èn phô thuéc vµo d÷ liÖu. Ta cã thÓ cÇn ph¶i thö c¶ hµm xÝch ma vµ siªu tiÕp tuyÕn ®Ó xem c¸i nµo lµm viÖc tèt. 8.3.2.3 Träng sè Träng sè ph¶n ¸nh tÇm quan träng t­¬ng ®èi cña c¸c liªn kÕt gi÷a c¸c nót m¹ng. Mçi liªn kÕt ®­îc g¾n mét träng sè. Gi¸ trÞ träng sè n»m trong kho¶ng tõ –x ®Õn +x. Lóc b¾t ®Çu cho m¹ng häc, Darwin cung cÊp mét tËp ngÇm ®Þnh c¸c träng sè n»m gi÷a –1 vµ 1. ViÖc d¹y m¹ng häc nghÜa lµ chuyÓn d÷ liÖu th«ng qua m¹ng, ®iÒu chØnh c¸c träng sè qua mçi b­íc. KÕt qu¶ cña viÖc d¹y m¹ng lµ mét tËp c¸c träng sè ®­îc sö dông trong tÝnh to¸n dù b¸o sau nµy. 8.3.3 Tuú chän d¹y m« h×nh m¹ng häc C¸c tham sè ¶nh h­ëng ®Õn m¹ng häc lµ c¸ch häc, thuËt to¸n häc, hµm chi phÝ vµ sè lÇn lÆp. Trªn giao diÖn ng­êi dïng cña Darwin, c¸c tham sè nµy ®­îc ®Æt trªn hép tho¹i Advanced Options, Net Train. 8.3.3.1 C¸ch häc Ta cã thÓ d¹y cho m« h×nh m¹ng n¬ron häc sö dông mét trong ba c¸ch sau: Häc vµ KiÓm tra (Train and Test), x¸c nhËn chÐo (Cross-Validation) vµ Häc ®¬n gi¶n (Simple Training): Train and Test lµ ngÇm ®Þnh vµ ®­îc thùc hiÖn ®ång thêi sö dông hai tËp d÷ liÖu hoÆc hai phÇn cña mét tËp d÷ liÖu. C¸ch nµy rÊt thuËn tiÖn tr¸nh ®­îc viÖc häc kh«ng ®Çy ®ñ khi tËp d÷ liÖu lÞch sö t­¬ng ®èi nhá. NÕu ta cã hai tËp d÷ liÖu hoÆc hai phÇn cña mét tËp d÷ liÖu th× còng cÇn ®­îc chØ râ phÇn nµo ®Ó häc vµ phÇn nµo ®Ó kiÓm tra. Train and Test s¶n sinh ra mét b¶ng hiÓn thÞ c¸c sai sãt häc vµ sai sãt kiÓm tra. Gi¸ trÞ hiÓn thÞ lµ sai sè ®é lÖch b×nh ph­¬ng. ë ®©y cã thÓ cã mét chót ph©n biÖt víi bµi to¸n ph©n líp nhÞ ph©n do viÖc sai sè ®é lÖch qu©n ph­¬ng lµ c¨n bËc hai cña sai sè ph©n líp. Cross-Validation sö dông viÖc triÓn khai hiÖu qu¶ x¸c nhËn chÐo hai ®o¹n ®Ó hç trî qu¸ tr×nh häc. Trong viÖc x¸c nhËn chÐo, Darwin sö dông c¸c tËp d÷ liÖu (hoÆc mét phÇn tËp d÷ liÖu) cho häc vµ kiÓm tra. NghÜa lµ, ®Çu tiªn nã d¹y víi A vµ kiÓm tra víi B, sau ®ã d¹y víi B vµ kiÓm tra víi A. Sau ®ã nã lÊy trung b×nh cña hai kÕt qu¶ ®Ó x¸c ®Þnh tÇn suÊt sai sãt. Khi lµm viÖc víi sè l­îng d÷ liÖu qu¸ nhá ®Ó t¸ch chóng thµnh ba phÇn, th× th«ng th­êng mét chiÕn l­îc tèt lµ sö dông x¸c nhËn chÐo tr­íc ®Ó kiÓm tra c¸c cÊu tróc m¹ng kh¸c nhau vµ sau ®ã sö dông Train and Test ®Ó d¹y thªm n÷a nh»m t¹o ra m« h×nh nhiÒu høa hÑn nhÊt. Simple Training d¹y cho m¹ng mét c¸ch ®¬n gi¶n víi mét sè lÇn lÆp cô thÓ. Trong qu¸ tr×nh häc, Darwin hiÓn thÞ sè vßng lÆp ®· hoµn thµnh vµ tÇn suÊt sai sè hiÖn thêi. NÕu ta sö dông Simple Training, ta cÇn ph¶i kiÓm tra m¹ng mét c¸ch riªng rÏ. 8.3.3.2 ThuËt to¸n häc Darwin sö dông 5 thuËt to¸n häc bao gåm: Modified Newton (Newton c¶i tiÕn) Conjugate gradient (gradient liªn hîp) Steepest descent (Dèc ®øng) Backpropagation (Lan truyÒn ng­îc) Genetic algorithm (thuËt to¸n di truyÒn) Gradient liªn hîp vµ Newton c¶i tiÕn lµ c¸c thuËt to¸n siªu tuyÕn tÝnh. Nh×n chung, chóng ®Òu héi tô (nghÜa lµ ®¹t tíi ®iÓm kÕt thóc) nhanh h¬n nhiÒu so víi Lan truyÒn ng­îc vµ Dèc ®øng, nh­ng chóng cÇn c¸c ®iÓm b¾t ®Çu tèt. Víi hÇu hÕt c¸c tËp d÷ liÖu, c¸c thuËt to¸n Gradient liªn hîp vµ Newton c¶i tiÕn héi tô nhanh h¬n c¸c thuËt to¸n kh¸c. Lan truyÒn ng­îc vµ Dèc ®øng sÏ lu«n héi tô tíi mét tèi thiÓu nµo ®ã bÊt kÓ chóng xuÊt ph¸t tõ ®©u. Lan truyÒn ng­îc lµ thuËt to¸n ®¬n gi¶n vµ chËm nhÊt trong c¸c thuËt to¸n dùa vµo gradient. Tèc ®é héi tô cña nã lµ tuyÕn tÝnh. Dèc ®øng gièng nh­ Lan truyÒn ng­îc nh­ng chØ kh¸c ë chç nã t×m kiÕm ®­êng ®Ó x¸c ®Þnh kÝch th­íc b­íc. ThuËt to¸n häc cuèi cïng lµ thuËt to¸n Di truyÒn. ThuËt to¸n Di truyÒn lu«n cã thÓ t×m ®­îc cùc tiÓu bÐ nhÊt. Nh­ng kh¸c víi bÊt kú thuËt to¸n t×m cùc tiÓu bÐ nhÊt nµo, nã cã thÓ cã chi phÝ thêi gian thùc hiÖn lín. Nguyªn t¾c th« cho viÖc chän mét thuËt to¸n häc lµ nh­ sau: §Çu tiªn, thö dïng Gradient liªn kÕt hoÆc Newton c¶i tiÕn do chóng héi tô nhanh. NÕu thuËt to¸n kh«ng héi tô, ta cÇn t×m c¸ch kh¸c: Sö dông lÖnh Transform/Randomize ®Ó cung cÊp mét ®iÓm xuÊt ph¸t míi cho thuËt to¸n hiÖn thêi, hoÆc, Thö dïng Lan truyÒn ng­îc hoÆc Dèc ®øng ®Ó b¾t ®Çu vµ sau ®ã tiÕp tôc víi thuËt to¸n ban ®Çu NÕu ta vÉn kh«ng tho¶ m·n víi kÕt qu¶, th× ®Õn víi thuËt to¸n Di truyÒn. NÕu ta chän Lan truyÒn ng­îc hoÆc ThuËt to¸n Di truyÒn, ta cÇn ph¶i chØ ra tÇn suÊt häc cho qu¸ tr×nh häc. 8.3.3.3 Hµm chi phÝ Darwin sö dông ba hµm chi phÝ nh­ sau: B×nh ph­¬ng: B×nh ph­¬ng lµ hµm ®­îc ngÇm ®Þnh sö dông ®­îc dïng cho bµi to¸n håi qui vµ còng cã thÓ sö dông cho bµi to¸n ph©n líp. Entropy ng­îc: Th­êng dïng cho bµi to¸n ph©n líp lµ tèt nhÊt Pnorm: §©y lµ hµm p-norm chuÈn vÒ sù kh¸c nhau gi÷a c¸c gi¸ trÞ m« h×nh vµ dù b¸o ®­îc. NÕu ta chän pnorm, cÇn chØ ra gi¸ trÞ p. Gi¸ trÞ ngÇm ®Þnh lµ 2. Víi gi¸ trÞ nµy, pnorm trë thµnh b×nh ph­¬ng. 8.3.3.4 B­íc lÆp ChØ ra sè b­íc lÆp dïng ®Ó d¹y cho m¹ng. Gi¸ trÞ ngÇm ®Þnh lµ 100. §©y lµ sè thêi gian Darwin sÏ chuyÓn d÷ liÖu qua m¹ng ®Ó d¹y häc. Ta cã thÓ b¾t ®Çu víi mét sè b­íc nhá (10 hoÆc 20), kiÓm tra kÕt qu¶ sau ®ã hoÆc t¹o ngay m« h×nh míi, tiÕp tôc thªm qu¸ tr×nh lÆp hay b¾t ®Çu l¹i qu¸ tr×nh häc xuÊt ph¸t tõ ®iÓm b¾t ®Çu míi. Ta cã thÓ yªu cÇu sè lÇn lÆp lín h¬n (100 hoÆc h¬n), quan s¸t tÇn suÊt lçi khi Darwin lµm viÖc vµ bÊm Stop trªn thùc ®¬n Project nÕu muèn ng¾t qu¸ tr×nh l¹i. Khi ta dïng Stop, Darwin kh«ng dõng ngay mµ nã hoµn thµnh nèt b­íc dë dang vµ ®­a ra kÕt qu¶ dùa trªn nh÷ng lÇn lÆp ®· thùc hiÖn Víi bÊt cø chiÕn l­îc nµo ®uîc chän, Darwin dõng viÖc häc m« h×nh khi ®· ®¹t tíi sè phÐp lÆp cho tr­íc hoÆc khi dß ®­îc ®iÓm dõng t¹i ®ã tÇn suÊt sai sãt ®· ®¹t ®­îc tèi thiÓu vµ b¾t ®Çu t¨ng. 8.3.3.5 TiÕp tôc d¹y häc cho m« h×nh m¹ng Cã thÓ cã nh÷ng t×nh huèng ta cÇn tiÕp tôc d¹y häc cho mét m« h×nh m¹ng ®· häc råi. Ch¼ng h¹n, ta ®· chØ ra mét sè b­íc lÆp ®Ó häc vµ ®Õn cuèi cïng ta thÊy tÇn suÊt sai sãt vµ kiÓm tra vÉn cßn ®ang gi¶m, nghÜa lµ m« h×nh vÉn ch­a ®¹t tíi tr¹ng th¸i tèt nhÊt. NÕu ta muèn tiÕp tôc d¹y cho m¹ng, th× sÏ ph¶i sö dông tuú chän Perturb. 8.3.4 D¹y l¹i mét m« h×nh m¹ng Khi Darwin t¹o ra mét m« h×nh m¹ng n¬ron, nã ¸nh x¹ c¸c ®iÓm t×m kiÕm vµo kh«ng gian n chiÒu, tèi thiÓu sù kh¸c nhau gi÷a gi¸ trÞ thùc vµ gi¸ trÞ tÝnh to¸n cña d÷ liÖu. BiÓu diÔn qu¸ tr×nh häc cã thÓ ®­îc h×nh dung bao gåm c¸c ®iÓm ®Ønh vµ thung lòng víi ®Ønh lµ c¸c møc kh¸c nhau cao vµ thung lòng lµ møc thÊp. §iÓm mµ Darwin cÇn t×m lµ thung lòng thÊp nhÊt tøc lµ cùc tiÓu toµn thÓ chø kh«ng ph¶i cùc tiÓu ®Þa ph­¬ng. Trong mét sè tr­êng hîp, m¹ng cã thÓ bÞ”m¾c kÑt” t¹i ®iÓm cùc tiÓu ®Þa ph­¬ng trong qu¸ tr×nh häc vµ nh­ vËy m¹ng t¹o ra sÏ cã hiÖu n¨ng ngÌo nµn. Trong tr­êng hîp ®ã, ta cã ba lùa chän: t¹o ra mét m¹ng víi cÊu tróc kh¸c, thö mét thuËt to¸n häc kh¸c nh­ ®· nªu trong phÇn 8.5.3 hoÆc d¹y l¹i m¹ng sö dông mét tËp c¸c träng sè b¾t ®Çu kh¸c. 8.3.4.1 D¹y l¹i KÕt qu¶ viÖc häc cña m¹ng lµ mét tËp c¸c träng sè ®­îc sö dông trong tÝnh to¸n x¸c ®Þnh dù b¸o. M¹ng häc l¹i nghÜa lµ mét m¹ng míi ®­îc x©y dùng víi träng sè khëi ®Çu míi. Ta cã thÓ chän c¸ch thay ®æi trùc tiÕp c¸c träng sè b»ng c¸ch tr­ît gi÷a kho¶ng 0 vµ 1, trong ®ã 0 nghÜa lµ kh«ng cã thay ®æi vµ träng sè cò vÉn ®­îc dïng. 8.3.4.2 Thay ®æi träng sè (perturbation) Cã hai t×nh huèng dÉn ®Õn viÖc ta ph¶i can thiÖp vµo viÖc thay ®æi träng sè: Cho m¹ng häc l¹i sö dông c¸c träng sè khëi ®Çu kh¸c trong tr­êng hîp ta ®· chän ®­îc c¸c tham sè tèt nh­ng ta l¹i kh«ng tho¶ m·n víi hiÖu n¨ng cña m« h×nh vµ kh«ng muèn x©y dùng mét c¸i míi víi mét t«p« kh¸c. Cã thÓ ta cßn chót b¨n kho¨n r»ng Darwin cã thÓ t×m ra mét tèi thiÓu ®Þa ph­¬ng mµ kh«ng ph¶i lµ tèi thiÓu tuyÖt ®èi cña tÇn suÊt lçi. Sù thay ®æi nhá vÒ träng sè cã thÓ cho phÐp Darwin t×m ra mét tèi thiÓu míi tèt h¬n. ViÖc t¾c nghÏn trong tèi thiÓu ®Þa ph­¬ng lµ ®iÒu cã thÓ trong c¸c thuËt to¸n häc hiÖn nay. ChØ cã thuËt to¸n di truyÒn lu«n cã thÓ t×m ra tèi thiÓu tuyÖt ®èi nh­ng l¹i cã chi phÝ thêi gian lín. 8.3.5 Qu¸ tr×nh x©y dùng m« h×nh Qu¸ tr×nh t¹o ra m¹ng n¬ron diÔn ra theo hai b­íc, ta x¸c ®Þnh cÊu tróc cña m¹ng sau ®ã d¹y m¹ng sö dông mét trong c¸cc c¸ch hcä ®· nªu trong môc 8.5.3.1. ViÖc m¹ng häctiÕn hµnh b»ng c¸ch cho d÷ liÖu chuyÓn qua nhiÒu lÇn vµ c¸c träng sè ®­îc Darwin ®iÒu chØnh sau mçi lÇn. 8.3.5.1 Khëi ®éng §Ó b¾t ®Çu dù b¸o ph©n líp dïng m¹ng n¬ron, ta cÇn chuÈn bÞ c¸c vÊn ®Ò sau ®©y: C©u hái cÇn tr¶ lêi víi c¸c mÖnh ®Ò, sao cho c©u tr¶ lêi lµ gi¸ trÞ cña tr­êng ®Ých cho mçi b¶n ghi. D÷ liÖu lÞch sö ®· ®­îc ph©n líp tr­íc C¸c b¶n ghi trong tËp d÷ liÖu häc cÇn theo thø tù ngÉu nhiªn (sö dông lÖnh Randomize). Lý do ph¶i ngÉu nhiªn lµ v× thø tù thÓ hiÖn trong c¸c b¶n ghi cã thÓ ¶nh h­ëng ®Õn sù héi tô cña c¸c thuËt to¸n häc. C¸c m« h×nh m¹ng ®ßi hái c¸c d÷ liÖu ®­îc chuÈn ho¸ vµ Darwin cã thÓ chuÈn ho¸ d÷ liÖu tù ®éng. Th­êng ta cã thÓ chia nguån d÷ liÖu thµnh ba phÇn cho häc, kiÓm tra vµ dù b¸o. Sö dông lÖnh Transform/Split ®Ó t¸ch c¸c nhãm d÷ liÖu nµy. LÖnh Randomize ®ù¬c thùc hiÖn tr­íc lÖnh Split. Tuy vËy, nÕu ta chØ cã sè l­îng d÷ liÖu nhá, ta cã thÓ chia chóng thµnh hai phÇn. Mét phÇn dµnh cho c¶ häc vµ kiÓm tra, phÇn cßn l¹i dµnh cho dù b¸o. Tuú chän x¸c nhËn chÐo lµ h÷u Ých trong tr­êng hîp nµy. Tªn cña tr­êng ®Ých cÇn ®­îc x¸c ®Þnh. §èi víi bµi to¸n håi qui, c¸c gi¸ trÞ tr­êng ®Ých cÇn ®­îc s¾p xÕp tr­íc. §èi víi bµi to¸n ph©n líp, ta cÇn ph¶i cã mét hay nhiÒu tr­êng nhÞ ph©n ®­îc chuyÓn ®æi tõ tr­êng nhiÒu líp. Sau ®©y lµ tãm t¾t c¸c b­íc ®Ó x©y dùng mét m¹ng n¬ron sö dông Darwin: T¹o ra cÊu tróc m¹ng n¬ron Häc vµ kiÓm tra (Train and Test) víi tËp d÷ liÖu häc vµ tËp d÷ liÖu kiÓm tra. Qua b­íc nµy ta sÏ thu nhËn ®­îc mét m« h×nh m¹ng n¬ron ®· häc tho¶ m·n c¸c yªu cÇu vÒ hiÖu n¨ng. Sö dông m¹ng n¬ron ®· häc dïng vµo viÖc dù b¸o. TËp d÷ liÖu sau khi dù b¸o sÏ dïng ®Ó ph©n tÝch kÕt qu¶ vµ ®­a ra th«ng tin vÒ hiÖu n¨ng cña m¹ng. 8.4 M« h×nh ®èi s¸nh Darwin (Darwin Match) PhÇn nµy ta sÏ giíi thiÖu chung vÒ c¸c m« h×nh ®èi s¸nh vµ m« h×nh ®èi s¸nh Darwin còng nh­ sù thùc hiÖn cô thÓ cña nã. 8.4.1 Giíi thiÖu chung vÒ m« h×nh ®èi s¸nh sö dông ë ®©y M« h×nh ®èi s¸nh Darwin thùc hiÖn viÖc ph©n líp vµ dù b¸o nhê suy diÔn cã nhí (MBR) víi thuËt to¸n k ng­êi l¸ng giÒng gÇn nhÊt. M« h×nh ®èi s¸nh Darwin cã thÓ gi¶i c¸c bµi to¸n ph©n líp vµ dù b¸o nhiÒu líp. Trong sè tÊt c¶ c¸c m« h×nh Darwin, ®©y lµ m« h×nh sö dông hiÖu qu¶ nhÊt c¸c d÷ liÖu trong mét tËp d÷ liÖu. C¸c m« h×nh ®èi s¸nh Darwin rÊt tiÖn dông trong xö lý c¸c d÷ liÖu mang tÝnh ®Æc thï cao. Chóng cã thÓ ph¸t hiÖn ra c¸c mÉu d÷ liÖu nèi côm, nghÜa lµ chóng ®Þnh vÞ ®­îc c¸c “èc ®¶o” riªng trong khi c¸c m« h×nh kh¸c chØ chØ ra ®­îc xu h­íng. Suy diÔn cã nhí so s¸nh mét b¶n ghi míi trùc tiÕp víi c¸c b¶n ghi ®· biÕt xem c¸c ®Æc tÝnh cña chóng cã gÇn gièng nhau kh«ng sö dông mét ®é ®o kho¶ng c¸ch cã träng sè. Hai nh©n tè quan träng lµ sè phÇn tö kÒ bªn (hµng xãm) vµ ®Æc tr­ng cña chóng. Nguêi dïng cã thÓ quyÕt ®Þnh cã bao nhiªu hµng xãm (gi¸ trÞ cña k) hoÆc lÊy gi¸ trÞ ngÇm ®Þnh cña Darwin lµ 2. Darwin x¸c ®Þnh c¸c träng sè ®i kÌm víi mçi biÕn vµ nh­ vËy x¸c ®Þnh ®­îc ®Æc tr­ng cña hµng xãm. 8.4.2 M« h×nh ®èi s¸nh Darwin lµm viÖc nh­ thÕ nµo? Sau ®©y lµ mét vÝ dô ®¬n gi¶n minh ho¹ M« h×nh ®èi s¸nh Darwin lµm viÖc nh­ thÕ nµo. Mçi b¶n ghi cã 4 tr­êng: ID (#), Tuæi, Thu nhËp vµ Sè d­. C¸c b¶n ghi trong tËp d÷ liÖu lÞch sö nh­ sau: # Tuæi Thu nhËp Sè d­ . . . 1 67 480,000 20,000,000 . . . 2 23 1,800,000 4,000,000 . . . 3 52 700,000 12,000,000 . . . B¶n ghi míi lµ: # Tuæi Thu nhËp Sè d­ . . . 4 54 650,000 18,400,000 . . . §Ó t×m nh÷ng ng­êi l¸ng giÒng gÇn nhÊt cho b¶n ghi thø 4, ta so s¸nh gi¸ trÞ trong mçi tr­êng víi gi¸ trÞ t­¬ng øng cña c¸c b¶n ghi kh¸c. Sau ®ã gép tÊt c¶ c¸c kh¸c nhau ®Ó x¸c ®Þnh mét “kho¶ng c¸ch” gi÷a hai b¶n ghi. Ta thÊy ngay ba b¶n ghi cã hai chiÒu t­¬ng ®èi gÇn nhau vµ nh­ vËy lµ “c¸c xãm giÒng gÇn”: 1 67 480,000 20,000,000 . . . gÇn nhÊt 4 54 650,000 18,400,000 . . . Míi 3 52 700,000 15,000,000 . . . gÇn nhÊt thø hai vµ mét b¶n ghi cã kho¶ng c¸ch xa h¬n vµ nh­ vËy Ýt thuËn lîi cho dù b¸o: 2 23 1,800,000 4,000,000 . . . Nh­ng ta còng biÕt r»ng kh«ng ph¶i tÊt c¶ c¸c tr­êng ®Òu thuËn tiÖn cho dù b¸o hµnh vi. Víi c¸c hµnh vi liªn quan ®Õn tuæi vµ thu nhËp, b¶n ghi thø ba lµ gÇn nhÊt víi b¶n ghi thø 4. Víi c¸c hµnh vi liªn quan ®Õn tiÒn nî vµ tiÒn göi th× b¶n ghi ®Çu tiªn lµ gÇn nhÊt. C¸c tr­êng còng kh«ng ®­a ra cïng mét kh¶ n¨ng vÒ kho¶ng c¸ch. Ch¼ng h¹n tuæi kh«ng thay ®æi nhanh chãng nh­ thu nhËp vµ tiÒn göi. Khi ®· x¸c ®Þnh c¸ch tÝnh kho¶ng c¸ch, Darwin tù ®éng bï trõ ®Ó cho c¸c kh¸c nhau nµy phï hîp khi tÝnh to¸n kho¶ng c¸ch. Nh­ vËy, kho¶ng c¸ch ®­îc tÝnh chÝnh lµ sù kh¸c nhau vÒ gi¸ trÞ cña tr­êng nh©n víi gi¸ trÞ träng sè nãi lªn tÇm quan träng cña tr­êng ®ã trong dù b¸o. Gi¸ trÞ träng sè nµy ®­îc Darwin tù tÝnh to¸n. C¸c tr­êng kh«ng cã gi¸ trÞ dù b¸o (ch¼ng h¹n, cã nèt ruåi ë c»m kh«ng liªn can ®Õn rñi ro tÝn dông) ®­îc lÊy träng sè lµ 0. C¸c tr­êng cã gi¸ trÞ nhá th­êng ®­îc lÊy träng sè nhá vµ c¸c tr­êng cã gi¸ trÞ lín ®­îc lÊy träng sè lín. C«ng thøc cho tÝnh to¸n “nh÷ng ng­êi l¸ng giÒng gÇn nhÊt” ®­îc tÝnh theo c«ng thøc sau: (Gi¸ trÞ kh¸c nhau cña tr­êng 1 * träng sè cho tr­êng 1) + (Gi¸ trÞ kh¸c nhau cña tr­êng 2 * träng sè cho tr­êng 2) +(Gi¸ trÞ kh¸c nhau cña tr­êng 3 * träng sè cho tr­êng 3) .... vµ cø thÕ tiÕp tôc..... ViÖc tèi ­u (®iÒu chØnh) sÏ dùa trªn d¹y mét m« h×nh ®èi s¸nh häc Mét sè qui ®Þnh tr­íc trong Darwin nh­ sau: §Ó xem c¸c b¶n ghi mµ Darwin ®· chän nh­ ng­êi l¸ng giÒng gÇn nhÊt khi lµm dù b¸o, chän lÖnh View Neighbors. NÕu d÷ liÖu ®­îc chuÈn ho¸ nghÜa lµ c¸c gi¸ trÞ n»m trong kho¶ng 0 vµ 1 th× kh«ng cÇn cã thªm ®iÒu chØnh nµo vÒ miÒn gi¸ trÞ n÷a. NÕu hai b¶n ghi trïng nhau th× kho¶ng c¸ch sÏ lµ 0. 8.4.3 Tuú chän tèi ­u m« h×nh ®èi s¸nh Cã ba tham sè cho phÐp tèi ­u m« h×nh. Chóng lµ träng sè, sè l­îng hµng xãm vµ ®Þnh h­íng kÕt qu¶. C¸c tham sè nµy ®­îc ®iÒu chØnh trong häp tho¹i Advanced Options/Match. 8.4.3.1 Träng sè Darwin ®· ngÇm ®Þnh mét tÖp träng sè, trong ®ã c¸c träng sè cã gi¸ trÞ gièng nhau. Ta cã thÓ tù t¹o ra tÖp träng sè nh­ sau: Dßng ®Çu tiªn cña tÖp nh­ sau: DARWIN(tm) MATCH WEIGHTS B¾t ®Çu tõ dßng tiÕp theo lµ danh s¸ch c¸c träng sè mµ cã gi¸ trÞ n»m trong kho¶ng 0 vµ 1. Mét träng sè t­¬ng øng víi mét tr­êng trong tËp d÷ liÖu m« h×nh ®­îc t¸ch biÖt bëi dÊu tr¾ng. Kh«ng cã khu«n d¹ng cho dßng cuèi cïng. Ta còng cã thÓ ®Ó Darwin tèi ­u c¸c träng sè nh»m c¶i thiÖn sù hiÖu qu¶ cña m« h×nh. 8.4.3.2 Chän sè c¸c hµng xãm Mét biÕn chñ chèt trong dù b¸o lµ sè c¸c hµng xãm gÇn nhÊt so víi d÷ liÖu cÇn dù b¸o (sè k). NÕu kh«ng chØ ra cô thÓ Darwin sÏ sö dông hai hµng xãm gÇn nhÊt vµ tÝnh to¸n x¸c suÊt cña dù b¸o. NÕu d÷ liÖu cã mËt ®é rÊt dµy, viÖc t¨ng sè hµng xãm kh«ng gióp g× nhiÒu. Nh­ng nÕu tËp d÷ liÖu lµ th­a, viÖc t¨ng sè hµng xãm cã thÓ sÏ rÊt h÷u Ých. KiÓu bµi to¸n còng ¶nh h­ëng ®Õn sè hµng xãm. Cã tr­êng hîp, c¸c hµng xãm gÇn cho phÐp ®é tin cËy cao khi dù b¸o, nh­ng trong nh÷ng tr­êng hîp kh¸c cã thÓ kh«ng ®­îc nh­ vËy. Tuy nhiªn, ta cã thÓ t¹o ra c¸c m« h×nh víi nhiÒu gi¸ trÞ sè hµng xãm kh¸c nhau ®Ó thö nghiÖm hiÖu n¨ng t­¬ng ®èi nµo sÏ lµ tèt nhÊt. Th«ng th­êng, gi¸ trÞ k trªn mét m« h×nh kho¶ng tõ 2 ®Õn 20. 8.4.3.3 §Þnh h­íng kÕt qu¶ Ta cã thÓ cho Darwin biÕt ®Þnh h­íng dù b¸o ®Õn ®Çu ra nµo ®ã nÕu muèn. Víi ®Þnh h­íng nh­ vËy, Darwin tÝnh to¸n c¸c träng sè cho c¸c tr­êng kh¸c nhau. §Þnh h­íng kh«ng b¾t buéc vµ cã thÓ sö dông c¸c ngÇm ®Þnh cña chóng cña øng dông. §Þnh h­íng ®­îc tÝnh theo c¸ch sau: 0 < ®Þnh h­íng < 0.5 thÓ hiÖn ®Þnh h­íng ©m Gi¸ trÞ 0.5 lµ trung tÝnh (ngÇm ®Þnh) 0.5 < ®Þnh h­íng < 1.0 thÓ hiÖn ®Þnh h­íng d­¬ng. Cã thÓ chän gi¸ trÞ ®Þnh h­íng trong c¸c t×nh h­íng sau: NÕu kÕt qu¶ d­¬ng sai tèn kÐm h¬n nhiÒu kÕt qu¶ ©m sai, th× ta nªn chän ®Þnh h­íng ©m. NÕu kÕt qu¶ ©m sai tèn kÐm h¬n nhiÒu kÕt qu¶ d­¬ng sai th× ta nªn chän ®Þnh h­íng d­¬ng. Khi kiÓm tra m« h×nh, thÊy s¶n sinh ra qu¸ nhiÒu ©m sai, ta ®Æt mét ®Þnh h­íng d­¬ng. Khi kiÓm tra m« h×nh, thÊy s¶n sinh ra qu¸ nhiÒu d­¬ng sai, ta ®Æt mét ®Þnh h­íng ©m. NÕu ta biÕt tr­êng nµo cÇn sö dông vµ muèn bá qua qu¸ tr×nh häc (tèi ­u träng sè), ta cã thÓ lµm dù b¸o víi Darwin dùa trªn thuËt to¸n k ng­êi l¸ng giÒng gÇn nhÊt mµ kh«ng nhÊt thiÕt ph¶i cã c¸c träng sè tèi ­u. Ta chØ cung cÊp tËp d÷ liÖu lÞch sö vµ mét tËp d÷ liÖu míi cho lÖnh Predict with Match. Sau ®ã, Darwin sö dông d÷ liÖu lÞch sö ®Ó t×m c¸c “hµng xãm” cho d÷ liÖu míi. 8.4.3.3 Qu¸ tr×nh x©y dùng m« h×nh §Ó x©y dùng mét m« h×nh ®èi s¸nh, ta cÇn b¾t ®Çu víi c¸c viÖc sau: Mét c©u hái mµ ta cÇn lêi gi¶i ®­îc chia thµnh c¸c mÖnh ®Ò sao cho c©u tr¶ lêi lµ gi¸ trÞ cña mét tr­êng ®¬n (tr­êng ®Ých) víi mçi b¶n ghi d÷ liÖu. Mét nguån d÷ liÖu lÞch sö (nghÜa lµ c¸c d÷ liÖu ®· cã s½n c¸c gi¸ trÞ cña tr­êng ®Ých). Chia tËp d÷ liÖu Darwin thµnh ba tËp con: mét cho d÷ liÖu m« h×nh, mét cho tèi ­u vµ mét cho dù b¸o. NÕu tr­êng ®Ých lµ nhÞ ph©n th× cÇn chuÈn ho¸ d÷ liÖu. Sö dông lÖnh Randomize vµ Normalize tõ dataset/Transform tr­íc khi dïng lÖnh Split ®Ó chia. X¸c ®Þnh tªn cña tr­êng ®Ých mµ ta muèn dù b¸o. Sau ®©y lµ c¸c b­íc ®Ó x©y dùng m« h×nh ®èi s¸nh: X¸c ®Þnh tËp d÷ liÖu t¹o m« h×nh vµ gi¸ trÞ k ng­êi l¸ng giÒng gÇn nhÊt ®Ó t¹o m« h×nh ®èi s¸nh. Cho m« h×nh häc sö dông tËp d÷ liÖu häc ®Ó x¸c ®Þnh c¸c träng sè ®èi s¸nh tèi ­u. Dù b¸o víi m« h×nh ®­îc t¹o ra víi tËp d÷ liÖu dù b¸o KÕt qu¶ dù b¸o ®­îc ®­a vµo ph©n tÝch vµ ®­a ra th«ng tin hiÖu n¨ng cña m« h×nh. Trªn ®©y lµ mét sè t×m hiÓu ban ®Çu vÒ øng dông Oracle Darwin. Do khu«n khæ cña mét luËn v¨n, nªn ch­a cã dÞp ®i s©u vÒ c¸c vÊn ®Ò nh­ viÖc x¸c ®Þnh bµi to¸n nghiÖp vô, chuÈn bÞ d÷ liÖu cho khai ph¸, vµ ph©n tÝch kÕt qu¶ khai ph¸. Ngoµi ra, ë ®©y còng ch­a cã nh÷ng khai th¸c thö nghiÖm vµ ®¸nh gi¸ hiÖu qu¶ sö dông cña s¶n phÈm nµy. Tuy nhiªn, qua t×m hiÓu, hoµn toµn cã thÓ h×nh dung râ rµng h¬n vÒ kh¶ n¨ng thùc sù ¸p dông c¸c kü thuËt khai ph¸ d÷ liÖu, còng nh­ tiÒm n¨ng øng dông to lín cho s¶n phÈm nµy trong thùc tÕ hiÖn nay t¹i ViÖt nam. KÕt luËn Tãm l¹i, khai ph¸ d÷ liÖu bao gåm mét tËp c¸c kü thuËt cho phÐp truy cËp d÷ liÖu bªn trong CSDL ®Ó t×m ra c¸c th«ng tin d­íi d¹ng Èn. §Æc biÖt, trong c¸c CSDL lín, ®iÒu v« cïng quan träng lµ lµm thÕ nµo läc ra th«ng tin thÝch hîp, chÝnh x¸c vµ h÷u dông mµ khã cã thÓ t×m ra ®­îc b»ng c¸c c«ng cô SQL truyÒn thèng. Ngoµi viÖc ph¸t hiÖn ®­îc c¸c th«ng tin nh­ vËy, c¸c kü thuËt khai ph¸ d÷ liÖu ph¶i gi¶i quyÕt ®­îc vÊn ®Ò hiÖu n¨ng khi quÐt mét sè lín d÷ liÖu trong thêi gian cho phÐp. H¬n n÷a, c«ng cô khai ph¸ d÷ liÖu chØ cã thÓ ph¸t huy tèt phôc vô cho yªu cÇu nghiÖp vô cña ng­êi dïng khi dùa trªn mét nÒn t¶ng m« h×nh d÷ liÖu ®­îc thiÕt kÕ tèt. Vµ kiÕn tróc kho d÷ liÖu cã thÓ ®¸p øng tèt nhÊt cho viÖc nµy. Do viÖc khai ph¸ d÷ liÖu kh«ng nh÷ng cÇn ®Õn c¸c d÷ liÖu ®ang thay ®æi, mµ cßn c¸c d÷ liÖu lÞch sö, nªn mét liªn kÕt ®éng ®èi víi c¸c nguån d÷ liÖu cña c¸c hÖ thèng t¸c nghiÖp hµng ngµy vµ d÷ liÖu bªn ngoµi còng lµ vÊn ®Ò quan träng. Do vËy, ta thÊy ë ®©y qu¸ tr×nh chuÈn bÞ d÷ liÖu cña qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL (KDD) hÇu nh­ chÝnh lµ qu¸ tr×nh x©y dùng kho d÷ liÖu. LuËn v¨n ®· xÐt ®Õn 10 nhiÖm vô cña khai ph¸ d÷ liÖu vµ ®i s©u h¬n vÒ hai nhiÖm vô t­¬ng ®èi quan träng vµ cã tiÒm n¨ng ¸p dông réng r·i. §ã lµ ph©n líp dùa trªn c©y quyÕt ®Þnh vµ ph¸t hiÖn luËt kÕt hîp trong CSDL lín. Mét thùc nghiÖm ph¸t hiÖn luËt kÕt hîp sö dông thuËt to¸n Apriori cho thÊy tri thøc ®­a ra rÊt bæ Ých cho nghiªn cøu vµ øng dông. Qua kh¶o nghiÖm s¬ bé mét phÇn mÒm khai ph¸ d÷ liÖu Oracle Data Mining Suite, ta thÊy ®©y lµ phÇn mÒm t­¬ng ®èi hoµn chØnh, dùa trªn c¸c lý thuyÕt khai ph¸ d÷ liÖu hiÖn ®¹i vµ ®­îc thiÕt kÕ tèt, cã tÝnh kh¶ thi ®Ó ¸p dông ngay vµo khai ph¸ d÷ liÖu. Qua ®©y ta thÊy tiÒm n¨ng to lín cña c¸c kü thuËt khai ph¸ d÷ liÖu. Tuy nhiªn, ®Ó cã thÓ tiÕp tôc c¸c nghiªn cøu tiÕp theo còng nh­ x©y dùng mét hÖ thèng ph¸t hiÖn tri thøc trong CSDL cô thÓ, ch¾c ch¾n cßn cÇn nhiÒu thêi gian vµ c«ng søc trªn c¬ së nh÷ng ®iÒu thu ®­îc ë ®©y. LuËn v¨n còng muèn chØ ra mèi liªn quan gi÷a c¸c kiÕn thøc kh¸c nh­ C¬ së d÷ liÖu, kho d÷ liÖu, Thèng kª, TrÝ tuÖ nh©n t¹o, HÖ chuyªn gia, vv... LuËn v¨n nµy lµ khëi ®iÓm cña qu¸ tr×nh nghiªn cøu øng dông c¸c c«ng nghÖ tiªn tiÕn trong lÜnh vùc qu¶n lý th«ng tin hç trî quyÕt ®Þnh. Trªn c¬ së nµy, sÏ tiÕp tôc ph¸t triÓn theo mét sè h­íng sau: TiÕp tôc ®i s©u nghiªn cøu c¸c kü thuËt häc m¸y ®Ó t×m ra c¸c gi¶i ph¸p kü thuËt tèt trong lÜnh vùc ph¸t hiÖn tri thøc. Nghiªn cøu ¸p dông c¸c kü thuËt Khai ph¸ d÷ liÖu, ®Æc biÖt vÒ ph¸t hiÖn luËt kÕt hîp vµ c¸c nhiÖm vô kh¸c dùa trªn c¸c yªu cÇu thùc tÕ. Nghiªn cøu c¸c gi¶i thuËt Khai ph¸ d÷ liÖu trong m«i tr­êng ®a xö lý vµ song song. Nghiªn cøu vÒ c¸c kü thuËt ph©n ho¹ch d÷ liÖu, trong ®ã viÖc xö lý d÷ liÖu ®­îc thùc hiÖn song song trong c¸c ph©n ho¹ch vËt lý nh­ng vÉn lµ thèng nhÊt ë møc l«gic øng dông. CËp nhËt c¸c th«ng tin nghiªn cøu ¸p dông míi nhÊt trong lÜnh vùc Khai ph¸ d÷ liÖu. Nghiªn cøu kh¶ thi viÖc ¸p dông c¸c c«ng nghÖ Khai ph¸ d÷ liÖu ë ViÖt nam. Do thêi gian cã h¹n còng nh­ khu«n khæ cña mét luËn v¨n cao häc, luËn v¨n nµy ch¾c ch¾n cßn nhiÒu thiÕu sãt, rÊt mong ®­îc c¸c thÇy c« gi¸o vµ nh÷ng ai quan t©m nhËn xÐt, gãp ý. Xin tr©n träng c¶m ¬n Hµ néi – 10/2001 NguyÔn An Nh©n Tµi liÖu tham kh¶o [1] Alex A. Freitas, Generic, Set-oriented Primitives to Support Data-parallel Knowledge Discovery in Relational Database systems, 1997 [2] Alex A. Freitas’s PhD Thesis Generic, Set-oriented Primitives to Support Data-parallel Knowledge Discovery in Relational Database Systems. 1999 [3] Ali, K.; Manganaris, S.; and Srikant, R. Partial Classication using Association Rules. In Proc. of the 3rd Int'l Conference on Knowledge Discovery in Large Databases, Technical Report No. GIT CC 97 04, 1997 [4] Ashok Savasere, E. Ominccinski, S. Navathe An Efficient Algorithm for Mining Association Rules in Large Databases, Technical Report No. GIT CC 95 04, 1995 [5] Barry Devlin, Data Warehouse from Architecture to Implementation, Addison-Wesley Longman, MA, 1997 [6] Darwin Reference, Release 3.0.1, Thinking Machines Corp., 1998 [7] Nimrod Megiddo and Ramakrishnan Srikant, Discovering Predictive Association Rules, IBM Almaden Research Center, 1998 [8] Oracle Data Mining Solutions An Oracle white paper, Oracle Corporation, September 2000 [9] Oracle Data Mining Suite (Oracle Darrwin) Data Sheet, Oracle Corporation, September 2000 [10] Pieter Adriaans, Dolf Zantinge Data Mining, Syllogic, Addison-Wesley Longman, MA, 1998 [11] Rakesh Agrawal, John C. Shafer, IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120, Parallel Mining of Association Rules, 1995 [12] Rakesh Agrawal, Ramakrishnan Srikant, IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120, Fast Algorithms for Mining Association Rules, 1994 [13] Rakesh Agrawal, Tomasz Imielinski, and Arun Swami. Database mining: A performance perspective. IEEE Transactions on Knowledge and Data Engineering, 5(6):914{925, December 1993. Special Issue on Learning and Discovery in Knowledge-Based Databases. [14] Vò HuyÒn Trang, NguyÔn Thanh Thuû ThiÕt kÕ gi¶i thuËt ph©n líp song song dùa trªn c©y quyÕt ®Þnh, LuËn v¨n TN§H, Khoa CNTT, §HBK Hµ néi, 2001.