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

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

HTML: Ngôn ng
ữ siêu liên kết (HyperText Markup Language)
IR: Mô hình tìm kiếm thông tin (Information Retrieval)
IDF: Tần suất nghịch đảo tài liệu (inverse document frequency)
KDD: Khai phá tri thức (Knowledge Discovery in Databases)
STC: Phân cụm cây hậu tố (Suffix tree clustering)
TF: Tần suất xuất hiện (term frequency)
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 10 -
DANH MỤC HÌNH VẼ, BẢNG BIỂU
Danh mục hình vẽ
Hình 1: Các bước trong KDD 16
Hình 2:
Quá trình phân cụm kết quả của một truy vấn. 29
Hình 3:
Các bước tạo ra tập luật 47
Hình 4:
Xây dựng tập tài liệu xác định từ 48
Hình 6:
Hai vector
j
d và Q càng gần nhau khi góc teta càng nhỏ 50
Hình 6:
Một cây lược đồ biểu diễn hình ảnh tiến trình trộn tạo nên cấp bậc.
Người dùng có thể cắt qua cây lược đồ tại một mức phù hợp của độ tương
t
ự để đạt được số cụm mong muốn 64
Danh mục bảng biểu
Bảng 1: Ví dụ phân cụm kết quả của truy vấn “Hồ Chí Minh”. Chỉ có 5 cụm đầu
tiên được biểu diễ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
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 13 -
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

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 bottom-
up. 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.
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 15 -
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
1.1 Khai phá dữ liệu
1.1.1 Khai phá dữ liệu là gì?
Khai phá dữ liệu - Data Mining “Khai phá dữ liệu được định nghĩa như
quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu” (Jiawei Han –
Data Mining: Concepts and Techiniques (2000) [5] ). M
ột ví dụ trực quan là việc
khai thác vàng từ đá và cát. Thuật ngữ Data Mining ám chỉ việc tìm một tập nhỏ
có giá trị từ một lượng lớn các dữ liệu thô. Khai phá dữ liệu khác với khai phá tri
thức – Knowledge Discovery in Databases (KDD). Khai phá dữ liệu chỉ là một

vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý
theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ
thuật của machine learning như cây quyết định (decision tree), mạng
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 17 -
nơ ron nhân tạo (neural network), .v.v. Người ta còn gọi phân lớp là
h
ọc có giám sát (học có thầy).
 Phân cụm (clustering): xếp các đối tượng theo từng cụm (số lượng
cũng như tên của cụm chưa được biết trước. Người ta còn gọi phân
c
ụm là học không giám sát (học không thầy).
 Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá
luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp
cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường
chứng khoán vì nó có tính dự báo cao.
1.1.3 Ứng dụng của khai phá dữ liệu
Data Mining tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều
sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực
tiễn của nó. Chúng ta có thể liệt kê ra đây một số ứng dụng điển hình:
 Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision
support)
 Điều trị y học (medical treatment)
 Text mining & Web mining
 Tin-sinh (bio-informatics)
 Tài chính và thị trường chứng khoán (finance & stock market)
 Bảo hiểm (insurance)
 Nhận dạng (pattern recognition)
 .v.v.
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007

ười đọc có thể không cần đọc một cách liên tục. Ví dụ khi đọc một cuốn sách
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 19 -
người đọc không phải đọc lần lượt từng trang từ đầu đến cuối mà có thể nhảy
cóc đến các đoạn sau để tham khảo về các vấn đề họ quan tâm.
Như vậy văn bản HyperText bao gồm dạng chữ
viết không liên tục,
chúng được phân nhánh và cho phép người đọc có thể chọn cách đọc theo ý
muốn của mình. Hiểu theo nghĩa thông thường thì HyperText là một tập các
trang chữ viết được kết nối với nhau bởi các liên kết và cho phép người đọc có
thể đọc theo các cách khác nhau. Như ta đã làm quen nhiều với các trang định
dạng HTML, trong các trang có những liên kết trỏ tới từng phần khác nhau của
trang đó hoặc trỏ tới trang khác, và người đọc sẽ đọc văn bản dựa v
ào những liên
k
ết đó.
Bên cạnh đó, HyperText cũng là một dạng văn bản Text đặc biệt nên
c
ũng có thể bao gồm các chữ viết liên tục (là dạng phổ biến nhất của chữ viết).
Do không bị hạn chế bởi tính liên tục trong HyperText, chúng ta có thể tạo ra các
dạng trình bày mới, do đó tài liệu sẽ phản ánh tốt hơn nội dung muốn diễn đạt.
Hơn nữa người đọc có thể chọn cho m
ình một cách đọc phù hợp chẳng hạn như
đi sâu vào một vấn đề m
à họ quan tâm. Sáng kiến tạo ra một tập các văn bản
cùng với các con trỏ trỏ tới các văn bản khác để liên kết một tập các văn bản có
m
ối quan hệ voiứ nhau với nhau là một cách thực sự hay và rất hữu ích để tổ
chức thông tin. Với người viết, cách này cho phép họ có thể thoải mái loại bỏ
những băn khoăn về thứ tự trình bày, mà có thể tổ chức vấn đề thành những phần

