ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

ĐẶNG ĐÌNH TUYẾN

PHÂN LỚP VĂN BẢN NHỜ MÁY VÉC – TƠ HỖ TRỢ VỚI HÀM STRING
KERNEL

Chuyên ngành: Khoa học máy tính

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

Người hướng dẫn khoa học: PGS.TS.Nguyễn Tân Ân

THÁI NGUYÊN - 2016
Số hóa bởi Trung tâm Học liệu – ĐHTN




ii
LỜI CẢM ƠN
Luận văn được hoàn thành tại trường Đại học Công nghệ Thông tin và Truyền
thông Thái Nguyên.
Tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn khoa học:
PGS.TS Nguyễn Tân Ân đã tận tình hướng dẫn, giúp đỡ và tạo mọi điều kiện để tác
giả thực hiện luận văn này. Tác giả cũng xin chân thành cảm ơn tập thể các thầy cô
giáo trong khoa CNTT, phòng quản lý sau đại học Trường Đại học Công nghệ
Thông tin và Truyên thông Thái Nguyên đã tạo mọi điều kiện giúp đỡ cho tác giả
nghiên cứu, học tập và hoàn thành luận văn.
Xin cảm ơn gia đình, bạn bè, đồng nghiệp đã tạo điều kiện thuận lợi về tinh

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




iv
MỤC LỤC
LỜI CẢM ƠN .............................................................................................................. i
LỜI CAM ĐOAN................................................................................................... iii
MỤC LỤC .................................................................................................................. iv
DANH MỤC HÌNH ẢNH ......................................................................................... vi
DANH MỤC BẢNG BIỂU ......................................................................................vii
CHƯƠNG 1: BÀI TOÁN PHÂN LỚP ....................................................................... 1
1.1. Nội dung bài toán phân lớp .................................................................................. 1
1.2. Các phương pháp phân lớp ................................................................................... 2
1.2.1. Phương pháp Naïve Bayes (NB) ...................................................................2
1.2.2. Phương pháp K–Nearest Neighbor (kNN) ....................................................3
1.2.3. Neural Network (NNet) .................................................................................5
1.2.4. Centroid- based vector ...................................................................................6
1.3. Máy véc-tơ hỗ trợ (Support Vector Machine SVM) ............................................ 7
1.3.1. Bài toán phân loại SVM ................................................................................7
1.3.2. Ý tưởng của SVM ..........................................................................................8
1.3.3. Phương pháp tìm α*, b. ................................................................................16
1.3.4. SVM đối với bài toán nhiều lớp ..................................................................21
1.3. Kết luận .............................................................................................................. 24
CHƯƠNG 2: NHỮNG KIẾN THỨC CƠ SỞ .......................................................... 25
2.1. Hàm Kernel ........................................................................................................ 25
2.1.1. Không gian gốc, không gian đặc trưng ........................................................25
2.1.2. Định nghĩa kernel ........................................................................................26
2.1.3. Một số ví dụ về Ф và k(,) .............................................................................26





vi

