HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

 

NGUYỄN NGỌC MINH

ỨNG DỤNG CÁC PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT VÀO BÀI
TOÁN PHÂN LOẠI VĂN BẢN

LUẬN VĂN THẠC SỸ KỸ THUẬT
 

 
 
 
 
HÀ NỘI – NĂM 2013 

 


 
 

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------


 
Tác giả luận văn

Nguyễn Ngọc Minh

 


 
 

LỜI CẢM ƠN
 
Lời đầu tiên em xin gửi lời cảm ơn đến toàn thể các thầy, cô giáo Học viện 
Công nghệ Bưu chính Viễn thông đã tận tình chỉ bảo em trong suốt thời gian học 
tập tại nhà trường.  
Em xin gửi lời cảm  ơn sâu sắc đến PGS.TS. Đoàn Văn Ban, người đã trực 
tiếp hướng dẫn, tạo mọi điều kiện thuận lợi và tận tình chỉ bảo cho em trong suốt 
thời gian làm luận văn tốt nghiệp.  
Bên cạnh đó, để hoàn thành đồ án này, em cũng đã nhận được rất nhiều sự 
giúp đỡ, những lời động viên quý báu của các bạn bè, gia đình và đồng nghiệp. Em 
xin chân thành cảm ơn.  
Tuy nhiên, do thời gian hạn hẹp, mặc dù đã nỗ lực hết sức mình, nhưng chắc 
rằng đồ án khó tránh khỏi thiếu sót. Em rất mong nhận được sự thông cảm và chỉ 
bảo tận tình của quý thầy cô và các bạn. 
 
HỌC VIÊN
Nguyễn Ngọc Minh

 

 


ii 
 
1.5.2. Mô hình toán học ....................................................................... 10
1.6. Tổng kết chương ............................................................................. 10
CHƯƠNG 2 - MỘT SỐ THUẬT TOÁN HỌC NỬA GIÁM SÁT ......... 11
2.1. Mô hình sinh và thuật toán kỳ vọng cực đại ................................. 11
2.1.1. Giới thiệu về mô hình sinh ......................................................... 11
2.1.2. Mô hình sinh trong học nửa giám sát ......................................... 11
2.1.3. Thuật toán kỳ vọng cực đại ........................................................ 12
2.1.3.1. Giới thiệu thuật toán ............................................................ 12
2.1.3.2. Nội dung thuật toán ............................................................. 12
2.1.3.3. Đánh giá thuật toán .............................................................. 14
2.2. Thuật toán tự huấn luyện............................................................... 15
2.2.1. Giới thiệu thuật toán tự huấn luyện ............................................ 15
2.2.2. Đánh giá thuật toán .................................................................... 16
2.3. Thuật toán S3VM ........................................................................... 16
2.3.1. Thuật toán SVM ........................................................................ 16
2.3.2. Giới thiệu thuật toán  S3VM ...................................................... 21
2.3.3. Nội dung thuật toán  S3VM ....................................................... 22
2.3.4. Nhận xét về S3VM .................................................................... 23
2.4. Thuật toán K - láng giềng gần nhất ............................................... 23
2.4.1. Giới thiệu thuật toán .................................................................. 23
2.4.2. Áp dụng KNN vào bài toán phân loại văn bản ........................... 24
2.5. Thuật toán Naive Bayes ................................................................. 26
2.5.1. Thuật toán .................................................................................. 26
2.5.2. Áp dụng vào bài toán phân loại .................................................. 27


 


iv 
 
3.3.1. Dữ liệu sử dụng.......................................................................... 49
3.3.2. Trích chọn đặc trưng .................................................................. 51
3.3.3. Phương pháp đánh giá ................................................................ 52
3.3.4. Công cụ phân lớp ....................................................................... 53
3.3.5. Kết quả thử nghiệm và đánh giá ................................................. 54
3.4. Tổng kết chương ............................................................................. 57
KẾT LUẬN ............................................................................................... 58
TÀI LIỆU THAM KHẢO ........................................................................ 59

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


Self-training 

Tự huấn luyện 

EM 

Expectation Maximization 

Kỳ vọng cực đại 

Machine learning 

Machine learning 

Học máy 

Supervised learning 

Supervised learning 

Học có giám sát 

Unsupervised learning 

Unsupervised 
learning 

Học không giám sát 



Máy véc tơ hỗ trợ 

Semi-supervised 
support vector machine 

S3VM 

 
 

 

Máy véc tơ hỗ trợ nửa 
giám sát 


vi 
 

DANH MỤC CÁC HÌNH
 
