BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - NGUYỄN THỊ HẠNH MỘT SỐ THỦ TỤC PHÂN LOẠI DỰA THEO CÁCH TIẾP CẬN THỐNG KÊ LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: TOÁN TIN Hà Nội - 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - - - - - - - - - - -o0o- - - - - - - - - - - NGUYỄN THỊ HẠNH MỘT SỐ THỦ TỤC PHÂN LOẠI DỰA THEO CÁCH TIẾP CẬN THỐNG KÊ Chuyên ngành: Toán Tin LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH: TOÁN TIN NGƯỜI HƯỚNG DẪN KHOA HỌC TS NGUYỄN HỮU TIẾN Hà Nội - 2014 Mục lục Lời mở đầu iii Danh mục kí hiệu chữ viết tắt vi Danh mục hình vẽ vii Tổng quan chung nhận dạng 1.1 Tầm quan trọng nhận dạng mẫu 1.2 Các đặc trưng, véc tơ đặc trưng lớp 1.3 Nhận dạng có hướng dẫn nhận dạng khơng có hướng dẫn Các thủ tục phân loại dựa nguyên lý định Bayes 2.1 Giới thiệu 2.2 Nguyên lý định Bayes 2.2.1 Tối thiểu hóa xác suất lỗi phân loại 11 2.2.2 Tối thiểu hóa rủi ro trung bình 13 2.3 Các phương trình phân biệt mặt định 16 2.4 Phân loại Bayes cho phân phối chuẩn 17 i Luận văn cao học 2.4.1 2.5 2.6 Nguyễn Thị Hạnh Phân loại khoảng cách tối thiểu 22 Ước lượng hàm mật độ xác suất chưa biết 25 2.5.1 Ước lượng tham số hợp lý cực đại 26 2.5.2 Ước lượng xác suất hậu tố cực đại 30 2.5.3 Suy luận Bayes 31 2.5.4 Ước lượng với thông tin tối đa 32 2.5.5 Mơ hình trộn 34 2.5.6 Ước lượng phi tham số 39 Quy tắc người láng giềng gần 44 Phân loại tuyến tính 3.1 48 Giới thiệu Tài liệu tham khảo 48 51 ii Luận văn cao học Nguyễn Thị Hạnh Lời mở đầu Lý thuyết nhận dạng ngành khoa học với mục đích nghiên cứu thuật tốn có khả phân loại cá thể đám đông vào lớp hay cụm khác nhau, tùy theo giả thiết biết hay chưa biết số lớp đám đông Theo ý nghĩa này, nghiên cứu lý thuyết nhận dạng tập trung vào hai hướng sau: • Các nghiên cứu thuật toán nhận dạng giả thiết số lớp đám đông cho trước gọi chung thuật tốn phân loại • Các nghiên cứu thuật tốn nhận dạng khơng có thông tin số lớp đám đơng gọi thuật tốn phân cụm Trong luận văn tìm hiểu số thuật toán phân loại dựa cách tiếp cận thống kê tốn học luận văn trình bày ba chương sau: • Chương tổng quan chung nhận dạng Chương gồm ba phần Trong đó, phần đầu giới thiệu chung tầm quan trọng nhận dạng mẫu Phần thứ hai trình bày khái niệm đặc trưng, vec tơ đặc trưng lớp Phần cuối khái niệm nhận dạng có hướng dẫn nhận dạng khơng có hướng dẫn Chương tảng cho chương sau với tài liệu tham khảo [3] iii Luận văn cao học Nguyễn Thị Hạnh • Chương tập trung vào thuật toán phân loại dựa nguyên lý định Bayes gọi thuật toán phân loại Bayes Các thuật toán xây dựng sở cho trước hàm mật độ phân phối xác suất lớp dạng Tuy nhiên thực tế hàm mật độ chưa biết Vì phương pháp ước lượng tham số phi tham số cho hàm mật độ phân phối xác suất xác định Đặc biệt khảo sát nhằm khẳng định vai trị thuật tốn phân loại Bayes thuật tốn phân loại cực tiểu hóa tổn thất trung bình hay thuật tốn phân loại cực tiểu hóa khoảng cách trình bày.Tài liệu tham khảo cho chương [3] • Chương tập trung vào phân loại tuyến tính Trong số trường hợp, lớp phân biệt tuyến tính nghĩa chúng tồn hàm phân biệt tuyến tính Việc phân loại tương đương với việc tìm hàm phân biệt tuyến tính cho xác suất lỗi phân loại nhỏ nhất.Thuật toán Perceptron giúp giải vấn đề Hơn nữa, biết lớp phân biệt tuyến tính việc tính tốn đơn giản Vì thế, nhiều trường hợp lớp khơng phân biệt tuyến tính muốn đưa phân lớp tuyến tính Các phương pháp bình phương tính tốn trọng số theo chuẩn tối ưu phù hợp để xác suất lỗi phân loại chấp nhận Qua đây, em xin gửi lời cảm ơn sâu sắc đến người hướng dẫn khoa học mình, TS Nguyễn Hữu Tiến, người đưa để tài tận tình iv Luận văn cao học Nguyễn Thị Hạnh hướng dẫn suốt trình nghiên cứu em Em xin chân thành cảm ơn thầy phản biện đọc có bảo, nhận xét quý báu Đồng thời em chân thành cảm ơn thầy cô viện Toán ứng dụng Tin học trường Đại học Bách khoa Hà Nội, tạo điều kiện thuận lợi để em hồn thành tốt chương trình học cao học Trường hoàn thành luận văn Hà Nội, tháng năm 2014 Học viên Nguyễn Thị Hạnh v Luận văn cao học Nguyễn Thị Hạnh Danh mục kí hiệu chữ viết tắt C tập số phức R tập số thực Z tập số nguyên x chuẩn x B đại số Borel λ độ đo Lebesgue R χA hàm đặc trưng tập A Rn không gian Euclid n chiều Lp (R) khơng gian hàm khả tích bậc p R L∞ (R) khơng gian hàm khả tích vô hạn R L1,loc (R) không gian hàm giá trị thực khả tích địa phương R a.e hầu khắp nơi (viết tắt cụm từ "almost everywhere") vi Luận văn cao học Nguyễn Thị Hạnh Danh mục hình vẽ Hình 2.1 Ví dụ trường hợp hai miền vii Chương Tổng quan chung nhận dạng 1.1 Tầm quan trọng nhận dạng mẫu Nhận dạng mơn khoa học mà mục tiêu phân loại đối tượng vào số lớp Tùy thuộc vào ứng dụng cụ thể đối tượng hình ảnh, hay tín hiệu dạng sóng dạng biểu diễn số Nhận dạng mẫu có lịch sử lâu đời trước năm 1960 nghiên cứu lý thuyết nhận dạng chưa quan tâm đầy đủ nhà khoa học Giống ngành khoa học khác, xuất máy tính làm tăng nhu cầu ứng dụng thực tế nhận dạng mẫu điều đặt vấn đề thúc đẩy xuất lý thuyết nhận dạng Giống phát triển xã hội từ thời công nghiệp tới thời hậu công nghiệp, tự động hóa sản xuất cơng nghiệp cần thiết cho việc cập nhật , trao đổi thông tin ngày trở nên quan trọng Ngày nay, xu hướng đưa nhận dạng mẫu đạt tới đỉnh cao ứng dụng vào việc nhận biết, tìm kiếm phân Luận văn cao học Nguyễn Thị Hạnh Để bước lặp hồn thành ta tính P (j/xk ; Θ (t)) Ta có P (j/xk ; Θ (t)) = p (xk /j; Θ (t)) Pj (t) p (xk ; θ (t)) (2.87) p (xk /j; θ (t)).Pj (t) (2.88) Công thức xác suất đầy đủ J p (xk ; θ (t)) = j=1 Các phương trình từ (2.84) -(2.88) tạo thuật toán EM cho ước lượng tham số chưa biết hỗn hợp Gauss (2.72) 2.5.6 Ước lượng phi tham số Chúng ta mơ hình tham số hàm mật độ xác suất theo nhiều cách khác liên quan đến tham số chưa biết ước lượng Trong tiểu mục làm việc với kỹ thuật phi tham số Đó biến biểu đồ xấp xỉ hàm mật độ xác suất chưa biết Ví dụ đơn giản trường hợp chiều Hình 2.8 Hình 2.8 hai ví dụ hàm mật độ xác suất xấp xỉ phương pháp biểu đồ Trục x (trường hợp chiều) chia thành cột chữ nhật với chiều dài h Khi xác suất mẫu x xác định cột ước lượng cho cột Nếu N tổng số mẫu, kN số trường hợp xác định cột chữ nhật, xác suất tương ứng xấp xỉ tỷ lệ tần số p= 39 kN N (2.89) Luận văn cao học Nguyễn Thị Hạnh Xấp xỉ hội tụ tới P N → ∞ Giá trị hàm mật độ xác suất tương ứng giả thiết số cột chữ nhật xấp xỉ pˆ (x) ≡ pˆ (ˆ x) = kN , hN |x − xˆ| ≤ h (2.90) Trong xˆ điểm cột chữ nhật Nó xác định biên độ đường biểu đồ cột chữ nhật Đây xấp xỉ hợp lý cho p(x) liên tục h đủ nhỏ, giả thiết p(x) số cột chữ nhật hợp lý Có thể thấy pˆ (x) hội tụ tới giá trị p(x) Khi N → ∞: • hN → • kN → ∞ • kN N →0 Trong hN phụ thuộc vào N Thấy kN phải đủ lớn để đảm bảo hội tụ Thật vậy, tất điểm đặt cỡ hN nhỏ tùy ý, xác suất p tất điểm cột chữ nhật hữu hạn Vì vậy, kN p.N kN tiến tới vô cúng N tiến vô Mặt khác, kích thước hN tiến tới 0, xác suất tương ứng tiến tới 0, chứng minh điều kiện cuối Mở rộng Parzen: 40 Luận văn cao học Nguyễn Thị Hạnh Trong trường hợp nhiều chiều, thay khoảng có độ dài h, khơng gian l chiều chia thành siêu khối với chiều dài h thể tích hl Cho xi , i = 1, 2, , N vec tơ đặc trưng cho trước Định nghĩa hàm φ (x) sau:   |xij | ≤ φ (xi ) =  |x | > ij 2 (2.91) Trong xij , j = 1, 2, , N thành phần xi Theo đó, hàm φ (x) cho tất điểm bên siêu khối ngược lại Khi (2.90) viết lại sau pˆ (x) = l h N N φ i=1 xi − x h (2.92) Điều giải thích sau Chúng ta xem siêu khối với độ dài h x, điểm mà hàm mật độ xác suất ước lượng Giả thiết kN điểm rơi vào bên siêu khối Khi ước lượng hàm mật độ xác suất kN /N , với thể tích siêu khối tương ứng hl Tuy nhiên xem phương trình (2.92) từ khía cạnh khác, ta thấy xấp xỉ hàm p(x) liên tục thông qua thuật ngữ mở rộng hàm không liên tục φ (.) Vì kết ước lượng bị sai từ lỗi Điều đưa Parzen khái quát việc sử dụng hàm mịn φ (.) Nó xác định sau: φ (x) ≥ (2.93) φ (x) dx = (2.94) x 41 Luận văn cao học Nguyễn Thị Hạnh Kết ước lượng hàm mật độ xác suất thống Các hàm mịn gọi hàm nhân hay gọi hàm hay hàm mở rộng Parzen Ví dụ loại hàm mũ, hàm Gauss N(0,1) Phần đưa ví dụ giới hạn việc xấp xỉ Cuối giá trị trung bình (2.92) E (ˆ p (x)) = l h N N E φ i=1 xi − x h x −x φ p (x ) dx hl h = (2.95) x Giá trị trung bình phiên mịn hàm mật độ xác suất p(x) Tuy nhiên h → hàm φ hl x −x h tiến tới hàm delta δ (x − x) Thật vậy, biên độ tiến tới khơng xác định, độ rộng tiến tới tích phân từ (2.94) Vì vậy, pˆ (x) ước lượng khơng chệch p(x) Điều độc lập với cỡ N tập liệu Ứng dụng vào phân lớp: Dựa tiếp nhận vec tơ đặc trưng x, hàm hợp lý kiểm tra (2.19) trở thành Gán x vào w1 (w2 )   l12  N1 hl  ≈  N2 hl N1 φ i=1 N2 φ i=1 xi −x h xi −x h  P (w2 ) λ21 − λ22   > ( ( (