PHÂN LỚP ẢNH SỬ DỤNG KỸ THUẬT MDS KẾT HỢP VỚI SVM

PHÂN LỚP ẢNH SỬ DỤNG KỸ THUẬT MDS KẾT HỢP VỚI SVM Nghiên cứu, tìm hiểu các phương pháp kỹ thuật áp dụng vào bài toán phân lớp, tìm hiểu cách thức hoạt động của mô hình nhận dạng và các kỹ thuật hoạt động. Phần nội dung: Có cấu trúc 3 chương • Chương 1: Khái quát về xử lý ảnh, tổng quan về các kỹ thuật phân lớp ảnh và nhận dạng. • Chương 2: Giới thiệu về kỹ thuật MDS, MDS kết hợp SVM, xây dựng mô hình phân lớp MDSSVM, mô tả hoạt động của hệ thống phân lớp cũng như lưu đồ giải thuật của hệ thống. • Chương 3: Cài đặt và chạy chương trình thử nghiệm, đưa ra các thông số mô phỏng, giới thiệu giao diện chương trình.

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC DUY TÂN

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC DUY TÂN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS ĐẶNG VIỆT HÙNG

ĐÀ NẴNG – 2014

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi

Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được aicông bố trong bất kỳ công trình nào khác

Tác giả

Ngô Thành Tâm

Tôi xin bày tỏ cảm ơn sâu sắc đến thầy TS Đặng Việt Hùng, người đã tậntình chỉ dẫn và giúp đỡ tôi trong suốt quá trình xây dựng đề cương cho đến khi hoànthành luận văn, Thầy cũng là người định hướng cho tôi những bước đi của mìnhtrong định hướng sự nghiệp tương lai, bên cạnh đó tôi xin bày tỏ lòng biết đến thầy

TS Phạm Anh Phương đã có những trao đổi, chia sẻ những kinh nghiệm quý báu vềlĩnh vực mà tôi nghiên cứu để tôi có thể hoàn thành tốt luận văn

Tôi xin bày tỏ lòng biết ơn Ban Giám Hiệu, cùng các thầy cô và các anh chịkhoa sau đại học Trường Đại Học Duy Tân chuyên ngành Khoa Học Máy Tính(2012-2014), đã tạo các điều kiện thuận lợi như thời gian, cơ sở vật chất để tôi cóthể học tốt trong cả khóa học và thời gian hoàn thành luận văn đúng tiến độ

Tác giả luận văn

Ngô Thành Tâm

LỜI CAM ĐOAN I LỜI CẢM ƠN II MỤC KÝ HIỆU, CHỮ VIẾT TẮT V DANH MỤC BẢNG VI DANH MỤC HÌNH VII

MỞ ĐẦU 1

1 Lý do chọn đề tài 1

2 Mục tiêu nghiên cứu: 1

3 Đối tượng và phạm vi nghiên cứu: 1

4 Phương pháp nghiên cứu 2

5 Kết quả đạt được: 2

6 Ý nghĩa khoa học và thực tiễn của luận văn 3

7 Cấu trúc luận văn 3

PHẦN NỘI DUNG 5

CHƯƠNG I: TỔNG QUAN VỀ PHÂN LỚP VÀ NHẬN DẠNG 5

1 Giới thiệu về xử lý ảnh: 5

1.1 Một số khái niệm 5

1.2 Tổng quan về phân lớp và nhận dạng: 8

1.2.1 Bài toán về phân loại 9

1.2.2 Một số bộ phân loại phổ biến 10

1.2.2.1 Cây quyết định 10

1.2.2.2 Mạng Bayes 10

1.2.2.3 Kỹ thuật K người láng giềng gần nhất: 10

1.2.2.4 Support Vector Machine 11

1.2.3 Bài toán phân lớp nhận dạng 11

1.2.4 Giới thiệu về kỹ thuật SVM, PCA, PCA-SVM 13

1.2.4.1 Giới thiệu về kỹ thuật SVM 13

a Cở sở lý thuyết của SVM 13

b Các khái niệm nền tảng 13

c Chiều VC (VC-dimension) 14

d Phân hoạch tập dữ liệu bằng các siêu mặt có hướng 14

e SVM tuyến tính 16

g SVM phi tuyến 20

h Các kỹ thuật cài đặt và phân lớp 22

i Hạn chế của phương pháp SVM 23

1.2.4.2 Giới thiệu về kỹ thuật PCA 23

a Thuật toán PCA để trích chọn đặc trưng: 24

b Phân tích thành phần chính PCA 25

1.2.4.3 Xây dựng mô hình kết hợp PCA-SVM 28

CHƯƠNG II: GIỚI THIỆU KỸ THUẬT MDS, MDS-SVM 30

2.1 Giới thiệu về kỹ thuật MDS 30

2.1.1 Cơ bản về Multidimensional Scaling (MDS) [3] 30

2.1.2 Cấu trúc kỹ thuật Ratio MDS (MDS tỉ lệ) 31

2.1.3 Cấu trúc kỹ thuật Ordinal MDS (MDS chỉ số) 33

2.1.4 Nonmetric MDS 39

2.1.5 Giới thiệu về Individual differences models (INDSCAL): [4] 43

2.1.5.1 The Tucker-Messick model 44

2.1.5.2 INDSCAL 44

2.1.6 Giới thiệu thuật toán SMACOF: [3] 45

2.1.7 Giới thiệu thuật toán classic metric algorithm [6] 46

2.2 Xây dựng mô hình hệ thống MDS-SVM 48

2.3 Mô tả hệ thống hoạt động MDS – SVM 48

CHƯƠNG III: KẾT QUẢ PHÂN LỚP ẢNH DỰA TRÊN KỸ THUẬT MDS VÀ SVM51 3.1 Cài đặt chương trình mô phỏng 51

3.1.1 Các thông số mô phỏng MDS và SVM 52

3.1.2 Giới thiệu giao diện chương trình 52

3.2 Kết quả mô phỏng PCA-SVM và MDS-SVM 57

3.2.3 So sánh Kết quả mô phỏng PCA- SVM và MDS-SVM 59

3.2.4 Kiểm tra kết quả nhận dạng mặt người sử dụng MDS-SVM 61

a Sử dụng cơ sở dữ liệu ifd: 61

b Sử dụng phương pháp phát hiện khuôn mặt trong nhận dạng : 63

KẾT LUẬN 64

1 Những vấn đề luận văn làm được: 64

2 Thách thức chưa giải quyết được 65

3 Hướng phát triển của đề tài 65

DANH MỤC TÀI LIỆU THAM KHẢO 67

7 SMACOF Scaling by Majorizing a Complicated Function

DANH MỤC BẢNG

g

Bảng 2 Thứ tự khoảng cách của bảng 1, khoảng cách nhỏ nhất là 1 34

Bảng 6

Bảng kết quả kiểm tra sử dụng 60% để huấn luyện và 40% kiểm

tra của cơ sở dữ liệu att sử dụng phương pháp PCA-SVM,

MDS-SVM

59

Bảng 7

Bảng kết quả kiểm tra sử dụng 70% để huấn luyện và 30% kiểm

tra của cơ sở dữ liệu att sử dụng phương pháp PCA-SVM,

MDS-SVM

60

Bảng 8

Bảng kết quả kiểm tra sử dụng 60% để huấn luyện và 40% kiểm

tra của cơ sở dữ liệu ifd sử dụng phương pháp PCA-SVM,

MDS-SVM

60

Bảng 9

