Luận văn 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

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

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

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

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.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

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

3

Danh môc c¸c tõ viÕt t¾t

STT

1

Tõ viÕt t¾t

ANN

NghÜa tiÕng viÖt

tiÕng anh

M¹ng n¬ron nh©n t¹o Artficial Neural Network

M¹ng n¬ron sinh häc Biological Neural Network

2

BNN

Gi¶i thuËt lan truyÒn

Back-Propagation of error

ng−îc cña sai sè

3

BP

C¬ së d÷ liÖu

Data Base

4

5

6

Csdl

dm

Khai ph¸ d÷ liÖu

Gi¶i thuËt di truyÒn

Data Mining

Genetic Algorithm

GA

Ph¸t hiÖn tri thøc Knowledge Discover in

trong CSDL Database

7

Kdd

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

4

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

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

5

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

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

6

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

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

7

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

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

8

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

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

9

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

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

10

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÷

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

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

11

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

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

12

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

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

13

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

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

14

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

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

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

15

- 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¸

MÉu

Thu thËp vµ tiÒn

xö lý d÷ liÖu

D÷ liÖu trùc

tiÕp

X¸c ®Þnh d÷ liÖu

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

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

16

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

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

17

- 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

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

18

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

D2

D3

N¾ng

©m u

Nãng

Cao

Yªó

M¹nh

Yªó

Kh«ng

Cã

D4

D5

M−a

Êm ¸p

L¹nh

Cao

Yªó

Cã

B×nh th−êng

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

20

D6

D7

M−a

©m u

N¾ng

M−a

N¾ng

©m u

M−a

L¹nh

B×nh th−êng

Cao

M¹nh

Yªó

Kh«ng

Cã

D8

Êm ¸p

L¹nh

Kh«ng

Cã

D9

B×nh th−êng

Cao

Yªó

D10

D11

D12

D13

D14

Êm ¸p

Nãng

Êm ¸p

Yªó

Cã

M¹nh

Yªó

Cã

B×nh th−êng

Cao

Cã

M¹nh

Kh«ng

B¶ng 1.1: D÷ liÖu häc trong vÝ dô quyÕt ®Þnh ®i ch¬i tennis

Tõ b¶ng d÷ liÖu trªn, ng−êi ta x©y dùng ®−îc c©y quyÕt ®Þnh trî gióp quyÕt ®Þnh

®i hay kh«ng ®i ch¬i tennis nh− sau:

Quang c¶nh

M−a

N¾ng

©m u

Cã

Giã

§é Èm

YÕu

Cã

Cao

B×nh th−êng

M¹nh

Kh«ng

Cã

• T¹o luËt: C¸c luËt ®−îc t¹o ra nh»m suy diÔn mét sè mÉu d÷ liÖu cã ý nghÜa

vÒ mÆt thèng kª. C¸c luËt cã d¹ng “NÕu P th× Q”, víi P lµ mÖnh ®Ò ®óng víi mét

phÇn d÷ liÖu cã trong CSDL, Q lµ mÖnh ®Ò dù ®o¸n.

diÔn ®−îc mét sè chøc n¨ng, v× vËy chóng giíi h¹n vÒ ®é chÝnh x¸c cña m« h×nh.

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

21

1.3.4.3. Ph¸t hiÖn luËt kÕt hîp

Ph−¬ng ph¸p nµy nh»m ph¸t hiÖn c¸c luËt kÕt hîp gi÷a c¸c thµnh phÇn d÷

liÖu trong CSDL. §Çu ra cña thuËt to¸n khai ph¸ d÷ liÖu lµ mét tËp luËt kÕt mµ mçi

luËt cã d¹ng: X => Y (nÕu cã X th× cã Y). KÌm theo mçi luËt t×m ®−îc lµ c¸c tham

sè ®é hç trî vµ ®é tin cËy cña luËt. §é hç trî vµ ®é tin cËy lµ hai ®é ®o chØ sù ®¸ng

thøc:

§é hç trî (Support) = Sè b¶n ghi chøa X / Tæng sè b¶n ghi.

§é tin cËy (Confidence) = Sè b¶n ghi chøa c¶ X vµ Y / Sè b¶n ghi chøa X