Hình 1.1: Mô hình học có giám sát ............................................................... 6
Hình 1.2: Mô hình học nửa giám sát ............................................................. 9
Hình 2.1: Dữ liệu có nhãn ........................................................................... 11
Hình 2.2: Dữ liệu có nhãn và chưa có nhãn ................................................. 12
Hình 2.3  Phân lớp  SVM ............................................................................ 17
Hình 2.4: Cây quyết định ............................................................................ 34
Hình 3.1: Mô hình giai đoạn huấn luyện ..................................................... 41
Hình 3.2: Chi tiết giai đoạn huấn luyện ....................................................... 42

Bảng 2.6: Kết quả phân lớp ......................................................................... 36
Bảng 3.1: Bộ dữ liệu thử nghiệm ban đầu ................................................... 50
Bảng 3.2: Danh sách 20 từ đặc trưng .......................................................... 50
Bảng 3.3: Bộ dữ liệu sau khi “stemming” ................................................... 51
Bảng 3.4: Danh sách 20 “stem” đặc trưng ................................................... 51
Bảng 3.5: Kết quả kiểm nghiệm bộ dữ liệu ban đầu .................................... 55
Bảng 3.6: Kết quả kiểm nghiệm bộ dữ liệu sau khi “stemming”.................. 55

 


1 
 

MỞ ĐẦU
1. Lý do chọn đề tài
Ngày nay sự phát triển mạnh mẽ của Internet đã dẫn đến sự bùng nổ thông 
tin  về  nhiều  mặt  kể  cả  về  nội  dung  lẫn  số  lượng,  hệ  thống  dữ  liệu  số  hóa  trở  nên 
khổng lồ để phục vụ cho việc lưu trữ trao đổi thông tin. Dữ liệu số hóa này rất đa 
dạng,  nó  có thể  là các  dữ  liệu dưới  dạng  tập tin văn  bản text,  tập  tin  văn bản MS 
word, tập tin văn bản PDF, mail, HTML, ... Các tập tin văn bản cũng được lưu trữ 
trên  máy  tính  cục  bộ hoặc  được truyền  tải  trên  Internet, cùng  với thời gian và với 
lượng người dùng tăng  nhanh thì các tập tin này ngày càng nhiều và đến một thời 
điểm nào đó thì số lượng tập tin này sẽ vượt quá tầm kiểm soát, do đó khi muốn tìm 
kiếm lại một văn bản nào đó việc tìm kiếm sẽ rất khó khăn và phức tạp, đặc biệt là 
trong trường hợp người cần tìm kiếm không rõ các câu cần tìm chính xác trong văn 
bản đó. 
Với sự thành công của một số chương trình học máy đã chứng minh rằng có 
thể tồn tại một tập hợp các quy tắc học tổng quát, cho phép xây dựng các chương 
trình có khả năng tự học trong nhiều lĩnh vực khác nhau. Vào tháng 1-2006, Xiaojin 

Thực nghiệm: Cài đặt thử nghiệm và đánh giá một số thuật toán học nửa giám sát, 
thuật toán học có giám sát. 
5. Nội dung luận văn
Luận văn gồm 3 chương: 
Chương 1: Tổng quan về phương pháp học máy 
Chương 2: Một số thuật toán học nửa giám sát 
Chương 3: Phân loại văn bản dựa vào phương pháp học nửa giám sát 
Trong đó đề tài tập trung vào chương 3 nhằm nghiên cứu và áp dụng các kỹ 
thuật phân loại email của bộ dữ liệu dbworld  [18]. 
 
 
 

 


3 
 

CHƯƠNG 1 - TỔNG QUAN VỀ PHƯƠNG PHÁP HỌC MÁY
1.1. Khái niệm học máy
Hoạt động học là hoạt động tiếp thu những tri thức lý luận, khoa học. Nghĩa 
là việc học không chỉ dừng lại ở việc nắm bắt những khái niệm đời thường mà học 
phải tiến đến những tri thức khoa học, những tri thức có tính chọn lựa cao, đã được 
khái quát hoá, hệ thống hoá. 
Hoạt động học tập không chỉ hướng vào việc tiếp thu những tri thức, kĩ năng, 
kĩ  xảo mà  còn  hướng  vào việc  tiếp  thu  cả  những  tri  thức  của  chính bản  thân  hoạt 
động  học.  Hoạt  động  học  muốn  đạt  kết  quả  cao,  người  học  phải  biết  cách  học, 
phương pháp học, nghĩa là phải có những tri thức về chính bản thân hoạt động học.  
Vậy,  việc  làm  thế  nào  để  máy  tính  có  khả  năng  học  tập,  tư  duy  và  có  khả 

 Mỗi phần tử  S  X  được  biểu diễn bởi  một tập gồm n thuộc tính  
