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.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2: MÁY TÌM KIẾM WEB 2. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. Đá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ề. Dq Rq precision 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. Dq Rq recall 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đượ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ế). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 3: PHÂN CỤM TÀI LIỆU VÀ VẤN ĐỀ TÁCH TỪ TIẾNG VIỆT 3. 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.