ĐẠ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

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

MỤC LỤC
LỜI CẢM ƠN ........................................................................................................8
DANH MỤC CHỮ VIẾT TẮT .............................................................................9
DANH MỤC HÌNH VẼ, BẢNG BIỂU...............................................................10
MỞ ĐẦU..............................................................................................................12
CHƯƠ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ướng tiếp cận và các kỹ thuật trong khai phá dữ liệu .................16
1.1.3 Ứ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
1.4.1 Giới thiệu bài toán................................................................................26
1.4.2 Tại sao đặt ra bài toán phân cụm tài liệu Web.....................................27

-3-


Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-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

2.2.3 Các phương pháp tách từ tiếng Việt.....................................................42
2.2.3.1 fnTBL (Fast Transformation-based learning)................................... 42
2.2.3.2 Longest matching.............................................................................. 49
2.2.3.3 Kết hợp giữa fnTBL và Longest matching.......................................49
2.3.1 Đo độ tương tự .....................................................................................49
2.3.1.1 Độ tương tự trùng lặp........................................................................ 49
2.3.1.2 Độ tương tự Cosine........................................................................... 50
2.4 Tổng kết chương 2 ..................................................................................53
CHƯƠ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ường Đại học Công nghệ-2007

3.3.2 Độ đo tươ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
3.3.3. 2 Giải thuật phân cụm K-Means mở rộng .......................................... 61
3.3.4 Đánh giá ...............................................................................................62
3.4 Phân hoạch Bottom-up ...............................................................................63
3.4.1 Thuật toán phân cụm tích tụ (AHC).....................................................63
3.4.2 Độ phức tạp tính toán ...........................................................................66

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 đề

World Wide Web (WWW) là một kho chứa lớn nhất và được biết đến
rộng rãi nhất của các siêu văn bản. Các tài liệu siêu văn bản chứa đựng văn bản
và thường nhúng các liên kết đến các tài liệu khác phân bố trên Web. Ngày nay,
Web bao gồm hàng tỷ tài liệu của hàng triệu tác giả được tạo ra , và được phân
tán qua hàng triệu máy tính được kết nối qua đường dây điện thoại, cáp quang,
sóng radio…. Web đang ngày càng được sử dụng phổ biến trong nhiều lĩnh vực
như báo chí, phát thanh, truyền hình, hệ thống bưu điện, trường học, các tổ chức
thươ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 trả lại một danh sách các tài liệu được phân hạng mà
ngườ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ó được
những tài liệu phù hợp. Ngoài ra các thông tin đó thường rất phong phú, đa dạng
và liên quan đến nhiều đối tượng khác nhau. Điều này tạo nên một sự nhập
nhằng gây khó khăn cho người sử dụng trong việc lấy được thông tin cần thiết.
Có nhiều hướng tiếp cận khác nhau để giải quyết vấn đề này. Các hướng
này thường chú ý giảm sự nhập nhằng bằng các phương pháp lọc hay thêm các
tùy chọn để cắt bớt thông tin. Trong khuôn khổ của luận văn chỉ tập trung vào
hướng biểu diễn các thông tin trả về bởi các máy tìm kiếm thành từng cụm để
cho người dùng có thể dễ dàng tìm được thông tin mà họ cần. Đã có nhiều thuật
toán phân cụm tài liệu dựa trên phân cụm ngoại tuyến toàn bộ tập tài liệu. Tuy

- 12 -


Đặ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 được ứng dụng trên các tập tài

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

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ước đầu nhưng
hứa hẹn sự phát triển và ứng dụng trong tương lai.
Luận văn được tổ chức thành 5 phần:

- 13 -


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

Chương 1: Trong chương này giới thiệu tổng quan về khai phá dữ liệu,
lĩnh vực khai phá dữ liệu Web, tổng quan về bài toán phân cụm tài liệu nói
chung, phân cụm tài liệu Web nói riêng, những yêu cầu đối với bài toán phân
cụm tài liệu Web. Các đại lượng dùng để đo độ chính xác cho bài toán.
Chương 2: Trình bày các phương pháp biểu diễn tài liệu. Những khó
khăn trong phân cụm Tiếng Việt và các phương pháp tách từ tiếng Việt, các cách
đo độ tương tự giữa các tài liệu.
Chương 3: Trình bày các thuật toán dùng để phân cụm tài liệu Web nói
chung. Trong chương này trình bày theo hai hướng tiếp cận. Thuật toán AHC
(Agglomerative Hierarchical Clustering) tiêu biểu cho hướng phân cụm bottomup. Thuật toán K-means tiêu biểu cho hướng phân cụm top-down. Và sự kết hợp
giữa hai hướ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ương lai.

- 14 -



Đặ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


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


Đặ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

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 -