S
ố hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌ



VŨ THỊ THU HUYỀN


KỸ THUẬT SVM
TRONG NHẬN DẠNG PHIẾU ĐIỂM
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01



LUẬN VĂN THẠ


: TS. Nguyễn Văn Vinh


Thái Nguyên – 2013
i

S
ố hóa bởi Trung tâm Học liệu

LỜI CAM ĐOAN

Tên tôi là: Vũ Thị Thu Huyền
Lớp: Cao học Công nghệ thông tin K10B
Khoá học: 2011 - 2013
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 60 48 01
Cơ sở đào tạo: Trƣờng Đại học Công nghệ thông tin và Truyền thông Thái Nguyên
Giáo viên hƣớng dẫn: TS Nguyễn Văn Vinh
Cơ quan công tác: Trƣờng Đại học Công nghệ Thông tin và Truyền thông -
Đại học Thái Nguyên
Tôi xin cam đoan toàn bộ nội dung đƣợc trình bày trong bản luận văn này là
kết quả tìm hiểu và nghiên cứu của riêng tôi, trong quá trình nghiên cứu luận văn
“Kỹ thuật SVM trong nhận dạng phiếu điểm” các kết quả và dữ liệu đƣợc nêu ra
là hoàn toàn trung thực. Mọi thông tin trích dẫn đều đƣợc tuân theo luật sở hữu trí
tuệ, có liệt kê rõ ràng các tài liệu tham khảo.
Tôi xin chịu hoàn toàn trách nhiệm với những nội dung đƣợc viết trong luận
văn này.

Thái Nguyên, ngày 18 tháng 09 năm 2013
HỌC VIÊN


Vũ Thị Thu Huyền

ii

S
ố hóa bởi Trung tâm Học liệu


LỜI CẢM ƠN
Luận văn đƣợc thực hiện tại Trƣờng Đại học Công nghệ Thông tin và Truyền
Thông - Đại học Thái Nguyên dƣới sự hƣớng dẫn của thầy TS. Nguyễn Văn Vinh.
Trƣớc hết em xin bày tỏ lòng biết ơn sâu sắc tới thầy TS. Nguyễn Văn Vinh,
trƣờng Đại học Công nghệ - ĐH Quốc gia Hà Nội, ngƣời đã tận tình hƣớng dẫn
giúp đỡ để em hoàn thành tốt luận văn của mình.
Em xin gửi lời cảm ơn chân thành đến các thầy cô giáo Trƣờng Đại học
Công nghệ Thông tin và Truyền Thông - Đại học Thái Nguyên, cùng các thầy cô
giáo đã nhiệt tình giảng dạy, truyền đạt kiến thức cho em trong suốt quá trình học
tập tại trƣờng cũng nhƣ quá trình làm luận văn này.
Cuối cùng em xin gửi lời cảm ơn đến gia đình, bạn bè, các đồng nghiệp
những ngƣời đã động viên, giúp đỡ và tạo điều kiện cho em trong quá trình học tập
và hoàn thành luận văn.

Thái Nguyên, ngày 18 tháng 09 năm 2013
HỌC VIÊN


Vũ Thị Thu Huyền




iii

S
ố hóa bởi Trung tâm Học liệu

MỤC LỤC
LỜI CAM ĐOAN i

LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT vi
DANH MỤC CÁC HÌNH VẼ vii
LỜI MỞ ĐẦU 1
CHƢƠNG 1. KHÁI QUÁT VỀ NHẬN DẠNG VÀ KỸ THUẬT SVM 3
1.1. Khái quát về nhận dạng 3
1.1.1. Khái niệm về nhận dạng 3
1.1.2. Một số kỹ thuật nhận dạng 4
1.1.2.1 Nhận dạng dựa theo miền không gian 4
1.1.2.2. Nhận dạng theo phƣơng pháp thống kê 6
1.1.2.3. Nhận dạng dựa vào khoảng cách 7
1.1.2.3. Nhận dạng dựa theo cấu trúc 8
1.1.3. Kết hợp các kỹ thuật nhận dạng 10
1.1.3.1. Kiến trúc tuần tự 11
1.1.3.2. Kiến trúc song song 11
1.1.3.3. Kiến trúc lai ghép 11
1.1.4. Một số khó khăn trong nhận dạng 12
1.2. Kỹ thuật SVM trong nhận dạng 13
1.2.1. Kỹ thuật SVM 13
1.2.2. Một số ứng dụng của SVM 14
1.2.2.1. Chẩn đoán Virus máy tính 14
1.2.2.2. Phân loại email 15
1.2.2.3. Nhận dạng mặt ngƣời 17
1.2.2.4. Nhận dạng chữ viết tay 17
1.3. Kết luận 19
iv

S
ố hóa bởi Trung tâm Học liệu


CHƢƠNG 2. KỸ THUẬT SVM TRONG NHẬN DẠNG PHIẾU ĐIỂM 21
2.1. Thuật toán SVM 21
2.1.1. Phân lớp nhị phân 21
2.1.2. Phân nhiều lớp 29
2.1.2.1. Chiến lƣợc một chống một (OVO: One - versus - One) 29
2.1.2.2. Chiến lƣợc một chống phần còn lại (OVR: One - versus - Rest) 30
2.1.2.3. Chiến lƣợc phân cấp 30
2.2. Các thuật toán huấn luyện SVM 31
2.2.1. Thuật toán chặt khúc 31
2.2.2. Thuật toán phân rã 32
2.2.3. Thuật toán SMO 32
2.2.3.1. Tối ƣu hai nhân tử Lagrange 33
2.2.3.2. Tối ƣu theo phƣơng pháp heuristic 34
2.2. Nhận dạng phiếu điểm với SVM 35
2.2.1. Đặc trƣng của phiếu điểm 35
2.2.2. Nhận dạng phiếu điểm 37
2.2.2.1. Tiền xử lý 38
2.2.2.2. Phân đoạn và trích chọn đặc trƣng 41
2.2.2.3. Huấn luyện và nhận dạng 41
2.2.2.4. Hậu xử lý 41
2.3. Kết luận 42
CHƢƠNG 3. THIẾT KẾ CHƢƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM 43
3.1. Phân lớp với SVM 43
3.2. Nhận dạng phiếu điểm 45
3.2.1. Huấn luyện 48
3.2.2. Nhận dạng 49
3.3. Đánh giá kết quả 50
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 53
v


S
ố hóa bởi Trung tâm Học liệu

