ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Trần Ngọc Hà
ỨNG DỤNG TẬP THÔ VÀO TÌM KIẾM WEB
LUẬN VĂN THẠC SĨ
Hà Nội 2010
Mục lục
MỞ ĐẦU ........................................................................................................... 6
Danh sách bảng biểu .......................................................................................... 4
Danh sách hình vẽ .............................................................................................. 5
Chương 1: GIỚI THIỆU TỔNG QUAN ........................................................... 9
1.1. Lý do chọn đề tài .....................................................................................9
1.2. Phạm vi công việc ................................................................................. 10
1.3. Cấu trúc luận văn ................................................................................... 10
Chương 2: MÁY TÌM KIẾM WEB .................................................................12
2.1. Khái niệm .............................................................................................. 12
2.2. Cấu trúc máy tìm kiếm web ................................................................... 13
2.3. Biểu diễn kết quả tìm kiếm .................................................................... 15
2.4. Đánh giá chất lượng tìm kiếm ................................................................ 17
Chương 3: PHÂN CỤM TÀI LIỆU VÀ VẤN ĐỀ TÁCH TỪ TIẾNG VIỆT ...19
3.1. Phân cụm ............................................................................................... 19
3.1.1.Khái niệm ............................................................................................. 19
3.1.2.Ứng dụng của phân cụm tài liệu trong thu thập và tổ chức thông tin ..... 20
3.2. Mô hình không gian vector và trình bày văn bản ................................... 21
3.2.1.Các kỹ thuật tiền xử lý tài liệu ............................................................... 22
3.2.2.Bảng trọng số ....................................................................................... 23
3.2.3.Độ đo tương tự ...................................................................................... 26
3.2.4.Biểu diễn cụm ....................................................................................... 27
3.3. Các giải thuật phân cụm ........................................................................ 27
3.3.1.Phương pháp phân cụm phân cấp .......................................................... 28
3.3.2.Phương pháp phân cụm phân hoạch ...................................................... 29
3.3.3.Thuật toán phân cụm bán giám sát Seeded - KMeans............................ 30
3.3.4.Tiêu chuẩn sự tối ưu ........................................................................ 32
3.3.5.Gán cứng và gán mềm........................................................................... 33
3.4. Các bước thực hiện phân cụm ................................................................ 34
3.5. Đánh giá kết quả phân cụm .................................................................... 34
3.6. Phân cụm kết quả tìm kiếm web ..................................................... 34
3.7. Các phương pháp tách từ tiếng Việt ....................................................... 35
3.7.1.Đặc điểm từ trong tiếng Việt ................................................................. 35
3.7.2.Phương pháp so khớp cực đại ............................................................... 36
3.7.3.Phương pháp học cải biến ..................................................................... 37
3.7.4.Mô hình tách từ bằng WFST và mạng Neural ....................................... 37
3.7.5.Phương pháp tách tách từ tiếng Việt dựa trên thống kê từ Internet và thuật
giải di truyền ................................................................................................. 38
Chương 4: LÝ THUYẾT TẬP THÔ ............................................................. 39
4.1. Giới thiệu .............................................................................................. 39
4.2. Hệ thông tin ........................................................................................... 40
4.3. Quan hệ bất khả phân biệt...................................................................... 42
4.3.1.Quan hệ tương đương - Lớp tương đương ............................................. 43
4.4. Xấp xỉ tập hợp ....................................................................................... 44
4.5. Hàm thuộc thô ....................................................................................... 50
4.6. Mô hình tập thô dung sai ....................................................................... 52
4.6.1.Không gian dung sai các từ chỉ mục ...................................................... 53
4.6.2.Nâng cao chất lượng biểu diễn tài liệu .................................................. 55
4.6.3.Mở rộng lược đồ trọng số cho xấp xỉ trên.............................................. 55
Chương 5: ÁP DỤNG LÝ THUYẾT TẬP THÔ VÀO PHÂN CỤM KẾT QUẢ
TÌM KIẾM WEB ..............................................................................................57
5.1. Vấn đề phân cụm kết quả tìm kiếm web ................................................ 57
5.2. Các thuật toán phân cụm tài liệu dựa trên TRSM .................................. 58
5.2.1.Biểu diễn cụm .................................................................................... 58
5.2.2.Thuật toán phân cụm không phân cấp dựa trên TRSM ............... 60
5.2.3.Thuật toán phân cụm phân cấp dựa trên TRSM .............................. 62
5.3. Thuật toán TRC .................................................................................. 62
5.3.1.Tiền xử lý ............................................................................................ 63
5.3.2.Xây dựng ma trận từ - tài liệu................................................................ 63
5.3.3.Tạo lớp dung sai.................................................................................... 64
5.3.4.Thuật toán phân cụm Seeded - KMeans cải tiến .................................... 68
Chương 6: XÂY DỰNG ỨNG DỤNG THỬ NGHIỆM ....................................71
6.1. Xác định yêu cầu ................................................................................... 71
6.2. Các thành phần của ứng dụng thử nghiệm ............................................. 71
6.3. Xây dựng các thành phần chức năng...................................................... 72
6.3.1.Trình thu thập nội dung web ................................................................. 72
6.3.2.Bộ tách từ tiếng Việt ............................................................................. 75
6.3.3.Bộ xử lý truy vấn .................................................................................. 76
6.3.4.Biểu diễn kết quả tìm kiếm web ............................................................ 76
6.4. Triển khai ứng dụng thử nghiệm ............................................................ 77
KẾT LUẬN ......................................................................................................84
Tài liệu tham khảo ............................................................................................86
Danh sách bảng biểu
Bảng 3-1. Ví dụ bảng trọng số nhị phân của các tài liệu. ...................................24
Bảng 3-2. Ví dụ bảng trọng số của các tài liệu. .................................................24
Bảng 3-3. Ví dụ trọng số cho các tài liệu trong bảng 3-2. Trọng số của vector tài
liệu được chuẩn hóa bằng độ dài của nó. ...........................................25
Bảng 3-4. Một số phép đo độ tương tự giữa hai vectơ tài liệu X, Y. Trong đó, xi, yi
là trọng số thành phần thứ i của vectơ ...............................................26
Bảng 3-5. So sánh các đặc điểm khác nhau giữa tiếng Anh và tiếng Việt ..........36
Bảng 4-1. Một hệ thông tin đơn giản .................................................................41
Bảng 4-2. Một bảng quyết định đơn giản ..........................................................42
Bảng 4-3. Bảng quyết định dùng minh hoạ hàm thuộc thô ................................52
Bảng 4-4. Các lớp dung sai quan trọng của các từ được sinh ra từ 200 snippets trả
về từ máy tìm kiếm Google với từ khóa “jaguar” và ngưỡng đồng xuất
hiện = 9 ..........................................................................................55
Danh sách hình vẽ
Hình 2-1. Giao diện biểu diễn kết quả tìm kiếm Web của Google .....................12
Hình2-2. Cấu trúc bên trong của của máy tìm kiếm Web ..................................13
Hình 2-3. Cấu trúc dữ liệu inverted index .........................................................14
Hình 3-1. Mô tả phân cụm ................................................................................20
Hình 3-2. Tiến trình phân cụm tài liệu ..............................................................20
Hình 3-3. So sánh giữa phân cụm tài liệu và phân cụm kết quả tìm kiếm web. .35
Hình 4- 1. Hình ảnh minh họa các khái niệm của tập thô ..................................40
Hình 4-2. Xấp xỉ tập đối tượng trong Bảng 4-2 bằng các thuộc tính điều kiện Age
và LEMS. Mỗi vùng được thể hiện kèm theo tập các lớp tương đương
tương ứng. .........................................................................................46
Hình 5-1. Các bước của thật toán TRC. ............................................................62
Hình 5-2. Sơ đồ các bước thuật toán tạo lớp dung sai .......................................65
Hình 6-1. Qui trình thu thập nội dung web ........................................................73
Hình 6-2. Nhận dạng tiêu đề bài viết bằng addon Firebug trên trình duyệt Firefox.
..........................................................................................................74
Hình 6-3. Giao diện quản trị các mẫu nhận dạng...............................................75
Hình 6-4. Website http://doctinnhanh.net. .........................................................78
Hình 6-5. Giao diện biểu diễn kết quả tìm kiếm chia theo chủ đề......................81
Hình 6-6. Website Bách khoa toàn thư văn hóa Việt .........................................83
MỞ ĐẦU
Những năm gần đây trên thế giới nói chung và ở Việt Nam nói riêng, đi cùng
với sự phát triển của công nghệ web 2.0, các hệ thống wiki và các mạng xã hội
đang có những sự phát triển nhảy vọt cả về số lượng và chất lượng. Có thể nói
chưa có bao giờ việc đưa thông tin lên mạng lại dễ dàng như giai đoạn hiện nay.
Bất cứ cá nhân nào tham gia vào cộng đồng mạng cũng có thể đóng góp những bài
viết vào kho thông tin khổng lồ của nhân loại. Chính vì sự phát triển đó mà hầu
như bất cứ vấn đề gì mà ta quan tâm đều có thể sử dụng các bộ máy tìm kiếm để
tìm kiếm trên Internet. Tuy nhiên việc khai thác các thông tin cần thiết trong một
kho dữ liệu khổng lồ sao cho tiện lợi và chuẩn xác cũng là một vấn đề cần phải giải
quyết.
Hiện nay khai thác và tìm kiếm thông tin trên Internet là vấn đề được rất
nhiều nhà nghiên cứu quan tâm. Trong khi khối lượng thông tin trên Web khổng
lồ, mà câu hỏi truy vấn của người sử dụng thường ít chính xác, nên số kết quả trả
về từ các máy tìm kiếm có thể lên đến hàng trăm hay hàng ngàn tài liệu. Do đó, tìm
được chính xác tài liệu mình quan tâm là khó và tốn nhiều thời gian. Thực nghiệm
cho thấy, nếu nội dung được chia thành các nhóm chủ đề sẽ giúp người dùng
nhanh chóng tìm được kết quả mình cần. Vì vậy, một trong những cách tiếp cận để
giải quyết vấn đề khai thác hiệu quả các kết quả từ các máy tìm kiếm thông tin là
sử dụng kĩ thuật phân cụm kết quả tìm kiếm theo chủ đề tạo nên cách biểu diễn kết
quả tìm kiếm Web cô đọng và rõ ràng. Đây là một vấn đề nhận được sự quan tâm
của rất nhiều tác giả, họ đã đề ra nhiều cách tiếp cận khác nhau để giải quyết bài
toán này. Trong đề tài này chúng tôi sẽ áp dụng lý thuyết tập thô vào phân cụm kết
quả tìm kiếm Web tiếng Việt. Cách tiếp cận của chúng tôi là sử dụng mô hình tập
thô dung sai để tăng chất lượng việc biểu diễn các tài liệu và các cụm từ đó làm
tăng hiệu quả việc phân cụm; đồng thời chúng tôi sử dụng phương pháp phân cụm
bán giám sát Seeded - KMeans để phân cụm và xác định chủ đề tài liệu.
Mục tiêu của đề tài là xây dựng thử nghiệm một công cụ tìm kiếm web tiếng
Việt có khả năng phân cụm các tài liệu vào các chủ đề khác nhau giúp người dùng
có thể nhanh chóng tìm được kết quả mình cần nhờ cách biểu diễn kết quả tìm
kiếm rõ ràng và cô đọng. Với mục tiêu đó, sau quá trình làm việc, chúng tôi đã xây
dựng được một công cụ tìm kiếm web tiếng Việt gồm các thành phần chính sau:
Trình thu thập web tiếng Việt, trình thu thập này có đặc điểm nổi bật là
có khả năng phân tích cấu trúc các trang web này thành các phần như
tiêu đề, tóm tắt bài viết, nội dung bài viết,… nhờ các mẫu nhận dạng
cấu trúc do người dùng đưa vào.
Thành phần thứ 2 được sử dụng để phân tích các trang web thành các từ
tiếng Việt và biểu diễn các tài liệu thu thập được dưới dạng vector tài
liệu trong không gian vector.
Thành phần thứ 3 là thành phần xử lý các truy vấn của người dùng và
trả về các kết quả tìm kiếm thỏa mãn truy vấn của người dùng.
Thành phần thứ 4 là biểu diễn kết quả tìm kiếm web, mục tiêu xây
dựng thành phần này là thể hiện được kết quả tìm kiếm web một cách
rõ ràng và cô đọng bằng cách gán chúng vào các chủ đề tạo thuận lợi
cho người sử dụng trong việc tìm kiếm thông tin. Vì vậy chúng tôi áp
dụng mô hình tập thô dung sai và thuật toán phân cụm bán giám sát
Seeded – Kmeans để phân cụm các kết quả tìm kiếm web. Các kết quả
tìm kiếm sẽ được phân thành các chủ đề khác nhau có nhãn được định
sẵn dựa trên các mẫu tài liệu đã được gán nhãn.
Mặc dù bản thân đã nỗ lực cố gắng, cùng sự giúp đỡ của các đồng nghiệp và
đặc biệt là sự hướng dẫn chỉ bảo tận tình của PGS. TS Hoàng Xuân Huấn, nhưng
vì thời gian có hạn nên đề tài không tránh khỏi những thiếu sót, rất mong nhận
được sự đóng góp ý kiến của các chuyên gia, bạn bè và đồng nghiệp.
Qua đây, tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS. TS Hoàng Xuân Huấn, đã
tận tình hướng dẫn cho tôi những định hướng và những ý kiến rất quý báu trong
suốt quá trình thực hiện luận văn này.
Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Truyền dữ liệu
và Mạng máy tính, Khoa Công nghệ thông tin, trường Đại học Công nghệ - Đại
học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất để tôi hoàn thành khóa học này.
Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích
và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng
nghiệp đã hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn
này.
Chương 1: GIỚI THIỆU TỔNG QUAN
1.1. Lý do chọn đề tài
Sự phát triển không ngừng của Word Wide Web (WWW) trong giai đoạn
hiện nay đã mang lại cho loài người một nguồn thông tin khổng lồ. Hầu như các
thông tin về mọi lĩnh vực của cuộc sống đều có thể tìm thấy trên Web. Cùng với sự
bùng nổ thông tin đó, các công cụ tìm kiếm web cũng không ngừng phát triển để
phục vụ cho nhu cầu tìm kiếm thông tin của con người.
Hiện nay có rất nhiều công cụ tìm kiếm web mạnh giúp chúng ta tìm kiếm
thông tin nhanh chóng như Google, Yahoo, Answer, Altavista, … Đặc điểm của
các công cụ tìm kiếm này là thực hiện việc tìm kiếm dựa trên phương pháp xếp
hạng tài liệu (Document Ranking) và biểu diễn kết quả tìm kiếm theo thứ tự hạng
xuất hiện. Với sự bùng nổ thông tin như hiện nay, mặc dù các công cụ tìm kiếm có
nhiều cải tiến nhưng cách tiếp cận này có một số hạn chế như dưới đây:
Do sự bùng nổ của thông tin trên WWW, và tính chất động của các trang web
nên máy tìm kiếm không thể thực hiện tính hạng được cho tất cả các tài liệu mà chỉ
có thể tính hạng cho một phần các tài liệu.
Khi có ý định tìm thông tin trên WWW, trong suy nghĩ của người dùng hình
thành khái niệm về cái họ cần tìm, khái niệm này được chuyển thành một tập các
từ khóa và được sử dụng để đặt câu hỏi truy vấn. Tuy nhiên do kinh nghiệm sử
dụng hạn chế, các từ khóa người dùng nhập thường ngắn và cho các kết quả tìm
kiếm là chung chung, có thể lên đến hàng trăm hoặc hàng ngàn kết quả. Trong khi
đó người sử dụng lại chỉ có thói quen xem kết quả trên trang đầu tiên và ít người
duyệt đến các trang sau, do đó bỏ qua một số kết quả tìm kiếm cần thiết nhất.
Với các lý do trên ta thấy phát triển giao diện tương tác thông minh giữa
người và máy, hỗ trợ người sử dụng trong việc tìm kiếm thông tin là việc làm cần
thiết. Đây là một trong những vấn đề được nhiều nhà nghiên cứu quan tâm. Mặc
dù đã có một số nghiên cứu thành công trong lĩnh vực này, nhưng đa phần chúng
chỉ xử lý tốt trên tiếng Anh, nên trong luận văn này, chúng tôi mạnh dạn áp dụng
tập thô vào việc xây dựng thử nghiệm một công cụ tìm kiếm web cho phép người
dùng tìm kiếm theo chủ đề và giải quyết tốt các đặc thù của tiếng Việt.
1.2. Phạm vi công việc
Để đạt được mục đích đã đề ra, chúng tôi sẽ phải thực hiện những công việc
sau:
Tìm hiểu các thành phần và việc xây dựng một hệ thống Search Engine. Áp
dụng vào xây dựng một hệ thống tìm kiếm thông tin tiếng Việt.
Tìm hiểu các thuật toán phân cụm tài liệu để áp dụng vào việc phân cụm các
kết quả tìm kiếm web.
Tìm hiểu các đặc điểm của tiếng Việt và các phương pháp tách từ tiếng Việt,
áp dụng các thuật phương pháp trên để phân tích các trang web tiếng Việt thành
các từ phục vụ cho việc mô hình hóa tài liệu và biểu diễn các đặc trưng của cụm.
Nghiên cứu lý thuyết tập thô đặc biệt là mô hình tập thô dung sai, từ đó áp
dụng mô hình tập thô dung sai để cải tiến thuật toán Seeded - KMeans sử dụng cho
việc phân cụm kết quả tìm kiếm web nhằm tối ưu hóa kết quả trả về của quá trình
tìm kiếm web.
1.3. Cấu trúc luận văn
Với phạm vi công việc cần thực hiện như trên, cấu trúc của đề tài được tổ
chức như sau:
Chương 1: Giới thiệu tổng quan.
Chương 2: Trình bày kiến thức tổng quan về máy tìm kiếm Web.
Chương 3: Trình bày các kiến thức về phân cụm tài liệu và vấn đề tách từ
Tiếng Việt.
Chương 4: Trình bày tổng quan về lý thuyết tập thô và mô hình tập thô dung
sai.
Chương 5: Trình bày cách áp dụng lý thuyết tập thô vào việc phân cụm kết
quả tìm kiếm Web.
Chương 6: Trình bày kết quả thử nghiệm của luận văn.
Và phần cuối cùng là kết luận của luận văn
Chương 2: MÁY TÌM KIẾM WEB
2.1.
Khái niệm
Máy tìm kiếm Web là một công cụ giúp người sử dụng tìm kiếm thông tin
trên mạng một cách nhanh chóng và đầy đủ.
Máy tìm kiếm web tương tác với người sử dụng thông qua một giao diện khá
đơn giản và thân thiện. Người sử dụng chỉ cần đặt câu hỏi truy vấn về vấn đề quan
tâm, máy tìm kiếm web ngay lập tức sẽ trả về tập kết quả tìm kiếm (snippets).
Thông thường, mỗi kết quả tìm kiếm bao gồm tựa đề, địa chỉ của tài liệu và miêu
tả ngắn gọn nội dung chính tài liệu. Ngoài ra một số máy tìm kiếm web còn cho
phép người dùng xem nội dung của tài liệu được lưu lại trên máy chủ của dịch vụ
tìm kiếm.
Tên tài liệu
Tóm tắt nội dung
Snippet
URL của tài liệu
Hình 2-1. Giao diện biểu diễn kết quả tìm kiếm Web của Google
2.2.
Cấu trúc máy tìm kiếm web
Cấu trúc của máy tìm kiếm web được thể hiện trong hình 2-2
Hình2- 2. Cấu trúc bên trong của của máy tìm kiếm Web
Trình thu thập web (Web Crawler)
Web Crawler hay còn được gọi là Web Spider là một trong hai thành phần
tương tác trực tiếp với WWW. WWW là một tập hợp các tài liệu được liên kết với
nhau bởi các siêu liên kết, web crawler có nhiệm vụ là phát hiện các trang mới trên
WWW bằng cách thu thập các siêu liên kết từ các trang tài liệu. Quá trình này
được thực hiện đệ qui để thăm dò hầu hết các trang web trên Internet. Trong quá
trình này web crawler sẽ phải sử dụng một số kỹ thuật để tránh không bị lấy thông
tin trùng lặp. Web crawler vừa thu thập các trang web mới nhưng cũng đồng thời
kiểm tra lại những siêu liên kết đã không còn tồn tại trên WWW để loại chúng khỏi
các kết quả tìm kiếm.
Chỉ mục tài liệu (Document Index)
Thành phần lập chỉ mục tài liệu thực hiện chức năng xây dựng bảng chỉ số
tài liệu hỗ trợ công việc tìm kiếm. Thông thường, các hệ thống tìm kiếm thông tin
thực hiện việc tìm kiếm các tài liệu hoặc dựa trên phương pháp lựa chọn tài liệu có
chứa các từ trong câu hỏi truy vấn, hoặc dựa trên phương pháp xếp hạng tài liệu
(Document Ranking) liên quan đến câu hỏi truy vấn. Do đó hầu hết các máy tìm
kiếm đều sử dụng biến dữ liệu có cấu trúc chỉ mục ngược (inverted index) để hỗ
trợ thực hiện công việc này. Inverted index có cấu trúc giống như bảng mục lục ở
phần cuối của cuốn sách – tương ứng với mỗi một từ là một danh sách liên kết
chứa địa chỉ các trang trong đó nó xuất hiện (hình 2-3). Với kiểu lưu trữ này nó có
khả năng giúp máy tìm kiếm xác định đúng các tài liệu liên quan đến câu hỏi truy
vấn một cách nhanh chóng.
Hình 2-3. Cấu trúc dữ liệu inverted index
Lưu trữ tài liệu (Document Cache)
Hiện nay có nhiều máy tìm kiếm vừa lưu trữ bảng chỉ số tài liệu như ở phần
trên, vừa lưu trữ tài liệu gốc. Ví dụ như trong Google, bảng chỉ số tài liệu gốc được
sử dụng để tạo các snippet và phục vụ cho việc lưu trữ các phiên bản của tài liệu.
Tính hạng tài liệu (Document Ranking)
World Wide Web càng ngày càng phát triển do vậy lượng thông tin ngày càng
lớn, số kết quả tìm kiếm với một từ khóa bất kỳ đều rất lớn, ngay cả với những câu
hỏi truy vấn hoàn thiện và chính xác, số kết quả tìm kiếm vẫn có thể lên đến hàng
ngàn hoặc hàng triệu. Chính vì vậy cần có module tính hạng tài liệu để xác định
được tài liệu nào có độ liên quan đến các từ khóa mà người dùng tìm kiếm nhất.
Xử lí truy vấn
Xử lí truy vấn là thành phần có nhiệm vụ phân tích cú pháp tìm kiếm của
người dùng thông qua các toán tử và cú pháp được định nghĩa sẵn, sau đó bộ xử lí
truy vấn kết hợp với bảng chỉ số tài liệu, các tài liệu được lưu trữ, và thành phần
tính hạng tài liệu để đưa ra tập kết quả tìm kiếm thỏa mãn cú pháp tìm kiếm của
người dùng. Kết quả của quá trình này được đưa đến người sử dụng thông qua giao
diện biểu diễn kết quả của máy tìm kiếm.
Giao diện biểu diễn kết quả
Giao diện biểu diễn kết quả tìm kiếm là thành phần quan trọng trong máy
tìm kiếm và trực tiếp tương tác với người sử dụng. Do vậy giao diện biểu diễn kết
quả tìm kiếm là yếu tố đầu tiên được xem xét khi đánh giá chất lượng của một
chương trình tìm kiếm, nó có vai trò vô cùng quan trọng và có ảnh hưởng rất lớn
đến toàn bộ chất lượng của máy tìm kiếm. Google được yêu thích và được đa số
người dùng sử dụng khi tìm kiếm thông tin là nhờ có một giao diện đơn giản
nhưng lại dễ sử dụng.
2.3.
Biểu diễn kết quả tìm kiếm
Giao diện của máy tìm kiếm đóng vai trò vô cùng quan trọng trong việc tìm
kiếm thông tin của người dùng, giao diện tìm kiếm được thiết kế tốt sẽ giúp người
dùng nhanh chóng tìm được kết quả tìm kiếm mình mong muốn.
Hầu hết các máy tìm kiếm hiện nay đều thực hiện việc tìm kiếm dựa trên
phương pháp tính hạng tài liệu và biểu diễn kết quả tìm kiếm theo thứ tự hạng xuất
hiện. Tuy nhiên hiện nay WWW đang phát triển với tốc độ rất nhanh, lượng thông
tin trên mạng ngày càng lớn vì thế số lượng kết quả tìm kiếm có thể lên đến hàng
ngàn tài liệu, nên người sử dụng không đủ thời gian và kiên nhẫn đọc toàn bộ
lượng tài liệu này để xác định các tài liệu cần thiết. Do vậy cách biểu diễn này có
nhiều hạn chế.
Thực tế cho thấy khi tìm kiếm thông tin, nếu biết được tài liệu mình tìm
kiếm thuộc chủ đề nào thì người sử dụng sẽ nhanh chóng tiếp cận được với tài liệu
cần tìm. Chính vì vậy để nâng cao hiệu quả trong việc tìm kiếm, ta nên biểu diễn
kết quả tìm kiếm Web theo nhóm chủ đề vì nó có những ưu điểm sau:
Tên chủ đề giúp người sử dụng phát hiện được các chủ đề chính của tập
kết quả trả về và do đó có thể xác định nhanh chóng tài liệu cần tìm.
Phân chia tập kết quả theo chủ đề còn giúp người sử dụng có thể nghiên
cứu thêm các tài liệu liên quan đến những chủ đề khác mà nó thường bị
bỏ qua khi duyệt kết quả tìm kiếm theo thứ tự hạng xuất hiện, vì những
kết quả này thường nằm ở các trang sau và thường bị người dùng bỏ
qua.
Khi người dùng tìm kiếm, tập kết quả phụ thuộc vào câu hỏi truy vấn mà
người dùng đưa ra, do đó không thể biết trước bất kỳ thông tin nào về các chủ đề
chứa trong tập kết quả này. Đây là một trong những khó khăn lớn để xây dựng các
công cụ tìm kiếm web theo chủ đề. Để giải quyết vấn đề này một trong các giải
pháp được đề xuất là sử dụng phương pháp phân cụm tài liệu. Phân cụm tài liệu
thực hiện nhóm các kết quả tìm kiếm theo chủ đề và tạo ra mô tả nội dung của mỗi
nhóm; người sử dụng chỉ cần quan sát tóm tắt nội dung các nhóm là dễ dàng định
vị được vùng tài liệu mà mình quan tâm.
2.4. Đánh giá chất lượng tìm kiếm
Để đánh giá chất lượng tìm kiếm của một máy tìm kiếm, hai độ đo chuẩn
thường được sử dụng để đánh giá là độ chính xác (precision) và độ hồi cứu (recall).
Giả sử, ta có tập các câu truy vấn Q, tập các văn bản D, với mỗi câu truy vấn
q Q ta có:
+ Tập các văn bản trả về Rq D
+ Tập các văn bản liên quan Dq (được chọn thủ công từ toàn bộ tập văn bản
D), Dq D
Độ chính xác (precision) được định nghĩa là tỉ lệ giữa các văn bản liên quan
được trả về với mọi văn bản trả về.
precision
Dq Rq
Rq
Độ chính xác biến thiên từ 0 đến 1, trường hợp xấu nhất nếu độ chính xác là 0
có nghĩa là không có văn bản liên quan nào được trả về, trường hợp tốt nhất nếu độ
chính xác là 1 nghĩa là toàn bộ văn bản được trả về đều là các văn bản liên quan.
Đây là trạng thái lý tưởng mà một hệ thống tìm kiếm cần đạt được, tuy nhiên có
thể vẫn còn các văn bản liên quan mà không được trả về.
Độ hồi cứu (recall) là độ đo biểu diễn tỉ lệ giữa các văn bản liên quan được trả
về với mọi văn bản liên quan.
recall
Dq Rq
Dq
Trường hợp lý tưởng là recall = 1, tức là mọi văn bản liên quan đều được trả
về, còn trường hợp xấu nhất là recall = 0, tức là không có văn bản liên quan nào
được trả về.
Độ độ chính xác và độ hồi cứu quyết định mối quan hệ giữa hai tập văn bản:
tập văn bản liên quan (Dq) và tập văn bản trả về (Rq). Trong trường hợp lý tưởng
thì độ chính xác và độ hồi cứu đều bằng 1 (tuy nhiên điều này không bao giờ xảy
ra trong các hệ thống thực tế).
Chương 3:
PHÂN CỤM TÀI LIỆU VÀ VẤN ĐỀ TÁCH TỪ TIẾNG VIỆT
3.1.
Phân cụm
3.1.1. Khái niệm
Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm,
phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn được quan tâm trong tập dữ
liệu lớn, từ đó cung cấp các thông tin hữu ích hỗ trợ cho việc ra quyết định.
Kỹ thuật phân cụm đã được áp dụng thành công trong các ứng dụng thuộc
lĩnh vực khai phá dữ liệu, thống kê hay lưu trữ thông tin.
Giả sử ta có tập các đối tượng D={d1,d2,…,dn} và (di; dj) là độ tương tự
giữa hai đối tượng di và dj. Phân cụm là quá trình chia tập đối tượng D vào K cụm
C={c1,c2,…,ck} sao cho mỗi đối tượng đều thuộc về một cụm, các đối tượng trong
cùng một cụm thì tương tự nhau, các phần tử thuộc các cụm khác nhau thì không
tương tự nhau. Như vậy thực chất của phân cụm dữ liệu là quá trình phân chia một
tập dữ liệu ban đầu thành các cụm riêng biệt sao cho các phần tử trong một cụm là
tương tự nhau và các phần tử thuộc các cụm khác nhau sẽ không tương tự với
nhau.
Với đặc điểm trên, khi phân cụm số lượng phần tử của các cụm có thể khác
nhau. Số các cụm dữ liệu có thể được xác định trước hay tự động xác định trong
quá trình phân cụm.
- Xem thêm -