HUTECH
B GIÁO DC VÀ ÀO TO
TRNG I HC K THUT CÔNG NGH
KHOA CÔNG NGH THÔNG TIN
B MÔN CÔNG NGH PHN MM LUN VN TT NGHIP

TÌM HIU V PHÂN LOI VN BN
VÀ XÂY DNG CHNG TRÌNH NG DNG Sinh viên thc hin:
1. H tên: PHAN THANH BÌNH
MSSV: 10102019
2. H tên: LÊ BCH V
MSSV: 10102218 TP. H CHÍ MINH
NM HC: 2005-2006
HUTECH
B GIÁO DC VÀ ÀO TO
TRNG I HC K THUT CÔNG NGH
KHOA CÔNG NGH THÔNG TIN
B MÔN CÔNG NGH PHN MM


nhu cu phân loi các thông tin đã xut hin t rt sm. Nhng nu dùng con
ngi đ phân loi các thông tin thì s mt rt nhiu công sc và tin bc. Cho
nên ngi ta đã tìm ra nhiu phng pháp phân loi vn bn t đng giúp gim
gánh nng cho con ngi.
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 2

TÓM TT NI DUNG

Trong lun vn này chúng tôi s trình bày v các phng pháp phân loi vn
bn và hin thc gii thut K-Nearest Neightbour (K-NN). ây là gii thut
không quá phc tp nhng có đ chính xác khá cao.
Các phn trong lun vn s đc trình bày nh sau:
Chng 1: Chng này s trình bày v nhu cu thc tin ca vic phân loi
vn bn và các ng dng thc t ca các ph ng pháp phân loi vn bn t
đng. Chng này s cho ta thy s cn thit ca vic phân loi vn bn t
đng trong thi đi ngày nay.
Chng 2: Chng này trình bày v các c s lý thuyt liên quan đn quá trình
phân loi vn bn t đng. Cung cp các kin thc rt quan trng dùng đ cài
đt và kim tra hiu qu ca các phng pháp phân loi t đng.
Chng 3: Chng này trình bày tng quan mt s phng pháp phân loi vn
bn t đng nh: Gii thut Rocchio, Gii thut K-Nearest Neighbour, Naïve
Bayes, Gii thut cây quyt đnh, Gii thut mng neuron, Gii thut Support
Vector Machine.
Chng 4: Chng này s trình bày bng thit k và cài đt chng trình phân
loi vn bn t đng theo phng pháp K-Nearest Neighbour. Sau đó chúng tôi
s trình bày các kt qu đt đc sau khi chy th nghim chng trình nh đ
chính xác, tc đ ca chng trình.  minh ha cho vic ng dng phng

DANH MC HÌNH 9
DANH MC BNG 11
Chng 1 12
PHÁT BIU VN  12
1.1. Gii thiu 12
1.1.1. ng c thúc đy vic phân loi vn bn t đng
13
1.1.2. Mt s ng dng ca vic phân loi vn bn theo ch đ
14
1.2. Ni dung đ tài
15
1.3. ng dng m rng - Lp ch mc và tìm kim ca Lucene
16
1.3.1. Gii thiu Lucene
16
1.3.2. C s nn tng ca Lucene
18
1.3.3. Mc đích, chc nng, công dng
18
1.3.4. To ch mc và tìm kim
19
Chng 2 20
C S LÝ THUYT PHN LOI VN BN 20
2.1. Biu din vn bn 20
2.1.1. Phng pháp Boolean
23
2.1.2. Phng pháp tn sut t (work frequency)
24
2.1.3. Phng pháp tf-idf (frequency x inverse document frequency)
24

2.4. ánh giá đ chính ca vic phân loi vn bn
34
2.4.1. Thông s precision.
35
2.4.2. Thông s recall
35
2.4.3. Thông s f (f-score)
35
2.4.4. Thông s accuracy
36
2.4.5. Thông s error
36
Chng 3 37
CÁC GII THUT PHÂN LOI VN BN 37
3.1. Gii thut Rocchio 37
3.1.1. Gii thiu
37
3.1.2. Giai đon hun luyn
38
3.1.3. Giai đon phân loi
39
3.1.4. ánh giá gii thut
40
3.2. Gii thut K-Nearest Neighbour
41
3.2.1. Gii thiu
41
3.2.2. Giai đon hun luyn
42
3.2.3. Giai đon phân loi

