Trang 2

MỤC LỤC
LỜI CAM ĐOAN.................................................................................................. 1
MỤC LỤC ............................................................................................................. 2
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ........................................... 4
DANH MỤC CÁC BẢNG.................................................................................... 5
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................... 6
MỞ ĐẦU ............................................................................................................... 7
CHƢƠNG 1 – GIỚI THIỆU ................................................................................. 8
1.1. Lý do chọn đề tài ................................................................................... 8
1.2.

Mục tiêu, phạm vi nghiên cứu của đề tài ............................................ 10

CHƢƠNG 2 – KHAI PHÁ QUAN ĐIỂM VÀ ỨNG DỤNG ............................ 11
2.1. Khai phá quan điểm (Opinion mining) ............................................... 11
2.1.1.

Các khái niệm liên quan................................................................ 11

2.1.2.

Khai phá quan điểm ...................................................................... 12

2.1.3.
2.1.4.

Động lực và Ứng dụng của Khai phá quan điểm.......................... 13
Thách thức của Khai phá quan điểm ............................................ 14


2.3.2.

Thuật toán bán giám sát cực đại EM đại phƣơng ......................... 28

2.3.3. Thuật toán Self-training ................................................................ 29
2.4. Phƣơng pháp đánh giá bộ phân lớp ..................................................... 30
2.5.

Kết luận................................................................................................ 31

CHƢƠNG 3 – ỨNG DỤNG HỌC BÁN GIÁM SÁT VÀO BÀI TOÁN KHAI
PHÁ QUAN ĐIỂM ............................................................................................. 33
3.1. Tổng quát về hƣớng tiếp cận và giải quyết bài toán ........................... 33
3.2.

Lựa chọn dữ liệu .................................................................................. 34

3.2.1.
3.2.2.

Kho tài liệu MPQA2.0(Multi-Perspective Question Answering) 35
SentiWordNet ............................................................................... 39


Trang 3

3.3. Trích chọn đặc trƣng và xác định nhãn ............................................... 40
3.3.1. Đặc trƣng SentiWordNet Score (SS) ............................................ 40
3.3.2.


Các tiêu chí chuẩn bị dữ liệu ........................................................ 50

3.5.3. Các cách chọn dữ liệu ................................................................... 50
3.6. Huấn luyện, đánh giá ........................................................................... 53
3.6.1.

Thƣ viện LibSVM ......................................................................... 54

3.6.2.

Học có giám sát ............................................................................. 55

3.6.3.

Học bán giám sát Co-training ....................................................... 55

3.7.

Kết luận................................................................................................ 55

CHƢƠNG 4 – THỰC NGHIỆM ........................................................................ 56
4.1. Thực nghiệm 1 ..................................................................................... 56
4.2. Thực nghiệm 2 ..................................................................................... 57
4.3.

Thực nghiệm 3 ..................................................................................... 60

KẾT LUẬN ......................................................................................................... 62
5.1. Kết luận................................................................................................ 62
5.1.1.

Bảng 3.2 Bảng mô tả chi tiết các kí hiệu từ loại. ................................................ 42
Bảng 3.3. Xác định từ loại của các từ trong câu. ................................................ 44
Bảng 3.4. Các thông số liên quan đến đặc trƣng TFIDF .................................... 45
Bảng 3.5. Thông số TFIDF của những từ thuộc câu s1. ..................................... 46
Bảng 3.6. Thông số TFIDF của những từ thuộc câu s2. ..................................... 46
Bảng 3.7. Thống kê dữ liệu tập con ORI ............................................................ 49
Bảng 3.8. Thống kê dữ liệu tập con ULA ........................................................... 49
Bảng 3.9. Thống kê dữ liệu tập con XBANK ..................................................... 50
Bảng 3.10. Chọn dữ liệu cho Thực nghiệm 1. .................................................... 51
Bảng 3.11. Chọn dữ liệu cho Thực nghiệm 2 ..................................................... 52
Bảng 3.12. Chọn dữ liệu cho Thực nghiệm 3 ..................................................... 53
Bảng 4.1. Kết quả của Thực nghiệm 1 theo nhãn tính chủ quan ........................ 56
Bảng 4.2. Kết quả của Thực nghiệm 1 theo nhãn tính phân cực cảm nghĩ ........ 57
Bảng 4.3. Các đặc trƣng, thông số tốt nhất cho từng bài toán phân lớp con. ..... 57
Bảng 4.4. Số lƣợng mẫu huấn luyện/đánh giá dùng cho Thực nghiệm 2. .......... 58
Bảng 4.5. Kết quả của Thực nghiệm 2 theo nhãn tính chủ quan. ....................... 59
Bảng 4.6. Kết quả của Thực nghiệm 2 theo nhãn tính phân cực cảm nghĩ. ....... 59
Bảng 4.7. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 10%, 70% .............. 60
Bảng 4.8. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 20%, 60% .............. 60
Bảng 4.9. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 30%, 50% .............. 61
Bảng 4.10. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 40%, 40% ............ 61
Bảng 4.11. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 50%, 30% ............ 61
Bảng 4.12. Kết quả Thực nghiệm 3 khi chọn L, U theo tỉ lệ 60%, 20% ............ 61


