TR

I H C QU C GIA HÀ N I
NG
I H C CÔNG NGH

ng Quang Huy

PH

NG PHÁP THU TH P, ÁNH GIÁ VÀ PHÂN C M
THÔNG TIN TI NG VI T TRÊN INTERNET

LU N V N TH C S

Hà N i – 2007


TR

I H C QU C GIA HÀ N I
NG
I H C CÔNG NGH

ng Quang Huy

PH

NG PHÁP THU TH P, ÁNH GIÁ VÀ PHÂN C M
THÔNG TIN TI NG VI T TRÊN INTERNET



U..............................................................................................................12
NG 1: T NG QUAN V KHAI PHÁ D

LI U VÀ BÀI TOÁN PHÂN

C M TÀI LI U WEB .........................................................................................15
1.1 Khai phá d li u..........................................................................................15
1.1.1 Khai phá d li u là gì? .........................................................................15
1.1.2 Các h
1.1.3

ng ti p c n và các k thu t trong khai phá d li u .................16

ng d ng c a khai phá d li u ............................................................17

1.2 D li u Fulltext và Hypertext.....................................................................18
1.2.1 Fulltext .................................................................................................18
1.2.2 Hypertext..............................................................................................18
1.3 Khai phá d li u Web .................................................................................21
1.3.1 Nhu c u ................................................................................................21
1.3.2

c đi m ..............................................................................................22

1.3.3 Các h

ng ti p c n...............................................................................24

1.4 Bài toán phân c m tài li u Web .................................................................26

NG 2: CÁC PH

NG PHÁP BI U DI N TÀI LI U ...........................34

2.1 Mô hình không gian vector.........................................................................34
2.1.1 M t s khái ni m..................................................................................34
2.1.1.1 T khóa (keywords).......................................................................... 34
2.1.1.2 T d ng (stopwords)......................................................................... 35
2.1.1.3 C t b t (word stemming) ............................................................... 36
2.1.2 Mô hình t n s ......................................................................................37
2.1.3 Mô hình Boolean..................................................................................39
2.1.4 Tính ch t c a vector .............................................................................40
2.1.4.1 Tích trong..........................................................................................40
2.1.4.2

l n vector .................................................................................... 41

2.2 Tách t trong ti ng Vi t..............................................................................41

-4-


ng Quang Huy-Lu n v n cao h c-Tr

ng

i h c Công ngh -2007

2.2.1 M t s đ c đi m chính v t ti ng Vi t ...............................................41
2.2.1.1 Ti ng ................................................................................................. 41

NG 3: CÁC THU T TOÁN PHÂN C M TÀI LI U ............................54

3.1 Gi i thi u ....................................................................................................54
3.2 Phân ho ch Top-down ................................................................................55
3.2.1 Thu t toán K-means v i gán “c ng”....................................................55
3.2.2 Thu t toán K-means v i gán “m m” ...................................................57
3.2.3

ph c t p tính toán ...........................................................................58

3.3 Phân c m d a trên tính m i c a tài li u.....................................................58
3.3.1 Mô t .....................................................................................................58

-5-


ng Quang Huy-Lu n v n cao h c-Tr

3.3.2

đo t

ng

i h c Công ngh -2007

ng t .....................................................................................59

3.3.3 Thu t toán phân c m d a trên thu t toán K-Means m r ng ..............60
3.3. 3.1 Ch m c phân c m ........................................................................... 60


-6-


ng Quang Huy-Lu n v n cao h c-Tr

CH

NG 5: T NG K T VÀ H

ng

i h c Công ngh -2007

NG PHÁT TRI N ....................................84

5.1 T ng k t ......................................................................................................84
5.2 H

ng phát tri n.........................................................................................85

TÀI LI U THAM KHÁO....................................................................................86

-7-


ng Quang Huy-Lu n v n cao h c-Tr

ng


th

c phân

ng h c, các t ch c

ng m i, chính ph …. Chính vì v y l nh v c Web Mining hay tìm ki m t

đ ng các thông tin phù h p và có giá tr trên Web là m t ch đ quan tr ng trong
Data Mining.
Các h th ng tìm ki m thông tin hay nói ng n g n là các máy tìm ki m
trên Web thông th
ng

ng tr l i m t danh sách các tài li u đ

c phân h ng mà

i dùng s ph i t n công ch n l c trong m t danh sách r t dài đ có đ

nh ng tài li u phù h p. Ngoài ra các thông tin đó th
và liên quan đ n nhi u đ i t
nh ng gây khó kh n cho ng
Có nhi u h
này th

