Nhan Dang1

  • Published on
    05-Jul-2015

  • View
    348

  • Download
    3

Embed Size (px)

Transcript

<p>Pattern RecognitionThS.Trn thanh hng 0988565130 hungttbk@gmail.com</p> <p>Chng I. Tng quan v nhn dngnh ngha: Nhn dng i tng l mt qu trnh phn hoch i tng thnh cc i tng con, chng c gn vo tng lp nhn c i snh vi mu v i snh theo cc quy lut bit trc no .</p> <p>Nhng gii hn ca bi ton nhn dng Qu trnh Nhn dng: Dng 1: Nhn dng cc i tng c th: k t, hnh nh, ... Dng 2: Nhn dng cc i tng tru tng: vn , khi nim, ... Ch kho st bi ton thuc dng 1; Nhn dng i tng a v nghin cu cc c im:khng gian v thi gian: Cc i tng theo c trng khng gian: k t, du vn tay, bn , i tng vt l; Cc i tng theo c trng thi gian: ting ni, tn hiu in t, chui thi gian.</p> <p> Gii hn 1:</p> <p>Nhng gii hn ca bi ton nhn dng Nhng hng nghin cu ca lnh vc Nhn dng:</p> <p> Gii hn 2: Ch quan tm ti cch tip cn th hai gii quyt bi ton nhn dng Bi ton nhn dng: a ( phn chia ) nhng d liu vo cc phn nhm xc nh da trn nhng tnh cht hoc du hiu c trng cho d liu.</p> <p> Nghin cu kh nng nhn dng ca cc h thng sinh hc (ngi, ng vt): lin quan ti cc lnh vc nh tm l, sinh hc, sinh l hc, ; Pht trin cc phng php v l thuyt xy dng nhng thit b, chng trnh gii quyt bi ton nhn dng trong nhng lnh vc c th.</p> <p>Nhng bi ton Nhn dng c bn V d bi ton nhn dng: Phn loi c trong dy chuyn thnh hai loi Cc bc thc hin: Tin x l nh c nhn c t camera Phn vng i tng(c) Trch chn cc c trng: sng, chiu di, chiu rng Phn loi i tng ( c )</p> <p>Nhng bi ton Nhn dng c bn M hnh ca qu trnh nhn dng</p> <p> Qu trnh xy dng h thng nhn dng</p> <p>Nhng bi ton Nhn dng c bn Nhng c s: Khng gian o c; Cc c trng; B phn loi; Cc bin gii quyt nh; Cc mu hun luyn; Xc sut li</p> <p> Gi thit: trong cc d liu c quan st tn ti tnh quy lut t vn : da trn cc quan st b nhiu, xc nh tnh quy lut trong d liu. Cc hng tip cn: thng k v cu trc.</p> <p>Nhng bi ton Nhn dng c bn Tip cn thng k v cu trc Tip cn thng k: cc i tng c c trng bng s tng hp thng k. V d cc k t 2 u c chung mt s thuc tnh thng k.</p> <p> Tip cn cu trc: cc cu trc c biu din bng cng mt c ch xy dng. V d cc cu trong mt ngn ng.</p> <p>Nhng bi ton Nhn dng c bn Nhng kh khn c bn: Phn vng i tng; Xc nh cc c trng; Tnh bt bin; Ng cnh; Nhiu.</p> <p> Minh ha nhng kh khn:</p> <p>Nhng bi ton Nhn dng c bn Nhng bi ton c bn: Thu nhn v tin x l d liu vo; Biu din d liu: Qu trnh m ha; Biu din khng gian vector;</p> <p> Trch chn c trng: Xc nh cc c im ca i tng; Gim s chiu biu din ca vector i tng;</p> <p> Xy dng b phn loi: Xc nh nhng th tc ti u trong vic xc nh v phn loi i tng M hnh: Phn loi N lp i tng 1, 2, , N; M hnh b phn loi theo hm quyt nh</p> <p>Nhng bi ton Nhn dng c bn H thng nhn dng thch nghi</p> <p>Nhng bi ton Nhn dng c bn Bi ton hun luyn ( learning ) t vn :tn ti hay khng mt phng php gii quyt trit bi ton phn loi, nhn dng? Kt lun: kinh nghim 40 nm nghin cu cho thy: khng tn ti mt phng php nh vy. Nguyn nhn: bi ton t ra thuc nhm ill-posed Cch tip cn: learning: gii quyt vn da trn qu trnh hun luyn qua mu Hun luyn:phng php s dng nhng thng tin kinh nghim t mi trng kt hp vi nhng tri thc c sn xy dng cc b phn loi v qu trnh hiu chnh tng bc hiu qu phn loi. Nhng thng tin kinh nghim: cc mu hun luyn; Nhng tri thc: cc bt bin, hm tng quan; Qu trnh hiu chnh tng bc hiu qu phn loi.</p> <p>Nhng bi ton Nhn dng c bn Cc phng php hun luyn: Hc c gim st: c thng tin phn loi km theo mu; Hc khng gim st: hon ton khng c thng tin t mi trng; Hc tng cng: c thng tin phn hi tng phn t mi trng.</p> <p>Nhng bi ton Nhn dng c bn</p> <p>Nhng nguyn l Nhn dng Cc nguyn l nhn dng c trng ca cc phn lp: c trng ca cc phn lp: Lit k nhng phn t tham gia vo phn lp; Nhng thuc tnh chung nht ca cc phn t thuc phn lp. Nh vy h nhn dng c xy dng trn nguyn l tng qut ha c im.</p> <p> Khi kho st cc phn lp, nu d liu c xu hng to thnh cc phn cm ( cluster ) trong khng gian i tng. Khi nhn dng s dng nguyn l phn cm.</p> <p>Nhng nguyn l Nhn dng Nguyn l lit k phn t Cc phn lp c c trng bng lit k cc i tng tham gia vo phn lp; Qu trnh t ng nhn dng a v bi ton i snh mu; Tp hp i tng ca mt phn lp c lu tr trong b nh; Khi xut hin i tng mi, h thng nhn dng ln lt i snh i tng vi cc mu lu tr. Qu trnh quyt nh: i tng s thuc phn lp cha mu ging nht vi i tng. Phng php n gin. Vn : la chn tp hp mu ti u.</p> <p>Nhng nguyn l Nhn dng Nguyn l xc nh cc tnh cht chung Cc phn lp c c trng bng nhng c im chung ca cc phn t tham gia; Qu trnh nhn dng bao gm vic tm nhng c im chung trn i tng; Gi thit quan trng: Nhng i tng trong mt phn lp phi c nhng c im chung. Do cn gi thit v tnh tng ng gia nhng i tng trong nhm. Cc tnh cht chung c lu tr trong b nh. Khi c mt i tng xut hin, h thng cn phi m ha i tng v so snh vi nhng c im c lu tr; u im: so vi phng php lit k, c u im v mt lu tr, nhn dng v bn vng hn vi cc bin dng</p> <p>Nhng nguyn l Nhn dng Nguyn l phn cm Cc i tng ca phn lp c biu din bng cc vector c thnh phn thc; Cc phn lp c coi l phn cm: nhng phn t trong mt lp th co cm, nhng phn t khng thuc lp th gin cch; H thng nhn dng da trn nguyn l ny c xc nh bng nhng phn b tng i gia cc lp. V d: phn loi bng khong cch nh nht Nu cc nhm phn tch: khng c vn ln ny sinh; Nu cc nhm khng phn tch: cn c nhng tiu ch phn loi phc tp hn; S che ph gia cc nhm l kt qu ca vic thiu thng tin do nhiu.</p> <p>Nhng phng php Nhn dng Phng php Heuristic (mo) C s ca phng php heuristic l s dng kinh nghim ca ngi gim st; S dng nguyn l lit k phn t v tm cc c im chung ca i tng; Xy dng thut ton ph thuc vo tng bi ton c th; Ph thuc nhiu vo kinh nghim. Cc lut phn loi da trn nhng biu din ton hc ca cc c im i tng; Da vo nguyn l tm cc c im chung v nguyn l phn nhm; c im khc bit vi phng php heuristic: li gii c xc nh bng cc quy tc lin quan cht ch vi thuc tnh ca bi ton;</p> <p> Phng php ton hc</p> <p>Nhng phng php Nhn dng C hai dng phng php ton hc: Phng php thng k: s dng cng c ca thng k ton hc nh lut Bayes; Phng php tt nh: khng s dng cc thuc tnh thng k ca lp i tng c nghin cu nh phng php phn tch tuyn tnh, perceptrron, i tng c m t qua cc thnh phn c s v mi lin quan gia nhng thnh phn c s ; Biu din i tng bng cc xu v quy tc sinh xu Qu trnh nhn dng tr thnh bi ton phn tch c php v da vo nguyn l tng qut ha tnh cht; Vn : trch chn c nhng thnh phn c bn v xc nh c quan h gia cc thnh phn .</p> <p> Phng php cu trc</p> <p>Chng II. Phn nhm da trn l thuyt quyt nh Bayesng dng Bayes Theorem trong phn lp (Using Bayes Theorem in Classification)1. Gii thiu Bayes Theorem</p> <p>Trong lnh vc Data Mining, Bayes Theorem (hay Bayes Rule) l k thut phn lp da vo vic tnh xc sut c iu kin. Bayes Rule c ng dng rt rng ri bi tnh d hiu v d trin khai.Bayes' Rule (CT1): Trong : </p> <p>D : Data h : Hypothesis (gi thuyt) P(h) : Xc sut gi thuyt h (tri thc c c v gi thuyt h trc khi c d liu D) v gi l prior probability ca gi thuyt h. P(D| h): Xc sut c iu kin D khi bit gi thuyt h (gi l likelihood probability). P(D): xc sut ca d liu quan st D khng quan tm n bt k gi thuyt h no. (gi l prior probability ca d liu D) T s : Ch s lin quan (irrelevance index) dng o lng s lin quan gia 2 bin A v B. Nu irrelevance index =1, c ngha A v B khng lin quan nhau. P(h|D) :Xc sut c iu kin h khi bit D (gi l posterior probability ca gi thuyt h)</p> <p>1. Gii thiu Bayes Theorem Trong rt nhiu ng dng, cc gi thuyt hi c th loi tr nhau v v d liu quan st D l tp con ca tp gi thuyt cho nn chng ta c th phn r P(D) nh sau (CT2): V nn (CT1) c th vit li nh sau (CT3) Thay P(D) trong (CT2) vo (CT1) ta c (CT4)</p> <p>1. Gii thiu Bayes Theorem (CT4) gi l Bayess Theorem</p> <p>V d sau y m t cch tnh Bayess Theorem Gi s ta c d liu quan st v 250 i tng tm hiu mi quan h gia 2 bin thu nhp (income: Low(D1), Medium(D2), High(D3)) v loi xe hi (Car: Second hand (h1), New (h2)) m h mua.</p> <p>V d sau y m t cch tnh Bayess Theorem By gi gi s rng ta ch bit phn trm theo dng (Percentage by Row) v phn trm theo cc bin (Marginal Percentage hay Percentage by Total) nh sau.</p> <p>Cu hi t ra l c th tnh phn trm theo ct (percentage by column) ch da vo thng tin t 2 bng trn hay khng?.</p> <p>V d sau y m t cch tnh Bayess Theorem</p> <p>V d sau y m t cch tnh Bayess Theorem Bng phn trm theo ct (Percentage by Column) c biu din nh sau:</p> <p> S dng Bayes Rule chng ta c th d dng tnh cc phn trm theo ct. Chn hn</p> <p>V d sau y m t cch tnh Bayess Theorem Tng t nh trn, ta tnh c tt c cc gi tr trong bng phn trm theo ct nh sau:</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier) Cc v d sau y minh ha vic s dng Bayes Theorem trong vic phn lp d liu. B phn lp d liu da trn Bayes theorem cn gi l Nave Bayes Classifier. V d 1: C training data v thi tit nh sau</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier) S dng Nave Bayes Classifier xc nh kh nng n chi th thao (Play = yes hay no) vi thi tit ca ngy quan st c nh sau:</p> <p>T Training data ta c d liu nh sau:</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier) V thuc tnh phn lp Play ch c 2 gi tr l yes (ngha l c n chi th thao) v no(khng n chi th thao) nn ta phi tnh Pr(yes|E) v Pr(no|E) nh sau. Trong E l d liu cn phn lp (d on)</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier)</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier)</p> <p> V P(no) &gt; P(yes) nn kt qu d on Play =no</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier) V d 2: C Training Data v Unseen data nh sau</p> <p>2. ng dng Bayes Theorem trong phn lp d liu (Nave Bayes Classifier) S dng Nave Bayes Classifier phn lp cho Unseen data (X) Class: C1:buys_computer =yes, C2:buys_computer =no Tnh P(X|Ci) cho mi class X=(age d(C, c2 ) = 0.22 C thuc cm 2 d(D, c1 ) = 25 &gt; d(D, c2 ) = 3.56 D thuc cm 267K-Mean v ng dung</p> <p>II.3 V D MINH HABc 4-2: Lp li bc 3-Cp nht trng tm c1 = (3/2, 1) v c2 = (9/2, 7/2)K-Mean v ng dung</p> <p>68</p> <p>II.3 V D MINH HABc 4-3: Lp li bc 2 d(A, c1 ) = 0.25 &lt; d(A, c2 ) = 18.5 A thuc cm 1 d(B, c1 ) = 0.25 &lt; d(B, c2 ) = 12.5 B thuc cm 1 d(C, c1 ) = 10.25 &lt; d(C, c2 ) = 0.5 C thuc cm 2 d(D, c1 ) = 21.25 &gt; d(D, c2 ) = 0.5 D thuc cm 269K-Mean v ng dung</p> <p>II.3 V D MINH HAK-Mean v ng dung</p> <p>70</p> <p>Bi tp C 1 mu khong sn c d on c vng, bc v ng, ta chia lm 5 im ta xt phn vng cc kim loi: Point A B C D E X 1 3 4 3 2 Y 2 1 2 3 1</p> <p>II.4 NH GI THUT TON U IM1. phc tp: O( K .N .l ) vi l: s ln lp 2. C kh nng m rng, c th d dng sa i vi nhng d liu mi. 3. Bo m hi t sau 1 s bc lp hu hn. 4. Lun c K cm d liu 5. Lun c t nht 1 im d liu trong 1 cm d liu. 6. Cc cm khng phn cp v khng b chng cho d liu ln nhau. 7. Mi thnh vin ca 1 cm l gn vi chnh cm hn bt c 1 cm no khc.K-Mean v ng dung</p> <p>72</p> <p>II.4 NH GI THUT TON NHC IM1. Khng c kh nng tm ra cc cm khng li hoc cc cm c hnh dng phc tp. 2. Kh khn trong vic xc nh cc trng tm cm ban u - Chn ngu nhin cc trung tm cm lc khi to - hi t ca thut ton ph thuc vo vic khi to cc vector trung tm cm 1. Kh chn ra c s lng cm ti u ngay t u, m phi qua nhiu ln th tm ra c s lng cm ti u. 2. Rt nhy cm vi nhiu v cc phn t ngoi lai trong d liu. 3. Khng phi lc no mi i tng cng ch thuc v 1 cm, ch ph hp vi ng bin gia cc cm r. 73</p> <p>K-Mean v ng dung</p> <p>II.5 TNG QUT HA V CC BIN THB. Cc bin th 1. Thut ton K-medoid:K-Mean v ng dung</p> <p>Tng t thut ton K-mean Mi cm c i din bi mt trong cc i tng ca cm. Chn i tng gn tm cm nht lm i din cho cm . K-medoid khc phc c nhiu, nhng phc tp ln hn.</p> <p>74</p> <p>II.5 TNG QUT HA V CC BIN TH2.</p> <p>Thut ton Fuzzy c-mean (FCM): Chung chin lc phn cm vi K-mean. Nu K-mean l phn cm d liu cng (1 im d liu ch thuc v 1 cm) th FCM l phn cm d liu m (1 im d liu c th thuc v nhiu hn 1 cm vi 1 xc sut nht nh). Thm yu t quan h gia cc phn t v cc cm d liu thng qua cc trng s trong ma trn biu bin bc ca cc thnh vin vi 1 cm.K-Mean v ng dung</p> <p> FCM khc phc c cc cm d liu chng nhau trn cc tp d liu c kch thc ln hn, nhiu chiu v nhiu nhiu, song vn nhy cm vi nhiu v cc phn 75 t ngoi lai.</p> <p>III. NG DNG CA THUT TON Phn cm ti liu web. 1. Tm kim v trch rt ti liu 2. Tin x l ti liu: Qu trnh tch t v vecto ha ti liu: tm kim v thay th cc t bi ch s ca t trong t in.Biu din d liu di dng vect. 3. p dng K-Mean Kt qu tr v l cc cm ti liu v cc trng tm tng ng. Phn vng nhK-Mean v ng dung</p> <p>76</p> <p>TI LIU THAM KHO Ti liu chnh: [WKQ08] Xindong Wu, Vipin Kumar, J. Ross Quinlan, Joydeep Ghosh, Qiang Yang, Hiroshi Motoda, Geoffrey J. McLachlan, Angus Ng, Bing Liu, Philip S. Yu , Zhi-Hua Zhou, Michael Steinbach, David J. Hand, Dan Steinberg (2008). Top 10 algorithms in data mining, Knowl Inf Syst (2008) 14:137 Pavel Berkhin (). Survey of Clustering Data Mining Techniques http://en.wikipedia.org/wiki/K-means_clustering http://en.wikipedia.org/wiki/Segmentation_(image_processing) Slide KI2 7 Clustering Algorithms - Johan Everts http://vi.wikipedia.org/wiki/Hc_khng_c_gim_st http://people.revoledu.com/kardi/tutorial/kMean/NumericalExample.htm</p> <p>77</p> <p>K-Mean v ng dung</p> <p>Chng 3: Phn loi theo khong cch Trong k thut ny, cc i tng nhn dng l cc i tng nh lng. Mi i tng c biu din bi mt vct nhiu chiu. Trc tin, ta xem xt mt s khi nim nh: phn hoch khng gian, hm phn bit sau s i vo mt s k thut c th.</p> <p>Phn hoch khng gian Gi s khng gian i tng X c nh ngha : X = {Xi, i=1, 2,...,m}, Xi l mt vct. Ngi ta ni P l mt phn hoch ca khng gian X thnh cc lp Ci, Ci X nu: Ci Cj = vi i j v Ci = X Ni chung, y l trng hp l tng: tp X tch c hon ton. Trong thc t, thng gp khng gian biu din tch c tng phn. Nh vy phn loi l da vo vic xy dng mt nh x f: X ---&gt; P. Cng c xy dng nh x ny l cc hm phn bit (Descriminant functions).</p> <p>Hm phn lp hay hm ra quyt nh phn i tng vo cc lp, ta phi xc nh s lp v ranh gii gia cc lp . Hm phn lp hay hm phn bit l mt cng c rt quan trng. Gi {gi} l lp cc hm phn lp. Lp hm ny c nh ngha nh sau: nu i k, gk(X) &gt; gi(X) th ta quyt nh X lp k. Nh vy phn bit k lp, ta cn k-1 hm phn bit. Hm phn bit g ca mt lp no thng dng l hm tuyn tnh, c ngha l: g(X) = W0 + W1X1 + W2X2+. . . +Wk Xk trong : - Wi l cc trng s gn cho cc thnh phn Xi. W0 l trng s vit cho gn. Trong trng hp g l tuyn tnh, ngi ta ni l vic phn lp l tuyn tnh hay siu phng (hyperplan).</p> <p>Hm phn lp hay hm ra quyt nh Cc hm phn bit thng c xy dng da trn khi nim khong cch hay da vo xc sut c iu kin. Khong cch l mt cng c rt tt xc nh xem i tng c "gn nhau" hay khng. Nu khong cch nh hn mt ngng no y ta coi 2 i tng l ging nhau v gp chng vo mt lp. Ngc li , nu khong cch ln hn ngng , c ngha l chng khc nhau v ta tch thnh 2 lp.</p> <p>Hm phn lp hay hm ra quyt nh Trong mt s trng hp, ngi ta da vo xc sut c iu kin phn lp cho i tng. L thuyt xc sut c iu kin c Bayes nghin cu kh k v chng ta c th p dng l thuyt ny phn bit i tng. Gi : P(X/Ci) l xc sut c X bit rng c xut hin lp Ci P(Ci /X) l xc sut c iu kin X thuc lp Ci. vi X l i tng nhn dng, Ci l cc lp i tng. Qu trnh hc cho php ta xc nh P(X/Ci) v nh cng thc Bayes v sc xut c iu kin p dng trong iu kin nhiu bin, chng ta s tnh c P(Ci/X) theo cng thc: P(Ci /X) =P ( X / Ci ) P ( Ci ) P ( X / Ci ) P (Ci ) = n P( X ) P ( C / Xi ) P ( C i ) i =1</p> <p> Nu P(Ci/X) &gt; P(Ck /X) vi i # k th X Ci. Tu theo cc phng php nhn dng khc nhau, hm phn bit s c cc dng khc nhau.</p> <p>Mt s thut ton nhn dng tiu biu trong t hc Thc t c nhiu thut ton nhn dng hc khng c thy. y, chng ta xem xt 3 thut ton hay c s dng: Thut ton nhn dng da vo khong cch ln nht thut ton K- trung bnh (K mean) thut ton ISODATA</p> <p>Thut ton da vo khong cch ln nhta) Nguyn tc Cho mt tp gm m i tng. Xc nh khong cch gia cc i tng v khong cch ln nht ng vi phn t xa nht to nn lp mi. S phn lp c hnh thnh dn dn da vo vic xc...</p>