TÀI LIỆU THAM KHẢO 54
vi

S
ố hóa bởi Trung tâm Học liệu

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Viết tắt
Ý nghĩa
NNSRM
Nearest Neighbor Rule-based Structural Risk Minimization
OVO
One - versus - One
OVR
One - versus - Rest
PCA
Principal Component Analysis
PLD
Picture Language Description
QP
Quadratic Programing
RBF
Radius Basic Function
SMO
Sequential Minimal Optimization
SVM

Support Vector Machine


vii

S
ố hóa bởi Trung tâm Học liệu

DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Sơ đồ tổng quát hệ thống nhận dạng ảnh 4
Hình 1.2. Các từ vựng cơ bản của ngôn ngữ hình thức PLD 9
Hình 1.3. Các phép toán trong ngôn ngữ LCD 10
Hình 1.4. Mô hình nhận dạng chữ viết tay rời rạc. 18
Hình 2.1. Phân lớp tuyến tính 21
Hình 2.2. Phân nhiều lớp với SVM 29
Hình 2.3. Mẫu phiếu điểm thi viết 36
Hình 2.4. Mẫu phiếu điểm thƣờng xuyên 37
Hình 2.5. Nhị phân hóa ảnh 38
Hình 2.6. Lọc nhiễu 38
Hình 2.7. Chuẩn hóa kích thƣớc ảnh các số “4” và “6”. 39
Hình 2.8. Làm tròn biên chữ 40
Hình 2.9. Làm mảnh chữ. 40
Hình 2.10. Hiệu chỉnh độ nghiêng của phiếu điểm. 41
Hình 2.11. Tách thông tin phiếu điểm 41
Hình 3.1. Chƣơng trình mô phỏng phân lớp 43
Hình 3.2. Mô phỏng phân lớp nhị phân với SVM 44
Hình 3.3. Phân nhiều lớp với SVM (trƣớc khi phân lớp) 44
Hình 3.4. Phân nhiều lớp với SVM (sau khi phân lớp) 45
Hình 3.5. Một mẫu dữ liệu huấn luyện 45
Hình 3.6. Phiếu điểm cần nhận dạng 46

Hình 3.7. Mô hình hệ thống nhận dạng phiếu điểm 47
Hình 3.8. Huấn luyện Support Vector theo dữ liệu mẫu 48
Hình 3.9. Các support vector 48
Hình 3.10. Nhận dạng các chữ số với SVM 49
Hình 3.11. Nhận dạng phiếu điểm 50
Hình 3.12. Xử lý phiếu điểm 50
viii

S
ố hóa bởi Trung tâm Học liệu

Hình 3.13. Nhận dạng phiếu điểm 50
1

S
ố hóa bởi Trung tâm Học liệu

MỞ ĐẦU
Các phƣơng pháp thống kê gần đây thƣờng đƣợc đề cập tới trong các lĩnh
vực xử lý ngôn ngữ tự nhiên, thị giác máy, nhận dạng tiếng nói, … xem nhƣ là sự
chọn lựa có cải tiến đối với các phƣơng pháp truyền thống bởi vì các phƣơng pháp
này tận dụng đƣợc lƣợng dữ liệu khổng lồ ngày càng tăng lên và sức mạnh tính toán
của máy tính [10]. Các phƣơng pháp học theo thống kê đặc biệt thích hợp với lĩnh
vực thị giác máy nhƣ nhận dạng và xác định đối tƣợng hiệu quả [13] . Một trong các
phƣơng pháp đó là Máy hỗ trợ vector (Support Vector Machine - SVM).
SVM là một phƣơng pháp máy học đƣợc giới thiệu từ năm 1995 và ngày
càng trở nên phổ biến trong việc ứng dụng vào các lĩnh vực nhƣ: xử lý ảnh, xử lý
ngôn ngữ, thị giác máy, … [10], [13]. SVM đƣợc xây dựng, mở rộng và phân tích
dựa trên lý thuyết một cách chặt chẽ. Ƣu điểm chính của SVM so với các phƣơng
pháp khác là cách giải quyết vấn đề mang tính toàn cục trong khi các phƣơng pháp

khác có thể mang tính cục bộ. Tăng cƣờng khả năng SVM bằng cách chọn một hàm
thích hợp là những hàm có khả năng học dữ liệu phức tạp và phân chia phi tuyến (ví
dụ hàm đa thức (Polynomial), hàm bán kính căn bản (RBF) và hàm Perceptron
(mạng nơron 2 lớp) thƣờng đƣợc dùng nhƣ các hàm xấp xỉ) để phát triển thành công
cụ phân lớp.
Các bài toán nhận dạng đƣợc nghiên cứu nhiều hiện nay bao gồm nhận dạng
các mẫu hình học (vân tay, mặt ngƣời, hình khối,…), nhận dạng tiếng nói và nhận
dạng ký tự viết. Nhận dạng ký tự viết bao gồm hai kiểu chính là nhận dạng ký tự in
và nhận dạng ký tự viết tay. Cho đến nay bài toán nhận dạng ký tự in đã đƣợc giải
quyết khá trọn vẹn với sự ra đời của nhiều hệ thống nhận dạng đạt tới độ chính xác
gần nhƣ tuyệt đối. Nhận dạng ký tự viết tay hiện vẫn đang là vấn đề thách thức đối
với các nhà nghiên cứu, bài toàn này chƣa thể giải quyết trọn vẹn đƣợc vì nó phụ
thuộc nhiều vào ngƣời viết và sự biến đổi đa dạng trong cách viết và trạng thái tinh
thần của từng ngƣời viết.
Hiện nay, có nhiều kỹ thuật học máy đƣợc ứng dụng cho bài toán nhận dạng
chữ viết tay và cho kết quả đầy triển vọng [11], [14]. Một trong các kỹ thuật đó là
2

S
ố hóa bởi Trung tâm Học liệu

kỹ thuật học máy SVM [5], [12]. Do đó chúng tôi chọn đề tài: “Kỹ thuật SVM
trong nhận dạng phiếu điểm”.
Tuy nhiên do hạn chế về mặt thời gian cũng nhƣ độ phức tạp của bài toán, do
đó tôi chỉ đi sâu nghiên cứu về kỹ thuật SVM và mô phỏng chƣơng trình nhận dạng
phiếu điểm. Các phiếu điểm đƣợc sử dụng trong luận văn này là những mẫu phiếu
điểm đang đƣợc sử dụng tại trƣờng Đại học Công nghệ Thông tin và Truyền thông,
Đại học Thái Nguyên.
Nội dung luận văn gồm:
Chƣơng 1: Khái quát về nhận dạng và kỹ thuật SVM

