i
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
thần và vật chất cho tác giả hoàn thành luận văn này. Xin cảm ơn tất cả!

Thái Nguyên, tháng 6 năm 2016
Tác giả luận văn

Đặng Đình Tuyến


ii

LỜI CAM ĐOAN
Tôi là Đặng Đình Tuyến, học viên cao học K13, chuyên ngành Khoa học
máy tính, khoá 2014-2016. Tôi xin cam đoan luận văn thạc sĩ “Phân lớp văn bản
nhờ Máy Véc-tơ hỗ trợ (SVM) với hàm string kernel” là công trình nghiên cứu của
riêng tôi cùng với sự hướng dẫn của PGS.TS Nguyễn Tân Ân. 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 ai công bố trong bất kỳ công
trình nào khác.
Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn
gốc một cách rõ ràng từ danh mục tài liệu tham khảo của luận văn. Trong luận văn,
không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ

2.1.2. Định nghĩa kernel ..................................................................................... 26
2.1.3. Một số ví dụ về Ф và k(,).......................................................................... 26
2.1.4. Một số hàm kernel .................................................................................... 28
2.1.5. Định lý ..................................................................................................... 30
2.1.6. Kernel là độ đo giống nhau giữa hai đối tượng ........................................ 31
2.1.7. Kernel trick .............................................................................................. 32
2.1.8. Xây dựng các kernel ................................................................................ 32


iv
2.1.9. Nhân hóa một số phương pháp phân lớp .................................................. 34
2.2. String kernel ................................................................................................... 39
2.2.1. Kernel dựa trên mô hình k_gram .............................................................. 39
2.2.2. Kernel dựa trên trọng số của các xâu ........................................................ 41
2.2.3. Tính string kernel dùng quy hoạch động ................................................... 43
2.2.4. Kernel dựa trên độ giống nhau giữa hai xâu. ............................................. 44
2.2.5. Một số đặc trưng của Tiếng Việt............................................................... 45
2.3. Kết luận .......................................................................................................... 48
CHƯƠNG 3: CÀI ĐẶT THỬ NGHIỆM THUẬT TOÁN SVM CHO BÀI TOÁN
TÌM KIẾM VĂN BẢN.......................................................................................... 49
3.1. Mô tả bài toán ................................................................................................. 49
3.2. Phân tích, cài đặt thuật toán ............................................................................ 49
3.2.1. Thuật toán huấn luyện để tìm từ khóa ....................................................... 49
3.2.2. Thuật toán sử dụng từ khóa tìm kiếm văn bản .......................................... 57
3.3. Kết luận .......................................................................................................... 61
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.............................................................. 62
TÀI LIỆU THAM KHẢO ..................................................................................... 63


v

Bảng 3.3: Bảng thống kê các từ đặc trưng từ Đoạn mẫu 2...................................... 52
Bảng 3.4: Tính toán tần xuất và trọng số của các từ (theo định nghĩa từ tiếng Việt) .... 54
Bảng 3.5: Bảng thống kê các từ đặc trưng từ Đoạn mẫu 3...................................... 55
Bảng 3.6: Tính toán tần xuất và trọng số của các từ (theo định nghĩa từ tiếng Việt) .... 56
Bảng 3.7: Bảng tổng hợp ....................................................................................... 56
Bảng 3.8: Số lần xuất hiện của các từ trong các văn bản huấn luyện ...................... 59
Bảng 3.9: Bảng phân nhóm với nhãn là “Vịnh Hạ Long”....................................... 59
Bảng 3.10: Bảng phân nhóm với nhãn là “Di sản” ................................................. 60
Bảng 3.11: Bảng phân nhóm với nhãn là “đảo” ..................................................... 60


1
CHƯƠNG 1: BÀI TOÁN PHÂN LỚP
1.1. Nội dung bài toán phân lớp
Phân lớp (classification) là một tiến trình xử lý nhằm xếp các mẫu dữ
liệu hay cá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 hay cá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) 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


