Tài liệu Giáo trình nhận dạng mẫu

ĐẠI HỌC QUÓC GIA HÀ NỘI TRƯ Ờ NG ĐẠI HỌC CÔNG N G H Ệ _____________________•_______ Ị_________________________ !_ HOÀNG XUÂN HUẤN GIÁO TRÌNH NHẬN DẠNG MAU NHÀ XUẤT BẢN ĐẠI HỌC Q ư ố c GIA HÀ NỘI MỤC LỤC Lời nói đ ầu 9 Chương 1. GIỚI THIỆU 11 1.1. Nhận dạng mẫu là gì? 11 1.2. Các ví dụ 13 1.2.1. Bài toán phân loại 13 1.2.2. Bài toán hồi quy 15 1.2.3. Bài toán mô tả 17 1.3. Các hệ thông nhận dạng mẫu 18 1.4 Quá trình xây dựng hệ nhận dạng mẫu 22 1.5 Học máy và các cách tiếp cận 25 1.5.1 Học có giám sát 25 1.5.2 Học không có giám sát 25 1.5.3 Học tăng cường 26 1.5.4. Học thống kê 26 1.5.5. Mạng nơron nhân tạo 26 1.5.6. Nhận dạng mẫu có cấu trúc 27 Chương 2. PHÂN BIỆT MAU 29 2.1. Miền và hàm quyết định 29 2.1.1 Hàm quyết định 30 2.1.2 Tách được bỏi siêu phẳng 34 3 2.2. Các mêtric trong không gian đặc trưng. 39 2.3. Ma trận hiệp phương sai 41 2.4. Các thành phần chính 45 2.5. Đánh giá đặc trưng 46 2.5.1. Quan sát đồ thị 47 2.5.2. Đánh giá mô hình phân bô' 48 2.5.3. Kiểm định suy luận thống kê 48 2.6. Bài toán tỷ lệ chiều 49 Chương 3. PHÂN CỤM DỬ LIỆU 53 3.1. Phân lớp không giám sát 53 3.2. Vấn đề chuẩn hóa dữ liệu 55 3.3. Một số phương pháp chính 57 3.3.1. Phương pháp phân cấp 57 3.3.2. Phương pháp phân hoạch 60 3.3.3. Phương pháp dựa vào mật độ 66 3.3.4. Phương pháp phân cụm dựa trên lưới 69 3.3.5. Phân cụm nửa giám sát 71 3.4. Một 8ốchủ để liên quan 72 3.4.1. Trực quan hóa và giảm chiều dữ liệu 72 3.4.2. Đánh giố cụm 73 Chương 4. PHÂN LỚP THỐNG KẺ 75 4.1. Phân biệt tuyến tính 75 4.1.1. Phân lớp khoảng cách cực tiểu 75 4.1.2 Phân biệt tuyến tính Euclide 78 4.1.3. Phân biệt tuyến tính Mahalanobis 80 4.1.4, Phần biệt tuyến tính Ficher 81 4.2. Phân lốp Bayes 82 4.2.1. Phân lốp xác suất hậu nghiệm cực đại 83 4.2.2. Phân lóp cực tiểu rủi ro 86 4 .2 .3 . M iề n b á c bò (re je c t region) 88 4.2.4. Tỷ lệ chiều và ước lượng lỗi 90 4.3. Kỹ thuật phi tham 80' 91 4.3.1. Phương pháp cửa sổ Parzen 93 4.3.2. Phương pháp ưóc lượng k- láng giềng gần nhất 95 4.4. Quy tắc phân loại k- láng giềng gần nhất 96 4.5. Lựa chọn đặc trưng 97 4.6. Đánh giá các bộ phân lớp 98 4.6.1. Ưâc lượng lỗi của bộ phân lớp 4.6.2. So sánh các bộ phân lớp khác dữ liệu đào tạo 98 100 Chương 5. PHÂN LỚP BẢNG CÂY QUYẾT ĐỊNH 103 5.1. Biểu diễn cây quyết định 103 5.2. Học quy nạp và cây quyết định 105 5.3. Thuật toán học ID3 107 5.3.1. Mô tả thuật toán 108 5.3.2. Chọn thuộc tính phân loại tốt nhất 109 5.3.3. Ví dụ minh họa 112 5.3.4. N hận xét về ID3 114 5.4 Những hướng giải quyết các vấn đề khi học bằng cầy quyết định 116 5.4.1 Phòng tránh 8ự phù hợp trội 116 5.4.2. Kết hợp các thuộc tính có giá trị liên tục 120 5.4.3. Tiêu chuẩn để chọn thuộc tính 121 5.4.4. Xử lý mẫu huấn luyện vối giá trị thuộc tính bị mất 122 Chương 6. DỬ LIỆU TUÂN T ự 125 6.1. N hận dạng các xâu 125 6.1.1. Đối sánh xâu 126 6.1.2. Khoảng cách soạn thào 130 6.1.3. Đốì sánh xâu vối lỗi 132 6.1.4. Đối sánh với ký hiệu trung tính 132 6.2. Mô hình Markov ẩn 133 6.2.1. Mô hình Markov bậc nhất 133 6.2.2. Mô hình Markov ẩn và các bài toán cơ bản 135 6.2.3. Bài toán đánh giá 137 6.2.4. Bài toán giải mã 140 6.2.5. Bài toán học 141 Chương 7. MẠNG NƠRON NHÂN TẠO 7.1 Giỗi thiệu 145 145 7.1.1. Mạng Nơron sinh học 145 7.1.2. Mạng Nơron nhân tạo 146 7.1.3. Mô hình và kiến trúc mạng nơron 147 7.2. Perceptron 152 7.2.1. Kiến trúc Perceptron 152 7.2.2. Luật học Perceptron 154 7.3. Học Widrow-Hofĩ 7.3.1 Mạng ADALINE 157 157 7.3.2 Lọc thích nghi 7 4. MạngMLP 164 169 7.4.1. Kiến trúc mạng 169 7.4.2. Thuật toán BP 171 7.4.3. Bình luận vể thuật toán 178 7.5. Mạng RBF 178 7.5.1. Kiến trúc mạng RBF 179 7.5.2 Đào tạo mạng'RBF 179 7.6. Mạng Hammiog 185 7.6.1. Kiến trúc mạng Hamming 185 7.6.2. Cơ chế hoạt động 185 7.7. Bản đồ đặc trưng tự tổ chức 187 7.7.1. Quan hệ lân cận giũa các nơron 187 7.7.2. Kiến trúc và hoạt động của SOFM 188 Chương 8. KẾT HỢP CÁC BỘ PHÂN LỚP 8.1. Các phương pháp tập thể trong học máy 193 193 8.2. Phương pháp bỏ phiếu 195 8.3 Hai kỹ thuật thông dụng tạo bộ nhận dạng cơ sở 196 8.3.1. Nhặt theo gói 196 8.3.2. Nhặt định hưống 197 8.4. Kiến trúc bậc thang 200 Tài liệu tham khảo 203 7 LỜI NÓI ĐẦU Giáo trìn h N h ậ n dạng mẫu vói thời lượng 2 đến 3 tín chỉ được giảng dạy cho học viên cao học ngành Khoa học m áy tín h của trưòng Đại học Công nghệ, cung cấp cho người học những kiến thức cơ bản để xây dựng các hệ phân lớp và mô tả m ẫu trong các ứng dụng. Ngoài ra giáo trình này cũng được dùng làm chủ đề lựa chọn của môn học các chủ đề hiện đại của khoa học m áy tín h cho sinh viên giai đoạn cuối của ngành này, nhằm hỗ trợ sinh viên làm khóa luận và có nhu cầu nghiên cứu. N hận dạng m ẫu có lịch sử phát triển khá sớm, nhưng trưóc những năm 1960 nó đơn thuần là kết quả ứng dụng của các nghiên cứu lý thu y ết trong lĩnh vực thống kê. Ngày nay nó phát triển m ạnh mẽ, bao gồm một phạm vi rộng và có ứng dụng rộng rãi, đặc biệt trong th iế t k ế các thiết bị nghe nhìn, xử lý tín hiệu tự động và khám phá tri thức từ dữ liệu. Vì lượng kiến thức r ấ t lón mà thòi lượng ít, hơn nữa để hiểu th ấu đáo th ì đòi hỏi ngưòi học phải có nền tảng toán học tốt, đặc biệt về xác suất thống kê, nên chúng tôi chú trọng giói thiệu các th u ậ t toán và hưống dẫn sử dụng mà không đi sâu vào bản chất toán học. M ột số kiến thức khó nhưng cần dùng, chẳng hạn như mô hình Markov ẩn, th u ậ t toán độj sánh nhanh các xâu..., chúng tôi giới thiệu những n é t chính để gợi mở cho những học viên muôn tìm hiểu sâu hơn. Chương đầu của giáo trìn h dành để giới thiệu khái niệm nhận dạng m ẫu, phác họa bức tran h chung của một hệ nhận dạng mẫu cùng vói quy trìn h th iế t kế. Chương 2 trìn h bày phương pháp phân biệt m ẫu nhò hàm quyết định và các vấn để liên quan kh i xử lý dữ liệu. Cốc phương pháp phân cụm dữ liệu được trìn h bày trong chương 3. Chương 4 giới thiệu các phương pháp nhận dạng m ẫu thống kê. Phương pháp phân lốp nhò cây quyết định được 9 trìn h bày trong chương 5. Chương 6 trìn h bày các bài toán và th u ật toán thưòng gặp trong xử lý dữ liệu tu ần tự bao gồm các th u ậ t toán đếi sánh xâu và các bài toán trong mô hình Markov ẩn. Các m ạng nơron nhân tạo thông dụng n h ấ t được giới thiệu trong chương 7. Chương cuối chúng tôi giối thiệu các phương pháp kết hdp các bộ phân lóp để nâng cao chất lượng hệ nhận dạng, bao gồm phương pháp học tập thể và tổ chức kiến trúc bậc thang. Giáo trìn h này cũng có thể dùng làm tài liệu tham khảo cho nghiên cứu sinh và sinh viên các ngành khác thuộc nhóm ngành công nghệ thông tin. Để hiểu sâu hơn, chúng tôi giới thiệu một số tài liệu tham khảo m à chúng tôi có thể cung cấp [1-5], bao gồm cả các tiếp cận liên quan m ật th iế t như học máy [6-8] và m ạng nơron [9-11]. Do lần đầu xuất bản nên chắc chốn giáo trình còn nhiều thiếu sót, chúng tôi rấ t mong nhận được cốc ý kiến gốp ý để giáo trìn h được hoàn thiện hơn. T ác giả 10 Chương 1 GIỚI THIỆU Trước khi đi sâu vào các phương pháp n h ận dạng mẫu, chương này giới thiệu khái niệm mẫu và n h ận dạng m ẫu máy, phác họa bức tra n h chung của một hệ nhận dạng m ẫu cùng với quy trìn h th iết k ế nó. 1.1. N h ậ n d ạ n g m ẫ u là gì? Ngày nay, m áy tính đã chửng tỏ khả năng nổi trội của nó trong tín h toán và xử lý thông tin so vối con người. Tuy nhiên, trong khi mỗi người bình thường đều dễ dàng cảm nhận, quan sát được các sự vật, hiện tượng xung quanh như nhận ra một gương m ặt quen, hiểu lòi nói đôi thoại, đọc các chữ viết tay và phân biệt thức ăn từ mùi của nó..., thì ngưòi ta vẫn rấ t khó tạo ra được máy tín h có các khả năng này như người. N hu cầu tạo r a các máy móc được tran g bị các hệ thống thông m inh, cạnh tran h được với con ngưòi trong quan sá t và cảm nhận các sự vật, hiện tượng trong môi trường như vậy thúc đẩy r a đòi lĩnh vực nghiên cứu "nhận dạng m ẫu má y” hay gọi gọn hơn là nh ậ n dạng m ẫu (Pattern Recognition - PR). Mẫu. Các đối tượng được quan sát, nhận biết sẽ được gọi chung là m ẫu (pattem ) và đôi khi vẫn được gọi là đối tượng. Tùy theo cốc ứng dụng, m ẫu có th ể phân làm hai loại: m ẫu trừ u tượng và mẫu cụ thể. Các ý tưỏng, lập luận và khái niệm là những ví dụ về mẫu trừ u tượng, nhận dạng các m ẫu như vậy thuộc về lĩnh vực nhận dạng khái niệm. Các m ẫu cụ th ể bao gồm cốc đốì tượng vật lý; chữ ký; chữ viết; ký hiệu; ảnh; đoạn sóng âm thanh; điện não đồ hoặc 11 điện tâm đồ; chuỗi DNA, hàm số... là đối tượng nghiên cứu chính trong giáo trìn h này. N h ậ n dạng mẫu. ở mức khái niệm, nhận dạng m ẫu là lĩnh vực khoa học nghiên cứu các phương pháp mô tả, phân lớp hay gán nhãn cho các m ẫu để tạo ra các hệ thống cạnh tra n h được vói khả năng này của con người. Từ th ế kỷ 16 Kepler đã sử dụng dữ liệu quan sá t thiên văn để khám phá quỹ đạo chuyển động của các h àn h tinh, thúc đẩy sự phát triển của cơ học cổ điển. Trước những năm 1960, các ứng dụng PR chủ yếu vẫn chỉ là áp dụng các nghiên cứu trong lĩnh vực thống kê. Ngày nay các hệ nhận dạng m ẫu có phạm vi ứng dụng rấ t rộng, dưới đây là các ví dụ về hoạt động thành công trong một số lĩnh vực ♦ điển hình. Nông nghiệp. • Dựa trên các dữ liệu về th ổ nhưỡng và đặc tín h cây trồng, vật nuôi, ngưòi ta đánh giá phân loại đ ấ t để hỗ trợ cho các quyết định canh tốc. • P hân tích các số liệu quá khứ và biến đổi thời tiế t để phát hiện, dự báo dịch bệnh và sản lượng m ùa vụ... Thiên văn học. • P hân tích tự động quang phổ. • P h át hiện các vật th ể mới và thay đổi của vũ trụ dựa trên ảnh thiên văn. S in h học. • Cốc ứng dụng PR trong tin-sinh học là công cụ hiệu quả để nghiên cứu sinh học phân tử, phân tích cấu trú c nhiễm sắc thể, xác định các đặc tín h di truyền và đưa ra các phương pháp biến đểi gen trong công nghệ sinh học. • P hân tích sự ph át triển của các quần thể 12 Y học. • Chẩn đoán và đưa phác đồ điều trị bệnh dựa trê n các triệu chứng, kết quả xét nghiệm và ảnh X-quang. • P hân tích điện não đồ, tâm đồ và ảnh điện quang để phát hiện bệnh và trạng thái sức khỏe... Quản lý đô thị. • P hân tích và điều khiển giao thông. • Đ ánh giá và dự báo sự phát triển đô thị. K inh tế-xã hội. • P hân tích và dự báo về các thay đổi trên thị trường. • P hân tích hoạt động doanh nghiệp, trợ giúp các quyết định kinh doanh, thương mại điện tử. • Khám phá tri thức trên cơ sở dữ liệu. A n ninh, quăn đội. • N hận dạng vân tay. • Khám phá, phân tích các tín hiệu rada, âm th an h và ảnh h àng không. • Theo dõi các hệ thống báo động. • Xác định mục tiêu tự động. 1.2. C á c v í d ụ Để m inh họa rõ hơn cho khái niệm PR, trong mục này giới th iệu ví dụ cho các bài toán điển hình: phân loại, hồi quy và mô tả. 1.2.1. B à i to á n p h â n lo ạ i P h â n loại hay phân lớp có giám sá t là dạng bài toán thường gặp n h ấ t trong nhận dạng mẫu. Trong bài toán này, dựa trê n các tr i thức hoặc quan sát đã có, người ta phân các đốì tượng mới vào một trong các lốp đã biết. Hệ nhận dạng tr á i cây là ví dụ cho bài to án này. 13 Ta tưỏng tượng một hệ thống phân loại trái cây trê n băng chuyển có mô hình như trong hình 1.1. Tín hiệu của trá i cây thu được từ các bộ cảm biến (Sensor) có thể là màu sắc, hình dáng, trọng lượng... Từ các tín hiệu th u được, ngưòi ta trích, chọn các đặc trưng để biểu diển cho mỗi trái cây sao cho việc tính toán phân lóp dễ dàng và chính xác. Để đơn giản, ta xét hệ phân biệt hai loại trái cây: cam và táo, các đặc trưng của chúng có th ể biểu diễn dưới dạng số hoặc định danh. Chẳng hạn, đặc trưng m àu có thể là: Dạng số: biểu diễn dưới dạng cường độ mức xám, là đại lượng thuộc khoảng [0, a], 0 ứng với mức không có màu còn a là mức xám cực • đại. T Dạng định danh: đỏ/ xanh lá cây/ xanh.... Hlnh 1.1. Mô hlnh hệ thống phãn loại trái cAy trôn b ỉn g chuyển Khi biểu diễn đặc trưng dạng số, mỗi quả sẽ ứng với một điểm trong không gian đặc trưng. Bài toán nhận dạng trỏ th à n h bài toán phân lớp cho mỗi vectơ (điểm) trong không gian đặc trưng, về sau ta dùng ký hiệu bằng chữ in đậm để chi các vectơ. Xét đặc trưng số của trọng lượng (xt) và m àu (xị) của trái cây, vectơ đặc trưng X là vectơ hai chiều: 14 V trọng lượng *2. màu Qua quan sát thực nghiệm, các quả cam chín và táo xanh rơi vào miền có tâm như trong hình 1.2-a. H ình 1.2-b cho thấy một quả táo đỏ có thể bị nhầm là cam còn quả cam xanh thì ta không phân biệt được. Để tăng độ chính xác, người ta có thể xét thêm đặc trư ng vỏ là nhẵn hoặc thô, nếu bộ cảm biến xác định đặc trưng này tốt thì cam sẽ có vỏ thô còn táo có vỏ nhẵn. Việc chọn đặc trư ng có ý nghĩa quan trọng đối vối hệ phân loại và phụ thuộc vào ch ất lượng của các bộ cảm biến. Hlnh 1.2. a) Q u ỉ cam vá táo trong kh&ng gian đ ặc tnm g. b) Quả táo đỏ giống cam còn cam xanh khó ph&n biệt 1.2.2. B à i to á n h ồ i q u y Trong thực tế, ta thường phải xác định giá trị của hàm nhiều biến tại các điểm mối thuộc miền nào đó dựa trê n những số liệu đo được (quan sát) của hàm trên miền này. Bài toán này là bài toán hồi quy nhiều biến và được phát biểu tổng qu át như sau. Xét hàm f: D ( c R n) -*R và tập dữ liệu T={xk,y 1<}N], xk e R" Vk đo được dưới dạng: 15 ( 1. 1) trong đó £t là nhiễu tráng (các đại lượng ngẫu nhiên độc lập cùng phân bố có kỳ vọng bằng không). Ta cần tìm hàm (p: D ( c R ) —'R có dạng nào đó sao cho: (p (x ) * y k ( 1.2 ) đủ tốt theo nghĩa nào đó và dùng

...,ck, trong đó (x,c......) là hàm phụ thuộc tham sô' nào đó đã chọn. Thông thường các tham số này được tìm nhò cực tiểu hàm mục tiêu nào đó, chẳng hạn sai số trung bình phương: (1.4) H ình 1.3 minh họa các hàm hồi quy (đưòng đứt) và hàm nội suy dạng đa thức cho hàm một biến có giá trị đo ỏ 8 điểm. 16 Hlnh 1.3. Đ ổ thị hàm hổi quy (đưòng đứt) và nộl su y (đưàng liổn) 1.2.3. B à i to á n m ô tả Các kỹ th u ậ t mô tả được ứng dụng đa dạng trong phân tích ảnh, đặc biệt là phân tích các tín hiệu lý-sinh. Để làm ví dụ, ta x ét các biểu đồ của tốc độ nhịp tim thai trong một thời kỳ nào đó. Các biểu đồ này ghi tầ n số tức thòi của nhịp đập tim th ai (sô" lần/phút) và sự biến đổi nhịp tim trong biểu đồ được các chuyên viên sản khoa dùng để phân tích, đánh giá th ể trạn g th ai nhi. Hình 1.4a m inh họa một biểu đồ tốc độ nhịp tim th ai (gọi tắ t là biểu đồ tim thai). b) Mô t ỉ phẩn đẩu củ a biểu đổ b in Một hệ mô tả sẽ xử lý các biểu đồ, ph át hiện và mô tả các thời gian nhịp tim thai có biến đổi nhiều để giúp chuyên gia nhận định th ể trạn g th ai nhi. Hệ này mô tả biểu đồ như là xâu-các-iỊiành tố 17 biến đổi sơ cấp trong các khoảng thòi gian bé để xấp xỉ biểu đồ, đặc biệt là ỏ các giai đoạn có thay đổi nhiều. Chẳng hạn, phần đầu của biểu đồ trong hình 1.4-a được mô tả như trong hình 1.4-b. Các thay đổi của biểu đồ được phân lớp theo các thành tô" cho bởi bảng 1.1 dựa trên hệ số tăn g hay giảm của tầ n sô” trong khoảng biến thiên được xét, trong đó À là ngưỡng được chọn trưổc. Bảng 1.1 C ác thành tố mô tà nhịp tim thai. Tèn thành tố K ỷ hiệu Mô tả Ngang n Đoạn giá trị không đổi Đi lên t Đoạn giá trị tăng vớí hệ số < À Đi xuống ỡ Đoạn giá trị giảm với hệ số >- À Lên mạnh T Đoạn giá trị tăng với hệ số > A Xuống mạnh G Đoạn giá trị giảm với hệ số <- A Hệ sẽ xử lý các xâu th àn h tố và quan tâm nhiều tói các thòi gian chứa điểm nhọn ứng với có u và D liên tiếp hoặc ngược lại, chẳng hạn, trong hình 1.4 đoạn biểu đồ được mô tả là xâu ‘tgtGTttg”. Việc phân tích và hiển thị các biểu đồ như vậy giúp cho các chuyên gia r ấ t nhiều. Ngoài ra, dựa trên các kiến thức chuyên gia, hệ thống có thể tự động đánh giá, phân loại biểu đồ tim th ai. 1.3. C ác h ệ th ố n g n h ậ n d ạ n g m ẫu Mặc dù có r ấ t nhiều loại bài toán PR, tuy nhiên, để giải quyết một bài toán PR thì thông thường một hệ thống n h ận dạng m ẫu gồm có các th àn h phần cd bản theo sơ đồ trong hình 1.5. Các bộ cảm biến th u nhận và chuyển đổi hình ảnh hoặc ẵm thanh hoặc các đầu vào vật lý khác th àn h dữ liệu dạng tín hiệu. Bộ phân đoạn tách các đốì tượng cảm biến khỏi hình nền hoặc các đối tượng khác. Một bộ trích chọn đặc trư ng đo các thuộc tín h củ a đốì tượng cần cho nhận dạng. Bộ nhận dạng phân tích những đặc trưng này để gán một đốì tượng vào một lớp hoặc tín hiệu mô Ità. Cuối cùng, bộ hậu xử lý để quyết định xử lý khi xét đến tác đỘỊng khác theo ngữ cạnh và srị£Bhải tr ả cho lỗi. 18 Hlnh 1.5. C á c thành phẩn trong hệ nhận dạng mẫu đlẩn hlnh Để hiểu được các vấn để khi thiết kế một hệ thống nhận dạng, chúng ta cần hiểu từng thành phần của nó. Các bộ cảm biến (sensor) Nếu là hệ nhận dạng đối tượng vật lý, ở đầu vào của hệ thống thường là một loại th iết bị chuyển đổi như m áy ghi hình hay ghi âm. Các đặc trưng và hạn chế của các thiết bị này như băng thông, độ phân giả, độ nhậy cảm ... có thể ảnh hưỏng tới hoạt động của hệ thống và ta không đi sâu vào chi tiết chủ đề này. Một số hệ không sử dụng các bộ cảm biến mà lấy tín hiệu từ một thiết bị hoặc đầu ra cùa hệ thống khác. Tiền xử lý tín hiệu (preprocessing) Tín hiệu nhận được từ các bộ cảm biến hoặc các th iết bị khác thường chứa nhiễu hoặc sai sót. Vì vậy ở công đoạn này, các tín hiệu được lọc nhiễu và tăng cường chất lượng. Phân đoạn (segmentation) và nhóm Trong ví dụ về phân loại trái cây chúng ta đã ngầm giả sử rằng các trá i cây tách biệt nhau và có thể dễ dàng phân biệt trên báng chuyền. Trong thực tế, chúng có thể gần hoặc sát nhau và hệ thống của chúng ta phải có khả năng xác định được từng quả riêng biệt. Việc xác định, phân lập tín hiệu từng cá thể gọi là phân đoạn (segmentation). Nếu chúng ta đã nhận dạng được các trá i cây thì việc phân lập từng cá thể là tương đôì dễ dàng nhưng vấn đề là ta phải thực hiện phân lập khi chưa biết chúng có những loại nào. Do đó chúng ta cần phải có cách để biết được khi nào thì chuyển từ 19 một đốì tượng này sang một đối tượng khác hoặc biết được phần nào chỉ là ảnh nền. Phân đoạn là một trong những bài toán rấ t khó trong nhận dạng m ẫu. Chẳng hạn, trong hệ thống tự động n h ận dạng tiếng nói, chúng ta phải cô" gắng n h ận ra từng âm riêng biệt. Liên quan chặt chẽ tới việc phân đoạn là bài toán nhận dạng hoặc nhóm nhiều đối tượng liên quan lại với nhau. Chữ i hoặc ký hiệu = có hai th àn h phần liên kết, nhưng ta thấy chúng như là một ký hiệu. Đây là vấn để phức tạp về quan hệ giữa các th àn h tố với đôl tượng, giữa tập hợp con và tập hợp cha, nó quyết định việc nghiên cứu bộ phận hay toàn thể các mối quan hệ. Trích chọn đặc trưng (feature extraction and selection) Mục tiêu chung của bộ trích chọn đặc trưng là dựa trên tín hiệu th u được, mô tả lại các đối tượng bằng các giá trị sô' hay định danh (các đặc trưng) sao cho chúng gần nhau với các đối tượng thuộc cùng loại và khác xa nhau nếu khác loại. Hơn nữa để tiện xừ lý thì càng ít đặc trưng càng tốt. Điều này dẫn đến việc phải tìm ra các đặc trưng khác nhau và chúng không phụ thuộc hoàn cảnh ta th u tín hiệu về đốì tượng. Như trong ví dụ phân lớp trái cây thì vị trí tuyệt đốì của mỗi trái cây trên băng chuyền là không liên quan đến loại quả, do đó chúng ta không cần quan tâm đến vị trí của các trá i cây cụ thể. N hiều khi ta muốn các đặc trưng phải không th ay đổi cho dù ta xoay ngang hay dọc hay tịn h tiến... và ta gọi đặc trư n g này có tính bất biến với biến đổi tưdng ứng. Chẳng hạn, các đặc trư n g của chữ viết tay b ấ t biến vói phép quay và tịn h tiến r ấ t th u ậ n lợi cho việc n h ận dạng. Trong nhận dạng tiếng nói, chúng ta muôn các đặc trưng không bị ảnh hưỏng theo thòi gian và tăn g hay giảm toàn bộ biên độ. Chúng ta cũng muốn các đặc trư ng không nhạy cảm vối độ dài của mỗi từ hay tốc độ lấy mẫu. Đ ầu r a của giai đoạn này cho ta một vectd đặc trư ng ứng vói mỗi đốì tượng được khảo sát, thích hợp n h ấ t là các vectơ thực. 20 Ranh giỏi khái niệm giữa việc trích chọn đặc trưng và phân lớp ỏ mức độ nào đó có phần không rõ ràng; một bộ trích chọn đặc trưng lý tưởng phải làm cho công việc còn lại của bộ phân lóp trở nên dễ dàng. Ngược lại, một bộ phân lớp tố t đòi hỏi ít ở bộ trích chọn đặc trưng. N h ận dạng Nhiệm vụ của th àn h phần này trong hệ thông là sử dụng các véc tơ đặc trưng được cung cấp từ bước trước để gán nhãn cho các đôi tượng (trong các bài toán phân lốp hoặc hồi quy) hay mô tả chúng. P h ân lóp là bài toán thường gặp nh ất trong PR và được chia th àn h hai bài toán: phân loại (phân lớp có giám sát) và phân cụm (phân lớp không giám sát). Trong phân lốp có giám sát, ta được biết n h ãn lỏp của một tập đối tượng cho trưóc và trê n sơ sở đó sẽ th iế t k ế bộ nhận dạng để gán nhãn cho các đối tượng mới. Độ khó của bài toán nhận dạng phụ thuộc vào cõ và sự biến thiên của vectơ đặc trưng trong từng bài toán, độ đo tương tự hay khoảng cách được xét giữa các đốì tượng. Các độ đo này phụ thuộc vào các đặc trưng được chọn, chúng cho phép ta xác định tính tương đồng của các đối tượng trong cùng một lóp/cụm và sự khác biệt giữa các đối tượng trong các lóp/cụm khác nhau. Với bài toán n h ận dạng cam và táo, nếu ta chọn đặc trưng 8ố về m àu và dáng rồi dùng khoảng cách ơ clit như minh họa trong hình 1.2 th ì sẽ có nhiều trưòng hợp không phân biệt nổi là quả nào. Tuy nhiên, nếu ta chọn đặc trưng là đặc điểm vỏ thô hay nhẵn th ì dễ dàng phân biệt được cam hay táo. H ậu xử lý Một bộ nhận dạng hiếm khi chỉ để dùng đơn lẻ. K ết quả nhận dạng thường dùng làm cơ sở để đưa ra thao tác tương ứng (đặt quả này vào giỏ này, đặt quả khác vào giỏ kia), mỗi thao tác m ất một chi p h í riêng. H ậu xử lý sẽ phân tích kết quả của bộ phân lớp để quyết định chọn thao tác tương ứng. 21