S  ( s1 , s2 ,..., sn )  . 

 Một đối tượng S cũng có thể được biểu diễn kết hợp với lớp liên thuộc của 
nó hay nói cách khác có thể được biểu diễn dưới dạng nhãn:  z  ( s, c)  . 

1.2.2. Bản chất của các dữ liệu
Bản chất của các dữ liệu có thể là các giá trị số trong tập số thực, các giá trị 
rời rạc, các giá trị nhị phân, dãy các phần tử trong một bảng chữ cái (alphabet), ... 
Không  gian  biểu  diễn  của  dữ  liệu  có  thể  biểu  diễn  dưới  dạng  thuần  nhất 
(cùng kiểu) hoặc dưới dạng trộn (không cùng kiểu). 

1.2.3. Tiền xử lý dữ liệu
Là quá trình xử lý dữ liệu đầu vào nhằm mục đích làm giảm số chiều của dữ 
liệu đầu vào, giảm số chiều của vấn đề, xử lý nhiễu, ...  
Ta thực hiện như sau: 
 Loại bỏ các thuộc tính không phù hợp hoặc ít phù hợp với quá trình học.  
 Sử dụng các phép biến đổi tuyến tính hoặc không tuyến tính trên các thuộc 
tính ban đầu, nhằm giảm số chiều của không gian đầu vào. 
 Dùng  các  chuyên  gia  hoặc  sử  dụng  trực  quan  để  phát  hiện  các  bất  thường, 
các lỗi mô tả thuộc tính hoặc nhãn, nhằm xử lý nhiễu.    
 


5 
 

1.2.4. Quá trình rời rạc hóa dữ liệu
Có  những  thuật  toán  học  không  xử lý được  các  dữ  liệu  mang  tính  liên tục. 
Do vậy, cần phải biến đổi các dữ liệu mang tính liên tục thành các giá trị rời rạc.  


6 
 
muốn. Đầu ra của hàm  f có thể là một giá trị liên tục hoặc có thể là dự đoán một 
nhãn phân lớp cho một đối tượng đầu vào. 

 
Hình 1.1: Mô hình học có giám sát

Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm f cho 
một đối tượng đầu vào hợp lệ bất kì, sau khi đã xét một số mẫu dữ liệu huấn luyện 
(nghĩa là các cặp đầu vào và đầu ra tương ứng). Để đạt được điều này, chương trình 
học  phải  tổng  quát  hóa  từ  các  dữ  liệu  sẵn  có  để  dự  đoán  được  những  tình  huống 
chưa gặp phải theo một cách hợp lý. 
Trong lý thuyết xác suất, một dãy các biến ngẫu nhiên được coi là có độc lập 
cùng  phân  phối  nếu  chúng  có  cùng  một  phân  phối  và  độc  lập  với  nhau  [26].  Các 
quan  sát  trong  một  mẫu  thường  được  giả  thiết  là  độc  lập  cùng  phân  phối  (i.i.d  – 
independently and identically distributed) nhằm làm đơn giản hoá tính toán toán học 
bên dưới của nhiều phương pháp thống kê.  
Hệ thống học sẽ quan sát một tập dữ liệu huấn luyện đã được gán nhãn, bao 
gồm các cặp (đặc tính, nhãn) được biểu diễn bởi  {( x1 , y1 ), ( x2 , y2 ),..., ( xn , yn )} . Trong 
đó  yi  Y  gọi là nhãn hoặc đích của các mẫu xi. Mục đích nhằm dự đoán nhãn y cho 
bất kỳ đầu vào mới với đặc tính x. Nếu nhãn là các số,  y  ( yi )Ti[n ]  biểu diễn véc tơ 
cột của các nhãn. Như đã nêu, một yêu cầu chuẩn là các cặp  ( xi , yi )  tuân theo giả 
thiết i.i.d trải khắp trên  X  Y .  Nhiệm vụ được định rõ là, ta có thể tính toán được 
một phép ánh xạ thông qua thi hành dự đoán của nó trên tập kiểm thử. Nếu các nhãn 
lớp là liên tục, nhiệm vụ phân lớp được gọi là hồi quy (regression). Có hai họ thuật 
toán  có  giám  sát:  mô  hình  sinh  mẫu  (generative  model)  và    mô  hình  phân  biệt 
(discriminative model) 