DANH MỤC HÌNH ẢNH
Hình 1.1: Kiến trúc mô đun (Modular Architecture). Các kết quả của từng mạng con
sẽ là giá trị đầu vào cho mạng siêu chủ đề và được nhân lại với nhau để dự đoán
chủ đề cuối cùng. .........................................................................................................6
Hình 1.2: Các trường hợp của siêu mặt h phân chia tập dữ liệu D trong SVM. .........8
Hình 1.3: Siêu mặt phân chia tập mẫu huấn luyện với 2 lớp là lớp + 1 hình vuông và
lớp – 1 hình tròn. .........................................................................................................9
Hình 1.4: Siêu phẳng tuyến tính phân chia dữ liệu, m là khoảng cách giữa hai lề ...10
Hình 1.5: Nguyên lý cơ bản của phương pháp một-chọi-phần còn lại cho ba lớp ...22
Hình 1.6: Nguyên lý cơ bản của phương pháp phân chia môt-chọi-một ..................22
Hình 1.7: Biểu diến phương pháp END để phân chia ba trạng thái của bài toán dự
đoán trong phân lớp...................................................................................................24
Hình 2.1: Mỗi điểm dữ liệu được ánh xạ bằng một hàm không tuyến tính Ф từ
không gian dữ liệu X vào không gian đặc trưng F. Trong đó Ф(x) và Ф(o) là các
véc-tơ đặc trưng của các điểm dữ liệu gốc x và o .....................................................26
Hình 2.2: Ánh xạ dữ liệu từ không gian đầu vào R2 sang không gian dữ liệu R3 .....27
Hình 2.3: Kernel đa thức bậc hai ánh xạ từ không gian hai chiều vào không gian đặc
trưng 3 chiều..............................................................................................................29
Hình 2.4: Dữ liệu được tách thành hai lớp trong không gian ban đầu ......................31
Hình 3.1: Trang web Du lịch Khát vọng Việt ...........................................................50
Hình 3.2: Trang web taxinoibaiphuonglong.com .....................................................52
Hình 3.3: Trang web vietnamtourism.com ...............................................................55

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

(attributes) cho mộ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ào cá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 đối tượng chứa trong lớp đó. Ví dụ: phân lớp văn bản, tế bào để
xác định tế bào ung thư.
Phân lớp còn được gọi là phân lớp có giám sát (supervised classification), là
một trong những lĩnh vực phổ biến nhất của học máy (machine learning) và khai
thác dữ liệu (data mining). Nó giải quyết việc xác định những quy tắc giữa số lượng
biến số độc lập và kết quả đạt được hay một biến số xác định phụ thuộc trong tập
dữ liệu được đưa ra. Tổng quát, đưa ra một tập mẫu học

x ,x
i1

i2



,..., xik , yi ,

i=1,….,N, nhiệm vụ là phải ước lượng được một bộ phân lớp hay một mô hình xấp
xỉ một hàm y = f(x) chưa biết mà phân lớp chính xác cho bất kỳ mẫu nào thuộc tập
các mẫu học. Có nhiều cách để biểu diễn một mô hình phân lớp và có rất nhiều
thuật toán giải quyết nó. Các thuật toán phân lớp 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ập này xây dựng những mô hình đều có khả năng
phân lớp cho một mẫu mới chưa biết dựa vào những mẫu tương tự đã được học.
Bài toán phân lớp có thể xử lý thông tin đượ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 được biể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ác phần tử trong bảng là các giá trị
xác định các thuộc tính (attributes hay features) của các đối tượng. Trong đó số cột


H BAYES




d'
d'
'
 Pr(C j ).  Pr(w i | C j ) 
 Pr(C j ).  Pr(w i | C j ) IF (w,d )
i 1
i 1
  arg max 
 arg max 
d'
d'
'
'

C j C
C j C 
'
' 
'
' IF ( w , d )
Pr(
C
).









3
Pr(Cj) được tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp

Pr(C j ) 

|| C j ||
|| C ||



|| C j ||

 || C

'

||

tương ứng với tập dữ liệu huấn luyện.

C 'C




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




4

* Ý tưởng
Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng
cách Euclide, Cosine ...) của tất cả các văn bản trong tập huấn luyện đến văn bản
này để tìm ra k văn bản gần nhất (gọi là k “láng giềng”), sau đó dùng các khoảng
cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất
cả khoảng cách ở trên của các văn bản trong k láng giềng có cùng chủ đề, chủ đề
nào không xuất hiện trong k láng giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ
được sắp xếp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ được
chọn là chủ đề của văn bản cần phân loại.
* Công thức


Trọng số của chủ đề cj đối với văn bản x :

 
     
w  x , c j    sim  x , di  . y  di , c j   b j



 


định và sai sót càng thấp ( theo Yang trình bày năm 1997). Giá trị tốt nhất được sử
dụng trên hai bộ dữ liệu Reuter và Oshumed là k=45.
Số hóa bởi Trung tâm Học liệu – ĐHTN




