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

pdf43 trang | Chia sẻ: trungkhoi17 | Lượt xem: 446 | Lượt tải: 0download
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:

  • pdfbai_giang_phan_loai_bang_bayes_ban_hay.pdf
Tài liệu liên quan