hµng mua m¸y tÝnh ®ång thêi còng cã khuynh h−íng mua phÇn mÒm qu¶n lý tµi

chÝnh trong cïng mét lÇn mua ®−îc m« t¶ trong luËt kÕt hîp nh− sau:

“M¸y tÝnh => PhÇn mÒm qu¶n lý”

[§é hç trî: 2%, ®é tin cËy: 60%]

LuËt trªn thÓ hiÖn cã 2% trªn tæng sè c¸c kh¸ch hµng ®· mua m¸y tÝnh, trong

sè nh÷ng kh¸ch hµng mua m¸y tÝnh, 60% còng mua phÇn mÒm qu¶n lý.

Ph¸t hiÖn c¸c luËt kÕt hîp lµ ph¶i t×m tÊt c¶ c¸c luËt tho¶ m·n ng−ìng ®é tin

cËy vµ ®é hç trî cho tr−íc. ThuËt to¸n t×m c¸c luËt kÕt hîp tr−íc tiªn ph¶i ®i t×m c¸c

tËp môc th−êng xuyªn, sau ®ã tõ c¸c tËp môc th−êng xuyªn t¹o nªn luËt kÕt hîp.

cho mçi phÇn hoÆc mçi nhãm sÏ gièng nhau theo mét tiªu chuÈn nµo ®ã. Mèi quan

hÖ thµnh viªn cña c¸c nhãm cã thÓ dùa trªn møc ®é gièng nhau cña c¸c thµnh viªn

phÇn nh− lµ hµm cña c¸c tham sè cña c¸c thµnh phÇn. Ph−¬ng ph¸p nµy ®−îc gäi lµ

MÉu ®Çu ra cña qu¸ tr×nh khai ph¸ d÷ liÖu dïng kü thuËt nµy lµ c¸c tËp mÉu

mÉu ®−îc thiÕt lËp, chóng cã thÓ ®−îc sö dông ®Ó t¸i t¹o c¸c tËp d÷ liÖu ë d¹ng dÔ

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

22

hiÓu h¬n, ®ång thêi còng cung cÊp c¸c nhãm d÷ liÖu cho c¸c ho¹t ®éng còng nh−

1.3.4.5. C¸c ph−¬ng ph¸p dùa trªn mÉu

Sö dông c¸c mÉu miªu t¶ tõ CSDL ®Ó t¹o nªn mét m« h×nh dù ®o¸n c¸c mÉu

míi b»ng c¸ch rót ra c¸c thuéc tÝnh t−¬ng tù nh− c¸c mÉu ®· biÕt trong m« h×nh.

neighbour), c¸c gi¶i thuËt håi quy vµ c¸c hÖ thèng suy diÔn dùa trªn t×nh huèng

(case based reasoning).

1.3.4.6. M« h×nh phô thuéc dùa trªn ®å thÞ x¸c suÊt

C¸c m« h×nh ®å thÞ x¸c ®Þnh sù phô thuéc x¸c suÊt gi÷a c¸c sù kiÖn th«ng

qua mèi liªn hÖ trùc tiÕp theo c¸c cung cña ®å thÞ. ë d¹ng ®¬n gi¶n nhÊt, m« h×nh

x¸c ®Þnh nh÷ng biÕn nµo phô thuéc nhau mét c¸ch trùc tiÕp. M« h×nh phô thuéc dùa

lo¹i. Tuy nhiªn, c¸c m« h×nh nµy còng ®−îc më réng cho mét sè tr−êng hîp ®Æc biÖt

nh− mËt ®é Gaussian hoÆc cho c¸c biÕn cã gi¸ trÞ thùc.

1.3.4.7. M« h×nh häc quan hÖ

mÖnh ®Ò logic, cßn m« h×nh häc quan hÖ (cßn gäi lµ lËp tr×nh logic quy n¹p) sö dông

ng«n ng÷ mÉu theo thø tù logic tr−íc (first – order logic) kh¸ linh ho¹t. M« h×nh nµy

cã thÓ dÔ dµng t×m ra c«ng thøc X=Y. Cho ®Õn nay, hÇu hÕt c¸c nghiªn cøu vÒ c¸c

