Bài giảng Phân loại bằng Bayes (Bản hay)

Dàn bài

Giới thiệu

Lý thuyết ra quyết định Bayes

Phân lớp bằng biệt hàm

◦ Biệt hàm, vùng ra quyết định

◦ Biệt hàm cho phân phối chuẩn

Một số vấn đề mở rộng

Xây dựng hệ phân lớpBiệt hàm

Mỗi lớp wi có một biệt hàm (discriminant function)

gi(x). Với mỗi đối tượng

43 trang | Chia sẻ: trungkhoi17 | Lượt xem: 484 | Lượt tải: 0

Bạn đang xem trước 20 trang tài liệu Bài giảng Phân loại bằng Bayes (Bản hay), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

PhânPhân lolo ii bb ngng BayesBayes Lê Phong DDàànn bb ààii Gi ới thi ệu ◦ Bài tóan ◦ Hng ti p c n Bayes Lý thuy t ra quy t nh Bayes Phân l p b ng bi t hàm Mt s vn m rng Xây d ng h phân l p GiGi ii thithi uu Bài toán phân lo i (Pattern Classification) Xác nh i t ng cóc tr ng x thu c l p nào trong c l p w 1, w 2,, w c. x ? ? ? ? w1 w2 wc Lý thuy t ra quy t nh Bayes là nn t ng cho các ph ơ ng pháp phân l p th ng kê. GiGi ii thithi uu (tt)(tt) Gi st tr c xác su t ti n nh P(w = w i) i = 1..c Gi p( x|w i) là mt xác su t c a c tr ng x trong lp w i. Khi ó, xác su t h u nh i t ng cóc tr ng x thu c l p w i là ◦ Trong ó ng n g n, vi t GiGi ii thithi uu (tt)(tt) p(x|w i), i=1..c x P(w |x) 1 P(w 2|x) P(w i|x) P(w c|x) w1 w2 wc P(w ) P(w ) 1 P(w 2) P(w i) c Da trên P(w i|x) quy t nh i t ng x thu c lp nào. DDàànn bb ààii Gi i thi u Lý thuy ết ra quy ết định Bayes ◦ Tr ng h p ơ n gi n – 2 l p ◦ Tr ng h p t ng quát ◦ Ví d Phân l p b ng bi t hàm Mt s vn m rng Xây d ng h phân l p LýLý thuythuy tt rara quyquy tt nhnh BayesBayes V mt c m quan, ch n l p w best sao cho P(w best |x) = min P(w i|x) i=1..c Xem xét 2 ng h p ◦ Tr ng h p ơ n gi n 2 l p ◦ Tr ng h p t ng quát TrTr ngng hh pp ơơ nn gigi nn Có 2 l p w 1 và w2 TrTr ngng hh pp ơơ nn gigi nn (tt)(tt) Trung bình xác su t l i (average probability of error) ◦ Trong ó là xác su t l i khi a ra quy t nh Lu t 1 ơng làm c c ti u hóa trung bình xác su t l i TrTr ngng hh pp tt ngng ququ áátt M rng gi thi t v i 1. S lp là bt k . 2. a hành ng 1, 2,, a (ví d ành ng i là phân x vào l p w i). 3. Hàm tiêu t n λ(i|wj) th hi n cái giá ph i tr khi th c hi n hành ng ing h p i t ng thu c l p w j (ví d à chi phí khi phân lo i sai). TrTr ngng hh pp tt ngng ququ áátt (tt)(tt) Xác su t l i c t ng quát hóa b ng r i ro cóu ki n Th hi n cái giá ph i tr cho hành ng ii tng cóc tr ng x Xác su t l i trung bình c t ng quát hóa b ng r i ro toàn b ◦ Trong ó (x) nh n các hành ng i i=1..a) tơ ng ng v i c tr ng x tìm (x) t c c ti u R. TrTr ngng hh pp tt ngng ququ áátt (tt)(tt) Lu t 2 t c c c ti u cho R* -c g i là ri ro Bayes. HHààmm tiêutiêu tt nn ii xx ngng Tr ng h p c bi t: i là hành ng phân i tng x vào l p w i vi hàm tiêu t n Ý ngh a: không tr giá nu phân lo i úng, ngc li tr giá là 1. Hàm r i ro cóu ki n VVíí dd 2 l p P(w 1)=2/3, P(w 2)=1/3 3 hành ng ◦ 1 = “xp i t ng vào l p w 1” ◦ 2 = “xp i t ng vào l p w 2” ◦ 3 = “không phân l p” Hàm tiêu t n λ VVíí dd (tt)(tt) Tính VVíí dd (tt)(tt) 1 3 2 DDàànn bb ààii Gi i thi u Lý thuy t ra quy t nh Bayes Phân l ớp b ằng bi ệt hàm ◦ Bi t hàm, vùng ra quy t nh ◦ Bi t hàm cho phân ph i chu n Mt s vn m rng Xây d ng h phân l p BiBi tt hh ààmm Mi l p w i có mt bi t hàm (discriminant function) gi(x). V i m i i t ng cóc tr ng x, h phân l p s phân x và lp w i nu BiBi tt hh ààmm (tt)(tt) Mt s ng h p ◦ Tính chi phí bng xác su t l i trung bình ho c ◦ Tính chi phí bng r i ro toàn c c VVùùngng rara quyquy tt nhnh Phân ho ch không gian c tr ng ra c ph n không giao nhau R 1,, R c vi x thu c R i nu x c phân vào l p w i Ric g i là vùng ra quy t nh (decision region) Biên bao quanh các R ic g i là biên ra quy t nh (decision boundary) VVùùngng rara quyquy tt nhnh (tt)(tt) BiBi tt hh ààmm chocho phânphân phph ii chuchu nn Xây d ng h phân l p v i tiêu chí cc ti u hóa trung bình xác su t l i S dng bi t hàm Gi thi t do ó 2 TrTr ngng hh pp 1:1: Σi = σ I mi l p: các c tr ng thành ph n c l p v i nhau và có cùng ph ơ ng sai σ 2 Biên ra quy t nh cóc nh gi i ph ơ ng trình gi()x= g j () x T Suy ra biên w( x− x 0 ) = 0 ◦ Trong ó w =µi − µ j 1 σ 2 P(ω ) x =+−(µµ ) lni ( µµ − ) 0 2i j 2 P (ω ) i j µi− µ j j 2 TrTr ngng hh pp 1:1: Σi = σ I Nu P(w i) = P(w j) 2 TrTr ngng hh pp 1:1: Σi = σ I Nu P(w i) P(w j) TrTr ngng hh pp 2:2: Σi = Σ Hi p ph ơ ng sai mi l p u nh nhau và bt k Biên ra quy t nh T w( x− x 0 ) = 0 ◦ Trong ó −1 w =Σ( µi − µ j ) 1 1 P(ω ) =+−i − x0 (µµi j )T −1 ln ( µµi j ) 2 (µij− µ )( Σµ ij − µ )()P ω j TrTr ngng hh pp 2:2: Σi = Σ TrTr ngng hh pp 3:3: Σ i bb tt kk y làng h p t ng quát nh t: các ma tr n hi p ph ơ ng sai không nh t thi t b ng nhau. Bi t hàm là hàm b c 2 1T−1 T − 1 T − 1  1 gi(x )=− x Σ ix − 2µ iiiii Σ x +µΣµ  − ln Σ i + lnP (ω i ) 2 2 T T =xWxi + w i x + w i 0 Biên ra quy t nh có th là hyperquadaric (hyperplane, c p hyperplane, hypersphare,) TrTr ngng hh pp 3:3: Σ i bb tt kk TrTr ngng hh pp 3:3: Σ i bb tt kk TrTr ngng hh pp 3:3: Σ i bb tt kk VVíí dd:: 2 l p w 1, w 2 vi P(w 1) = P(w 2) = 0.5 1 1 x2  p( xω1 )= N (0,3) = exp − .  2π 3 2 3  1 1  pxN(ω )= (2,1) = exp −− ( x 2) 2  2 2π 2  VVíí dd (tt)(tt) Bi t hàm 1 1 gx( )=− x2 − ln 3 + ln P (ω ) 1 6 2 1 1 gx()=− xx2 + 2 −+ 2ln() P ω 2 2 2 Vùng ra quy t nh R 1 th a g 1(x) > g 2(x) 1 1 1 −x2 −ln3ln() + Pω >− xxP2 +−+ 2 2ln() ω 6 21 2 2 2 ⇔−+−+2xx 12 12 3ln3 6ln P (ω1 ) − 6ln P ( ω 2 ) > 0 ⇔x ∈()() −∞,0.84 ∪ 5.16, ∞ VVíí dd (tt)(tt) DDàànn bb ààii Gi i thi u Lý thuy t ra quy t nh Bayes Phân l p b ng bi t hàm Một s ố vấn đề mở rộng ◦ c tr ng r i r c ◦ c tr ng khi m khuy t Xây d ng h phân l p cc trtr ngng rr ii rr cc d x ch nh n 1 trong m giá tr v1,, v m ∈ ℜ Thay p( x|w) b ng P( x|w) cc trtr ngng bb thithi uu vv àà bibi nn dd ngng bb ii nhinhi uu Khi ã xây d ng xong h phân l p. Vi m t c tr ng m i có khi m khuy t a vào ◦ Do thi u m t vài c tr ng thành ph n ◦ Do nhi u Cn ph i kh c ph c nh ng khi m khuy t ó (t tìm hi u trong Phân l p Bayes.pdf) DDàànn bb ààii Gi i thi u Lý thuy t ra quy t nh Bayes Phân l p b ng bi t hàm Mt s vn m rng Xây d ựng h ệ phân l ớp ◦ Hu n luy n và ki m tra ◦ Independent Test Sample ◦ Cross-validation XâyXây dd ngng hh phânphân ll pp Tp d li u D = { x1, x2, , xn} 2 bc xây d ng h phân l p ◦ B1: Hu n luy n tìm ra tham s cho mô hình phân lp ◦ B2: Ki m tra ‘ tt’ ca h phân l p tìm c Cn chia D ra làm 2 t p ◦ Dtrain c 1 ◦ Dtest c 2 BBcc 1:1: huhu nn luyluy nn P(w i) i=1..c cost BBcc 2:2: kiki mm tratra c (i) ∑ n cc i=1 Dtest cost IndependentIndependent TestTest SampleSample c ng d ng khi t p m u l n -Lấy ng ẫu nhiên n train đối t ượng ở D cho vào Dtrain , ph ần còn l ại n test đối t ượng cho vào Dtest . - Dùng D train để hu ấn luy ện - Dùng D test để ki ểm tra - Xác định t ỉ lệ phân lo ại đúng c (i) ∑ n cc P(CC ) = i=1 Dtest CrossCross --validationvalidation c ng d ng khi t p m u nh - Chia t ập m ẫu thành k ph ần b ằng nhau D 1,, D k -Ncc := 0 - For i t ừ 1 k Dtrain = D\Di; D test = D i Dùng D train để hu ấn luy ện Dùng D test để ki ểm tra c (i) Ncc := Ncc + ∑ n cc - End for i=1 N P(CC ) = cc D

Các file đính kèm theo tài liệu này:

bai_giang_phan_loai_bang_bayes_ban_hay.pdf