Trang 6

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1. Minh họa về “Máy học” ...................................................................... 17
Hình 2.2. Minh họa các hƣớng nghiên cứu học máy. ......................................... 18

dùng kỹ thuật Co-training vào phân tích tính chủ quan và phân tích cảm nghĩ, thì
chƣa đƣợc phổ biến nhiều qua các bài báo, bằng cả tiếng Việt và tiếng Anh,
đƣợc công khai trên mạng. Ngoài ra việc phân tích ở mức câu cũng là một trở
ngại so với ở mức tài liệu [5].
Đề tài luận văn này định hƣớng giải quyết bài toán phân lớp các câu cảm
nghĩ nhƣ sau: Cho một tập văn bản gồm nhiều câu văn tiếng Anh. Phân lớp xem
câu nào là câu mô tả cảm nghĩ, câu nào không. Đối với những câu mô tả cảm
nghĩ, dùng bộ phân lớp phân cực để xác định đó là câu mô tả cảm nghĩ tích cực,
tiêu cực hay trung lập. Trong đó, các bộ phân lớp đƣợc xây dựng dựa trên kỹ
thuật Co-training.
Trên cơ sở định hƣớng đó, nội dung trình bày báo cáo luận văn bao gồm:
(1) lý do, mục tiêu của đề tài và các đề tài nghiên cứu liên quan – Chƣơng 1; (2)
trình bày các kiến thức cơ sở liên quan – Chƣơng 2; (3) cách tiếp cận và giải
quyết bài toán – Chƣơng 3; (4) thực nghiệm và các kết quả - Chƣơng 4; (5) kết
luận và hƣớng phát triển của đề tài.


Trang 8

CHƢƠNG 1 – GIỚI THIỆU
1.1. Lý do chọn đề tài
Khai phá dữ liệu (KPDL) là một chuyên ngành mới, thu hút đƣợc nhiều
nghiên cứu trong thời gian gần đây. Hƣớng tiếp cận và giải quyết vấn đề dựa
trên KPDL là hoàn toàn khác so với cách xử lý Cơ sở dữ liệu (CSDL) truyền
thống. Trong xử lý CSDL truyền thống, các thao tác xử lý chỉ có thể truy xuất và
đƣa ra các thông tin đã có dƣới dạng liệt kê các giá trị dựa trên tính toán, thống
kê các giá trị bản ghi hoặc một báo cáo gồm tập hợp nhiều giá trị bản ghi, giá trị
tính toán, thống kê khác nhau. KPDL có thể đƣa ra kết quả là những tri thức
tiềm ẩn trong tập dữ liệu mà các xử lý truyền thống nhƣ trƣớc đây không thể
truy vấn đƣợc.