3.5.2. ánh giá gii thut
53
3.6. Gii thut Support Vector Machine
54
3.6.1. Các mt phân cách (Hyperplanes)
54
3.6.2. Gii thut Support Vector Machine.
55
3.6.3. Nhân xét.
56
3.7. Chn gii thut
57
Chng 4 58
THIT K VÀ HIN THC CHNG TRÌNH PHÂN LOI VN BN 58
4.1. Quá trình xây dng gii thut K-Nearest Neighbour 58
4.1.1. Xây dng t đin (danh sách t khóa)
58
4.1.2. Giai đon hun luyn
58
4.1.3. Giai đon phân loi
59
4.2. S đ usecase
60
4.3. S đ tun t ca vài nghip v chính
61
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 7
4.3.1. Hun luyn vn bn 61

4.6. Thit k giao din
76
4.6.1. Màn hình chính ca chng trình
76
4.6.2. Màn hình to loi vn bn
76
4.6.3. Màn hình hun luyn chng trình
77
4.6.4. Màn hình phân loi d liu
77
4.6.5. Màn hình kt qu phân loi
78
4.6.6. Màn hình to ch mc (reverted index)
78
4.6.7. Màn hình trích rút d liu trên mng
79
4.6.8. Trang ch tìm kim theo ch đ
79
4.6.9. Trang tìm kim theo ch đ
80
4.7. Kt qu đt đc
80
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 8
Chng 5 83
ÁNH GIÁ VÀ HNG PHÁT TRIN 83
5.1. ánh giá 83
5.1.1. Kt qu đt đc

Hình 15. S đ use case mô t các nghip v ch ng dng 60
Hình 16. S đ tun t ca quá trình hun luyn chng trình 61
Hình 17. S đ tun t ca quá trình phân loi vn bn 62
Hình 18. S đ tun t ca quá trình đánh giá kt qu phân loi 64
Hình 19. S đ tun t ca quá trình đánh giá kt qu phân loi 65
Hình 20. S đ tun t ca quá trình lp ch mc 66
Hình 21. S đ tun t ca quá trình tìm kim 67
Hình 22. Package reader 68
Hình 23. Pakage analysis 69
Hình 24. Pakage training 70
Hình 25. Pakage category 72
Hình 26. Package store 72
Hình 27. Package crawler 73
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 10
Hình 28. Package index 74
Hình 29. Package util 75
Hình 30. C s d liu 75

HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 11
DANH MC BNG
Bng 1. Ví d mt t đin 21
Bng 2. Các version ca tuyn tp Reuter. 31
Bng 3 . Thng kê mt s ch đ trong tp Reuters 33
Bng 4. Thng kê mt s ch đ trong tp 20-newsgroup 34

 Sinh ra ngôn ng t nhiên (Natural Language Generation)
 Máy dch thut (Machine Translation)
 Tr li câu hi (Question Answering)
 Tìm kim thông tin (Information Retrieval)
 Trích rút thông tin (Information Extraction)
 Kim chng vn bn (Text-Proofing)
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 13
 Tóm tc t đng (Automatic Summarization)
 M h v ng ngha (Syntactic ambiguity)
 X lý ngôn ng bng thng kê (Statistical Natural Language Processing)
Trong lun vn này chúng tôi trình bày là phân loi vn bn t đng - mt
hng nghiên cu trong lnh vc x lý ngôn ng t nhiên bng thng kê. Mc
tiêu ca vic phân loi vn bn t đng là phi vit mt chng trình có kh
nng phân loi chính xác mt vn bn bt k (bng ting Anh).
1.1.1. ng c thúc đy vic phân loi vn bn t đng
Phân loi vn bn t đng đem li rt nhiu li ích trong đi sng hin nay.
Tht vy, s phát trin vt bc ca Internet dn đn s bùng n ca các vn
bn trc tuyn, cho nên cn phi phân loi các vn bn nhn đc vào các ch
đ khác nhau.
Nu vic phân loi vn bn c đin đc thc hin th công, ngha là thông
qua con ngi (các chuyên gia ca tng lnh vc), thì s lng chuyên gia
tham gia vào vic phân loi là rt ln và thi gian phân loi cng ln hn, điu
này rt tn kém và gây nhàm chán cho các chuyên gia này. Tuy nhiên vic
phân loi th công cng không tránh khi nhng ý kin ch quan ca nhng
chuyên gia, vì vy đ chính xác cng không cao.
Khi đó các công c ph ân loi vn bn t đng rt hu ích cho ngi đc trong
vic t chc d liu. Do đó vic phân loi tin hành bng máy có u đim là