ph−¬ng ph¸p ®¸nh gi¸ m« h×nh häc quan hÖ ®Òu theo logic trong tù nhiªn.

1.3.4.8. Khai ph¸ d÷ liÖu v¨n b¶n (Text Mining)

c¸c d÷ liÖu v¨n b¶n kh«ng ®Þnh d¹ng. C¸c lÜnh vùc øng dông cña khai ph¸ d÷ liÖu

v¨n b¶n nh− nghiªn cøu thÞ tr−êng, thu nhËp, t×nh b¸o, .... Ph−¬ng ph¸p nµy ®−îc sö

c¸c tµi liÖu phøc t¹p.

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

23

1.3.4.9. M¹ng n¬ron

M¹ng n¬ron lµ c¸ch tiÕp cËn tÝnh to¸n míi liªn quan ®Õn viÖc ph¸t triÓn c¸c

cÊu tróc to¸n häc víi kh¶ n¨ng häc. M¹ng n¬ron lµ kÕt qu¶ cña viÖc nghiªn cøu m«

h×nh häc cña hÖ thÇn kinh con ng−êi. M¹ng cã thÓ ®−a ra ý nghÜa tõ c¸c d÷ liÖu phøc

t¹p hoÆc kh«ng chÝnh x¸c vµ cã thÓ ®−îc sö dông ®Ó chiÕt suÊt c¸c mÉu vµ ph¸t hiÖn

ra c¸c xu h−íng phøc t¹p mµ con ng−êi còng nh− c¸c kü thuËt m¸y tÝnh kh¸c kh«ng

thÓ ph¸t hiÖn ®−îc.

Khi ®Ò cËp ®Õn khai th¸c d÷ liÖu, ng−êi ta th−êng ®Ò cËp nhiÒu ®Õn m¹ng

khai nh−ng nã còng cã nh÷ng −u ®iÓm ®¸ng kÓ. Mét trong sè nh÷ng −u ®iÓm ®ã lµ

kh¶ n¨ng t¹o ra c¸c m« h×nh dù ®o¸n cã ®é chÝnh x¸c cao, cã thÓ ¸p dông ®−îc cho

rÊt nhiÒu bµi to¸n kh¸c nhau ®¸p øng ®−îc nhiÖm vô ®Æt ra cña khai ph¸ d÷ liÖu nh−

1.3.4.10. Gi¶i thuËt di truyÒn

Gi¶i thuËt di truyÒn chÝnh lµ sù m« pháng l¹i qu¸ tr×nh tiÕn ho¸ di truyÒn

trong tù nhiªn. Mét c¸ch chÝnh x¸c th× ®ã lµ gi¶i thuËt chØ ra tËp c¸c c¸ thÓ ®−îc

h×nh thµnh, −íc l−îng vµ biÕn ®æi nh− thÕ nµo. Cô thÓ lµ c¸c vÊn ®Ò nh− lµm thÕ nµo

®Ó lùa chän c¸c c¸ thÓ t¸i t¹o vµ c¸c c¸ thÓ nµo sÏ bÞ lo¹i bá, qu¸ tr×nh lai ghÐp vµ

®ét biÕn sÏ diÔn ra nh− thÕ nµo? Gi¶i thuËt còng m« pháng l¹i yÕu tè gien trong

nhiÔm s¾c thÓ sinh häc trªn m¸y tÝnh ®Ó cã thÓ gi¶i quyÕt ®−îc c¸c bµi to¸n thùc tÕ

kh¸c nhau.

Gi¶i thuËt di truyÒn lµ mét gi¶i thuËt tèi −u ho¸, ®−îc sö dông réng r·i trong

viÖc tèi −u ho¸ c¸c kü thuËt khai ph¸ d÷ liÖu trong ®ã cã kü thuËt m¹ng n¬ron. Sù

liªn hÖ cña gi¶i thuËt di truyÒn víi c¸c gi¶i thuËt khai ph¸ lµ ë chç viÖc tèi −u ho¸ rÊt

t¹o luËt, ....

VÊn ®Ò lùa chän ph−¬ng ph¸p:

Qua phÇn tr×nh bÇy trªn, ta nhËn thÊy cã rÊt nhiÒu ph−¬ng ph¸p khai ph¸ d÷

