401
Ch¬ng 20
NHẬN DẠNG MẪU:
PHÂN LỚP VÀ ĐÁNH GIÁ
20.1. GIỚI THIỆU
Trong chương 18, chúng ta đã giới thiệu về nhận dạng mẫu thống kê và đã đề cập
đến việc tách và trích chọn các đối tượng từ một cảnh phức tạp. Chương 19 đã chỉ ra
các phương pháp xác định những đặc điểm của các đối tượng đó. Trong chương này,
chúng ta tiếp cận bài toán nhận biết các đối tượng bằng cách phân lớp chúng thành
từng nhóm. Có lẽ phải viết nhiều về chủ đề này và chúng ta chỉ có thể giới thiệu các
khái niệm cơ bản ở đây. Nếu muốn nghiên cứu đầy đủ hơn, độc giả nên tham khảo
tài liệu về chủ đề này (Phụ lục 2)
20.2. PHÂN LỚP
20.2.1. Chọn lọc đặc trưng
Nếu ta muốn một hệ thống phân biệt các loại đối tượng khác nhau, đầu tiên chúng
ta phải quyết định nên xác định những đặc điểm nào để tạo ra các tham số miêu tả.
Các đặc điểm riêng biệt cần xác định gọi là các đặc trưng của đối tượng và các giá trị
tham số kết quả gồm có vec tơ đặc trưng đối với từng đối tượng. Việc chọn lựa các
đặc trưng thích hợp là rất quan trọng, vì chỉ có chúng mới được sử dụng để nhận biết
đối tượng.
Có vài phương tiện phân tích để hướng dẫn chọn lựa các đặc trưng. Khả năng trực
giác thường xuyên chỉ đạo danh sách các đặc trưng có ích tiềm tàng. Các kỹ thuật
sắp xếp đặc trưng tính toán có liên quan đến số lượng các đặc trưng khác nhau. Điều
này cho phép lược bớt danh sách chỉ còn một vài đặc trưng tốt nhất.
Các đặc trưng tốt có bốn đặc điểm:
1. Sự phân biệt đối xử. Các đặc trưng phải nhận những giá trị khác nhau một cách
đáng kể đối với các đối tượng thuộc các lớp khác nhau. Ví dụ, đường kính là
dặc tính tốt trong ví dụ sắp xếp trái cây ở chương 18, vì nó nhận những giá trị
khác nhau đối với những quả sơ ri và những quả nho.
2. Tính tin cậy. Các đặc trưng phải nhận các giá trị giống nhau đối với mọi đối
tượng cùng lớp. Ví dụ, màu sắc có thể là đặc trưng kém đối với những quả táo
nếu chúng xuất hiện theo các mức độ chín không ổn định. Tức là, một quả táo
xanh và một quả táo chín (đỏ) có thể rất khác nhauvề màu sắc, mặc dù cả hai
đều thuộc lớp đối tượng là các quả táo.
3. Tính độc lập. Nhiều đặc trưng được sử dụng khác nhau không được tương quan
với nhau. Đường kính và trọng lượng của một trái cây sẽ tạo thành các đặc
trưng tương quan chặt, vì trọng lượng tỷ lệ gần đúng với đường kính mũ ba.
Bài toán mà cả đường kính lẫn trọng lượng về bản chất đều phản ánh cùng một
tính chất, ấy là kích thước của trái cây. Trong khi các đặc trưng tương quan
chặt có thể kết hợp (ví dụ, bằng cách lấy trung bình tất cả chúng cùng với nhau)
402
để làm giảm tính nhậy cảm đối với nhiễu, thì nói chung chúng lại không được
sử dụng như những đặc trưng độc lập.
4. Các số nhỏ. Tính phức tạp của một hệ thống nhận dạng mẫu tăng nhanh chóng
theo kích cỡ (số các đặc trưng được dùng) của hệ thống. Quan trọng hơn là số
các đối tượng cần có để huấn luyện bộ phân lớp và để đo lường hiệu suất của
nó tăng theo cấp số mũ với số các đặc trưng. Trong vài trường hợp, để có thể
đạt được lượng dữ liệu cần thiết cho việc huấn luyện bộ phân lớp tương xứng
chỉ là điều hão huyền. Cuối cùng, việc thêm các đặc trưng nhiễu hay đặc trưng
tương quan chặt với các đặc trưng hiện có có thể làm suy giảmhiệu suất của
những bộ phân lớp, đặc biệt bởi vì kích thước giới hạn của tập huấn luyện.
Trong thực tế, quá trình chọn lựa đặc trưng thường bao gồm cả việc kiểm tra tập
các đặc trưng hợp lý quatrực giác và việc giảm tập xuống còn một số các đặc trưng
tốt nhất có thể chấp nhận. Thường có ít hoặc không có sẵn các đặc trưng lý tưởng
dưới dạng các tính chất đã nói ở trên.
20.2.2. Thiết kế bộ phân lớp
Thiết kế bộ phân lớp bao gồm việc thiết lập cấu trúc logic của bộ phân lớp và cơ
sở toán học của quy tắc phân lớp. Thông thường, đối với mỗi đối tượng thường gặp,
sự phân lớp tính toán, với từng lớp, giá trị báo hiệu (bằng độ lớn của nó) mức độ mà
đối tượng đó tương tự đối tượng điển hình của lớp đó. Giá trị này được tính như một
hàm đặc trưng và nó được dùng để chọn lớp gần giống với công việc được giao nhất.
Hầu hết các quy tắc quyết định bộ phân lớp đều giảm đến một vạch ngưỡng phân
chia các không gian kích cỡ thành các vùng rời nhau, mỗi lớp một (hoặc nhiều) vùng.
Mỗi vùng (phạm vi các giá trị đặc trưng) ứng với một lớp riêng lẻ. Nếu các giá trị
đặc trưng nằm trong một vùng riêng biệt thì đối tượng được ấn định cho lớp tương
ứng. Trong vài trường hợp, một hoặc nhiều vùng như vậy có thể ứng với một lớp
“không xác định”.
20.2.3. Huấn luyện bộ phân lớp
Một khi các quy tắc quyết định cơ bản của bộ phân lớp đã được thiết lập thì ta
phải xác định các giá trị ngưỡng riêng biệt phân tách các lớp. Điều này thường được
thực hiện bằng cách huấn luyện bộ phân lớp theo nhóm các đối tượng đã biết. Tập
huấn luyện là một tập hợp các đối tượng từ mỗi lớp đã được nhận biết trước đó bằng
một phương pháp chính xác nào đó. Các đối tượng trong tập huấn luyện được đo, và
không gian kích cỡ được phân chia, bằng các bề mặt quyết định, thành các vùng mà
độ chính xác của bộ phân lớp là tối đa khi nó hoạt động trên tập huấn luyện.
Khi huấn luyện một bộ phân lớp, ta có thể sử dụng quy tắc đơn lẻ, ví dụ như tối
thiểu hoá tổng các sai số phân lớp. Nếu một vài sự phân lớp sai lầm có thể gây rắc rối
hơn những cái khác thì ta có thể thiết lập một hàm giá để giải thích điều này bằng
cách cân nhắc các sai số khác nhau một cách gần đúng. Các đường quyết định sau đó
được đặt vào để tối thiểu hoá toàn bộ “giá” của việc thao tác bộ phân lớp.
Nếu tập huấn luyện là biểu diễn của các đối tượng nói chung thì bộ phân lớp loại
cũng phải thực hiện xung quanh các đối tượng mới giống như nó đã từng thực hiện
trên tập huấn luyện. Có được một tập huấn luyện đủ lớn thường là một công việc
gian khổ. Để được thể hiện, tập huấn luyện phải bam gồm các ví dụ về tất cả những
đối tượng có thể gặp, kể cả những đối tượng hiếm khi nhìn thấy. Nếu tập huấn luyện
ngăn chận một đối tượng không phổ biến nào đó, thì nó không biểu hiện. Nếu nó
chứa các sai số phân lớp thì nó bị thành kiến.
403
20.2.4. Xác định hiệu suất
Sự chính xác của một bộ phân lớp có thể được đánh giá trực tiếp bằng cách liệt kê
hiệu suất của nó dựa trên tập các đối tượng kiểm tra đã biết. Nếu tập kiểm tra đủ lớn
để biểu diễn các đối tượng lớn và nếu nó không có sai số, thì hiệu suất được đánh giá
có thể rất hữu ích.
Một phương pháp lựa chọn cho việc đánh giá hiệu suất là sử dụng tập kiểm tra của
các đối tượng đã biết để đánh giá PDF của những đặc trưng theo từng nhóm. Từ
những PDF cơ bản đã cho, ta có thể sử dụng các tham số phân lớp để tính tỷ lệ sai số
mong muốn. Nếu đã dạng tổng quát của các PDF đó thì kỹ thuật này có thể sử dụng
tập kiểm tra kích thước ở mép tốt hơn.
Ta muốn có được hiệu suất của bộ phân lớp trên tập huấn luyện như một phép đo
toàn bộ hiệu suất của nó, nhưng đánh giá này thường bị nghi ngờ về tính lạc quan.
Một phương pháp tiếp cận tốt hơn là sử dụng một tập kiểm tra riêng biệt đối với việc
đánh giá hiệu suất của bộ phân lớp. Tuy nhiên, điều này làm tăng đáng kể sự cần
thiết của những dữ liệu trước phân lớp.
Nếu những đối tượng đã phân lớp trước đây được đánh giá cao, thì ta có thể sử
dụng một thủ tục vòng luân chuyển mà trong đó bộ phân lớp được huấn luyện với
hầu hết mọi đối tượng và tiếp theo sau là đối tượng đó được phân lớp. Khi điều này
được thực hiện với tất cả các đối tượng thì ta sẽ có một đánh giá của toàn bộ hiệu
suất thực hiện của bộ phân lớp.
20.3. CHỌN LỰA ĐẶC TRƯNG
Trong một bài toán nhạn dạng mẫu, ta thường phải đối mặt với côngviệc chọn lựa
trong nhiều đặc trưng sẵn có, đặc trưng nào xác định và thể hiện bộ phân lớp. Bài
toán chọn lựa đặc trưng đã nhận được sự quan tâm đáng kể trong tài liệu, nhưng lại
nổi lên tình trạng không rõ ràng. Phần này dành cho độc giả như một vấn đề lý thú.
Như đã lưu ý trước đây, ta tìm kiếm một tập nhỏ các đặc trưng tin cậy, độc lập và
sự phân biệt đối xử. Nói chung, ta mong muốn làm suy giảm hiệu suất của bộ phân
lớp khi các đặc trưng được đánh giá, ít ra cũng là những đặc trưng hữu ích. Thực tế,
đánh giá nhiễu hay các đặc trưng tương quan chặt có thể thực sự cải tiến hiệu suất
thực hiện.
Sau đó, chọn lựa đặc trưng có thể được coi như quá trình đánh giá một vài đặc
trưng và kết hợp các đặc trưng có liên quan khác, cho đến khi tập đặc trưng trở nên
dễ sử dụng và sự thực hiện vẫn còn chính xác.
Nếu tập đặc trưng được giảm từ M đặc trưng xuống còn một lượng N nào đó nhỏ
hơn, thì chúng ta sẽ tìm kiếm tập N đặc trưng riêng biệt để tối thiểu hoá toàn bộ việc
thực hiện bộ phân lớp.
Một phương pháp tiếp cận bằng cách lặp đi lặp lại một thủ tục đơn giản nhiều lần
để chọn lựa đặc trưng được cho dưới đây. Đối với tất cả các tập con của N đặc trưng
có thể có, huấn luyện bộ phân lớp, và xác định hiệu suất của nó bằng cách liệt kê các
tỷ số phân lớp nhầm các nhóm khác nhau của bộ phân lớp. Sau đó tạo ra một chỉ số
hiệu suất tổng thể là một hàm tỷ số lỗi. Cuối cùng, sử dụng tập N đặc trưng đó để tạo
ra chỉ số hiệu suất tốt nhất.
Dĩ nhiên bài toán với cách tiếp cận bằng cách lặp đi lặp lại một thủ tục đơn giản
nhiều lần là một khối lượng khổng lồ đối với tất cả trừ các bài toán nhận dạng mẫu
đơn giản nhất. Thực tế, thường thì tài nguyên chỉ đủ để huấn luyện và đánh giá bộ
phân lớp. Trong đa số các bài toán thực tiễn, phương pháp tiếp cận bằng cách lặp đi
404
lặp lại một thủ tục đơn giản nhiều lần là không thực tế và một kỹ thuật ít tốn tiền phải
được sử dụng để đạt được cùng một mục đích.
Trong phần thảo luận dưới đây, chúng ta sẽ xem xét trường hợp giảm một bài toán
hai đặc trưng xuống còn một đặc trưng đơn giản. Giả sử tập huấn luyện là có sẵn và
chứa các đối tượng của M lớp khác nhau. Đặt Nj là số đối tượng trong lớp j. Hai đặc
trưng xij và yij thu được khi xác định đối tượng thứ i trong lớp j. Ta có thể khởi đầu
bằng việc tính giá trị trung bình của từng đặc trưng trong mỗi lớp:
j
N
i
ij
j
xj x
N1
1
(1)
và
j
N
i
ij
j
yj y
N1
1
(2)
Dấu mũ trên đầu
xj và
yj nhắc ta rằng đây là những đánh giá của các giá trị trung
bình trong lớp dựa trên tập huấn luyện, chứ không phải là các giá trị trung bình thật
sự của lớp.
20.3.1. Độ lệch đặc trưng
Lý tưởng mà nói, các đặc trưng phải nhận các giá trị giống nhau đối với mọi đối
tượng trong cùng một lớp. Độ lệch đặc trưng x trong lớp j được đánh giá là
j
N
i
xj
ij
j
xj x
N1
2
21
(3)
và đối với đặc trưng y là
j
N
i
yj
ij
j
yj y
N1
2
21
(4)
20.3.2. Tương quan đặc trưng
Sự tương quan của các đặc trưng x và y trong lớp j có thể được đánh giá bởi
yjxj
N
i
yj
ij
xj
ij
j
xyj
j
yx
N
1
1
(5)
Đại lượng này nằm giữa -1 và +1. Giá trị 0 cho thấy rằng hai đặc trưng là không
tương quan, trong khi giá trị gần +1 cho thấy một mức đọ cao của sự tương quan. Giá
trị -1 chứng tỏ rằng mỗi biến tỷ lệ với giá trị âm của biến khác. Nếu độ lớn của một
tương quan xấp xỉ 1, thì hai đặc trưng có thể được kết hợp thành một hay có thể bỏ đi
một trong hai đặc trưng đó.
20.3.3. Khoảng cách phân tách lớp
Một phép tính xác đáng về khả năng của một đặc trưng để phân biệt hai lớp là
khoảng cách độ lệch đã chuẩn hoá giữa các giá trị trung bình của lớp. Với đặc trưng
x, khoảng cách này được cho bởi
405
22
xkxj
xkxj
xjk
D
(6)
trong đó j, k là hai lớp. Rõ ràng, đặc trưng cao hơn là đặc trưng tạo ra sự tách lớp
phổ biến nhất.
20.3.4. Giảm chiều
Có nhiều phương pháp kết hợp hai đặc trưng x và y thành một đặc trưng z đơn lẻ.
Một phương pháp đơn giản là sử dụng một hàm tuyến tính (Xem phần 13.6.2.1)
byaxz
(7)
Bởi vì hiệu suất phân lớp không bị ảnh hưởng bởi việc lấy tỷ lệ độ lớn của các đặc
trưng, chúng ta có thể lợi dụng sự hạn chế về độ lớn, ví dụ như
1
22 ba (8)
Biểu thức này có thể hợp nhất với biểu thức (7) bằng cách viết
sincos yxz
(9)
trong đó
là một biến mới chỉ rõ tỷ lệ của x và y trong biểu thức.
Nếu mỗi đối tượng trong tập huấn luyện tương ứng với một điểm trong không
gian đặc trưng hai chiều (ví dụ mặt phẳng x, y), thì biểu thức (9) miêu tả mọi điểm
lên trục z, làm thành với trục x một góc
. Điều này được cho trong bảng 20-1. Rõ
ràng, phải được chọn để tối thiểu hoá sự tách lớp hay một tiêu chuẩn chất lượng
nào đó của một đặc trưng. Để hiểu thêm về sự giảm chiều, độc giả nên tham khảo
một cuốn sách nói về nhận dạng mẫu.
HÌNH 20-1
Hình 20-1 Giảm chiều bằng phép chiếu
20.4. SỰ PHÂN LỚP THỐNG KÊ
Trong phần này, chúng ta sẽ xem xét một vài phương pháp thống kê phổ biến
được dùng cho phân lớp.