ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜ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


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜ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

Ngành: Công nghệ thông tin.
Mã số: 1.01.10

LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS ĐOÀN SƠN

Hà Nội - 2007


1.4.3 Đặc điểm của bài toán phân cụm tài liệu Web.....................................28
1.4.4 Các yêu cầu đối vơi bài toán phân cụm tài liệu Web...........................30
1.4.5 Một số đại lượng đo độ chính xác cho bài toán ...................................31
1.5 Những khó khăn trong Phân cụm tiếng Việt ..............................................32
1.5.1 Vấn đề tách từ tiếng Việt.....................................................................32
1.5.2 Vấn đề bảng mã tiếng Việt...................................................................33
1.5.3 Các khó khăn khác ...............................................................................33
1.6 Kết luận chương 1 ...................................................................................33
CHƯƠ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
2.2.1.2 Từ ...................................................................................................... 42
2.2.2 Tách từ tự động tiếng Việt ...................................................................42

3.5 Kết hợp giữa bottom-up và top-down ........................................................67
3.5.1 Mô tả.....................................................................................................67
3.5.2 Thuật toán buckshot .............................................................................67
3.6 Nhận xét......................................................................................................70
3.7 Tổng kết chương 3......................................................................................72
CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM VỚI PHÂN CỤM TIẾNG VIỆT ...73
4.1 Môi trường thực nghiệm.............................................................................73
4.2 Dữ liệu ........................................................................................................73
4.3 Kết quả thực nghiệm...................................................................................75
4.3.1 So sánh các thuật toán phân cụm .........................................................76
4.3.2 Phân cụm sử dụng tách từ tiếng Việt ...................................................80
4.4 Kết luận chương 4.......................................................................................82

-6-


Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007

CHƯƠNG 5: TỔNG KẾT VÀ HƯỚ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 Đại học Công nghệ-2007

MỞ ĐẦU
Đặt vấn đề

liệu nhỏ hơn đượ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
toán phân cụm tài liệu Web. K-Means mở rộng không coi một tài liệu như tập
hợp các từ mà là một xâu sử dụng quan hệ thông tin giữa các từ.
Nội dung thực hiện


Tìm hiểu các yêu cầu của bài toán phân cụm tài liệu Web.



Trình bày một số phương pháp biểu diễn tài liệu.



Trình bày một số phương pháp phân cụm tài liệu Web.



Một số kết quả thực nghiệm bước đầu.



Đề xuất hướng phát triển.
Giới hạn nghiên cứu

Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007

TÀI LIỆU THAM KHÁO
Tiếng Việt
[1].

Đinh Điền, Xử lý ngôn ngữ tự nhiên, NXB Giáo Dục.

Tiếng Anh
[2]. Sophoin, Yoshiharu Ishikawa và Hiroyuki Kitagawa (2006), Incremental
Clustering Based on Novelty of Online Documents
[3]. Clement T.Yu và Weiyi Meng (1998), Principles of Database Query
Processing for Advanced Application, Morgan Kaufmann Publisher, Inc.
[4]. Gerard Salton/Michael J.McGill, Introduction to Modern Information
Retrieval.
[5]. Jiawei Han (2000), Data Mining: Concepts and Techiniques
[6]. M. Steinbach, G. Karypis, V. Kumar (2000), A Comparison of Document
Clustering Techniques, TextMining Workshop, KDD.
[7]. O. Zamir and O. Etzioni (1998), Web Document Clustering: A Feasibility
Demonstration, Proc. of the 21st ACM SIGIR Conference, 46-54.
[8]. O. Zamir, O. Etzioni, O Madani, R. M. Karp (1997), Fast and Intuitive
Clustering of Web Documents, Proc. of the 3rd International Conference on
Knowledge Discovery and Data Mining.
[9]. K. Cios, W. Pedrycs, R. Swiniarski (1998), Data Mining – Methods for
Knowledge Discovery, Kluwer Academic Publishers.

- 86 -


Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007

[18]. R. Michalski, I. Bratko, M. Kubat (1998), Machine Learning and Data
Mining – Methods and Applications, John Wiley & Sons Ltd..
[19]. J. Jang, C. Sun, E. Mizutani (1997), Neuro-Fuzzy and Soft Computing – A
Computational Approach to Learning and Machine Intelligence, Prentice
Hall.
[20]. G. Biswas, J.B. Weinberg, D. Fisher (1998), ITERATE: A Conceptual
Clustering Algorithm for Data Mining, IEEE Transactions on Systems, Man
and Cybernetics.
[21]. Z. Huang (1997), A Fast Clustering Algorithm to Cluster Very Large
Categorical Data Sets in Data Mining, Workshop on Research Issues on
Data Mining and Knowledge Discovery.

[22]. Y. Yang và J. Pedersen (1997), A Comparative Study on Feature Selection
in Text Categorization, In Proc. of the 14th International Conference on
Machine Learning.
[23]. A Guttman (1984). R-tree: A dynamic index structure for spatial searching,
In Proceedings of ACM SIGMOD.
[24]. Bjornal Larsen và Chinatsu Aone (1999). Fast and effective text mining
using lineartime document clustering, In Proceedings of the ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, San
Diego, CA, USA.
[25]. C.J.van Rijbergen(1979), Information Retrieval, Butterworth & Co
(Publishers) LTd.

- 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