Một số thủ tục phân loại dựa theo cách tiếp cận thống kê.

- -NGUYỄN THỊ HẠNHMỘT SỐ THỦ TỤC PHÂN LOẠIDỰA THEO CÁCH TIẾP CẬN THỐNG KÊLUẬN VĂN THẠC SĨ KHOA HỌCCHUYÊN NGÀNH: TOÁN TINHà Nội - 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- -NGUYỄN THỊ HẠNHMỘT SỐ THỦ TỤC PHÂN LOẠIDỰA THEO CÁCH TIẾP CẬN THỐNG KÊChuyên ngành: Toán TinLUẬN VĂN THẠC SĨ KHOA HỌCNGÀNH: TOÁN TINNGƯỜI HƯỚNG DẪN KHOA HỌCTS.
- NGUYỄN HỮU TIẾNHà Nội - 2014 Mục lụcLời mở đầu iiiDanh mục các kí hiệu và chữ viết tắt viDanh mục các hình vẽ vii1 Tổng quan chung về nhận dạng 11.1 Tầm quan trọng của nhận dạng mẫu.
- 11.2 Các đặc trưng, véc tơ đặc trưng và các lớp.
- 31.3 Nhận dạng có hướng dẫn và nhận dạng không có hướngdẫn.
- 42 Các thủ tục phân loại dựa trên nguyên lý quyết địnhBayes 82.1 Giới thiệu.
- 92.2.1 Tối thiểu hóa xác suất lỗi phân loại.
- 132.3 Các phương trình phân biệt và các mặt quyết định.
- 162.4 Phân loại Bayes cho phân phối chuẩn.
- 17i Luận văn cao học Nguyễn Thị Hạnh2.4.1 Phân loại khoảng cách tối thiểu.
- 222.5 Ước lượng hàm mật độ xác suất chưa biết.
- 443 Phân loại tuyến tính 483.1 Giới thiệu.
- 48Tài liệu tham khảo 51ii Luận văn cao học Nguyễn Thị HạnhLời mở đầuLý thuyết nhận dạng là một ngành khoa học với mục đích nghiên cứucác thuật toán có khả năng phân loại các cá thể của một đám đông vàocác lớp hay các cụm khác nhau, tùy theo giả thiết đã biết hay chưa biếtvề số lớp của đám đông này.
- Theo ý nghĩa này, các nghiên cứu của lýthuyết nhận dạng sẽ tập trung vào hai hướng cơ bản sau:• Các nghiên cứu về các thuật toán nhận dạng khi giả thiết về sốlớp của đám đông đã cho trước sẽ được gọi chung là các thuật toánphân loại.• Các nghiên cứu về các thuật toán nhận dạng khi không có bất cứthông tin nào về số lớp của đám đông sẽ được gọi là các thuật toánphân cụm.Trong luận văn này chúng ta sẽ tìm hiểu một số thuật toán phân loạidựa trên cách tiếp cận thống kê toán học và luận văn sẽ được trình bàytrong ba chương sau:• Chương 1 là tổng quan chung về nhận dạng.
- Trong đó, phần đầu giới thiệu chung về tầm quan trọng củanhận dạng mẫu.
- Phần thứ hai trình bày các khái niệm về các đặctrưng, vec tơ đặc trưng và các lớp.
- Phần cuối là khái niệm về nhậndạng có hướng dẫn và nhận dạng không có hướng dẫn.
- Chương nàylà nền tảng cho chương sau với tài liệu tham khảo chính là [3].iii Luận văn cao học Nguyễn Thị Hạnh• Chương 2 tập trung vào các thuật toán phân loại dựa trên nguyênlý của quyết định Bayes và còn được gọi là các thuật toán phân loạiBayes.
- Các thuật toán này đều được xây dựng trên cơ sở đã chotrước các hàm mật độ phân phối xác suất của các lớp dạng.
- Vì vậy cácphương pháp ước lượng tham số và phi tham số cho hàm mật độphân phối xác suất cũng sẽ được xác định.
- Đặc biệt các khảo sátnhằm khẳng định vai trò của thuật toán phân loại Bayes trong cácthuật toán phân loại cực tiểu hóa tổn thất trung bình hay các thuậttoán phân loại cực tiểu hóa khoảng cách cũng sẽ được trình bày.Tàiliệu tham khảo chính cho chương này là [3.
- Chương 3 sẽ tập trung vào phân loại tuyến tính.
- Trong một sốtrường hợp, các lớp của chúng ta là phân biệt tuyến tính nghĩa làgiữa chúng tồn tại các hàm phân biệt tuyến tính.
- Việc phân loại bâygiờ sẽ tương đương với việc tìm ra các hàm phân biệt tuyến tính đósao cho xác suất lỗi phân loại là nhỏ nhất.Thuật toán Perceptronsẽ giúp chúng ta giải quyết vấn đề này.
- Hơn nữa, như chúng ta đãbiết nếu các lớp là phân biệt tuyến tính thì việc tính toán khá đơngiản.
- Vì thế, trong nhiều trường hợp các lớp không phân biệt tuyếntính nhưng chúng ta vẫn muốn đưa ra một phân lớp tuyến tính.Các phương pháp bình phương sẽ tính toán các trọng số theo mộtchuẩn tối ưu phù hợp để xác suất lỗi phân loại là chấp nhận được.Qua đây, em xin gửi lời cảm ơn sâu sắc đến người hướng dẫn khoahọc của mình, TS.
- Nguyễn Hữu Tiến, người đã đưa ra để tài và tận tìnhiv Luận văn cao học Nguyễn Thị Hạnhhướng dẫn trong suốt quá trình nghiên cứu của em.
- Đồng thời em cũng chân thành cảm ơn các thầy cô trong viện Toánứng dụng và Tin học trường Đại học Bách khoa Hà Nội, đã tạo mọiđiều kiện thuận lợi để em hoàn thành tốt chương trình học cao học củaTrường và hoàn thành bản luận văn này.Hà Nội, tháng 4 năm 2014Học viênNguyễn Thị Hạnhv Luận văn cao học Nguyễn Thị HạnhDanh mục các kí hiệu và chữ viết tắtC tập các số phứcR tập các số thựcZ tập các số nguyênkxk chuẩn của xB đại số Borelλ độ đo Lebesgue trên RχAhàm đặc trưng của tập ARnkhông gian Euclid n chiềuLp(R) không gian các hàm khả tích bậc p trên RL∞(R) không gian các hàm khả tích vô hạn trên RL1,loc(R) không gian các hàm giá trị thực khả tích địa phương trên Ra.e.
- hầu khắp nơi (viết tắt của cụm từ "almost everywhere")vi Luận văn cao học Nguyễn Thị HạnhDanh mục các hình vẽHình 2.1 Ví dụ trường hợp hai miềnvii Chương 1Tổng quan chung về nhận dạng1.1 Tầm quan trọng của nhận dạng mẫuNhận dạng là một môn khoa học mà mục tiêu của nó là sự phân loạicủa các đối tượng vào trong một số các lớp.
- Nhận dạng mẫu có mộtlịch sử lâu đời nhưng trước những năm 1960 các nghiên cứu lý thuyếtvề nhận dạng còn chưa được sự quan tâm đầy đủ của các nhà khoa học.Giống như mọi ngành khoa học khác, sự xuất hiện của máy tính đã làmtăng các nhu cầu về các ứng dụng thực tế của nhận dạng mẫu và chínhđiều này đã đặt ra các vấn đề mới thúc đẩy sự xuất hiện của lý thuyếtnhận dạng.
- Ngày nay, xu hướng này đã đưa nhận dạng mẫu đạttới đỉnh cao của những ứng dụng vào việc nhận biết, tìm kiếm và phân1 Luận văn cao học Nguyễn Thị Hạnhloại thuộc nhiều lĩnh vực khác nhau của đời sống xã hội.
- Để minh họađiều này chúng ta sẽ giới thiệu một số ứng dụng điển hình của lý thuyếtnhận dạng vào các lĩnh vực cụ thể của đời sống:• Máy quan sát là một phần quan trọng trong nhận dạng mẫu.
- Một loại ứng dụng của hệ thống máy quan sát là trong sảnsuất công nghiệp nhằm tự động hóa quá trình kiểm tra một dâychuyền lắp ráp.
- Ví dụ việc kiểm tra các sản phẩm được sản xuấttrên một dây chuyền tự động dựa trên các kết quả quan sát từ mộtcamera.
- Khi đó các hình ảnh thu được từ camera được phân tíchvà phân loại một sản phẩm được quan sát là "lỗi" hay "không lỗi"và theo kết quả này sản phẩm được chấp nhận hay từ chối.• Máy tính hỗ trợ chẩn đoán là một ứng dụng quan trọng khác củanhận dạng mẫu.
- Máy tính hỗ trợ chẩn đoán được ứng dụng và đượcquan tâm trong nhiều bài toán xử lý số liệu y tế như X- quang,hình ảnh chụp cắt lớp, hình ảnh siêu âm, điện tim đồ (ECGs) vàđiện não đồ (EEGs).
- Thực tế dữ liệu y tế nói chung không dễ diễngiải và việc giải thích nó còn phụ thuộc vào kinh nghiệm của bácsỹ.• Nhận dạng giọng nói là một lĩnh vực được đầu tư và nghiên cứurất mạnh mẽ.
- Vì thế mục tiêu xây dựng máy thông2 Luận văn cao học Nguyễn Thị Hạnhminh nhận biết ngôn ngữ nói đã và đang là đề tài nghiên cứu củanhiều tập thể các kỹ sư và các nhà khoa học.
- Các thành tựu đã đạtđược thuộc hướng nghiên cứu này có thể được sử dụng để nâng caohiệu quả trong môi trường sản xuất công nghiệp, đặc biệt là trongkiểm soát các quá trình sản xuất ở môi trường độc hại cũng nhưvào việc giúp người khuyết tật điều khiển máy bằng cách sử dụnggiọng nói để giao tiếp với các máy móc.
- Một thành công đáng kểcủa các nghiên cứu này là các ứng dụng để nhập dữ liệu vào máytính thông qua một micro.
- Phần mềm được xây dựng xung quanhmột hệ thống nhận dạng mẫu công nhận các văn bản nói và chuyểnnó thành ký tự ASCII , sau đó sẽ được hiển thị trên màn hình vàcó thể được đưa vào trong bộ nhớ của các máy tính để xử lý.Trên đây chỉ là một vài ví dụ của lý thuyết nhận dạng trong vài lĩnh vựckhác nhau của đời sống xã hội.
- Chúng ta còn có thể đề cập đến các ứngdụng điển hình như nhận dạng ký tự, nhận dạng vân tay, chứng thựcchữ ký, phục hồi văn bản và nhận dạng khuôn mặt, cử chỉ.
- Các ứngdụng mới này đã thu hút được nhiều sự quan tâm, đầu tư và nghiên cứunhằm tạo điều kiện thuận lợi hơn cho tương tác người- máy và nâng caohơn nữa vai trò của máy tính trong tự động hóa văn phòng, tự động hóacác điều kiện làm việc...1.2 Các đặc trưng, véc tơ đặc trưng và các lớpXét bài toán phân loại một tập các cá thể thuộc một hiện tượng nàođó.
- Khi đó ta sẽ sử dụng các khái niệm và các quy ước:3 Luận văn cao học Nguyễn Thị Hạnh• Không gian dạng: Không gian dạng là tập tất cả các cá thể hay đốitượng của một đám đông cần khảo sát và được ký hiệu là Ω với mỗiphần tử của nó được gọi là một dạng của không gian dạng, ký hiệulà ω và có ω ∈ Ω.• Không gian đặc trưng: Các dạng của không gian dạng khi quan sáthay thu thập được, thường được biểu diễn bằng một tập các đặctrưng hay các giá trị quan sát bằng số về một số thuộc tính xácđịnh của một dạng, nghĩa là mỗi một dạng ω của không gian dạngđược cho tương ứng với một véc tơ n chiều x các giá trị quan sát vềdạng này, trong đó thành phần thứ i của véc tơ được ký hiệu xivàđược gọi là biến hay đặc trưng thứ i của véc tơ dạng.
- Như vậy tacó véc tơ đặc trưng x ở dạng x = (x1.
- Rn, nghĩa là tập Rncác véc tơ đặc trưng còn được gọi là không gian đặc trưng.1.3 Nhận dạng có hướng dẫn và nhận dạng khôngcó hướng dẫnBài toán nhận dạng tổng quát sẽ là xác định cấu trúc của không giandạng thông qua các nghiên cứu xác định cấu trúc của không gian đặctrưng tương ứng của nó.
- Để thực hiện được các nghiên cứu này một tậpcác véc tơ đặc trưng là các kết quả quan sát trên các dạng của khônggian dạng Ω sẽ được cho trước.
- Tập dữ liệu này sẽ được gọi các tập luyệnvà được ký hiệu là S và tùy theo giả thiết đã cho về tập luyện S chúngta phân biệt bài toán nhận dạng thành hai bài toán cơ bản sau:4 Luận văn cao học Nguyễn Thị Hạnh• Nếu tập luyện S có dạng S :=x(k), ρ(k)|x(k)∈ Rn, ρ(k)∈ {1.
- Nnghĩa là cùng với các véc tơ đặc trưng, các chỉ số lớp của dạng đượcxét cũng đã cho trước thì tập luyện S được gọi là tập luyện có hướngdẫn và bài toán nhận dạng trong trường hợp này sẽ được gọi là bàitoán nhận dạng có hướng dẫn hay bài toán phân loại.• Nếu tập luyện S có dạng S :=x(k)|x(k)∈ Rn, k = 1.
- Nhay cácvéc tơ đặc trưng là cho trước nhưng chỉ số lớp của dạng là chưa biếtthì tập luyện S được gọi là tập luyện không có hướng dẫn và bàitoán nhận dạng trong tương ứng sẽ được gọi là bài toán nhận dạngkhông có hướng dẫn hay bài toán phân cụm.Trong hai bài toán nhận dạng cơ bản trên rõ ràng bài toán phân cụm làkhó hơn vì có ít thông tin cho trước hơn.Ta có thể minh họa bài toán phân lớp và phân cụm thông qua hai vídụ sau:Ví dụ 1.1.
- Bài toán xếp loại học lực của sinh viên trong một học kỳ:Giả sử một lớp học có N sinh viên, trong một học kỳ có 5 môn học (tức làn = 5).
- 5 của sinh viên thứ k ký hiệu là x(k)i.Khi đó sinh viên thứ k được đặc trưng bởi véc tơ là x(k)=x(k)1.
- "Trung bình( có điểm trung bình các môn từ 5,05 Luận văn cao học Nguyễn Thị Hạnhđến 6,9.
- Như vậy, học lực của sinh viên thứ k làρ(k .
- Chọn ngẫu nhiên ra một sinh viên, tất nhiên sinhviên này có đủ điểm của 5 môn học, khi đó thuật toán phân loại sẽ giúpchúng ta xác định xem sinh viên đó được xếp loại học lực nào, tức làxác đinh được ρ tương ứng của sinh viên đó.Ví dụ 1.2.
- Trong viễn thám đa phổ, năng lượng mặt điện từ phát ra từbề mặt trái đất được đo bằng máy quét nhạy cảm nằm trên một vệ tinh,một phi cơ hay một trạm không gian.
- Chúng ta sẽ đặt mỗi tế bào từ "cảm nhận"của bề mặt trái đất là một vec tơ x.
- n của vec tơtương ứng với cường độ điểm ảnh trong các dải quang phổ khác nhau.6 Luận văn cao học Nguyễn Thị HạnhCó thể sử dụng thuật toán phân cụm để tìm ra những nhóm mà các vectơ đặc trưng được phân cụm trong không gian n chiều

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt