Toán học - Phân loại bằng Bayes

Giới thiệu

◦ Bài tóan

◦ Hướng tiếp cận Bayes

 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

 Xây dựng hệ phân lớp

pdf43 trang | Chia sẻ: Mr Hưng | Ngày: 02/09/2016 | Lượt xem: 107 | Lượt tải: 0download
Bạn đang xem trước 20 trang nội dung tài liệu Toán học - Phân loại bằng Bayes, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Phân loại bằng Bayes Lê Phong Dàn bài  Giới thiệu ◦ Bài tóan ◦ Hướng tiếp cận Bayes  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  Xây dựng hệ phân lớp Giới thiệu  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 w1, w2,, wc.  Lý thuyết ra quyết định Bayes là nền tảng cho các phương pháp phân lớp thống kê. w1 w2 wc x ? ? ? ? Giới thiệu (tt)  Giả sử đã biết trước xác suất tiền định P(w = wi) i = 1..c  Gọi p(x|wi) là mật độ xác suất của đặc trưng x trong lớp wi.  Khi đó, xác suất hậu định để đối tượng có đặc trưng x thuộc lớp wi là ◦ Trong đó  Để ngắn gọn, viết Giới thiệu (tt) w1 w2 wc x P(w1|x) P(w2|x) P(wi|x) P(wc|x) P(w1) P(w2) P(wi) P(wc) p(x|wi), i=1..c  Dựa trên P(wi|x) để quyết định đối tượng x thuộc lớp nào. Dàn bài  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  Một số vấn đề mở rộng  Xây dựng hệ phân lớp Lý thuyết ra quyết định Bayes  Về mặt cảm quan, chọn lớp wbest sao cho P(wbest|x) = min P(wi|x) i=1..c  Xem xét 2 trường hợp ◦ Trường hợp đơn giản 2 lớp ◦ Trường hợp tổng quát Trường hợp đơn giản  Có 2 lớp w1 và w2 Trường hợp đơn giản (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 tương ứng làm cực tiểu hóa trung bình xác suất lỗi Trường hợp tổng quát  Mở rộng giả thiết với 1. Số lớp là bất kỳ. 2. a hành động α1, α2,, αa (ví dụ như hành động αi là phân x vào lớp wi). 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 αi trong trường hợp đối tượng thuộc lớp wj (ví dụ như là chi phí khi phân loại sai). Trường hợp tổng quát (tt)  Xác suất lỗi được tổng quát hóa bằng rủi ro có điều kiện Thể hiện cái giá phải trả cho hành động αi khi đối tượng 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. Trường hợp tổng quát (tt)  Luật 2 đạt được cực tiểu cho R* - còn được gọi là rủi ro Bayes. Hàm tiêu tốn đối xứng  Trường hợp đặc biệt: αi là hành động phân đối tượng x vào lớp wi với hàm tiêu tốn  Ý nghĩa: không trả giá nếu phân loại đúng, ngược lại trả giá là 1.  Hàm rủi ro có điều kiện Ví dụ  2 lớp P(w1)=2/3, P(w2)=1/3  3 hành động ◦ α1 = “xếp đối tượng vào lớp w1” ◦ α2 = “xếp đối tượng vào lớp w2” ◦ α3 = “không phân lớp”  Hàm tiêu tốn λ Ví dụ (tt)  Tính Ví dụ (tt) α1 α3 α2 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ớp Biệ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 có đặc trưng x, hệ phân lớp sẽ phân x và lớp wi nếu Biệt hàm (tt)  Một số trường hợp ◦ Tính chi phí bằng xác suất lỗi trung bình ◦ Tính chi phí bằng rủi ro toàn cục hoặc Vùng ra quyết định  Phân hoạch không gian đặc trưng ra c phần không giao nhau R1,, Rc với x thuộc Ri nếu x được phân vào lớp wi  Ri được gọi là vùng ra quyết định (decision region)  Biên bao quanh các Ri được gọi là biên ra quyết định (decision boundary) Vùng ra quyết định (tt) Biệt hàm cho phân phối chuẩn  Xây dựng hệ phân lớp với tiêu chí cực tiểu hóa trung bình xác suất lỗi  Sử dụng biệt hàm  Giả thiết do đó Trường hợp 1:  Ở mọi lớp: các đặc trưng thành phần độc lập với nhau và có cùng phương sai  Biên ra quyết định có được nhờ giải phương trình  Suy ra biên ◦ Trong đó 2 i σ=Σ I 2σ ( ) ( )i jg g=x x 0( ) 0T − =w x x i j= −w µ µ 2 0 2 ( )1 ( ) ln ( ) 2 ( ) i i j i j ji j P P ωσ ω = + − − − x µ µ µ µ µ µ Trường hợp 1:  Nếu P(wi) = P(wj) 2 i σ=Σ I Trường hợp 1:  Nếu P(wi) ≠ P(wj) 2 i σ=Σ I Trường hợp 2:  Hiệp phương sai ở mọi lớp đều như nhau và bất kỳ  Biên ra quyết định ◦ Trong đó i =Σ Σ 0( ) 0T − =w x x 1( )i j−= −w Σ µ µ 0 1 ( )1 1( ) ln ( ) 2 ( ) ( ) ( ) i i j i jT i j i j j P P ω ω− = + − − − − x µ µ µ µ µ µ Σ µ µ Trường hợp 2: i =Σ Σ Trường hợp 3: bất kỳ  Đầy là trườ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  Biên ra quyết định có thể là hyperquadaric (hyperplane, cặp hyperplane, hypersphare,) iΣ 1 1 1 0 1 1( ) 2 ln ln ( ) 2 2 T T T i i i i i i i i i T T i i i g P w ω− − − = − − + − +  = + + x x Σ x µ Σ x µ Σ µ Σ x Wx w x Trường hợp 3: bất kỳiΣ Trường hợp 3: bất kỳiΣ Trường hợp 3: bất kỳiΣ Ví dụ:  2 lớp w1, w2 với P(w1) = P(w2) = 0.5 2 1 2 2 1 1( ) (0,3) exp . 2 32 3 1 1( ) (2,1) exp ( 2) 22 xp x N p x N x ω pi ω pi   = = −      = = − −    Ví dụ (tt)  Biệt hàm  Vùng ra quyết định R1 thỏa g1(x) > g2(x) 2 1 1 2 2 2 1 1( ) ln 3 ln ( ) 6 2 1( ) 2 2 ln ( ) 2 g x x P g x x x P ω ω = − − + = − + − + ( ) ( ) 2 2 1 2 2 1 2 1 1 1ln3 ln ( ) 2 2 ln ( ) 6 2 2 2 12 12 3ln 3 6ln ( ) 6 ln ( ) 0 ,0.84 5.16, x P x x P x x P P x ω ω ω ω − − + > − + − + ⇔ − + − + − > ⇔ ∈ −∞ ∪ ∞ Ví dụ (tt) 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  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 Đặc trưng rời rạc  x chỉ nhận 1 trong m giá trị v1,, vm ∈ ℜd  Thay p(x|w) bằng P(x|w) Đặc trưng bị thiếu và biến dạng bởi nhiễu  Khi đã xây dựng xong hệ phân lớp.  Với 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  Cần phải khắc phục những khiếm khuyết đó  (tự tìm hiểu trong Phân lớp Bayes.pdf) 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  Một số vấn đề mở rộng  Xây dựng hệ phân lớp ◦ Huấn luyện và kiểm tra ◦ Independent Test Sample ◦ Cross-validation Xây dựng hệ phân lớp  Tập dữ liệu D = {x1, x2, , xn}  2 bước 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 lớp ◦ B2: Kiểm tra ‘độ tốt’ của hệ phân lớp tìm được  Cần chia D ra làm 2 tập ◦ Dtrain cho bước 1 ◦ Dtest cho bước 2 Bước 1: huấn luyện P(wi) i=1..c cost Bước 2: kiểm tra cost test c i cc i D n∑ =1 )( Independent Test Sample  Được ứng dụng khi tập mẫu lớn - Lấy ngẫu nhiên ntrain đối tượng ở D cho vào Dtrain, phần còn lại ntest đối tượng cho vào Dtest. - Dùng Dtrain để huấn luyện - Dùng Dtest để kiểm tra - Xác định tỉ lệ phân loại đúng test c i cc i D n CCP ∑ = = 1 )( )( Cross-validation  Được ứng dụng khi tập mẫu nhỏ - Chia tập mẫu thành k phần bằng nhau D1,, Dk - Ncc := 0 - For i từ 1  k Dtrain = D\Di; Dtest = Di Dùng Dtrain để huấn luyện Dùng Dtest để kiểm tra Ncc := Ncc + - End for ∑ = c i cc in 1 )( D NCCP cc=)(

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

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