Trình bày những lý thuyết cơ bản về nhận dạng, kỹ thuật SVM trong nhận
dạng: khái niệm về nhận dạng, các phƣơng pháp nhận dạng. Các vấn đề và ứng dụng
của nhận dạng. Giới thiệu sơ lƣợc về SVM, những ứng dụng trong thực tế của SVM.
Chƣơng 2: Kỹ thuật SVM trong nhận dạng phiếu điểm
Giới thiệu về kỹ thuật SVM, thuật toán SVM. Đặc trƣng của phiếu điểm, kỹ
thuật SVM trong nhận dạng phiếu điểm.
Chƣơng 3: Thiết kế chƣơng trình và kết quả thử nghiệm
Thiết kế chƣơng trình minh họa kỹ thuật phân lớp với SVM, nhận dạng số
viết tay, phiếu điểm với SVM.
Kết luận và hƣớng phát triển
Trình bày các kết quả đã đạt đƣợc, hƣớng phát triển tiếp theo.
Do thời gian và trình độ còn hạn chế nên luận văn khó tránh khỏi những
thiếu sót, kính mong nhận đƣợc sự đóng góp, chỉ bảo của các thầy giáo, cô giáo và
các bạn đồng nghiệp.
Cuối cùng, tác giả xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy giáo -
TS. Nguyễn Văn Vinh - Giảng viên Đại học Công nghệ, Đại học Quốc Gia Hà Nội
đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ, khích lệ tác giả trong suốt quá trình làm
luận văn. Đồng thời, tác giả xin chân thành cảm ơn các thầy cô trong trƣờng Đại
học Công nghệ Thông tin và Truyền thông, Đại học Thái Nguyên đã tạo điều kiện
thuận lợi, giúp đỡ tác giả hoàn thành luận văn này.
3

S
ố hóa bởi Trung tâm Học liệu

CHƢƠNG 1
KHÁI QUÁT VỀ NHẬN DẠNG VÀ KỸ THUẬT SVM
1.1. Khái quát về nhận dạng
1.1.1. Khái niệm về nhận dạng [4]
Nhận dạng ảnh là quá trình phân loại các đối tƣợng đƣợc biểu diễn theo một

mô hình nào đó và gán cho chúng một tên gọi dựa theo những quy luật và mẫu
chuẩn. Quá trình nhận dạng dựa vào những mẫu học biết trƣớc gọi là nhận dạng
mẫu. Quá trình nhận dạng gồm 3 giai đoạn chính:
- Chọn mô hình biểu diễn đối tƣợng.
- Chọn luật ra quyết định (phƣơng pháp nhận dạng) và suy diễn.
- Học trong nhận dạng.
Trong việc lựa chọn để biểu diễn đối tƣợng, đối tƣợng có thể đƣợc xác định
theo cách định lƣợng (mô hình tham số) hay định tính (mô hình cấu trúc). Khi đối
tƣợng đã đƣợc xác định, quá trình nhận dạng chuyển sang giai đoạn thứ hai -
giai đoạn học (Learning). Học là giai đoạn cung cấp tri thức cho hệ thống. Mục
đích học nhằm cải thiện, điều chỉnh việc phân loại tập đối tƣợng thành các lớp.
Nhận dạng là tìm ra quy luật và các thuật toán để có thể gắn đối tƣợng vào một lớp
hay nói một cách khác gán cho đối tƣợng một tên.
Học theo mẫu: Kỹ thuật phân loại nhờ kiến thức biết trƣớc gọi là học theo
mẫu. Đặc điểm cơ bản của kỹ thuật này là ta có một thƣ viện các mẫu chuẩn. Mẫu
cần nhận dạng sẽ đƣợc đem so sánh với mẫu chuẩn để xem nó thuộc loại nào. Vấn
đề chủ yếu là thiết kế một hệ thống để có thể đối sánh đối tƣợng trong ảnh với mẫu
chuẩn và quyết định gán cho chúng vào một lớp. Việc đối sánh nhờ vào các thủ tục
ra quyết định dựa trên một công cụ gọi là hàm phân lớp hay hàm ra quyết định [2].
Học không có mẫu: Kỹ thuật này phải tự định ra các lớp khác nhau và xác
định các tham số đặc trƣng cho từng lớp. Học không có mẫu gặp khó khăn hơn so
với học theo mẫu. Một mặt, do số lớp không đƣợc biết trƣớc, mặt khác những đặc
trƣng của lớp cũng không đƣợc biết trƣớc. Kỹ thuật này nhằm tiến hành mọi cách
4

S
ố hóa bởi Trung tâm Học liệu

gộp nhóm có thể và chọn lựa cách tốt nhất. Bắt đầu từ tập dữ liệu, nhiều thủ tục xử
lý khác nhau nhằm phân lớp và nâng cấp dần để đạt đƣợc một phƣơng án phân loại.

Lĩnh vực nhận dạng chữ đƣợc chia làm hai loại: Nhận dạng chữ in và nhận
dạng chữ viết tay. Đến thời điểm này, nhận dạng chữ in đã đƣợc giải quyết gần nhƣ
trọn vẹn. Tuy nhiên, nhận dạng chữ viết tay vẫn đang là vấn đề thách thức lớn đối với
các nhà nghiên cứu. Nhận dạng chữ viết tay đƣợc phân ra làm hai loại: nhận dạng
chữ viết tay online (trực tuyến) và nhận dạng chữ viết tay offline (ngoại tuyến) [5].
Nhận dạng chữ viết tay online đƣợc thực hiện trên cơ sở lƣu lại các thông tin
về nét chữ nhƣ thứ tự nét viết, hƣớng và tốc độ của nét viết trong quá trình nó đang
viết. Đây chính là cơ sở để máy tính nhận diện đƣợc các chữ cái, do đó việc nhận
dạng không gặp quá nhiều khó khăn. Ngƣợc lại, đối với nhận dạng chữ viết tay
offline, dữ liệu đầu vào là ảnh văn bản đƣợc quét vào nên việc nhận dạng có độ khó
cao hơn nhiều so với nhận dạng chữ viết tay online. Do dữ liệu đầu vào là ảnh văn
bản nên nhận dạng chữ viết tay offline và nhận dạng chữ in còn đƣợc gọi chung là
nhận dạng chữ quang học (OCR - Optical Character Recognition).
Một hệ thống nhận dạng có thể tóm tắt theo sơ đồ sau:

Hình 1.1. Sơ đồ tổng quát hệ thống nhận dạng ảnh
1.1.2. Một số kỹ thuật nhận dạng
1.1.2.1 Nhận dạng dựa theo miền không gian [4], [14]
Trong kỹ thuật này, các đối tƣợng nhận dạng là các đối tƣợng định lƣợng.
Mỗi đối tƣợng đƣợc biểu diễn bởi một vectơ nhiều chiều.
Phân hoạch không gian
5

S
ố hóa bởi Trung tâm Học liệu

Giả sử không gian đối tƣợng
X
đƣợc định nghĩa:
{X , 1,2 }

i
X i m
, với X
i

là một vectơ. Ngƣời ta nói D là một phân hoạch của không gian X thành các lớp C
i
,
,ii
C C X
nếu:
ij
CC
với
ij
và
i
CX

Đây là trƣờng hợp lý tƣởng khi tập X tách đƣợc hoàn toàn. Trong thực tế,
thƣờng gặp không gian biểu diễn tách đƣợc từng phần. Nhƣ vậy, phân loại là dựa
vào việc xây dựng một ánh xạ f:
XD
. Công cụ xây dựng ánh xạ này là các hàm
phân biệt (Descriminant Functions).
Để chia đối tƣợng thành các lớp, cần xác định số lớp và ranh giới giữa các
lớp đó. Gọi {g i} là các hàm phân lớp hay hàm tách biệt. Lớp hàm này đƣợc định
nghĩa nhƣ sau:
Nếu
ik"¹

, g k(X>) g i (X) thì ta quyết định
X Î
lớp k.
Nhƣ vậy để phân biệt lớp k lớp ta cần k-1 hàm phân biệt. Hàm phân biệt g(.)
củamột lớp nào đó thƣờng đƣợc dùng trong thực tế do tính đơn giản, dễ xử lý là
hàm tuyến tính. Hàm tuyến tính có dạng:
0 1 1 2 2
( ) W W W W
kk
g X X X X

Trong đó:
W
i
là trọng số gán cho các thành phần X
i
;
W
0
là trọng số hằng.
Trong trƣờng hợp hàm g(.) là tuyến tính, ngƣời ta nói việc phân lớp là tuyến
tính (trong trƣờng hợp một hay hai chiều) hay siêu phẳng (trong trƣờng hợp nhiều
chiều). Các hàm phân biệt thƣờng đƣợc xây dựng dựa trên khái niệm khoảng cách
hay dựa vào xác suất có điều kiện.
Phân lớp dựa theo khoảng cách (Distance) là một công cụ tốt để xác định
đối tƣợng có “gần nhau” về một đặc trƣng nào đó hay không. Nếu khoảng cách nhỏ
hơn một ngƣỡng nào đấy thì ta coi hai đối tƣợng là giống nhau. Nếu chúng giống
6

S

ố hóa bởi Trung tâm Học liệu

nhau ta gộp chung lại, nếu chúng khác nhau thì ta tách thành hai hoặc nhiều lớp
phân biệt.
Phân lớp dựa theo xác suất có điều kiện (Conditional Probability). Trong
một số trƣờng hợp, ngƣời ta dựa vào xác suất có điều kiện để phân lớp cho đối
tƣợng. Lý thuyết xác suất có điều kiện đƣợc Bayes nghiên cứu khá kỹ lƣỡng và
đƣợc dùng để phân biệt đối tƣợng.
1.1.2.2. Nhận dạng theo phương pháp thống kê [4]
Giả sử các đối đối tƣợng nhận dạng tuân theo luật phân bố Gauss, với hàm
mật độ xác suất:


Trong đó m là kỳ vọng, là độ lệch chuẩn.
Ngƣời ta có dùng phƣơng pháp ra quyết định dựa vào lý thuyết Bayes. Lý
thuyết Bayes thuộc loại lý thuyết thống kê nên phƣơng pháp nhận dạng dựa trên lý
thuyết Bayes có tên là phƣơng pháp thống kê.
Quy tắc Bayes:
Cho không gian đối tƣợng X={X
l
, l=1,2,…L},không gian diễn dịch
Ω={C
1
,C
2
,…C
r
} với r là số lớp.
Giả sử tồn tại một sai số trong kết quả nhận dạng, khi đó quy tắc Bayes
đƣợc phát biểu:

: X
sao cho
k
XC
nếu
( / ) ( / )
kl
P C X P C X
lk
,
1,2, , .lr

ở đây:
( / )
k
P C X
là xác suất của C
k
trong điều kiện X xảy ra. Tƣơng tự đối với
( / )
l
P C X
.
Trƣờng hợp lý tƣởng là nhận dạng đúng (không có sai số). Thực tế, luôn tồn
tại sai số trong quá trình nhận dạng. Vấn đề chính ở đây là xây dựng quy tắc nhận
dạng với sai số là nhỏ nhất.
Phƣơng pháp ra quyết định với tối thiểu:
2
22
1 ( )

( ) exp
22
xm
fx
7

S
ố hóa bởi Trung tâm Học liệu

Cần xác định
k
XC
nhờ xác suất
( / )
k
P C X
. Nếu có sai số sẽ đƣợc tính bởi
1 ( / )
k
P C X
. Để đánh giá sai số trung bình, ngƣời ta xây dựng một ma trận
( , )L r r
với giả thiết có n lớp.
Ma trận L đƣợc định nghĩa nhƣ sau:
,
,
,
0 khi
0 khi
ki

ki
kj
l k j
L
l k j
í
ï
>¹
ï
=
ì
ï
£=
ï
î

Nhƣ vậy, sai số trung bình của sự phân lớp sẽ là:

,
1
/
r
k k j j
j
r X l P C X

(1.1)
Để sai số là nhỏ nhất ta cần có r
k
là nhỏ nhất (min). Từ lý thuyết xác suất ta

có công thức tính xác suất có điều kiện (Công thức Bayes):

( )
( / ) ( )
( / )
jj
j
P X C P C
P C X
PX
=
(1.2)
Từ công thức (1.1) và (1.2) suy ra:
(1.3)

Vậy, quy tắc ra quyết định dựa trên lý thuyết Bayes có tính đến sai số đƣợc
phát biểu nhƣ sau:

k
XCÎ
nếu p
k
<p
p
với p<>k, p=1,2, r
Với p
k
là r
k
(X) đƣợc xác định theo (1.3). Rõ ràng, từ điều kiện p

