TRNG I HC KHOA HC T NHIÊN
KHOA CÔNG NGH THÔNG TIN

B MÔN H THNG THÔNG TIN SINH VIÊN THC HIN

NGUYN TRN THIÊN THANH - TRN KHI HOÀNG TÌM HIU CÁC HNG TIP CN
BÀI TOÁN PHÂN LOI VN BN VÀ
XÂY DNG PHN MM
PHÂN LOI TIN TC BÁO IN T
KHÓA LUN C NHÂN TIN HC Tp.HCM, 2005
TRNG I HC KHOA HC T NHIÊN
KHOA CÔNG NGH THÔNG TIN

Vit Thành và thy Nguyn Thanh Hùng đã tn ty hng dn, đng viên,
giúp đ chúng em trong sut thi gian thc hin đ tài.
Chúng em xin chân thành cm n quý Thy Cô trong Khoa Công Ngh
Thông Tin truyn đt kin thc quý báu cho chúng em trong nhng nm hc
va qua.
Chúng con xin nói lên lòng bit n đi vi Ông Bà, Cha M luôn là ngun
chm sóc, đng viên trên mi bc
đng hc vn ca chúng con.
Xin chân thành cám n các anh ch và bn bè đã ng h, giúp đ và đng
viên chúng em trong thi gian hc tp và nghiên cu.
Mc dù chúng em đã c gng hoàn thành lun vn trong phm vi và kh
nng cho phép nhng chc chn s không tránh khi nhng thiu sót. Chúng
em kính mong nhn đc s cm thông và tn tình ch bo ca quý Thy Cô
và các bn.

Sinh viên thc hin,
Nguyn Trn Thiên Thanh & Trn Khi Hoàng
07/2005 ii
LI NÓI U
Trong nhng nm gn đây, s phát trin vt bc ca công ngh thông tin đã
làm tng s lng giao dch thông tin trên mng Internet mt cách đáng k đc bit

iii
cách nhanh chóng nh hin nay, phn mm phân loi vn bn t đng ca chúng
em còn có kh nng ng dng cho nhiu loi trang báo đin t ting Vit khác.
Ni dung ca lun vn đc trình bày bao gm 8 chng; trong đó, 3 chng
đu trình bày các hng tip cn cho phân loi vn bn và tách t ting Vit hin
nay; 2 chng tip theo trình bày hng tip cn ca lun v
n đi vi phân loi vn
bn và tách t ting Vit; 3 chng cui trình bày h thng th nghim vn bn,
ng dng vào phân loi tin tc bán t đng, và cui cùng là đánh giá, kt lun quá
trình nghiên cu ca lun vn.
Ü Chng 1. Tng quan: gii thiu s lc v các phng pháp phân loi vn
bn và các hng tip cn cho vic tách t ti
ng Vit; đng thi xác đnh
mc tiêu ca đ tài.
Ü Chng 2. Mt s phng pháp phân loi vn bn: gii thiu tóm tt mt
s phng pháp phân loi vn bn dành cho ting Anh.
Ü Chng 3. Phng pháp tách t ting Vit hin nay: trình bày tóm tt
mt s phng pháp tách t ting Vit hin nay, u đim và hn ch ca các
ph
ng pháp đó.
Ü Chng 4. Phng Tách t Ting Vit không da trên tp ng liu
đánh du (annotated corpus) hay t đin (lexicon) – Mt thách thc:
trình bày phng pháp tách t ting Vit mi ch da vào vic thng kê t
Internet thông qua Google mà không cn bt k t đin hay tp ng liu nào.
Ü Chng 5. Bài toán phân loi tin tc báo đin t: trình bày hng tip c
n
cho bài toán phân loi tin tc báo đin t.


