Xem mẫu
- Chu.o.ng 9 ˆ ` ˆ NHAN DANG VA NOI SUY . . . Chu.o.ng n`y tr` b`y mˆt sˆ k˜ thuˆt nhˆn dang v` nˆi suy anh. C´c vˆ n d` d ˇt ra .´ ´ e. ˙ ’ a ınh a ooy a a ao a a ¯ˆ ¯a . . . . o. d ˆy liˆn quan chu yˆu d e n nh˜.ng u.ng dung trong phˆn t´ch anh tu. d ˆng. ’´ ´ ˙ ¯a e ’ ˙ e ¯ˆ aı˙ ’ u´ . ¯o . . Phˆn t´ anh tu. d ˆng l` qu´ tr`nh ph´t hiˆn, nhˆn dang v` hiˆ’u c´c mˆu trˆn ˙ ˜ a ıch ˙’ . ¯o aaı a e a aea a e . . . . . so. cua mˆt anh. Mˆt trong nh˜.ng muc d´ch ch´nh cua phˆn t´ anh tu. d ˆng l` co ˙ ˙’’ o˙ .’ ˙’ a ıch ˙ ’ o u . ¯ı ı . ¯o a . . thiˆt kˆ c´c m´y c´ kha nˇng nhˆn biˆt d .o.c nhu. con ngu.`.i theo ngh˜ n`o d o. Chˇng˙ ’ ´´ ´ a o ˙a ’ e ea a e ¯u . o ıa a ¯´ a . han, trong hˆ thˆng nhˆn dang ch˜. viˆt t`. c´c trang t`i liˆu (anh), c´c mˆu quan tˆm ˜ .´ ´ ae˙ .’ eo a. u eua a a a . . l` c´c k´ tu. v` muc tiˆu l`m sao nhˆn dang d .o.c c´c ch˜. c´i mˆt c´ch ch´nh x´c. aa y. a . ea a ¯u . a ua o a ı a . . . Do d ´, mˆt hˆ thˆng phˆn t´ch anh tu. d ˆng cˆn c´ kha nˇng thˆng minh v´.i .´ `o aı˙ ’ ˙a ’ ¯o oeo . ¯o a o o . . m´.c d o n`o d ´. Thˆng minh l` kh´i niˆm mˆp m`., d ˇc biˆt d ˆi v´.i c´c m´y. Tuy ´ u ¯ˆ a ¯o o aae a o ¯a e ¯o o a a . . . . . .p c´c quan niˆm kh´c nhau v´.i kh´i niˆm thˆng minh. nhiˆn, ta c´ thˆ’ dˆ d`ng kˆt ho a ˙e o e˜a ´ e e. e a o ae o . . Mˆt v`i d ˇc tru.ng cˆn quan tˆm l`: ` o a ¯a a aa . . 1. kha nˇng t´ch thˆng tin th´ch ho.p tu.o.ng u.ng c´c chi tiˆt trong anh; ´ ˙a ’ ˙ ’ a o ı ´ a e . 2. kha nˇng hoc c´c v´ du v` tˆ’ng qu´t ho´ tri th´.c c´ d u.o.c dˆ’ ´p dung v`o c´c ˙ ˙ ˙a ’ . a ı . ao a a u o ¯ . ¯e a aa . t` huˆng m´.i kh´c nhau; v` ´ ınh o o a a 3. kha nˇng suy luˆn t`. nh˜.ng thˆng tin khˆng d` y d ˙ . ˙a ’ ’ auu o o ¯ˆ ¯u a . Trong ch`.ng mu.c n`o d ´ (phu thuˆc v`o vˆ n d` cˆn giai quyˆt) ch´ng ta c´ thˆ’ ˙ o a a ¯ˆ `´ ea ´ ˙’ u . a ¯o e u oe . . .i c´c d ac tru.ng trˆn. Xˆy du.ng c´c hˆ thˆng c´ ´´ .´ .´ aı˙ ’ thiˆt kˆ c´c hˆ thˆng phˆn t´ch anh v´ a ¯ˇ e ea e o o e a aeo o . . .c hiˆn nh˜.ng ch´.c nˇng phˆn t´ch anh nhu. con ngu.`.i vˆn l` vˆ n d` c`n ˜ ´e ˙a ’ aı˙ ’ kha nˇng thu e u ua o a a a ¯ˆ o . . .a giai quyˆt d .o.c. Nghiˆn c´.u c´c hˆ thˆng sinh hoc v` t´ to´n dˆ’ giai th´ch ˙’ ´ .´ ˙ ’ . a ınh a ¯e ˙ chu e ¯u . euaeo ı 285
- hˆ thˆng nhˆn dang cua thi gi´c ngu.`.i c`n d ˜ .´ ´ ` ´ ˙ ’ eo a .a o o ¯ang tiˆp diˆn. Tuy nhiˆn, trong hˆu hˆt e e e ae . . .`.ng ho.p, phˆn t´ anh bˇ ng m´y t´nh d e’ giai quyˆt nh˜.ng b`i to´n chuyˆn ˙’ ` ´ a ıch ˙ ’ ¯ˆ ˙ c´c tru o a a aı e u a a e . .a v`o nh˜.ng ph´t biˆ’u heuristic. Chˇng han, mˆt sˆ m´y c´ kha nˇng d c c´c ˙ ˙ ’ .´ o o a o ˙ a ¯o a’ dung du a u ae a . . . . .i tˆc d ˆ nhanh ho.n rˆ t nhiˆu tˆc d ˆ cua con ngu.`.i. Nhu.ng ´ ¯o ´ ` o ¯o ˙ ´.’ trang t`i liˆu ch´ x´c v´ o . ae ınh a o a e o . . vˆy qu´ chuyˆn dung v` do d o kh´ c´ kha nˇng mo. rˆng trong c´c .´ ˙a ’ ˙o ’. c´c hˆ thˆng nhu a aeo a e a ¯´ o o a . . .c kh´c. T´.c l`, l´ thuyˆt v` thu.c tˆ hiˆn nay cua phˆn t´ch anh phu thuˆc v`o ´ ´. ˙ ’ aı˙ ’ l˜nh vu ı a uay ea.ee oa . . . b`i to´n d at ra. a a ¯ˇ . C´c Chu.o.ng 1-3 tr` b`y nh˜.ng kiˆn th´.c co. ban cua xu. l´ anh; c´c Chu.o.ng ´ ˙ ’ ˙ ’ ˙ y˙ ’ ’ a ınh a u e u a . l´ anh; v` c´c Chu.o.ng 7-9 liˆn quan ch´nh d e n nh˜.ng u.ng 4-6 d` cˆp dˆn tiˆn xu y ˙ ¯ˆ a ¯e `´ ´ ˙ ’ ’ e. e aa e ı ¯ˆ u ´ dung trong phˆn t´ anh. Phˆn loai theo c´ch n`y, mˇc d` c´ tˆ’ ch´.c, khˆng c´ ngh˜ ˙ a ıch ˙ ’ a a a a uoo u o o ıa . . . .ng vˆ n d` trong c´c Chu.o.ng 1-6 khˆng h˜.u ´ch trong b`i to´n phˆn t´ch anh. ` ´e aı˙ ’ rˇ ng nh˜ a u a ¯ˆ a o uı aa Thu nhˆn anh, nˆng cao chˆ t lu.o.ng anh, phuc hˆi v` n´n anh thu.`.ng l` nh˜.ng u.ng ´ . ` ae˙ a˙ .’ ˙ ’ ’ a a o o au ´ . .`.i v` m´y xu. l´ d˜. liˆu h`nh anh sˆ. Trong chu.o.ng ´ ´ ˙yue ı ’ ˙ ’ dung c´ liˆn quan dˆn con ngu o a a oe ¯e o . . n`y, ch´ng ta s˜ thˆ y rˇ ng thiˆt kˆ c´c hˆ thˆng phˆn t´ch anh tu. d ˆng d oi hoi c´ ea` ´a ´´ .´ aı˙ ’ ¯` ˙ o ’ a u e ea e o . ¯o . nh˜.ng hiˆ’u biˆt hˆu hˆt c´c kiˆn th´.c trong gi´o tr`nh. ˙ e` ´aea ´ ´ u e e u a ı Co. so. cua phˆn t´ anh ˙˙ ’’ a ıch ˙ ’ 9.1 C´c phu.o.ng ph´p phˆn t´ anh c´ thˆ’ chia th`nh ba nh´m: ˙ a ıch ˙ ’ a a oe a o 1. xu. l´ m´.c thˆ p; ´ ˙y u ’ a 2. xu. l´ m´.c trung gian; v` ˙y u ’ a 3. xu. l´ m´.c cao. ˙y u ’ Mˇc d` khˆng c´ biˆn gi´.i chung gi˜.a c´c nh´m, nhu.ng c´ch phˆn chia n`y gi´p ch´ng auo oe o ua o a a a u u . ta dˆ d`ng giai quyˆt b`i to´n phˆn t´ch anh tu. d ˆng bˇ ng c´ch d .a vˆ giai t`.ng b`i ˜a ` ´ a ¯u ` ˙ u ˙ ’ aı˙ ’ e’ e eaa . ¯o a a . . nhˆt ˙aı ’ to´n con. H`nh 9.1 minh hoa kh´i niˆm n`y, trong d o v`ng giao cua c´c h`nh ch˜ a a ı ae a ¯´ u u . . . .t chı ra khˆng tˆn tai ranh gi´.i chung gi˜.a c´c tiˆn tr`nh xu. l´. V´ du, ngu.˜.ng `. ´ ˙ ’ ˙y ı. ’ n´t du e ¯´ o o o uae ı o .o.ng anh (bu.´.c tiˆn xu. l´) hoˇc cˆng cu c´ thˆ’ xem l` cˆng cu dˆ’ nˆng cao chˆ t lu . ˙ ˙ ´ o` ˙ ’ ˙y ’ oe ao . ¯e a a e ao . . .ng dung cu thˆ’. ˙ a ¯. ˙ ’ trong phˆn d oan anh tu` theo u y ´ .e . Xu. l´ m´.c thˆ p gˆm c´c ch´.c nˇng c´ thˆ’ xem nhu. c´c hoat d ˆng khˆng d `i hoi ˙ a` ´o ˙y u ’ o ¯o ˙ ’ a ua oe a . ¯o . thˆng minh trong hˆ thˆng phˆn t´ anh. Ch´ng ta coi thu nhˆn anh v` tiˆn xu. l´ .´ a` a ıch ˙ ’ a˙ .’ ˙y ’ o eo u e .o.ng 2-6) l` c´c ch´.c nˇng m´.c thˆ p. Phˆn loai n`y c´ t´c dung t´ cu.c do c´c ´ (Chu aa ua u a a . a oa . ıch . a 286
- Xu. l´ m´.c trung gian ˙y u ’ Phˆn d oan a ¯. Biˆ’u diˆn v` .................................................................................................... ˙ ˜a e e ........................ .. . . . . . . . . . . ................................. ................................................................. . . . . . . ˙ ’ e˙ ’ . anh miˆu ta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . .. . . .. ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . .. .. . . .. . . . .. .. .. . . . . . . ` Tiˆne . ................................... ... . .. . . . . . . . . . . . . . xu. l´ ˙y ’ Nhˆn dang a . . . .. .. . ... . . . Co. so. ´ . Kˆt e . ˙’ . v` a . . . . . .. .. . . . . . . ....... .................................. .... . . . . . . . . . . . .. ... . ...................... . .. . . . . tri th´.c . . nˆi suy o . u . . . ˙ ’ qua . . . . . . . . . . B`i a Thu nhˆn a . .. ................................... ..... .. . . . . . . . . . . . . . ........................ . . . . . . . . ... . ˙’ anh to´n a Xu. l´ m´.c thˆ p Xu. l´ m´.c cao ´ ˙y u ’ ˙y u ’ a ` ’.´ ˙eo a ıch ˙ ’ H` 9.1: C´c th`nh phˆn cua hˆ thˆng phˆn t´ anh. ınh a a a anh cˆn phai ho`n thiˆn chˇng han giam nhiˆu hay nho`. C´c ch´.c nˇng m´.c thˆ p c´ ˙ ’ ˜ ` ´ ˙ ’ ˙ ’ ˙’ a a e a e ea ua u ao . . thˆ’ so s´nh v´.i c´c qu´ tr` cam nhˆn v` th´ch nghi m` mˆt ngu.`.i t` mˆt chˆ ngˆi ˙ ˜o o` a ınh ˙ ’ e a oa aaı ao o ım o . . . ngay sau khi d i t`. ngo`i (s´ng) v`o rap h´t (tˆi). Qu´ tr` (thˆng minh) t`m mˆt ´ ¯u aa a. a o a ınh o ı o . ˜ trˆng chı c´ thˆ’ bˇt d` u khi ngu.`.i d o nhˆn th´.c d u.o.c mˆi tru.`.ng xung quanh, ˙ a ¯ˆ ´a o´ ˙o e ’ chˆ o o ¯´ a u ¯. o o . .c c´ mˆt anh th´ ho.p. Xu. l´ bo.i n˜o trong hˆ thˆng thi gi´c d e’ tao ra mˆt anh ˙ .´ t´ o o ˙ .’ ˙y˙ a ’ ’ o˙ .’ u ıch . eo . a ¯ˆ . nhu. thˆ l` mˆt t´c d ˆng tro. lai tu. d ˆng khˆng c´ y th´.c. ´ ˙ . . ¯o ’ e a o a ¯o o o´ u . . . Xu. l´ anh m´.c trung gian nghiˆn c´.u c´c tiˆn tr`nh phˆn t´ch v` d ac tru.ng c´c ´ ˙ y˙ ’ ’ u euae ı aa a ¯ˇ a . th`nh phˆn (chˇng han, c´c v`ng) trong anh d˜ qua bu.´.c xu. l´ m´.c thˆ p. Nhu. H` ˙ ’ ` ´ ˙’ ˙y u ’ a a a au a o a ınh . . l´ m´.c trung gian bao gˆm phˆn d n v` tr´ch chon d ac tru.ng su. ` ˙ ’ a˙ ’ ˙ ’ 9.1 chı ra, c´c xu y u o a ¯oa a ı . ¯ˇ . . dung c´c k˜ thuˆt d ˜ d` cˆp trong c´c Chu.o.ng 7-8. Mˆt sˆ kha nˇng thˆng minh cˆn . ´ ˙a ` ’ ay a ¯a ¯ˆ a e. a oo o a . . .o.c d .a v`o d e’ tao ra c´c thu tuc phˆn d oan mˆm deo. Chˇng han, lˆ p c´c chˆ ˙ ˙ ’ ˜ ` ´ ˙. ’ ˙ ’ d u . ¯u a ¯ˆ . ¯ a a ¯. e a aa o . trˆng nho xuˆ t hiˆn trong d u.`.ng biˆn sau khi phˆn d oan c´ liˆn quan d e n xu. l´ m´.c ´ ´e ´ ˙y u ˙a ’ ’ o ¯o e a ¯. o e ¯ˆ . .n l` c´c phan u.ng tu. d ˆng m´.c thˆ p. ´ ˙´ ’ trung gian ho a a . ¯o u a . Cuˆi c`ng, xu. l´ m´.c cao liˆn quan d e n nhˆn dang v` nˆi suy v` l` muc tiˆu ´ ´ ˙y u ’ ou e ¯ˆ a ao aa . e . . . .o.ng n`y. Hai tiˆn tr`nh n`y rˆ t giˆng v´.i qu´ tr`nh m` ta thu.`.ng goi l` ´ ´´ ınh ˙ ’ ch´ cua chu a e ı aao o aı a o .a .c thˆng minh. Da sˆ c´c k˜ thuˆt d u.o.c su. dung trong qu´ tr` xu. l´ m´.c - ´ a¯. ˙ . ’ a ınh ˙ y u ’ nhˆn th´ a u o oa y . . .c trung gian du.a trˆn co. so. l´ thuyˆt. Tuy nhiˆn, tiˆn tr`nh nhˆn dang, ´ ´ ´ ˙y ’ thˆ p v` m´ aau e e e e ı a . . . 287
- v` d ˇc biˆt nˆi suy, tri th´.c v` nh˜.ng hiˆ’u biˆt cua ch´ng ta d ong vai tr` quan trong ˙ ´’ e˙ a ¯a eo uau e u ¯´ o . .. . .n l` nh˜.ng nguyˆn tˇc mang t´nh l´ thuyˆt. N´i chung, tri th´.c ´ ´ trong suy luˆn ho a u a ea ı y e o u . .`.ng d .o.c thiˆt kˆ ˜ .´ ´´ trong mˆi b`i to´n l` kh´c nhau nˆn c´c hˆ thˆng nhˆn dang thu o oa aaa eaeo a ¯u . ee . . chuyˆn dung. e . Chu.o.ng n`y s˜ d` cˆp d e n: ´ a e ¯ˆ a ¯ˆ e. 1. phu.o.ng ph´p nhˆn dang theo l´ thuyˆt quyˆt d .nh; ´ ´ a a y e e ¯i . . 2. phu.o.ng ph´p nhˆn dang cˆ u tr´c; v` ´ a a a u a . . 3. phu.o.ng ph´p nˆi suy. ao . Nhˆn dang theo l´ thuyˆt quyˆt d .nh (Phˆn 9.3) du.a v`o biˆ’u diˆn c´c mˆu (pattern) ˙ ˜a ˜ ´ ´ ` a. y e e ¯i a .a e e a . dang vector v` sau d ´ t` kiˆm c´ch d e’ nh´m v` g´n c´c mˆu v`o c´c l´.p mˆu ˙ ˜ ˜ ´ a ¯o ım e a ¯ˆ o aa a a aao a . (pattern class) kh´c nhau. a Mˆu v` c´c l´.p ˜ 9.2 a aa o Nhu. d ˜ d` cˆp trong Phˆn 9.1, kha nˇng thu.c hiˆn nhˆn dang mˆu o. m´.c n`o d o ˜’ ` ˙a ’ a ˙ u a ¯´ ¯a ¯ˆ ae. a e a . . . . . l` mˆt tiˆn tr` cˇn ban trong phˆn t´ch anh. O d ˆy, mˆu l` mˆt d ˇc tru.ng d .nh ˙ ¯a ’ ˜ ´ ˙ ’ aı˙ ’ aoe ınh a a a o ¯a ¯i . . . .o.ng hoˇc l` d ˇc tru.ng cˆ u tr´c cua mˆt d ˆi tu.o.ng hoˇc thu.c thˆ’ cˆn quan tˆm ˙a ´ ´ e` ˙ ’ lu . a a ¯a a u o ¯o a a . . . . . . n`o d ´ trong anh. Nhu. d ˜ d` cˆp trong Chu.o.ng 8, n´i chung mˆu d u.o.c tao ra t`. ˜ ˙ ’ a ¯o ¯a ¯ˆ a e. o a ¯. . u .ng. N´i c´ch kh´c, mˆu l` mˆt vector nhiˆu chiˆu, trong d o ˜ ` ¯ˇ ` ` mˆt hoˇc nhiˆu d ac tru o a e oa a aao e e ¯´ . . . . mˆi th`nh phˆn cua vector tu.o.ng u.ng mˆt d ˇc tru.ng cua d ˆi tu.o.ng. (Thuˆt ng˜. d ˇc ˜ ` ’´ ˙’ ˙ ¯o o a a ´ o ¯a a u ¯a .. . . . .ng thu.`.ng d .o.c su. dung trong c´c t`i liˆu nhˆn dang mˆu nhˇ m ´m chı c´c k´˜ `a ˙. ’ ˙a y ’ tru o ¯u . aae a a a . . . . t`., ng˜.). L´.p c´c mˆu l` mˆt tˆp c´c mˆu c´ chung nh˜.ng t´ chˆ t n`o ˜ ˜ ´ hiˆu nhu u e u oa aaoaa ao u ınh a a . .. .p mˆu l` ω , ω , . . . , ω , trong d o M l` sˆ c´c l´.p. Nhˆn dang mˆu ˜ ˜ ´ d ´. K´ hiˆu c´c l´ ¯o y e a o aa12 ¯´ aoa o a. a . . M bˇ ng m´y liˆn quan d e n c´c k˜ thuˆt g´n c´c mˆu v`o c´c l´.p tu.o.ng u.ng cua ch´ng ` ˜ ´ ˙ ’ a ae ¯ˆ a y aaa a aao ´ u . . d ˆng v` tr´nh su. can thiˆp cua con ngu.`.i. e˙ ’ mˆt c´ch tu ¯o oa aa o . .. . . Ba c´ch sˇp xˆp mˆu ch´ thu.`.ng su. dung trong thu.c tˆ l` c´c vector (d oi v´.i ´´ ˜ ´ ´ ˙. ’ a ae a ınh o . eaa ¯ˆ o .ng d nh lu.o.ng), c´c chuˆi v` c´c cˆy (d oi v´.i c´c miˆu ta cˆ u tr´c). C´c ˜ ´ ’´ e ˙a c´c d ac tru a ¯ˇ ¯i a o a a a ¯ˆ o a u a . . . 288
- vector mˆu d .o.c biˆ’u diˆn bo.i c´c k´ tu. thu.`.ng d am nhu. x, y, v` z, v` c´ dang ˙ ˜ ˜ ˙ a y. ’ a ¯u . e e o ¯ˆ a ao. . x1 x2 x = . , . . xn trong d o xi l` d ac tru.ng th´. i v` n l` sˆ c´c d ac tru.ng. C´c vector mˆu d .o.c viˆt ˜ ´ ´ ¯´ a ¯ˇ u a a o a ¯ˇ a a ¯u . e . . dang vector cˆt. Do d ´ ta c´ thˆ’ viˆt x = (x1, x2 , . . . , xn ) . ˙´ t o ¯o oee . . ˜ ´’ ` ınh a ˙ a ˙ ’ T´ chˆ t cua c´c th`nh phˆn cua mˆt vector mˆu phu thuˆc v`o k˜ thuˆt d o a a o a oay a¯ . . . . .`.ng d u.o.c su. dung dˆ’ miˆu ta ban chˆ t cua mˆu. Chˇng han, gia su. ta muˆn miˆu ˙e˙˙ ˜ ˙ ’ ´˙ ´ ˙. ’ ’’ ’ ˙˙ ’’ lu o ¯. ¯e a a a o e . ´ ` ˙’ ta ba loai hoa ng˜ sˇc (setosa, virginica v` versicolor) bˇ ng c´ch d d o rˆng v` d ˆ d`i ua a a a ¯o ¯ˆ o a ¯o a . .. . ˙ a ch´ng. Trong tru.`.ng ho.p n`y, ta su. dung vector 2D ’ ˙. ’ c´c c´nh hoa cu aa u o a . x1 x= , x2 trong d ´ x1 , x2 tu.o.ng u.ng d ˆ rˆng v` d ˆ d`i cua c´nh hoa. Trong tru.`.ng ho.p n`y, ba a ¯o a ˙ a ’ ¯o ´ ¯o o o a .. . . .p mˆu l` setosa, virginica v` versicolor. ˜ l´ o aa a Nˆu ch´ng ta miˆu ta d ˆi tu.o.ng bˇ ng k´ sˆ cua n´ (xem Phˆn 8.1.3) th` ta nhˆn ` ´ ’´ ´’ ` e ˙ ¯o yo ˙ o e u a a ı a . . .o.c mˆt h`m 1D. Lˆ y mˆu h`m n`y tai c´c d e’m θ , θ , . . . , θ , v` x´t vector mˆu ˙ ˜ ˜ ´ du . ¯ oa a aa a . a ¯iˆ ae a . 12 n x = (x1 = r(θ1 ), x2 = r(θ2), . . . , xn = r(θn ))t . C´c vector n`y l` c´c d iˆ’m trong khˆng gian n chiˆu v` c´c l´.p mˆu tro. th`nh c´c ˙ ˜ ` ˙a ’ a a a a ¯e o e aa o a a “d ´m mˆy” trong khˆng gian n`y. ¯a a o a Thay v` su. dung tru.c tiˆp biˆn d o cua k´ sˆ, ch´ng ta c´ thˆ’ t´nh chˇng han n ˙ ˙ ’ ´ ´u ı˙ . ’ e ¯ˆ ˙ y o .’ e o eı a . . ´’ ´ ` ` a˙ moment bˆc nhˆ t cua mˆt k´ sˆ d ˜ cho (Phˆn 8.2.4) v` xem ch´ng l` c´c th`nh phˆn a o y o ¯a a a u aa a a . . .o.ng u.ng. Thˆt ra c´ mˆt sˆ c´ch kh´c nhau d e’ tao ra c´c vector ˙ ˜ .´ ˙ ’ cua vector mˆu tu a ´ a o o oa a ¯ˆ . a . mˆu. Ch´ng ta s˜ d` cˆp d e n c´c phu.o.ng ph´p trong chu.o.ng n`y. Cˆn ch´ y rˇ ng, ˜ ` ´ ` a u e ¯ˆ a ¯ˆ a e. a a a u´ a .`.ng d e’ tao ra c´c th`nh phˆn cua vector mˆu c´ ˙ ˜ ` .´ ` ˙ ’ chon mˆt hoˇc nhiˆu hˆ thˆng d o lu o o a eeo¯ ¯ˆ . a a a ao . . . mˆt anh hu.o.ng rˆ t l´.n d e n kˆt qua thu.c hiˆn sau c`ng cua hˆ thˆng phˆn t´ch anh ´ ´´ ’.´ o˙ .’ ˙ ’ ˙ ’. ˙eo aı˙ ’ a o ¯ˆ e e u . .a v`o c´ch tiˆp cˆn phˆn loai theo vector mˆu. ˜ ´. du a a ea a a . . C´c k˜ thuˆt d u.o.c mˆ ta trˆn dˆ’ tao ra c´c vector mˆu v` do d ´ c´c l´.p mˆu ˙ ˜ ˜ o ˙ e ¯e . ’ ay a¯. a aa ¯o a o a . .a v`o thˆng tin d inh lu.o.ng. Trong mˆt sˆ u.ng dung, c´ch tˆt nhˆ t dˆ’ lˆ y c´c d ac ´ ˙´ .´ ´ du a o ¯. o o´ a o a ¯e a a ¯ˇ . . . . .ng cua mˆu du.a trˆn c´c quan hˆ cˆ u tr´c. Chˇng han, nhˆn dang vˆn tay du.a ˜ ˙ ’ .´ ˙ ’ tru a ea ea u a a a . . . . . .a c´c d ˇc tru.ng dˆ u vˆt goi l` c´c tiˆ’u tiˆt. C´c d ac tru.ng n`y ˙e ´ ´ e . aa e ´ ´ trˆn mˆi quan hˆ gi˜ a ¯a e o eu a a ¯ˇ a . . . 289
- a a ··· ··· .. .. . . .. . .. . .................... . . . . .. . . . . . ................... . . . . . . . . ..... . .................... . . . . . . .. .... . . . . . . . . . . . . . . . . . . . . . . b ba . . . . . . . . . . . . . ... ... . . . . . . .. .. . .. . .................... ..................... . . . . .. . . ..... .. . . . .. . . . . . . . . . .. . . . . . . . . . . . . . ba . . . . . . . . . . . . . .. ... . ..................... .................... .... .. . . . ... .. . .. .. . . . . . . .. .. .. . . . . . . . . . . . . . ba . . . . . . . . ... . . . . .. . .................... .................... .. .. .. . . . . . ... . . . . . . . . . .. . . .. .. . . . . . ............................... .............a............... . . ... .. . .. .. . . . . . . . . . . . . . . . ba . . . . . . . . . . .. . ... . . ................... ··· ··· .................... .. .. . . . . . .. . . . . .. . . . . . .. .... . . . . (a) (b) H` 9.2: (a) Cˆ u tr´c h`nh bˆc thang; (b) cˆ u tr´c d .o.c m˜ ho´ theo c´c nguyˆn so. ´ ´ ınh a uı a a u ¯u . aa a e . a v` b v` chuˆi biˆ’u diˆn l` · · · ababab · · · . ˙ ˜ ˜a a a oe e l` c´c th`nh phˆn nguyˆn so. mˆ ta c´c t´ chˆ t d u.`.ng vˆn tay nhu. c´c d iˆ’m cut, ˙ ` ´ o ˙ a ınh a ¯ o ’ aa a a e a a ¯e . ˙m r˜ nh´nh, c´c d . n du.t qu˜ng c`ng v´.i c´c k´ thu.´.c v` vi tr´ tu.o.ng d oi cua ’ea ´’ ¯ˆ ˙ d iˆ ¯e a ¯oa ¯´ a u o a ıch o a.ı .o.ng c`n c´ c´c -e ˙ ch´ng. Dˆ’ giai quyˆt c´c b`i to´n dang n`y (ngo`i c´c thˆng sˆ d inh lu . ˙’ ´ ´ u eaaa. a aa o o ¯. o oa mˆi quan hˆ khˆng gian gi˜.a c´c d ac tru.ng), c´ch tˆt nhˆ t du.a theo phu.o.ng ph´p ´ ´ ´. o eo u a ¯ˇ a o a a . . ´ cˆ u tr´c. a u H` 9.2(a) minh hoa d ˆi tu.o.ng c´ dang bˆc thang. Ta c´ thˆ’ lˆ y mˆu v` biˆ’u˙´ ˙ ˜ ´ ınh . ¯o o. a o ea aae . . diˆn d oi tu.o.ng n`y theo dang vector mˆu tu.o.ng tu. nhu. c´ch tiˆp cˆn d .o.c su. dung ˜ ¯ˆ ˜ ´ ´. e a ¯u . ˙ . ’ e a a a . . . trong H` ??. Tuy nhiˆn cˆ u tr´c co. so. gˆm c´c ph´p lˇp cua hai nguyˆn so. d o.n ´ ˙` ’o ˙’ ınh ea u a ea e ¯ . .o.ng ph´p miˆu ta n`y. Ch´ng ta c´ thˆ’ miˆu ta bˇ ng ˙ ’` ´ ˙ e. a ’ e ˙a’ oe e ˙a gian s˜ bi mˆ t khi ´p dung phu a a u . c´ch d inh ngh˜a hai phˆn tu. a v` b v` xem mˆu l` chuˆi c´c k´ hiˆu w = · · · ababab · · · ˜ ˜ `˙ a’ a ¯. ı aa aa oaye . . trong H` 9.2(b). Du.a v`o liˆn kˆt c´ th´. tu. cua chuˆi v` xen k˜ cua hai nguyˆn ˜ ´ . a e eo u.˙ ’ e˙ ’ nhu ınh oa e so., cˆ u tr´c cua l´.p c´c mˆu dang d ac biˆt n`y d u.o.c gi˜. lai theo c´ch biˆ’u diˆn n`y. ˙ ˜ ˜a ´ u˙oa ’ a a ¯ˇ e a¯. u. a e e . . . .ng cˆ u tr´c nhu. vˆy c´ thˆ’ ´p dung khˆng nh˜.ng cho c´c bˆc thang c´ ˙ ´ C´ch xˆy du a a a u a o ea o u aa o . . . . d ˆ d`i tu` y m` c`n cho c´c cˆ u tr´c kh´c d .o.c sinh ra bˇ ng c´ch tˆ’ ho.p c´c nguyˆn ˙ ` ´ ¯o a y´ a o aa u a ¯u . a a o. a e . . a v` b. (Nhˇc lai l` c´c phu.o.ng ph´p ph´.c tap ho.n d e’ tao ra c´c chuˆi mˆu d .o.c ˙ ´ ˜˜ so a a .aa a u. ¯ˆ . a o a ¯u . ` tr` b`y trong Phˆn 8.5). ınh a a C´c biˆ’u diˆn chuˆi mˆt c´ch th´ ho.p sinh ra c´c mˆu cua c´c d oi tu.o.ng v` ˙ ˜ ˜ ˜ ´ ˙ a ¯ˆ ’ a e e ooa ıch . a a a . . c´c thu.c thˆ’ kh´c m` cˆ u tr´c cua ch´ng du.a trˆn liˆn kˆt d o.n gian cua c´c nguyˆn ˙ ´ ´ u˙ ’ ˙ ’ ˙a ’ a ea aa u e e e¯ e . . . thu.`.ng d u.o.c kˆt ho.p v´.i h`nh dang cua biˆn. Trong nhiˆu u.ng dung, dˆ’ hiˆu qua ˙. ´ `´ ˙’ ˙ ’ so o ¯. e . oı e e ¯e e . . ho.n khi miˆu ta c´c d ˆi tu.o.ng ta c´ thˆ’ d`ng cˆy nhu. trong Phˆn 8.5. Vˆ co. ban, ˙ ´ ` ` e ˙ a ¯o ’ ˙ ’ o eu a a e . . d` th`.a kˆ c´ th´. tu. c´ thˆ’ d u.a vˆ cˆ u tr´c dang cˆy. ˙ ` ´ ´ `a e´ hˆu hˆt c´c so ¯ˆ u e o u . o e ¯ aea o u. a 290
- Phu.o.ng ph´p l´ thuyˆt quyˆt d .nh ´ ´ 9.3 ay e e ¯i Phu.o.ng ph´p quyˆt d .nh su. dung h`m quyˆt d.nh (decision function) hay h`m biˆt ´ ´ ˙. ’ a e ¯i a e ¯i a e . . ω , ω , . . . , ω l` c´c l´.p mˆu. X´t vector mˆu n ˜ ˜ ˙˙ ’’ tˆp (discriminant function). Gia su 1 2 a Maa o a e a . chiˆu x = (x1, x2, . . . , xn )t . Vˆ n d` co. ban trong phu.o.ng ph´p nhˆn dang theo phu.o.ng ` ´e ˙ ’ e a ¯ˆ a a. . ˜ ´ ´ ph´p quyˆt d .nh l` t`m M h`m biˆt tˆp d1 (x), d2 (x), . . . , dM (x) sao cho nˆu mˆu x a e ¯i aı a ea e a .. thuˆc l´.p ωi th` oo ı . di (x) > dj (x), (9.1) v´.i moi j = 1, 2, . . . , M, j = i. o . Biˆn t´ch hai l´.p ωi v` ωj l` tˆp ea o a aa . {x | di (x) − dj (x) = 0}. Trong thu.c tˆ dˆ’ x´c d .nh biˆn gi˜.a hai l´.p ta su. dung h`m dij (x) = di (x) − dj (x). ´˙ ˙. ’ . e ¯e a ¯i e u o a .i c´c mˆu thuˆc l´.p ω v` d (x) < 0 d oi v´.i c´c mˆu thuˆc ˜ ˜ ´ ´ Do d ´ dij (x) > 0 d oi v´ a ¯o ¯ˆ o a oo i a ij ¯ˆ o a a o . . .p ω . l´ o j Muc d´ ch´ cua phˆn n`y l` tr` b`y c´c c´ch dˆ’ t`m c´c h`m biˆt tˆp thoa ˙ ` . ¯ıch ınh ˙ ’ ˙ ’ a a a ınh a a a ¯e ı aa ea .. m˜n Phu.o.ng tr`nh (9.1). a ı -o a ´ 9.3.1 Dˆi s´nh Phˆn l´.p theo khoang c´ch nho nhˆt ˙ ’ ˙ ’ ´ ao a a Gia su. mˆi l´.p mˆu d .o.c biˆ’u diˆn bo.i vector trung b`nh (hay vector mˆu): ˙ ’’ ˜ ˜ ˜ ˜ ˙˙ oo ˙ ’ a ¯u . e e ı a 1 mi = x, j = 1, 2, . . . , M, Nj x∈ωj trong d ´ Nj l` sˆ c´c vector mˆu trong l´.p ωj . Dˆ’ t`m l´.p mˆu ch´.a vector mˆu x -e ı o ˙ ˜ ˜ ˜ ´ ¯o aoa a o a u a .i n´ nhˆ t. Cu thˆ’, d at ˙. ınh ` ´ ch´ng ta t`m vector trung b` gˆn v´ o a u ı ao . e ¯ˇ Dj (x) = x − mj , j = 1, 2, . . . , M, a, a l` chuˆ’n Euclid. Khi d o ta g´n x thuˆc l´.p ωi nˆu Di (x) nho ˙ ´ ˙ ’ trong d ´ a = ¯o a a ¯´ a oo e . .c l` theo cˆng th´.c n`y, khoang c´ch nho nhˆ t suy ra d oi s´nh tˆt nhˆ t. Dˆ˜ ´ ´ ´ ´ ´ ˙ ’ ˙a ’ nhˆ t. T´ a a u o ua a ¯ˆ a o a e d`ng ch´.ng minh rˇ ng, x thuˆc l´.p ωi nˆu di (x) l´.n nhˆ t, trong d o ` ´ ´ a u a oo e o a ¯´ . 1 dj (x) = x, mj − mj , mj , j = 1, 2, . . . , M. (9.2) 2 291
Chính trị học
Báo chí - Truyền thông
Xã hội học
Giáo dục học
Tâm lý học
Lịch sử - Văn hoá
Triết học
Ngôn ngữ học
Thư viện thông tin
Văn học nước ngoài
Ngư nghiệp
Hành chính - Pháp luật
Địa lý - Địa danh
Văn học Việt nam
Lịch sử Đảng
CNXH - KH
Tư Tưởng HCM
Ngụ ngôn - Cổ tích
Ca dao - Tục ngữ
Hoá học
Sinh học
Y khoa - Dược
Kinh tế học