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
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
Chuyªn ngµnh: C«ng nghÖ th«ng tin
LuËn v¨n th¹c sü c«ng nghÖ th«ng tin
Ngêi híng dÉn khoa häc:
Pgs. Ts. NguyÔn thanh thñy
Hµ néi - 2008
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
...................................................................... Error! Bookmark not defined.
1.1.1. T¹i sao cÇn ph¸t hiÖn tri thøc? .................... Error! Bookmark not defined.
1.1.2. Khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖuError! Bookmark
not defined.
1.2. Qu¸ tr×nh ph¸T HIÖN TRI THøC trong C¥ Së D÷ LIÖUError! Bookmark
not defined.
1.2.2. Thu thËp vµ tiÒn xö lý d÷ liÖu ..................... Error! Bookmark not defined.
1.2.3. Khai ph¸ d÷ liÖu .......................................... Error! Bookmark not defined.
1.2.4. Minh ho¹ vµ ®¸nh gi¸ .................................. Error! Bookmark not defined.
1.2.5. §a kÕt qu¶ vµo thùc tÕ ............................... Error! Bookmark not defined.
1.3. c¸c kü thuËt Khai ph¸ d÷ liÖu ....... Error! Bookmark not defined.
1.3.1. KiÕn tróc cña hÖ thèng khai ph¸ d÷ liÖu ..... Error! Bookmark not defined.
1.3.3. NhiÖm vô chÝnh cña khai ph¸ d÷ liÖu.......... Error! Bookmark not defined.
1.3.4. Mét sè ph¬ng ph¸p khai ph¸ d÷ liÖu phæ biÕnError!
Bookmark
not
defined.
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........................................ Error! Bookmark not defined.
KÕt luËn ch¬ng 1 ................................. Error! Bookmark not defined.
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ÖuError!
Bookmark
not
defined.
2.1.1. Kh¸i niÖm m¹ng n¬ron ............................... Error! Bookmark not defined.
2.1.2. N¬ron sinh häc vµ m¹ng n¬ron sinh häc .... Error! Bookmark not defined.
2.1.3. M« h×nh vµ qu¸ tr×nh xö lý trong n¬ron nh©n t¹oError!
Bookmark
not
defined.
2.1.4. CÊu tróc vµ ph©n lo¹i m¹ng n¬ron .............. Error! Bookmark not defined.
2.1.5. Häc vµ lan truyÒn trong m¹ng ..................... Error! Bookmark not defined.
2.1.6. §¸nh gi¸ vÒ m¹ng n¬ron ............................. Error! Bookmark not defined.
2.2. Gi¶i thuËt di truyÒn trong khaI PH¸ D÷ LIÖUError! Bookmark not
defined.
2.2.1. C¬ b¶n vÒ gi¶i thuËt di truyÒn ..................... Error! Bookmark not defined.
2.2.2. Mét sè c¸ch biÓu diÔn lêi gi¶i cña gi¶i thuËt di truyÒnError!
Bookmark
not defined.
2.2.3. C¸c to¸n tö di truyÒn ................................... Error! Bookmark not defined.
2.2.4. C¬ së to¸n häc cña gi¶i thuËt di truyÒn ....... Error! Bookmark not defined.
2.2.5. Nh÷ng c¶i tiÕn cña gi¶i thuËt di truyÒn ....... Error! Bookmark not defined.
KÕt luËn ch¬ng 2 ................................. Error! Bookmark not defined.
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 ®Ò ............................................. Error! Bookmark not defined.
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 ....... Error! Bookmark not defined.
3.2.1. KiÕn tróc cña m¹ng n¬ron truyÒn th¼ng nhiÒu lípError! Bookmark not
defined.
3.2.2. C¬ chÕ häc cña m¹ng n¬ ron truyÒn th¼ng nhiÒu lípError! Bookmark not
defined.
3.2.3. ThuËt to¸n lan truyÒn ngîc sai sè ............. Error! Bookmark not defined.
3.2.2. Mét sè c¶i tiÕn cña gi¶i thuËt BP ................ Error! Bookmark not defined.
3.3. KÕt hîp gi¶i thuËt di truyÒn víi gi¶i thuËt BPError!
Bookmark
not defined.
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 Error!
Bookmark not defined.
3.3.2. GhÐp nèi víi gi¶i thuËt lan truyÒn ngîc sai sèError!
Bookmark
not
defined.
KÕt luËn ch¬ng 3 ................................. Error! Bookmark not defined.
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 ............................. Error! Bookmark not defined.
4.2. m« h×nh ho¸ bµi to¸n, thiÕt kÕ d÷ liÖu vµ gi¶i thuËt.................. Error!
Bookmark not defined.
4.2.1. M« h×nh ho¸ bµi to¸n .................................. Error! Bookmark not defined.
4.2.2. ThiÕt kÕ d÷ liÖu ........................................... Error! Bookmark not defined.
4.2.3. ThiÕt kÕ gi¶i thuËt ....................................... Error! Bookmark not defined.
4.3. ch¬ng tr×nh dù b¸o d÷ liÖu .......... Error! Bookmark not defined.
KÕt luËn ch¬ng 4 ................................. Error! Bookmark not defined.
KÕt luËn .......................................................................................................... 99
Tµi liÖu tham kh¶o ........................................................................................ .100
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
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
Gi¶i thuËt lan truyÒn
ngîc cña sai sè
Back-Propagation of error
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 lu 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µ lu tr÷ ngµy cµng nhiÒu nhng 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 lu 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.
Cho ®Õn nay, KDD ®· ®îc øng dông réng r·i trong c¸c lÜnh vùc kh¸c nh viÔn
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
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, … nhng 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 nhng 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 nhng 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 ®· lu tr÷ trong c¸c CSDL, kho d÷ liÖu hoÆc c¸c n¬i lu 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 lu 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
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 lu 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¸
Thu thËp vµ tiÒn
xö lý d÷ liÖu
MÉ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
- Xem thêm -