dòng chữ viết tay, ... 
Bước 2: Thu thập tập dữ liệu huấn luyện. Khi thu thập tập dữ liệu huấn luyện 
cần phải đảm bảo được sự đặc trưng cho thực tế sử dụng của hàm chức năng. Do đó 
tập các dữ liệu đầu vào và đầu ra tương ứng phải được thu thập từ các chuyên gia 
hoặc từ việc đo đạc tính toán. 
Bước 3: Xác định việc biễu diễn các đặc trưng đầu vào cho hàm mục tiêu cần 
tìm. Độ chính xác của mục tiêu phụ thuộc rất lớn vào các đối tượng đầu vào được 
biểu diễn như thế nào. Đa số các đối tượng đầu vào được chuyển đổi thành một véc 
tơ đặc trưng chứa các đặc trưng cơ bản của đối tượng đó. Chú ý số lượng các đặc 

 


8 
 
trưng không được lớn quá, để tránh sự bùng nổ tổ hợp  tuy nhiên nó phải đủ lớn để 
đảm bảo dự đoán chính xác đầu ra. 
Bước 4: Xác định cấu trúc của hàm mục tiêu cần tìm và giải thuật học tương 
ứng. Ví dụ, ta có thể sử dụng mạng nơ-ron nhân tạo, cây quyết định, ...  
Bước 5: Hoàn thiện thiết kế.  
Tiến hành chạy giải thuật học với tập dữ liệu huấn luyện thu thập được. Ta 
có thể điều chỉnh các tham số của giải thuật học bằng cách tối ưu hóa hiệu năng trên 
một tập con của tập huấn luyện, (gọi là tập kiểm chứng -validation set) của tập huấn 
luyện hay thông qua kiểm chứng chéo (cross-validation). Sau đó ta tiến hành đo đạc 
hiệu năng của giải thuật trên một tập dữ liệu kiểm tra độc lập với tập huấn luyện. 

1.4. Học không có giám sát
1.4.1. Khái niệm
Học không có giám sát (unsupervised learning) [5],[16] là một phương pháp 
học máy mà dữ liệu huấn luyện là dữ liệu hoàn toàn chưa được gán nhãn, nhằm tìm 

Học  nửa  giám  sát  (semi-supervised  learning)  [5],[16]  là  một  phương  pháp 
học máy mà dữ liệu huấn luyện là sự kết hợp của dữ liệu được gán nhãn và dữ liệu 
chưa được gán nhãn.  

 
Hình 1.2: Mô hình học nửa giám sát

Như chúng ta đã biết khi áp dụng học có giám sát thì các dữ liệu huấn luyện 
đã được gán nhãn. Do đó sẽ thu được kết quả có độ chính xác rất cao. Tuy nhiên, 
khi đó ta sẽ gặp một vấn đề rất khó khăn là khi lượng dữ liệu lớn, thì công việc gán 
nhãn cho dữ liệu sẽ tốn rất nhiều thời gian và công sức. Hay nói cách khác những 
dữ  liệu  được  gán  nhãn  là  rất  đắt  và  việc  tạo  ra  nhãn  cho  những  dữ  liệu  đòi  hỏi 
những nỗ lực rất lớn của con người.  
Đối với mô hình học không có giám sát thì ngược lại, các dữ liệu huấn luyện 
không  được  gán  nhãn.  Do  đó  kết  quả  thu  được  có  độ  chính  xác  không  cao.  Tuy 

 


10 
 
nhiên dữ liệu chưa được gán nhãn, có thể dễ dàng thu thập được rất nhiều. Hay nói 
cách khác là dữ liệu chưa gán nhãn có chi phí rất rẻ. 
Học nửa giám sát đã khắc phục được các nhược điểm, và phát huy được ưu 
điểm của học có giám sát và học không có giám sát. Bằng cách kết hợp giữa học có 
giám sát và học không có giám sát, với một lượng lớn dữ liệu chưa gán nhãn và một 
lượng nhỏ những dữ liệu đã được gán nhãn, bằng các giải thuật học nửa giám sát sẽ 
thu được kết quả vừa có độ chính xác cao vừa mất ít thời gian công sức. Do đó, học 
nửa giám sát là một phương pháp học đạt được hiệu quả rất tốt trong lĩnh vực học 
máy. 