Vic phân loi vn bn có th áp dng trong các h thng tìm kim thông tin
nhm tng hiu sut cng nh tng đ chính xác ca vic tìm kim. Do s phát
trin ca Internet, s lng thông tin trc tuyn ngày càng tng. Mt thao tác
ph bin trên Internet là tìm kim. Tuy nhiên, do khi lng thông tin rt ln
nên các c máy tìm kim (search engine) thng t chc d liu vào các ch đ
giúp không gian tìm kim gim đi, qua đó tng hiu sut ca h thng.
Ngoài ra vic tìm kim theo t khoá thng không đt đc đ chính xác cao
nên các search engine thng kt hp vi tìm kim theo ch đ nhm ci thin
đ chính xác ca vic tìm kim.
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 15
d. Phân loi email
Chc nng ca mt h thng phân loi email t đng là:
- T chi mail theo lut.
- Phân phi mail vào các folder đnh trc.
- Chuyn mail đn đa ch khác.
1.2. Ni dung đ tài

Trong lun vn chúng tôi tìm hiu và áp dng phng pháp k – Nearest
Neighbour đ phân loi vn bn ting Anh. i vi ngôn ng ting Anh hin
nay có rt nhiu công trình liên quan nh: Google, Yahoo, …
Các vn bn cn phân loi trong lun vn chúng tôi gói gn trong 5 ch đ: Trí
tu nhân to (artificial intelligence), Cu trúc d liu + gii thut (structure and
algorithm), mng máy tính (network), sinh hc (biology), bóng đá (football).
Các ch đ trên đc thu thp t các trang web đc Google phân loi sn do
đó mi th loi rt đa dng v ni dung. Trong đó hai ch đ cu trúc d liu +
gii thut và trí tu nhân to đc xem là tiêu biu nht cho vic phân loi vì
chúng giao nhau rt ln, thêm vào đó là ch đ mng máy tính cng rt gn vì

tìm kim đy đ chc nng cho website ca mình.
Ta có th xem Lucene là mt tng phía di, giúp x lí thao tác index và search
cho các chng trình bên trên, nh trong hình sau:
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 17

Hình 1. Mô hình kin trúc ca Lucene
Mt s chng trình tìm kim có đy đ chc nng đc xây dng da trên c
s Lucene. Nu bn đang tìm mt s th cn thit đã đc xây dng sn hay
mt khung làm vic dùng cho vic crawling, x lí vn bn, và tìm kim, bn có
th xem ti trang Lucene Wiki (http://wiki.apache.org/jakarta-
lucene/PoweredBy) vi nhiu chng trình: Zilverline, SearchBlox, Nutch,
LARM, và jSearch.
Vi s phong phú ca thông tin, và thi gian là mt trong nhng th quý giá
ca hu ht mi ngi, chúng ta cn làm cho nhng câu truy vn tr nên linh
hot, đc lp, đc bit đ nhanh chóng ct ngang rào cn phân loi cng nhc
và tìm kim chính xác sau đó đa ra kt qu hp lý nht theo yêu cu.

HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 18
1.3.2. C s nn tng ca Lucene
Lucene là sn phm sáng to ca Doug Cutting và sn có trên SourceForge,
cho phép mi ngi download. Nó gia nhp dòng sn phm phn mm Apache
Software Foundation's Jakarta mã ngun m bng Java vào tháng 9 nm 2001.
T khi đc ph bin rng rãi, Lucene ngày càng đc nhiu ngi dùng và
các nhà phát trin ng h. Tháng 11 nm 2002, phiên bn Lucene 1.2 đc phát

bn có th to index cho các vn bn, hay phiên bn ca vn bn nhm
d dàng trong vic phc hi.
Tt nhiên, nhiu công c tìm kim có th thc hin hu ht các chc nng trên,
nhng ít có công c tìm kim mã ngun m nào li d dùng và linh hot nh
Lucene.
1.3.4. To ch mc và tìm kim