Bảng kết quả kiểm tra sử dụng 60% để huấn luyện và 40% kiểm

tra của cơ sở dữ liệu ifd sử dụng phương pháp PCA-SVM.,

MDS-SVM

60

Hình 1.6 Siêu mặt phân cách tuyến tính trường hợp phân cách được 17

Hình 1.7 Siêu mặt phân cách tuyến tính cho trường hợp không phân cách 20

Hình 1.8 Chuyển từ không gian ít chiều sang không gian nhiều 21

Hình 1.9 Mặt phẳng [-1,1] X [-1,1] ∈ R2 thành mặt cong trong R3 23

Hình 1.10 Minh họa PCA tìm các trục tọa độ mới sao cho dữ liệu có độ biến

Hình 1.11 Hình hiển thị dung PCA giảm số chiều những vẫn đảm bảo được các

Hình 2.1 Bước đầu tiên của MDS với khoảng cách trong bảng 1 33

Hình 2.4 Kết quả cuối cùng của MDS cho bảng dữ liệu 1 33

Hình 2.6 Phản ánh ngang cấu hình trong hình 2.5 để hướng Đông nằm bên phải 33

Hình 2.8 Cấu hình của các Hình 2.7 trên bảng đồ châu Âu 34

Hình 2.9 Không gian của tất cả điểm 9 với d39 < d29 35

Hình 2.10 Không gian các điểm với điều kiện d29 < d23 và d39 < d23 35

Hình 2.18 Mặt phẳng Cartesian với các điểm i, j được nối với nhau bởi các đoạn

Hình 2.20 Sơ đồ mô tả các bước hoạt động của hệ thống MDS&SVM 50

Hình 2.21 Ảnh sau khi được chuẩn hóa chuyển về dạng Gray 51

Hình 3.5 Giao diện huấn luyện và kiểm tra kết quả so sánh giữa hai phương

Hình 3.6 Hình kết quả số chiều/vector, độ chính xác, thời gian xử lý 57

Hình 3.7 Hình kết quả ID các ảnh dung Train & Test 57

Hình 3.9 Giao diện nhận dạng mặt người sử dụng MDS-SVM 58

Hình 3.10 Sơ đồ của cơ sở dữ liệu att, sử dụng 60% huấn luyện, 40% kiểm tra 61

Hình 3.11 Sơ đồ của cơ sở dữ liệu att, sử dụng 70% huấn luyện, 30% kiểm tra 62

Hình 3.12 Sơ đồ của cơ sở dữ liệu ifd, sử dụng 60% huấn luyện, 40% kiểm tra 62

Hình 3.13 Sơ đồ của cơ sở dữ liệu ifd, sử dụng 80% huấn luyện, 20% kiểm tra 63

Hình 3.14 Kết quả thể hiện chính xác đối tượng nhận dạng trong ifd 64

Hình 3.15 Kết quả thể hiện không chính xác đối tượng nhận dạng trong ifd 64

Hình 3.16 Sử dụng phương pháp dò tìm khuôn mặt để tách ảnh khuôn mặt 65

Hình 3.17 Sử dụng phương pháp dò tìm khuôn mặt để tách ảnh nhiều khuôn mặt 65

MỞ ĐẦU

1 Lý do chọn đề tài

Trong thời đại công nghệ thông tin hiện nay lĩnh vực xử lý ảnh và nhận dạngngày càng chiếm một vị trí quan trọng Các hệ thống thông minh liên quan đến lĩnhvực này ngày càng phát triển như Robốt, máy bay không người lái, các hệ thống giámsát giao thông thông minh, các hệ thống nhận dạng trong y học Tuy nhiên vẫn cònrất nhiều vấn đề cần giải quyết - và cần cải tiến, trong các hệ thống như hệ thống nhậndạng mặt người, phân lớp và nhận dạng đối tượng, nhận dạng chữ viết tay, hay trongcác lĩnh vực khác như y học, sinh học Việc tìm cách cải thiện các cách thức hệ thốngphân lớp và nhận dạng vào các ứng dụng quan trọng đó luôn luôn cần, nó góp phầnvào phát triển kinh tế, tăng hiệu quả công việc và giúp đỡ con người thực hiện đượccác công việc khó khăn và phức tạp

Đối với các hệ thống phân lớp và nhận dạng với lượng thông tin khổng lồ đểthực hiện tốt trên phần dữ liệu lớn này đòi hỏi phải có những kỹ thuật phân lớp vànhận dạng phải thực hiện một vừa chóng vừa chính xác thì mới đáp ứng được yêu cầucho ứng dụng ngày nay

Xuất phát từ những lý do trên mà tôi đã chọn đề tài: “Phân lớp ảnh sử dụng kỹthuật MDS kết hợp SVM”

2 Mục tiêu nghiên cứu:

 Tìm hiểu các kỹ thuật áp dụng trong phân lớp và nhận dạng: MDS-SVM, SVM

PCA- Xây dựng chương trình mô phỏng để lấy kết quả hoạt động các kỹ thuật trên

 Đánh giá và kết luận hiệu quả và hiệu năng làm việc của các kỹ thuật

 Xây dựng mô hình hệ thống phân lớp và nhận dạng của các phương pháp trên ápdụng vào phân lớp nhận dạng mặt người

3 Đối tượng và phạm vi nghiên cứu:

a Đối tượng nghiên cứu:

 Xử lý ảnh

 Lý thuyết nhận dạng

 Các kỹ thuật loại bỏ không gian chứa ít thông tin và nhận dạng như: PCA, MDS, SVM

b Phạm vi nghiên cứu:

 Luận văn chủ yếu nghiên cứu tập trung vào phân lớp ảnh mặt người

 Tìm hiểu phân lớp dữ liệu ảnh các đối tượng ảnh khác nhau

 Tìm ra thông số đánh giá hiệu năng các kỹ thuật áp dụng trong hệ thống phân lớp ảnh

4 Phương pháp nghiên cứu

Nghiên cứu, tìm hiểu các phương pháp kỹ thuật áp dụng vào bài toán phân lớp,tìm hiểu cách thức hoạt động của mô hình nhận dạng và các kỹ thuật hoạt động

Các phương pháp đã thực hiện để đạt được mục tiêu nghiên cứu:

a Phương pháp thu thập thông tin:

Tìm kiếm dữ liệu mẫu phục vụ cho hệ thống phân lớp ảnh

Tìm kiếm và tham khảo các thông tin về hệ thống từ các nguồn khác nhau đểphục vụ đối chiếu về thông số hoạt động của hệ thống

b Phương pháp so sánh:

Tổng hợp và đối chiếu các tài liệu thu được để đưa ra cái nhìn tổng quan nhất

về hiệu quả và hiệu năng các kỹ thuật áp dụng vào phân lớp ảnh

c Phương pháp phân tích:

Phân tích về cách trích xuất và phân lớp dữ liệu ảnh của các kỹ thuật

Phân tích các kỹ thuật toán học được sử dụng cho các kỹ thuật

d Phương pháp chuyên gia:

Tham vấn các chuyên gia về lĩnh vực này nhằm cũng cố và hoàn thiện nội dungcần nghiên cứu

e Phương pháp thực nghiệm:

Dựa trên các kỹ thuật đã tìm hiểu, xây dựng chương trình mô phỏng thựcnghiệm để có kết quả về các thông số kỹ thuật cần quan tâm như thời gian thựchiện hệ thống, độ chính xác và sai lệch của các kỹ thuật từ đó có đánh giá vềhiệu quả và hiệu năng của các kỹ thuật khi sử dụng vào bài toán phân lớp ảnh