v
MC LC
Chng 1. TNG QUAN 2
1.1. t vn đ 2
1.2. Các phng pháp phân loi vn bn 2
1.3. Tách t Ting Vit – Mt thách thc thú v 3
1.4. Mc tiêu ca lun vn 5
1.4.1. Phn tìm hiu các thut toán phân loi vn bn 5
1.4.2. Phn tách t ting Vit 5
1.4.3. Phn mm phân loi tin tc báo đin t bán t đng 5
1.4.4. óng góp ca lun vn 6
Chng 2. CÁC PHNG PHÁP PHÂN LOI VN BN TING ANH 8
2.1. Bi cnh các phng pháp phân loi vn bn hin nay 8
2.2. Các phng pháp phân loi vn bn ting Anh hin hành 8
2.2.1. Biu din vn bn 8
2.2.2. Support vector Machine(SVM) 10
2.2.3. K–Nearest Neighbor (kNN) 12

4.2. Các nghiên cu v thng kê da trên Internet 40
4.2.1. Gii thiu 40
4.2.2. Mt s công trình nghiên cu v thng kê da trên Internet 41
4.2.3. Nhn xét 43
4.3. Các phng pháp tính đ liên quan gia các t da trên thng kê 43
4.3.1. Thông tin tng h và t-score dùng trong ting Anh 44
4.3.2. Mt s ci tin trong cách tính đ liên quan ng dng trong tách t ting
Hoa và ting Vit 46
4.3.3. Nhn xét v các cách tính đ liên quan khi áp dng cho ting Vit 48
4.4. Tin x lý (Pre-processing) 49
4.4.1. X lý vn bn đu vào 49
4.4.2. Tách ng & tách stopwords 50
4.5. Hng tip cn tách t da trên thng kê t Internet và thut toán di truyn
(Internet and Genetic Algorithm - based ) 51
4.5.1. Công c trích xut thông tin t Google 51
4.5.2. Công c tách t dùng thut toán di truyn (Genetic Algorithm – GA) 53
4.6. Kt lun 61
Chng 5. BÀI TOÁN PHÂN LOI TIN TC IN T 63
5.1. Lý do chn phng pháp Naïve Bayes 63
5.2. Thut toán Naïve Bayes 64
5.2.1. Công thc xác sut đy đ Bayes 64
vii
5.2.2. Tính đc lp có điu kin (Conditional Independence) 65
5.2.3. Ngun gc thut toán Naïve Bayes 65
5.2.4. Phng pháp Naïve Bayes trong phân loi vn bn 66
5.2.5. Hai mô hình s kin trong phân loi vn bn bng phng pháp Naïve
Bayes 68

viii
Chng 7. NG DNG PHÂN LOI TIN TC IN T T NG 99
7.1. Gii thiu tòa son báo đin t 99
7.2. Tính cn thit ca phân loi tin tc t đng 99
7.3. Phân tích hin trng 100
7.3.1. Mô hình DFD quan nim cp 2 hin hành cho ô x lý Nhn bài và Tr bài
100
7.3.2. Phê phán hin trng 103
7.3.3. Mô hình DFD quan nim cp 2 mi cho ô x lý Nhn bài và Tr bài 104
7.4. Trin khai DLL 105
7.5. Chng trình cài đt “Tòa son báo đin t” đã tích hp module phân loi tin
tc 106
7.6. Kt qu 110
Chng 8. TNG KT 112
8.1. Kt qu đt đc 112
8.1.1. V mt lý thuyt 112
8.1.2. V mt thc nghim 113
8.2. Hn ch và hng phát trin 113
8.3. Kt lun 114

ix
DANH SÁCH HÌNH
Hình 2. 1. Biu din vn bn 9
Hình 2. 2. Siêu mt phng h phân chia d liu hun huyn thành 2 lp + và – vi khong
cách biên ln nht. Các đim gn h nht là các vector h tr ,Support Vector (đc
khoanh tròn) 11
Hình 2. 3. Hình Kin trúc mô đun (Modular Architecture) . Các kt qu ca tng mng con

