intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Luận văn thạc sĩ: 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

Chia sẻ: Nguyen Bao Ngoc | Ngày: | Loại File: PDF | Số trang:102

Thêm vào BST
Báo xấu
453
lượt xem 222
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn tập trung nghiên cứu kỹ thuật 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 noron.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 no7ron truyền thẳng huấn luyện bằng giải thuật lai GA-BP

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: 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. 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
  2. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 1 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
  3. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 2 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
  4. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 3 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 M¹ng n¬ron nh©n t¹o Artficial Neural Network 1 ANN M¹ng n¬ron sinh häc Biological Neural Network 2 BNN Gi¶i thuËt lan truyÒn 3 BP Back-Propagation of error ng−îc cña sai sè C¬ së d÷ liÖu Data Base 4 Csdl Khai ph¸ d÷ liÖu Data Mining 5 dm Gi¶i thuËt di truyÒn Genetic Algorithm 6 GA Ph¸t hiÖn tri thøc Knowledge Discover in 7 Kdd trong CSDL Database D−¬ng ThÞ HiÒn Thanh – CNTT 2006
  5. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 4 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
  6. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 5 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
  7. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 6 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 GA- BP. 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
  8. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 7 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
  9. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 8 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
  10. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 9 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
  11. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 10 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
  12. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 11 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
  13. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 12 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
  14. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 13 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
  15. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 14 trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông Ng−êi sö Ng−êi sö dông 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 Kho d÷ liÖu CSDL 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
  16. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 15 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 MÉu Thu thËp vµ tiÒn khai ph¸ xö lý d÷ liÖu D÷ liÖu trùc X¸c ®Þnh d÷ liÖu tiÕp liªn quan 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
  17. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 16 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
  18. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 17 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
  19. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 18 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
  20. Kü thuËt m¹ng n¬ron vµ gi¶i thuËt di truyÒn 19 trong khai ph¸ d÷ liÖu vµ thö nghiÖm øng dông 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.26: Bộ 320 Luận Văn Thạc Sĩ Y Học
320 tài liệu
1246 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2