5 Kết quả đạt được:

 Phân tích được quy trình xử lý ảnh và nhận dạng

 Phân tích và xây dựng quy trình hoạt động của phương pháp MDS kết hợp

với SVM để cho kết quả thực nghiệm.

 Phân tích và xây dựng quy trình hoạt động của phương pháp PCA kết hợp với SVM để cho kết quả thực nghiệm

 So sánh đánh giá kết quả của 2 phương pháp MDS&SVM và PCA&SVM

 Kiểm tra mức độ chính xác nhận dạng mặt người bằng phương pháp MDS kết hợp SVM

6 Ý nghĩa khoa học và thực tiễn của luận văn

 Về mặt lý thuyết: Luận văn đã chứng tỏ rằng phương pháp MDS kết hợp

SVM có nhiều ưu điểm hơn đối với phương pháp PCA kết hợp SVM Mộttrong những tối ưu cơ bản của phương pháp MDS là giảm chiều của dữ liệutuy nhiên không làm mất nhiều thông tin như phương pháp PCA

 Về mặt thực tiễn: Đây là một phương pháp có ứng dụng phổ biến trong rất

nhiều ngành Cách hoạt động của hệ thống đơn giản phù hợp cho việc càiđặt ở nhiều hệ thống

7 Cấu trúc luận văn

Luận văn được chia làm bố cục 3 phần:

Phần mở đầu: Nêu lên lý do chọn đề tài, mục tiêu nghiên cứu, đối tượng và phạm vi nghiên cứu, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễncủa luận văn

Phần nội dung: Có cấu trúc 3 chương

 Chương 1: Khái quát về xử lý ảnh, tổng quan về các kỹ thuật phân lớp ảnh

và nhận dạng Chương này giới thiệu về bài toán phân lớp và nhận dạng, giớithiệu các kỹ thuật tiếp cận trong phân lớp như SVM, PCA, PCA-MDS Xácđịnh phạm vi thực hiện đề tài cũng như giới thiệu mô hình hệ thống phân lớpPCA kết hợp MDS

 Chương 2: Giới thiệu về kỹ thuật MDS, MDS kết hợp SVM, xây dựng mô

hình phân lớp MDS-SVM, mô tả hoạt động của hệ thống phân lớp cũng nhưlưu đồ giải thuật của hệ thống

 Chương 3: Cài đặt và chạy chương trình thử nghiệm, đưa ra các thông số mô

phỏng, giới thiệu giao diện chương trình Thể hiện kết quả mô phỏng các

phương pháp PCA-SVM và MDS-SVM, so sánh đánh giá kết quả của haiphương pháp này bằng sơ đồ Kiểm tra độ chính xác của phương pháp MDS-SVM sử dụng cho việc nhận dạng khuôn mặt

Phần kết luận: Đánh giá những vấn đề luận văn đã làm được, những thách thức chưa giải quyết được và hướng phát triển của đề tài

PHẦN NỘI DUNG

CHƯƠNG I: TỔNG QUAN VỀ PHÂN LỚP VÀ NHẬN

DẠNG

1 Giới thiệu về xử lý ảnh:

Hình 1.1: Quá trình xử lý ảnh.

Xử lý ảnh là một trong những mảng quan trọng nhất trong kỹ thuật thị giácmáy tính, là tiền đề cho nhiều nghiên cứu thuộc lĩnh vực này Hai nhiệm vụ cơ bảncủa quá trình xử lý ảnh là nâng cao chất lượng thông tin hình ảnh và xử lý số liệucung cấp cho các quá trình khác trong đó có việc ứng dụng thị giác và điều khiển.Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc mộtkết luận

Quá trình bắt đầu từ việc thu nhận ảnh nguồn (từ các thiết bị thu nhận ảnh dạng

số hoặc tương tự) gửi đến máy tính Dữ liệu ảnh được lưu trữ ở định dạng phù hợp vớiquá trình xử lý Người lập trình sẽ tác động các thuật toán tương ứng lên dữ liệu ảnhnhằm thay đổi cấu trúc ảnh phù hợp với các ứng dụng khác nhau

Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặctrưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trongkhông gian và nó có thể xem như một hàm n biến P(c1, c2, , cn) Do đó, ảnh trong xử

lý ảnh có thể xem như vector n chiều

1.1 Một số khái niệm

 Điểm ảnh (Picture Element)

Điểm ảnh (Pixel): là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc

màu nhất định Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợpsao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu) củaảnh số gần như ảnh thật Mỗi phần tử trong ma trận được gọi là một phần tử ảnh

 Mức xám của ảnh

Mức xám: Là kết quả của sự biến đổi tương ứng 1 giá trị độ sáng của 1 điểm

ảnh với 1 giá trị nguyên dương Thông thường nó được xác định trong [0, 255] tuỳthuộc vào giá trị mà mỗi điểm ảnh được biểu diễn

Các thang giá trị mức xám thông thường: 16, 32, 64, 128, 256 (Mức 256 là mứcphổ dụng Lý do: từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám Mứcxám dùng 1 byte biểu diễn: 28 = 256 mức, tức là từ 0 đến 255)

 Độ phân giải của ảnh

Định nghĩa: Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn

định trên một ảnh số được hiển thị

Theo định nghĩa, khoảng cách giữa các điểm ảnh phải được chọn sao cho mắtngười vẫn thấy được sự liên tục của ảnh Việc lựa chọn khoảng cách thích hợp tạo nênmột mật độ phân bổ, đó chính là độ phân giải và được phân bố theo trục x và y trongkhông gian hai chiều

Ví dụ: Độ phân giải của ảnh trên màn hình CGA (Color Graphic Adaptor) làmột lưới điểm theo chiều ngang màn hình: 320 điểm chiều dọc * 200 điểm ảnh(320*200) Rõ ràng, cùng màn hình CGA 12” ta nhận thấy mịn hơn màn hình CGA17” độ phân giải 320*200 Lý do: cùng một mật độ (độ phân giải) nhưng diện tích mànhình rộng hơn thì độ mịn (liên tục của các điểm) kém hơn

 Các cách phân loại ảnh

Ảnh nhị phân: Giá trị xám của tất cả các điểm ảnh chỉ nhận giá trị 1 hoặc 0

như vậy mỗi điểm ảnh trong ảnh nhị phân được biểu diễn bởi 1 bit

Ảnh xám: Giá trị xám nằm trong [0, 255] như vậy mỗi điểm ảnh trong ảnh nhị

phân được biểu diễn bởi 1 byte

Ảnh màu:

Hệ màu RGB: Một pixel được biểu diễn bằng 3 giá trị (R, G, B) trong đó R,

G, B là một giá trị xám và được biểu biểu diễn bằng 1 byte Khi đó ta có mộtảnh 24 bits P(x, y) = (R, G, B)

Hệ màu CMY: là phần bù của hệ màu RGB (C, M, Y) = (1, 1, 1) - (R, G, B)Hay C+R=M+G=Y+B=1 => Hệ màu này thường được dùng trong máy in

Hệ màu CMYK: trong đó K là độ đậm nhạt của màu: K= min(C, M, Y) P(x,y) = (C-K, M-K, V-K, K)

 Chỉnh mức xám

Nhằm khắc phục tính không đồng đều của hệ thống gây ra Thông thường có 2hướng tiếp cận:

Giảm số mức xám: Thực hiện bằng cách nhóm các mức xám gần nhau thành một

bó Trường hợp chỉ có 2 mức xám thì chính là chuyển về ảnh đen trắng Ứng dụng: in ảnh màu ra máy in đen trắng

Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian bằng kỹ thuật nội suy Kỹ thuật này nhằm tăng cường độ mịn cho ảnh

 Nhận dạng

Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân loại và phânnhóm các mẫu là những vấn đề quan trọng trong thị giác máy, được ứng dụng trongnhiều ngành khoa học khác nhau Tuy nhiên, một câu hỏi đặt ra là: mẫu (pattern) là gì?Watanabe, một trong những người đi đầu trong lĩnh vực này đã định nghĩa: “Ngược lạivới hỗn loạn (chaos), mẫu là một thực thể (entity), được xác định một cách ang áng(vaguely defined) và có thể gán cho nó một tên gọi nào đó” Ví dụ mẫu có thể là ảnhcủa vân tay, ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặcmột ký đồ tín hiệu tiếng nói Khi biết một mẫu nào đó, để nhận dạng hoặc phân loạimẫu đó có thể:

Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân tích phânbiệt (discriminant analyis), trong đó mẫu đầu vào được định danh như một thành phầncủa một lớp đã xác định

Hoặc phân loại không có mẫu (unsupervised classification hay clustering)

trong đó các mẫu được gán vào các lớp khác nhau dựa trên một tiêu chuẩn đồng dạngnào đó Các lớp này cho đến thời điểm phân loại vẫn chưa biết hay chưa được địnhdanh

Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ

để phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếpcận khác nhau Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhậndạng và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lai(hybrid system) bao gồm nhiều mô hình kết hợp

Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trongcuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu

Dữ liệu vào Thuật toán phân lớp hoạt động (SVM)

1.2 Tổng quan về phân lớp và nhận dạng:

Phân loại (hay phân lớp) là một tiến trình xử lý nhằm xếp các mẫu dữ liệu haycác đối tượng vào một trong các lớp đã được định nghĩa trước Các mẫu dữ liệu haycác đối tượng được xếp về các lớp dựa vào giá trị của các thuộc tính (attributes) chomột mẫu dữ liệu hay đối tượng Sau khi đã xếp tất cả các đối tượng đã biết trước vàocác lớp tương ứng, lúc này mỗi lớp được đặc trưng bởi tập các thuộc tính của các đốitượng chứa trong lớp đó

Các thuật toán phân loại tiêu biểu bao gồm như mạng neural, cây quyết định,suy luận quy nạp, mạng Beyesian, Support Vector Machine… Tất cả các cách tiếp cậnnày xây dựng nên những mô hình đều có khả năng phân loại cho một mẫu mới chưabiết dựa vào những mẫu tương tự đã được học Bài toán phân loại có thể xử lý thôngtin được thu thập từ mọi lĩnh vực hoạt động của con người và thế giới tự nhiên đượcbiểu diễn dưới dạng các bảng Bảng này bao gồm các đối tượng và các thuộc tính Cácphần tử trong bảng là các giá trị xác định các thuộc tính (attributes hay features) củacác đối tượng Trong đó số cột chính là số thuộc tính của các đối tượng, mỗi cột là mộtthuộc tính và số dòng chính là số đối tượng chứa trong dữ liệu này Mọi dữ liệu đượcbiểu diễn dưới các dạng khác có thể được chuyển thành dạng bảng như trên để thựchiện quá trình phân loại

1.2.1 Bài toán về phân loại

Một bài toán phân loại và nhận dạng bao gồm 2 bước sau:

Bước 1: Huấn luyện

Mục đích của bước này là xây dựng một mô hình xác định một tập các lớp dữliệu Mô hình này được xây dựng bằng cách phân tích các bộ dữ liệu của một cơ sở dữliệu, mỗi bộ dữ liệu được xác định bởi giá trị của các thuộc tính Giả sử mỗi bộ dữ liệu

đã thuộc về một trong các lớp đã được định nghĩa trước, điều này được xác định bởimột trong các thuộc tính, gọi là thuộc tính phân loại Trong ngữ cảnh của bài toán phânloại, mỗi bộ dữ liệu được xem như là một mẫu, một ví dụ, hay một đối tượng Những

bộ dữ liệu được phân tích để xây dựng mô hình phân loại được lấy từ trong tập dữ liệuhọc hay dữ liệu huấn luyện (training data set) Những bộ dữ liệu riêng lẻ tạo thành tập

dữ liệu huấn luyện còn gọi là những mẫu huấn luyện (training samples) và được chọnngẫu nhiên từ một kho các mẫu

Bước 2: Kiểm tra và đánh giá, bước này sử dụng mô hình phân lớp đã được xây

dựng ở bước 1 vào việc phân lớp

Đầu tiên, đánh giá độ chính xác của mô hình hay bộ phân lớp này, bằng cách sửdụng một tập các mẫu đã được phân lớp để thử (test) gọi là bộ thử (test set) Nhữngmẫu này được chọn ngẫu nhiên và độc lập với các mẫu đã được học ở bước 1 gọi làmẫu thử (test sample) Độ chính xác của một mô hình phân lớp dựa trên bộ thử là tỷ lệnhững mẫu thử được phân lớp đúng bằng mô hình phân lớp đó Nghĩa là với mỗi mẫuthử, so sánh lớp đúng mà mẫu thử đó thuộc về với lớp mà mô hình phân lớp này dựđoán cho mẫu thử đó

1.2.2.1 Cây quyết định

Một cây quyết định là một cấu trúc cây, trong đó mỗi node trong biểu thị chomột phép phân nhánh tương ứng cho một thuộc tính, mỗi nhánh biểu thị cho một kếtquả của một phép thử, các node lá biểu thị cho lớp hoặc các phân bố lớp Node trêncùng trong một cây được gọi là gốc Để phân lớp một mẫu chưa biết, những giá trịthuộc tính của mẫu đó được thử ngược lại trên cây quyết định Một đường dẫn từ gốcđến một node lá là cơ sở cho việc dự đoán lớp của một mẫu Cây quyết định có thể dễdàng chuyển đổi sang một tập các luật phân lớp Cơ sở toán học của cây quyết định là

thuật toán tham lam, thuật toán này đã xây dựng cây quyết định đệ quy từ trên xuốngdưới, theo phương pháp chia để trị.

1.2.2.2 Mạng Bayes

Bayesian là phương pháp phân lớp dựa vào thống kê Ta có thể dự đoán xácsuất của các lớp trong tập dữ liệu, dựa vào xác suất này có thể xếp các mẫu vào các lớpriêng biệt Thuật toán phân lớp Bayesian giả thiết rằng giá trị các thuộc tính của mộtlớp độc lập với giá trị của các thuộc tính khác, giả thiết này còn được gọi là lớp độc lập

có điều kiện, nó làm đơn giản các tính toán sau này Mạng Bayesian là một đồ thị, trên

đồ thị cho phép biểu diễn mối quan hệ giữa các thuộc tính

1.2.2.3 Kỹ thuật K người láng giềng gần nhất:

Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phânlớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đốitượng trong tập huấn luyện Để phân lớp cho một điểm dữ liệu mới x, trước hết bộphân lớp sẽ tính khoảng cách từ điểm dữ liệu trong tập huấn luyện Qua đó tìm đượctập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất Ví dụ nếucác dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụngkhoảng cách Euclide để tính khoảng cách giữa các điểm dữ liệu với nhau Sau khi xácđịnh được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếmđại đa số trong tập N(x, D, k) Mặc dù rất đơn giản, nhưng thuật toán K người lánggiềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế

1.2.2.4 Support Vector Machine

SVM là một phương pháp mới để phân lớp dữ liệu Nó dễ sử dụng hơn mạngneural, tuy nhiên nếu không sử dụng nó chính xác thì dễ bị bỏ qua một số bước đơngiản nhưng cần thiết, dẫn đến kết quả không được thỏa mãn Mục đích của phươngpháp SVM là phát sinh ra một mô hình từ tập mẫu học, mô hình này có khả năng dựđoán lớp cho các mẫu thử SVM tìm ra một hàm quyết định phi tưyến trong tập mẫuhọc bằng cách ánh xạ hoàn toàn các mẫu học vào một không gian đặc trưng kích thướclớn có thể phân lớp tuyến tính và phân lớp dữ liệu trong không gian này bằng cách cựcđại khoảng cách lề (geometric margin) và cực tiểu lỗi học cùng một lúc Vấn đề tối ưuchủ yếu là tìm mặt phân cách phân chia dữ liệu sao cho khoảng cách mặt phẳng nàyđến 2 lớp dữ liệu là cực đại

Hình 1.3: Quá trình nhận dạng.

Đối với bài toán nhận dạng đối tượng được dựa vào kết quả của bài toán phân lớp

Để thực hiện bài toán nhận dạng chúng ta thực hiện các bước như sau:

Bước 1: Chuẩn bị dữ liệu mẫu để huấn luyện và dữ liệu nhận dạng.

Bước 2: Xử lý ảnh đầu vào (tiền xử lý).

Mục đích: Chuẩn hóa, khữ nhiễu và nâng cao chất lượng ảnh.

Mục đích của việc trích chọn đặc trưng là lựa chọn các thuộc tính của các mẫu

để xây dựng độ đo về sự khác biệt giữa các lớp mẫu Trích chọn đặc trưng đóng vai tròcực kỳ quan trọng trong một hệ thống nhận dạng Đặc trưng được trích chọn phải rút

gọn lại càng nhỏ càng tốt nhưng vẫn phải đảm bảo được thông tin của ảnh

a Dựa vào đặc trưng hình học:

Những đặc trưng hình học thường là những vị trí đặc biệt trên khuôn mặt nhưgóc của mắt, miệng…hoặc là hình dáng của các bộ phận trên khuôn mặt như mắt,miệng, lông mày…

b Dựa vào đặc trưng diện mạo:

Xác định những thay đổi trên khuôn mặt và được áp dụng trên toàn bộ bề mặtcủa bức ảnh hoặc một phần để trích ra các đặc trưng và phát hiện ra sự thay đổi củakhuôn mặt

Một số kỹ thuật:

+ Trích chọn đặc trưng wavelet Haar

+ Phương pháp PCA(Phân tích các thành phần chính )

+ Phương pháp MDS(Hướng tiếp cận dựa trên diện mạo)

Bước 4: Huấn luyện:

Chọn mô hình huấn luyện phù hợp như sử dụng một trong số các kỹ thuật phân lớp để huấn luyện ví dụ như SVM, mạng Nơron cho ra kết quả huấn luyện Đối với SVM sẽ cho ra các support vector của các lớp đối tượng

Bước 5: Nhận dạng:

Quá trình nhận dạng cũng tiến hành các bước tuần tự như huấn luyện, tuy nhiênđối tượng cần nhận dạng sau khi được trích chọn đặc trưng sẽ được sử dụng để phânlớp dữ liệu dựa vào kết quả huấn luyện đã thực hiện trước đó Kết quả cuối cùng là đốitượng sẽ thuộc về lớp của một trong số đối tượng được huấn luyện trước đó hoặckhông có đối tượng nào trong dữ liệu huấn luyện

1.2.4.1 Giới thiệu về kỹ thuật SVM

a Cở sở lý thuyết của SVM

SVM là phương pháp học do Vladimir N Vapnik đề xuất vào năm 1995, vàngày càng được sử dụng phổ biến trong nhiều lĩnh vực, đặc biệt là lĩnh vực phân loạimẫu và nhận dạng mẫu Đồng thời có nhiều tính năng ưu việt so với các phương pháp

cổ điển khác: dễ dàng xử lý, xử lý với tính ổn định cao trên dữ liệu phức tạp, có thể có

số chiều lớn và quan trọng hơn cả là khả năng xử lý tổng quát

b Các khái niệm nền tảng

Đường bao tổng quát cho một hệ máy học:

Khảo sát bao gồm l mẫu quan sát Mỗi quan sát gồm một cặp: một vector xi ∈

Rn, i = 1,…, l với một giá trị xác định y i mà giá trị của nó xuất phát từ việc gán chủ

quan từ người tổ chức dữ liệu Gọi P(x,y) là hàm phân phối xác xuất giữa x và y và

chưa được xác định tường minh Cách tổ chức trên đây có tính tổng quát cao hơn sovới việc kết hợp cứng giữa y với mỗi x, điều này cho phép tính được phân phối của ydựa vào dữ liệu x cho trước Tuy nhiên, sau phần này, ta thừa nhận cố định y với x chotrước

Hệ máy học có nhiệm vụ học ánh xạ xi yi , được định nghĩa từ một tập hợp

các ánh xạ x f (x,α ) , trong đó hàm f (x,α ) được gán nhãn bởi các tham số α (α có

thể hiệu chỉnh được trong quá trình xử lý trên tập học) Hệ máy học có thể xem như là

một hệ quyết định Với dữ liệu đầu vào là x cho trước, chọn ra một α thích hợp, và kết

xuất sẽ là f (x, α) Việc chọn α có thể có nhiều cách khác nhau, ở đây chúng ta sẽ tiếp

cận theo phương pháp máy học

Lỗi thử nghiệm đối với một hệ máy học đã được huấn luyện:

R (α )=1

2∫ |y−f ( x , α )|dP(x , y ) (1.1)

Nếu tồn tại hàm mật độ p(x,y) thì dP(x,y) có thể được viết thành dP(x,y) =

P(x,y)dxdy Đây là cách viết khác của trung bình lỗi, nhưng trong trường hợp đã ước

lượng được P(x,y) thì cách viết này sẽ không còn ý nghĩa nữa.

R(α) được gọi là lỗi kì vọng, hay lỗi Ở đây ta gọi nó là lỗi thực Lỗi huấn luyện

(thực nghiệm) R emp (α )được định nghĩa là độ đo tỷ lệ lỗi trung bình xảy ra trên tập học(Ở đây chỉ chú trọng vào trường hợp dữ liệu là hữu hạn):

Remp(α) là một giá trị tường minh tương ứng với một hệ số α riêng từ dữ liệu

huấn luyện riêng {xi, yi}

Đại lượng 12∨y i−f(x i , α)∨¿ được gọi là độ lệch Trong trường hợp này, nó chỉ

có thể lấy giá trị 0 và 1 Chọn η sao cho 0 ≤ η ≤ 1 và cho độ lệch nhận các giá trị này, với xác suất 1-η, ta có:

R (α )≤ R emp (α )+√h(log(2l h )+1)−log ⁡(η /4)

l

(1.3)

h là một số nguyên không âm và còn được gọi là chiều VC (Vapnik Chervonenkis) (VC-dimension) Gọi vế phải của (1.3) là đường bao lỗi hay biên lỗi.

