Ứ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

Ứ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 công nghẹ thông tin

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

-

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

MàSỐ:       60.48.01.04 

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

 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS TS ĐOÀN VĂN BAN

HÀ NỘI - NĂM 2013

LỜI CAM ĐOAN

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

MỤC LỤC

LỜI CAM ĐOAN i

MỤC LỤC i

DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT v

DANH MỤC CÁC HÌNH vi

DANH MỤC CÁC BẢNG vii

MỞ ĐẦU 1

CHƯƠNG 1 - TỔNG QUAN VỀ PHƯƠNG PHÁP HỌC MÁY 3

1.1 Khái niệm học máy 3

1.2 Một số khái niệm cơ bản trong học máy 4

1.2.1. Không gian biểu diễn của dữ liệu   4

1.2.2. Bản chất của các dữ liệu   4

1.2.3. Tiền xử lý dữ liệu   4

1.2.4. Quá trình rời rạc hóa dữ liệu   5

1.2.5. Tập mẫu   5

1.2.6. Quá trình tìm kiếm trong không gian giả thuyết   5

1.3 Học có giám sát 5

1.3.1. Khái niệm   5

1.3.2. Cách giải một bài toán học có giám sát   7

1.4 Học không có giám sát 8

1.4.1. Khái niệm   8

1.4.2. Mô hình toán học   9

1.5 Học nửa giám sát 9

1.5.1. Khái niệm   9

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

2.6 Thuật toán cây quyết định 32

2.6.1.  Giới thiệu thuật toán   32

2.6.2. Thuật toán ID3   36

2.6.2.1. Entropy  36

2.6.2.2. Information Gain   36

2.6.2.3. Phát biểu thuật toán ID3   37

2.6.3. Đánh giá thuật toán cây quyết định   37

2.7 Tổng kết chương 38

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 39

3.1 Phát biểu bài toán phân loại văn bản 39

3.1.1. Mô hình tổng quát   41

3.1.1.1. Giai đoạn huấn luyện   41

3.1.1.2. Giai đoạn phân lớp   43

3.1.2. Quá trình tiền xử lý văn bản   44

3.1.3. Phương pháp biểu diễn văn bản   44

3.1.3.1. Mô hình không gian véc tơ   45

3.1.3.2. Khái niệm trọng số   45

3.1.4. Đánh giá bộ phân lớp   47

3.1.4.1. Macro-Averaging   48

3.1.4.2. Micro-Averaging   49

3.2 Giới thiệu bài toán thực nghiệm 49

3.3 Môi trường thực nghiệm 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

DANH MỤC CÁC THUẬT NGỮ VÀ TỪ VIẾT TẮT

Supervised learning  Supervised learning  Học có giám sát 

Semi-supervised 

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

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

Hình 3.3: Mô hình giai đoạn phân lớp   43

Hình 3.4: Chi tiết giai đoạn phân lớp   43

Hình 3.5: So sánh độ chính xác và độ bao phủ bộ dữ liệu ban đầu   57

Hình 3.6: So sánh độ chính xác và độ bao phủ bộ dữ liệu sau khi “stemming”    57  

DANH MỤC CÁC BẢNG

Bảng 2.1: Dữ liệu huấn luyện thời tiết  28

Bảng 2.2: Dữ liệu kết quả huấn luyện   29

Bảng 2.3: Bộ từ vựng   31

Bảng 2.4: Dữ liệu huấn luyện cây quyết định   33

Bảng 2.5: Dữ liệu kiểm tra   35

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

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 Zhu đã cho một cái nhìn tổng quan về các thuật toán nói trên [16]. 

Trích chọn thông tin trên  Web đã và  đang tạo thêm nhiều tài nguyên thông tin, tri thức mới đáp ứng ngày càng hiệu quả nhu cầu thông tin của con người. Ngày nay, công nghệ trích chọn thông tin trên  Web đã hình thành loại hình dịch vụ đầy triển  vọng  trong  việc  cung  cấp  thông  tin  phong  phú  và  hữu  ích  từ  nguồn  dữ  liệu được coi là vô hạn trên Web. Tự động phân lớp văn bản là một nhiệm vụ rất quan trọng có thể giúp ích cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn này. 