5
1.2.3. Neural Network (NNet)
Nnet được nghiên cứu mạnh trong hướng trí tuệ nhân tạo. Wiener là người đã
sử dụng Nnet để phân loại văn bản, sử dụng 2 hướng tiếp cận : kiến trúc phẳng
(không sử dụng lớp ẩn) và mạng nơron 3 lớp (bao gồm một lớp ẩn)(theo Wiener
trình bày năm 1995)
Cả hai hệ thống trên đều sử dụng một mạng nơron riêng rẽ cho từng chủ đề,
NNet học cách ánh xạ phi tuyến tính những yếu tố đầu vào như từ, hay mô hình
vector của một văn bản vào một chủ đề cụ thể.
Khuyết điểm của phương pháp NNet là tiêu tốn nhiều thời gian dành cho việc
huấn luyện mạng nơron.
* Ý tưởng
Mô hình mạng neural gồm có ba thành phần chính như sau: kiến trúc
(architecture), hàm chi phí (cost function), và thuật toán tìm kiếm (search
algorithm). Kiến trúc định nghĩa dạng chức năng (functional form) liên quan giá trị
nhập (inputs) đến giá trị xuất (outputs).
Kiến trúc phẳng ( flat architecture ) : Mạng phân loại đơn giản nhất ( còn gọi
là mạng logic) có một đơn vị xuất là kích hoạt kết quả (logistic activation) và không
có lớp ẩn, kết quả trả về ở dạng hàm (functional form) tương đương với mô hình
hồi quy logic. Thuật toán tìm kiếm chia nhỏ mô hình mạng để thích hợp với việc
điều chỉnh mô hình ứng với tập huấn luyện. Ví dụ, chúng ta có thể học trọng số
trong mạng kết quả (logistic network) bằng cách sử dụng không gian trọng số giảm
dần (gradient descent in weight space) hoặc sử dụng thuật toán interatedreweighted least squares là thuật toán truyền thống trong hồi quy (logistic

điều kiện p

(0,1).

1.2.4. Centroid- based vector
Là một phương pháp phân loại đơn giản, dễ cài đặt và tốc độ nhanh do có độ
phức tạp tuyến tính O(n) ( được Han trình bày năm 2000)
* Ý tưởng
Mỗi lớp trong dữ liệu luyện sẽ được biểu diễn bởi một vector trọng tâm. Việc
xác định lớp của một văn bản thử bất kì sẽ thông qua viêc tìm vector trọng tâm nào
gần với vector biểu diễn văn bản thử nhất. Lớp của văn bản thử chính là lớp mà
vector trọng tâm đại diện. Khoảng cách được tính theo độ đo cosine.


C
i

1
i



d j ei

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



dj


Chủ đề của x là Cx thoả cos  x , Ci  arg max  cos  x, Ci  






1.3. Máy véc-tơ hỗ trợ (Support Vector Machine SVM)
1.3.1. Bài toán phân loại SVM
Máy véc-tơ hỗ trợ có thể được hiểu là kỹ thuật giải quyết bài toán sau:” Giả sử
chúng ta có tập dữ liệu D gồm 2 loại đối tượng là O1 và O2 trong không gian Rn,
hãy tìm một siêu mặt h chia tập D thành 2 phần rời nhau và khi chúng ta có một đối
tượng mới b chúng ta phải trả lời được b thuộc loại O1 hay O2, nếu b thuộc O1 thì
được gán nhãn là 1, ngược lại b được gán nhãn là -1?”. Siêu mặt h mà chúng ta cần
tìm gồm có các trường hợp sau:

Siêu phẳng h là (b) Siêu phẳng h là đường (c) Siêu phẳng h là đường
cong được ánh xạ vào
đường thẳng
cong
không gian mới thành
(a)

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




8
đường thẳng

nhất, nếu khoảng cách từ điểm dữ liệu gần nhất đến siêu mặt là gần nhất. Khi đó,
việc xác định một dãy xk

D có thuộc phân loại c hay không, tương ứng với việc

xét dấu của f(xk), nếu f(xk) > 0 thì xk

c, nếu f(xk) ≤ 0 thì xk

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

c.




9

Hình 1.3: Siêu mặt phân chia tập mẫu huấn luyện với 2 lớp là lớp + 1 hình vuông
và lớp – 1 hình tròn.
Trong hình 1.3: - Hình tô đậm là siêu mặt tốt nhất.
-

Các điểm được bao bởi hình chữ nhật là những điểm gần nhất

-

Các đường nét đứt mà các véc-tơ nằm trên đó được gọi là lề

Để giải quyết bài toán phân hai lớp trên ta phải tìm siêu mặt tách 2 lớp. Khi

1

WTx + b = - 1

Hình 1.4: Siêu phẳng tuyến tính phân chia dữ liệu, m là khoảng cách giữa hai lề
Với mỗi xi ta luôn có
T

 w xi  b  0
f  xi    T

 w xi  b  0

Trong đó: - w
-b

Nếu yi = 1
Nếu yi = -1

Rn là véc-tơ trọng số
R là hệ số tự do

- w.x là tích vô hướng của hai véc-tơ w và x.
Sao cho với tập dữ liệu kiểm tra x = { x1, x2,…,xn}, lấy yi

{-1,1} là nhãn của xi, ta

có hàm quyết định:

1

≥ 0, i= 1…l

(1.4)

R là một biến mà chúng ta cần xác định.

Bây giờ vấn đề đặt ra là cần xác định số w và b,

như thế nào để siêu phẳng

tìm được là tốt nhất? Siêu phẳng tốt nhất là siêu phẳng có khoảng cách từ điểm dữ
liệu huấn luyện gần nhất đến siêu phẳng là xa nhất. Mà khoảng cách từ một điểm
dữ liệu xi đến siêu phẳng là:

D  w, b, xi  

| w.xi  b |
|w|

| w.xi  b | là giá trị tuyệt đối của biểu thức

(1.5)

,|w| là độ dài Ơ-cơ-lít của véc-

tơ w. Giả sử h( w,b) là tổng của khoảng cách từ điểm dữ liệu gần nhất của lớp 1 đến
siêu phẳng và khoảng cách từ điểm dữ liệu gần nhất của lớp – 1 đến siêu phẳng thì:

h  w, b   min xi , yi 1 d  w, b; xi   min xi , yi 1 d  w, b; xi 
w.xi  b


Tóm lại, việc tìm siêu phẳng tốt nhất tương đương với việc giải bài toán tối ưu
minФw, (w)= || w||2 –vp
Với ràng buộc: yi  w.xi  b   với
Với v là một tham số của (1.7), v

≥ 0 và I = 1….l

[0,1]

Hàm La-gơ-răng của bài toán tối ưu trên là:
Số hóa bởi Trung tâm Học liệu – ĐHTN



(1.7)


12
l

L(w,b, ) = || w||2 - v

  y  wx

-

i

i 1

Với ràng buộc αi ≥ 0, i= 1,…,l

i 1

và δ ≥ 0

Nghiệm của bài toán tối ưu (1.21) với ràng buộc (1.18) chính là điểm yên
ngựa của hàm Lagrangian (1.7).
Theo định lý Kuhn-Tucker, giá trị tối thiểu của (1.22) trên b, w và ρ đạt được khi:
l
L
 0    i yi  0
b
i 1
l
L
 0  w    i yi xi
b
i 1
l
L
 0  i  v  
b
i 1

Xét điều kiện

l



j 1

i

j

yi y j xi x j

Với các ràng buộc:
Số hóa bởi Trung tâm Học liệu – ĐHTN



(1.10)


13
α≥0

i = 1,…l
l


i 1

i

(1.11)

l


Khi đó các hệ số của siêu phẳng tối ưu là:

w* 

b* 

1 l *
i yi xi
2 j 1

1

2s rr 0

l



*
i i

y ( xi xr )

(1.13)

i

Trong đó: xr là support vecto thỏa mãn  r*  0 , s là tổng số các véc-tơ hỗ trợ
của siêu phẳng tối ưu.

y i  wx i  b    i

i = 1,…, l

(1.15)

Ở đây, ξi gọi là các biến lới lỏng ( slack varibale) ξi ≥ 0.
Khi đó bài toán tối ưu (1.7) với ràng buộc (1.4) được mở rộng thành bìa toán (OP1)
như sau:

1 
1 l
w v     i
Tối thiểu   w,   
2
l i 1

(1.16)

Với các ràng buộc

y i  wx i  b     i

i  0
 0

i = 1,…,l

(1.17)



 i 

i
i
i
i
l i 1
i 1
i 1

(1.18)

Ở đây,   1 , 2 ,....,l  ,    1 ,  2 ,..., l  , và αi, βi ( i= 1,…, l), δ là các hệ số
Lagrange multiplies. Hàm Lagrange phải tối thiểu với w, b, ξ, ρ và tối đa với
α

0, β ≥ 0, δ ≥ 0.

Lập luận tương tự như trường hợp 1, ta có bài toán Lagragian đối ngẫu (OP2) là:

max LD    


1 l

2 i 1

l


(1.22)

l


i 1

Giải bài toán tối ưu OP2 trên ta tìm được nghiệm là α*, tương ứng với các siêu
phẳng của tối ưu là:
Số hóa bởi Trung tâm Học liệu – ĐHTN




15
l

w *    i* yi xi
i 1

1
b 

2s r \ r* 0
*

(1.23)

l


max LD     

2 i 1

l

 
i 1

l

Với các ràng buộc: 0 ≤ αi ≤ 1/l

i= 1,…, l ,

i


j 1

j

yi y j (x i )(x j )

j y j  0 và

l


i 1

 
i 1

Với các ràng buộc: 0 ≤ αi ≤ 1/l

i

j

yi y j k( xi , x j )
(1.26)

i= 1,…,l

(1.27)

l


j 1

l


i 1

i

j


i

(1.30)

Như vậy, trong không gian m- chiều, việc phân loại tài liệu x tương đương với
việc tìm hàm f(x):

 l

f ( x)  sgn   i* yi k( xi .x)  b* 
 i 1


(1.31)

Đến đây, công việc còn lại của bài toán huấn luyện phân loại chỉ còn là đi giải
bài toán tối ưu (1.26) với các ràng buộc (1.27), (1.28), và (1.29). Làm thế nào để
tìm được α*.
1.3.3. Phương pháp tìm α*, b.
Bài toán tối ưu (1.40) có hàm mục tiêu là hàm bậc 2 đối với α và các ràng
buộc (1.41), (1.42), (1.43) của nó đều là các ràng buộc tuyến tính. Mặt khác, hàm
mục tiêu và các ràng buộc của nó là hàm lồi trong không gian Rn. Vì vậy, nó được
Số hóa bởi Trung tâm Học liệu – ĐHTN


17

gọi là bài toán QP (quadratic programming) lồi. Vì OP2 là bài toán QP lồi, nên nếu
hàm mục tiêu đạt cực trị địa phương thì nó cũng sẽ đạt cực trị toàn cục. Do đó, ý
tưởng tìm α* của bài toán OP2 là tại mỗi bước lặp ta sẽ cập nhật lại giá trị cho mỗi

  v 
, C  l 1    
  v  

1

Với

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




18

Trong đó l+, l- tương ứng với số mẫu huấn luyện thuộc lớp dương và số
mẫu huấn luyện thuộc lớp âm.
Tìm tập biến quyết định, { αi} , mà làm cực đại hàm mục tiêu sau:

Output

LD  

1
i j yi y j Kij
2 ij

Thỏa mãn: 0 ≤ αi ≤ Ci,

 y


Method




  i , j 






  i , j 









 i(k)  0,  (k)
 Cj 
j


i , j  1,..., l ,