dựng từ tập dữ liệu có nhãn. Do vậy dữ liệu chƣa đƣợc gán nhãn là vô dụng đối
với học có giám sát. Nếu tận dụng đƣợc cả dữ liệu chƣa có nhãn mà có thể nâng
cao đƣợc hiệu năng so với học có giám sát thì sẽ đƣợc lợi là không phải làm việc
gán nhãn một cách thủ công với những dữ liệu chƣa có nhãn có thể đƣợc thu
thập một cách dễ dàng. Việc tận dụng cả dữ liệu chƣa đƣợc gán nhãn để xây
dựng mô hình / hàm phân lớp tốt hơn nhƣ vậy đƣợc gọi là học bán giám sát.
Chính vì những lý do nêu trên mà đề tài đƣợc định hƣớng giải bài toán
khai phá quan điểm dựa trên học bán giám sát.
Những vấn đề liên quan trọng Khai phá quan điểm cần đƣợc tham khảo từ
những đề tài, nghiên cứu khác bao gồm: các đặc trƣng, thuật toán Co-training,
thuật toán phân lớp trong bài toán khai phá quan điểm. Mỗi vấn đề tồn tại trong
rất nhiều nghiên cứu đã đƣợc công bố. Ở đây chỉ liệt kê một hoặc hai nghiên cứu
tiêu biểu nhất cho mỗi vấn đề.
Liên quan đến trích chọn đặc trƣng trong bài toán Khai phá quan điểm, có
nhiều nghiên cứu, trong đó tiêu biểu là “Sentence Level Subjectivity and
Sentiment Analysis Experiments in NTCIR-7 MOAT Challenge” [3]. Nghiên
cứu này có cách tiếp cận 2 bài toán phân lớp ở mức câu trong Khai phá quan
điểm trên các tập dữ liệu khác nhau, trong đó các thực nghiệm đƣợc tiến hành
với nhiều đặc trƣng câu khác nhau đƣợc chia thành các nhóm đặc trƣng nhất
định.
Về thuật toán Co-training, có rất nhiều nghiên cứu tiếp theo sau bài báo
của Tom Mitchell, tác giả đề xuất ra giải thuật. Tuy nhiên, nghiên cứu của chính
tác giả, đạt giải thƣởng bài báo xuất sắc nhất của ICML năm 1998 (Best paper of
ICML 1998) và giải thƣởng bài báo xuất sắc nhất trong 10 năm của
ICML/COLT (ICML/COLT 10-Year Best Paper Award) vào năm 2008, là cơ
bản nhất.
“Combining Labeled and Unlabeled Data with Co-Training” [4], của hai
tác giả Avrim Blum và Tom Mitchell, năm 1998: đề xuất thuật toán Co-Training
và chứng minh đƣợc tính hiệu quả của nó so với phân lớp dựa trên học máy có
giám sát.

xuất; các bƣớc tiền xử lý và chuẩn bị dữ liệu cho phân lớp, cài đặc hai bộ phân
lớp con riêng lẻ, hai bộ phân lớp con dựa trên Co-training với các nhãn phân lớp
tƣơng ứng là nhãn về sự tồn tại cảm nghĩ và nhãn về tính phân cực cảm nghĩ ở
mức câu; cuối cùng thực hiện huấn luyện và đánh giá trên cùng các tập huấn
luyện và đánh giá; tổng hợp các kết quả và đánh giá.


Trang 11

CHƢƠNG 2 – KHAI PHÁ QUAN ĐIỂM VÀ ỨNG DỤNG
2.1. Khai phá quan điểm (Opinion mining)
2.1.1. Các khái niệm liên quan
a. “Opinion” (ý kiến, quan điểm) đƣợc từ điển “Oxford Advanced
Learner’s Dictionary” định nghĩa là “your feelings or thoughts about
sb/sth, rather than a fact”. Dịch ra tiếng Việt là “cảm xúc hoặc suy
nghĩ về ngƣời/vật chứ không phải là một sự thật”.
b. “Ý kiến” theo “Từ điển Bách khoa toàn thƣ Việt Nam”
(bachkhoatoanthu.gov.vn): “trong triết học cổ đại, là một loại tri thức
cấp thấp, và trái với khoa học, không đƣợc biện minh bằng một suy lí.
Do đó YK có thể xác thực, có thể không xác thực, không phù hợp với
chân lí. Với Platôn (Platôn; nhà triết học Hi Lạp cổ đại), YK phải là
một tri thức đúng, nhƣng không thể biện minh, không thể đem ra giảng
dạy đƣợc. Phái Êlêa [mang tên thành phố cổ Êlêa (Elea; Hi Lạp)] quan
niệm YK là tri thức dựa trên những tri giác cảm tính và chỉ cho biết
đƣợc bề ngoài sự vật thôi, YK khác với nhận thức duy lí là nhận thức
chân lí. Với Arixtôt (Aristote; nhà triết học Hi Lạp cổ đại), YK khác
với tri thức khoa học, vì tri thức khoa học là tri thức nhận thức đƣợc
cái tất yếu và cái phổ biến.”
Dựa trên sự tồn tại của cảm nghĩ mà thông tin dạng text có thể đƣợc chia
làm hai loại chính, đó là sự thật và cảm nghĩ. Sự thật (không mang cảm nghĩ) là