liÖu. Mçi ph−¬ng ph¸p cã nh÷ng ®Æc ®iÓm riªng phï hîp víi mét líp c¸c bµi to¸n,

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

24

víi c¸c d¹ng d÷ liÖu vµ miÒn d÷ liÖu nhÊt ®Þnh. HiÖn ng−êi ta vÉn ch−a ®−a ra ®−îc

mét tiªu chuÈn nµo trong viÖc quyÕt ®Þnh sö dông ph−¬ng ph¸p khai ph¸ nµo trong

tr−êng hîp nµo th× hiÖu qu¶.

HÇu hÕt c¸c kü thuËt khai ph¸ d÷ liÖu ®Òu cßn míi mÎ víi lÜnh vùc kinh

doanh. H¬n n÷a, l¹i cã rÊt nhiÒu kü thuËt, mçi kü thuËt ®−îc sö dông cho nhiÒu bµi

kh«ng ®¬n gi¶n. Mçi kü thuËt ®Òu cã ®iÓm m¹nh vµ ®iÓm yÕu nhÊt ®Þnh, nªn vÊn ®Ò

®èi víi ng−êi sö dông lµ ph¶i lùa chän vµ ¸p dông c¸c kü thuËt mét c¸ch thËt ®¬n

gi¶n, dÔ sö dông ®Ó kh«ng c¶m thÊy nh÷ng phøc t¹p vèn cã cña kü thuËt ®ã.

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

1.3.5.1. ¦u thÕ cña khai ph¸ d÷ liÖu so víi c¸c ph−¬ng ph¸p c¬ b¶n

Khai ph¸ d÷ liÖu lµ lÜnh vùc liªn quan tíi rÊt nhiÒu ngµnh häc kh¸c nh−: hÖ

CSDL, thèng kª, hiÓn thÞ trùc quan ho¸,... H¬n n÷a, tuú vµo c¸ch tiÕp cËn, khai ph¸

d÷ liÖu cßn cã thÓ ¸p dông mét sè kü thuËt nh− m¹ng n¬ron, lü thuyÕt tËp th« hoÆc

tËp mê, biÓu diÔn tri thøc,... Tuy nhiªn, khai ph¸ d÷ liÖu cã mét sè −u ®iÓm râ rÖt so

víi c¸c ph−¬ng ph¸p c¬ b¶n kh¸c, cô thÓ nh− sau:

• So víi ph−¬ng ph¸p häc m¸y, khai ph¸ d÷ liÖu cã lîi thÕ h¬n ë chç nã cã thÓ

sö dông c¸c CSDL chøa nhiÔu, d÷ liÖu kh«ng ®Çy ®ñ hoÆc biÕn ®æi liªn tôc. Trong

khi ph−¬ng ph¸p häc m¸y chñ yÕu ®−îc ¸p dông trong nh÷ng CSDL ®Çy ®ñ, Ýt biÕn

®éng vµ tËp d÷ liÖu kh«ng qu¸ lín.

• Ph−¬ng ph¸p hÖ chuyªn gia: ph−¬ng ph¸p nµy kh¸c víi khai ph¸ d÷ liÖu ë chç

c¸c vÝ dô cña chuyªn gia th−êng ë møc chÊt l−îng cao h¬n nhiÒu so víi d÷ liÖu

trong CSDL vµ chóng chØ bao hµm c¸c tr−êng hîp quan träng. H¬n n÷a, c¸c chuyªn

gia sÏ x¸c nhËn gi¸ trÞ vµ tÝnh h÷u Ých cña c¸c mÉu ph¸t hiÖn ®−îc vµ nh− thÕ ®ßi hái

ph¶i cã sù tham gia cña con ng−êi trong viÖc ph¸t hiÖn tri thøc.

• Ph−¬ng ph¸p thèng kª lµ mét trong nh÷ng nÒn t¶ng lý thuyÕt cña khai ph¸ d÷

liÖu, nh−ng khi so s¸nh chóng víi nhau, cã thÓ thÊy ph−¬ng ph¸p thèng kª cßn cã

mét sè ®iÓm yÕu mµ khai ph¸ d÷ liÖu ®· kh¾c phôc ®−îc:

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

25