Hình 7. 2. Mô hình DFD ci tin 104
Hình 7. 3. Màn hình ly tin tc cho phép phân loi t đng 106
Hình 7. 4. Màn hình bt đu. Click Next đ bt đu cài đt 107
Hình 7. 5.Màn hình chn ch đ cài đt hoc tháo g chng trình 107
Hình 7. 6.Màn hình chn đng dn đ cài đt chng trình. 108
Hình 7. 7.Màn hình cài đt chng trình 108
Hình 7. 8.Màn hình chn chc nng g chng trình 109
Hình 7. 9.Màn hình g chng trình thành công 109

xi
DANH SÁCH BNG
Bng 3. 1. So sánh gia ting Vit và ting Anh 23
Bng 4. 1. Thng kê đ dài t trong t đin 54
Bng 4. 2. Tham s thc hin GA 56
Bng 6. 1. Mô t mt s control ca màn hình tách t 79
Bng 6.2. Mô t mt s control ca màn hình trích t Google 80
Bng 6.3. Bng mô t mt s control ca màn hình phân loi tin tc đin t 81
Bng 6. 4. Tham s s dng dch v Google 82
Bng 6. 5. Mt s câu truy vn đc bit ca Google 83
Bng 6. 6. Kt qu thc nghim các công thc tính đ tng h MI 87
Bng 6. 7. Bn trng hp ca phân loi vn bn 90
Bng 6. 8. Kt qu phân loi vn bn cho tng ch đ 94
Bng 7. 1. Bng kho d liu nhng bài vit cha đc đng 102
Bng 7. 2. Bng mô t các ô x lý ca mô hình DFD hin hành 103

N
N
G
GQ
Q
U
U
A
A
N
N

t vn đ
Các phng pháp phân loi vn bn
Tách t ting Vit – Mt thách thc thú v
Mc tiêu ca lun vn
Phn tìm hiu các thut toán phân loi vn bn
Phn tách t ting Vit
Phn mm phân loi tin tc báo đin t bán t đng
2
Chng 1. TNG QUAN

based [Shankar and Karypis, 1998]. Các phng pháp trên đu da vào xác sut
3
thng kê hoc thông tin v trng s ca t trong vn bn. Chi tit v ý tng và
công thc tính toán ca mi phng pháp s đc chúng em trình bày  chng 3,
mc 3.3.
Mi phng pháp phân loi vn bn đu có cách tính toán khác nhau, tuy nhiên,
nhìn mt cách tng quan thì các phng pháp đó đu phi thc hin mt s bc
chung nh sau: đu tiên, mi phng pháp s da trên các thông tin v s xut hi
n
ca t trong vn bn (ví d tn s, s vn bn cha t…) đ biu din vn bn thành
dng vector; sau đó, tu tng phng pháp mà ta s áp dng công thc và phng
thc tính toán khác nhau đ thc hin vic phân loi.
i vi ting Anh, các kt qu trong lnh vc này rt kh quan, còn đi vi ting
Vit, các công trình nghiên cu v phân lo
i vn bn gn đây đã có mt s kt qu
ban đu nhng vn còn nhiu hn ch. Nguyên nhân là ngay  bc đu tiên, chúng
ta đã gp khó khn trong vic x lý vn bn đ rút ra tn s xut hin ca t. Trong
khi đó, đ phân loi vn bn thì có th nói bc đu tiên là quan trng nht bi vì
nu  bc tách t đ
ã sai thì vic phân loi hu nh không th thành công đc.
Phn trình bày tip theo s cho chúng ta bit nhng thách thc đt ra trong vic tách
t ting Vit, cng nh nhng ng dng thú v ca nó.
1.3. Tách t Ting Vit – Mt thách thc thú v
i vi ting Anh, “t là mt nhóm các ký t có ngha đc tách bit vi nhau
bi khong trng trong câu” (Webster Dictionary), do vy vic tách t tr nên rt
đn gin. Trong khi đi vi ting Vit, ranh gii t không đc xác đnh mc đnh
là khong trng mà tùy thuc vào ng cnh dùng câu ting Vit. Ví d các t trong