mục của từ điển.
2.1.2. Khai phá quan điểm
Khai phá quan điểm, một dạng của xử lý ngôn ngữ tự nhiên, là một lĩnh
vực nghiên cứu mới nhằm trích rút thông tin về cảm nghĩ từ các nguồn dữ liệu
text. Cụ thể, Khai phá quan điểm bao gồm phân tích tính chủ quan và tính cảm
nghĩ trong văn bản (Subjectivity and Sentiment Analysis). Trong đó, phân tích
tính chủ quan hƣớng đến việc tự động nhận ra nội dung nào là chủ quan, nội
dung nào là khách quan. Phân tích cảm nghĩ liên quan đến một số xử lý chính
nhƣ: (1) xác định tính phân cực (polarity) của nội dung cảm nghĩ, (2) xác định
đối tƣợng của cảm nghĩ, (3) xác định chủ thể đƣa ra cảm nghĩ. [3]
Phân tích tính chủ quan là quá trình thực hiện phân loại một nội dung
dạng text thành một trong hai loại là Khách quan (Subjective) hoặc Chủ quan
(Objective).
Về tính phân cực thì các nghiên cứu đƣa ra nhiều mức độ phân loại khác
nhau, luận văn này chọn cách phân loại thành 3 lớp chính dựa trên phân loại của
MPQA2.0, đó là Tích cực (Positive), Tiêu cực (Negative) và Trung lập
(Neutral).
Trong phạm vi luận văn này, phân tích tính chủ quan là phân lớp tính chủ
quan (Subjectivity Classification). Phân tích cảm nghĩ dừng lại ở phân lớp tính


Trang 13

phân cực (Polarity Classification). Mức text ở đây là câu, cụ thể là câu văn tiếng
Anh. Việc lựa chọn ngôn ngữ tiếng Anh là do tính sẵn có của bộ dữ liệu đƣợc
đƣa ra phục vụ cho mục đích nghiên cứu.
Các bài toán phân lớp này cũng tƣơng tự nhƣng có điểm khác với phân
lớp text theo chủ đề, theo đó các tài liệu đƣợc phân loại vào các chủ đề định
trƣớc, ví dụ nhƣ chính trị, khoa học, và thể thao. Trong phân lớp theo chủ đề,
các từ liên quan đến chủ đề đóng vai trò quan trọng. Tuy nhiên, trong phân lớp

Trang 14