ng khác nhau.

c




ng Quang Huy-Lu n v n cao h c-Tr

ng

i h c Công ngh -2007

nhiên t p h p tài li u c a các máy tìm ki m là quá l n và luôn thay đ i đ có th
phân c m ngo i tuy n. Do đó vi c phân c m ph i đ
li u nh h n đ

c ng d ng trên các t p tài

c tr v t các truy v n. Và thay vì tr v m t danh sách r t dài

các thông tin gây nh p nh ng cho ng

i s d ng c n có m t ph

ng pháp t

ch c l i các k t qu tìm ki m m t cách h p lý.
M c đích nghiên c u
a ra yêu c u c a bài toán phân c m tài li u Web. Nh n m nh đ n k
thu t phân c m K-Means m r ng, s d ng tính m i c a tài li u, đây là m t
thu t toán phân c m t ng, th i gian tuy n tính đáp ng đ

c các yêu c u c a bài



Gi i h n nghiên c u
Do h n ch v m t th i gian nên vi c nghiên c u, tìm hi u m i ch thu
đ

c nh ng ki n th c c b n v k thu t và nh ng th nghi m b

h a h n s phát tri n và ng d ng trong t
Lu n v n đ

ng lai.

c t ch c thành 5 ph n:

- 13 -

c đ u nh ng


ng Quang Huy-Lu n v n cao h c-Tr

Ch

ng 1: Trong ch

ng

i h c Công ngh -2007

ng này gi i thi u t ng quan v khai phá d li u,

gi a hai h

ng phân c m bottom-

ng phân c m top-down. Và s k t h p

ng đó – Buckshot.

Trình bày thu t toán K-Means m r ng cho bài toán phân c m tài li u
Web d a trên tính m i c a tài li u.
Ch

ng 4: K t qu th c nghi m

Ch

ng 5: T ng k t và h

ng phát tri n trong t

- 14 -

ng lai.


ng Quang Huy-Lu n v n cao h c-Tr

ng

i h c Công ngh -2007

ng

i h c Công ngh -2007

[10]. R. Krishnapuram, A. Joshi, L. Yi (1999), A Fuzzy Relative of the k-Medoids
Algorithm with Application to Web Document and Snippet Clustering, Proc.
IEEE Intl. Conf. Fuzzy Systems, Korea.
[11]. Z. Jiang, A. Joshi, R. Krishnapuram, L. Yi (2000), Retriever: Improving
Web Search Engine Results Using Clustering, Technical Report, CSEE
Department, UMBC.
[12]. T. H. Haveliwala, A. Gionis, P. Indyk (2000), Scalable Techniques for
Clustering the Web, Extended Abstract, WebDB’2000, Third International
Workshop on the Web and Databases, In conjunction with ACM
SIGMOD’2000, Dallas, TX.
[13]. A. Bouguettaya (1996), On-Line Clustering, IEEE Trans. on Knowledge
and Data Engineering.
[14]. A. K. Jain và R. C. Dubes (1988), Algorithms for Clustering Data, John
Wiley & Sons.
[15]. G. Karypis, E. Han, V. Kumar (1999), CHAMELEON: A Hierarchical
Clustering Algorithm Using Dynamic Modeling, IEEE Computer 32.
[16]. O. Zamir và O. Etzioni (1999), Grouper: A Dynamic Clustering Interface to
Web Search Results, Proc. of the 8th International World Wide Web
Conference, Toronto, Canada.
[17]. D. R. Cutting, D. R. Karger, J. O. Pedersen, J.W. Tukey (1993),
Scatter/Gather: A Clusterbased Approach to Browsing Large Document
Collections, In Proceedings of the 16th International ACM SIGIR
Conference on Research and Development in Information Retrieval.

- 87 -



- 88 -


ng Quang Huy-Lu n v n cao h c-Tr

ng

i h c Công ngh -2007

[26]. Wai-chiu Wong và Ada Fu (2000), Incremental Document Clustering for
Web Page Classification, IEEE 2000 Int, Conf. on Infor, Society in the 21st
century: emerging technologies anf new challenges (IS2000), Nh t B n.
[27]. Pierre Baldi, Paolo Frasconi, Padhraic Smyth (2003). Modeling the Internet
and the Web: Probabilistic Methods and Algorithms. Wiley, 2003.
[28]. Sen Slattery (2002). Hypertext Classification. PhD Thesis (CMU-CS-02142). School of Computer Science. Carnegie Mellon University, 2002.

- 89 -