nghiêng,…). Nhờ các thẻ này mà chúng ta có thêm một tiêu chuẩn (so với tài
li
ệu fulltext) để có thể tìm kiếm và phân loại chúng. Dựa vào các thẻ đã quy định
trước chúng ta có thể phân thành các độ ưu tiên khác nhau cho các từ khóa nếu
chúng xuất hiện ở những vị trí khác nhau. Ví dụ khi tìm kiếm các tài liệu có nội
dung liên quan đến “people “ th
ì chúng ta đưa từ khóa tìm kiếm là “people”, và
các tài li
ệu có từ khóa “people” đứng ở tiêu đề thì sẽ gần với yêu cầu tìm kiếm
hơn.
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 21 -
1.3 Khai phá dữ liệu Web
1.3.1 Nhu cầu
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một
khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với sự
thay đổi v
à phát triển hàng ngaỳ hàng giờ về nội dung cũng như số lượng của các
trang Web trên Internet thì vấn đề tìm kiếm thôn g tin đối với người sử dụng lại
ngày càng khó khăn. Có thể nói nhu cầu t
ìm kiếm thông tin trên môt cơ sở dữ
liệu phi cấu trúc đã được phát triển chủ yếu cùng với sự phát triển của Internet.
Thực vậy với Internet con người đã làm quen với các trang Web cùng với vô vàn
các thông tin. Trong nh
ững năm gần đây Intrnet đã trở thành một trong những
kênh về khoa học, thông tin kinh tế, thương mại và quảng cáo. Một trong những
lý do cho sự phát triển này là sự thấp về giá cả tiêu tốn khi công khai một trang
Web trên Internet. So sánh với những dịch vụ khác như mua bản hay quảng cáo
trên một tờ báo hay tạp chí, thì một trang Web "đòi" rẻ hơn rất nhiều và cập nhật
nhanh chóng hơn tới h

vẫn là bài toán hay và cần phát triển nghiên cứu hiện nay.
1.3.2 Đặc điểm
1. Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ
Data mining
Các cơ sở dữ liệu truyền thống thì có kích thước không lớn lắm và
thường được lưu trữ ở một nơi, trong khi đó kích thước Web rất lớn, tới hàng
terabytes và thay đổi liên tục, không những thế còn phân tán trên rất nhiều máy
tính khắp nơi trên thế giới. Một vài nghiên cứu về kích thước của Web đã đưa ra
các số liệu như sau: Hiện nay trên Internet có khoảng hơn một tỷ các trang Web
được cung cấp cho người sử dụng., giả sử kích thước trung b
ình của mỗi trang là
5-10Kb thì t
ổng kích thước của nó ít nhất là khoảng 10 terabyte. Còn tỷ lệ tăng
của các trang Web thì thật sự gây ấn tượng. Hai năm gần đây số các trang Web
tăng gấp đôi v
à còn tiếp tục tăng trong hai năm tới. Nhiều tổ chức và xã hội đặt
hầu hết những thông tin công cộng của họ lên Web. Như vậy việc xây dựng một
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 23 -
kho dữ liệu để lưu trữ, sao chép hay tích hợp các dữ liệu trên Web là gần như
không thể
2. Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu
văn bản truyền thống khác
.
Các d
ữ liệu trong các cơ sở dữ liệu truyền thống thì thường là loại dữ liệu
đồng nhất (về ngôn ngữ, định dạng,…), c
òn dữ liệu Web thì hoàn toàn không
đồng nhất. Ví dụ về ngôn ngữ dữ liệu Web bao gồm rất nhiều loại ngôn ngữ
khác nhau (Cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập trình), nhiều loại định

"lạc" khi đang "mò mẫm trong "bóng tối" của mạng hoặc sẽ chán khi tìm kiếm
mà chỉ nhận những mảng thông tin không mấy hữu ích
5. Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích
Theo thống kê, 99% của thông tin Web là vô ích với 99% người dùng
Web. Trong khi nh
ững phần Web không được quan tâm lại bị búi vào kết quả
nhận được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào để
nhận được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng?
Như vậy chúng ta có thể thấy các điểm khác nhau giữa việc tìm kiếm
trong một cơ sở dữ liệu truyền thống với việc tìm kiếm trên Internet. Những đặc
điểm trên đ
ã đẩy mạnh việc nghiên cứu khai phá và sử dụng tài nguyên trên
Internet.
1.3.3 Các hướng tiếp cận
Như đã phân tích về đặc điểm và nội dung các văn bản HyperText ở trên,
t
ừ đó khai phá dữ liệu Web cũng sẽ tập trung vào các thành phần có trong trang
Web. Đó chính là:
1. Khai phá nội dung trang Web (Web Content mining)
Đặng Quang Huy-Luận văn cao học-Trường Đại học Công nghệ-2007
- 25 -
Khai phá nội dung trang Web gồm hai phần:
a. Web Page Content
Ngh
ĩa là sẽ sử dụng chỉ các từ trong văn bản mà không tính đến các liên
k
ết giữa các văn bản. Đây chính là khai phá dữ liệu Text (Textmining)
b. Search Result
Tìm ki
ếm theo kết quả. Trong các máy tìm kiếm, sau khi đã tìm ra những