cáo hay đƣa ra sản phẩm mới, giúp xác định phiên bản nào của sản phẩm hoặc
dịch vụ đƣợc ngƣời dùng ƣa chuộng và cụ thể hơn là giúp chỉ ra những tính
năng nào đƣợc hoặc không đƣợc ƣa chuộng. Ví dụ, một ý kiến có thể đánh giá
cao về tổng thể về một máy ảnh, nhƣng ngƣợc lại có thể đánh giá tiêu cực về
trọng lƣợng của nó. Việc thu thập và xác định đƣợc những thông tin kiểu này
một cách có hệ thống, thông qua hệ thống khai phá quan điểm, sẽ giúp nhà sản
xuất có thể có cái nhìn rõ ràng và nhanh chóng hơn về ý kiến của ngƣời dùng so
với việc tiến hành điều tra ý kiến khách hàng. Những ý kiến này đƣợc chính
khách hàng đƣa ra và tồn tại sẵn có trên mạng Internet để có thể đƣợc thu thập
thay vì nhƣ trƣớc đây các nhà sản xuất thƣờng chi nhiều tiền để biết đƣợc thị
hiếu của khách hàng thông qua các chiến dịch điều tra khách hàng.
Đối với cá nhân thì những công cụ khai phá quan điểm giúp thu thập và
phân tích ý kiến của ngƣời khác về những vấn đề quan tâm nhƣ khi cần mua một
sản phẩm, dùng một dịch vụ hoặc khi cần tìm hiểu các ý kiến về một vấn đề
chính trị nào đó.
Ngoài ra, khai phá quan điểm có một ứng dụng khá thú vị là đặt quảng
cáo theo ngữ cảnh trên các nội dung do ngƣời dùng tạo ra trên mạng. Khi nội
dung có chứa lời khen một sản phẩm thì đặt quảng cáo của công ty mình. Và đặt
quảng cáo của công ty đối thủ nếu ngƣời dùng phê bình sản phẩm.
2.1.4. Thách thức của Khai phá quan điểm
Mặc dù việc nghiên lĩnh vực này là cần thiết, nhƣng do là lĩnh vực mới
nên nó có nhiều thách thức. Hầu hết những khó khăn này bắt nguồn từ sự giàu
đẹp của ngôn ngữ mà con ngƣời sử dụng. Hơn nữa, tùy thuộc vào trình độ kiến
thức, nghề nghiệp, tuổi tác… mà con ngƣời có cách hành văn khác nhau.
Một từ có thể đƣợc xem là mang cảm nghĩ tích cực trong một tình huống
này có thể đƣợc xem là tiêu cực trong một tình huống khác. Lấy ví dụ nhƣ từ
"long" trong tiếng Anh, có nghĩa là “dài” hoặc “lâu”. Nếu một khác hàng nhận
xét rằng thời gian sử dụng pin là “long”, thì đây là một ý kiến tích cực. Ngƣợc

 Độ dài tài liệu sẽ xác định mức độ khó.
 Kết quả phân tích quan điểm ở mức tài liệu cũng có thể đƣợc kế thừa
từ các mức nhỏ hơn.
b. Mức câu (Sentence Level): phân tích quan điểm ở mức câu có thể cho kết
quả thấp hơn so với mức tài liệu.
c. Mức cụm từ (Phrase Level): có một số tập dữ liệu mẫu, đƣợc tạo ra nhằm
phục vụ mục đích nghiên cứu, trong đó có một số thuộc tính gợi ý liên
quan đến khai phá quan điểm. Có thể dùng tập này để huấn luyện các bộ
phân lớp sau này.
Tùy vào tình huống ứng dụng cụ thể mà ta chọn một mức cho bài toán
phân lớp hoặc kết hợp các mức này với nhau để tạo ra một luật phân lớp dựa
trên các mức phân lớp trên. Hoặc cũng có thể tạo ra luật phân lớp cho mức cao
hơn bằng cách đƣa ra luật phân lớp dựa trên mức thấp. Ví dụ, một tài liệu có thể
đƣợc gán nhãn “Chủ quan” nếu tài liệu đó chứa nhiều câu có nhãn “Chủ quan”
hơn là nhãn "Khách quan”.
2.2. Các thuật toán học có giám sát


Trang 16

2.2.1. Học máy - Machine Learning
Trong [6], Tom Mitchell có định nghĩa về “Learning” và “Machine
Learning” nhƣ sau:
 Learning – Học: “Learning is about seeking a predictive and/or
executable understanding of natural/artificial subjects, phenomena, or
activities from …”. Tạm dịch là “Học là tìm kiếm một hiểu biết có thể
hiểu đƣợc và/hoặc có thể thực thi đƣợc về các chủ thể, hiện tƣợng hoặc
hoạt động tự nhiên/nhân tạo từ …”. Ở đây có thể ngầm hiểu là từ kinh
nghiệm trong quá khứ.
 Machine Learning – Học máy: “Machine Learning = Study of


Hình 2.2. Minh họa các hướng nghiên cứu học máy.

