Mục Lục
I. Tổng quan và lý do chọn đề tài.
1. Tổng quan.
- Máy học là một nhóm công cụ không thể thiếu trong quá trình khám phá tri
thức, đặc biệt là trong trường hợp dữ liệu cần khám phá rất lớn và mỗi mẫu dữ liệu
mang rất nhiều thông tin và các thông tin này lại nằm trên một miền liên tục, khi
đó việc sử dụng cây định dạnh hoặc rút trích luật là vô cùng khó khăn.
- Các hệ thống máy học thường được dùng để tích lũy các dạng tri thức
không tường minh trên một lượng dữ liệu lớn và đã được áp dụng rất thành công
cho nhiều bài toán khác nhau như: phân lớp dữ liệu, detect đối tượng chuyển động
trên ảnh hoặc video động, nhận dạng mặt người hoặc các đối tượng như biển số
xe, chướng ngại vật,
- Các hệ thống máy học ra đời dựa trên nhiều tư tưởng tiếp cận khác nhau
như:
o Mô phỏng theo một phần cấu trúc của não người: Mạng neural nhân tạo.
o Dựa trên việc tổng hợp các thông tin/tri thức ít quan trọng theo một cách
hợp lý để tạo ra tri thức quan trọng hơn: Phương pháp boosting.
o Dựa trên các nền tảng hình học và lý thuyết tối ưu: Các hệ thống máy học
dùng vector hỗ trợ.
o Dựa trên nền tảng toán học xác suất: Các hệ thống dựa trên mô hình
Markov như xích Markov và trường ngẫu nhiên Markov.
o Ngoài ra còn rất nhiều mô hình khác nhau được đưa ra nhằm mục tiêu
chính là trích xuất các tri thức dưới dạng ánh xạ từ dữ liệu đầu vào ra thành
các quyết định, các lớp, hay cường độ của thuộc tính ngữ nghĩa nào đó.
1
- Dựa trên vai trò của hệ thống máy học trong các phương pháp rút trích tri
thức, tác giả chọn đề tài áp dụng máy học SVM cho bài toán phân lớp các loại
hoa, đề tài này có thể áp dụng cho các vấn đề khác trong thực tế như phân lớp các
loại trái cây hay côn trùng gây hại, Do đặc trưng của bài toán này đó là đầu vào
là ảnh của các loại hoa, ảnh được biểu diễn theo dạng ma trận rời rạc với các pixel
là các giá trị màu trong đoạn nguyên [0:255], do đó việc áp dụng các phương pháp

khoảng cách theo thứ tự tăng dần và xác định K láng giềng gần nhất với đối
tượng cần phân lớp.
o B3: Lấy tất cả các lớp của K láng giềng gần nhất đã xác định.
o B4: Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho các
đối tượng cần phân lớp.
a) Phương pháp K-Means
- K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong việc
giải quyết các bài toán phân lớp. Tư tưởng chính của thuật toán K-Means là tìm
cách phân nhóm các đối tượng đã cho vào K cụm (K là số các cụm được xác định
trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối
tượng đến tâm của nhóm là nhỏ nhất.
- Thuật toán K-Means thực hiện qua các bước chính sau:
o B1: Chọn ngẫu nhiên K tâm cho K cụm. Mỗi cụm được đại diện bằng các
tâm của cụm.
o B2: Tính khoảng cách giữa các đối tượng đến K tâm (thường dùng khoảng
cách Euclidean)
o B3: Nhóm các đối tượng vào nhóm gần nhất.
3
o B4: Xác định lại tâm mới cho các nhóm.
b) Phương pháp mạng neural nhân tạo (ANN)
- Một cách tiếp cận khá phổ biến hiện nay dùng phương pháp mạng Neural
nhân tạo cho bài toán phân lớp mẫu. Với cách tiếp cận này một mạng Neural nhân
tạo sẽ được huấn luyện với tập mẫu để tìm ra bộ trọng số phục vụ cho quá trình
phân lớp. Với bài toán phân lớp ảnh kích thước ảnh lớn (không gian biểu diễn mẫu
có nhiều chiều) các phương pháp truyền thống K-NN và K-Means sẽ không thích
hợp. Quá trình phân lớp ảnh sẽ được chia ra làm 2 giai đoạn: (1) xây dựng không
gian biểu diễn ảnh; (2) áp dụng mạng Neural nhân tạo phân lớp ảnh.
o Giai đoạn (1): Xây dựng không gian biểu diễn ảnh. Một ảnh ban đầu sẽ
được tách thành m ảnh con. Mỗi ảnh con sẽ trích chọn ra một vector đặc
trưng tương ứng. Các vector này đại diện cho ảnh ban đầu. Như vậy, ảnh