bởi Sahami)...
* Ý tưởng
Ý tưởng cơ bản của cách tiếp cận Naïve Bayes là sử dụng xác suất có điều
kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của một văn bản cần phân loại.
Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện
của tất cả các từ trong văn bản đều độc lập với nhau. Với giả định này NB không sử
dụng sự phụ thuộc của nhiều từ vào một chủ đề, không sử dụng việc kết hợp các từ
để đưa ra phán đoán chủ đề và do đó việc tính toán NB chạy nhanh hơn các phương
pháp khác với độ phức tạp theo hàm số mũ.
* Công thức
Mục đích chính là tính được xác suất Pr(Cj,d′), xác suất để văn bản d′ nằm
trong lớp Cj. Theo luật Bayes, văn bản d′ sẽ được gán vào lớp Cj nào có xác suất
Pr(Cj, d′) cao nhất. Công thức sau dùng để tính Pr(Cj,d′) (do Joachims đề xuất năm
1997)

HBAYES





d'
d'
'
IF
(w,
d
)
 Pr(Cj ). Pr(wi | Cj ) 
 Pr(Cj ). Pr(wi | Cj )


1
 C'C

 C'C


Với:
 (TF,d’) là số lần xuất hiện của từ wi trong văn bản d′
 |d′| là số lượng các từ trong văn bản d′
 wi là một từ trong không gian đặc trưng F với số chiều là |F|


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

'

||

khác nhau. Tuy nhiên NB ngoài giả định tính độc lập giữa các từ còn phải cần đến
một ngưỡng tối ưu để cho kết quả khả quan. Nhằm mục đích cải thiện hiệu năng
của NB, các phương pháp như multiclass- boosting, ECOC (do Berger trình bày
năm 1999 và Ghani mô tả lại năm 2000) có thể được dùng kết hợp.
1.2.2. Phương pháp K–Nearest Neighbor (kNN)
Đây là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên
thống kê đã được nghiên cứu trong nhận dạng mẫu hơn bốn thập kỷ qua (theo tài
liệu của Dasarathy năm 1991). kNN được đánh giá là một trong những phương
pháp tốt nhất (áp dụng trên tập dữ liệu Reuters phiên bản 21450), được sử dụng từ
những thời kỳ đầu của việc phân loại văn bản (được trình bày bởi Marsand năm
1992, Yang năm 1994, Iwayama năm 1995)


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 :

 



sử dụng độ đo cosine để tính sin  x , di 
Bj là ngưỡng phân loại của chủ đề cj được tự động học sử dụng một tập văn bản hợp
lệ được chọn ra từ tập huấn luyện.
Để chọn được tham số k tốt nhất cho việc phân loại, thuật toán phải được chạy
thử nghiệm trên nhiều giá trị k khác nhau, giá trị k càng lớn thì thuật toán càng ổn
đị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.


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


Trong đó, η = β x là sự kết hợp của những đặc trưng đầu vào và p phải thỏa
đ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

d j ei

j








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:

(a)

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
đường thẳng


8
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.
Giả sử chúng ta tìm được cách biểu diễn dữ liệu của bài toán thành dạng có
thể áp dụng được vào bài toán SVM, dữ liệu huấn luyện của SVM là tập các dãy đã
được gán nhãn trước D   x1 , y1  ,  x2 , y2  ,...  xn , yn  .


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

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

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
siêu mặt là siêu phẳng thì hàm f có dạng là f(x) = w.x + b sẽ phân loại tốt nhất trên
dữ liệu mới.
Có ba trường hợp xảy ra đối với tập dữ liệu D là: Tập D là tuyến tính có thể
tách được, tập D là tuyến tính không tách được, tập D không tuyến tính. Tương ứng
chúng ta có ba trường hợp để giải quyết bài toán SVM.