Học máy có tƣơng lai ứng dụng thiết thực vào thực tế do nó có liên quan
đến tìm kiếm một giả thiết mô tả tốt nhất dữ liệu quan sát và phù hợp với tri thức
nền, trong một không gian giả thiết rất lớn. Tuy nhiên học máy cũng có những
thách thức xung quanh những thành phần bên trong nó, nhƣ là dữ liệu học, thuật
toán học, tri thức nền, hiệu năng. Việc kết hợp các yếu tố này lại với nhau trong
một thiết lập tối ƣu là một khó khăn.
2.2.2. Học có giám sát - Supervised Learning
Học có giám sát hay còn đƣợc gọi là Phân lớp, nhƣ đã nêu trong phần
2.1.4, là tiến trình khám phá các luật phân loại hay đặc trƣng cho các tập dữ liệu
đã đƣợc xếp lớp. Mục tiêu là xây dựng đƣợc mô hình trong đó giá trị của một
biến có thể dự đoán từ các giá trị của các biến khác từ một tập dữ liệu đã biết tất
cả biến.
Có thể mô tả bài toán phân lớp nhƣ sau:
Tìm hàm 𝑓: 𝑋 → 𝑌 cho trƣớc tập dữ liệu huấn luyện 𝑥𝑖 , 𝑦𝑖 . Trong đó
𝑋 là không gian vector các thuộc tính quyết định có số chiều là 𝑛, 𝑌 là tập thuộc
tính phân lớp, chứa các giá trị 𝑦𝑖 rời rạc.
Nếu 𝑌 = 2 thì đây là phân lớp nhị phân, nếu 𝑌 > 2 thì đƣợc gọi là
phân lớp đa lớp.
Quá trình phân lớp dữ liệu gồm ba bƣớc là xây dựng mô hình, đánh giá
mô hình và vận hành mô hình.


Trang 19

a. Xây dựng mô hình: nhằm mục tiêu mô tả một tập những bộ hoặc mẫu
dữ liệu đã đƣợc định nghĩa trƣớc trong đó mỗi bộ sẽ đƣợc gán về một
lớp đƣợc xác định bởi thuộc tính nhãn lớp. Tập hợp những bộ đƣợc


Trang 20

Ý tƣởng chính của SVM là chuyển tập mẫu từ không gian biểu diễn 𝑅𝑚
của chúng sang một không gian 𝑅𝑑 có số chiều lớn hơn. Trong không gian 𝑅𝑑 ,
tìm một siêu phẳng tối ƣu để phân hoạch tập mẫu này dựa trên phân lớp của
chúng, cũng có nghĩa là tìm ra miền phân bố của từng lớp trong không gian 𝑅𝑚
để từ đó xác định đƣợc phân lớp của 1 mẫu cần nhận dạng.
Cho tập dữ liệu học 𝐷 = 𝑥𝑖 , 𝑦𝑖 , 𝑖 = 1 … 𝑛 với 𝑥𝑖 ∈ 𝑅𝑚 và 𝑦𝑖 ∈ 0,1 là
một số là một số nguyên xác định 𝑥𝑖 là dữ liệu dƣơng hay âm. Một tài liệu 𝑥𝑖
đƣợc gọi là dữ liệu dƣơng nếu 𝑦𝑖 = 1; 𝑥𝑖 đƣợc gọi là dữ liệu âm nếu 𝑦𝑖 = 0. Bộ
phân lớp tuyến tính đƣợc xác định bằng siêu phẳng:
𝑥: 𝑓 𝑥 = 𝑤 𝑇 + 𝑤0 = 0
Trong đó 𝑤 ∈ 𝑅𝑚 và 𝑤0 ∈ 𝑅 đóng vai trò là tham số của mô hình. Hàm
phân lớp nhị phân 𝑕: 𝑅𝑚 → 0,1 , có thể thu đƣợc bằng cách xác định dấu của
𝑓 𝑥 :
𝑕=

1 𝑛ế𝑢 𝑓 𝑥 > 0
0 𝑛ế𝑢 𝑓 𝑥 ≤ 0

Học bộ phân lớp của mô hình bao gồm việc xác định 𝑤 và 𝑤0 từ dữ liệu.
Với thuật toán này, mỗi dữ liệu đƣợc xem là một điểm trong mặt phẳng. Dữ liệu
học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho
hàm phân lớp phù hợp với tất cả các nhãn, tức là 𝑦𝑖 = 𝑓 𝑥𝑖 > 0, ∀𝑖 = 1 … 𝑛.
Với giả thuyết này, Rosenblatt đã đƣa ra một thuật toán đơn giản để xác định
siêu phẳng:
1.
2.
3.

