Tài liệu Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM 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Ệ Nguyễn Thị Thu Hằng PHƯƠNG PHÁP PHÂN CỤM TÀI LIỆU WEB VÀ ÁP DỤNG VÀO MÁY TÌM KIẾM 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: PGS.TS HÀ QUANG THỤY Hà Nội - 2007 Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. Những lời đầu tiên Với những dòng chữ đầu tiên này, tôi xin dành để gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy giáo, tiến sỹ Hà Quang Thụy - người đã tận tình hướng dẫn, chỉ bảo và tạo cho tôi những điều kiện tốt nhất từ khi bắt đầu cho tới khi hoàn thành công việc của mình. Đồng thời xin cảm ơn tất cả những người thân yêu trong gia đình tôi cùng toàn thể bạn bè, những người đã luôn giúp đỡ và động viên tôi mỗi khi vấp phải những khó khăn, bế tắc. Cuối cùng, xin chân thành cảm ơn đồng nghiệp của tôi tại Trung tâm CNTT, NHNo&PTNT VN những người đã đem đến cho tôi những lời khuyên vô cùng bổ ích để giúp tháo gỡ những khó khăn, vướng mắc trong quá trình làm luận văn. -1- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân, không sao chép lại của người khác. Trong toàn bộ nội dung của luận văn, những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 01 tháng 11 năm 2007 Nguyễn Thị Thu Hằng -2- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. MỤC LỤC DANH MỤC CHỮ VIẾT TẮT ........................................................................................ 5 DANH MỤC HÌNH VẼ, BẢNG BIỂU ............................................................................ 6 MỞ ĐẦU .......................................................................................................................... 7 CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB ................................... 9 1.1. Khai phá dữ liệu Web ....................................................................................... 9 1.1.1. Giới thiệu về Khai phá dữ liệu .................................................................. 9 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin ........................................... 11 1.1.3. Đặc điểm của dữ liệu Web ...................................................................... 12 1.1.4. Các hướng tiếp cận khai phá dữ liệu Web .............................................. 13 1.1.5. Nhu cầu Phân cụm tài liệu Web.............................................................. 14 1.2. Mô hình tìm kiếm thông tin ............................................................................ 15 1.2.1. Giới thiệu ................................................................................................ 15 1.2.2. Quy trình tìm kiếm thông tin trong hệ thống .......................................... 15 1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm ........................................... 18 1.3. Kết luận chương 1 ........................................................................................... 19 CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB ................................................... 20 2.1. Một số nội dung cơ bản về thuật toán phân cụm tài liệu ................................ 20 2.2. Tiêu chuẩn đánh giá thuật toán phân cụm ...................................................... 22 2.3. Các đặc tính của các thuật toán phân cụm web .............................................. 24 2.3.1. Mô hình dữ liệu....................................................................................... 24 2.3.2. Độ đo về sự tương tự .............................................................................. 27 2.3.3. Mô hình phân cụm .................................................................................. 29 2.4. Một số kỹ thuật Phân cụm Web điển hình ...................................................... 30 2.4.1. Phân cụm theo thứ bậc ............................................................................ 30 2.4.2. Phân cụm bằng cách phân mảnh ............................................................. 33 2.5. Các yêu cầu đối với các thuật toán phân cụm Web ........................................ 35 2.5.1. Tách các thông tin đặc trưng................................................................... 35 2.5.2. Phân cụm chồng lặp ................................................................................ 36 2.5.3. Hiệu suất ................................................................................................. 36 2.5.4. Khả năng khử nhiễu ................................................................................ 36 2.5.5. Tính tăng ................................................................................................. 37 2.5.6. Việc biểu diễn kết quả ............................................................................ 37 2.6. Bài toán tách từ tự động tiếng Việt ................................................................. 37 2.6.1. Một số khó khăn trong phân cụm trang Web tiếng Việt ......................... 37 2.6.2. Tiếng và Từ trong tiếng Việt .................................................................. 39 2.6.3. Phương pháp tách từ tự động tiếng Việt fnTBL ..................................... 39 2.6.4. Phương pháp Longest Matching ............................................................. 43 2.6.5. Kết hợp giữa fnTBL và Longest Matching ............................................. 44 2.7. Kết luận chương 2 ........................................................................................... 44 CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐ VÀ THUẬT TOÁN CÂY PHÂN CỤM TÀI LIỆU ........................................................................................ 45 3.1. Giới thiệu về thuật toán phân cụm trang Web có tính tăng ............................ 45 3.2. Thuật toán phân cụm cây hậu tố ..................................................................... 46 3.2.1. Mô tả ....................................................................................................... 46 3.2.2. Thuật toán STC ....................................................................................... 47 -3- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. 3.3. Thuật toán phân cụm sử dụng cây phân cụm tài liệu ...................................... 51 3.3.1. Giới thiệu ................................................................................................ 51 3.3.2. Trích chọn đặc trưng và phân cụm tài liệu ............................................. 51 3.3.3. Cây phân cụm tài liệu –DC Tree ............................................................ 55 3.4. Kết luận chương 3 ........................................................................................... 60 CHƯƠNG 4 - PHẦN MỀM THỬ NGHIỆM VÀ KẾT QUẢ THỰC NGHIỆM ...... 61 4.1. Giới thiệu ........................................................................................................ 61 4.2. Thiết kế cơ sở dữ liệu ..................................................................................... 62 4.3. Chương trình thử nghiệm ................................................................................ 65 4.4. Kết quả thực nghiệm ....................................................................................... 66 4.5. Kết luận chương 4 ........................................................................................... 69 -4- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. DANH MỤC CHỮ VIẾT TẮT AHC: Phân cụm tích tụ theo thứ bậc (Agglomerative Hierarchical Clustering) CSDL: Cơ sở dữ liệu DF: tần suất xuất hiện tài liệu (Document Frequency) DC-tree: Cây phân cụm tài liệu (Document Clustering Tree) fnTBL: Học dựa trên sự biến đổi (Fast Transformation-based learning) FCM: Fuzzy C-means FCMdd: Fuzzy C-Medoids 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) UPGMA: (Unweighter Pair-Group Method using Arithmetic averages) -5- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. DANH MỤC HÌNH VẼ, BẢNG BIỂU -6- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. MỞ ĐẦU World Wide Web là một kho thông tin khổng lồ với tiềm năng được coi là không có giới hạn. Khai phá Web là vấn đề nghiên cứu thời sự trong thời gian gần đây, đã thu hút nhiều nhóm nhà khoa học trên thế giới tiến hành nghiên cứu, đề xuất các mô hình, phương pháp mới nhằm tạo ra các công cụ hiệu quả hỗ trợ người dùng trong việc tổng hợp thông tin và tìm kiếm tri thức từ tập hợp các trang Web khổng lồ trên Internet. Phân cụm tài liệu Web là một bài toán điển hình trong khai phá Web, nhằm phân hoạch tập văn bản thành các tập con có tính chất chung, trong đó bài toán phân cụm các trang Web là kết quả trả về từ máy tìm kiếm là rất hữu dụng [4-6, 8-15, 18, 19, 22, 24]. Như đã biết, tập hợp các trang Web đáp ứng một câu hỏi trả về từ máy tìm kiếm nói chung là rất lớn, vì vậy, thuật toán phân cụm văn bản ở đây cần có được một tính chất rất quan trọng là tính "tăng" theo nghĩa thuật toán phân cụm không phải thực hiện chỉ trên toàn bộ tập dữ liệu mà có thể được thực hiện theo cách từ bộ phận dữ liệu tới toàn bộ dữ liệu [4, 6, 11, 14, 15, 24]. Điều đó cho phép thuật toán tiến hành ngay trong giai đoạn máy tìm kiếm đưa các trang web kết quả về. Luận văn tập trung khảo sát các phương pháp phân cụm trong Web có tính chất tăng và thực hiện một số thử nghiệm tích hợp các kết quả nghiên cứu nói trên vào một phần mềm tải trang Web theo dạng máy tìm kiếm. Đồng thời, luận văn triển khai một số bước đầu tiên trong việc áp dụng phân cụm cho các trang Web tiếng Việt. Luận văn xây dựng một phần mềm thử nghiệm và tiến hành các thử nghiệm phân cụm Web tiếng Việt. Ngoài Phần Mở đầu, Phần Kết luận và các Phụ lục, nội dung luận văn được chia thành 4 chương chính: Chương 1 – Khái quát về khai phá dữ liệu Web. Chương này giới thiệu những nội dung cơ bản nhất, cung cấp một cái nhìn khái quát về Khai phá dữ liệu Web. Đồng thời, luận văn cũng mô tả sơ bộ một hệ thống thông tin tìm kiếm và nhu cầu phân cụm áp dụng cho hệ thống này. -7- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. Chương 2 – Thuật toán phân cụm Web. Chương này trình bày một cách khái quát về các thuật toán phân cụm Web, những đặc trưng và yêu cầu đối với các thuật toán phân cụm Web. Những yêu cầu và độ đo áp dụng cho các thuật toán phân cụm Web cũng được trình bày trong chương này. Một số kiến thức cơ bản về tiếng Việt cũng được giới thiệu ở đây. Chương 3 – Thuật toán phân cụm cây hậu tố và thuật toán cây phân cụm tài liệu. Chương này đi sâu vào phân tích các thuật toán phân cụm Web có tính chất tăng. Luận văn tập trung vào hai thuật toán phân cụm Web có tính “tăng” là thuật toán STC và thuật toán phân cụm có sử dụng cấu trúc cây DC (DC-tree). Chương 4 – Phần mềm thử nghiệm và kết quả thực nghiệm. Chương này trình bày kết quả thực nghiệm phân cụm Web theo phần mềm thử nghiệm trên cơ sở thuật toán phân cụm DC-tree. Chương trình cài đặt thử nghiệm được viết trên ngôn ngữ lập trình C# trên nền tảng .Net Framework của Microsoft sử dụng SQL Server 2000 để lưu trữ cơ sở dữ liệu. Phần mềm đã hoạt động, cho kết quả phân cụm, tuy nhiên, do thời gian hạn chế nên luận văn chưa tiến hành đánh giá kết quả phân cụm một cách chính thống. Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và phương hướng nghiên cứu tiếp theo về các nội dung của luận văn. Luận văn đã đạt một số kết quả khả quan bước đầu trong việc nghiên cứu và triển khai các thuật toán phân cụm Web có tính chất tăng, tuy nhiên, luận văn không tránh khỏi những sai sót. Rất mong được sự đóng góp ý kiến, nhận xét để tác giả có thể hoàn thiện được kết quả nghiên cứu. -8- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. CHƯƠNG 1 - KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU WEB 1.1. Khai phá dữ liệu Web 1.1.1. Giới thiệu về Khai phá dữ liệu Khái niệm Khai phá dữ liệu (Data Mining) Khai phá dữ liệu được định nghĩa như một quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu. 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ô. Có sự phân biệt giữa khái niệm "Khai phá dữ liệu" với khái niệm "Phát hiện tri thức" (Knowledge Discovery in Databases - KDD) mà theo đó, khai phá dữ liệu chỉ là một bước trong quá trình KDD. Quá trình KDD gồm một số bước sau: • Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết • Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau tích hợp lại • Lựa chọn dữ liệu: Các dữ liệu có liên quan đến quá trình phân tích được lựa chọn từ cơ sở dữ liệu • Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý • Khai phá dữ liệu: Là một trong những bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để lựa chọn ra những mẫu dữ liệu. • Ước lượng mẫu: Quá trình đánh giá kết quả thông qua một độ đo nào đó • Biểu diễn tri thức: Biểu diễn các kết quả một cách trực quan cho người dùng. -9- Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. Hình 1. Các bước trong KDD Các hướng tiếp cận và các kỹ thuật trong khai phá dữ liệu Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau: • Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. • Luật kết hợp (association rules): là dạng luật biểu diễn tri thứ ở dạng khá đơn giản. Ví dụ: “50% những người mua máy tính thì cũng mua máy in”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trường chứng khoán, .v.v. • Phân lớp và dự đoán (classification & prediction): xếp một đối tượng 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 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. - 10 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được sự quan tâm của rất nhiều 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 [7,16]: • 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. 1.1.2. Dữ liệu Web và nhu cầu khai thác thông tin 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 ngày 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ông 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 (bao gồm dữ liệu văn bản) đã đượ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à giá cả thấp cần 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" chi phí rẻ hơn rất nhiều mà lại được cập nhật nhanh chóng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thể nói không gian Web như là cuốn từ điển Bách khoa toàn thư. Thông tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Có thể nói Internet như một xã hội ảo, nó bao gồm các - 11 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. thông tin về mọi mặt của đời sống kinh tế, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh,... Tuy nhiên cùng với sự đa dạng và số lượng lớn thông tin như vậy đã nảy sinh vấn đề quá tải thông tin. Người ta không thể tìm tự 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. Các tiện ích này quản lý dữ liệu trang Web như các đối tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy, đó là Yahoo, Google, Alvista, ... Mặt khác, 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 hàng xem hoặc download về, sau khi phân lớp các yêu cầu như thế của khách hàng, chúng ta sẽ biết được khách hàng hay tập trung vào nội dung gì trên trang Web của chúng ta, mà 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. Ngược lai, về phía khách hàng, sau khi được phục vụ phù hợp yêu cầu, khách hàng sẽ hướng sự quan tâm tới hệ thống của chúng ta hơn. 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 thời sự và cần được phát triển nghiên cứu. Như vậy, chúng ta có thể hiểu rằng khai phá Web như là việc trích chọn ra các thành phần được quan tâm hay được đánh giá là có ích cùng các thông tin tiềm năng từ các tài nguyên hoặc các hoạt động liên quan tới World-Wide Web [25, 26]. Một cách trực quan có thể quan niệm khai phá Web là sự kết hợp giữa Khai phá dữ liệu, Xử lý ngôn ngữ tự nhiên và Công nghệ Web: Khai phá web = Khai phá dữ liệu + Xử lý ngôn ngữ tự nhiên + World Wide Web. 1.1.3. Đặc điểm của dữ liệu Web * Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ Khai phá dữ liệu. * Độ 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. - 12 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. * Web là một nguồn tài nguyên thông tin có độ thay đổi cao * Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng * Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích 1.1.4. Các hướng tiếp cận khai phá dữ liệu Web Như đã phân tích về đặc điểm và nội dung các siêu văn bản ở 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) 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 trang Web thoả mãn yêu cầu người dùng, còn một công việc không kém phần quan trọng, đó là phải sắp xếp kết quả theo thứ tự dộ gần nhau với nội dung cần tìm kiếm. Đây cũng chính là khai phá nội dung trang Web. 2. Web Structure Mining Khai phá dựa trên các siêu liên kết giữa các văn bản có liên quan. 3. Web Usage Mining a. General Access Partern Tracking: Phân tích các Web log để khám phá ra các mẫu truy cập của người dùng trong trang Web. b. Customize Usage Tracking: Phân tích các mẫu truy cập của người dùng tại mỗi thời điểm để biết xu hướng truy cập trang Web của từng đối tượng người dùng tại mỗi thời điểm khác nhau - 13 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. Luận văn này tập trung chủ yếu vào nội dung “khai phá phá nội dung trang Web” và định hướng vào phân cụm tập trang web là kết quả tìm kiếm của các máy tìm kiếm. 1.1.5. Nhu cầu phân cụm tài liệu Web Một trong những bài toán quan trọng trong lĩnh vực khai phá Web là bài toán phân cụm Web. Phân cụm Web - nói một cách khái quát - là việc tự động sinh ra các "cụm" (lớp) tài liệu dựa vào sự tương tự của các tài liệu. Các lớp tài liệu ở đây là chưa biết trước, người dùng có thể chỉ yêu cầu số lượng các lớp cần phân loại, hệ thống sẽ đưa ra các tài liệu theo từng tập hợp, từng cụm, mỗi tập hợp chứa các tài liệu tương tự nhau. Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các tài liệu được lấy từ Web. Có hai tình huống phân cụm tài liệu. Tình huống thứ nhất là việc phân cụm trên toàn bộ một CSDL có sẵn gồm rất nhiều tài liệu Web. Thuật toán phân cụm cần tiến hành việc phân cụm toàn bộ tập dữ liệu thuộc CSDL đó. Tình huống này thường được gọi là phân cụm không trực tuyến (offline). Tình huống thứ hai thường được áp dụng trên một tập tài liệu nhỏ là tập hợp các tài liệu do máy tìm kiếm trả về theo một truy vấn của người dùng. Trong trường hợp này, giải pháp phân cụm được tiến hành kiểu phân cụm trực tuyến (on-line) theo nghĩa việc phân cụm tiến hành theo từng bộ phận các tài liệu nhận được. Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân cụm ngay khi chưa có đủ tài liệu và phân cụm tiếp theo không cần phải tiến hành với dữ liệu đã được phân cụm trước đó. Do tập tài liệu trên Web là vô cùng lớn cho nên cách phân cụm trực tuyến là thích hợp hơn và phải đòi hỏi tính "gia tăng" của thuật toán phân cụm. Quá trình xử lý truy vấn và kết quả phân hạng được phản hồi từ các máy tìm kiếm phụ thuộc vào việc tính toán độ tương tự giữa truy vấn và các tài liệu. Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhưng nó thường quá ngắn và dễ xảy ra sự nhập nhằng. Như đã biết, trung bình các truy vấn trên Web chỉ gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn, truy vấn star dẫn đến sự nhập nhằng rất cao, các tài liệu lấy được liên quan đến astronomy, plants, animals, popular media and sports figures… Độ tương tự giữa các tài liệu của một truy từ đơn như vậy là có sự khác nhau rất lớn. Vì lẽ đó, - 14 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. nếu máy tìm kiếm phân cụm các kết quả theo từng chủ đề thì người dùng có thể nhanh chóng hiểu kết quả truy vấn hoặc tìm vào một chủ đề xác định. 1.2. Mô hình tìm kiếm thông tin 1.2.1. Giới thiệu Với sự phát triển nhanh chóng của công nghệ tin học, khối lượng thông tin lưu trữ trên máy tính ngày càng nhiều, vì vậy cần có các hệ thống tìm kiếm thông tin (IR: Information Retrieval) cho phép người dùng tìm kiếm một cách chính xác và nhanh nhất các thông tin mà họ cần trên kho dữ liệu khổng lồ này, trong đó, Internet chính là một kho dữ liệu như thế. Mục tiêu của hệ thống tìm kiếm là cung cấp công cụ để trả về cho người dùng các tài liệu trong kho dữ liệu có liên quan tới câu truy vấn [3,23,25,26]. Đó là nhu cầu chung của hầu hết các ngôn ngữ và tiếng Việt của chúng ta cũng phải là một ngoại lệ. Khác với các ngôn ngữ khác, tiếng Việt có nhiều đặc điểm riêng biệt và rất khó xử lý bằng máy tính, nên các đề tài liên quan đến các hệ thống tìm kiếm tiếng Việt còn rất ít. Mà nhu cầu tìm kiếm tài liệu trên kho tàng kiến thức của người Việt là rất lớn. 1.2.2. Quy trình tìm kiếm thông tin trong hệ thống Quy trình của một hệ thống tìm kiếm thông tin như sau [3,23,26]: • Người dùng muốn xem những tài liệu liên quan tới một chủ đề nào đó. • Người dùng cung cấp một mô tả về chủ đề đó dưới dạng câu truy vấn • Từ câu truy vấn này hệ thống sẽ lọc ra những cụm từ chỉ mục • Những cụm từ chỉ mục này sẽ được so khớp với những cụm từ chỉ mục của các tài liệu đã được xử lý trước đó. • Những tài liệu nào có mức độ liên quan cao nhất sẽ được trả về cho người sử dụng. Mục đích của hệ thống tìm kiếm thông tin là tìm kiếm và hiển thị cho người dùng một tập các thông tin thoả mãn nhu cầu của họ. Chúng ta định nghĩa - 15 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. chính xác cho thông tin cần thiết là “câu truy vấn” (query), và các thông tin được chọn là “tài liệu” (documents). Mỗi cách tiếp cận trong IR bao gồm hai thành phần chính (1) các kỹ thuật để biểu diễn thông tin (câu truy vấn, tài liệu), và (2) phương pháp so sánh các cách biểu diễn này. Mục đích là để tự động quy trình kiểm tra các tài liệu bằng cách tính toán độ tương quan giữa các câu truy vấn và tài liệu. Quy trình này được đánh giá là thành công khi nó trả về các kết quả giống với các kết quả được con người tạo ra khi so sánh câu truy vấn với các tài liệu. Có một vấn đề thường xảy ra đối với hệ thống tìm kiếm là những từ mà người dùng đưa ra trong câu truy vấn thường khác xa những từ trong tập tài liệu chứa thông tin mà họ tìm kiếm. Trường hợp như thế gọi là “paraphrase problem” (vấn đề về diễn giải). Để giải quyết vấn đề này, hệ thống đã tạo ra các hàm biểu diễn xử lý các câu truy vấn và các tài liệu một cách khác nhau để đạt tới một độ tương thích nào đó. Hình 2. Mô hình hệ thống tìm kiếm thông tin Gọi miền xác định của hàm biểu diễn câu truy vấn q là Q, tập hợp các câu truy vấn có thể có; và miền giá trị của nó là R, không gian thống nhất biểu diễn - 16 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. thông tin. Gọi miền xác định của hàm biểu diễn tài liệu d là D, tập hợp các tài liệu; và miền giá trị của nó là R2. Miền xác định của hàm so sánh c là R × R và miền giá trị của nó là [0,1] là tập các số thực từ 0 đến 1. Trong một hệ thống tìm kiếm lí tưởng: c(q(query),d(doc)) = j(query,doc), ∀ query ∈ Q, ∀ doc ∈ D, khi j: Q × D → [0,1] biểu diễn việc xử lý của người dùng giữa các mối quan hệ của 2 thông tin, được tính dựa trên một tiêu chuẩn nào đó(ví dụ: sự giống nhau về nội dung hay sự giống nhau về kiểu,...). Hình 2 minh hoạ mối quan hệ này. Có hai kiểu hệ thống tìm kiếm: tìm kiếm dựa trên so khớp chính xác và dựa trên sắp xếp. Mô hình trên đây có thể mô tả cả hai cách tiếp cận như thế. Trong hệ thống tìm kiếm dựa trên so khớp chính xác, miền giá trị của c được giới hạn hai lựa chọn là 0 và 1, và nó được chuyển sang nhị phân để quyết định liệu 1 tài liệu có thoả biểu thức bool được xác định bởi câu truy vấn hay không? Các hệ IR dựa trên sự so khớp chính xác thường cung cấp các tài liệu không sắp xếp thoả mãn câu truy vấn của người sử dụng, hầu hết các hệ thống tìm kiếm hiện nay đều dùng cách này. Cách hoạt động chi tiết của hệ thống sẽ được mô tả ở phần sau. Đối với hệ thống IR dựa trên sắp xếp, thì các tài liệu sẽ được sắp xếp theo thứ tự giảm dần về mức độ liên quan. Có 3 loại hệ thống tìm kiếm dựa trên sắp xếp: “ranked Boolean”, “probabilistic” và “similarity base”. Trong 3 cách này thì miền giá trị của c là [0, 1], tuy nhiên chúng khác nhau ở cách tính “giá trị trạng thái tìm kiếm” (“retrieval status value”): • Trong hệ thống dựa trên “ranked Boolean” giá trị này là mức độ mà thông tin thoả mãn biểu thức Bool được chỉ ra bởi các thông tin còn lại. • Trong hệ thống dựa trên “probabilistic”, khái niệm này hơi khác một chút, giá trị này là xác suất mà thông tin có liên quan đến một câu truy vấn. Rất nhiều hệ thống tìm kiếm dựa trên xác suất được thiết kế để chấp nhận câu truy vấn được diễn tả bằng ngôn ngữ tự nhiên hơn là một biểu thức bool. • Trong hệ thống tìm kiếm dựa trên sự giống nhau, giá trị trạng thái tìm kiếm được tính bằng cách tính mức độ giống nhau của nội dung thông tin. Trong các hệ thống tìm kiếm dựa trên sự so khớp chính xác, việc đánh giá hệ thống chủ yếu dựa trên việc đánh giá mức độ liên quan. Giả sử j là giá trị nhị - 17 - Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007. phân và được cho trước. Nói cách khác, ta giả sử rằng các tài liệu hoặc có hoặc không có liên quan đến câu truy vấn, và độ liên quan giữa tài liệu và câu truy vấn do con người xác định là chính xác. Theo giả định này, tính hiệu quả của các hệ thống tìm kiếm dựa trên so khớp chính xác được đánh giá dựa trên hai đại lượng thống kê là “độ chính xác” ( precision) và “độ hồi tưởng” (recall). Độ chính xác là tỷ lệ các tài liệu được chọn, các tài liệu thực sự có liên quan đến các thông tin mà người dùng cần, độ hồi tưởng là tỉ lệ tài liệu có liên quan được sắp xếp chính xác theo độ liên quan bởi hệ thống tìm kiếm. Nói cách khác, độ chính xác bằng 1 trừ đi tỷ lệ cảnh báo sai, trong khi đó độ hồi tưởng đo mức độ hoàn chỉnh của việc tìm kiếm. Về hai độ đo đánh giá này cũng sẽ được đề cập chi tiết trong phần tiêu chuẩn đánh giá phân cụm cho thuật toán phân cụm ở phía sau. Việc đánh giá tính hiệu quả của hệ thống tìm kiếm dựa trên sắp xếp là phức tạp hơn. Một cách tính độ hiệu quả phổ biến cho các hệ thống này “độ chính xác trung bình”. Nó được tính bằng cách chọn 1 tập lớn hơn các tài liệu ở đầu danh sách có giá trị hồi tưởng giữa 0 và 1. Phương pháp thường được sử dụng là phương pháp tính dựa trên 5,7,11 điểm theo độ hồi tưởng. Độ chính xác sau đó sẽ tính cho từng tập một. Quy trình sẽ được lặp lại cho từng câu truy vấn, và tương ứng với mỗi độ chính xác trung bình sẽ cho một độ hồi tưởng. Mỗi giá trị trung bình của những số này sau đó sẽ được tính toán và ghi nhận như một đặc trưng của hệ thống. Độ chính xác trung bình càng lớn thì càng tốt, và việc so sánh chỉ thực sự có ý nghĩa khi chúng ta sử dụng cùng một tập tài liệu và câu truy vấn. Tuy nhiên độ chính xác trung bình cũng làm giảm đi mức độ thay đổi của các câu truy vấn có các đặc tính khác nhau (ví dụ như số lượng tài liệu có liên quan khác nhau). Hơn thế nữa, các tài liệu có liên quan thường tập trung ở đầu danh sách sắp xếp nên thông thường độ chính xác sẽ giảm mỗi khi tập tài liệu được mở rộng để tăng độ hồi tưởng. 1.2.3. Ứng dụng phân cụm vào hệ thống tìm kiếm Như vậy, với việc phân tích nhu cầu phân cụm đối với các tài liệu Web, khi ta xây dựng một hệ thống tìm kiếm thì đồng thời ta cũng sẽ tiến hành tích hợp module phân cụm vào hệ thống này. Việc phân cụm văn bản như một phương thức tổ chức các dữ liệu trả lại khác giúp người sử dụng thay vì phải xem xét chọn lọc danh sách dài các văn bản theo thứ tự để tìm kiếm các văn bản liên - 18 -