k
,<p
p
ta hoàn
toàn xác định đối tƣơng X thuộc lớp C
k
nào. Đây chính là nội dung tƣ tƣởng của
phƣơng pháp thống kê.
1.1.2.3. Nhận dạng dựa vào khoảng cách [4]
a. Nguyên tắc
Giả sử có tập gồm m đối tƣợng. Xác định khoảng cách giữa các đối tƣợng và
khoảng cách lớn nhất ứng với phần tử xa nhất tạo nên lớp đối tƣợng mới. Việc phân
lớp đƣợc tạo nên dần dần dựa vào thủ tục xác định khoảng cách giữa các đối tƣợng
và các lớp.
( )
( ) ( )
,
1
/
r
k k j j j
j
r X l P X C P C
=
=
å
8

S
ố hóa bởi Trung tâm Học liệu


b. Thuật toán
Bước 1:
Chọn hạt nhân ban đầu. Giả sử X
1
C
1
gọilà lớp g
1

Gọi Z
1
là phần tử trung tâm của g
1

Tính tất cả các khoảng cách D
j1
=D(X
j
,Z
1
) với j=1,2, m
Tìm D
k1
=max
j
D
jk
trong đó X
k

là phần tử xa nhất của nhóm g
1.

Như vậy, X
k
là phần tử trung tâm của lớp mới g
2
. Kí hiệu Z
2
.
Tính d
1
=D
12
=D(Z
1,
Z
2
).
Bước 2:
Tính khoảng cách D
j1
, D
j2
với
D
j1
=D(X
j
,Z

1
); D
j2
=D(X
j
,X
2
). Đặt D
k
(2)
=max
j
D
j

Nguyên tắc chọn:
Nếu D
k
(2)
<Өd
k
, với Ө là ngưỡng cho trước.
Kết thúc thuật toán. Việc phân lớp kết thúc;
Nếu không, tạo nhóm thứ ba. Gọi X
3
là phần tử trung tâm của g
3
, ký hiệu Z
3
;

Tính D
3
=(D
12
+D
13
+D
23
);
D
13
=D(Z
1
,Z
3
);
D23=D(Z
2
,Z
3
).
Quá trình lặp lại cho đến khi phân xong.
Kết quả thu được các lớp đại diện Z
1
,Z
2
, ,Z
m
1.1.2.3. Nhận dạng dựa theo cấu trúc [4]
Biểu diễn định tính: Ngoài cách biểu diễn định lƣợng (theo tham số) nhƣ đã

mô tả ở trên, tồn tại nhiều kiểu đối tƣợng mạng tính định tính (theo cấu trúc). Trong
cách biểu diễn này, ngƣời ta quan tâm đến các dạng và mối quan hệ giữa chúng. Giả
thiết rằng, mỗi đối tƣợng đƣợc biểu diễn bởi một dãy ký tự, các đặc tính biểu diễn
bởi cùng một số ký tự. Phƣơng pháp nhận dạng ở đây là nhận dạng logic, dựa vào
hàm phân biệt là hàm Bool. Cách nhận dạng là nhận dạng các từ có cùng độ dài.
Giả sử hàm phân biệt cho mọi ký hiệu là g
a
(X), g
b
(X), tƣơng ứng với các ký hiệu
9

S
ố hóa bởi Trung tâm Học liệu

a, b, Để dễ dàng hình dung, ta giả sử có từ 'abcd' đƣợc biểu diễn bởi một dãy ký
tự X={x
1
, x
2
, x
3
, x
4
}, khi đó hàm phân biệt tƣơng ứng nhận đƣợc là:
g a(x
1
)+ g b(x
2
) + g c(x

3
) + gd(x
4
)
Các phép cộng ở đây có thể áp dụng toán tử OR trên cơ sở tính giá trị cực đại
của hàm phân biệt, xác định (quyết định) X có thuộc lớp các từ "abcd" hay không.
Trong cách tiếp cận này, đối tƣợng của ta có thể xem là tƣơng đƣơng với một câu
hay một mệnh đề.
Thủ tục phân loại và nhận dạng ở đây gồm hai giai đoạn:
Giai đoạn 1: Xác định các quy tắc xây dựng, tƣơng đƣơng với việc nghiên
cứu một văn phạm trong một ngôn ngữ chính thống.
Giai đoạn 2: Xem xét tập các dạng trong không gian mẫu có đƣợc sinh ra hoàn
toàn từ các dạng cơ bản đó không. Nếu nó thuộc tập đó thì coi nhƣ đã phân loại xong.
Tuy nhiên, ở phƣơng pháp này, văn phạm là một vấn đề lớn khá phức tạp và
khó có thể tìm đƣợc loại phù hợp một cách hoàn hảo với mọi đối tƣợng. Vì vậy,
trong nhận dạng dựa theo cấu trúc, ta chỉ sử dụng đƣợc một phần rất nhỏ.
Nhƣ đã trình bày trong phần các mô hình biểu diễn mẫu. Mô hình cấu trúc
tƣơng đƣơng với một văn phạm G: G={V1, Vn, P, S}. Ngoài ra còn có rất nhiều văn
phạm khác nhau từ chính tắc đến phi ngữ cảnh. Một văn phạm sẽ đƣợc sử dụng
trong nhận dạng bởi một ngôn ngữ hình thức, trong đó có một ngôn ngữ điển
hình cho nhận dạng cấu trúc là PLD (Picture Language Description).
Trong ngôn ngữ PLD, các từ vựng là các vạch có hƣớng. Có bốn từ vựng cơ bản:

Hình 1.2. Các từ vựng cơ bản của ngôn ngữ hình thức PLD
Các phép toán cho các từ vựng trên đƣợc định nghĩa nhƣ sau:

10

S
ố hóa bởi Trung tâm Học liệu