Trong học nửa giám sát, phương pháp được áp dụng lâu đời nhất là phương 
pháp sử dụng mô hình sinh. Mô hình sinh được mô tả bởi những chức năng và thao 
tác toán học được sắp xếp theo sự phân cấp trên cùng một tập dữ liệu điểm. 
Mô hình có dạng  p ( x, y )  p ( y )  p ( x | y )  với  p ( x | y )  là một phân phối nhận 
dạng  hỗn hợp [4],[16].  
Ví  dụ:  Mô  hình  hỗn  hợp  Gaussian,  là  mô  hình  với  một  lượng  lớn  dữ  liệu 
chưa  gán  nhãn  và  một  số  ít  dữ  liệu  gán  nhãn,  các  phần  hỗn  hợp  có  thể  được  xác 
định, sau đó chúng ta chỉ cần gán một nhãn cho mỗi ví dụ thành phần để xác định 
đầy đủ phân phối hỗn hợp. 

2.1.2. Mô hình sinh trong học nửa giám sát
Người ta thường áp dụng mô hình sinh để giải quyết những bài toán nhận dạng 
ảnh, nhận dạng văn bản, nhận dạng tiếng nói và một số bài toán khác.  
Giả sử có một có một tập dữ liệu  ( x , y ) đã được gán nhãn. Với  x  là dữ liệu,  y  
là nhãn tương ứng. Chúng được phân lớp như hình sau:

 
Hình 2.1: Dữ liệu có nhãn

 


12 
 
Khi dữ liệu chưa được gán nhãn được thêm  vào. Thì ta sẽ có  một  mô hình 
phù hợp nhất với tập dữ liệu này, để có thể phân lớp tất cả các dữ liệu mới được đưa 
vào.    

 
Hình 2.2: Dữ liệu có nhãn và chưa có nhãn

 { 
For d  U do  
{ 
E-bước: dùng phân lớp Bayes thứ nhất xác định P(c|d,i); 
End for 
 } 
For c và t do  
{ 
 

M-bước: xác định c,t dùng công thức (**) để xây dựng mô hình i+1; 

 

End for  

 

} 

End for 
 }  
 0 ,t 

1   d D P ( c | d ) n ( d , t )
| W |   d D   P (c | d ) n( d , )

P (c ) 

1

14 
 
Thuật toán kỳ vọng cực đại được thực hiện như sau: 
Bước 1:    Tiến  hành  gán  giá  trị  ngẫu  nhiên  cho  tất  cả  các  tham  số  của  mô 
hình.  
Bước 2: Tiến hành lặp hai bước lặp sau: 
Bước kỳ vọng (Expectation step): Trong bước này thuật toán tiến hành tính 
toán hàm mục tiêu mong muốn cho dữ liệu dựa trên các thiết lập tham số và dữ liệu 
không đầy đủ. 
Bước tối đa hóa (Maximization step): Trong bước này thuật toán tiến hành 
tính toán lại tất cả các tham số, bằng cách sử dụng tất cả các dữ liệu.  
Qua đó ta sẽ nhận được một tập các tham số mới.Tiến trình tiếp tục cho đến 
khi hàm mục tiêu hội tụ, ví dụ như hàm mục tiêu  đạt tới cực đại địa phương. 
Thuật toán kỳ vọng cực đại sử dụng hướng tiếp cận là xuất phát từ một giá trị 
khởi ngẫu nhiên nào đó. Do vậy chỉ đảm bảo đạt được giá cực đại địa phương mang 
tính phương. Nên việc đạt tới cực đại toàn cục hay không là phụ thuộc vào điểm bắt 
đầu xuất phát. Nếu ta xuất phát từ một điểm đúng thì ta có thể tìm được cực đại toàn 
cục. Tuy nhiên vấn đề tìm điểm xuất phát đúng thường rất khó. Ta có thể sử dụng 
hai phương pháp để giải quyết vấn đề này như sau: 
Một là: Tiến hành thử nhiều giá trị khởi đầu khác nhau, qua đó tiến hành lựa 
chọn phương án mà giá trị hàm mục tiêu hội tụ lớn nhất.  
Hai là: Ta sẽ sử dụng một mô hình đơn giản hơn để tiến hành xác định giá 
trị khởi đầu. Qua đó sẽ tìm được vùng tồn tại cực đại toàn cục, sau đó ta sẽ chọn 
một giá trị khởi đầu trong vùng đó để tiến hành bắt đầu với mô hình phức tạp.  

2.1.3.3. Đánh giá thuật toán 
Thuật toán kỳ vọng cực đại có ưu điểm là có mô hình toán rõ ràng, học theo 
khung mô hình xác suất khá tốt và có hiệu quả rất tốt nếu mô hình đó là mô hình 
dạng  đóng.  Tuy  nhiên,  thuật  toán  còn  những  mặt  hạn  chế  là  ta  cần  phải  xác  định 
được tính chính xác của mô hình, xác minh được tính đồng nhất của mô hình, ngoài