Với mục tiêu góp phần vào lĩnh vực nghiên cứu và ứng dụng phân loại văn bản vào cuộc sống, tác giả đã chọn đề tài “Ứ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”  làm  đề  tài  nghiên  cứu  luận  văn  tốt nghiệp thạc sĩ chuyên ngành hệ thống thông tin.  

2 Mục đích nghiên cứu

Nghiên cứu tổng quan về học máy và một số phương pháp học máy, nghiên cứu một số thuật toán học có giám sát, học nửa giám sát từ kết quả thu được đề tài cài đặt ứng dụng thử nghiệm vào bài toán phân loại văn bản. 

3 Đối tượng và phạm vi nghiên cứu

Luận văn này thực hiện nghiên cứu các kiến thức cơ bản về học máy, một số các thuật toán học có giám sát, nửa giám sát và ứng dụng phân loại văn bản.  

4 Phương pháp nghiên cứu

Nghiên cứu lý thuyết:

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ả năng học tập giống con người là một lĩnh vực nghiên cứu rất được chú ý trong thời đại hiện nay. 

Học máy (machine learning) [5],[6] là một ngành khoa học nghiên cứu, xây dựng  các  kĩ  thuật  trên  nền  tảng  của  trí  tuệ  nhân  tạo  giúp cho  máy  tính  có  thể  suy luận  (dự  đoán)  kết  quả  tương  lai  thông  qua  quá  trình  huấn  luyện  (học)  từ  dữ  liệu lịch sử . 

Qua đó ta thấy học máy có liên quan rất mật thiết với thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhưng học máy khác với thống kê ở chỗ, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Học máy được ứng dụng vào nhiều lĩnh vực như: Máy truy vấn dữ liệu, chẩn đoán y khoa, phát hiện thẻ tín dụng giả, phân tích thị trường chứng khoán, nhận dạng tiếng nói và chữ viết, dịch tự động, chơi trò chơi và hoạt động rô-bốt,   

Mô hình toán học [5]. 

Cho một tập dữ liệu  X  

+ Một tập mẫu  TX  

+ Một số hàm mục tiêu  f  :  X→ {đúng, sai} 

+ Một tập huấn luyện D x y, |xT y,  f x( )  

+ Tính toán một hàm  f' :  X→{đúng, sai} sao cho f '( )x  f x( ),  x X . 

1.2 Một số khái niệm cơ bản trong học máy

1.2.1 Không gian biểu diễn của dữ liệu

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, 

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. 

1.2.6 Quá trình tìm kiếm trong không gian giả thuyết

Trong  một  không  gian  các  giả  thiết  X,  học  trở  thành  bài  toán  tìm  kiếm  giả thiết tốt nhất trong X. 

Nếu ta đánh giá mỗi giả thiết bởi một hàm "mục tiêu" thì ta xét học như một 

bài toán tối ưu hoá. Nghĩa là bài toán tìm phần tử của  X  làm tối ưu hàm mục tiêu. 

Trong học máy người ta thường dùng tối ưu không ràng buộc hoặc tối ưu có ràng buộc. Các phương pháp tối ưu hoá thường dùng trong học máy như  Gradient, nhân tử Lagrange  

1.3 Học có giám sát

1.3.1 Khái niệm

Học có giám sát (supervised learning) [5],[16] là một kỹ thuật của ngành học máy nhằm  mục  đích  xây  dựng  một  hàm  f từ  dữ  tập  dữ  liệu  huấn  luyện  (Training data). Dữ  liệu  huấn  luyện bao  gồm  các  cặp  đối  tượng  đầu  vào  và  đầu  ra  mong 

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 {( ,x y1 1), ( ,x y2 2), , (x y n, n)}. Trong 

đó y i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( )y i i n T[ ] 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 ( ,x y i i) 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) 

 Mô hình sinh mẫu 

Phương  pháp  này  sẽ  tạo  ra  một  mô  hình  mật  độ  phụ  thuộc  vào  lớp  conditional density) p(x|y) bằng một vài thủ tục học không có giám sát. Một mật độ sinh có thể được suy luận bằng cách sử dụng lý thuyết Bayes. 

