Tài liệu Kỹ thuật mạng noron và giải thuật di truyền trong khai phá dữ liệu và thử nghiệm ứng dụng

  • Số trang: 102 |
  • Loại file: PDF |
  • Lượt xem: 112 |
  • Lượt tải: 0
bangnguyen-hoai

Đã đăng 3509 tài liệu

Mô tả:

bé gi¸o dôc vµ ®µo t¹o tr−êng ®¹i häc b¸ch khoa hµ néi D−¬ng thÞ hiÒn thanh Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông LuËn v¨n th¹c sü c«ng nghÖ th«ng tin Hµ néi – 2008 1 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Môc lôc Môc lôc....................................................................................................................... 1 Danh môc c¸c tõ viÕt t¾t ............................................................................................. 3 Danh môc c¸c b¶ng .................................................................................................... 4 Danh môc c¸c h×nh vÏ vµ ®å thÞ ................................................................................. 5 Lêi nãi ®Çu ................................................................................................................. 6 Ch−¬ng 1. khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong csdl ..................8 1.1. tæng quan vÒ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong CSDL .......8 1.1.1. T¹i sao cÇn ph¸t hiÖn tri thøc? ......................................................................8 1.1.2. Khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu ............................9 1.2. Qu¸ tr×nh ph¸T HIÖN TRI THøC trong C¥ Së D÷ LIÖU.....................................10 1.2.2. Thu thËp vµ tiÒn xö lý d÷ liÖu .....................................................................10 1.2.3. Khai ph¸ d÷ liÖu ..........................................................................................12 1.2.4. Minh ho¹ vµ ®¸nh gi¸..................................................................................12 1.2.5. §−a kÕt qu¶ vµo thùc tÕ...............................................................................13 1.3. c¸c kü thuËt Khai ph¸ d÷ liÖu ..........................................................................13 1.3.1. KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu .....................................................13 1.3.3. NhiÖm vô chÝnh cña khai ph¸ d÷ liÖu..........................................................17 1.3.4. Mét sè ph−¬ng ph¸p khai ph¸ d÷ liÖu phæ biÕn ..........................................19 1.3.5. Nh÷ng −u thÕ vµ khã kh¨n th¸ch thøc trong nghiªn cøu vµ øng dông kü thuËt khai ph¸ d÷ liÖu .......................................................................................24 ™ KÕt luËn ch−¬ng 1 ....................................................................................................27 Ch−¬ng 2. kü thuËt khai ph¸ d÷ liÖu sö dông m¹ng n¬ron vµ gi¶i thuËt di truyÒn ......................................................................................................21 2.1. M¹ng n¬ron trong khai ph¸ d÷ liÖu ..............................................................28 2.1.1. Kh¸i niÖm m¹ng n¬ron ...............................................................................28 2.1.2. N¬ron sinh häc vµ m¹ng n¬ron sinh häc ....................................................29 2.1.3. M« h×nh vµ qu¸ tr×nh xö lý trong n¬ron nh©n t¹o .......................................30 2.1.4. CÊu tróc vµ ph©n lo¹i m¹ng n¬ron ..............................................................33 2.1.5. Häc vµ lan truyÒn trong m¹ng.....................................................................36 2.1.6. §¸nh gi¸ vÒ m¹ng n¬ron .............................................................................40 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 2 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 2.2. Gi¶i thuËt di truyÒn trong khaI PH¸ D÷ LIÖU ..............................................42 2.2.1. C¬ b¶n vÒ gi¶i thuËt di truyÒn .....................................................................42 2.2.2. Mét sè c¸ch biÓu diÔn lêi gi¶i cña gi¶i thuËt di truyÒn...............................45 2.2.3. C¸c to¸n tö di truyÒn ...................................................................................46 2.2.4. C¬ së to¸n häc cña gi¶i thuËt di truyÒn.......................................................52 2.2.5. Nh÷ng c¶i tiÕn cña gi¶i thuËt di truyÒn .......................................................54 ™ KÕt luËn ch−¬ng 2 ....................................................................................................56 Ch−¬ng 3. tÝch hîp gi¶i thuËt di truyÒn víi gi¶i thuËt huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp ..........................................................50 3.1. §Æt vÊn ®Ò ................................................................................................................57 3.2. m¹ng n¬ron truyÒn th¼ng nhiÒu líp víi gi¶i thuËt lan truyÒn ng−îc sai sè vµ mét sè c¶i tiÕn ..........................................................................57 3.2.1. KiÕn tróc cña m¹ng n¬ron truyÒn th¼ng nhiÒu líp......................................57 3.2.2. C¬ chÕ häc cña m¹ng n¬ ron truyÒn th¼ng nhiÒu líp..................................59 3.2.3. ThuËt to¸n lan truyÒn ng−îc sai sè .............................................................60 3.2.2. Mét sè c¶i tiÕn cña gi¶i thuËt BP ................................................................71 3.3. KÕt hîp gi¶i thuËt di truyÒn víi gi¶i thuËt BP ..........................................73 3.3.1. Gi¶i thuËt GA trong huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp ........73 3.3.2. GhÐp nèi víi gi¶i thuËt lan truyÒn ng−îc sai sè..........................................75 ™ KÕt luËn ch−¬ng 3 ....................................................................................................76 Ch−¬ng 4. øng dông trong bµi to¸n dù b¸o d÷ liÖu .....................................71 4.1. giíi thiÖu bµi to¸n ................................................................................................78 4.2. m« h×nh ho¸ bµi to¸n, thiÕt kÕ d÷ liÖu vµ gi¶i thuËt..............................80 4.2.1. M« h×nh ho¸ bµi to¸n ..................................................................................80 4.2.2. ThiÕt kÕ d÷ liÖu ...........................................................................................81 4.2.3. ThiÕt kÕ gi¶i thuËt .......................................................................................82 4.3. ch−¬ng tr×nh dù b¸o d÷ liÖu .............................................................................93 ™ KÕt luËn ch−¬ng 4 ....................................................................................................98 KÕt luËn .......................................................................................................... 99 Tµi liÖu tham kh¶o........................................................................................ .100 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 3 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Danh môc c¸c tõ viÕt t¾t STT Tõ viÕt t¾t NghÜa tiÕng viÖt tiÕng anh 1 ANN M¹ng n¬ron nh©n t¹o Artficial Neural Network 2 BNN M¹ng n¬ron sinh häc Biological Neural Network 3 BP Gi¶i thuËt lan truyÒn Back-Propagation of error ng−îc cña sai sè 4 Csdl C¬ së d÷ liÖu Data Base 5 dm Khai ph¸ d÷ liÖu Data Mining 6 GA Gi¶i thuËt di truyÒn Genetic Algorithm 7 Kdd Ph¸t hiÖn tri thøc Knowledge trong CSDL D−¬ng ThÞ HiÒn Thanh – CNTT 2006 Database Discover in 4 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Danh môc c¸c b¶ng B¶ng 1.1: D÷ liÖu häc trong vÝ dô quyÕt ®Þnh ®i ch¬i tennis.................................... 20 B¶ng 2.1: VÝ dô dïng phÐp t¸i t¹o............................................................................ 48 B¶ng 2.2: Qu¸ tr×nh t¸i t¹o ....................................................................................... 51 B¶ng 2.3: Qu¸ tr×nh lai ghÐp..................................................................................... 51 B¶ng 3.1: C¸c hµm kÝch ho¹t.................................................................................... 69 B¶ng 4.1: Sè liÖu thö nghiÖm cña bµi to¸n dù b¸o ....................................................79 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 5 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Danh môc c¸c h×nh vÏ vµ ®å thÞ H×nh 1.1: Qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL .................................................. 10 H×nh 1.2: KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu .................................................. 14 H×nh 1.3: Qu¸ tr×nh khai ph¸ d÷ liÖu........................................................................ 15 H×nh 1.4: KÕt qu¶ cña ph©n côm .............................................................................. 18 H×nh 1.5: C©y quyÕt ®Þnh ®i ch¬i tennis................................................................... 20 H×nh 2.1: CÊu t¹o cña n¬ron..................................................................................... 29 H×nh 2.2: Thu nhËn tÝn hiÖu trong n¬ron.................................................................. 30 H×nh 2.3: M« h×nh cña mét n¬ron nh©n t¹o ............................................................. 31 H×nh 2.4: Hµm Sigmoidal......................................................................................... 33 H×nh 2.5: M¹ng n¬ron truyÒn th¼ng nhiÒu líp......................................................... 35 H×nh 2.6: M¹ng håi quy ........................................................................................... 35 H×nh 2.7: S¬ ®å häc tham sè cã gi¸m s¸t ................................................................. 37 H×nh 2.8: S¬ ®å häc t¨ng c−êng ............................................................................... 38 H×nh 2.9: S¬ ®å häc kh«ng gi¸m s¸t ........................................................................ 38 H×nh 3.1: M¹ng n¬ron truyÒn th¼ng 2 líp................................................................ 58 H×nh 3.2: S¬ ®å hiÖu chØnh c¸c träng sè cña gi¶i thuËt BP ...................................... 59 H×nh 3.3: S¬ ®å m· ho¸ c¸c träng sè cña m¹ng n¬ron............................................. 74 H×nh 3.4: S¬ ®å cña gi¶i thuËt lai ............................................................................. 76 H×nh 4.1: S¬ ®å khèi gi¶i thuËt Ph©n hÖ 1 ............................................................... 84 H×nh 4.2: S¬ ®å khèi gi¶i thuËt Ph©n hÖ 1.1 ............................................................ 86 H×nh 4.3: S¬ ®å khèi gi¶i thuËt Ph©n hÖ 1.2 ............................................................ 89 H×nh 4.4: S¬ ®å khèi gi¶i thuËt Ph©n hÖ 2 ............................................................... 91 H×nh 4.5: Mµn h×nh chÝnh cña ch−¬ng tr×nh dù b¸o................................................. 93 H×nh 4.6: D÷ liÖu tÖp huÊn luyÖn ............................................................................. 94 H×nh 4.7: Mµn h×nh nhËp tham sè cho m¹ng n¬ron................................................. 94 H×nh 4.8: Mµn h×nh nhËp tham sè cho gi¶i thuËt GA .............................................. 95 H×nh 4.9: T×m kiÕm b»ng gi¶i thuËt GA................................................................... 95 H×nh 4.10: HuÊn luyÖn b»ng gi¶i thuËt BP............................................................... 96 H×nh 4.11: Mµn h×nh dù b¸o .................................................................................... 98 D−¬ng ThÞ HiÒn Thanh – CNTT 2006 6 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Lêi nãi ®Çu Trong nh÷ng n¨m gÇn ®©y, vai trß cña m¸y tÝnh trong viÖc l−u tr÷ vµ xö lý th«ng tin ngµy cµng trë nªn quan träng. Bªn c¹nh ®ã, c¸c thiÕt bÞ thu thËp d÷ liÖu tù ®éng còng ph¸t triÓn m¹nh gãp phÇn t¹o ra nh÷ng kho d÷ liÖu khæng lå. D÷ liÖu ®−îc thu thËp vµ l−u tr÷ ngµy cµng nhiÒu nh−ng ng−êi ra quyÕt ®Þnh l¹i cÇn cã nh÷ng th«ng tin bæ Ých, nh÷ng “tri thøc” rót ra tõ nh÷ng nguån d÷ liÖu h¬n lµ chÝnh d÷ liÖu ®ã cho viÖc ra quyÕt ®Þnh cña m×nh. Víi nh÷ng yªu cÇu ®ã, c¸c m« h×nh CSDL truyÒn thèng vµ ng«n ng÷ thao t¸c d÷ liÖu kh«ng cßn thÝch hîp n÷a. §Ó cã ®−îc tri thøc tõ CSDL, ng−êi ta ®· ph¸t triÓn c¸c lÜnh vùc nghiªn cøu vÒ tæ chøc c¸c kho d÷ liÖu vµ kho th«ng tin, c¸c hÖ trî gióp ra quyÕt ®Þnh, c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong CSDL. Trong sè ®ã, khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc ®· trë thµnh mét lÜnh vùc nghiªn cøu rÊt s«i ®éng. LuËn v¨n tËp trung nghiªn cøu kü thuËt sö dông m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu, ®Æc biÖt lµ gi¶i ph¸p tÝch hîp gi¶i thuËt di truyÒn víi gi¶i thuËt huÊn luyÖn m¹ng n¬ron. Trªn c¬ së ®ã, luËn v¨n x©y dùng ch−¬ng tr×nh dù b¸o d÷ liÖu sö dông m¹ng n¬ron truyÒn th¼ng huÊn luyÖn b»ng gi¶i thuËt lai GABP. LuËn v¨n ®−îc tr×nh bÇy gåm 4 ch−¬ng víi néi dung chÝnh nh− sau : Ch−¬ng 1: Tr×nh bÇy mét c¸ch tæng quan vÒ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong CSDL. Trong ®ã ®Ò cËp ®Õn c¸c kh¸i nÖm, qu¸ tr×nh ph¸t hiÖn tri thøc, nhiÖm vô chÝnh vµ c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu còng nh− nh÷ng vÊn ®Ò th¸ch thøc trong nghiªn cøu vµ ¸p dông kü thuËt khai ph¸ d÷ liÖu vµo thùc tÕ. Ch−¬ng 2: Nghiªn cøu kü thuËt khai ph¸ d÷ liÖu sö dông m¹ng n¬ron vµ gi¶i thuËt di truyÒn, cô thÓ lµ nh÷ng vÊn ®Ò vÒ lùa chän cÊu tróc m¹ng vµ c¸c tham sè, x©y dùng gi¶i thuËt häc vµ lan truyÒn trong m¹ng n¬ron, còng nh− c¸ch biÓu diÔn lêi gi¶i, c¸c to¸n tö di truyÒn c¬ b¶n vµ nh÷ng c¶i tiÕn cña gi¶i thuËt di truyÒn. §ång thêi, ch−¬ng 2 còng ®−a ra nh÷ng ®¸nh gi¸ vÒ hiÖu qu¶ cña kü thuËt sö dông m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu, qua ®ã cã thÓ ®Þnh h−íng cho viÖc lùa chän ph−¬ng ph¸p khai ph¸ thÝch hîp cho c¸c vÊn ®Ò thùc tÕ. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 7 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Ch−¬ng 3 : Giíi thiÖu kiÕn tróc m¹ng n¬ron truyÒn th¼ng nhiÒu líp, gi¶i thuËt BP, c¸c vÊn ®Ò vÒ sö dông gi¶i thuËt BP vµ tr×nh bÇy gi¶i ph¸p tÝch hîp gi¶i thuËt GA víi gi¶i thuËt BP trong huÊn luyÖn m¹ng n¬ron truyÒn th¼ng nhiÒu líp. Ch−¬ng 4 : Giíi thiÖu bµi to¸n øng dông dù b¸o lò trªn s«ng, tõ ®ã m« h×nh ho¸ bµi to¸n, thiÕt kÕ thuËt to¸n, d÷ liÖu vµ cµi ®Æt ch−¬ng tr×nh thö nghiÖm víi c«ng cô m¹ng n¬ron truyÒn th¼ng huÊn luyÖn b»ng gi¶i thuËt lai GA-BP. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 8 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Ch−¬ng 1: khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong CSDL 1.1. tæng quan vÒ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong C¬ Së D÷ LiÖu 1.1.1. T¹i sao cÇn ph¸t hiÖn tri thøc? H¬n hai thËp niªn trë l¹i ®©y, l−îng th«ng tin ®−îc l−u tr÷ trªn c¸c thiÕt bÞ ®iÖn tö kh«ng ngõng t¨ng lªn. ViÖc tÝch luü d÷ liÖu diÔn ra víi mét tèc ®é bïng næ. Ng−êi ta −íc ®o¸n r»ng l−îng th«ng tin trªn toµn cÇu t¨ng gÊp ®«i sau kho¶ng hai n¨m vµ theo ®ã kÝch th−íc c¬ së d÷ liÖu (CSDL) còng t¨ng lªn mét c¸ch nhanh chãng, c¶ vÒ sè b¶n ghi cña CSDL lÉn sè tr−êng, thuéc tÝnh trong b¶n ghi. L−îng d÷ liÖu khæng lå nµy thùc sù lµ nguån tµi nguyªn rÊt gi¸ trÞ v× th«ng tin chÝnh lµ yÕu tè then chèt trong mäi ho¹t ®éng. Tuy nhiªn, d÷ liÖu sÏ kh«ng cã ®Çy ®ñ ý nghÜa nÕu kh«ng ph¸t hiÖn ra nh÷ng tri thøc tiÒm Èn cã gi¸ trÞ trong ®ã. Nh÷ng tri thøc nµy th−êng rÊt nhá so víi l−îng d÷ liÖu, do ®ã ph¸t hiÖn ra chóng lµ mét vÊn ®Ò kh¸ khã kh¨n. ViÖc x©y dùng c¸c hÖ thèng cã kh¶ n¨ng ph¸t hiÖn ®−îc c¸c mÈu tri thøc cã gi¸ trÞ trong khèi d÷ liÖu ®å sé nh− vËy gäi lµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu (Knowledge Discover in Database_KDD). C¸c kü thuËt xö lý c¬ b¶n chÝnh lµ kü thuËt khai ph¸ d÷ liÖu (Data Mining_DM). ViÖc ph©n tÝch d÷ liÖu mét c¸ch tù ®éng vµ mang tÝnh dù b¸o cña KDD cã −u thÕ h¬n h¼n so víi c¸c ph−¬ng ph¸p ph©n tÝch th«ng th−êng, dùa trªn nh÷ng sù kiÖn trong qu¸ khø cña c¸c hÖ hç trî ra quyÕt ®Þnh truyÒn thèng tr−íc ®©y. Víi tÊt c¶ nh÷ng −u thÕ ®ã, KDD ®· chøng tá ®−îc tÝnh h÷u dông cña nã trong m«i tr−êng ®Çy tÝnh c¹nh tranh ngµy nay. KDD ®· vµ ®ang trë thµnh mét h−íng nghiªn cøu chÝnh cña lÜnh vùc khoa häc m¸y tÝnh vµ c«ng nghÖ tri thøc. Ph¹m vi øng dông cña KDD ban ®Çu chØ lµ trong lÜnh vùc th−¬ng m¹i vµ tµi chÝnh. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 9 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Cho ®Õn nay, KDD ®· ®−îc øng dông réng r·i trong c¸c lÜnh vùc kh¸c nh− viÔn th«ng, gi¸o dôc, ®iÒu trÞ y häc, … Cã thÓ nãi, KDD lµ mét sù cè g¾ng ®Ó gi¶i quyÕt vÊn ®Ò nan gi¶i cña kû nguyªn th«ng tin sè: vÊn ®Ò trµn d÷ liÖu. 1.1.2. Khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu Kh¸i niÖm “ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu” ®−îc ®−a ra lÇn ®Çu tiªn vµo n¨m 1989, trong ®ã nhÊn m¹nh r»ng tri thøc lµ s¶n phÈm cuèi cïng cña qu¸ tr×nh khai ph¸ d÷ liÖu. Ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu ®−îc ®Þnh nghÜa nh− lµ qu¸ tr×nh ch¾t läc tri thøc tõ mét l−îng lín d÷ liÖu. Nãi c¸ch kh¸c, cã thÓ quan niÖm KDD lµ mét ¸nh x¹ d÷ liÖu tõ møc thÊp thµnh c¸c d¹ng c« ®äng h¬n, tãm t¾t vµ h÷u Ých h¬n. Mét vÝ dô trùc quan th−êng ®−îc dïng lµ viÖc khai th¸c vµng tõ ®¸ vµ c¸t, ng−êi khai th¸c muèn ch¾t läc vµng tõ ®¸ vµ c¸t trong ®iÒu kiÖn l−îng ®¸ vµ c¸t rÊt lín. ThuËt ng÷ “data mining” ¸m chØ viÖc t×m kiÕm mét tËp hîp nhá tri thøc, th«ng tin cã gi¸ trÞ tõ mét l−îng lín c¸c d÷ liÖu th« [7]. Nã bao hµm mét lo¹t c¸c kü thuËt nh»m ph¸t hiÖn ra nh÷ng th«ng tin cã gi¸ trÞ tiÒm Èn trong c¸c CSDL lín. NhiÒu thuËt ng÷ hiÖn ®−îc dïng còng cã nghÜa t−¬ng tù víi tõ data mining nh− knowledge mining (khai ph¸ tri thøc), knowledge extraction (ch¾t läc tri thøc), data/patern analysis (Ph©n tÝch d÷ liÖu/mÉu), data archaeology (kh¶o cæ d÷ liÖu), data dredging (n¹o vÐt d÷ liÖu). Nh− vËy, nÕu quan niÖm tri thøc lµ mèi quan hÖ gi÷a c¸c phÇn tö d÷ liÖu th× ph¸t hiÖn tri thøc chØ qu¸ tr×nh chiÕt suÊt tri thøc tõ c¬ së d÷ liÖu, trong ®ã tr¶i qua nhiÒu giai ®o¹n kh¸c nhau. Khai ph¸ d÷ liÖu sö dông c¸c gi¶i thuËt ®Æc biÖt ®Ó chiÕt xuÊt ra c¸c mÉu, c¸c m« h×nh tõ d÷ liÖu vµ chØ lµ mét giai ®o¹n trong qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL. Ph¸t hiÖn tri thøc trong CSDL vµ khai ph¸ d÷ liÖu lµ mét kü thuËt míi xuÊt hiÖn vµ cã tèc ®é ph¸t triÓn rÊt nhanh. Ngoµi ra nã cßn lµ mét lÜnh vùc ®a ngµnh, liªn quan ®Õn nhiÒu lÜnh vùc kh¸c nh−: lý thuyÕt thuËt to¸n, Data Warehouse, OLAP, tÝnh to¸n song song, … nh−ng chñ yÕu dùa trªn nÒn t¶ng cña x¸c suÊt thèng kª, c¬ së d÷ liÖu vµ häc m¸y. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 10 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 1.2. Qu¸ tr×nh ph¸T HIÖN TRI THøC trong C¥ Së D÷ LIÖU H×nh 1.1 m« t¶ 5 giai ®o¹n trong qu¸ tr×nh ph¸t hiÖn tri thøc tõ c¬ së d÷ liÖu. MÆc dï cã 5 giai ®o¹n, song ph¸t hiÖn tri thøc tõ c¬ së d÷ liÖu lµ mét qu¸ tr×nh t−¬ng t¸c vµ lÆp ®i lÆp l¹i thµnh mét chu tr×nh liªn tôc theo kiÓu xo¸y tr«n èc, trong ®ã lÇn lÆp sau hoµn chØnh h¬n lÇn lÆp tr−íc. Ngoµi ra, giai ®o¹n sau l¹i dùa trªn kÕt qu¶ cña giai ®o¹n tr−íc theo kiÓu th¸c n−íc [7, 4]. 5. §−a kÕt qu¶ vµo thùc tÕ 4. Minh ho¹ vµ ®¸nh gi¸ tri thøc ®−îc ph¸t hiÖn 3. Khai ph¸ d÷ liÖu – TrÝch ra c¸c mÉu/ c¸c m« h×nh 2. Thu thËp vµ tiÒn xö lý d÷ li 1. HiÓu vµ x¸c ®Þnh vÊn ®Ò H×nh 1.1: Qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL Sau ®©y sÏ tr×nh bÇy cô thÓ h¬n tõng giai ®o¹n cña qu¸ tr×nh nµy: 1.2.1. X¸c ®Þnh vÊn ®Ò Qu¸ tr×nh nµy mang tÝnh ®Þnh tÝnh víi môc ®Ých x¸c ®Þnh ®−îc lÜnh vùc yªu cÇu ph¸t hiÖn tri thøc vµ x©y dùng bµi to¸n tæng thÓ. Trong thùc tÕ, c¸c c¬ së d÷ liÖu ®−îc chuyªn m«n ho¸ vµ ph©n chia theo c¸c lÜnh vùc kh¸c nhau. Víi mçi tri thøc ph¸t hiÖn ®−îc, cã thÓ cã gi¸ trÞ cho lÜnh vùc nµy nh−ng l¹i kh«ng mang l¹i nhiÒu ý nghÜa ®èi víi mét lÜnh vùc kh¸c. V× vËy, viÖc x¸c ®Þnh bµi to¸n gióp ®Þnh h−íng cho giai ®o¹n thu thËp vµ tiÒn xö lý d÷ liÖu. 1.2.2. Thu thËp vµ tiÒn xö lý d÷ liÖu Trong qu¸ tr×nh thu thËp d÷ liÖu cho bµi to¸n, c¸c c¬ së d÷ liÖu thu ®−îc th−êng chøa rÊt nhiÒu thuéc tÝnh nh−ng l¹i kh«ng ®Çy ®ñ, kh«ng thuÇn nhÊt, cã D−¬ng ThÞ HiÒn Thanh – CNTT 2006 11 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông nhiÒu lçi vµ cã c¸c gi¸ trÞ ®Æc biÖt. Nguyªn nh©n cã thÓ lµ do ý kiÕn ph¸t biÓu cña c¸c chuyªn gia kh«ng thèng nhÊt, do c¸c sai sè khi ®o ®¹c d÷ liÖu,… V× vËy, giai ®o¹n thu thËp vµ tiÒn xö lý d÷ liÖu trë nªn rÊt quan träng trong qu¸ tr×nh ph¸t hiÖn tri thøc tõ c¬ së d÷ liÖu. Giai ®o¹n nµy th−êng chiÕm tõ 70% ®Õn 80% gi¸ thµnh cña toµn bé bµi to¸n. Giai ®o¹n thu thËp vµ tiÒn xö lý d÷ liÖu ®−îc chia thµnh c¸c c«ng ®o¹n nh−: lùa chän d÷ liÖu, lµm s¹ch d÷ liÖu, lµm giµu d÷ liÖu, m· ho¸ d÷ liÖu. C¸c c«ng ®o¹n ®−îc thùc hiÖn theo tr×nh tù nh»m ®−a ra mét c¬ së d÷ liÖu thÝch hîp cho c¸c giai ®o¹n sau. Tuy nhiªn, tuú tõng d÷ liÖu cô thÓ mµ qu¸ tr×nh trªn ®−îc ®iÒu chØnh cho phï hîp 1.2.2.1. Chän läc d÷ liÖu §©y lµ b−íc chän läc c¸c d÷ liÖu liªn quan trong c¸c nguån d÷ liÖu kh¸c nhau. C¸c th«ng tin ®−îc chän ra lµ nh÷ng th«ng tin cã nhiÒu liªn quan ®Õn lÜnh vùc cÇn ph¸t hiÖn tri thøc ®· x¸c ®Þnh trong giai ®o¹n x¸c ®Þnh vÊn ®Ò. 1.2.2.2. Lµm s¹ch d÷ liÖu D÷ liÖu thùc tÕ, ®Æc biÖt lµ nh÷ng d÷ liÖu ®−îc lÊy tõ nhiÒu nguån kh¸c nhau th−êng kh«ng ®ång nhÊt. Do ®ã, cÇn cã biÖn ph¸p xö lý ®Ó thèng nhÊt c¸c d÷ liÖu thu ®−îc phôc vô cho khai ph¸. Giai ®o¹n lµm s¹ch d÷ liÖu th−êng bao gåm c¸c phÐp xö lý nh−: ®iÒu hoµ d÷ liÖu, xö lý c¸c gi¸ trÞ khuyÕt, xö lý nhiÔu vµ c¸c ngo¹i lÖ,... 1.2.2.3. Lµm giµu d÷ liÖu ViÖc thu thËp d÷ liÖu ®«i khi kh«ng ®¶m b¶o tÝnh ®Çy ®ñ cña d÷ liÖu. Mét sè th«ng tin rÊt quan träng cã thÓ thiÕu hoÆc kh«ng ®Çy ®ñ. ViÖc lµm giµu d÷ liÖu chÝnh lµ t×m c¸ch bæ sung c¸c th«ng tin cã ý nghÜa vµ quan träng cho qu¸ tr×nh khai ph¸ d÷ liÖu sau nµy. Qu¸ tr×nh lµm giµu d÷ liÖu còng bao gåm viÖc tÝch hîp vµ chuyÓn ®æi d÷ liÖu. C¸c d÷ liÖu tõ nhiÒu nguån kh¸c nhau ®−îc tÝch hîp thµnh mét kho thèng nhÊt. C¸c khu«n d¹ng kh¸c nhau cña d÷ liÖu còng ®−îc quy ®æi, tÝnh to¸n l¹i ®Ó ®−a vÒ mét kiÓu thèng nhÊt, tiÖn cho qu¸ tr×nh ph©n tÝch. §«i khi, mét sè thuéc tÝnh míi còng cã thÓ ®−îc x©y dùng dùa trªn c¸c thuéc tÝnh cò. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 12 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 1.2.2.4. M∙ ho¸ §©y lµ giai ®o¹n m· ho¸ c¸c ph−¬ng ph¸p dïng ®Ó chän läc, lµm s¹ch, lµm giµu d÷ liÖu thµnh c¸c thñ tôc, ch−¬ng tr×nh hay c¸c tiÖn Ých nh»m tù ®éng ho¸ viÖc kÕt xuÊt, biÕn ®æi vµ di chuyÓn d÷ liÖu. C¸c hÖ thèng con ®ã cã thÓ ®−îc thùc thi ®Þnh kú ®Ó lµm t−¬i d÷ liÖu phôc vô cho viÖc ph©n tÝch. 1.2.3. Khai ph¸ d÷ liÖu Giai ®o¹n khai ph¸ d÷ liÖu ®−îc b¾t ®Çu sau khi d÷ liÖu ®· ®−îc thu thËp vµ xö lý. Trong giai ®o¹n nµy, c«ng viÖc chñ yÕu lµ x¸c ®Þnh ®−îc bµi to¸n khai ph¸ d÷ liÖu, tiÕn hµnh lùa chän c¸c ph−¬ng ph¸p khai ph¸ thÝch hîp víi d÷ liÖu cã ®−îc vµ t¸ch ra c¸c tri thøc cÇn thiÕt. Th«ng th−êng, c¸c bµi to¸n khai ph¸ d÷ liÖu bao gåm: c¸c bµi to¸n mang tÝnh chÊt m« t¶, ®−a ra nh÷ng tÝnh chÊt chung nhÊt cña d÷ liÖu, c¸c bµi to¸n khai ph¸, dù b¸o, bao gåm c¶ viÖc thùc hiÖn c¸c suy diÔn dùa trªn d÷ liÖu hiÖn cã. Tuú theo tõng bµi to¸n x¸c ®Þnh ®−îc mµ ta lùa chän c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu cho phï hîp. 1.2.4. Minh ho¹ vµ ®¸nh gi¸ C¸c tri thøc ph¸t hiÖn ®−îc tõ c¬ së d÷ liÖu cÇn ®−îc tæng hîp vµ biÓu diÔn d−íi d¹ng gÇn gòi víi ng−êi sö dông nh− ®å thÞ, c©y, b¶ng biÓu, hay c¸c luËt, c¸c b¸o c¸o,... phôc vô cho c¸c môc ®Ých hç trî quyÕt ®Þnh kh¸c nhau. Do nhiÒu ph−¬ng ph¸p khai ph¸ cã thÓ ®−îc ¸p dông nªn c¸c kÕt qu¶ cã thÓ cã nhiÒu møc ®é tèt xÊu kh¸c nhau vµ viÖc ®¸nh gi¸ c¸c kÕt qu¶ thu ®−îc lµ rÊt cÇn thiÕt. Th«ng th−êng, c¸c kÕt qu¶ sÏ ®−îc tæng hîp, so s¸nh b»ng c¸c biÓu ®å vµ ®−îc kiÓm nghiÖm, tinh läc. §Ó ®¸nh gi¸ tri thøc, ng−êi ta th−êng dùa vµo c¸c tiªu chÝ nhÊt ®Þnh nh−: - Tri thøc ph¶i ®ñ ®é ®¸ng quan t©m: thÓ hiÖn ë tÝnh h÷u dông (useful), tÝnh míi l¹ (novel) cña tri thøc vµ qu¸ tr×nh trÝch rót kh«ng tÇm th−êng. - Tri thøc ph¶i ®ñ ®é tin cËy. §©y lµ c«ng viÖc cña c¸c nhµ chuyªn gia, c¸c nhµ ph©n tÝch vµ ra quyÕt ®Þnh. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 13 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 1.2.5. §−a kÕt qu¶ vµo thùc tÕ C¸c kÕt qu¶ cña qu¸ tr×nh ph¸t hiÖn tri thøc cã thÓ ®−îc ®−a vµo øng dông trong c¸c lÜnh vùc kh¸c nhau. Do c¸c kÕt qu¶ cã thÓ lµ c¸c dù b¸o hoÆc c¸c m« t¶ nªn cã thÓ ®−a vµo c¸c hÖ thèng hç trî ra quyÕt ®Þnh nh»m tù ®éng ho¸ qu¸ tr×nh nµy. Nh− vËy, qu¸ tr×nh ph¸t hiÖn tri thøc tõ c¬ së d÷ liÖu th−êng ®−îc thùc hiÖn theo n¨m b−íc nªu trªn. Tuy nhiªn, trong qu¸ tr×nh khai th¸c, cã thÓ thùc hiÖn nh÷ng c¶i tiÕn, n©ng cÊp cho phï hîp víi tõng øng dông cô thÓ. Trong sè c¸c b−íc, tiÒn xö lý d÷ liÖu vµ khai ph¸ d÷ liÖu hai b−íc rÊt quan träng, chiÕm phÇn lín c«ng søc vµ gi¸ thµnh cña toµn bé bµi to¸n. ViÖc lùa chän c¸c ph−¬ng ph¸p thùc hiÖn cô thÓ cho qu¸ tr×nh tiÒn xö lý vµ khai ph¸ d÷ liÖu phô thuéc rÊt nhiÒu vµo ®Æc ®iÓm d÷ liÖu vµ yªu cÇu cña bµi to¸n. Sau ®©y, ta sÏ xem xÐt cô thÓ h¬n qu¸ tr×nh khai ph¸ d÷ liÖu. 1.3. c¸c kü thuËt Khai ph¸ d÷ liÖu Ta ®· biÕt, qu¸ tr×nh ph¸t hiÖn tri thøc, vÒ nguyªn lý, tr¶i qua nhiÒu giai ®o¹n kh¸c nhau mµ khai ph¸ d÷ liÖu chØ lµ mét giai ®o¹n trong qu¸ tr×nh ®ã. Tuy nhiªn, ®©y l¹i lµ giai ®o¹n ®ãng vai trß chñ chèt vµ lµ giai ®o¹n chÝnh t¹o nªn tÝnh ®a ngµnh cña KDD. 1.3.1. KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu Khai ph¸ d÷ liÖu lµ mét b−íc quan träng trong qu¸ tr×nh ph¸t hiÖn tri thøc tõ sè l−îng lín d÷ liÖu ®· l−u tr÷ trong c¸c CSDL, kho d÷ liÖu hoÆc c¸c n¬i l−u tr÷ kh¸c. B−íc nµy cã thÓ t−¬ng t¸c lÉn nhau gi÷a ng−êi sö dông hoÆc c¬ së tri thøc. C¸c mÉu ®¸ng quan t©m ®−îc ®−a ®Õn cho ng−êi sö dông hoÆc l−u tr÷ nh− lµ tri thøc míi trong c¬ së tri thøc. KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu cã thÓ cã c¸c thµnh phÇn chÝnh sau: D−¬ng ThÞ HiÒn Thanh – CNTT 2006 14 Ng−êi sö dông Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Ng−êi sö dông Giao diÖn ng−êi dïng §¸nh gi¸ mÉu C¬ së tri thøc M« t¬ khai ph¸ d÷ liÖu (Data mining engine) CSDL hay kho d÷ liÖu phôc vô Lµm s¹ch d÷ liÖu Läc d÷ liÖu CSDL Kho d÷ liÖu H×nh 1.2: KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu - CSDL, kho d÷ liÖu hay c¸c kho l−u tr÷ kh¸c: lµ mét hoÆc mét tËp c¸c CSDL, kho d÷ liÖu, ... C¸c kü thuËt lµm s¹ch d÷ liÖu, tÝch hîp, läc d÷ liÖu cã thÓ thùc hiÖn trªn d÷ liÖu. - CSDL hay kho d÷ liÖu phôc vô: lµ nh÷ng d÷ liÖu cã liªn quan ®−îc läc vµ lµm s¹ch tõ kho d÷ liÖu trªn c¬ së yªu cÇu khai ph¸ d÷ liÖu cña ng−êi dïng. - C¬ së tri thøc: lµ lÜnh vùc tri thøc ®−îc sö dông ®Ó h−íng dÉn viÖc t×m hî¨c ®¸nh gi¸ c¸c mÉu kÕt qu¶ t×m ®−îc. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 15 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông - M« t¬ khai ph¸ d÷ liÖu: bao gåm tËp c¸c modul chøc n¨ng ®Ó thùc hiÖn c¸c nhiÖm vô nh− m« t¶ ®Æc ®iÓm, kÕt hîp, ph©n líp, ph©n côm d÷ liÖu, ... - Modul ®¸nh gi¸ mÉu: thµnh phÇn nµy sö dông c¸c ®é ®o vµ t−¬ng t¸c víi c¸c modul khai ph¸ d÷ liÖu ®Ó tËp trung t×m c¸c mÉu ®¸ng quan t©m. - Giao diÖn ng−êi dïng: cho phÐp ng−êi dïng t−¬ng t¸c víi hÖ thèng trªn c¬ së nh÷ng truy vÊn hay t¸c vô, cung cÊp c¸c th«ng tin cho viÖc t×m kiÕm. 1.3.2. Qu¸ tr×nh khai ph¸ d÷ liÖu vµ gi¶i thuËt khai ph¸ d÷ liÖu 1.3.2.1. Qu¸ tr×nh khai ph¸ d÷ liÖu C¸c gi¶i thuËt khai ph¸ d÷ liÖu th−êng ®−îc m« t¶ nh− nh÷ng ch−¬ng tr×nh ho¹t ®éng trùc tiÕp trªn tÖp d÷ liÖu. Qu¸ tr×nh khai ph¸ d÷ liÖu ®−îc thÓ hiÖn bëi m« h×nh sau: Thèng kª vµ tãm t¾t Gi¶i thuËt khai ph¸ Thu thËp vµ tiÒn xö lý d÷ liÖu X¸c ®Þnh d÷ liÖu liªn quan MÉu D÷ liÖu trùc tiÕp X¸c ®Þnh nhiÖm vô H×nh 1.3: Qu¸ tr×nh khai ph¸ d÷ liÖu - X¸c ®Þnh nhiÖm vô: X¸c ®Þnh chÝnh x¸c vÊn ®Ò cÇn ®−îc gi¶i quyÕt - X¸c ®Þnh d÷ liÖu liªn quan: Trªn c¬ së vÊn ®Ò cÇn ®−îc gi¶i quyÕt, x¸c ®Þnh c¸c nguån d÷ liÖu liªn quan ®Ó cã thÓ x©y dùng gi¶i ph¸p. - Thu thËp vµ tiÒn xö lü d÷ liÖu: Thu thËp c¸c d÷ liÖu cã liªn quan vµ xö lý chóng ®−a vÒ d¹ng sao cho gi¶i thuËt khai ph¸ d÷ liÖu cã thÓ hiÓu ®−îc. ë ®©y cã thÓ gÆp mét sè vÊn ®Ò nh−: d÷ liÖu ph¶i ®−îc sao ra nhiÒu b¶n (nÕu ®−îc D−¬ng ThÞ HiÒn Thanh – CNTT 2006 16 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông chiÕt xuÊt vµo c¸c tÖp), qu¶n lý c¸c tÖp d÷ liÖu, ph¶i lÆp ®i lÆp l¹i nhiÒu lÇn toµn bé qu¸ tr×nh (nÕu m« h×nh d÷ liÖu thay ®æi), ... - Thèng kª vµ tãm t¾t d÷ liÖu, ®ång thêi kÕt hîp víi c¸c d÷ liÖu trùc tiÕp ®Ó lµm ®Çu vµo cho b−íc thùc hiÖn gi¶i thuËt khai ph¸ d÷ liÖu. - Chän thuËt to¸n khai ph¸ d÷ liÖu thÝch hîp vµ thùc hiÖn viÖc khai ph¸ d÷ liÖu ®Ó t×m ®−îc c¸c mÉu cã ý nghÜa. Víi c¸c nhiÖm vô kh¸c nhau cña khai ph¸ d÷ liÖu, d¹ng cña c¸c mÉu chiÕt xuÊt ®−îc còng kh¸c nhau. MÉu chiÕt xuÊt ®−îc cã thÓ lµ mét m« t¶ xu h−íng, cã thÓ lµ d−íi d¹ng v¨n b¶n, mét ®å thÞ m« t¶ c¸c mèi quan hÖ trong m« h×nh,... 1.3.2.2. C¸c thµnh phÇn cña gi¶i thuËt khai ph¸ d÷ liÖu Gi¶i thuËt khai ph¸ d÷ liÖu gåm ba thµnh phÇn chÝnh: • BiÓu diÔn m« h×nh: M« h×nh ®−îc biÓu diÔn b»ng mét ng«n ng÷ L ®Ó m« t¶ c¸c mÉu cã thÓ khai th¸c ®−îc. NÕu m« h×nh m« t¶ qu¸ h¹n chÕ th× sÏ kh«ng thÓ häc ®−îc hoÆc sÏ kh«ng cã c¸c mÉu t¹o ra ®−îc mét m« h×nh chÝnh x¸c cho d÷ liÖu. Tuy nhiªn, kh¶ n¨ng m« t¶ cña m« h×nh cµng lín th× cµng t¨ng møc ®é nguy hiÓm do bÞ häc qu¸ vµ lµm gi¶m kh¶ n¨ng dù ®o¸n cña c¸c d÷ liÖu ch−a biÕt. Do ®ã, viÖc quan träng lµ ng−êi ph©n tÝch d÷ liÖu vµ thiÕt kÕ gi¶i thuËt cÇn ph¶i hiÓu ®Çy ®ñ c¸c gi¶ thiÕt m« t¶ vµ cÇn ph¶i diÔn t¶ ®−îc c¸c gi¶ thiÕt m« t¶ nµo ®−îc t¹o ra tõ luËt nµo. • §¸nh gi¸ m« h×nh: §¸nh gi¸ xem mét mÉu cã ®¸p øng ®−îc c¸c tiªu chuÈn cña qu¸ tr×nh ph¸t hiÖn tri thøc hay kh«ng. ViÖc ®¸nh gi¸ ®é chÝnh x¸c dù ®o¸n ®−îc thùc hiÖn dùa trªn ®¸nh gi¸ chÐo (cross validation). §¸nh gi¸ chÊt l−îng liªn quan ®Õn ®é chÝnh x¸c dù ®o¸n, ®é míi, kh¶ n¨ng sö dông, kh¶ n¨ng hiÓu ®−îc cña m« h×nh. Cã thÓ sö dông chuÈn thèng kª vµ chuÈn logic ®Ó ®¸nh gi¸ m« h×nh. • Ph−¬ng ph¸p t×m kiÕm: Ph−¬ng ph¸p t×m kiÕm gåm hai thµnh phÇn: t×m kiÕm tham sè vµ t×m kiÕm m« h×nh. - Trong t×m kiÕm tham sè, gi¶i thuËt cÇn t×m kiÕm c¸c tham sè ®Ó tèi −u ho¸ c¸c tiªu chuÈn ®¸nh gi¸ m« h×nh víi c¸c d÷ liÖu quan s¸t ®−îc vµ mét miªu t¶ m« h×nh ®· ®Þnh tr−íc. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 17 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông - T×m kiÕm m« h×nh thùc hiÖn gièng nh− mét vßng lÆp qua ph−¬ng ph¸p t×m kiÕm tham sè, miªu t¶ m« h×nh bÞ thay ®æi t¹o nªn mét hä c¸c m« h×nh. Víi mçi mét miªu t¶ m« h×nh, ph−¬ng ph¸p t×m kiÕm tham sè ®−îc thùc hiÖn ®Ó ®¸nh gi¸ chÊt l−îng m« h×nh. C¸c ph−¬ng ph¸p t×m kiÕm m« h×nh th−êng sö dông c¸c ph−¬ng ph¸p t×m kiÕm heuristic v× kÝch th−íc cña kh«ng gian t×m kiÕm c¸c m« h×nh th−êng ng¨n c¶n c¸c kü thuËt t×m kiÕm tæng thÓ. 1.3.3. NhiÖm vô chÝnh cña khai ph¸ d÷ liÖu §èi víi khai ph¸ d÷ liÖu, cã hai bµi to¸n chÝnh lµ: - Bµi to¸n m« t¶ (description): §−a ra m« h×nh biÓu thÞ nh÷ng tÝnh chÊt chung nhÊt cña d÷ liÖu mÉu. - Bµi to¸n khai ph¸ dù b¸o (prediction): Suy diÔn dùa trªn d÷ liÖu mÉu hiÖn cã ®Ó ®−a ra mét kÕt qu¶ nµo ®ã. Nh− vËy, cã thÓ coi môc ®Ých chÝnh cña khai ph¸ d÷ liÖu lµ m« t¶ vµ dù b¸o. C¸c mÉu ®−îc ph¸t hiÖn nh»m vµo hai môc ®Ých nµy. Bµi to¸n dù b¸o liªn quan ®Õn viÖc sö dông c¸c biÕn hoÆc c¸c tr−êng trong CSDL ®Ó chiÕt xuÊt ra c¸c mÉu, trªn c¬ së ®ã dù ®o¸n c¸c gi¸ trÞ ch−a biÕt hoÆc c¸c gi¸ trÞ t−¬ng lai cña c¸c biÕn ®¸ng quan t©m. Bµi to¸n m« t¶ tËp trung vµo viÖc t×m kiÕm c¸c mÉu m« t¶ d÷ liÖu cã thÓ hiÓu ®−îc cho c¸c øng dông thùc tÕ. §Ó ®¹t ®−îc hai môc ®Ých nµy, nhiÖm vô chÝnh cña khai ph¸ d÷ liÖu bao gåm c¸c vÊn ®Ò sau: • Ph©n líp (clasification): Ph©n líp t−¬ng øng víi viÖc x¸c lËp mét ¸nh x¹ (hay ph©n lo¹i) mét tËp d÷ liÖu vµo mét trong sè c¸c líp ®· x¸c ®Þnh. • Håi quy (Regression): Håi quy t−¬ng øng víi viÖc x¸c lËp ¸nh x¹ tõ mét tËp d÷ liÖu vµo mét biÕn dù ®o¸n cã gi¸ trÞ thùc. • Ph©n côm (Clustering): Ph©n côm nh»m ghÐp nhãm c¸c ®èi t−îng d÷ liÖu. C¸c ®èi t−îng d÷ liÖu ®−îc coi lµ gièng nhau, nÕu chóng thuéc cïng mét côm vµ kh¸c nhau nÕu chóng thuéc c¸c côm kh¸c nhau. C¸c côm cã thÓ t¸ch rêi nhau hoÆc ph©n cÊp hoÆc gèi lªn nhau. NghÜa lµ mét ®èi t−îng d÷ liÖu cã thÓ võa thuéc côm nµy, võa thuéc côm kia. Qu¸ tr×nh nhãm c¸c ®èi t−îng thµnh c¸c côm ®−îc gäi lµ D−¬ng ThÞ HiÒn Thanh – CNTT 2006 18 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông ph©n côm hay ph©n nhãm. Mét vÝ dô øng dông cña khai ph¸ d÷ liÖu cã nhiÖm vô ph©n côm lµ ph¸t hiÖn tËp nh÷ng kh¸ch hµng cã hµnh vi gièng nhau trong c¬ së d÷ liÖu tiÕp thÞ. Côm 3 Côm 1 Côm 2 H×nh 1.4: KÕt qu¶ cña ph©n côm H×nh 1.4 m« t¶ c¸c mÉu cña qu¸ tr×nh khai ph¸ d÷ liÖu víi nhiÖm vô ph©n côm. C¸c mÉu lµ nhãm kh¸ch hµng ®−îc xÕp vµo ba nhãm gèi lªn nhau. Nh÷ng kh¸ch hµng ë c¶ hai côm chøng tá kh¸ch hµng ®ã cã thÓ thuéc hai tr¹ng th¸i. • Tãm t¾t (summarization): liªn quan ®Õn c¸c ph−¬ng ph¸p t×m kiÕm mét m« t¶ tãm t¾t cho mét tËp con d÷ liÖu. • M« h×nh ho¸ sù phô thuéc (Dependency Modeling): Bao gåm viÖc t×m kiÕm mét m« h×nh m« t¶ sù phô thuéc gi÷a c¸c biÕn. C¸c m« h×nh phô thuéc tån t¹i d−íi hai møc: - Møc cÊu tróc, lµ m« h×nh x¸c ®Þnh c¸c biÕn nµo lµ phô thuéc côc bé víi nhau (th−êng ë d¹ng ®å ho¹). - Møc ®Þnh l−îng lµ m« h×nh x¸c ®Þnh ®é lín cña sù phô thuéc theo mét th−íc ®o nµo ®ã. • Ph¸t hiÖn thay ®æi vµ sai lÖch (Change and Deviation detection): X¸c ®Þnh nh÷ng thay ®æi ®¸ng kÓ nhÊt trong d÷ liÖu tõ c¸c gi¸ trÞ chuÈn ®o ®−îc tr−íc ®ã. Râ rµng, nh÷ng nhiÖm vô kh¸c nhau kÓ trªn yªu cÇu vÒ sè l−îng vµ c¸c d¹ng th«ng tin rÊt kh¸c nhau. Do ®ã, tuú theo tõng nhiÖm vô cô thÓ, sÏ cã nh÷ng ¶nh h−ëng ®Õn viÖc thiÕt kÕ vµ lùa chän gi¶i thuËt khai ph¸ d÷ liÖu. D−¬ng ThÞ HiÒn Thanh – CNTT 2006 Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 19 1.3.4. Mét sè ph−¬ng ph¸p khai ph¸ d÷ liÖu phæ biÕn 1.3.4.1. Ph−¬ng ph¸p quy n¹p Cã hai kü thuËt chÝnh ®Ó thùc hiÖn lµ suy diÔn vµ quy n¹p. • Suy diÔn: nh»m rót ra th«ng tin lµ kÕt qu¶ logic cña c¸c th«ng tin trong CSDL. Ph−¬ng ph¸p suy diÔn dùa trªn nh÷ng sù kiÖn chÝnh x¸c ®Ó suy ra c¸c tri thøc míi tõ c¸c th«ng tin cò. MÉu chiÕt xuÊt theo kü thuËt nµy th−êng lµ c¸c luËt suy diÔn. • Quy n¹p: Ph−¬ng ph¸p quy n¹p suy ra th«ng tin ®−îc sinh ra tõ c¬ së d÷ liÖu, cã nghÜa lµ nã tù t×m kiÕm, t¹o mÉu vµ sinh ra tri thøc chø kh«ng ph¶i b¾t ®Çu víi c¸c tri thøc ®· biÕt tr−íc. C¸c th«ng tin do ph−¬ng ph¸p nµy mang l¹i lµ nh÷ng th«ng tin hay tri thøc cÊp cao diÔn t¶ vÒ c¸c ®èi t−îng trong CSDL. Ph−¬ng ph¸p nµy liªn quan ®Õn viÖc t×m kiÕm c¸c mÉu trong CSDL. Ph−¬ng ph¸p quy n¹p th−êng ®−îc nãi ®Õn trong kü thuËt c©y quyÕt ®Þnh vµ t¹o luËt. 1.3.4.2. C©y quyÕt ®Þnh vµ t¹o luËt • C©y quyÕt ®Þnh: lµ mét d¹ng m« t¶ tri thøc ®¬n gi¶n nh»m ph©n c¸c ®èi t−äng d÷ liÖu thµnh mét sè líp nhÊt ®Þnh. C¸c nót cña c©y ®−îc g¸n nh·n lµ tªn c¸c thuéc tÝnh, c¸c cung ®−îc g¾n gi¸ trÞ cã thÓ cña c¸c thuéc tÝnh, c¸c l¸ miªu t¶ c¸c líp kh¸c nhau. C¸c ®èi t−îng ®−îc ph©n líp theo c¸c ®−êng ®i trªn c©y, qua c¸c cung t−¬ng øng víi gi¸ trÞ cña thuéc tÝnh cña ®èi t−îng tíi l¸. VÝ dô: B¶ng d÷ liÖu häc trong vÝ dô quyÕt ®Þnh ®i ch¬i tennis: Ngµy Quang c¶nh NhiÖt ®é §é Èm Giã Ch¬i tennis D1 N¾ng Nãng Cao Yªó Kh«ng D2 N¾ng Nãng Cao M¹nh Kh«ng D3 ©m u Nãng Cao Yªó Cã D4 M−a Êm ¸p Cao Yªó Cã D5 M−a L¹nh B×nh th−êng Yªó Cã D−¬ng ThÞ HiÒn Thanh – CNTT 2006
- Xem thêm -