MỞ ĐẦU 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. Chúng ta đều biết, khối lượng thông tin trên Web khổng lồ, 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à rất khó và đôi lúc là không thể. Một trong những cách tiếp cận để giải quyết vấn đề này là sử dụng kĩ thuật phân cụm tài liệu 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.
Trong luận văn này tôi xin mạnh dạn đề xuất giải thuật Phân cụm kết quả tìm kiếm Web theo cách tiếp cận phân tích ngữ nghĩa tiềm ẩn (Latent Semantic Analysis) và Fisher Kernel. Tư tưởng chính của giải thuật là, trước tiên phân tích ngữ nghĩa tiềm ẩn bên trong tập kết quả để tìm ra các khái niệm bao hàm trong đó, sau đó phân cụm tập kết quả theo tư tưởng giải thuật phân cụm K-means sử dụng hàm độ đo tương tự Fisher Kernel để nhóm các kết quả theo khái niệm chúng mô tả. Giải thuật được cài đặt trên mô hình Carrot2. Mặc dù bản thân đã nổ lực cố gắng, được sự tạo điều kiện nghiên cứu rất tốt của trường ĐH Công nghệ và sự hướng dẫn của thầy giáo Vũ Đức Thi, nhưng đề tài không tránh khỏi những thiếu sót, rất mong nhận được sự cộng tác của các chuyên gia, bạn bè và đồng nghiệp.
6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1 - GIỚI THIỆU TỔNG QUAN 1.1 Động lực Ngày nay, cùng với sự bùng nổ thông tin và sự phát triển của mạng truyền thông, Word Wide Web trở thành nguồn tài nguyên thông tin khổng lồ và quý giá, luôn sẵn sàng phục vụ tất cả mọi người. Nếu không có nó mọi hoạt động diễn ra hàng ngày sẽ kém hiệu quả. Nhưng làm thế nào sử dụng nguồn tài nguyên ấy hiệu quả là vấn đề không đơn giản. Điều này phụ thuộc vào nhiều yếu tố như kinh nghiệm tìm kiếm, kiến thức cơ bản liên quan đến lĩnh vực cần nghiên cứu, hoặc là sự thành thạo về ngôn ngữ v.v… Mặc dù hiện nay đã có rất nhiều máy tìm kiếm như Google1, Altavista2, HotBot3, Lycos4, AllTheWeb5, v.v…giúp chúng ta rất nhiều trong việc tìm kiếm thông tin.
Song hầu hết các máy này đều thực hiện việc tìm kiếm dựa trên phương pháp tính hạng liên quan (Document Ranking) và biểu diễn kết quả tìm kiếm theo thứ tự hạng xuất hiện. Tuy nhiên phương pháp này được đánh giá là không hiệu quả vì một vài nguyên nhân sau đây: WWW là một kho dữ liệu khổng lồ và luôn được cập nhật thay đổi do tính động của các trang Web, nên máy tìm kiếm chỉ có thể xây dựng được một phần bảng chỉ số tài liệu 6, do vậy không thể thực hiện tính hạng được cho tất cả các tài liệu. Người sử dụng đặt câu hỏi truy vấn quá ngắn không đủ để thể hiện được mục đích của họ. Khi đó kết quả tìm kiếm là chung chung và có thể lên đến hàng trăm hoặc hàng ngàn kết quả.
Theo thống kê cho 1 http://www.com 2 http://www.com 3 http://www.com 4 http://www.com 5 http://www.com 6 Theo thông tin Google năm 2001 bảng chỉ số có 1.35 tỷ trang, năm 2003 có trên 3.08 tỷ trang 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com biết không quá một nữa số người sử dụng duyệt quá trang thứ hai và chỉ có 3/4 người sử dụng duyệt hết 2 trang. Vậy đa số người sử dụng duyệt tối đa 10-30 kết quả (mặc định hiển thị 10 – 20 kết quả trên một trang), do đó bỏ qua một số kết quả tìm kiếm cần thiết nhất. Đa số người sử dụng gặp khó khăn trong việc đặt câu hỏi truy vấn nên câu hỏi thường không đúng như mong muốn. Sở dĩ như vậy là vì khi có ý định tìm thông tin trên WWW, thì trong suy nghĩ của họ cũng hình thành khái niệm về cái họ cần tìm.
Sau đó khái niệm này được chuyển thành một tập các từ và được sử dụng để đặt câu hỏi truy vấn. Tuy nhiên tính chính xác của việc chuyển đổi khái niệm thành tập các từ lại phụ thuộc vào nhiều nhân tố, chẳng hạn như kinh nghiệm tìm kiếm, kiến thức cơ bản liên quan đến khái niệm đó, hoặc là sự thành thạo về ngôn ngữ. Điều này tạo nên sự bất cân xứng giữa khái niệm và câu hỏi truy vấn. Máy tìm kiếm lại chỉ có thể tìm kiếm và sắp xếp kết quả theo các từ khóa trong câu hỏi truy vấn, nên thứ tự hạng xuất hiện của các kết quả không đúng như mong muốn người sử dụng.1 Sự mất cân xứng giữa ý tưởng và câu hỏi truy vấn của người sử dụng 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Hơn nữa, phương pháp tính hạng yêu cầu quá khắt khe về mức độ liên quan giữa kết quả tìm kiếm với câu hỏi truy vấn và giả định rằng các kết quả luôn so sánh được với nhau.
Tuy nhiên điều này là không đúng, vì đối với các câu hỏi truy vấn chung chung có những kết quả chỉ là chủ đề con nên việc so sánh giữa các kết quả không cân xứng. Ví dụ, đối với câu hỏi truy vấn “jaguar”, kết quả trả về có thể bao gồm những từ về jaguar cars, jaguar as a cat, Mac OS X Jaguar.v… Ngoài ra phương thức này dễ bị Spam lợi dụng để đưa những trang Web xấu lên đầu. Do đó yêu cầu 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à cần thiết. Nó đang là một trong những vấn đề được nhiều nhà nghiên cứu quan tâm.
Mặc dù gần đây đã có nhiều giải thuật được đưa ra, nhưng tôi vẫn mạnh dạn đề xuất giải thuật Phân cụm kết quả tìm kiếm Web theo cách tiếp cận LSA và Fisher Kernel, viết tắt là LSA-FK, với hy vọng đóng góp được một giải thuật phân cụm tốt xử lí được vấn đề từ đồng nghĩa và từ đa nghĩa trong ngôn ngữ tự nhiên với mức độ nhất định.2 Phạm vi công việc Để đạt được mục đích trên, tôi sẽ phải thực hiện những công việc sau: Tìm hiểu hướng nghiên cứu hiện tại đối với bài toán tìm kiếm thông tin, đặc biệt tập trung vào khai phá nội dung trang Web và tối ưu kết quả trả về; Vận dụng lí thuyết đại số tuyến tính và kĩ thuật phân tích ma trận để rút gọn số chiều của vectơ biểu diễn nội dung tài liệu, từ đó xây 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com dựng cách biểu diễn tài liệu theo các khái niệm ngữ nghĩa ẩn bên trong tập tài liệu; Vận dụng lí thuyết xác suất, thống kê toán học và Kernel Method để xây dựng hàm Fisher Kernel đo độ tương tự giữa các tài liệu. Cài đặt giải thuật LSA-FK trên nền Carrot2; Đánh giá giải thuật đề ra. Các vấn đề trên thuộc vào lĩnh vực khai phá Web – lĩnh vực riêng của khai thác và tìm kiếm thông tin. Trong đó khai phá Web tiếp tục được phân thành một số lĩnh vực sau: + Khai phá sử dụng Web, phân tích mẫu truy cập và phân tích xu hướng cá nhân.
+ Khai phá kết hợp cấu trúc Web, tập trung vào vấn đề phân tích các cấu trúc liên kết của Web. + Cuối cùng khai phá nội dung Web, nghiên cứu các vấn đề tìm kiếm thông tin từ Internet. Luận văn của tôi thuộc vào lĩnh vực sau cùng này. KHAI PHÁ WEB Khai phá nội dung Khai phá cấu trúc Khai phá sử dụng Web Web Web Khai phá nội dung Tối ưu kết Khai phá các Phân tích các xu trang Web quả trả về mẫu truy nhập hướng cá nhân Hình 1.2 Khai phá Web 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Cấu trúc luận văn Các phần còn lại của luận văn được tổ chức như sau: Chương 2 tóm tắt ngắn gọn về máy tìm kiếm Web.
Đồng thời khảo sát các cách tiếp cận biểu diễn kết quả tìm kiếm Web, trong đó đặc biệt chú ý cách biểu diễn theo chủ đề. Phần tiếp của chương này tôi trình bày về các kỹ thuật phân cụm và xử lí văn bản liên quan. Chương 3 giới thiệu các khái niệm sử dụng trong giải thuật phân cụm kết quả tìm kiếm Web. Đầu tiên, trình bày hai mô hình Không gian vectơ và Phân tích ngữ nghĩa tiềm ẩn (Latent Semantic Analysis - LSA) được sử dụng nhiều trong bài toán tìm kiếm thông tin.
Sau cùng, trình bày về Fisher Kernel. Chương 4 trình bày chi tiết về giải thuật phân cụm LSA-FK và cho ví dụ minh hoạ cần thiết. Tóm tắt mô hình Carrot2 cài đặt giải thuật LSA-FK. Chương 5 trình bày các phương pháp đánh giá kết quả thực nghiệm, sau đó thực hiện đánh giá giải thuật LSA-FK.
11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 2 - VẤN ĐỀ TÌM KIẾM WEB VÀ PHÂN CỤM TÀI LIỆU 2.1 Máy tìm kiếm Web Máy tìm kiếm Web là một loại chương trình tiện ích hỗ trợ nhằm giúp người sử dụng tìm kiếm thông tin một cách nhanh chóng và đầy đủ. Giao diện tương tác giữa người và máy 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, sau đó lập tức máy trả về tập kết quả tìm kiếm (snippets). Mỗi snippet bao gồm tựa đề, địa chỉ web của tài liệu (được gọi là URL7) và miêu tả ngắn gọn nội dung chính tài liệu Web.1 Cấu trúc bên trong Hình 2.1 Cấu trúc bên trong của của máy tìm kiếm Web Web Crawler Web Crawler là một trong hai thành phần tương tác trực tiếp với Internet, còn được gọi là Web Spider hoặc Robot.
Công việc chính của Web Crawler phát hiện những nguồn tài nguyên mới trên Web. Để thực hiện công 7 URL – Uniform Resource Locator 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com việc này, Web Crawler tìm kiếm đệ quy trên các đường link của tất cả các trang đã được duyệt. Đồng thời, trong khi khai phá các nguồn tài nguyên mới trên Internet, Web Crawler kiểm tra liệu rằng các trang có còn giá trị sử dụng hay không và liệu chúng đã được cập nhật hay chưa. Với chức năng này nó giúp cho máy tìm kiếm cập nhật được nguồn tài nguyên mới và xóa bỏ tài nguyên không còn giá trị sử dụng trong World Wide Web.
Chỉ số tài liệu (Document Index) Modul lập chỉ số 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.