Hình 2.3. Mối quan hệ giữa các siêu phẳng phân cách

Trong Hình 2.3, giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dƣơng
đều tuân theo luật phân bố chuẩn Gaussian, và đƣợc tạo ra với cùng một xác
suất. Khi đó một siêu phẳng phân cách đƣợc gọi là lý tƣởng nếu nó làm cực tiểu
xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu
phẳng phân cách lý tƣởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có
mật độ xác suất lớn nhất.
Rõ ràng các siêu phẳng đƣợc xây dựng nhằm phân cách các điểm dữ liệu
mẫu có thể lệch đi rất nhiều so với siêu phẳng lý tƣởng, do đó sẽ dẫn tới việc
phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định
siêu phẳng lý tƣởng sẽ tăng theo số chiều của không gian đầu vào m, vì với một
số lƣợng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế sẽ tăng theo
hàm mũ với lũy thừa m. Với bài toán phân lớp văn bản, m thƣờng rất lớn,
khoảng vài ngàn hay thậm chí là hàng triệu từ.


Trang 22

Hình 2.4. Siêu phẳng tối ưu và biên

Lý thuyết thống kê đƣợc phát triển bởi Vapnik năm 1998 chỉ ra rằng có
thể xác định một siêu phẳng tối ƣu thoả mãn hai tính chất quan trọng: (1) nó là
duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; (2) khả năng overfitting là
nhỏ hơn so với các siêu phẳng khác. Định nghĩa biên 𝑀 của bộ phân lớp là
khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ƣu
là siêu phẳng có biên lớn nhất, điều đó có nghĩa là ta cần tìm siêu phẳng sao cho
khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 2.4).
Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ƣu nhỏ
hơn so với các siêu phẳng khác.

1
𝐿 𝐷 =− 𝑤
2

𝑛
2

𝛼𝑖 𝑦𝑖 𝑤 𝑇 + 𝑤0 − 1

+
𝑖=1

Sau đó tính đạo hàm của phƣơng trình trên theo 𝑤, 𝑤0 ta đƣợc:
1
max − αT Λα +
α
2

n

αi thỏ amãn αi ≥ 0, i = 1 … n
i=1

Với Λ là ma trận 𝑛 × 𝑛 trong đó αi = yi yj xiT xj . Đây là bài toán bậc hai,
theo lý thuyết có thể giải đƣợc bằng phƣơng pháp chuẩn tối ƣu. Với mỗi dữ liệu
học i, cách giải phải thoả mãn điều kiện:
𝛼𝑖 𝑦𝑖 𝑤 𝑇 + 𝑤0 − 1 = 0
Và do đó hoặc 𝛼𝑖 = 0 hoặc 𝑦𝑖 𝑤 𝑇 + 𝑤0 = 1. Nói cách khác, nếu 𝛼𝑖 > 0
thì khoảng cách từ điểm xi đến mặt phẳng phân cách là M.
Các điểm thoả mãn 𝛼𝑖 > 0 đƣợc gọi là các vector hỗ trợ. Hàm quyết định


αi thỏa mãn C ≥ αi ≥ 0, i = 1 … n
i=1

Bộ phân lớp theo cách này đƣợc gọi là bộ phân lớp máy vector hỗ trợ –
Support Vector Machines.
b. Phân lớp đa lớp với SVM


Trang 24

