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

Nguyễn tuấn trinh
TÌM HI󰗃U PHƯƠNG PHÁP V󰗁 H󰗍C N󰗭A GIÁM SÁT VÀ VI󰗇C PHÂN
LO󰖡I VĂN B󰖣N ÁP D󰗥NG VÀO BÀI TOÁN
LUẬN VĂN THẠC SỸ KỸ THUẬT
HÀNỘI–NĂM2015
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

HÀNỘI-NĂM2015
LỜI CAM ĐOAN
Tôicamđoanđâylàcôngtrìnhnghiêncứucủariêngtôi.
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ác giả luận văn
Nguyễn tuấn trinh
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.
HỌCVIÊN
Nguyễn tuấn trinh
i


MỤC LỤC
LỜI CAM ĐOAN i


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

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.5.2.Ápdụngvàobàitoánphânloại 27

iii


2.5.3.ỨngdụngNaiveBayestrongphânlớpvănbản 30

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.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

















Decisiontree Decisiontree Câyquyếtđịnh
Supportvectormachine

SVM 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


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

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

-Nghiêncứucáctàiliệudothầygiáohướngdẫncungcấp
-Tìm hiểu, nghiêncứu cáctài liệu liênquantrong sách,tạpchí,cácbàibáo
nướcngoài.
-Tìmkiếmcáctàiliệutrênmạnginternet,….
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ả

, | , ( )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làmộttậphợp:
 Kýhiệulà
X
,mỗiphầntửthuộc
X
cóthểđượcgọilàcácdữliệu,cácthể
hiện,cácđốitượnghaycácvídụ.
 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
1 2
( , , , )
n
S s s s
.
 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

Cóbakiểutậpmẫu:
+Tậpmẫuhọchaytậphọc.
+Tậpmẫuhợpthứchoáhaytậphợpthức.
+Tậpmẫuthửhaytậpthử.
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
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


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
( , )
i i
x y
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)
7


 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(class-
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.
( | ) ( )
( | )
( | ) ( )
y
p x y p y
p x y
p x y p y dy



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.
9


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
1 2

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.
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.
1.5.2. Mô hình toán học
Cho
1 2
( , , , )
n
X x x x
làtậphợpgồmnmẫu.
Tagiảthiếtrằngđasốmẫuđượctạoramộtcáchđộclậpvàgiốngnhautừ
mộtphânphốichungtrênXvàmộtsốlượngnhỏmẫuđãđượcgánnhãn.Mụctiêu
làtìmramộtcấutrúcthôngminhtrêntậpdữliệuX.
1.6. Tổng kết chương
Trênđâylàmộtsốkiếnthứccơbảnvềhọcmáy,thôngquađótacóthểnắm
bắtđượccáckiếnthứcnềntảngvềhọcmáynhư:Kháiniệmthếnàolàhọcmáy,
họccógiámsát,họckhônggiámsátvàhọcnửagiámsát;Cácmôhìnhtoáncủa
họcmáy,họccógiámsát,họckhônggiámsát,họcnửagiámsát;Nắmđượccác
bướcgiảimộtbàitoántronghọcmáy.Đâychínhlànhữngkiếnthứccơsởđểtacó
thể tiếp tục tìm hiểu, nghiên cứu các thuật toán về học nửa giám sát trong các


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
2.1.3. Thuật toán kỳ vọng cực đại
2.1.3.1.Giớithiệuthuậttoán
Thuậttoánkỳvọngcựcđại(ExpectationMaximization-EM)làmộtthuật
toántổngquátđánhgiásựcựcđạikhảnăng(ML–MaximumLikelihood)màdữ
liệulàkhônghoànchỉnh(incompletedata)hoặchàmlikelihoodliênquanđếncác
biến ẩn (latent variables) [5]. Ở đây, hai khái niệm “incomplete data” và “latent
variables” có liênquan đếnnhau: Khi tồn tạibiến ẩn, thì dữ liệu làkhông hoàn
chỉnhvìtakhôngthểquansátđượcgiátrịcủabiếnẩn;tươngtựnhưvậykhidữliệu
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.
13


Đầu ra:









Dd
Dd
Dd
t
dcP
D
cP
dndcPW
tdndcP




Với









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
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.