Hình 1.3. Các phép toán trong ngôn ngữ LCD
Văn phạm sinh ra các mô tả trong ngôn ngữ PLD đƣợc định nghĩa nhƣ sau:
GA = {Vn, VT, P, S}
Với Vn = {A, B, C, D, E} và VT = {a, b, c , d}. S là ký hiệu bắt đầu và P là
tập luật sản xuất.
Các bƣớc nhận dạng
Các đối tƣợng cần đƣợc nhận dạng theo phƣơng pháp này đƣợc biểu diễn bởi
một câu trong ngôn ngữ, gọi là L(G). Khi đó thao tác phân lớp chính là xem xét một
đối tƣợng có thuộc văn phạm L(G) không. Nói cách khác, nó có đƣợc sinh ra bởi
các luật của văn phạm G hay không.
Nhƣ vậy các bƣớc cần phải thực hiện là:
Xác định tập V
1
chung cho tất cả mọi đối tƣợng
Xác định các quy tắc P để sản sinh ra một câu và chúng khác nhau đối với
mỗi lớp.
Thực hiện quá trình học với các câu biểu diễn các đối tƣợng mẫu l nhằm xác
định văn phạm G.
Ra quyết định: xác định một đối tƣợng X đƣợc biểu diễn bởi một câu
l
x
. Nếu l
x
nhận biết bởi L(G

k
) thì ta nói rằng X là một đối tƣợng thuộc loại C
k
.
Nói cách khác, việc ra quyết định phân lớp dựa vào phân tích câu G
k

biểu diễn lớp C
k
.

1.1.3. Kết hợp các kỹ thuật nhận dạng
Các phần đã trình bày ở trên cho thấy rằng có nhiều phƣơng pháp nhận dạng
lớp có thể áp dụng đối với các hệ nhận dạng chữ viết tay. Mỗi phƣơng pháp trên đều
11

S
ố hóa bởi Trung tâm Học liệu

có những ƣu điểm và nhƣợc điểm riêng. Vấn đề đặt ra là các phƣơng pháp trên caó
thể kết hợp với nhau theo một cách nào đó để nâng cao chất lƣợng nhận dạng hay
không ? Nhiều công trình nghiên cứu kiến trúc phân lớp theo ý tƣởng kết hợp các
phƣơng pháp nhận dạng đã nêu trên. Các hƣớng tiếp cận kiến trúc kết hợp để phân
lớp có thể chia thành ba nhóm sau: Kiến trúc tuần tự, kiến trúc song song và kiến
trúc lai ghép.
1.1.3.1. Kiến trúc tuần tự
Kiến trúc này chuyển kết quả đầu ra của một máy phân lớp thành đầu vào của
máy phân lớp tiếp theo. Có bốn chiến lƣợc cơ bản đƣợc sử dụng trong kiến trúc
tuần tự, đó là dãy, chọn lựa boosting và thác nƣớc.
Trong chiến lƣợc về dãy, mục tiêu của mỗi giai đoạn là thu gọn số lớp mà

mẫu đầu vào có thể thuộc về các lớp đó. Số lớp có thể thu gọn tại mỗi giai đoạn sinh
ra nhãn của mẫu ở giai đoạn cuối cùng. Trong chiến lƣợc chọn lựa, đầu tiên máy
phân lớp gán mẫu chƣa biết vào một nhóm ký tự gần giống nhau. Các nhóm này
tiếp tục đƣợc phân lớp ở các giai đoạn sau đó theo một cây phân cấp. Tại mỗi mức
của cây, nhánh con cùng mẹ là giống nhau theo một độ đo nào đó. Vì vậy, các máy
phân lớp thực hiện phân lớp từ thô đến tinh dần trong các nhóm nhỏ. Đối với chiến
lƣợc boosting, mỗi máy phân lớp điều khiển một số lớp, các máy phân lớp ở phía
trƣớc không thể điều khiển đƣợc các lớp của các máy phân lớp ở phía sau.Cuối
cùng, trong chiến lƣợc thác nƣớc, các máy phân lớp đƣợc kết nối từ đơngiản đến
phức tạp. Các mẫu không thỏa mãn ở một mức độ tin cậy nào đó thì phải thông qua
một máy phân lớp mạnh hơn trong một giới hạn nào đó của các đặc trƣng
hoặc các chiến lƣợc nhận dạng khác.
1.1.3.2. Kiến trúc song song
Kiến trúc này kết nối kết quả của các thuật toán phân lớp độc lập bằng cách
sử dụng nhiều phƣơng pháp khác nhau. Trong số các kiến trúc này, tiêu biểu nhất là
phƣơng pháp bỏ phiếu và luật quyết định Bayes.
1.1.3.3. Kiến trúc lai ghép
12

S
ố hóa bởi Trung tâm Học liệu

Kiến trúc này là một sự lai ghép giữa hai kiến trúc tuần tự và song
song. Ý tƣởng chính là kết hợp các điểm mạnh của cả hai kiến trúc trên và chặn bớt
những khó khăn trong việc nhận dạng chữ viết. Sau đây là một vài ví dụ điển
hình về các hƣớng kết hợp các kỹ thuật nhận dạng:
Theo Yuan Y. Tang (1998), một hƣớng tiếp cận dãy trên cơ sở phân lớp đa
đặc trƣng và đa mức đƣợc phát triển cho chữ viết tay Trung Quốc. Hệ thống này sử
dụng mƣời lớp đặc trƣng nhƣ các đặc trƣng về hình dáng bên ngoài, các đặc trƣng
về mật độ nét bút và các đặc trƣng về hƣớng nét bút. Đầu tiên, một nhóm các máy

phân lớp phân chia toàn bộ các ký tự thành một số nhóm nhỏ hơn, vì vậy số lƣợng
mẫu cần xử lý trong mỗi bƣớc tiếp theo giảm đi đáng kể. Sau đó, phƣơng pháp phân
lớp ký tự đa mức đƣợc đề xuất với năm mức phục vụ cho quyết định phân lớp cuối
cùng. Trong mức thứ nhất, một phân bố Gausse đƣợc lựa chọn để sử dụng cho việc
lựa chọn một số mẫu nhỏ hơn từ một vài nhóm. Từ mức thứ hai đến mức thứ năm,
các hƣớng tiếp cận đối sánh đƣợc sử dụng với các đặc trƣng khác nhau để nhận dạng.
Srihari (1989) và các cộng sự đã đề xuất một hƣớng tiếp cận song song cho
việc nhận dạng bản thảo viết tay ở mức từ, họ kết hợp ba thuật toán: đối sánh mẫu,
phân lớp cấu trúc và phân lớp hỗn hợp giữa thống kê - cấu trúc. Các kết quả nhận
đƣợc từ ba thuật toán trên đƣợc kết nối lại theo một trình tự thích hợp. Kết quả cho
thấy tốc độ nhận dạng tăng lên đáng kể.
1.1.4. Một số khó khăn trong nhận dạng
- Sự che khuất: Ảnh có thể bị chèn bởi ảnh khác, hoặc bị cắt một phần ảnh
- Hƣớng của ảnh: Ảnh có thể bị xoay chiều, không đúng so với chiều gốc do
quá trình chụp, scan.
- Điều kiện chụp, scan ảnh: Ảnh đƣợc chụp, scan trong các điều kiện khác
nhau về ánh sáng, tính chất của máy scan nên ảnh hƣởng nhiều đến chất lƣợng ảnh.
Khó khăn khi nghiên cứu bài toán nhận dạng chữ viết tay là sự biến thiên đa
dạng trong cách viết của từng ngƣời. Cùng một ngƣời viết nhƣng đôi khi cũng có
nhiều sự khác biệt trong cách viết tuỳ thuộc vào từng ngữ cảnh, kiểu viết của một
13

