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.
88 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2527 | Lượt tải: 5
Bạn đang xem trước 20 trang 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, để xem tài liệu hoàn chỉnh 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ý, lu 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 trng 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 nhng 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µ cha 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 (nhng 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, nhng 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 cha 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 cha 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 cha 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” nhng 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 cha ®î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, nhng ®«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 nhng 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 lu 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, nhng 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é, cha ai biÕt chÝnh x¸c m¹ng n¬ron ®¹t ®îc kÕt qu¶ nh thÕ nµo, nhng 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 trng 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¬ nhng 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, nhng 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 nhng 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. Nhng 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 cha ®¹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 nhng 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 nhng 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 trng 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 trng 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 . . .
Nhng 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. Nhng nÕu tËp d÷ liÖu lµ tha, 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, nhng 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 cha 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 cha 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ý nhng 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:
- Khai phá dữ liệu và phát hiện luật kết hợp trong cơ sở dữ liệu lớn.docx