Tập dữ liệu D có thể phân chia tuyến tính mà không có nhiễu ( nghĩa

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
f  xi   sign  w T x  b   
1

Nếu yi = 1

(x,y)

D

(1.2)

Nếu yi = -1

Giả sử siêu phẳng phân chia dữ liệu với các ràng buộc:
min| w.xi+b|=
Hay yi[ w.xi+b] ≥

(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

 min xi , yi 1
1
w
2

w


 min xi , yi 1

w

 min

xi , yi 1

w.xi  b
w

w.xi  b  min xi , yi 1 w.xi  b |


i 1

i

 b      

(1.8)


12
Ở đây,   1 ,  2 ,...,  l  và

i

≥ 0 ( i= 1,…,l),

≥ 0 là các hệ số của Lagrange

multiplier.
Ta có bài toán Lagrangian tương ứng với bài toán tối ưu (1.7) với các ràng
buộc (1.4) là:

1
min w,   w, b,   
w
2

l



l

Xét điều kiện



i

 v   , chúng ta thấy rằng theo điều kiện bổ sung trong

i 1

hệ điều kiện của định lý Kuhn-Tucker, δρ = 0, do đó ρ > 0 suy ra δ = 0. Như vậy,
trong trường hợp ρ > 0 chúng ta có thể thay điều kiện này bằng điều kiện
l



i

v

i 1

Từ nhận xét trên và thay (1.9) vào (1.8) ta có bài toán Lagragian đối ngẫu:

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

l





i

 v

i 1

Giả sử α* là nghiệm của (1.10) với các ràng buộc (1.11) thì:

1 l
  arg min 
2 i 1
*

l

 
i

j

yi y j xi x j

(1.12)


của siêu phẳng tối ưu.
Từ (1.13) ta thấy chỉ những  r*  0 mới có ý nghĩa trong việc xây dựng véc-tơ
w. Mà theo điều kiện bổ sung trong hệ điều kiện của định lý Kuhn-Tucker,

i*  yi  w.xi  b      0

thì  r*  0 tương đương với yi(w.xi+b)-ρ= 0. Như

vậy, điểm xi được gọi là support vector cũng chính là điểm có  r*  0 .
Bây giờ, để phân loại một tài liệu x ta chỉ cần xét dấu của hàm f(x)

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

(1.14)

 Tập dữ liệu huấn luyện D có thể phân chia được tuyến tính nhưng có
nhiễu ( Hình 1.9). Trong trường hợp này, hầu hết các điểm trong tập dữ liệu được
phân chia bởi siêu phẳng tuyến tính. Tuy nhiên, có một số ít điểm bị nhiễu ( là điểm
có nhãn dương nhưng thuộc về phía âm của siêu phẳng).
Trong trường hợp này, chúng ta thay ràng buộc (1.4) bằng ràng buộc sau>

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

i = 1,…, l

(1.15)

1 
w
2

2

v  

l
l
1 l



y
wx

b





i i  

 i 

i i
i
i

(1.19)

i 1

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

i = 1,…, l

(1.20)

l



j

yj

(1.21)

i

v

(1.22)

j 1
l



i

 

r \ r*  0

y i (x i x r )

i

Trong đó: xr là véc-tơ hỗ trợ thỏa mãn *r  0 .
S là tổng các support vector của siêu phẳng tối ưu.
Bây giờ, để gán nhãn cho một tài liệu x ta chỉ cần xét dấu của hàm f(x):


f (x )  sg n 


l





*
i

yi (x

i


 
i

j

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

l

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

i= 1,…, l ,

(1.24)

i 1



l

j y j  0 và

j 1



i


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

i 1

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

i= 1,…,l

(1.27)

l



j

y j 0
( 1.28)

j 1

l



i

v
(1.29)

i

y i k( x i x r )
(1.30)

i

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):


f (x)  sgn 


l



i1



*
i

y

i

k ( x i.x )  b

 Thuật toán tối ưu tìm α*
Input

Cho

x  Rn
Yi = { +1, -1}
I= 1,…, l
v+,v- là các tham số cho trước

C

i

yi   1
C 
 
yi  1
C 
K ij  K ( x i , x j )

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

1

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

i

Definitio
n

i

v

i

+ Định nghĩa các công thức:

G i(k ) 



(k )
j

y j K ji , S p(kq  1)  G p(k )  G q(k )

j

+ Và các tập:

W

W



i

 y

(k )
i

j

  1

 0 ,

(k )
j

j



j



yi  y j   1


 i( k )  0 ,  (j k )  0 
i, j  1, ..., l ,


 0,

i

   y
0

i

i

 v,

i

Trong khi:

 ( p , q )  W


(k )




 

m S p( k q1)  0 v  p , q  W( k ) m S p( kq1)  0


,q

) W

và
(k )


(k )


(p ,q )  W(k) ,

S
S

( k  1)
pq
( k  1)
pq

,


o Nếu

     
(p,q) = (p+,q+),

 