S
ố hóa bởi Trung tâm Học liệu

ngƣời cũng có thể thay đổi theo thời gian hoặc theo thói quen. Điều này gây ra nhiều
trở ngại trong việc trích chọn đặc trƣng cũng nhƣ lựa chọn mô hình nhận dạng.
1.2. Kỹ thuật SVM trong nhận dạng
1.2.1. Kỹ thuật SVM
Support Vector Machine (SVM) là một phuơng pháp phân lớp dựa trên lý

thuyết học thống kê, đƣợc đề xuất bởi Vapnik (1995) [5], [6]. Ý tƣởng chính của
thuật toán này là cho trƣớc một tập huấn luyện đƣợc biểu diễn trong không gian
vector trong đó mỗi tài liệu là một điểm, phƣơng pháp này tìm ra một mặt phẳng
quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt
tƣơng ứng lớp + và lớp Chất lƣợng của siêu mặt phẳng này đƣợc quyết định bởi
khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến mặt phẳng
này. Khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt đồng thời việc
phân loại càng chính xác. Mục đích thuật toán SVM tìm ra đƣợc khoảng cách biên
lớn nhất để tạo kết quả phân lớp tốt [6].
SVM sử dụng thuật toán học nhằm xây dựng một siêu phẳng làm cực tiểu
hoá độ phân lớp sai của một đối tƣợng dữ liệu mới. Độ phân lớp sai của một siêu
phẳng đƣợc đặc trƣng bởi khoảng cách bé nhất tới siêu phẳng đấy. SVM có khả
năng rất lớn cho các ứng dụng đƣợc thành công trong bài toán phân lớp văn bản.
Phân lớp văn bản là một cách tiếp cận mới để tạo ra tập phân lớp văn bản từ các
mẫu cho trƣớc. Cách tiếp cận này phối hợp với sự thực thi ở mức độ cao và hiệu
suất cùng với những am hiểu về mặt lý thuyết, tính chất thô ngày càng đƣợc hoàn
thiện. Thông thƣờng, hiệu quả ở mức độ cao không có các thành phần suy nghiệm.
Phƣơng pháp SVM có khả năng tính toán sẵn sàng và phân lớp, nó trở thành lý
thuyết học mà có thể chỉ dẫn những ứng dụng thực tế. Đặc trƣng cơ bản quyết định
khả năng phân lớp là khả năng phân lớp những dữ liệu mới dựa vào những tri thức
đã tích luỹ đƣợc trong quá trình huấn luyện. Sau quá trình huấn luyện nếu hiệu suất
tổng quát hoá của bộ phân lớp cao thì thuật toán huấn luyện đƣợc đánh giá là tốt.
Hiệu suất tổng quát hoá phụ thuộc vào hai tham số là sai số huấn luyện hay và năng
14

S
ố hóa bởi Trung tâm Học liệu

lực của máy học. Trong đó sai số huấn luyên là tỷ lệ lỗi phân lớp trên tập dữ liệu
huấn luyện. Còn năng lực của máy học đƣợc xác định bằng kích thƣớc Vapnik -

Chervonenkis (kích thƣớc VC) [7], [8]. Kích thƣớc VC là một khái niệm quan trọng
đối với một họ hàm phân tách (hay là tập phân lớp). Đại lƣợng này đƣợc xác định
bằng số điểm cực đại mà họ hàm có thể phân tách hoàn toàn trong không gian đối
tƣợng. Một tập phân lớp tốt là tập phân lớp đơn giản nhất và đảm bảo sai số huấn
luyện nhỏ. Phƣơng pháp SVM đƣợc xây dựng trên ý tƣởng này.
1.2.2. Một số ứng dụng của SVM
1.2.2.1. Chẩn đoán Virus máy tính
Ngày nay, cùng với sự phổ biến của mạng Internet, virus máy tính đã trở
thành một vấn đề cấp bách. Các hoạt động lây nhiễm, phá hoại, đánh cắp dữ liệu
của virus máy tính ngày càng lan rộng và phổ biến, ảnh hƣởng trực tiếp đến vấn đề
an ninh mạng và an toàn dự liệu cho nhiều hệ thống công nghệ thông tin trên quy
mô toàn cầu. Trƣớc tình hình đó, các hệ chống virus (thƣờng gọi là anti-virus - AV)
cần cải tiến phƣơng pháp và công nghệ nhằm đạt mục tiêu: chủ động, nhanh chóng,
hiệu quả và an toàn.
Chẩn đoán virus máy tính là một quá trình xử lý phức tạp thực hiện qua
nhiều giai đoạn. Có rất nhiều loại virus máy tính. Mỗi loại có phƣơng pháp, hành vi
lây nhiễm trên nhiều đối tƣợng khác nhau. Do tính liên tục của quy trình chẩn đoán,
độ chính xác của bài toán phụ thuộc vào kết quả xử lý từng giai đoạn và đặc điểm
xử lý, mỗi giai đoạn có thể áp dụng nhiều tiếp cận, giải pháp khác nhau. Để gia tăng
tốc độ chẩn đoán cũng nhƣ đảm bảo độ chính xác cao, chúng ta có thể thực hiện
phƣơng pháp NNSRM (Nearest Neighbor Rule-based Structural Risk Minimization
- Cực tiểu rủi ro cấu trúc dựa vào luật láng giềng gần nhất) [3] sử dụng hàm đa thức
cho giai đoạn nhận dạng đối tƣợng.
Cho trƣớc tập các đối tƣợng chẩn đoán {x
1
, x
2
, x
3
,…,x

n
} là các vectơ trong
không gian X. Mục tiêu của giai đoạn nhận dạng đối tƣợng là phân tích các đặc
trƣng giống nhau giữa các x
i
để phân chúng vào lớp 1- Có thể nhiễm lớp virus V
15