- C¸c ph−¬ng ph¸p thèng kª chuÈn kh«ng phï hîp víi c¸c kiÓu d÷ liÖu cã cÊu

tróc trong rÊt nhiÒu c¸c CSDL.

- C¸c ph−¬ng ph¸p thèng kª ho¹t ®éng hoµn toµn theo d÷ liÖu, nã kh«ng sö

dông tri thøc s½n cã vÒ lÜnh vùc.

1.3.5.2. Nh÷ng vÊn ®Ò khã kh¨n th¸ch thøc

MÆc dï khai ph¸ d÷ liÖu lµ mét kü thuËt khai ph¸ tri thøc hiÖu qu¶, nh−ng

còng béc lé nhiÒu khã kh¨n. Nh÷ng khã kh¨n ®ã chÝnh lµ nh÷ng th¸ch thøc lín

trong qu¸ tr×nh nghiªn cøu vµ øng dông c¸c kü thuËt khai ph¸ d÷ liÖu vµo thùc tÕ.

¾ C¸c vÊn ®Ò vÒ c¬ së d÷ liÖu:

§Çu vµo cña hÖ thèng ph¸t hiÖn tri thøc chñ yÕu lµ c¸c d÷ liÖu th« trong

CSDL. Nh÷ng vÊn ®Ò ph¸t sinh trong qu¸ tr×nh khai ph¸ d÷ liÖu chÝnh tõ c¸c nguyªn

sè tr−êng hîp, ng−êi ta kh«ng biÕt d÷ liÖu cã chøa th«ng tin cÇn thiÕt cho viÖc khai

th¸c hay kh«ng vµ lµm thÕ nµo ®Ó gi¶i quyÕt sù d− thõa nh÷ng th«ng tin kh«ng thÝch

hîp.

• VÊn ®Ò d÷ liÖu lín: C¸c CSDL th«ng th−êng lµ rÊt lín, víi hµng tr¨m tr−êng

vµ b¶ng cã hµng triÖu b¶n ghi. Khi ®ã kÝch th−íc l−u tr÷ còng rÊt lín, hµng

gigabytes thËm chÝ terabytes. Do ®ã, lµm t¨ng kh«ng gian t×m kiÕm, t¨ng qu¸ tr×nh

suy diÔn, ®ång thêi còng lµm t¨ng kh¶ n¨ng gi¶i thuËt khai ph¸ d÷ liÖu t×m ®−îc c¸c

mÉu gi¶. Ph−¬ng ph¸p kh¾c phôc vÊn ®Ò nµy hiÖn nay lµ ®−a ra mét ng−ìng cho

CSDL, lÊy mÉu, c¸c ph−¬ng ph¸p xÊp xØ, xö lý song song, gi¶m kÝch th−íc t¸c ®éng

cña bµi to¸n vµ sö dông c¸c tri thøc ®· biÕt tr−íc ®Ó x¸c ®Þnh c¸c biÕn kh«ng phï

hîp.

• VÊn ®Ò d÷ liÖu ®éng: HÇu hÕt c¸c CSDL cã néi dung thay ®æi liªn tôc theo thêi

gian vµ viÖc khai ph¸ d÷ liÖu bÞ ¶nh h−ëng bëi thêi ®iÓm quan s¸t. ViÖc thay ®æi d÷

liÖu nhanh chãng cã thÓ lµm cho c¸c mÉu khai ph¸ ®−îc tr−íc ®ã mÊt gi¸ trÞ. H¬n

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

26

n÷a, c¸c biÕn trong CSDL cña øng dông cã thÓ bÞ thay ®æi, bÞ xo¸ hoÆc t¨ng lªn theo

mÉu vµ coi nh÷ng thay ®æi nh− lµ c¬ héi ®Ó khai th¸c b»ng c¸ch sö dông nã ®Ó t×m

kiÕm c¸c mÉu bÞ thay ®æi.

• VÊn ®Ò c¸c tr−êng kh«ng phï hîp: Mét ®Æc ®iÓm quan träng kh¸c lµ tÝnh

kh«ng thÝch hîp cña d÷ liÖu, nghÜa lµ d÷ liÖu trë thµnh kh«ng thÝch hîp víi môc tiªu