Trc tiên, bn cn đ d liu vào ng dng tìm kim ca mình (indexing) hay
ly d liu ra (searching).
- To ch mc (Indexing) bng các to các đi tng Documents vi nhng
Fields ca nó (là mt cp tên/giá tr) và đ nó vào mt IndexWriter đ phân
tích ni dung ca các Field values thành các token và to ra index.
- Tìm kim (Searching) dùng mt đi tng IndexSearcher. Trc ht, ly
câu truy vn (kiu String) t ngi dùng, truyn nó cho QueryParser (và nh là
QueryParser cn phi đc khi to trc đó, có cùng loi Analyzer khi bn
xây dng index; QueryParser s dùng Analyzer đ phân tích chui truyn vào)
và tr v mt đi tng Query. Sau đó, ly đi tng Query này dùng cho
phng thc IndexSearcher.search(). Nó s tr v đi tng Hits, là mt tp
hp các đi tng Document đc tìm thy. i tng Hits cng cha c score
cho mi Document.
HUTECH
Lun vn tt nghip GVHD: Th.s Nguyn Chánh Thành

SVTH: Phan Thanh Bình & Lê Bch V Trang 20
Chng 2
C S LÝ THUYT PHN LOI VN BN
2.1. Biu din vn bn

Hu ht các vn bn đu chuyn đi mt hay nhiu chui gm các t sang mt
dng thích hp đ có th đc x lý bi gii thut. Các vn bn đc coi là mt

bn.
Mt khi t đin đc to ra nhng vector t đin riêng l đc phát sinh.
Mô hình không gian vector biu din nhng vn bn nh nhng vector trng s
trong không gian n chiu to thành mô hình biu din d liu ca chúng ta.
Phng pháp này cn x lý trc mt lng d liu tng đi nh đ làm tin
ích khi chúng ta x lý mt khi lng d liu khng l.
Trong mô hình này mt vn bn đ c biu din bng mt vector các t vi s
chiu t là tng s t khác nhau ca t đin.

Mi t (term) th i trong mt vn bn d hoc trong câu truy vn th j có mt
giá tr trng s là w
ij

Ví d:
Biu din mt tp hp gm ba vn bn D1, D2, Q vi s chiu t = 3 ngha là
trong t đin có 3 t là T1, T2, T3.
Vn bn D1 cha 2 t T1, 3 t T2 và 5 t T3 => D1 = 2T1 + 3T2 + 5T3
Vn bn D2 cha 3 t T1, 7 t T2 và 1 t T3 => D2 = 3T1 + 7T2 + T3
là s thc.
Nh vy mt vn bn hoc câu truy vn đc biu din di dng:
S chiu = t = | tng s t vng |
d
j
= (w
1j
, w
2j
, …, w
tj
)


tn2n1nn
t222122
t112111
t21
w… w wD
… … … … …
w… w wD
w… w wD
T … T T

T
3

T
1

T
2

D
1
= 2T
1
+ 3T
2
+ 5T
3
D
2

ch đ ca vn bn càng ln.
Nu mt t xut hin trong hu ht các vn bn, mà các vn bn đó đu thuc
các ch đ khác nhau, thì t đó không có ý ngha đi vi bt k mt ch đ
nào.
Gi
f
ij
là s ln xut hin ca t i trong vn bn j.
N là tng s các vn bn.
t là tng s t khác nhau trong t đin.
df
i
là tng s vn bn cha t i.
Có nhiu phng pháp đ xác đnh giá tr ca trng s w
ij
2.1.1. Phng pháp Boolean

. Sau đây là mt vài
phng pháp ph bin.
Mt vn bn đc biu din mi mt tp hp các t khóa. Các câu truy vn
da trên phng pháp Boolean là các biu thc Boolean gm các t khóa đc
lien kt vi nhau bi các toán t AND, OR, NOT và các du ngoc đ ch
phm vi. Ví d nh:
[[Rio & Brazil] | [Hilo & Hawaii]] & hotel & !Hilton]
D liu kt xut là các vn bn có liên quan hoc không liên quan và không có
sp xp.
ây là phng pháp đc s dng ph bin vì nó đn gin, d truy vn, hình
thc rõ ràng. Giá tr w
ij
ch bng 1 hoc 0, ngha là t i có hoc không xut