ngày nay, ngôn ng còn tip tc phát trin và thay đi tng ngày. Xét v mt ph
bin, ti
ng Anh là ngôn ng đc dùng rng rãi trong giao dch trên th gii. Do đó
đ to ra mt tp ng liu ting Anh tha các tiêu chí chn mu ng liu là không
quá phc tp. Trong khi đó, Vit Nam ch mi cho phép truy cp Internet trong
vòng chc nm tr li đây, do đó s lng trang web ting Vit là không nhiu. Cho
đn nay, vn cha có mt tp ng liu hun luyn chun nào dành cho vic tách t

và phân loi trang web ting Vit đc công b.
Gn đây, mt phng pháp tách t mi đc gii thiu có u đim là không cn
dùng tp ng liu hay t đin đ ly thông tin thng kê hay trng s ca t, đó là
phng pháp Internet and Genetics Algorithm-based Text Categorization
(IGATEC) ca H. Nguyen et al (2005). im sáng to ca thut toán là kt hp
thut toán di truyn vi vic trích xut thông tin th
ng kê t Internet thông qua mt
công c tìm kim (nh Google chng hn) thay vì ly t tp ng liu nh các
phng pháp trc.
5
Chúng em thc hin bc tách t trong lun vn này da trên ý tng ca thut
toán IGATEC nhng có b sung nhiu ci tin đáng k đ tng đ chính xác đng
thi thc hin các thí nghim chi tit nhm so sánh các cách áp dng thut toán đ
tìm ra cách ti u nht.
1.4. Mc tiêu ca lun vn
1.4.1. Phn tìm hiu các thut toán phân loi vn bn
Trong khuôn kh lun vn này, chúng em tìm hiu  mc c bn mt s phng
pháp phân loi vn bn hin có đang áp dng cho ting Anh và đa ra mt s so
sánh nht đnh gia các phng pháp: Support Vector Machine (Joachims, 1998), k-

, khó đáp ng đc hoàn toàn vic cho phép các sinh viên
lên mng Internet đ xem các tin tc mi hng ngày.  gii quyt phn nào vn đ
trên, chúng ta có th chn lc mt s tin tc t các ngun khác, đng ti trên trang
web ni b ca trng. Trên c s đó, chúng em tích hp phn mm phân loi tin
tc báo đin t t đng vào toà son báo đin t cho phép ly tin t
đng t các
trang web khác. Nh vy, công vic ly tin và phân loi tin tc gi đây đã tr nên
rt d dàng và nhanh chóng, tit kim nhiu công sc và thi gian cho nhà qun tr.
Không ch ng dng cho các trng đi hc, phn mm phân loi tin tc ca
chúng em còn có th ng dng, h tr cho nhiu công vic khác nh : lu tr
(clipping) báo chí, xây dng b ng liu cho các bài toán cn d
liu đc phân
loi, tin đ cho các bài toán khác nh phân loi website.
1.4.4. óng góp ca lun vn
Lun vn đã thc hin vic đc nhiu ci tin ca hng tip cn tách t ting
Vit dùng trong phân loi vn bn theo phng pháp da trên thng kê Internet.
i vi tách t ting Vit, chúng em đ ngh thêm mt công thc tính toán đ
tng h mi, t đó thc hin th nghim tính hiu qu ca cách tính này so vi
cách công thc  nh
ng công trình khác.
Trong quá trình xây dng thut toán di truyn dùng trong tách t, chúng em đã
ci tin hình thc đt bin mi phù hp vi hình thc cu to t trong câu.
i vi vic phân loi vn bn, chúng em ci tin công thc tính trong hng
tip cn Naïve Bayes phù hp vi phng pháp tính da trên thng kê t Google.

