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 -