Đề 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

Mục đích của luận văn là nghiên cứu, tổng hợp kiến thức về khai phá dữ liệu trong khung nhìn của quá trình phát hiện tri thức đồng thời, chú ý đến dự báo phân lớp nhờ kỹ thuật cây quyết định và đặc biệt đi sâu tìm hiểu nhiệm vụ phát hiện luật kết hợp trong cơ sở dữ liệu lớn. Luận văn gồm các nội dung chính như sau: Chương 1 giới thiệu chung về lĩnh vực khai phá dữ liệu và mô tả quá trình phát hiện tri thức trong cơ sở dữ liệu. Chương 2 xét đến 10 nhiệm vụ của Khai phá dữ liệu. Chương 3 trình bày các kỹ thuật khai phá dữ liệu. Chương 4 trình bày về kho dữ liệu, kiến trúc và các khía cạnh thiết kế kho dữ liệu. Chương 5 đi sâu hơn về nhiệm vụ phân lớp dựa trên cây quyết định. Chương 6 giới thiệu các thuật toán hiệu quả phát hiện luật kết hợp trong cơ sở dữ liệu lớn. Chương 7 là một thực nghiệm cho việc phát hiện luật kết hợp trên một cơ sở dữ liệu kinh doanh mặt hàng sách. Chương 8 khảo nghiệm sơ bộ về một phần mềm Khai phá dữ liệu thương mại sử dụng các kỹ thuật đã đề cập như 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. Phần mềm dựa trên nền tảng công nghệ Oracle mà tác giả đã có một thời gian dài nghiên cứu.

docx88 trang | Chia sẻ: lvcdongnoi | Ngày: 01/07/2013 | Lượt xem: 1635 | Lượt tải: 5download
Bạn đang xem nội dung tài liệu Đề 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, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trê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.

Các file đính kèm theo tài liệu này:

  • docxKhai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu lớn.docx