S
ố hóa bởi Trung tâm Học liệu

hoặc Lớp 2- Không nhiễm lớp virus V. Ý tƣởng ứng dụng kỹ thuật phân lớp này dựa
vào tính chất miễn nhiễm của một số đối tƣợng đặc biệt, nhằm thỏa mãn yêu cầu
giảm số lƣợng các điểm mô tả dữ liệu khi hoạt động trên các tập dữ liệu lớn. Để đạt
đƣợc quy luật phân lớp tổng quát, chúng ta thực hiện giải thuật NNSRM trên không
gian chuẩn đoán với giá trị tối thiểu của sai số thực nghiệm R
emp
(fs) → 0.
Vai trò của SVM trong giải quyết bài toán
Với các hàm đa thức bậc cao hơn nếu tăng số chiều của không gian chuyển
đổi thì sẽ làm mất tính tổng quát. Tuy nhiên hàm phân lớp SVM thực thi tốt hơn với
dữ liệu tổng hợp có các hàm đa thức bậc cao (số chiều dữ liệu tăng) trong khi công
cụ phân lớp NNSRM [6] giảm đi mức độ chính xác (dù với số lƣợng nhỏ) do bản
chất xấp xỉ của giải pháp NNSRM.
Với phƣơng pháp SVM, sự thực thi bắt đầu giảm sút khi số bậc cao mở rộng
và còn phụ thuộc vào việc chọn các tham số hợp lý để đảm bảo thu đƣợc kết quả.
1.2.2.2. Phân loại email [6]
Lọc thƣ rác
Sự phát triển của các dịnh vụ thông tin trên Internet và nhu cầu trao đổi
thông tin làm cho các hệ thống thƣ điện tử phát triển mạnh. Song song với sự phát

triển đó, nạn thƣ rác ngày càng gây nhiều thiệt hại cho cộng đồng ngƣời sử dụng
nhƣ: làm hao phí tài nguyên của mạng máy tính, làm mất thời gian của ngƣời dùng
và thậm trí có thể phát tán những thông tin văn hóa độc hại. Vì vậy, việc xây dựng
các giải pháp tự động lọc và chống thứ rác dựa trên các phƣơng pháp phân loại văn
bản, tức là gán văn bản vào một hoặc một số nhóm văn bản đã đƣợc biết trƣớc.
Đối với bài toán lọc thƣ rác, đầu vào là các bức thƣ điện tử đƣợc gửi trên
mạng Internet. Thông thƣờng, có hai nhóm văn bản là thƣ rác (Spam mail) và thƣ
sạch. Việc xác định nhóm thƣ rác thƣờng không có một định nghĩa chính xác, nó
thay đổi theo từng đối tƣợng và hoàn cảnh. Theo định nghĩa thông thƣờng, đó là các
thƣ có nội dung văn hóa độc hại, quảng cáo đƣợc phát tán với số lƣợng lớn, các thƣ
tuyên truyền với mục đích xấu,… Vì vậy, một hệ thống phân loại tự động có khả
16

S
ố hóa bởi Trung tâm Học liệu

năng học để thích nghi là cần thiết cho các hệ thống thƣ điện tử. Phƣơng pháp dùng
SVM khá hiệu quả trong việc phân loại thƣ rác, vì về bản chất nó vẫn là phƣơng
pháp sử dụng thống kê nên có những ƣu điểm nhất định.
Ta biểu diễn các thƣ nhận đƣợc dƣới dạng các vector. Giả sử ta có một tập
thuật ngữ T= {t
1
, t
2
,…t
n
} mỗi văn bản d
i
đƣợc biểu diễn bởi một vectơ x
i

= {w
i1
,
w
i2
, w
in
} trong không gian vectơ, trong đó w
ij
là trọng số của thuật ngữ trong văn
bản. Tọa độ của mỗi vectơ tƣơng ứng với tọa độ của một điểm dữ liệu trong không
gian n chiều R
n
. Khi đó bài toán đặt ra là kiểm tra xem một văn bản có thuộc hay
không thuộc vào một nhóm cho trƣớc: Những văn bản nào thuộc nhóm đang xét thì
đƣợc gán nhãn 1 (gọi là những điểm dữ liệu dƣơng), ngƣợc lại thì gán nhãn -1 (gọi
là những điểm dữ liệu âm).
Dữ liệu huấn luyện của SVM là tập các văn bản đã đƣợc gán nhãn trƣớc:
Tr = {(x
1
, y
1
), (x
2
, y
2
),…, (x
m
,y
m

)}
Trong đó x
i
là vectơ dữ liệu biểu diễn văn bản d
i
với x
i
Î
R
n
và y
i
Î
{-1,1}. Cặp
(x
i
, y
i
) đƣợc hiểu là vectơ x
i
(hay văn bản d
i
) đƣợc gán nhãn là y
i
. Từ đó, ứng dụng
phƣơng pháp SVM để tìm một siêu phẳng f(x) “tốt nhất” trong không gian n-chiều
nhằm phân chia dữ liệu sao cho tất cả các điểm dữ liệu x “dƣơng” đƣợc gán nhãn 1
thuộc về phía dƣơng của siêu phẳng (f(x)>0), còn các điểm x “âm” đƣợc gán nhãn
-1 thuộc về phía âm của siêu phẳng (f(x)<0). Một siêu phẳng phân chia dữ liệu đƣợc
gọi là “tốt nhất”nếu khoảng cách từ điểm dữ liệu gần nhất đến siêu phẳng là lớn

nhất. Khi đó, việc xác định một tài liệu x
Î
Tr có thuộc phân loại
l
hay không tƣơng
ứng với việc xét dấu của f(x): nếu f(x)>0 thì x
Î l
, nếu ngƣợc lại thì x
Ï
l
.
So sánh với cách tiếp cận khác dùng để phân lớp và lọc thƣ rác thì việc sử
dụng phƣơng pháp SVM có những tiện ích, phù hợp với yêu cầu của ngƣời dùng. Ở
đây, tiêu chuẩn phân loại có thể đƣợc học từ các ví dụ mẫu học riêng của từng
ngƣời dùng, vì thế mỗi ngƣời hay mỗi đơn vị có thể tạo đƣợc cách lọc thƣ rác riêng
của mình. Đồng thời sự mềm dẻo của nó cũng giúp dễ dàng cho việc điều chỉnh
tƣơng thích với sự xuất hiện của các loại thƣ rác mới. Trong khi các công cụ khác