Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải
1
LỜI CẢM ƠN
Em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy giáo tiến sĩ Hà
Quang Thụy và thầy Nguyễn Trí Thành, khoa Công nghệ, ĐHQG Hà nội đã hướng
dẫn và động viên em rất nhiều trong quá trình làm luận văn.
Em xin cảm ơn các Thầy Cô trong khoa Công nghệ, Đại học Quốc Gia Hà
Nội, và nhóm Xemina "Máy tìm kiếm VietSeek" thuộc bộ môn Các Hệ thống Thông tin,
khoa Công nghệ, những người đã giúp đỡ cho em trong suốt quá trình học tập và
nghiên cứu.
Cuối cùng, em xin bày tỏ lòng biết ơn tới gia đình và các bạn bè đã giúp đỡ,
động viên em rất nhiều trong suốt quá trình học tập.
Hà Nội ngày 28/05/2003
Sinh viên
Đặng Thanh Hải
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải
2
TÓM TẮT NỘI DUNG
Do kích thước khổng lồ của dữ liệu Web, việc xây dựng cũng như tích hợp các
yếu tố khai phá dữ liệu Web vào công cụ tìm kiếm trên mạng Internet đang thu hút
được sự quan tâm rất lớn của rất nhiều nhà nghiên cứu. Khóa luận đề cập tới vấn đề
cải tiến chất lượng và tốc độ của máy tìm kiếm bằng việc nghiên cứu bài toán phân lớp
trong máy tìm kiếm.
Nội dung chính của khóa luận trình bày cấu trúc cũng như mô hình hoạt động
của modul đánh chỉ mục trong máy tìm kiếm VietSeek, các kỹ thuật cơ bản và các
thuật toán thông dụng liên quan đến quá trình khai phá dữ liệu Web trong máy tìm
kiếm, mà cụ thể là bài toán phân lớp trang văn bản Web. Đặc biệt khóa luận tập trung
vào giải pháp phân lớp theo phương pháp Bayes thứ nhất. Xuất phát từ công thức (3.8)
[1], khóa luận đề xuất các công thức (3.15), (3.16) và chứng minh tính đúng đắn của
chúng, với giả thiết về tính độc lập của các biến cố. Đi kèm với giải pháp phân lớp
Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho các lớp.
Khóa luận đã tích hợp thành công các đề xuất này vào máy tìm kiếm VietSeek
và thu được kết quả rất khả quan.
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải
3
PHẦN MỞ ĐẦU
Ngày nay sự phát triển vượt bậc của công nghệ thông tin, đặc biệt là sự ra đời
và phát triển như vũ bão của mạng Internet đã tạo ra một cuộc cách mạng trong mọi
lĩnh vực đời sống xã hội. Có thể nói rằng Internet là một thế giới ảo với vô vàn các
thông tin về mọi mặt của đời sống kinh tế, chính trị, xã hội được trình bày dưới dạng
văn bản, hình ảnh, âm thanh,...
Internet luôn biến đổi không ngừng cả về kích thước lẫn nội dung. Đến nay
không có một ai biết được chính xác kích thước của Internet là bao nhiêu, có bao
nhiêu Website và bao nhiêu trang Web. Bên cạnh đó, thông tin trong chính các trang
Web cũng được cập nhật liên tục. Theo kết quả nghiên cứu , hơn 500.000 trang Web
trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì
50% các trang trong tên miền đó biến mất, nghĩa là địa chỉ URL của nó không còn tồn
tại nữa [2].
Một điều thực tế là khối lượng dữ liệu tăng lên gấp nhiều lần, nhưng tỷ lệ các
thông tin có ích so với khối lượng dữ liệu đó lại giảm đi rất nhiều. Theo thống kê, 99%
của thông tin Web là vô ích với 99% người dùng Web [2]. Rõ ràng với một khối lượng
khổng lồ dữ liệu được lưu trữ trên Internet thì vấn đề tìm kiếm thông tin có ích đang
trở thành một vấn đề nghiên cứu có tính thời sự cao. Người dùng không thể tự tìm
kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một
trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ
trang Web có nội dung giống với yêu cầu của người tìm kiếm. Hiện nay, trên thế giới
có một số máy tìm kiếm thông dụng như Yahoo, Google, Alvista,...đã được xây dựng
và triển khai nhằm đáp ứng nhu cầu tìm kiếm thông tin của người dùng.
Mặc dù đã đáp ứng ứng được phần lớn nhu cầu tìm kiếm thông tin của người
dùng, tuy nhiên hầu hết các máy hiện nay mới chỉ hỗ trợ việc tìm kiếm theo từ khóa,
mà chưa xét đến vấn đề ngữ nghĩa của các từ cần tìm kiếm. Với việc tìm kiếm bằng
cách đối sánh các từ khóa, kết quả tìm kiếm có thể không bao gồm tất cả các tài liệu
như ý muốn của người dùng (do vấn đề từ đồng nghĩa). Thậm chí các tài liệu tìm thấy
có thể không liên quan đến yêu cầu của người dùng (do vấn đề từ đa nghĩa).
Mặc khác các máy tìm kiếm thông dụng hiện nay đều chưa có chức năng lưu
trữ và phân tích tiểu sử của người dùng, để từ đó có khả năng hỗ trợ tốt hơn với từng
lớp người dùng. Cụ thể, giả sử chúng ta có các trang Web về các vấn đề Tin học, Thể
thao, Kinh tể-Xã hội và Xây dựng...Căn cứ vào nội dung của các tài liệu mà khách
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải
4
hàng xem hoặc tải về, sau khi phân lớp chúng ta sẽ biết khách hàng hay tập trung vào
nội dung gì, từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà
khách hàng quan tâm.
Từ những nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài
toán hay, có tính thời sự cao, cần được phát triển và nghiên cứu hiện nay.
Đề tài khóa luận tốt nghiệp ‘Thuật toán phân lớp văn bản Web và thực
nghiệm trong máy tìm kiếm VietSeek (Vinahoo)’ cũng không nằm ngoài mục đích
trên.
Ngoài phần mở đầu và phần kết luận, nội dung của khóa luận được tổ chức
thành 4 chương với nội dung chính như sau:
Chương 1, với tên gọi Máy tìm kiếm VietSeek, nhằm mục đích giới thiệu một
cách chi tiết cấu trúc cũng như cơ chế hoạt động của các máy tìm kiếm VietSeek.
Ngoài ra, phần đầu của chương còn giới thiệu tổng quát về cấu trúc chung của các máy
tìm kiếm đang được sử dụng rộng rãi hiện nay.
Chương 2 có tên gọi là Khai phá dữ liệu Web trong máy tìm kiếm. Nội dung
chính của chương trình bày các kỹ thuật cơ bản liên quan dến bài toán khai phá dữ liệu
Web trong máy tìm kiếm.
Chương 3, tích hợp giải pháp phân lớp trang văn bản vào máy tìm kiếm
VietSeek, giới thiệu các thuật toán điển hình được áp dụng để giải quyết bài toán phân
lớp văn bản. Trong đó đặc biệt tập trung vào giải pháp phân lớp theo phương pháp
Bayes thứ nhất. Các công thức đề xuất (3.15) và (3.16), cùng với quá trình chứng minh
tính đúng đắn của chúng được trình bày một cách chi tiết trong chương này. Đi kèm
với giải pháp phân lớp Bayes là các đề xuất nhằm giải quyết vấn đề tính ngưỡng cho
các lớp. Phần cuối của chương giới thiệu quá trình tích hợp giải pháp phân lớp trang
văn bản vào máy tìm kiếm VietSeek.
Chương 4 với tựa đề Kết qủa thực nghiệm và đánh giá sẽ giới thiệu các kết
quả thực nghiệm thu được khi tiến hành tích hợp giải pháp phân lớp văn bản Web vào
máy tìm kiếm VietSeek. Sau đó đưa ra các đánh giá về các công thức đề xuất dựa trên
kết quả thực nghiệm.
Thuật toán phân lớp văn bản Web và thực nghiệm trong máy tìm kiếm VietSeek
Khóa luận tốt nghiệp đại học Đặng Thanh Hải
5
Chương 1. MÁY TÌM KIẾM VIETSEEK
1.1. Giới thiệu máy tìm kiếm VietSeek
Hiện nay, trên thế giới có một số máy tìm kiếm thông dụng như Yahoo,
Google, Alvista,...đã được xây dựng và triển khai nhằm đáp ứng nhu cầu tìm kiếm
thông tin ngày càng lớn của người dùng.
Máy tìm kiếm là một hệ thống được xây dựng có khả năng tiếp nhận các yêu
cầu tìm kiếm từ phía người dùng (thường là một tập các từ khoá), phân tích nội dung
câu truy vấn và tiến hành tìm kiếm trong cơ sở dữ liệu đã được xây dựng sẵn từ trước.
Kết quả trả về cho người sử dụng bởi máy tìm kiếm là tập hợp các trang Web liên
quan hoặc có chứa các từ khóa xuất hiện trong câu truy vấn.
Đối với các máy tìm kiếm, vấn đề biểu diễn dữ liệu là rất quan trọng. Biểu
diễn các trang Web như thế nào để vừa có khả năng lưu trữ được một số lượng khổng
lồ các trang Web, vừa cho phép máy tìm kiếm thực hiện việc tìm kiếm nhanh chóng
và chính xác.
Cấu trúc điển hình của một máy tìm kiếm được mô tả như trong hình (1.0 )
Trong thực tế thì mỗi máy tìm kiếm lại có các sửa đổi riêng theo cách riêng, tuy nhiên
về cơ bản vẫn dựa trên các bộ phận được mô tả trong hình (1.0 )
Kho trang web
Bé t×m
duyÖt
Hình 1.0. Mô hình cấu trúc hoạt động của máy tìm kiếm