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


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


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

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

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

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

learning
Semi-supervised
learning
Họcnửagiámsát
NaiveBayes NaiveBayes Bayesngâythơ
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


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

1


MỞ ĐẦU
1. Lý do chọn đề tài

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

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

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.
Cóthểsửdụngcácphươngphápsau:
+Phươngphápphânđoạn.
+Phươngphápđolườngentropy.
+Nếudữliệutuântheomộtluậtphânphốinàođó,vídụphânphốGauss,
phânphốđều,…thìtacóthểrờirạcthànhcáckhoảngphânphốitươngứng.
1.2.5. Tập mẫu
Tậpmẫulàtậphữuhạncácvídụ.
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

i
.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ố,
[ ]
( )
T
i i n
y y


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.

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

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

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

(**);)|(
||
1
)(
),()|(||
),()|(1
,0

 








Dd
Dd
Dd
t
dcP
D
cP
dndcPW
tdndcP





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