Trong thực tế có nhiều trƣờng hợp yêu cầu một bộ phân lớp đa lớp, do đó
cần cải tiến SVM cơ bản (phân lớp nhị phân) thành bộ phân lớp đa lớp. Một
trong những phƣơng pháp cải tiến đó là sử dụng thuật toán 1-against-all. Tƣ
tƣởng cơ bản nhƣ sau:
- Giả sử tập dữ liệu mẫu (𝑥1 , 𝑦1 ), … , (𝑥𝑚 , 𝑦𝑚 ) với 𝑥𝑖 là một vector n
chiều. Và 𝑦𝑖 ∈ 𝑌 là nhãn lớp đƣợc gán cho vector 𝑥𝑖 .
- Chia tập 𝑌 thành 𝑚 tập lớp con có cấu trúc nhƣ sau 𝑧𝑖 = 𝑦𝑖 , 𝑌\𝑦𝑖 .
- Áp dụng SVM phân lớp nhị phân cơ bản với 𝑚 tập 𝑧𝑖 để xây dựng siêu
phẳng cho phân lớp này.
- Bộ phân lớp với sự kết hợp của 𝑚 bộ phân lớp trên đƣợc gọi là bộ phân
lớp đa lớp mở rộng với SVM.
c. Tập dữ liệu học không tách tuyến tính
Khi thuật toán SVM cho kết quả đánh giá với chất lƣợng không nhƣ ý
muốn, giả thiết hai lớp dữ liệu tách đƣợc tuyến tính bị vi phạm, cần phải điều
chỉnh thuật toán SVM.
Trong một số trƣờng hợp, sự dụng thuật toán SVM với siêu phẳng lề
mềm. Nếu thuật toán SVM với siêu phẳng lề mềm cũng không hiệu quả, các
phép biến đổi không gian vector đƣợc thực hiện bằng các phép biến đổi chiều
VC thích hợp khác. Một trong những nội dung cốt lõi về các phép biến đổi chiều

cos⁡
(𝑥, 𝑥 ′ )

𝑆𝑐𝑜𝑟𝑒(𝑐|𝑥) =
𝑥′ ∈𝑁𝑐 (𝑥,𝐷,𝑘)

Trong đó 𝑁𝑐 (𝑥, 𝐷, 𝑘) là tập con chỉ chứa chứa các đối tƣợng thuộc lớp c
của tập.
Khi đó tài liệu x sẽ đƣợc phân vào lớp c0 nếu:
𝑆𝑐𝑜𝑟𝑒(𝑐0 |𝑥) = max 𝑠𝑐𝑜𝑟𝑒 𝑐 𝑥
𝑐∈𝐶

2.3. Các thuật toán học bán giám sát
Các thuật toán học có giám sát có đặc điểm là chỉ có thể học từ dữ liệu đã
gán nhãn, việc tạo ra các dữ liệu gán nhãn thƣờng là công việc buồn tẻ, nhƣng
lại tốn công sức. Trong thực tế, các dữ liệu chƣa gán nhãn thƣờng tồn tại với số
lƣợng lớn. Nếu tận dụng đƣợc cả các nguồn dữ liệu chƣa đƣợc gán nhãn thì sẽ
làm giảm đƣợc công sức tạo dữ liệu cũng nhƣ nâng cao chất lƣợng của các bộ
phân lớp. Hiện tại đã có rất nhiều nghiên cứu và đề xuất các giải thuật có khả
năng sử dụng dữ liệu có nhãn, đồng thời tận dụng cả dữ liệu chƣa gán nhãn để
làm phong phú thêm dữ liệu huấn luyện, nhằm làm tăng chất lƣợng phân lớp.
Các giải thuật có đặc điểm này đƣợc phân vào lớp giải thuật học bán giám sát.
[1]
Trong thuật toán học bán giám sát, mẫu không nhãn có tác dụng hỗ trợ để
cung cấp một số tri thức miền toàn diện hơn. Tuy nhiên, mẫu không nhãn cũng
có phạm vi tác dụng của nó. Mẫu không nhãn cũng có thể làm sai lệch tri thức
miền nếu việc lựa chọn chúng không đảm bảo tính đại diện cho miền ứng dụng.


Trang 26

liệu
mẫu
huấn
luyện
là
𝐿 ∪ 𝑈,
với
𝐿 = 𝑥11 , 𝑥12 , 𝑦1 … 𝑥𝑙1 , 𝑥𝑙2 , 𝑦𝑙 ⊂ X × Y là tập mẫu có nhãn và 𝑈 =
1
2
1
2
𝑥𝑙+1
, 𝑥𝑙+1
… 𝑥𝑙+𝑢
, 𝑥𝑙+𝑢
⊂ X là tập không nhãn. Thông thƣờng thì 𝑙 ≪ 𝑢.