®é phï hîp lµ tÝnh øng dông cña mét thuéc tÝnh ®èi víi mét tËp con cña CSDL.

• VÊn ®Ò c¸c tr−êng hay c¸c gi¸ trÞ bÞ thiÕu: Mét quan s¸t kh«ng ®Çy ®ñ cña

CSDL cã thÓ lµm cho d÷ liÖu cã gi¸ trÞ bÞ xem nh− lµ cã lçi. ViÖc quan s¸t CSDL

ph¶i ph¸t hiÖn ®−îc toµn bé c¸c thuéc tÝnh cã thÓ dïng ®Ó khai ph¸ d÷ liÖu trong bµi

lµ vÊn ®Ò th−êng x¶y ra trong CSDL kinh doanh, c¸c thuéc tÝnh quan träng cã thÓ bÞ

thiÕu d÷ liÖu, kh«ng s½n sµng cho viÖc khai ph¸ d÷ liÖu.

• §é nhiÔu vµ kh«ng ch¾c ch¾n: §é nhiÔu cña d÷ liÖu (®é chÝnh x¸c, dung sai,

• Mèi quan hÖ phøc t¹p gi÷a c¸c tr−êng: c¸c thuéc tÝnh hoÆc c¸c gi¸ trÞ d÷ liÖu

dung cña CSDL dÉn tíi c¸c gi¶i thuËt ph¶i cã kh¶ n¨ng khai ph¸ mét c¸ch hiÖu qu¶

c¸c d÷ liÖu nµy.

¾ Mét sè vÊn ®Ò kh¸c:

• Qu¸ phï hîp: Khi mét thuËt to¸n t×m kiÕm c¸c tham sè tèt nhÊt cho mét m«

h×nh nµo ®ã sö dông mét tËp d÷ liÖu h÷u h¹n, cã thÓ x¶y ra t×nh tr¹ng “qu¸ ®é”,

nghÜa lµ chØ phï hîp víi mét tËp d÷ liÖu mµ kh«ng cã kh¶ n¨ng ®¸p øng víi c¸c d÷

liÖu l¹. §iÒu ®ã lµm cho m« h×nh ho¹t ®éng rÊt kÐm víi c¸c d÷ liÖu thö. Cã thÓ kh¾c

phôc b»ng c¸ch ®¸nh gi¸ chÐo, thùc hiÖn theo nguyªn t¾c nµo ®ã hoÆc sö dông c¸c

biÖn ph¸p thèng kª kh¸c.

• Kh¶ n¨ng biÓu ®¹t mÉu: trong rÊt nhiÒu øng dông, ®iÒu quan träng lµ nh÷ng

mÉu khai th¸c ®−îc ph¶i cµng dÔ hiÓu ®èi víi con ng−êi cµng tèt. V× vËy, c¸c gi¶i

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

27

h−íng, biÓu diÔn b»ng ng«n ng÷ tù nhiªn vµ c¸c kü thuËt kh¸c nh»m biÓu diÔn tri

thøc vµ d÷ liÖu.

• T−¬ng t¸c víi ng−êi sö dông vµ c¸c tri thøc s½n cã: rÊt nhiÒu c«ng cô vµ

ph−¬ng ph¸p khai ph¸ d÷ liÖu kh«ng thùc sù t−¬ng t¸c víi ng−êi dïng vµ kh«ng dÔ

dµng kÕt hîp cïng víi c¸c tri thøc ®· biÕt tr−íc ®ã. ViÖc sö dông tri thøc miÒn lµ rÊt

quan träng trong khai ph¸ d÷ liÖu. §· cã nhiÒu biÖn ph¸p nh»m kh¾c phôc vÊn ®Ò

nµy nh− sö dông CSDL suy diÔn ®Ó ph¸t hiÖn tri thøc, sau ®ã sö dông nh÷ng tri thøc

ph¸t hiÖn ®−îc ®Ó h−íng dÉn cho viÖc t×m kiÕm khai ph¸ d÷ liÖu hoÆc sö dông sù

KÕt luËn ch−¬ng 1

Qu¸ tr×nh ph¸t hiÖn tri thøc trong CSDL lµ qu¸ t×nh rót ra nh÷ng tri thøc cã

Ých, tiÒm tµng trong CSDL. 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 trong ®ã, khai ph¸ d÷ liÖu lµ giai ®o¹n quan träng nhÊt, ®ã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. NhiÖm vô

cña khai ph¸ d÷ liÖu lµ kh¸m ph¸ c¸c mÉu cã Ých tõ nguån d÷ liÖu, trong ®ã, d÷ liÖu

cã thÓ ®−îc l−u tr÷ trong c¸c CSDL, kho d÷ liÖu. Ch−¬ng nµy còng tr×nh bµy c¸c

nhiÖm vô chÝnh cña khai ph¸ d÷ liÖu, c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu còng nh−

c¸c 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Õ.

Trong c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu ®· giíi thiÖu, m¹ng n¬ron vµ gi¶i

Ch−¬ng sau sÏ tr×nh bÇy chi tiÕt h¬n vÒ kü thuËt khai ph¸ d÷ liÖu dïng m¹ng n¬ron

vµ gi¶i thuËt di truyÒn.

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

28

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

2.1. M¹ng n¬ron trong khai ph¸ d÷ liÖu

Khi ®Ò cËp ®Õn khai th¸c d÷ liÖu, ng−êi ta th−êng ®Ò cËp nhiÒu ®Õn m¹ng

triÓn khai, nh−ng nã còng cã nh÷ng −u ®iÓm ®¸ng kÓ. Mét trong sè c¸c −u ®iÓm ph¶i

kÓ ®Õn lµ m¹ng cã kh¶ n¨ng t¹o ra c¸c m« h×nh dù ®o¸n cã ®é chÝnh x¸c cao, cã thÓ

¸p dông cho rÊt nhiÒu lo¹i bµi to¸n kh¸c nhau, ®¸p øng ®−îc c¸c nhiÖm vô ®Æt ra cña

thuéc thêi gian,....

2.1.1. Kh¸i niÖm m¹ng n¬ron

hay m¹ng n¬ron sinh häc cña con ng−êi nãi riªng. Trong luËn v¨n nµy, khi nãi ®Õn

häc (Biological Neural Network - BNN) cã cÊu t¹o phøc t¹p h¬n nhiÒu so víi m¹ng

qu¸t nµo vÒ m¹ng n¬ron, song phÇn lín nh÷ng nhµ nghiªn cøu trong lÜnh vùc nµy

®Òu thèng nhÊt víi kh¸i niÖm:

M¹ng n¬ron lµ mét hÖ thèng gåm nhiÒu phÇn tö xö lý ®¬n gi¶n gäi lµ c¸c

n¬ron ®−îc liªn kÕt víi nhau vµ cïng ho¹t ®éng song song. TÝnh n¨ng ho¹t ®éng cña

m¹ng phô thuéc vµo cÊu tróc m¹ng, träng sè liªn kÕt gi÷a c¸c n¬ron vµ qu¸ tr×nh xö

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

29

lý bªn trong c¸c n¬ron. Ngoµi chøc n¨ng xö lý, hÖ thèng cßn cã kh¶ n¨ng häc sè

liÖu vµ tæng qu¸t ho¸ tõ c¸c sè liÖu ®· häc.

2.1.2. N¬ron sinh häc vµ m¹ng n¬ron sinh häc

HÖ thÇn kinh con ng−êi cã kho¶ng 10¹⁰tÕ bµo thÇn kinh ®−îc gäi lµ c¸c n¬

ron, mçi n¬ron cã thÓ liªn kÕt víi 10⁴n¬ron kh¸c th«ng qua c¸c khíp nèi [12].

Khíp nèi (Synaspe)

Trôc (Axon)

Nh©n

(Soma)

H×nh 2.1: CÊu t¹o cña n¬ron

truyÒn tíi c¸c n¬ron kh¸c ®−îc nèi víi ®Çu ra qua trôc.

§é lín cña c¸c tÝn hiÖu vµo cã thÓ bÞ thay ®æi khi ®−îc truyÒn qua c¸c khíp

thÇn kinh cã trªn c¸c nh¸nh thÇn kinh vµo. Tû lÖ biÕn ®æi tÝn hiÖu ë khíp thÇn kinh

t¹o.

D−¬ng ThÞ HiÒn Thanh – CNTT 2006