gọi là biên) từ đ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ì càng có sự phân chia tốt các điểm ra thành hai lớp, nghĩa là sẽ
đạt được kết quả phân lớp tốt. Mục tiêu của phương pháp SVM là tìm được
khoảng cách biên lớn nhất để tạo kết quả phân lớp tốt nhất.
5
Một ví dụ về biên tối ưu.
- Với những yêu cầu như trên bài toán đặt ra tìm siêu phẳng tách:
h(x) = w
T
x + b
với: trong đó:
Trong đó:
w: vector trọng số (weight vector).
b: trọng số ngưỡng (threshold weight).
- SVM là một phương pháp phân lớp phổ biến hiện nay, với khả năng vượt
trội của SVM về tính hiệu quả, độ chính xác và khả năng xử lý các bộ dữ liệu một
cách linh hoạt. Việc sử dụng SVM đã và đang là sự lựa chọn tối ưu nhất trong việc
giải quyết các bài toán phân loại, dự báo trong một số các ngành khoa học. Trong
phạm vi đề tài này sẽ tìm hiểu và phát triển phương pháp phân lớp ảnh sử dụng
SVM.
3. Máy học sử dụng vector hỗ trợ (SVM).
- Trong phần này đề tài sẽ trình bày một cách chi tiết hơn về phương pháp
SVM phục vụ cho việc phân lớp.
- SVM là phương pháp học có giám sát được sử dụng rộng rãi trong lĩnh vực
phân lớp mẫu và nhận dạng mẫu. SVM là một họ các phương pháp dựa trên cơ sở
các hàm nhân (kernel methods) để tối thiểu hoá rủi ro ước lượng. Phương pháp
này được Boser, Guyon, và Vapnik giới thiệu lần đầu tiên vào năm 1995 để giải
quyết vấn đề phân lớp mẫu hai lớp sử dụng nguyên tắc cực tiểu hóa rủi ro cấu
6
trúc (Structural Risk Minimization). Đây là phương pháp tiếp cận phân loại

∈ {+1,-1}, cặp (x
i
, y
i
) được hiểu là vector x
i
được
gán nhãn là y
i
.
- 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. Phương trình tổng quát của
một siêu phẳng phân chia như vậy được biểu diễn có dạng như sau:
w
T
x + b = 0 (1)
Trong đó:
W
T
: Vector trọng số, W
T
= {w
1
, w
2
,…,w
n
}.
n: Số thuộc tính (hay còn gọi là số chiều của dữ liệu).
b: Bộ trọng số.

Trong đó: w
0
tương đương với hằng số b trong PT tổng quát của siêu phẳng.
Vì vậy mỗi điểm nằm trên siêu phẳng phân cách thỏa mãn:
(3)
Tương tự, những điểm nằm dưới siêu phẳng phân cách phải thỏa mãn:
(4)
Bằng cách điều chỉnh trọng số w
0
ta có:
Đường biểu diễn H
1
và H
2
, đường màu đỏ là khoảng cách Euclidean của hai
điểm 1 và 2. Đường màu xanh là khoảng cách Euclidean nhỏ nhất.
8
- Điều này có nghĩa là nếu bất kì bộ nào nằm tại hoặc trên H
1
đều thuộc về
lớp +1, và bất kì bộ nào nằm tại hoặc dưới H
2
đều thuộc về lớp -1. Kết hợp 2 bất
đẳng thức trên ta có:
(5)
- Mỗi bộ huấn luyện nằm tại các mặt biên H
1
hay H
2
thỏa mãn phương trình

d) Mô hình phân lớp tuyến tính
- Tập dữ liệu D có thể phân chia tuyến tính được mà không có nhiễu (tất cả
các điểm được gán nhãn +1 thuộc về phía dương của siêu phẳng, tất cả các điểm
được gán nhãn –1 thuộc về phía âm của siêu phẳng).
Tập dữ liệu có thể được phân chia tuyến tính.
- SVM biên cứng được áp dụng đối với dữ liệu khả tách tuyến tính và nó cho
kết quả phân lớp một cách chính xác đối với tất cả các dữ liệu dạng này. Ta sẽ tìm
siêu phẳng tách với w∈R
n
là vector trọng số (weight vector), b∈R là hệ số tự do,
sao cho:
(6)
10
Lúc này, để có (1), ta giải bài toán tối ưu:
(7)
Để giải quyết bài toán này người ta đưa ra hàm Lagrange:
(8)
Điều kiện Kuhn Tucker (cần và đủ)
Với
Ta có ↔ với
Vậy bài toán đối ngẫu tương đương là:
Khi đó , b = y
i
– w
T
x
i
tại α
i
> 0

(w
T
.x
i
+ b)≥ 1 bằng ràng buộc:
y
i
(w
T
.x
i
+ b) ≥ 1 - ξ
i
i = 1, …, l (9)
Ở đây, ξ
i
gọi là các biến slack (slack variable), ξ
i
≥ 0.
Bài toán tối ưu trở thành: (10)
- Trong đó, C là tham số xác định trước, định nghĩa giá trị ràng buộc, C càng
lớn thì mức độ vi phạm đối với những lỗi thực nghiệm càng cao. Lỗi thực nghiệm
12
(empirical error) hay còn gọi là lỗi huấn luyện (training error) hoặc rủi ro thực
nghiệm (empirical risk) là lỗi xảy ra lúc huấn luyện, tính bằng thương số của số
phần tử lỗi và tổng số phần tử huấn luyện.
Từ đó ta có bài toán đối ngẫu sau : (11)
Đây là dạng mô hình SVM tổng quát giải quyết đồng thời hai mục tiêu: độ
rộng lớn nhất và lỗi tách là bé nhất.
f) Mô hình phân lớp phi tuyến