(class-( | ) (class-( )( | )

1.3.2 Cách giải một bài toán học có giám sát

Để giải một bài toán học có giám sát  ta thực hiện theo các bước sau: 

Bước  1:  Xác  định  loại  của  các  dữ  liệu  huấn  luyện:  Trước  tiên  ta  cần  phải quyết định xem loại dữ liệu nào sẽ được sử dụng làm dữ liệu huấn luyện. Ta có thể chọn  dữ  liệu    một  kí  tự  viết  tay  đơn  lẻ,  toàn  bộ  một  từ  viết  tay,  hay  toàn  bộ  một 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 

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 

ra một mô hình phù hợp với các quan sát. Học không có giám sát khác với học có giám sát ở chỗ, là đầu ra đúng tương ứng cho mỗi đầu vào là chưa biết trước. Trong học  không  có  giám  sát,  một  tập  dữ  liệu  đầu  vào  thường  được  thu  thập  một  cách ngẫu nhiên,  và sau  đó  một  mô  hình  mật  độ  kết  hợp  sẽ  được xây  dựng  cho  tập  dữ liệu đó. 

Ta có  thể kết  hợp  học  không có  giám sát  với  suy  diễn  Bayes  để  tạo  ra  xác suất có điều kiện cho bất kỳ biến ngẫu nhiên nào khi biết trước các biến khác. Hay nói cách khác khi đó ta đã chuyển từ việc học không có giám sát sang học có giám sát. Mọi giải thuật nén dữ liệu, về cơ bản hoặc là dựa vào một phân bố xác suất trên một  tập  đầu  vào  một  cách  tường  minh  hay  không  tường  minh.  Do  đó  trong  công nghệ nén dữ liệu học không có giám sát được ứng dụng một cách rất hữu dụng. 

1.4.2 Mô hình toán học

Chẳng hạn cho trước một mẫu chỉ gồm các đối tượng (objects), cần tìm kiếm cấu trúc đáng quan tâm (interesting structures) của dữ liệu, và nhóm các đối tượng giống nhau. Biểu diễn toán học của phương pháp này như sau: 

Đặt X  ( ,x x1 2, ,x n) là tập hợp gồm n mẫu (examples or points), x  i X với mọi  i ∈ [ ]:={1,2, ,n}.  Thông  thường,  ta giả  thiết  các  mẫu  được  tạo  ra một  cách độc lập và giống nhau (i.i.d – independently and identically distributed) từ một phân phối chung trên X. Mục đích của học không có giám sát là tìm ra một cấu trúc thông minh (interesting structures) trên tập dữ liệu đó. 

1.5 Học nửa giám sát

1.5.1 Khái niệ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 

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. 

Tóm lại học nửa giám sát là một phương pháp của ngành học máy nhằm xây dựng một hàm mục tiêu từ các dữ liệu huấn luyện. Sau đó tổng quát hóa thành mô hình chung cho tất cả các dữ liệu gán nhãn và chưa được gán nhãn. Nhằm mục đính tìm ra một kết quả mong đợi. 

CHƯƠNG 2 - MỘT SỐ THUẬT TOÁN HỌC NỬA GIÁM SÁT

2.1 Mô hình sinh và thuật toán kỳ vọng cực đại

2.1.1 Giới thiệu về mô hình sinh

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

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.    

là không hoàn chỉnh, ta cũng có thể liên tưởng đến một vài biến ẩn với dữ liệu thiếu  2.1.3.2. Nội dung thuật toán 

Đầu vào:

D : Tập dữ liệu có nhẵn và chưa có nhãn. 

L : Tập dữ liệu đã gán nhãn trong D. 

U : Tập dữ liệu chưa có nhãn trong D

| (

|

|

1 ) ( ) , ( )

| (

|

|

) , ( )

| ( 1

d

D d

D c P d n d c P W

t d n d c P

t d n t d

d

t d n

l c l L P c d

)}

,({)

|()

|

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: 

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 

ra xác định tối ưu bằng giải thuật kỳ vọng cực đại sẽ làm ảnh hưởng đến những dữ liệu không được gán nhãn nếu mô hình bị sai. 

2.2 Thuật toán tự huấn luyện

2.2.1 Giới thiệu thuật toán tự huấn luyện

Tự huấn luyện (Self-training) là một phương pháp phổ biến ra đời vào những năm 1960 đến 1970, được sử dụng trong lĩnh vực học nửa giám sát. Trong phương pháp  này,  với  một  bộ  phân  lớp  (classfier)  ban  đầu  được  huấn  luyện  bằng  một  số lượng nhỏ các dữ liệu đã gán nhãn. Bộ phân lớp sau đó được sử dụng để gán nhãn cho các dữ liệu chưa gán nhãn. Các dữ liệu được gán nhãn có độ tin cậy cao (vượt trên  một  ngưỡng  nào  đó)  và  nhãn  tương  ứng  của  chúng  được  đưa  vào  tập  huấn luyện  (train  set).  Tiếp  đó  bộ  phân  lớp được  học  lại  trên  tập  huấn  luyện  mới  ấy  và thủ tục lặp tiếp tục. Ở mỗi vòng lặp, bộ học sẽ chuyển một vài các mẫu tin có độ tin cậy cao nhất sang tập dữ liệu huấn luyện cùng với các dự đoán phân lớp của chúng. Tên  gọi  self-training  xuất  phát  từ  việc  nó  sử  dụng  dự  đoán  của  chính  nó  để  dạy chính nó.  

Thuật toán: 

Repeat

Huấn luyện bộ phân lớp có giám sát h trên tập L; 

2.2.2 Đánh giá thuật toán

Giải thuật tự huấn luyện là phương pháp đơn giản nhất trong học nửa giám sát.  Thuật  toán  tự  huấn  luyện  được  ứng  dụng  để  giải  quyết  các  bài  toán  về  xử  lý ngôn ngữ tự nhiên, các bài toán phát hiện các đối tượng hệ thống từ các hình ảnh. Ngoài  ra  thuật  toán  tự  huấn  luyện  còn  được  ứng  dụng  để  giải  quyết  các  bài  toán phân tách và dịch máy, …  

Giải thuật có mô hình toán học dễ hiểu, sáng sủa và dễ học, giải thuật có độ phức tạp phụ thuộc vào số lượng mẫu huấn luyện và độ phức tạp của bộ phân lớp có giám sát h. 

Thuật  toán  SVM  đã  được  ứng  dung  để  giải  quyết  rất  nhiều  những  bài  toán trong  các  lĩnh  vực  khác  nhau.  Đặc  biệt  SVM  đã  được  ứng  dụng  để  giải  quyết  bài toán phân lớp văn bản và thu được nhưng thành tựu rất tích cực, nó đã được chứng minh là một trong những thuật toán phân lớp văn bản mạnh nhất để giải quyết bài toán này [17]. 

Hình 2.3 sẽ minh hoa cho ý tưởng phân lớp của thuật toán SVM. 

 Nội dung thuật toán SVM

Nôi dung giải thuật dựa trên bài toán phân lớp đơn giản nhất là bài toán phân lớp nhi phân. với tập dữ liệu huấn luyện như sau: 

D = {(xi, yi) | xi  RP, yi  {-1, 1}, i = 1, 2, …, n} 

Trong đó tập dữ liệu huấn luyện là các vector đối tượng được phân lớp thành các mẫu dương và mẫu âm. 

+ Các mẫu dương là các mẫu xi thuộc lĩnh vực quan tâm và được gán nhãn yi = 1. 

Các  mẫu dương Các 

mẫu âm 

Mặt  siêu phẳng lề 

Hình 2.3 Phân lớp SVM

Bài toán lúc này chính là một bài toán tối ưu với mục tiêu là tìm ra một không gian H và siêu mặt phẳng quyết định h trên H sao cho sai số phân lớp là nhỏ nhất. Trong tình  huống  này  bộ  phân  lớp  SVM  là  mặt  siêu phẳng  phân  tách  các  mẫu dương  và  các  mẫu  âm  ra  thành  hai  nhóm  với  độ  chênh  lệch  là  cực  đại.  Trong  đó khoảng cách giữa các mẫu dương và các mẫu âm gần mặt siêu phẳng nhất còn được gọi là lề. Mặt siêu phẳng này được gọi là mặt siêu phẳng lề tối ưu.  

Trong không gian đối tượng, mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm thỏa mãn:  w x + b = 0. 

Với w là một véc tơ pháp tuyến của siêu phẳng hay còn gọi là véc tơ trọng số, b 

là độ dịch. Khi ta thay đổi w và b thì hướng và khoảng cách từ gốc toạ độ đến mặt siêu phẳng thay đổi. 

Bộ phân lớp SVM được xác định như sau:

Bô phân lớp SVM phụ thuộc vào tham số vector trọng số w và độ dịch b. Mục tiêu của phương pháp SVM là ước lượng w và b sao cho cực đại hoá lề giữa các lớp 

dữ liệu dương và âm.  

Vậy chúng ta cần chọn w và b để cực đại hóa lề sao cho khoảng cách giữa hai siêu mặt song song ở xa nhau nhất có thể trong khi vẫn phân chia được dữ liệu. Các siêu phẳng được xác định bằng các công thức sau:  

w x + b = 1 và  w x + b = -1. 

Ta thấy rằng nếu dữ liệu huấn luyện có thể được chia tách một cách tuyến tính, thì ta có thể chọn hai siêu phẳng của lề sao cho không có điểm nào nằm giữa chúng 

và sau đó tiến hành tăng khoảng cách giữa  chúng đến tối đa  có thể. Bằng phương 

Ta  có  thể  giải  bài  toán  này  bằng  các  kĩ  thuật  gải  bài  toán  quy  hoạch  toàn phương. Theo điều kiện Karush–Kuhn–Tucker lời giải của bài có thể được viết dưới dạng tổ hợp tuyến tính của các vector huấn luyện như sau: 

w

1

y x w N

b

1

) (

1

  Sau  khi  tìm  được  vector  trọng  số  w  và  độ  dịch  b.  Từ  đó  ta  xây  dựng  được phương trình tổng quát của siêu phẳng tìm được bởi thuật toán SVM như sau:   f(x) = w x + b; 

y x w N

b

1

) (

Có  thể  nói  giải  thuật  huấn  luyện  SVM  là  việc  giải  bài  toán  quy  hoạch  toàn phương.  Để  giải  bài  toán  quy  hoạch  này  ta  cần  phải  lưu  trữ  một  ma  trận  có  kích thước  bằng  bình  phương  của  số  lượng  mẫu  huấn  luyện,  mà  trong  những  bài  toán thực tế thông thường kích thước của tập dữ liệu huấn luyện là rất lớn, dẫn đến việc giải bài toán này là không khả thi. Tuy nhiên có rất nhiều thuật toán khác nhau được nghiên cứu để giải quyết vấn đề này. Các thuật toán này thường phân rã tập dữ liệu huấn luyện thành những nhóm dữ liệu nhỏ để thực hiện giải bài toán tối ưu. Nghĩa 

là bài toán quy hoạch toàn phương ban đầu được chia thành các bài toán quy hoạch toàn phương với kích thước nhỏ hơn. Sau đó những thuật toán này kiểm tra các điều kiện Karush-Kuhn-Tucker để xác định phương án tối ưu, … 

Qua đó ta có nhận định sau: Giải thuật SVM có ưu điểm là thích hợp cho nhiều kiểu xử lý dữ liệu. Giải thuật có mô hình toán học dễ hiểu, sáng sủa. Tuy nhiên giải thuật SVM còn có những mặt hạn chế như độ phức tạp cao, giải quyết bài toán tối 

ưu  khó.  Hơn  nữa  thuật  toán  lại  chỉ  chấp  nhận  những  dữ  liệu  huấn  luyện  có  gán nhãn, mà việc xây dựng các dữ liệu huấn luyện có gán nhãn đòi hỏi tốn thời gian và công sức. Đây cũng chính là nhược điểm của các phương pháp học có giám sát. Để giải quyết vấn đề trên người ta đã đề xuất  một phương pháp SVM cải tiến  mà tận dụng  được  các  khả năng  của  dữ  liệu  huấn  luyện  đã  gán  nhãn  và  dữ  liệu  chưa  gán nhãn. Trong phần tiếp theo ta sẽ đi tìm hiểu phương pháp SVM cải tiến, hay còn gọi 

là phương pháp học bán giám sát SVM.      

2.3.2 Giới thiệu thuật toán S3VM

Thuật toán S3VM (Semi-supervised support vector machine) có mục đích nhằm xây dựng một máy hỗ trợ vector sử dụng tập dữ liệu huấn luyện là một lượng nhỏ các  dữ  liệu  đã  gán  nhãn  (training  set)  và  một  lượng  lớn  chưa  gán  nhãn  (working set). Bài toán truyền dẫn sẽ dự đoán giá trị của một hàm phân lớp tới các điểm đã cho trong tập dữ liệu chưa gán nhãn.  

Thuật toán S3VM được xây dựng để sử dụng hỗn hợp dữ liệu huấn luyện là dữ liệu đã gán nhãn và chưa gán nhãn với mục đích là gán các nhãn cho dữ liệu trong tập dữ liệu huấn luyện chưa gán nhãn một các tốt nhất có thể. Sau đó sử dụng hỗn 

Ta nhân thấy rằng nếu toàn bộ dữ liệu huấn luyện đã được gán nhãn thì bài toán này lại trở thành bài toán học  có giám sát SVM (Support vector  machine). Ngược lại nếu toàn bộ dữ liệu huấn luyện chưa được gán nhãn thì bài toán lại trở thành bài toán học không giám sát. 

2.3.3 Nội dung thuật toán S3VM

i

i i y

b w

b x w y u

b wx y l

w

,

)) (

1 , 0 max(

2

' )) (

1 , 0 max(

1

))(

,0

max(

1

. Tập dữ liệu chưa gán nhãn sau khi đã gán nhãn sẽ được đưa vào tập dữ liệu huấn luyện, tiếp theo đó sẽ sử dung thuật toán SVM để học tạo ra SVM mới, SVM này chính là S3VM có một siêu phẳng mới. Sau đó áp dụng siêu phẳng này để phân lớp các mẫu dữ liệu mới được đưa vào. 

2.3.4 Nhận xét về S3VM

Vậy  giải  thuật  S3VM  chính  là  một  phương  pháp  cải  tiến  của  giải  thuật  SVM, giải thuật đã tân dụng được những ưu điểm của học có giám sát là có độ chính xác cao và đã tận dụng được nguồn đữ liệu huấn luyện không gán nhãn rất sẵn có nhằm giải quyết bài toán phân lớp một cách tối ưu. Tuy nhiên vì giải thuật được xây dựng trên  nền  tảng là  giải  thuật  SVM  nên  nó  vẫn  gặp  phải  những  vẫn  đề  của giải  thuật SVM như sự bùng nổ tổ hợp, độ phức tạp cao, giải quyết bài toán tối ưu khó, …  2.4 Thuật toán K - láng giềng gần nhất

2.4.1 Giới thiệu thuật toán

K-Nearest  Neighbors  algorithm  (K-NN)  [24]  được  sử  dụng  rất  phổ  biến trong lĩnh vực Data Mining. K-NN là phương pháp để phân lớp các đối tượng dựa vào  khoảng  cách  gần  nhất  giữa  đối  tượng  cần  xếp  lớp (Query  point)  và  tất  cả  các đối tượng trong dữ liệu huấn luyện. 

Một đối tượng được phân lớp dựa vào K láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các đối tượng. 

Thuật toán K-NN được mô tả như sau: 

 Xác định giá trị tham số K (số láng giềng gần nhất) 

 Tính khoảng cách giữa đối tượng cần phân lớp với tất cả các đối tượng trong 

dữ liệu huấn luyện (thường sử dụng khoảng các Euclidean, Cosine ) 

 Sắp xế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 

 Lấy tất cả các lớp của K láng giềng gần nhất đã xác định 

 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 đối tượng 

2.4.2 Áp dụng KNN vào bài toán phân loại văn bản

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 Euclidean, 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ả 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 độ 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. 

Khoảng cách giữa 2 văn bản chính là độ tương tự giữa 2 văn bản đó, 2 văn bản có giá trị độ tương tự càng lớn thì khoảng cách càng gần nhau. 

 Các bước thực hiện thuật toán KNN 

Thông  thường  các  thuật  toán  sẽ  gồm  2  giai  đoạn  huấn  luyện  và  phân  lớp, riêng đối với thuật toán KNN do thuật toán này không cần tạo ra mô hình khi làm trên tập huấn luyện các văn bản đã có nhãn/lớp sẵn, nên không cần giai đoạn huấn luyện (giai đoạn huấn luyện của KNN là gán nhãn cho các văn bản trong tập huấn luyện bằng cách gom nhóm các văn bản có vector đặc trưng giống nhau thành cùng 

1 nhóm). 

Mô  tả  vector  đặc  trưng  của  văn  bản:  Là  vector  có  số  chiều  là  số  đặc  trưng trong toàn tập dữ liệu, các đặc trưng này đôi một khác nhau. Nếu văn bản có chứa đặc trưng đó sẽ có giá trị 1, ngược lại là 0.