Các thuật ngữ trước đây của một số nhà nghiên cứu: (Guyon et al., 1992) gọi là lỗiđược thừa nhận nhưng cách gọi này có thể gây ra một số nhầm lẫn, vì nó thực sự chỉ làđường bao trên miền lỗi chứ không phải là giá trị chính xác của lỗi, và nó chỉ đúng ởmột xác suất nào đó nên thật sự là không đảm bảo được độ đo này là chính xác Thuậtngữ thứ hai là độ tin cậy Vapnik Chervonenkis

c Chiều VC (VC-dimension)

Chiều VC là một thuộc tính của tập hàm {f(α)} (ta dùng α như là một tập các

tham số có đặc điểm chung sau: Cứ chọn ra một hệ số α thì sẽ xác định được một hàmriêng tương ứng), và dùng chiều VC chúng ta có thể biểu diễn các dạng biến thể khácnhau của hàm f có thể có Ở đây chỉ khảo sát các loại hàm cho trường hợp giải quyết

bài toán nhận dạng mẫu hai lớp, như vậy f(α) ∈ {-1,1} ∀x, α Cho trước tập quan sát

gồm l (mẫu), có thể gán nhãn theo 2l cách, và với mỗi cách gán nhãn, có thể tìm được

một thành viên của tập { f(α)} gán chính xác các nhãn này, ta gọi tập các điểm như vậy

bị shatter (phân cách) bởi tập hàm này Chiều VC cho tập hàm {f(α)} được định nghĩa

là số điểm huấn luyện lớn nhất có thể bị phân tách bởi {f(α)} Chú ý rằng, nếu chiều

VC là h khi đó tồn tại ít nhất một tập h điểm có thể bị phân cách, nhưng không chắcmọi tập h điểm có thể bị phân cách

d Phân hoạch tập dữ liệu bằng các siêu mặt có hướng

Giả sử không gian dữ liệu là R 2, và tập hàm { f(α)} là các đường thẳng có

hướng, như vậy với một đường cho trước, mọi điểm mẫu trên một mặt của đường sẽ

được gán nhãn bằng 1, và các điểm thuộc về mặt khác sẽ được gán nhãn -1 Hướng

mũi tên trong Hình 1.4 xác định mặt của đường thẳng mà các điểm thuộc về mặt đó sẽ

được gán nhãn 1 Có thể tìm được ba điểm phân cách bởi tập các hàm này, nhưng

không thể luôn luôn tìm được mặt phân cách với bốn điểm Do đó chiều VC cho cácđường có định hướng trong không gian hai chiều ( R2) là 3

Hình 1.4: Ba điểm trong R2.

0.20.40.60.81.01.21.4

Hình 1.5: Độ tin cậy VC là hàm đơn điệu theo h.

h/l = số chiều VC /số mẫu dữ liệu

Xét các siêu mặt phẳng trong không gian n chiều (R n).

Định lý 1: Khảo sát tập mẫu gồm m điểm trong không gian Rn Chọn một điểm

bất kỳ làm điểm tọa độ gốc Khi đó m điểm này có thể bị phân rã bằng các siêu mặt

(đường thẳng có định hướng) nếu và chỉ nếu vị trí các vector của các điểm đang đề cập

là độc lập tuyến tính (“Mangasarian, 1969”)

Hệ quả: VC-dimension cho các siêu mặt có hướng trong Rn là n+1, vì ta luôn

có thể chọn n+1 điểm dữ liệu, và sau đó chọn một điểm bất kì trong số đó làm điểmgốc, để vị trí các vector của các điểm đang đề cập là độc lập tuyến tính

Cực tiểu đường bao lỗi trên cơ sở cực tiểu chiều VC

Hình 1.5: Cho thấy nhóm biểu thức thứ hai bên vế phải của phương trình (1.3)

√h(log(2 l h )+1)−log ⁡(η/4)

l

biến thiên theo số chiều h, bằng cách chọn độ tin cậy 95% (η = 0.05), tập mẫu huấn

luyện l =10,000 (mẫu) Chiều VC là hàm tăng đều theo h Điều này đúng với bất kỳ

giá trị của l

e SVM tuyến tính

Trường hợp dữ liệu có thể phân cách được

Bắt đầu với trường hợp đơn giản nhất: máy học được huấn luyện trên dữ liệu cóthể phân loại tuyến tính Gán nhãn dữ liệu huấn luyện {xi, yi }, i = 1, , l, y i ∈ {-1,1}, xi

∈ R d Giả sử có các siêu mặt phẳng phân loại mẫu dương với mẫu âm (gọi là “siêu mặt

phân cách”) Điểm x nằm trên siêu mặt thỏa phương trình w.x + b = 0, trong đó w là

pháp tuyến của siêu mặt, |b| / ||w|| là khoảng cách từ siêu mặt đến gốc toạ độ, và ||w||

độ lớn (Euclide) của w Đặt (d+), (d-) là khoảng cách ngắn nhất từ siêu mặt phân cách

đến mẫu dương (âm) gần nhất Định nghĩa “bờ” (margin) của siêu mặt phân cách (kí

hiệu r), là (d+) + (d-) Với trường hợp tập mẫu có thể phân loại tuyến tính, thuật toán

SVM chỉ đơn giản là tìm siêu mặt có khoảng cách bờ là cực đại Các mô tả trên đâyđược công thức hoá như sau: giả sử mọi điểm trong tập học thỏa các ràng buộc:

`

là các vector hỗ trợ; đó là các điểm được bao bằng các hình tròn trong Hình 1.6.

Các support vector chính là các điểm được bao bằng viền tròn

Một cách để giải quyết bài toán là dùng hàm Largange Có hai lý do cho điều

này

Thứ nhất là ràng buộc (1.6) sẽ được thế bằng ràng buộc trên hệ số nhânLagrange, để dễ làm việc hơn Thứ hai là dữ liệu huấn luyện sẽ chỉ xuất hiện dướidạng phép nhân vô hướng giữa các vector Điều này cho phép tổng quát hoá chotrường hợp phi tuyến

Đưa ra các hệ số nhân Lagrange dương αi , i = 1, , l và α i > 0, cho các ràng buộcbất đẳng thức (1.6) (Nhớ rằng với ràng buộc dạng ci ≥ 0, phương trình ràng buộc đượcnhân với hệ số nhân Lagrange dương và bị trừ khỏi hàm mục tiêu Với các ràng buộcđẳng thức, hệ số nhân Lagrange không bị ràng buộc) Khi đó hàm Lagrange có dạngnhư sau:

Ta phải cực tiểu Lp theo (w), (b), đồng thời đòi hỏi đạo hàm của Lp triệt tiêu

với mọi αi, với điều kiện αi ≥ 0 (gọi tập ràng buộc này là C1) Hay giải bài toán đối

ngẫu đó là cực đại Lp với điều kiện đạo hàm của Lp triệt tiêu với w, b và cũng với ràng

buộc αi ≥ 0 (gọi tập ràng buộc này là C2)

Đạo hàm Lp triệt tiêu với w và b ta có các điều kiện:

Như vậy sau khi giải bài toán tối ưu sẽ tương đương với việc giải bài toán đốingẫu sau:

Điều kiện tối ưu Karush-Kuhn-Tucker

Điều kiện Karush-Kuhn-Tucker (KKT) có vai trò quan trọng đối với bài toántối ưu ràng buộc Với bài toán trên, điều kiện KKT có thể phát biểu:

kiện KKT.

Vector w được tính bằng cách huấn luyện, nhưng b thì không Tuy nhiên b dễdàng tính được khi sử dụng các điều kiện KKT bổ sung, công thức (1.15), bằng việcchọn i có αi ≠ 0 và tính b (lấy giá trị trung bình của b từ các phương trình trên)

Sau khi giải bài toán đối ngẫu ( **) ta thu được các giá trị αi tương ứng với các

mẫu (x i ,y i) khi đó, một mẫu x sẽ được phân lớp theo hàm quyết định:

f ( x )=sign(w T x +b)=sign(α∑i ≠0

α i x i y i x +b) (***)

Trường hợp dữ liệu không thể phân cách được:

Thuật toán trên chỉ phù hợp cho trường hợp tập dữ liệu học có thể phân cách

được, khi áp dụng cho dữ liệu không thể phân cách tuyến tính, sẽ không nhận được lời

giải khả thi do hàm Lagrange lớn Để mở rộng ý tưởng này cho trường hợp dữ liệu

không thể phân cách ta đưa thêm các biến slack (chùng, lỏng) dương ξi ≥ 0, i = 1 , …,

l vào các ràng buộc như sau:

từ việc cực tiểu ||w||2/2 sang việc cực tiểu ||w||2/2 + C(Σi ξi ) , trong đó C là tham số do

người dùng chọn, và C càng lớn thì tỉ lệ lỗi sẽ càng cao Khi đó hàm Lagrange trở

Hình 1.7: Siêu mặt phân cách tuyến tính cho trường hợp không phân cách được.

Với μi là các hệ số nhân Lagrange đảm bảo ξi dương Khi đó điều kiện KKT là:

Có thể dùng các điều kiện bổ sung KKT, công thức (1.30) và (1.31), để xác

định ngưỡng b Công thức (1.27) và (1.31) cho thấy rằng ξi = 0 nếu αi < C Do đó có thể lấy điểm huấn luyện bất kỳ thỏa 0 < αi < C để dùng công thức (1.27) (với ξi =0) để tính b.

Hình 1.8: Chuyển từ không gian ít chiều sang không gian nhiều chiều.

g SVM phi tuyến

Làm thế nào các phương thức đã khảo sát trên có thể được tổng quát hoá chotrường hợp hàm quyết định không phải là hàm tuyến tính đối với dữ liệu? Ta thấy rằng

dữ liệu trong bài toán huấn luyện, công thức (1.19) – (1.21), xuất hiện dưới dạng tích

vô hướng xi⋅xj Giả sử ta đã ánh xạ dữ liệu sang không gian Euclide Η khác (số chiều

có thể vô hạn) dùng hàm ánh xạ Φ:

Khi đó thuật toán huấn luyện chỉ phụ thuộc vào dữ liệu qua tích vô hướng trong

Η, tức là hàm có dạng Φ(xi)⋅Φ(xj) Nếu có một hàm xử lý chính K (hàm Kernel) mà

K(xi.xj) = Φ(xi)⋅Φ(xj) , ta sẽ chỉ cần dùng hàm K trong thuật toán huấn luyện, mà

không cần biết dạng tường minh của Φ là gì? Chẳng hạn:

K(xi.xj)=e− ¿ ∨x i−x j∨ ¿2/2 σ 2

Điều kiện để xác định được hàm nhân K(x,y) = Φ(xi)⋅Φ(xj) thì phải thỏa mãn

điều kiện Mercer Mercer đưa ra điều kiện cần và đủ là: phiếm hàm

∫K ( x , y ) g ( x ) g ( y ) d ( x ) d ( y)

Xác định không âm trên các hàm g bình phương khả tích.

Trong ví dụ này, Η có số chiều vô hạn, vì thế không dễ làm việc với Φ một cáchtường minh Tuy nhiên, nếu thay xi.xj bằng K(xi.xj) trong thuật toán huấn luyện, thuậttoán sẽ tạo ra vector hỗ trợ trong không gian số chiều vô hạn, hơn nữa thời gian huấnluyện tương đương thời gian huấn luyện trên dữ liệu chưa được ánh xạ Mọi xem xét

trong các phần trước vẫn thỏa, vì ta vẫn làm việc với trường hợp phân cách tuyến tính,nhưng trong một không gian khác.

Sử dụng hệ thống này như thế nào? Ta cần tìm w, trong hình(1.8) Nhưng khithử nghiệm, máy được sử dụng bằng cách tính tích vô hướng của mẫu thử nghiệm xvới w, hay cụ thể hơn tính dấu của

Như vậy bài toán đối ngẫu trong trường hợp dữ liệu phi tuyến được xác địnhtương tư như dữ liệu tuyến tính tách được:

rằng, ngoài việc w nằm trên Η ra, nói chung không có vector nào trong Λ, qua ánh xạ

Φ, thành w Nếu có, f(x) trong công thức (1.35) có thể được tính bằng một bước, bỏ qua việc tính tổng (và tạo ra vector hỗ trợ tương ứng nhanh hơn Ns lần) Dễ dàng tìm được dạng hàm xử lý chính (Kernel) (chẳng hạn hàm phép nhân vô hướng xi trong Λ)

để thuật toán huấn luyện và lời giải tìm được là độc lập với số chiều của cả Λ và Η

Giả sử dữ liệu là các vector trong không gian R 2, và chọn K( x i )( xj ) = (xi xj) 2

Khi đó dễ dàng tìm được không gian Η, và ánh xạ Φ từ R 2 vào Η, để (x y)2 =

Với dữ liệu trong Λ đã xác định trong hình vuông [-1,1] x [-1,1] ∈ R 2, ảnh của

Φ được biểu diễn trong Hình 1.9 Hình này cũng cho thấy rằng ảnh của Φ có thể nằmtrong không gian có số chiều lớn hơn

Hình 1.9: Mặt phẳng [-1,1] X [-1,1] ∈ R2 thành mặt cong trong R3 .

Chú ý rằng hàm ánh xạ Φ và không gian Η là không duy nhất với một hàm xử

lý chính (kernel) cho trước Ta có thể chọn Η = R 3 và

Sau khi xác định được hàm nhân K thì việc giải bài toán đối ngẫu (1.36) tương

tự như giải bài toán đối ngẫu của dữ liệu tuyến tính Kết quả phân lớp dữ liệu cũng dựa

vào hàm quyết định: f ( x )=sign(∑

i=1

N SV

α i y i K(x i x)+b)

h Các kỹ thuật cài đặt và phân lớp

 Thuật toán Chunking

 Thuật toán phân rã

 Thuật toán SMO (Sequential Minimal Optimization)

 Chiến lược OVO (One-vs-One)

Với N lớp, chúng ta phải xây dựng tất cả N(N-1)/2 máy phân lớp nhịphân, thông qua phương pháp bỏ phiếu để đánh giá kết quả phân lớp: lớp nào

có số phiếu nhiều nhất sẽ được chọn làm kết quả phân lớp

 Chiến lược OVR (One-vs-Rest)

Với N lớp, ta chỉ cần xây dựng đúng N máy phân lớp nhị phân, một máy

1

√ ¿ ( x 2 1 − x 22¿ ) ( 2x 1 xalignl ¿ 2 ¿ ¿ ¿¿ ) ¿

¿

¿

cho mỗi lớp Máy phân lớp thứ i sẽ được huấn luyện trên toàn bộ tập mẫu đểphân lớp i với các lớp còn lại

 Chiến lược phân cấp

Ý tưởng của chiến lược này dựa trên cấu trúc phân cấp, sử dụng cây nhịphân Nút gốc của cây là một máy phân lớp nhị phân chia toàn bộ các lớp thànhhai nhóm lớp, sau đó tùy đầu ra của máynày mà các nút con tiếp tục được chiađôi cho tới khi xuống đến nút lá

Giới hạn thứ hai là tốc độ và kích thước, cả trong huấn luyện và thử nghiệm

1.2.4.2 Giới thiệu về kỹ thuật PCA

Phân tích thành phần chính (Principal Component Analysis – PCA) là một

trong những phương pháp phân tích dữ liệu nhiều biến đơn giản nhất Nói một cáchngắn gọn, mục tiêu của PCA là tìm một không gian mới (với số chiều nhỏ hơn khônggian cũ) Các trục tọa độ trong không gian mới được xây dựng sao cho trên mỗi trục,

độ biến thiên của dữ liệu trên đó là lớn nhất có thể Một điểm nữa của PCA là các trụctọa độ trong không gian mới luôn đảm bảo trực giao đôi một với nhau, mặc dù trongkhông gian ban đầu, các trục có thể không trực giao.Về mặt ứng dụng của phươngpháp PCA là rất rộng trong công nghiệp, nông nghiệp, kinh tế, khoa học cơ bản… vớibảng số liệu mà các cột là các biến và các dòng là các cá thể, trên đó đo giá trị củabiến

Giả sử tập dữ liệu ban đầu trong không gian 3D, dữ liệu này sẽ được chiếu lêncác cặp trục tọa độ không gian 2D, theo hình 1.10 thì khi chiếu lên trục y, z ta thuđược kết quả có độ biến thiên cao nhất

Hình 1.10: Minh họa PCA tìm các trục tọa độ mới sao cho dữ liệu có độ biến thiên cao nhất.

Hình 1.11: Hình hiển thị dùng PCA giảm số chiều những vẫn đảm bảo được các thông tin quan trọng nhất.

a Thuật toán PCA để trích chọn đặc trưng:

Thuật toán

Khuôn mặt con người có rất nhiều nét để nhận biết, nếu như ta gặp lại một

người bạn sau một thời gian dài, ta có thể nhận ra ngay người đó dù những chi tiết cụ

thể trên mặt có thể thay đổi như da, mái tóc Ta nhận ra không phải vì nhớ đôi mắt,

hay mũi hay môi hay tóc, lông mày người đó mà ta nhận ra vì nhớ diện mạo của người

đó Tức là trên khuôn mặt tồn tại một nét tổng thể nào đó để có thể nhận diện, thuật

toán của ta bắt đầu từ ý tưởng này

Phân tích thành phần chính (Principal Component Analysis ) gọi tắt là PCA làthuật toán nhận dạng ảnh dựa trên những nét tổng thể của khuôn mặt, ta sẽ áp dụngthuật toán này để thực hiện công việc sau:

• Tìm các k vector riêng có giá trị lớn nhất của các khuôn mặt để sử dụng choSVM huấn luyện và kiểm tra

Ban đầu ta có một tập ảnh khuôn mặt gọi là tập ảnh huấn luyện (training set) Giả sử mỗi ảnh có kích thước M*N, ta coi mỗi bức ảnh này là một vector trongkhông gian M*N chiều Bây giờ mỗi khuôn mặt là một vector, ta thấy những vectornày không phân bố ngẫu nhiên trong không gian ảnh mà phân bố theo một quy luậttương đối nào đó, ta có thể nói những vector này nằm trong một không gian con gọi làkhông gian khuôn mặt Từ những vector trong tập huấn luyện, ta sẽ tìm một cơ sở trựcchuẩn cho không gian khuôn mặt Những vector thuộc cơ sở này có thể coi là nhữngvector mang những nét tổng thể đặc trưng về khuôn mặt

32

1]3 x 3

[ 12

33

−1245

x = 3 x

A Vλ(eigenvalue)eigenvalue) (eigenvalue)eigenvector)

Nếu v là một vector riêng của ATA và λ là trị riêng tương ứng, khi đó ta có:

Đặt L= ATA , tìm V là tập hợp các vector riêng của L, D là tập hợp các trị riêngtương ứng V bao gồm Q vector riêng ứng với những trị riêng lớn hơn một giá trị nào

đó hoặc ứng với Q trị riêng lớn nhất trong D

Ví dụ: Các vector riêng vi của ATA là

ui = Avi là tập các vector riêng hiệp phương sai của ATA

Ví dụ: ta tính được các ui và sau đó chuyển vào ma trận U (face space)

U =

u1 u2 u3 u1 u2 u3

ui = AVi

Hình 1.2: Ảnh gốc ban đầu chuyển sang eigenfaces.

Do đây là những vector riêng, mà nó lại có dạng khuôn mặt nên còn được gọi làEigenfaces E là ma trận M*N×Q, mỗi cột là một vector riêng

Chuẩn hóa các vector cột trong E (chia mỗi vector cho độ dài của vector đó) Bây giờ, ta có thể coi E là một cơ sở trực chuẩn của không gian khuôn mặt Như vậy các vector cột trong E đại diện cho các các ảnh đã được trích chọn đặctrưng bởi các Eigenfaces của các đối tượng Dữ liệu này sẽ là dữ liệu đầu vào sử dụngcho SVM sử dụng để huấn luyện và nhận dạng đối tượng

Hình 1.13: Sơ đồ hoạt động của hệ thống PCA và SVM.

1.2.4.3 Xây dựng mô hình kết hợp PCA-SVM

Mô hình sơ đồ kết hợp PCA-SVM được thể hiện trong sơ đồ hình 1.13 Môhình hệ thống hoạt động như sau:

Bước 1: Dữ liệu đầu vào được phân chia làm hai loại dữ liệu (dữ liệu huấnluyện, dữ liệu nhận dạng) Dữ liệu đầu vào được xử lý và chuẩn hóa bởi giai đoạn tiền

xử lý

Bước 2: Sau giai đoạn tiền xử lý đến giai đoạn trích chọn đặc trưng, ở đây ta sửdụng phương pháp PCA để trích chọn Như đã giới thiệu ở trên phương pháp PCA sẽtìm ra vector riêng và giá trị riêng của ảnh

Bước 3: Sau khi xác định số lượng trị riêng lớn nhất của ảnh cần sử dụng đểlàm đầu vào cho việc huấn luyện và ta chọn mô hình huấn luyện, tại đây ta sử dụng kỹthuật SVM để huấn luyện và kiểm tra Kết quả sau khi huấn luyện là các vector tựa củacác lớp dữ liệu đồng thời gán nhãn cho từng lớp

Bước 4: Đến giai đoạn kiểm tra ta cũng làm các bước tương tự như huấn luyện,đầu tiên ta cũng tiền xử lý để chuẩn hóa dữ liệu, tiếp đến là trích chọn đặc trưng củaảnh cần kiểm tra

Bước 5: Sau khi xác định được các đặc trưng là các giá trị riêng của ảnh cầnkiểm tra kết hợp với nhãn của ảnh để làm đầu vào cho kiểm tra dữ liệu Ta phải sửdụng kỹ thuật SVM giống như khi huấn luyện Ta sẽ dùng một trong các phương phápphân lớp để kiểm tra dữ liệu

Bước 6: Kết quả cuối cùng là thông tin cho ta biết ảnh cần kiểm tra thuộc lớpnào trong bộ dữ liệu mẫu ban đầu.