, x
j
)=(x
i
x
j
+k)
d
- Trong đó, k thường được chọn là 0 (đồng nhất) hoặc 1 (không đồng nhất).
Không gian đặc trưng cho các hàm kernel không đồng nhất bao gồm các đơn thức
bậc nhỏ hơn d (Schölkopf và Smola, 2002). Nhưng thời gian tính toán của nó là
tuyến tính với số chiều của không gian đầu vào.
- Kernel với d=1 và k=0 (biểu hiện bằng K
linear
) là kernel tuyến tính dẫn đến
một hàm phân tách tuyến tính. Bậc của kernel đa thức kiểm soát sự linh hoạt của
bộ phân lớp. Đa thức bậc thấp nhất là kernel tuyến tính. Hàm kernel này không đủ
tốt nếu không gian đặc trưng là phi tuyến.
14
Mức độ tác động của kernel đa thức.
Kernel đa thức dẫn đến một sự phân tách tuyến tính (A).
Kernel đa thức cho phép một ranh giới quyết định linh hoạt hơn (B-C).
- Đối với các dữ liệu trong hình trên, ở đa thức bậc 2 đã đủ linh hoạt để
phân biệt giữa hai lớp với một biên tốt. Đa thức bậc 5 định lượng một ranh giới
quyết định tương tự, với độ cong lớn hơn. Quá trình chuẩn hóa có thể giúp cải
thiện hiệu suất và ổn định d.
 Gaussian kernel:
K
σ
Gaussian

pháp này tạo ramỗi bộ phân loại nhị phân cho từng cặp phân lớp.Ứng với mỗi cặp
phân lớp C
ij
, một bộ SVM C
ij
được thiết lập sẽ phân lớp thứ i và lớp thứ j.Khi đưa
mẫu x vào phân loại, nếu bộ phân loại nhị phân C
ij
quyết địnhx thuộc về phân lớp i
thì giá trị bầu cử của phân lớp i (vote i) sẽ được tăng lên 1, ngược lại giá trị bầu cử
của phân lớp j (vote j) sẽ được tăng lên 1. Phương pháp này sẽ quyết định mẫu x
thuộc về phân lớp có giá trị bầu cử lớn nhất (giá trị vote lớn nhất).Khi đó, nếu có c
phân lớp thì sẽ có tất cả
2
)1( −cc
bộ phân loại nhị phân.
- Thuật toán cho phương pháp phân loại theo từng cặp:
 Giả sử có c phân lớp, mẫu cần phân lớp là X.
 Tính các hàm phân biệt giữa 2 phân lớp i, j bất kì:
 (1, 2), (1, 3), …., (1, c), (2, 3), …, (c-1, c)
 Như vậy có tất cả
2
)1( −cc
hàm phân biệt (tương ứng với
2
)1( −cc

cặp).
16
 Khởi tạo mảng vote với c phần tử. Giá trị ban đầu bằng 0.

lớp sẽ được giảm bớt so với các phương pháp one-vs-rest.
j) Nhận xét
- Giống như các phương pháp máy học khác, để phương pháp SVM hoạt
động tốt nó phải được huấn luyện trên một bộ dữ liệu lớn, bao quát đầy đủ các
trường hợp.
- Ưu điểm của phương pháp này là có độ chính xác cao. Tuy nhiên nó gặp
phải khuyết điểm là tốn thời gian và chi phí cho việc huấn luyện.
III. Chương trình minh họa.
- Chương trình minh họa cho bài toán phân lớp áp dụng bộ phân lớp SVM
được xây dựng từ thư viện Aforge.NET, các ảnh đầu vào được lấy đặc trưng như
sau:
17
o Mỗi ảnh sẽ được tách thành 3 ảnh theo 3 kênh màu sau đó các ảnh của từng
kênh sẽ được dùng để huấn luyện trên 3 bộ SVM khác nhau.
o Ở giai đọan phân lớp, ảnh đầu vào cụng 4 được tách kênh màu và dùng 3
bộ phân lớp đã huấn luyện để phân lớp, kết quả cuối cùng sẽ được tổng hợp
lại theo tiêu chí chọn đa số.
- Giao diện của chương trình như sau:
Màn hình chính của chương trình.
18
Màn hình trích chọn đặc trưng màu sắc của ảnh hoa theo từng hệ màu.
Màn hình huấn luyện và phân lớp ảnh hoa.
19
Màn hình phân lớp ảnh hoa.
IV. Tài liệu tham khảo
Tiếng việt
[1] P.T.Bình(2007), Phân loại văn bản bằng phướng pháp Support Vector Machine,
trường đại học Nha Trang, khoa Công nghệ Thông tin.
[2] Lê Hoàng Thái, Trần Sơn Hải (2009), “Phát Triển Mô Hình Liên Kết Mạng Áp Dụng
Cho Bài Toán Phân Lớp Ảnh”, Kỷ yếu hội thảo @ Một số vấn đề chọn lọc về Công