H
H




N
N
G
GP
P
H
H
Á
Á
P
PP
P
H
H
Â
Â
N
N

I
I


N
N
G
GA
A
N
N
H
H
Bi cnh các phng pháp phân loi vn bn hin nay
Các phng pháp phân loi vn bn ting Anh hin hành
Biu din vn bn
Support vector Machine (SVM)
K–Nearest Neighbor (kNN)
Naïve Bayes (NB)
Neural Network (NNet)
Linear Least Square Fit (LLSF)

2.2. Các phng pháp phân loi vn bn ting Anh hin hành
2.2.1. Biu din vn bn
Bc đu tiên ca mi phng pháp phân loi là chuyn vic mô t vn bn
dùng chui ký t thành mt dng mô t khác, phù hp vi các thut toán hc theo
mu và phân lp. Hu ht các thut toán đu s dng cách biu din vn bn s
dng vector đc trng, s khác nhau có chng là vic chn không gian đc trng
khác nhau. Vì vy  phn này chúng em s trình bày s lc v
 vector đc trng.
9
Ý tng chính là xem mi vn bn
i
d tng ng là mt vector đc trng
()
12
( ), ( ), , ( )
in
d TFw TFw TFw
iif
trong không gian các t
n
W (
i
w là mt t, mt đc
trng, tng ng mt chiu ca không gian). Gía tr ca
()
i
TF w chính là s ln xut

(w )TFIDF thay cho ()
i
TF w :
( ) log( )
()
i
i
m
IDF w
DF w
=

() (). ()
iii
TFIDF w TF w IDF w
=

Vi
Ü m chính là s vn bn hun luyn
10
Ü DF(w
i
) là s vn bn có cha t
i
w .
Mt vn đ ny sinh khi biu din vn bn theo hng vector đc trng chính là
vic chn đc trng và s chiu cho không gian. Cn phi chn bao nhiêu t và

11
2.2.2.1. Ý tng
Cho trc mt tp hun luyn đc biu din trong không gian vector trong đó
mi tài liu là mt đim, phng pháp này tìm ra mt siêu mt phng
h quyt đnh
tt nht có th chia các đim trên không gian này thành hai lp riêng bit tng ng
lp + và lp –. Cht lng ca siêu mt phng này đc quyt đnh bi khong
cách (gi là biên) ca đim d liu gn nht ca mi lp đn mt phng này.
Khong cách biên càng ln thì mt phng quyt đnh càng tt đng thi vic phân
lo
i càng chính xác. Mc đích thut toán SVM tìm đc khong cách biên ln nht.
Hình sau minh ha cho thut toán này :

Hình 2. 2. Siêu mt phng h phân chia d liu hun huyn thành 2 lp + và –
vi khong cách biên ln nht. Các đim gn h nht là các vector h tr
,Support Vector (đc khoanh tròn)
2.2.2.2. Công thc chính
SVM thc cht là mt bài toán ti u, mc tiêu ca thut toán này là tìm đc
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 loi là
thp nht
Phng trình siêu mt phng cha vector
i
d trong không gian nh sau :
0=+⋅ bwd
i

t

1
±
=
i
y ,
i
y = + 1, vn bn
i
d ∈ lp +;
i
y = - 1, vn bn
i
d ∈ lp - Khi này đ có siêu mt
phng h ta s phi gii bài toán sau :

Tìm Min
w vi w và b thõa điu kiên sau :
(
)
1)(:,1 ≥+⋅∈∀ bwdsignyni
ii

Bài toán SVM có th gii bng k thut s dng toán t Lagrange đ bin đi
thành dng đng thc.
im thú v  SVM là mt phng quyt đnh ch ph thuc vào các vector h tr
(Support Vector) có khong cách đn mt phng quyt đnh là
w
1
. Khi các đim
khác b xóa đi thì thut toán vn cho kt qu ging nh ban đu. Chính đc đim