Khóa luận Xây dựng bộ ngữ liệu để đánh giá bằng Tiếng Việt và chương trình trợ giúp đánh giá hệ tìm kiếm thông tin

SV ne t.vn TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CƠNG NGHỆ THƠNG TIN BỘ MƠN HỆ THỐNG THƠNG TIN TSÀN QUẾ HƯƠNG – 0112385 VÕ HỒ BẢO KHANH – 0112387 XÂY DỰNG BỘ NGỮ LIỆU ĐỂ ĐÁNH GIÁ BẰNG TIẾNG VIỆT VÀ CHƯƠNG TRÌNH TRỢ GIÚP ĐÁNH GIÁ CÁC HỆ TÌM KIẾM THƠNG TIN KHĨA LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN T.S HỒ BẢO QUỐC NIÊN KHĨA 2001 - 2005 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 2 Ý KIẾN CỦA GIÁO VIÊN PHẢN BIỆN ……………………………………………………………………………………… ….………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… Xác nhận của GVPB SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 3 ĐỀ CƯƠNG CHI TIẾT Thơng tin chung về đề tài: Tên đề tài: Xây dựng bộ ngữ liệu để đánh giá (test collection) bằng tiếng Việt và chương trình trợ giúp đánh giá các hệ tìm kiếm thơng tin GVHD: Tiến sĩ Hồ Bảo Quốc Sinh viên thực hiện: 1. MSSV: 0112385 Họ và tên: Tsàn Quế Hương 2. MSSV: 0112387 Họ và tên: Võ Hồ Bảo Khanh Tĩm tắt nội dung luận văn: Đề tài gồm 2 phần : 1. Xây dựng bộ ngữ liệu để đánh giá các hệ thống tìm kiếm thơng tin tiếng Việt. Việc xây dựng bộ ngữ liệu gồm ba phần : _ Xây dựng ngữ liệu mẫu tiếng Việt _ Xây dựng tập câu truy vấn mẫu tiếng Việt _ Xây dựng một bảng đánh giá bằng thủ cơng 2.Xây dựng một hệ thống chương trình trợ giúp việc đánh giá các hệ thống tìm kiếm thơng tin với thành phần đầu vào : ngữ liệu mẫu, câu truy vấn mẫu, hệ thống tìm kiếm thơng tin ; các thành phần đầu ra : kết quả truy vấn, kết quả đánh giá, nội dung tập tài liệu, câu truy vấn Một số từ khĩa chính liên quan đến nội dung đề tài: Đánh giá các hệ thống tìm kiếm thơng tin (information retrieval systems evaluation) Lĩnh vực áp dụng: Đánh giá các hệ thống tìm kiếm thơng tin tiếng Việt. Các thuật tốn, phương pháp, quy trình chính được nghiên cứu, ứng dụng trong đề tài _ Tìm hiểu về tìm kiếm thơng tin (information retrieval), đánh giá các hệ thống tìm kiếm thơng tin (information retrieval systems evaluation) _ Tìm hiểu cấu trúc của bộ ngữ liệu, phương pháp xây dựng bộ ngữ liệu của TREC (Text REtrieval Conference) _ Tìm hiểu và sử dụng các hệ thống tìm kiếm : SMART, IOTA ,Lucene,Terrier… _ Xây dựng bộ ngữ liệu kiểm tra bằng tiếng Việt SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 4 _ Xây dựng một hệ chương trình phục vụ việc kiểm tra và đánh giá các hệ thống tìm kiếm thơng tin. Chương trình phải chạy được trên hai hệ điều hành : Windows và Linux, chương trình viết bằng ngơn ngữ Java Các cơng cụ, cơng nghệ chính được nghiên cứu, ứng dụng trong đề tài Borland Jbuider X Visual Studio . NET Microsoft Visio 2003 Rational Rose Microsoft Word, Power Point Xác nhận của GVHD SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 5 Lời cám ơn Z X   Chúng em xin chân thành cảm ơn các Thầy Cơ Khoa Cơng nghệ Thơng tin đã hướng dẫn và giảng dạy rất nhiệt tình cho chúng em trong suốt bốn năm học ở Trường Đại học Khoa học Tự nhiên. Những kiến thức mà chúng em đã học được trên giảng đường sẽ là hành trang quý báu trên bước đường đời của chúng em. Chúng em xin cảm ơn Thầy Hồ Bảo Quốc đã tạo cơ hội cho chúng em được nghiên cứu học hỏi về lĩnh vực tìm kiếm thơng tin bằng Tiếng Việt, một lĩnh vực tương đối mới và hấp dẫn ở Việt Nam . Một lần nữa chúng em xin cảm ơn Thầy vì Thầy đã tận tình hướng dẫn chúng em đề tài luận văn “Xây dựng bộ ngữ liệu dùng để đánh giá bằng tiếng Việt và chương trình trợ giúp đánh giá các hệ thống tìm kiếm thơng tin”. Chúng em xin cảm ơn gia đình, các anh chị, bạn bè đã động viên, giúp đỡ chúng em để hồn thành tốt đề tài luận văn này. Nhĩm sinh viên thực hiện Tsàn Quế Hương – Võ Hồ Bảo Khanh SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 6 MỤC LỤC MỞ ĐẦU ............................................................................................................10 Chương 1 : TỔNG QUAN .................................................................................13 1.1. Tổng quan về tìm kiếm thơng tin và hệ thống tìm kiếm thơng tin ........................13 1.2. Tổng quan về đánh giá các hệ thống tìm kiếm thơng tin ......................................14 1.2.1. Lý do để tiến hành đánh giá các hệ thống tìm kiếm thơng tin........................14 1.2.2. Các tiêu chuẩn được dùng để đánh giá .........................................................15 1.2.3. Các mơ hình đánh giá...................................................................................15 1.2.4. Các độ đo dùng để đánh giá .........................................................................18 1.2.5. Các phương pháp xây dựng bộ ngữ liệu dùng để đánh giá ............................18 1.2.6. Phương pháp xây dựng bộ ngữ liệu được chọn.............................................20 1.2.7. Phương pháp đánh giá tầm quan trọng của kết quả trả về .............................21 Chương 2 : CƠ SỞ LÝ THUYẾT.......................................................................22 2.1. Tìm kiếm thơng tin và các hệ thống tìm kiếm thơng tin.......................................22 2.1.1. Lịch sử tìm kiếm thơng tin và hệ thống tìm kiếm thơng tin ...........................22 2.1.2. Hệ thống tìm kiếm thơng tin.........................................................................25 2.1.2.1. Khái niệm về hệ thống tìm kiếm thơng tin .............................................25 2.1.2.2. Cách thức hoạt động của hệ thống tìm kiếm thơng tin............................25 2.1.2.3. Các phương tiện tìm kiếm thơng tin (Search Engines) ...........................27 2.1.3. So sánh tìm kiếm thơng tin cổ điển và tìm kiếm thơng tin trên Web .............29 2.1.4. So sánh tìm kiếm thơng tin với tìm kiếm dữ liệu ..........................................30 2.1.5. Cơng thức trừu tượng trong tìm kiếm thơng tin ............................................31 2.1.6. Các mơ hình tìm kiếm thơng tin cổ điển để sắp thứ tự liên quan ...................32 2.1.6.1. Mơ hình Đại số Bool .............................................................................32 2.1.6.2. Mơ hình khơng gian vec-tơ....................................................................33 2.2. Đánh giá các hệ thống tìm kiếm thơng tin ...........................................................36 2.2.1. Nền tảng đánh giá các hệ thống tìm kiếm thơng tin ......................................36 2.2.2. Mơ hình đánh giá hướng hệ thống ................................................................37 2.2.2.1. Từ Cranfield đến TREC ........................................................................37 2.2.2.2. Thủ tục đánh giá....................................................................................39 2.2.2.3. Đánh giá sự liên quan............................................................................40 2.2.3. Thực hiện đo khả năng tìm kiếm ..................................................................41 2.2.3.1. Các khái niệm về độ đo và liên quan .....................................................41 2.2.3.2. Cách tính độ bao phủ (R) và độ chính xác (P)........................................42 2.2.3.3. Phương pháp tính độ chính xác dựa trên 11 điểm chuẩn của độ bao phủ 44 2.2.3.3.1. Đồ thị biểu diễn hiệu suất thực thi hệ thống tìm kiếm .....................44 2.2.3.3.2. Đường cong độ bao phủ và độ chính xác RP...................................45 2.2.3.3.3. Đường cong RP cho tập truy vấn ....................................................47 2.2.3.3.4. Đánh giá hệ thống tìm kiếm thơng tin dựa vào đồ thị ......................48 2.2.3.4. Sự liên quan giữa câu hỏi và tài liệu ......................................................49 2.2.3.4.1. Các độ liên quan .............................................................................49 2.2.3.4.2. Các vấn đề về độ liên quan .............................................................49 2.2.3.4.3. Đánh giá với độ liên quan nhiều cấp độ ..........................................51 2.2.3.4.4. Phương pháp đo độ bao phủ (R), độ chính xác (P) dựa trên độ liên quan nhiều cấp độ ..........................................................................................53 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 7 2.2.4. TREC và đánh giá theo chuẩn TREC ...........................................................54 2.2.4.1. TREC là gì? ..........................................................................................54 2.2.4.2. Cách xây dựng ngữ liệu của TREC........................................................56 2.2.4.2.1. Xây dựng tập hợp các tài liệu..........................................................57 2.2.4.2.2. Xây dựng các chủ đề.......................................................................57 2.2.4.2.3. Xây dựng bảng đánh giá liên quan chuẩn........................................58 2.3. Ngữ liệu tiếng Việt .............................................................................................59 2.3.1. Từ ................................................................................................................60 2.3.1.1. Quan niệm về từ ....................................................................................60 2.3.1.2. Quan niệm về hình vị ............................................................................61 2.3.1.3. Khái niệm về cấu tạo từ.........................................................................61 2.3.2. Ranh giới từ .................................................................................................62 Chương 3 : THIẾT KẾ VÀ CÀI ĐẶT.................................................................63 3.1. Xây dựng bộ ngữ liệu dùng để đánh giá ..............................................................63 3.1.1. Xây dựng kho ngữ liệu bằng tiếng Việt ........................................................63 3.1.1.1. Chuẩn hĩa ngữ liệu ...............................................................................63 3.1.1.1.1. Chuẩn hĩa dạng ngữ liệu ................................................................63 3.1.1.1.2. Định dạng ngữ liệu .........................................................................64 3.1.2. Xây dựng tập câu hỏi bằng tiếng Việt...........................................................64 3.1.3. Tách từ tiếng Việt ........................................................................................65 3.1.4. Xây dựng bảng đánh giá...............................................................................65 3.1.4.1. Hệ thống SMART .................................................................................66 3.1.4.1.1. Giới thiệu hệ thống SMART...........................................................66 3.1.4.1.2. Quá trình tìm kiếm thơng tin của SMART ......................................66 3.1.4.1.3. Mơ hình vec-tơ của hệ thống SMART ............................................67 3.1.4.1.4. Sử dụng mơ hình vec-tơ..................................................................69 3.1.4.2. Hệ thống Search4Vn .............................................................................73 3.1.4.3. Hệ thống TERRIER ..............................................................................73 3.1.4.4. Hệ thống X-IOTA .................................................................................74 3.1.4.5. Hệ thống LUCENE ...............................................................................74 3.2. Phân tích hệ thống đánh giá các hệ thống tìm kiếm thơng tin ..............................74 3.2.1. Mơ tả hệ thống trợ giúp đánh giá..................................................................74 3.2.1.1. Phát biểu bài tốn..................................................................................74 3.2.1.2. Mục tiêu................................................................................................75 3.2.1.3. Phạm vi .................................................................................................75 3.2.1.4. Chức năng .............................................................................................75 3.2.1.5. Tính khả dụng .......................................................................................76 3.2.1.6. Hiệu suất ...............................................................................................76 3.2.1.7. Tính bảo mật .........................................................................................76 3.2.2. Phân tích hệ thống đánh giá..........................................................................76 3.2.2.1. Chức năng của hệ thống ........................................................................76 3.2.2.2. Chức năng yêu cầu ................................................................................77 3.2.2.2.1. Chức năng đánh giá một hệ thống IR..............................................77 3.2.2.2.2. Chức năng so sánh nhiều hệ thống IR .............................................77 3.2.2.2.3. Sơ đồ use case ................................................................................77 3.2.2.2.4. Sơ đồ tuần tự hoạt động usecase .....................................................79 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 8 3.3. Thiết kế hệ thống đánh giá ..................................................................................86 3.3.1. Các chức năng của chương trình...................................................................86 3.3.1.1. Chức năng “Định dạng cơ sở dữ liệu tài liệu” ........................................86 3.3.1.2. Chức năng “Định dạng kết quả trả về”...................................................86 3.3.1.3. Chức năng “Định dạng file index”.........................................................87 3.3.1.4. Chức năng “Thực thi hệ thống IR” ........................................................87 3.3.1.5. Chức năng “Xử lý kết quả trả về” ..........................................................87 3.3.1.6. Chức năng ”Đánh giá một hệ thống IR”.................................................87 3.3.1.7. Chức năng “Đánh giá nhiều hệ thống IR”..............................................87 3.3.2. Thiết kế hệ thống .........................................................................................88 3.3.2.1. Sơ đồ kiến trúc tổng thể.........................................................................88 3.3.2.1.1. Danh sách các lớp đối tượng...........................................................88 3.3.2.1.2. Lớp đối tượng thể hiện....................................................................88 3.3.2.1.3. Lớp đối tượng xử lý........................................................................91 3.3.2.1.4. Lớp đối tượng lưu trữ .....................................................................99 3.3.2.2. Sơ đồ kiến trúc tổng quát cho từng chức năng của chương trình ............99 3.3.2.2.1. Chức năng “Định dạng tài liệu” ......................................................99 3.3.2.2.2. Chức năng “Định dạng câu hỏi”....................................................100 3.3.2.2.3. Chức năng “Thực thi hệ thống” ....................................................101 3.3.2.2.4. Chức năng “Định dạng kết quả”....................................................102 3.3.2.2.5. Chức năng “Định dạng file index” ................................................103 3.3.2.2.6. Chức năng “Đánh giá và hiện thi kết quả đánh giá” ......................103 3.3.2.2.7. Chức năng ”So sánh các hệ thống IR đã được thực thi” ................104 3.3.2.3. Thiết kế dữ liệu – tổ chức lưu trữ.........................................................105 3.3.2.3.1. Mơ hình dữ liệu ............................................................................105 3.3.2.3.2. Sơ đồ logic dữ liệu........................................................................107 3.3.2.4. Tố chức lưu trữ dữ liệu........................................................................110 3.3.2.4.1. System..........................................................................................110 3.3.2.4.2. Topic ............................................................................................112 3.3.2.4.3. Index_topic...................................................................................113 3.3.2.4.4. Document .....................................................................................114 3.3.2.4.5. Index_Doc....................................................................................115 3.3.2.4.6. relevant_TT..................................................................................115 3.3.2.4.7. relevant_LT..................................................................................116 3.3.2.4.8. evaluation.....................................................................................117 3.3.2.5. Thiết kế giao diện................................................................................119 3.3.2.5.1. Sơ đồ liên hệ giữa các màn hình ...................................................119 3.3.2.6. Thiết kế màn hình................................................................................ 122 3.3.2.6.1. Màn hình chính (TH_Main) ..........................................................122 3.3.2.6.2. Màn hình định dạng tài liệu (TH_DDTaiLieu) ..............................122 3.3.2.6.3. Màn hình tạo thuộc tính cho tài liệu (TH_TTTaiLieu) ..................124 3.3.2.6.4. Màn hình định dạng câu hỏi (TH_DDCauHoi)..............................125 3.3.2.6.5. Màn hình tạo thuộc tính cho câu hỏi (TH_TTCauHoi) ..................127 3.3.2.6.6. Màn hình xử lý điều kiện để thực thi hệ thống IR..........................128 3.3.2.6.7. Màn hình thực thi hệ thống (TH_ThucThiHT) ..............................129 3.3.2.6.8. Màn hình định dạng kết quả (TH_DDKetQua)..............................130 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 9 3.3.2.6.9. Màn hình định dạng thơng tin index (TH_DDIndex).....................131 3.3.2.6.10. Màn hình đánh giá hệ thống (TH_KqDanhGia)...........................133 3.3.2.6.11. Màn hình xem đồ thị của hệ thống ..............................................136 3.3.2.6.12. Màn hình xem chi tiết (TH_XemChiTiet) ...................................136 3.3.2.6.13. Màn hình so sánh hệ thống (TH_SoSanhHT) ..............................138 3.3.2.7. Thiết kế hệ thống lớp đối tượng...........................................................139 3.3.2.7.1. Các lớp đối tượng xử lý ................................................................139 3.3.2.7.2. Các lớp đối tượng lưu trữ..............................................................169 Chương 4 : KẾT QUẢ ĐÁNH GIÁ .................................................................. 171 4.1. Ngưỡng đánh giá ..............................................................................................171 4.2. Đánh giá hệ thống tìm kiếm thơng tin search4VN .............................................171 4.3. So sánh hệ thống tìm kiếm search4VN và hệ thống Lucene............................... 177 4.4. Nhận xét chương trình hỗ trợ đánh giá hệ thống tìm kiếm thơng tin ..................179 4.4.1. Ưu điểm.....................................................................................................179 4.4.2. Khuyết điểm ..............................................................................................179 Chương 5 : KẾT LUẬN .................................................................................... 181 Chương 6 : HƯỚNG PHÁT TRIỂN.................................................................. 182 PHỤ LỤC ......................................................................................................... 183 Tài liệu tham khảo .......................................................................................... 186 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 10 MỞ ĐẦU Tìm kiếm thơng tin là nhu cầu thiết thực của tất cả mọi người. Đặc biệt trong bối cảnh bùng nổ thơng tin như hiện nay, gồm cĩ sự ra đời của internet và sáng kiến về thư viện điện tử, nhu cầu tìm kiếm thơng tin lại càng phát triển. Nhưng nhờ cĩ sự trợ giúp của cơng nghệ thơng tin con người cĩ thể thỏa mãn nhu cầu này một cách dễ dàng. Thật vậy, cĩ rất nhiều hệ thống tìm kiếm thơng tin (Information Retrieval system hay IR system) trên máy tính đang tồn tại để trợ giúp con người. Tuy nhiên, khả năng tìm kiếm thơng tin của các hệ thống này chắc chắn khác nhau. Do đĩ, việc đánh giá các hệ thống tìm kiếm thơng tin (Evaluation of Information Retrieval systems) là một nhu cầu khơng thể thiếu nhằm xác định các hệ thống tìm kiếm thơng tin hiệu quả. Việc đánh giá này cĩ ý nghĩa rất lớn đối với sự tồn tại và phát triển của các hệ thống tìm kiếm thơng tin. Nĩ giúp xác định khả năng tìm kiếm của các hệ thống tìm kiếm thơng tin từ đĩ mà các tổ chức, cơng ty, trường học tạo ra hệ thống này cĩ thể phát triển, thay đổi hệ thống để đưa ra khả năng tìm kiếm thơng tin tốt nhất. Ngồi ra, việc xác định các hệ thống tìm kiếm thơng tin hiệu quả rất hữu ích đối với người dùng, họ sẽ cảm thấy tin tưởng vào kết quả tìm kiếm mà hệ thống tìm được. Xa hơn nữa, việc đánh giá sẽ tạo ra một cuộc cách mạng trong lĩnh vực tìm kiếm thơng tin; giúp đưa tìm kiếm thơng tin vào trong thế giới thực của đời sống. Chẳng hạn, khi các hệ thống tìm kiếm thơng tin tiến bộ chuyển từ nghiên cứu sang thế giới thực của cạnh tranh thương mại thì những nhà thiết kế, nhà phát triển, người bán hàng, và những đại diện bán hàng của các sản phẩm thơng tin mới như sách điện tử, và các phương tiện tìm kiếm (Search engines) … muốn biết sản phẩm của họ cĩ cung cấp cho những người sử dụng và người mua hàng tiềm năng các lợi thế cạnh tranh hay khơng, sẽ được thỏa mãn nhu cầu thơng tin này một cách dễ dàng, chính xác. Khả năng tìm kiếm của hệ thống tìm kiếm thơng tin chúng tơi vừa đề cập được nghiên cứu ở nhiều cấp độ: thứ nhất là về khả năng xử lý tức thời gian tìm kiếm và khơng gian lưu trữ hay cịn gọi là hiệu năng; thứ hai là về khả năng tìm SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 11 kiếm hay hiệu quả của kết quả trả về; thứ ba là khả năng về hệ thống tức hệ thống cĩ thỏa mãn nhu cầu thơng tin của người dùng hay khơng. Hiện nay, trên thế giới đã cĩ rất nhiều hệ thống đánh giá các hệ thống tìm kiếm thơng tin nhưng chủ yếu là đánh giá các hệ thống tìm kiếm thơng tin tiếng Anh, tiếng Pháp. Đối với tiếng Việt, theo chúng tơi được biết, chưa cĩ một hệ thống nào được dùng để đánh giá các hệ thống tìm kiếm thơng tin tiếng Việt. Nhưng theo xu hướng phát triển của đất nước và nhu cầu tìm kiếm thơng tin thì các hệ thống tìm kiếm thơng tin tiếng Việt bắt buộc phải tồn tại và phát triển. Vì vậy, Việt Nam chúng ta rất cần các hệ thống được dùng để đánh giá hiệu năng, hiệu quả của các hệ thống tìm kiếm thơng tin tiếng Việt. Do ý nghĩa to lớn của lĩnh vực nghiên cứu đánh giá này, chúng tơi đã quyết định chọn đề tài đánh giá các hệ thống tìm kiếm thơng tin. Chúng tơi nghĩ rằng hệ thống đánh giá của chúng tơi sẽ là cơ sở để đánh giá tất cả các hệ thống tìm kiếm thơng tin, nhất là hệ thống tìm kiếm thơng tin tiếng Việt. Chúng tơi cũng hy vọng hệ thống của chúng tơi sẽ gĩp phần vào sự phát triển của các hệ thống tìm kiếm thơng tin, của tìm kiếm thơng tin và của cơng nghệ thơng tin nước ta. Thực hiện đánh giá khả năng tìm kiếm, chúng tơi tập trung vào đánh giá hiệu quả của kết quả tìm kiếm được trả về (cấp độ thứ hai trong khả năng tìm kiếm của hệ thống thơng tin ở trên). Hiệu quả của kết quả trả về được định nghĩa là khả năng hệ thống tìm kiếm thơng tin tìm được các tài liệu liên quan (Relevant Documents) và loại bỏ đi những tài liệu khơng liên quan (Irrelevant Documents). Đây là mơ hình hướng hệ thống trong nghiên cứu tìm kiếm thơng tin. Mơ hình này mơ hình đánh giá được sử dụng nhiều nhất và hiệu quả nhất trên thế giới. Và để xây dựng hệ thống đánh giá các hệ thống tìm kiếm thơng tin tiếng Việt theo mơ hình hướng hệ thống, trước hết, chúng tơi cần phải xây dựng bộ ngữ liệu dùng để đánh giá bằng tiếng Việt (a Vietnamese Test collection). Bộ ngữ liệu dùng để đánh giá gồm cĩ kho ngữ liệu mẫu bằng tiếng Việt (a Vietnamese SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 12 Corpus hay a set of Vietnamese documents), tập câu truy vấn mẫu bằng tiếng Việt (a set of Vietnamese queries), và bảng đánh giá liên quan chuẩn (Relevance Judgment). Chúng tơi tìm hiểu và thực hiện xây dựng bộ ngữ liệu dùng để đánh giá theo tiêu chuẩn của Hội nghị về Tìm kiếm thơng tin Văn bản (Text REtrieval Conference hay TREC) của Hoa Kỳ, một trong những Hội nghị hàng đầu trên thế giới về Tìm kiếm Thơng tin. Tiếp theo, chúng tơi xây dựng chương trình trợ giúp đánh giá các hệ thống tìm kiếm thơng tin, cho phép người dùng thao tác, thực hiện đánh giá các hệ thống một cách dễ dàng. Kết quả trả về của chương trình đánh giá cĩ được dựa vào bộ ngữ liệu mẫu được dùng đánh giá. Kết quả trả về này gồm cĩ kết quả truy vấn của hệ thống tìm kiếm thơng tin và kết quả đánh giá. Kết quả đánh giá được tính dựa trên sự kết hợp của hai độ đo: độ bao phủ (Recall) và độ chính xác (Precision). Từ kết quả trả về, chúng ta cĩ thể biết được khả năng tìm kiếm của riêng từng hệ thống tìm kiếm thơng tin và so sánh khả năng của các hệ thống tìm kiếm với nhau. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 13 Chương 1 : TỔNG QUAN 1.1. Tổng quan về tìm kiếm thơng tin và hệ thống tìm kiếm thơng tin Tìm kiếm thơng tin liên quan đến việc biểu diễn, lưu trữ, tổ chức và tiếp cận các yếu tố thơng tin (một tài liệu cĩ thể cĩ một hoặc nhiều yếu tố thơng tin) [1 ]. Theo lý thuyết, khơng cĩ giới hạn về các loại yếu tố thơng tin trong tìm kiếm thơng tin. Trên thực tế, các loại yếu tố thơng tin ngày càng trở nên đa dạng cùng với sự phát triển của xã hội. Ngồi ra, một tập hợp các yếu tố thơng tin được gọi là hữu dụng khi và chỉ khi nĩ đầy đủ và luơn được cập nhật. Đầy đủ ở đây cĩ nghĩa là tập hợp này phải chứa một tỉ lệ lớn các yếu tố thơng tin được xem là cĩ khả năng liên quan đến các lĩnh vực xác định. Hơn nữa, việc biểu diễn và tổ chức các yếu tố thơng tin nên cung cấp cho người dùng cách truy cập dễ dàng nhất đến thơng tin mà người đĩ quan tâm. Nhưng khơng may là tính chất của nhu cầu thơng tin người dùng khơng phải đơn giản. Chúng ta xem xét một ví dụ về một nhu cầu thơng tin hiển nhiên của người sử dụng trong ngữ cảnh tìm kiếm World Wide Web hay chỉ là Web: Tìm tất cả các trang hay tài liệu chứa thơng tin về bệnh ung thư phổi và nguyên nhân dẫn đến ung thư phổi, các tài liệu được xem là liên quan phải vừa nĩi đến các triệu chứng ung thư phổi, vừa nĩi đến nguyên nhân dẫn đến căn bệnh này gồm cả tác hại của việc hút thuốc và ơ nhiễm mơi trường. Từ ví dụ trên, chúng ta thấy rõ ràng là sự mơ tả đầy đủ nhu cầu thơng tin người dùng khơng thể được sử dụng trực tiếp để tìm kiếm trên bình diện của các phương tiện tìm kiếm Web (Web Search Engine) hay hệ thống tìm kiếm thơng tin (IR system) hiện nay. Thay vào đĩ, người sử dụng phải dịch nhu cầu thơng tin của mình sang một câu truy vấn cĩ thể được xử lý bằng phương tiện tìm kiếm hay hệ thống tìm kiếm thơng tin. Điều này tạo ra một tập các từ khĩa tĩm tắt mơ tả nhu cầu thơng tin người dùng hay cịn gọi là câu truy vấn. Dựa trên câu truy vấn của người sử dụng, mục đích chính của hệ thống tìm kiếm thơng tin là tìm kiếm các thơng tin hữu ích hay liên quan cho người sử dụng. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 14 Vậy cĩ thể nĩi một cách tổng quát, hệ thống tìm kiếm thơng tin là một hệ thống cho phép người sử dụng tìm kiếm tài liệu để thỏa mãn nhu cầu thơng tin từ một kho ngữ liệu lớn. Để tìm kiếm thơng tin, hệ thống tìm kiếm phải thực hiện các cơng việc sau. Trước hết, hệ thống tìm kiếm xử lý tài liệu thơ thành những tài liệu được tách từ, phân đoạn (tokenized documents) và sau đĩ lập chỉ mục (index) dựa trên vị trí của từ. Khi người dùng đưa vào câu truy vấn, hệ thống tìm kiếm thơng tin cũng sẽ xử lý các câu truy vấn thành ngơn ngữ chỉ mục mơ tả các yếu tố thơng tin cần tìm kiếm và thực hiện đối chiếu với chỉ mục tài liệu để tìm ra các tài liệu liên quan. Cuối cùng, các tài liệu liên quan sẽ được trả về cho người dùng theo một danh sách được sắp xếp theo độ ưu tiên chính xác giảm dần (ranked list). 1.2. Tổng quan về đánh giá các hệ thống tìm kiếm thơng tin 1.2.1. Lý do để tiến hành đánh giá các hệ thống tìm kiếm thơng tin Khi nhu cầu tìm kiếm thơng tin phát triển, cĩ rất nhiều mơ hình, thuật tốn, hệ thống tìm kiếm thơng tin ra đời. Do đĩ, việc đánh giá các mơ hình, thuật tốn, hệ thống tìm kiếm thơng tin là điều bắt buộc phải làm. Chúng ta so sánh một hệ thống (cĩ thể là một hệ thống mới) với các hệ thống khác đã tồn tại về phương diện: tính hiệu quả, chi phí, thời gian , tốc độ xử lý… Hệ thống tìm kiếm thơng tin thường thực hiện hai quá trình: quá trình lập chỉ mục và quá trình tìm kiếm. Mỗi một quá trình sẽ cĩ nhiều phương pháp để thực hiện, đánh giá hệ thống cũng cĩ thể dùng để xác định tính tối ưu của các phương pháp trên. Lý do khác để tiến hành đánh giá là để so sánh các thành phần của hệ thống. Do hệ thống gồm nhiều thành phần, đánh giá hệ thống để xác định cách mỗi thành phần của hệ thống thực thi để khi cĩ sự thay đổi một thành phần bởi một thành phần khác thì sự thay đổi đĩ ảnh hưởng đến hệ thống như thế nào, từ đĩ ta cĩ thể quyết định cĩ nên thay đổi thành phần đĩ khơng. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 15 Đánh giá để tìm kiếm thành phần nào là tốt nhất cho hàm xếp thứ tự (dot- product, cosine…); thành phần nào là tốt nhất cho lựa chọn thuật ngữ (loại bỏ stopword, phương pháp lấy gốc từ stemming …); thành phần nào là tốt nhất trong lựa chọn phương pháp đánh giá thuật ngữ (term weighting) như TF, IDF … (các thành phần này sẽ được nĩi rõ hơn trong chương sau). So sánh để biết người sử dụng cần danh sách các tài liệu trả về (ranked list) dài cỡ bao nhiêu để họ cĩ thể nhìn dễ dàng nhất. Đánh giá để biết hệ thống nào thật sự tốt, người dùng cĩ thể tin tưởng kết quả trả về được. 1.2.2. Các tiêu chuẩn được dùng để đánh giá Hiện nay, trên thế giới cĩ ba tiêu chuẩn được dùng để đánh giá hệ thống tìm kiếm thơng tin. Thứ nhất là tiêu chuẩn về tính hiệu quả tức sự chính xác, tính đầy đủ của kết quả trả về so với mục đích tìm kiếm của người sử dụng, và giá trị vẫn cĩ thể đốn được trong các tình huống khác cĩ nghĩa là khi đưa vào các câu truy vấn khác, tập tài liệu khác thì hệ thống vẫn cĩ thể tìm ra kết quả chính xác. Thứ hai là tiêu chuẩn về hiệu năng, gồm cĩ tốc độ tìm kiếm của thuật tốn, khả năng lưu trữ, thời gian trả về cho người sử dụng, thời gian lập chỉ mục, kích thước chỉ mục… Thứ ba là tiêu chuẩn về khả năng sử dụng hệ thống tức là cĩ thể nghiên cứu, học hỏi trên hệ thống tìm kiếm, người khơng biết tin học hay các chuyên gia tin học đềi cĩ thể sử dụng hệ thống. 1.2.3. Các mơ hình đánh giá Theo chúng tơi được biết, trên thế giới cĩ tất cả bốn mơ hình đánh giá các hệ thống tìm kiếm thơng tin. Chúng bao gồm : đánh giá hộp kính, đánh giá hộp đen, đánh giá hướng hệ thống, đánh giá hướng người dùng hay cịn gọi là đánh giá nghiên cứu người dùng [ 2]. Đánh giá hộp kính (glass box evaluation) : đánh giá hệ thống dựa trên việc đánh giá tất cả mọi thành phần của hệ thống. Cĩ nghĩa là khi biết rõ các thành phần của hệ thống, chúng ta tiến hành đánh giá các thành phần đĩ. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 16 Đánh giá hộp đen (black box evaluation) : đánh giá hệ thống bằng cách xem hệ thống như là một thực thể hợp nhất, khơng đánh giá chính xác các thành phần bên trong hệ thống. Đánh giá hướng hệ thống (system-oriented evaluation) là xu hướng đánh giá chính từ khi các hệ thống tìm kiếm và lập chỉ mục tự động được phát triển vào những năm 1960. Một trong những mục đích chính của hướng đánh giá này là kiểm tra các hệ thống tự động cũng như các thủ tục thủ cơng thực thi như thế nào. Ngồi ra, mơ hình này cịn đánh giá so sánh các cách thực hiện liên quan đến các ngơn ngữ chỉ mục, xử lý tìm kiếm của hệ thống của các hệ thống khác nhau hay đánh giá so sánh các lược đồ chỉ mục tự động khác nhau. Đánh giá hướng hệ thống cĩ một điểm lợi là điều kiện mơi trường kiểm tra được quản lý chặt chẽ, sử dụng phương pháp đánh giá theo lơ hay cịn gọi là đánh giá dựa trên tập câu truy vấn; cĩ nghĩa là hệ thống tìm kiếm thơng tin lần lượt thực hiện các câu truy vấn, tìm kiếm trên tập dữ liệu đã được xây dựng và ghi lại kết quả những tài liệu nào liên quan đến câu truy vấn nào rồi đem so sánh với Bảng Đánh giá liên quan chuẩn (Relevance judgment) đã được xây dựng. Với mỗi câu truy vấn tính tốn độ chính xác và độ bao phủ dựa trên kết quả trả về và bảng đánh giá liên quan chuẩn để nhận xét hiệu quả tìm kiếm của hệ thống tìm kiếm thơng tin. Hướng đánh giá này được thực hiện rất phổ biến ở các dự án, hội nghị về nghiên cứu hệ thống tìm kiếm thơng tin như: Cranfield , MEDLARS, SMART, STAIRS và TREC. Đánh giá hướng người dùng (user studies evaluation): Hướng nghiên cứu người dùng ra đời vào những năm 1970 khi mà nhiều hệ thống tìm kiếm thơng tin thương mại ra đời. Mục đích chính của hướng nghiên cứu này là nhằm xác định cách thức tìm kiếm của người sử dụng [ 3]. Hướng đánh giá này cịn cho phép xem xét hệ thống ở khía cạnh người dùng; tức là đánh giá về mặt tương tác với người sử dụng như giao diện của hệ thống tìm kiếm thơng tin, thời gian hệ thống tìm kiếm đối với một câu truy vấn, SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 17 mức độ hài lịng của người sử dụng… Hướng nghiên cứu này cho rằng nhu cầu của người dùng được thoả mãn tương đương với hiệu quả của hệ thống. Chỉ khi nhu cầu thơng tin người dùng được thỏa mãn, khi ấy tìm kiếm thơng tin mới được gọi là cĩ ích. Hội nghị quốc tế về Tìm kiếm Thơng tin trong Ngữ cảnh (Information Seeking in Context) được tổ chức như là một diễn đàn cho các nhà nghiên cứu lĩnh vực này khám phá các phương pháp và các kết quả nghiên cứu. Một hội nghị khác mới được thành lập tên là Nhĩm Quan tâm Đặc biệt (Special Interest Group - SIG) đến tìm kiếm, nhu cầu và sử dụng thơng tin của Xã hội Hoa Kỳ về Khoa học Thơng tin (American Society of Information Science). Những hội nghị này cũng tương tự như TREC trong việc cố gắng khuyến khích nghiên cứu hướng người dùng, để phát triển mối liên hệ giữa các nhà nghiên cứu trong kỹ thuật, giáo dục và chính phủ, và để xác định, cải tiến các kỹ thuật tìm kiếm thích hợp. Nhưng các hội nghị này khác nhau ở chỗ các hội nghị mới chưa cĩ phương pháp luận đánh giá chuẩn nào được xúc tiến. Đánh giá hướng người dùng cĩ đĩng gĩp rất lớn đến lĩnh vực tìm kiếm thơng tin. Đĩng gĩp này gồm cĩ việc xác định cách thức tìm kiếm thơng tin của con người, nối liền khoảng cách giữa nhu cầu thơng tin giữa các cá nhân và các hệ thống tìm kiếm thơng tin, dẫn đến một thế hệ mới của các hệ thống tìm kiếm thơng tin bao gồm các giao diện đồ hoạ máy tính-người sử dụng. Hiện nay, trong số bốn mơ hình trên thì hai mơ hình đánh giá hướng hệ thống và hướng người dùng đang được sử dụng chính và rộng rãi nhất. Trong phạm vi đề tài của chúng tơi, chúng tơi chỉ sử dụng mơ hình đánh giá hướng hệ thống vì mơ hình đánh giá hướng người dùng cần cĩ sự hợp tác của rất nhiều người dùng để lấy thơng tin phản hồi sau khi sử dụng hệ thống tìm kiếm thơng tin đĩ hoặc cần phải tham gia trao đổi về hiệu năng tìm kiếm tại các hội nghị. Nhưng các hội nghị dành cho mơ hình đánh giá hướng người dùng đa số chưa cĩ một phương pháp luận cụ thể nào dùng để đánh giá. Ngồi ra, với mơ hình hướng hệ thống, chúng SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 18 tơi cĩ thể xây dựng ứng dụng để đánh giá nhiều hệ thống tìm kiếm thơng tin một cách tự động. 1.2.4. Các độ đo dùng để đánh giá Độ bao phủ (Recall) và độ chính xác (Precision) là 2 đơn vị đo cơ bản nhất để đánh giá chất lượng một hệ thống tìm kiếm thơng tin [4 ]. Độ bao phủ là tỉ lệ giữa các tài liệu liên quan được trả về trên tổng số các tài liệu liên quan thật sự. Trong khi đĩ, độ chính xác là tỉ lệ giữa các tài liệu liên quan được trả về trên tổng số tài liệu được trả về. Cĩ nhiều phương pháp sử dụng một hoặc các độ đo này để tính tốn đánh giá, chẳng hạn phương pháp Độ chính xác trung bình (Mean Average Precision – MAP) chỉ sử dụng độ chính xác, khơng quan tâm đến độ bao phủ. Phương pháp đo dựa trên giá trị đơn Swet’s E-Measure hoặc chiều dài tìm kiếm trung bình thì cũng chỉ sử dụng một giá trị để tính tốn. Phương pháp tính độ chính xác dựa trên 11 điểm chuẩn của độ bao phủ sử dụng cả hai độ đo độ bao phủ và độ chính xác. Chúng tơi thực hiện đánh giá theo phương pháp tính độ chính xác dựa trên 11 điểm chuẩn của độ bao phủ bởi vì phương pháp này khá đơn giản, dễ thực hiện tính tốn, đo và đánh giá. Ngồi ra, phương pháp này trực quan với cách biểu diễn đồ thị của các điểm bao phủ, chính xác từ đĩ dễ dàng thấy hiệu quả tìm kiếm của riêng từng hệ thống và so sánh các hệ thống đánh giá với nhau. 1.2.5. Các phương pháp xây dựng bộ ngữ liệu dùng để đánh giá Theo mơ hình hướng hệ thống, trước hết phải xây dựng bộ ngữ liệu dùng để đánh giá (test collection). Bộ ngữ liệu dùng để đánh giá gồm cĩ tập các tài liệu mẫu, tập câu truy vấn mẫu, và bảng đánh giá liên quan chuẩn. • Tập tài liệu dùng để đánh giá được thu thập từ các nguồn khác nhau, gồm nhiều chủ đề khác nhau. Tập tài liệu này phải là những tài liệu mẫu bao quát càng nhiều lĩnh vực càng tốt, phản ánh được các vấn đề đa dạng khác nhau, các phong cách văn chương khác nhau … Điều này cĩ nghĩa là tập SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 19 tài liệu mẫu này phải cĩ kích thước lớn, vì vậy tập tài liệu này cịn được gọi là kho ngữ liệu mẫu. • Tập câu truy vấn mẫu là những câu hỏi được tạo ra phù hợp với tập tài liệu mẫu. Tập câu truy vấn này sau đĩ sẽ được sử dụng để tìm kiếm. • Bảng đánh giá liên quan chuẩn là bảng chứa thơng tin về số thứ tự câu hỏi và các tài liệu liên quan thật sự của câu hỏi đĩ. Bảng Đánh giá liên quan chuẩn được dùng như là bảng đối chiếu để tính độ bao phủ và độ chính xác. Cĩ nhiều cách khác nhau để tạo bảng đánh giá liên quan chuẩn hay bảng Relevance judgment. Các phương pháp này gồm cĩ: 8 Phương pháp đánh giá tồn bộ, phương pháp này thường khơng khả thi vì tỉ lệ tập câu hỏi*tập tài liệu là quá lớn. Phương pháp này rất tốn chi phí. 8 Phương pháp Pooling hay cịn gọi là phương pháp lấy một số tài liệu liên quan nhất để làm bảng đánh giá liên quan chuẩn. Phương pháp này sử dụng tốt cho đánh giá nhiều hệ thống tìm kiếm thơng tin. Phương pháp này địi hỏi phải cĩ một sự đa dạng các hệ thống tìm kiếm thơng tin. Bước đầu tiên của phương pháp này là tìm thấy các tài liệu liên quan cho mỗi hệ thống. Các hệ thống khác nhau tìm thấy các tài liệu liên quan khác nhau. Bước tiếp theo là tổng hợp các kết quả của tất cả các hệ thống lại và lấy phần giao của các bảng đánh giá liên quan của các hệ thống. Nhưng phần giao này cĩ thể chỉ là một số lượng nhất định các tài liệu gần như chính xác nhất. Việc đánh giá dựa trên phương pháp này thật sự khách quan khi đánh giá các hệ thống khơng được chọn để giao lấy bảng Đánh giá liên quan chuẩn. 8 Phương pháp đánh giá hướng dẫn chỉ tìm kiếm thỉnh thoảng cho kết quả tốt. Phương pháp này cho phép tương tác giữa nghiên cứu truy vấn, tìm kiếm, đánh giá. Tăng cường thêm bằng cách xem lại, điều chỉnh, đánh giá lại. Nĩi chung, khi sử dụng phương pháp này, người đánh giá SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 20 phải thao tác bằng tay rất nhiều, xem các tài liệu trả về cĩ thật sự là liên quan hay chưa để đưa vào bảng Đánh giá liên quan chuẩn. 8 Các đánh giá dựa trên những thành phần đã biết, phương pháp này tốn ít chi phí nhất. Phương pháp này cho phép thay đổi câu hỏi để tìm ra một tài liệu đã biết. 1.2.6. Phương pháp xây dựng bộ ngữ liệu được chọn Kể từ năm 1992, khi Hội nghị về Tìm kiếm thơng tin Văn bản (Text REtrieval Conference hay TREC) của Hoa Kỳ ra đời, mơ hình hướng hệ thống mới thật sự phát triển. Bởi vì hằng năm, TREC tổ chức hội nghị để kêu gọi tham gia đánh giá các hệ thống tìm kiếm thơng tin, đặc biệt kêu gọi đánh giá theo mơ hình hướng hệ thống. Nhờ đĩ mà mỗi năm khối lượng, kích thước bộ ngữ liệu dùng để đánh giá tăng lên rất đáng kể cùng với sự phát triển về số lượng các tổ chức, trường Đại học tham gia TREC. TREC được xem là Hội nghị lớn nhất thế giới về đánh giá các hệ thống tìm kiếm thơng tin và là một trong những Hội nghị cĩ uy tín trong lĩnh vực tìm kiếm thơng tin. TREC xây dựng bảng đánh giá liên quan chuẩn theo phương pháp Pooling. TREC cịn đưa ra các tiêu chuẩn, định dạng cho ngữ liệu rất rõ ràng, và dễ tuân theo. Vì vậy, chúng tơi quyết định chọn phương pháp xây dựng ngữ liệu theo tiêu chuẩn và cách làm của TREC. Chúng tơi định dạng câu hỏi và tài liệu theo tiêu chuẩn định dạng mà TREC đưa ra, đồng thời làm bảng đánh giá liên quan chuẩn theo phương pháp Pooling hay phương pháp lấy một số tài liệu liên quan nhất để làm bảng Đánh giá liên quan giống TREC vì cách tạo bảng đánh giá khách quan mà nĩ mang lại và khơng phải tốn nhiều thời gian, chi phí. Tuy nhiên, đối với tiếng Việt, việc xây dựng bộ ngữ liệu đánh giá phức tạp hơn là xây dựng bộ ngữ liệu tiếng Anh, tiếng Pháp trong trường hợp dùng các hệ thống tìm kiếm phổ biến, nổi tiếng sẵn cĩ cho tiếng Anh, Pháp để tìm kiếm thơng tin tiếng Việt. Bởi vì đặc thù loại hình ngơn ngữ khác nhau giữa tiếng Anh, Pháp và tiếng Việt. Chẳng hạn, trong tiếng Anh, Pháp mỗi từ là một từ đơn, cách nhau bởi SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 21 một khoảng trắng nhưng tiếng Việt thì hồn tồn khác, một từ cĩ thể gồm từ một từ đơn trở lên. Do đĩ, để những hệ thống tìm kiếm thơng tin, ngữ liệu phải được chuẩn hĩa về giống với tiêu chuẩn ngữ liệu dùng để tìm kiếm của hệ thống đĩ. Nhưng cũng chính điều này làm cho ngữ liệu của chúng tơi cĩ thể được sử dụng linh hoạt để đánh giá nhiều hệ thống tìm kiếm thơng tin cho nhiều thứ tiếng khác nhau. Điều này cịn cĩ ý nghĩa rất lớn trong tìm kiếm thơng tin vì chúng ta cĩ thể sử dụng hệ thống tìm kiếm hiệu quả của nước ngồi để tìm kiếm thơng tin tiếng Việt. 1.2.7. Phương pháp đánh giá tầm quan trọng của kết quả trả về Các độ đo thực hiện tồn bộ hệ thống tìm kiếm chủ yếu được lấy trung bình trên tập câu hỏi. Vì tính chất biến đổi của các câu hỏi là rất lớn, và sự thay đổi của các độ đo tính tốn là rất cao, nên địi hỏi một phương pháp phân tích thống kê thích hợp để đánh giá xem sự khác biệt được đo giữa các hệ thống cĩ phải là cĩ ý nghĩa thống kê đến một độ tin cậy nhất định khơng. Vì vậy, phương pháp đánh giá tầm quan trọng của kết quả trả về được sử dụng là phương pháp thống kê. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 22 Chương 2 : CƠ SỞ LÝ THUYẾT 2.1. Tìm kiếm thơng tin và các hệ thống tìm kiếm thơng tin 2.1.1. Lịch sử tìm kiếm thơng tin và hệ thống tìm kiếm thơng tin Tìm kiếm thơng tin cĩ một lịch sử lâu đời gắn liền với các thư viện và trung tâm tìm kiếm thơng tin. Trước đây, khi mà máy tính và internet chưa ra đời, những người cĩ nhu cầu thơng tin ngồi việc nhờ sự trợ giúp thơng tin từ bạn bè, người thân cịn cĩ thể tìm đến thư viện hoặc các trung tâm thơng tin để tìm kiếm thơng tin cần thiết. Cách biểu diễn, lưu trữ, tổ chức và phổ biến thơng tin của thư viện được xem là cách làm truyền thống của một hệ thống tìm kiếm thơng tin. Thư viện, khi tiếp nhận các yếu tố thơng tin hay tài liệu mới, trước hết là phân tích yếu tố thơng tin đĩ. Sau đĩ, những mơ tả thích hợp sẽ được chọn ra để mơ tả, phản ánh nội dung của yếu tố thơng tin đĩ. Dựa trên những mơ tả này, mỗi yếu tố thơng tin sẽ được phân loại theo những thủ tục đã được thiết lập rồi sáp nhập vào tập hợp các yếu tố thơng tin đã tồn tại. Các thủ tục này được tạo ra để hệ thống hĩa các yêu cầu (các yêu cầu được thiết kế để thay thế cho một nhu cầu thơng tin ) và để so sánh những yêu cầu, truy vấn đĩ với mơ tả của các yếu tố thơng tin đã lưu trữ. Việc so sánh này chính là cơ sở để quyết định các yếu tố thơng tin thích hợp với câu truy vấn tương ứng. Cuối cùng, một cơ chế tìm kiếm và phổ biến thơng tin sẽ được dùng để trả các yếu tố thơng tin cần thiết đến người sử dụng hệ thống. Tuy nhiên, chúng ta phải xem xét vấn đề nảy sinh về vị trí thật sự của một yếu tố thơng tin mới được thêm vào trong tập hợp tài liệu. Cĩ nhiều cơ chế tiếp cận khác nhau để giải quyết vấn đề này nhưng chúng đều liên quan đến cách tổ chức vật lý hoặc luận lý các yếu tố thơng tin. Trong thư viện, cách tổ chức vật lý chính là việc lập chỉ mục cho tài liệu, tức là sự sắp xếp các con số của các quyển sách, cách đánh số thường được quy định bởi các thư viện lớn. Những quyển sách sẽ được đặt vào những vị trí xác định dựa vào những con số này. Ngồi ra, cách tổ chức luận lý dữ liệu phải được thêm vào với cách tổ chức vật lý để giúp người sử SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 23 dụng tìm kiếm thơng tin dễ dàng hơn. Chẳng hạn, những quyển sách ấn bản về tìm kiếm thơng tin cĩ thể được xác định bằng cách nhìn vào danh mục các chủ đề của thư viện với thuật ngữ cần tìm là “tìm kiếm thơng tin”. Một khi ta tìm thấy thuật ngữ thích hợp, các thẻ số kế tiếp nhau sẽ xác định những quyển sách liên quan đến chủ đề đang tìm kiếm. Những quyển sách này phụ thuộc vào các con số và chúng sẽ được tìm thấy tại những vị trí xác định. Bên cạnh đĩ, mỗi khi muốn thay đổi thuật ngữ chủ đề của sách, chúng ta khơng cần thay đổi vị trí của sách trên kệ sách; tức là, các yếu tố thơng tin cĩ thể được tổ chức luận lý lại bằng cách thay đổi danh mục thư viện mà khơng cần thay đổi sắp xếp vật lý. Xã hội ngày càng phát triển do đĩ thơng tin rất đa dạng phong phú, bài tốn đặt ra là chúng ta phải làm sao để quản lý được số lượng thơng tin khổng lồ một cách cĩ hiệu quả. Từ đĩ dẫn đến nhu cầu làm giảm một lượng các yếu tố thơng tin đến một kích thước cĩ thể quản lý, các yếu tố thơng tin cịn lại được xem là cĩ liên quan nhiều nhất đến lĩnh vực tìm kiếm. Mặt khác, chúng ta rất khĩ dự đốn mẫu, trạng thái phát triển tương lai của thơng tin, hoặc nếu cĩ thể dự đốn thì tỉ lệ rủi ro rất cao. Khĩ khăn tiếp theo trong việc tổ chức thơng tin hiệu quả là ước muốn giữ những yếu tố liên quan gần nhau. Ví dụ, những chủ đề liên quan đến nhiều lĩnh vực như phân tích hệ thống (nĩ liên quan đến khoa học máy tính, vận trù học, kỹ thuật học, khoa học quản lý, giáo dục và các hệ thống thơng tin) khơng thể để gần nhau được mà phải để riêng ra theo từng lĩnh vực : đây là một khĩ khăn. Cịn rất nhiều khĩ khăn nữa, chẳng hạn các khĩ khăn trong phân loại, so sánh tài liệu, yếu tố thơng tin; lập chỉ mục, đánh số cho tài liệu. Và những khĩ khăn này sẽ khơng được giải quyết nếu khơng cĩ sự ra đời của máy tính. Quả thật, nhờ cĩ máy tính mà việc lưu trữ, tìm kiếm thơng tin trở nên dễ dàng hơn. Máy tính cĩ thể thao tác trên tất cả các loại thơng tin và cĩ thể lưu trữ một cách nhanh chĩng một số lượng thơng tin khổng lồ. Ngồi ra, cơ chế tìm kiếm thơng tin trên máy tính cĩ thể rất nhanh chĩng và hiệu quả tùy thuộc mơ hình cài đặt, thuật tốn của cơ chế đĩ. Cơ chế tìm kiếm này cũng khá giống với cơ chế tìm kiếm thơng tin của thư viện. Trước hết, dựa trên ngơn ngữ chỉ mục và các yếu tố thơng tin đại diện cho nội SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 24 dung của tài liệu, tập tài liệu sẽ được biểu diễn dưới dạng tập hợp các chỉ mục đại diện cho tập tài liệu đĩ. Trong khi đĩ, nhu cầu tìm kiếm thơng tin được biểu diễn dưới dạng câu truy vấn cĩ cấu trúc hoặc khơng cấu trúc mà máy cĩ thể hiểu được. Sau đĩ, máy sẽ so sánh hai dạng biểu diễn trên, biểu diễn tài liệu và biểu diễn câu truy vấn, để biết được tài liệu nào phù hợp với truy vấn nào. Sau khi so sánh, máy sẽ định vị được vị trí vật lý của yếu tố thơng tin cần tìm kiếm và phổ biến nĩ đến người sử dụng. Đây là cơ chế tìm kiếm chung cho mọi hệ thống tìm kiếm thơng tin. Tuy nhiên, cách đây khơng quá 20 năm, sau khi máy tính ra đời, các hệ thống tìm kiếm thơng tin chủ yếu được sử dụng trong phịng thí nghiệm để tìm kiếm một kho ngữ liệu sách và tài liệu. Mặc dù chúng khơng bao hàm các phương pháp tốn phức tạp, nhưng khi Internet phát triển thì kỹ thuật tìm kiếm chủ yếu trên World Wide Web chính là các kỹ thuật tìm kiếm thơng tin. Quả thật, các hệ thống tìm kiếm thơng tin ngày càng phát triển về thuật tốn, kỹ thuật tìm kiếm thơng tin nhờ cĩ sự ra đời của Internet. Vì nhu cầu tìm kiếm thơng tin của con người trên Internet là một nhu cầu phổ biến, thiết thực, khơng thể thiếu nên các nhà phát triển hệ thống tìm kiếm thơng tin cũng phải nỗ lực để mang lại hiệu năng, hiệu quả cho người sử dụng. Chúng ta thấy rõ ràng là nghiên cứu tìm kiếm thơng tin cĩ truyền thống tập trung vào tìm kiếm thơng tin dạng văn bản (Text Retrieval) hay tài liệu văn bản (Document Retrieval). Trong một thời gian dài, tìm kiếm thơng tin gần như đồng nghĩa với tìm kiếm tài liệu hay tìm kiếm văn bản. Trong thời gian gần đây, các viễn cảnh ứng dụng mới như ứng dụng trả lời câu hỏi (question answering), ứng dụng nhận dạng chủ đề (topic detection), hay ứng dụng lưu vết (tracking) trở thành các lĩnh vực hoạt động mạnh mẽ trong nghiên cứu tìm kiếm thơng tin. Càng ngày ranh giới giữa cộng đồng tìm kiếm thơng tin hay cộng đồng tìm kiếm thơng tin và các cộng đồng nghiên cứu xử lý ngơn ngữ tự nhiên, cộng đồng nghiên cứu cơ sở dữ liệu trở nên mờ nhạt khi các cộng đồng này cùng nhau phát triển các SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 25 lĩnh vực quan tâm chung; ví dụ như trả lời câu hỏi, tĩm tắt và tìm kiếm thơng tin từ các tài liệu cĩ cấu trúc. Một lĩnh vực phát triển khác mà các kỹ thuật tìm kiếm thơng tin đang kế tục và phát huy, đĩ là tìm kiếm thơng tin khơng văn bản hay cịn gọi là tìm kiếm thơng tin đa phương tiện. Loại hình tìm kiếm này sẽ dựa trên rút trích tự động các phần văn bản hay lời nĩi của các tài liệu đa phương tiện, sau đĩ được xử lý bởi các kỹ thuật tìm kiếm thơng tin dựa văn bản (text-based IR techniques). Tuy nhiên, người ta ngày càng quan tâm đến sự phát triển các kỹ thuật phơi bày cụ thể thơng tin phương tiện truyền thơng rồi tích hợp chúng với các phương pháp tìm kiếm đã được thiết lập tốt hơn là cách rút trích chúng tơi đã trình bày. Trong phạm vi đề tài, chúng tơi chỉ giới hạn tìm kiếm thơng tin trên văn bản. 2.1.2. Hệ thống tìm kiếm thơng tin 2.1.2.1. Khái niệm về hệ thống tìm kiếm thơng tin Theo lý thuyết, hệ thống tìm kiếm thơng tin là một hệ thống thơng tin. Nĩ được sử dụng để lưu trữ, xử lý, tra cứu, tìm kiếm, và phổ biến các yếu tố thơng tin đến người sử dụng. Hệ thống tìm kiếm thơng tin thường thao tác với các dữ liệu dạng văn bản và khơng cĩ sự giới hạn về các yếu tố thơng tin trong văn bản. Hệ thống thơng tin bao gồm một tập hợp các yếu tố thơng tin, một tập các yêu cầu, và một vài cơ chế tìm kiếm để quyết định yếu tố thơng tin nào liên quan đến các yêu cầu. Theo nguyên tắc, mối quan hệ giữa các câu truy vấn và tài liệu cĩ được từ sự so sánh trực tiếp. Nhưng trên thực tế, sự liên quan giữa các câu truy vấn và tài liệu xác định khơng phải được quyết định trực tiếp; mà gián tiếp bằng cách : các tài liệu, yếu tố thơng tin phải chuyển sang ngơn ngữ chỉ mục trước khi xác định mức độ liên quan. 2.1.2.2. Cách thức hoạt động của hệ thống tìm kiếm thơng tin Hình 1 minh họa cấu trúc, cách hoạt động cơ bản của một hệ thống tìm kiếm thơng tin cổ điển. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 26 Hình 1. Ở giai đoạn đầu tiên, giai đoạn tiền xử lý, tài liệu thơ của ngữ liệu được xử lý thành các tài liệu được tách từ, phân đoạn (tokenized documents) và sau đĩ được lập chỉ mục thành một danh sách các vị trí của từ (postings per terms). Ở giai đoạn thứ hai, người sử dụng đưa ra một câu truy vấn (phi cấu trúc bằng ngơn ngữ tự nhiên) mơ tả nhu cầu thơng tin của họ. Hệ thống tìm kiếm thơng tin sẽ biểu diễn câu truy vấn này thành những câu truy vấn cĩ hoặc khơng cĩ cấu trúc mà máy cĩ thể hiểu được. Hệ thống tìm kiếm thơng tin bắt đầu thực hiện chất vấn, đối chiếu để tìm ra tài liệu, các yếu tố thơng tin cĩ thể trả lời và liên quan đến câu truy vấn. Các thủ tục được dùng để quyết định các yếu tố thơng tin cĩ liên quan đến câu truy vấn đều dựa trên biểu diễn của các câu truy vấn và các yếu tố thơng tin cĩ chứa các thành phần ngơn ngữ chỉ mục. Cuối cùng, các tài liệu, yếu tố thơng tin được tìm thấy được hiển thị thành một danh sách tài liệu và được sắp xếp theo thứ tự liên quan (ranked retrieved documents). Thơng thường, những tài liệu, yếu tố thơng tin cĩ SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 27 liên quan nhiều nhất được xếp trên những tài liệu ít liên quan hơn. Tùy vào các hệ thống tìm kiếm thơng tin khác nhau mà chúng hiển thị thơng tin liên quan theo những cách khác nhau. Chẳng hạn, cĩ hệ thống chỉ hiển thị tên tiêu đề và đường dẫn đến tài liệu đĩ, hoặc cĩ hệ thống vừa hiển thị tên, đường dẫn, vừa hiển thị một ít nội dung liên quan đến câu truy vấn, hoặc cĩ những hệ thống phục vụ tìm kiếm thơng tin trên mạng thì thêm vào các liên kết đến các trang web khác nhau. Nhiều hệ thống thơng tin cịn cĩ cả cơ chế cho phép người sử dụng cung cấp phản hồi đến chất lượng của kết quả trả về. Sử dụng phản hồi, hệ thống cố gắng thích ứng và nỗ lực tìm ra những kết quả tốt nhất cho câu truy vấn. Việc lập chỉ mục trong giai đoạn tiền xử lý chúng tơi vừa đề cập về nguyên tắc thì giống nhau đối với từng hệ thống nhưng về thuật tốn, cách thức thì khác nhau. Nguyên tắc lập chỉ mục: Tài liệu hay yếu tố thơng tin phi cấu trúc khi thêm mới sẽ được hệ thống tìm kiếm thơng tin chuyển sang một thể đặc biệt, đĩ là ngơn ngữ chỉ mục. Việc chuyển đổi thành phần thơng tin thành ngơn ngữ chỉ mục được thực hiện thủ cơng, hay tự động hoặc cả hai và nĩ được gọi là tiến trình lập chỉ mục. Tiến trình lập chỉ mục này được thực hiện dựa trên các yếu tố thơng tin đại diện cho nội dung của tài liệu. Do đĩ, kết quả của tiến trình này là một tập chỉ mục đại diện cho tài liệu đĩ. 2.1.2.3. Các phương tiện tìm kiếm thơng tin (Search Engines) Hình 2 minh họa cấu trúc cơ bản của các phương tiện tìm kiếm. Một phương tiện tìm kiếm là một hệ thống tìm kiếm thơng tin, tuy nhiên, nĩ khơng giống hồn tồn với hệ thống tìm kiếm thơng tin cổ điển đã mơ tả ở trên. Sự khác biệt giữa các hệ thống tìm kiếm thơng tin cổ điển và các phương tiện tìm kiếm bắt nguồn từ sự khác biệt nguồn gốc dữ liệu, cĩ nghĩa là một kho lưu trữ khép kín được định nghĩa tốt trái ngược với World Wide Web. Vì khơng cĩ cách tiếp cận trực tiếp đến các tài liệu trên Web (như là cĩ trong kho ngữ liệu thư viện), phương tiện tìm kiếm phải cần đến thành phần crawler ( tạm gọi là đường chạy của xích). Thành phần SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 28 phần mềm này chịu trách nhiệm lấy các trang web về và lưu trữ chúng trong một kho nội bộ. Cơ chế crawling (đường chạy của xích) đưa ra các thách thức cơng nghệ liên quan đến hiệu năng của quá trình và đến sự liên quan của tài liệu – vì các trang web là động, nên crawler phải giữ cho kho nội bộ luơn được cập nhật hằng ngày. Việc crawling các tài liệu ngồi Web thì khơng đủ bởi vì dữ liệu web gồm cĩ nhiều thơng tin dư thừa. Phân tích tồn cục cĩ trách nhiệm loại bỏ dữ liệu khơng quan trọng như các trang Web giống nhau và các trang bao gồm sách báo khơng lành mạnh. Ngồi ra, phân tích tồn cục cũng chịu trách nhiệm tính tốn tồn cục được dùng trong các hệ thống tìm kiếm thơng tin như sắp xếp thứ tự trang (thứ tự trang hầu hết được xác định bởi những trang cĩ liên kết với nĩ và những trang nĩ liên kết tới). Hình 2. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 29 2.1.3. So sánh tìm kiếm thơng tin cổ điển và tìm kiếm thơng tin trên Web Bảng dưới đây biểu diễn sự khác biệt giữa các hệ thống tìm kiếm thơng tin cổ điển (IR cổ điển) và các hệ thống tìm kiếm thơng tin Web (Web IR). IR cổ điển Web IR Kích thước Lớn Khổng lồ Chất lượng dữ liệu Sạch, khơng trùng lắp Lộn xộn, trùng lắp Tỉ lệ thay đổi dữ liệu Hiếm Liên tục Khả năng truy cập dữ liệu Cĩ thể Truy cập một phần Đa dạng định dạng Đồng nhất, cùng nguồn gốc Rất đa dạng Tài liệu Văn bản HTML # liên quan Nhỏ Lớn Kỹ thuật IR Dựa nội dung Dựa liên kết Khối lượng dữ liệu trong một hệ thống IR cổ điển khá lớn, trong khi đĩ khối lượng dữ liệu này trong hệ thống Web IR là khổng lồ. Khác biệt lớn nhất trong khối lượng dữ liệu, chính là các thứ tự của lượng, ảnh hưởng đến phần cứng được địi hỏi (một máy tính thì khơng bao giờ đủ, bộ nhớ khơng thể chứa tồn bộ dữ liệu) và các thuật tốn (các định nghĩa hiệu năng của thời gian và khơng gian bị thay đổi). Một khác biệt nữa là khác biệt của dữ liệu. Trong hệ thống IR cổ điển dữ liệu được làm sạch, trong khi đĩ dữ liệu trên Web IR thì phức tạp, cả hai đều do sự trùng lắp vơ ý và do các spam cĩ dụng ý tăng thứ hạng của trang đĩ hoặc chỉ tạo sự lộn xộn . Như đã đề cập ở trên, sự thay đổi dữ liệu trong IR cổ điển là khơng thường xuyên ,do đĩ nĩ thường được lập chỉ mục 1 lần. Ngược lại, dữ liệu trên Web thì SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 30 thay đổi thường xuyên nên chỉ mục cũng cần được cập nhật. Hơn nữa, tính khả truy cập của dữ liệu là khơng quan trọng trong Web IR. Tài liệu trong IR cổ điển thường đồng nhất về định dạng cịn tài liệu trong Web IR gồm nhiều loại khác nhau: bất cứ ai cũng cĩ thể tạo một trang web trong bất kì định dạng nào và bất kì ngơn ngữ nào. Một điểm khác biệt quan trọng nữa là tài liệu web khơng thường xuyên được viết ở dạng văn bản thơ như trong tài liệu IR cổ điển. Trang Web thường được viết bằng HTML (Hypertext Markup Language) , vừa cĩ những lợi ích và bất lợi đối với hệ thống tìm kiếm thơng tin : một mặt, nĩ bao gồm dữ liệu cĩ cấu trúc giúp việc phân tích dễ dàng hơn ; mặt khác, nĩ thường khơng chứa nhiều văn bản (hệ thống IR dựa trên thứ này), do đĩ khĩ phân loại hơn. Kết quả trả về trong Web IR cũng nhiều hơn so với IR cổ điển, do đĩ khĩ để sắp thứ tự danh sách kết quả hơn. Và cuối cùng, IR cổ điển sử dụng kĩ thuật sắp thứ tự chỉ dựa trên nội dung (content-based). Tuy nhiên, kĩ thuật này khơng thể áp dụng với Web IR. Nĩ đã từng là một kĩ thuật thơng dụng cho đến khi Google giới thiệu kĩ thuật sắp thứ tự mới dựa trên liên kết (link-based) . Kĩ thuật sắp thứ tự dựa trên liên kết sử dụng siêu liên kết (hyperlink) giữa các tài liệu web để sắp thứ tự các trang web một cách hiệu quả và chắc chắn hơn. 2.1.4. So sánh tìm kiếm thơng tin với tìm kiếm dữ liệu Một hệ thống tìm kiếm thơng tin khơng phải là một hệ thống tìm kiếm dữ liệu. Bảng dưới đây trình bày một số thuộc tính khác nhau giữa hệ thống tìm kiếm thơng tin và hệ thống tìm kiếm dữ liệu. Tìm kiếm thơng tin Tìm kiếm dữ liệu Dữ liệu Văn bản tự do, khơng cấu trúc Các bảng dữ liệu, cĩ cấu trúc Truy vấn Từ khĩa, ngơn ngữ tự nhiên SQL, đại số quan hệ Kết quả Liên quan tương đối, xấp xỉ Liên quan chính xác SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 31 Kết quả Sắp xếp theo mức độ liên quan Khơng sắp xếp Truy cập Những người khơng phải chuyên gia Người sử dụng cĩ kiến thức hoặc các tiến trình tự động Hệ thống tìm kiếm thơng tin thu thập tài liệu dựa trên yêu cầu thơng tin của người dùng. Câu truy vấn trên dữ liệu khơng cĩ cấu trúc (thường là dạng văn bản tự do), sử dụng từ khĩa hoặc ngơn ngữ tự nhiên và do vậy cĩ thể được viết bởi người dùng khơng thơng thạo. Vì cú pháp của câu truy vấn khơng được định nghĩa chính xác nên kết quả cĩ thể bao gồm các kết hợp khơng chính xác và thứ tự liên quan hay tương quan (relevance) của chúng chỉ là gần đúng. Hệ thống tìm kiếm dữ liệu thu thập một tập hợp các tài liệu phù hợp về mặt cú pháp với câu truy vấn của người sử dụng. Câu truy vấn trên dữ liệu cĩ cấu trúc ( hường là bảng trong cơ sở dữ liệu) và thường sử dụng một ngơn ngữ truy vấn được định nghĩa hồn chỉnh như là SQL hay đại số quan hệ. Người sử dụng phải quen thuộc với cú pháp và hiểu được ngữ nghĩa của ngơn ngữ truy vấn. Vì vậy, câu truy vấn thường được viết bởi người am hiểu hoặc một quá trình tự động. Kết quả trả về bao gồm tất cả các tài liệu chính xác phù hợp với ngữ nghĩa của câu truy vấn, thứ tự bất kì. 2.1.5. Cơng thức trừu tượng trong tìm kiếm thơng tin Gọi D là tập hợp các tài liệu và Q là tập hợp các câu truy vấn. Hàm f: D × Q → R là hàm tính độ tương quan của một cặp (tài liệu, câu truy vấn) bởi mức độ tương quan của tài liệu đối với câu truy vấn. Đối với mỗi câu truy vấn q trong Q , f chỉ ra một thứ tự ( riêng phần) qπ trên D. Hoạt động của một hệ thống tìm kiếm thơng tin bao gồm 2 pha chính. Trong suốt pha đầu tiên, D được tiền xử lí và chỉ mục I được tạo ra tương ứng. Trong pha thứ 2 , cho trước một câu truy vấn trong Q, I được dùng để xuất ra một hốn vị π trên D. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 32 Mục tiêu chính của một hệ thống tìm kiếm thơng tin là xuất ra một hốn vị π gần với qπ bằng cách sử dụng một chỉ mục đặc và phản hồi trong một thời gian ngắn. Chẳng hạn, chúng ta khơng muốn đạt độ chính xác cao bằng cách sử dụng chỉ mục lớn trong đĩ bao gồm một hốn vị trên D cho mỗi câu truy vấn cĩ thể cĩ hoặc bằng cách duyệt tồn bộ chỉ mục cho mỗi câu truy vấn. Chúng ta sử dụng khái niệm tokens để biểu diễn tài liệu. Đặt T là khơng gian tokens. Khơng gian tokens cĩ thể bao gồm , ví dụ như là :tồn bộ từ trong tiếng Anh, một tập hợp các cụm từ hoặc một tập hợp các URLs. Chúng ta định nghĩa một tài liệu là một vec-tơ thực d trong kR (k là số tokens trong khơng gian tokens). Goị id là trọng lượng của it trong d. Cĩ rất nhiều cách để tính id ,cách dễ nhất là tính số lần xuất hiện của it trong d. 2.1.6. Các mơ hình tìm kiếm thơng tin cổ điển để sắp thứ tự liên quan Nghiên cứu tìm kiếm thơng tin dựa trên rất nhiều mơ hình khác nhau. Ở đây, chúng tơi xin nêu ra hai mơ hình được sử dụng nhiều nhất. 2.1.6.1. Mơ hình Đại số Bool Mơ hình liên quan (relevance) cơ bản nhất trong hệ thống tìm kiếm thơng tin cổ điển là mơ hình Đại số Bool hay Boolean. Một tài liệu được định nghĩa là một vec-tơ boolean d trong (trọng lượng boolean) trong đĩ id =1 khi id cĩ mặt trong d. Một câu truy vấn được định nghĩa là một cơng thức boolean q trên các tokens :q: k}1,0{ → {0,1} .Nghĩa là, q là một hàm mà khi cho trước một vec-tơ trong k}1,0{ biểu diễn một tài liệu thì sẽ trả về một giá trị boolean phụ thuộc vào độ liên quan giữa tài liệu và câu truy vấn. Hàm tính độ liên quan được định nghĩa đơn giản bằng cách áp dụng hàm này trên một tài liệu, f(d,q) = q(d). Ví dụ như ,một câu truy vấn trong mơ hình boolean cĩ thể là “Micheal Jordan” AND (Not basketball). Lợi ích chính của mơ hình boolean là tính đơn giản cho người sử SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 33 dụng, tuy nhiên hàm tính độ liên quan của nĩ quá tồi khi nĩ chỉ trả về một giá trị boolean. 2.1.6.2. Mơ hình khơng gian vec-tơ Mơ hình thơng dụng trong hệ thống tìm kiếm thơng tin cổ điển dùng để sắp thứ tự liên quan là mơ hình khơng gian vectơ hay vec-tơ (VSM). Một tài liệu là một vec-tơ thực d trong kR (trọng lượng thực), id được xác định dựa trên một hàm tính tốn, thường là điểm TF-IDF (sẽ được đề cập sau trong phần này). Tương tự như một tài liệu, một câu truy vấn cũng là một vec-tơ thực trong kR trong đĩ iq là trọng lượng của it trong q. Hàm tính độ liên quan là f(d,q) = sim (d,q) trong đĩ sim(d,q) là mức độ giống nhau giữa d và q. Tiếp theo chúng ta sẽ phương thức để đo sự giống nhau của một vec-tơ tài liệu và một vec-tơ truy vấn, sau đĩ trình bày điểm TF-IDF dùng để tính trọng lượng của tokens trong tài liệu. Trực giác cĩ thể dẫn ta đến cách định nghĩa sự giống nhau giữa một vec-tơ tài liệu và một vec-tơ truy vấn bằng vec-tơ khác biệt của chúng (hình bên dưới) Phương thức này sẽ gán một trọng lượng đáng kể cho các tokens xuất hiện trong tài liệu nhưng khơng xuất hiện trong câu truy vấn. Vec-tơ truy vấn thường thưa thớt hơn nhiều so với vec-tơ tài liệu, vì vậy một phương thức tốt hơn nên loại bỏ hiệu ứng của các tokens khơng xuất hiện trong câu truy vấn. (a) Vec-tơ khác nhau (b) Cosin Hình biểu diễn độ tương tự của vec-tơ tài liệu d và vec-tơ truy vấn q SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 34 Phương thức đo sự giống nhau cosine (hình 5b) dựa trên quan sát ở trên, là phương thức thơng dụng để đo sự giống nhau giữa một vec-tơ tài liệu và một vec- tơ truy vấn. Chú ý là nếu gĩc giữa 2 vec-tơ nhỏ thì cosine gần tới 1, là giá trị lớn nhất của sự giống nhau. Nếu 2 vec-tơ gần như vuơng gĩc thì cosine gần tới khơng,nghĩa là sự giống nhau nhỏ nhất. TF-IDF là phương pháp thơng dụng để “cân nặng” (đánh giá) các thuật ngữ (term) trong một tài liệu. Ý tưởng cơ bản của phương pháp này là xem xét tính phổ biến của một thuật ngữ trong một tài liệu khi so sánh với tính phổ biến của thuật ngữ đĩ trong các tài liệu khác. Ví dụ như , xem xét một tài liệu 1d cĩ 100 thuật ngữ, 10 trong số đĩ là “java” và một tài liệu 2d cĩ 100000 thuật ngữ, 10 trong số đĩ là “java”. Vì tần số xuất hiện (tính phổ biến) của thuật ngữ “java” trong 1d cao hơn đáng kể so với trong 2d nên trọng lượng của thuật ngữ “java” trong 1d phải cao hơn trong 2d .Bây giờ xem xét một sự thật là thuật ngữ “the” ,cũng xuất hiện 10 lần trong 1d . Vì nĩ là một thuật ngữ thơng dụng trong các tài liệu nên nĩ khơng nên cĩ trọng lượng bằng thuật ngữ “java” mặc dù mức độ phổ biến của chúng là như nhau. Định nghĩa chính qui của điểm TF-IDF cho một tài liệu được định nghĩa như sau. Gọi n(d, it ) là số lần xuất hiện của it trong d và ),(∑= i itdnN là tổng số tokens trong d. iD chỉ số tài liệu chứa it và D là tổng số tài liệu cĩ trong tập hợp. Tần số thuật ngữ ( term frequency) TF (d, it ) ,là tần số xuất hiện của it trong d. Cĩ một vài cách để tính tần số thuật ngữ. 2 cách thơng dụng nhất là chia số lần xuất hiện của token trong tài liệu cho hoặc là tổng số token cĩ trong tài liệu hoặc là số lần xuất hiện của token xuất hiện nhiều nhất trong tài liệu: SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 35 Trong bất kì trường hợp nào, thuật ngữ xuất hiện nhiều hơn sẽ cĩ điểm TF cao (cao nhất là 1) và thuật ngữ ít xuất hiện sẽ cĩ điểm TF gần bằng 0. Ngược lại, IDF( it ) (Inverse Document Frequency) là tần số nghịch đảo của it trong tất cả các tài liệu cĩ trong tập hợp. Nĩ thường được đo bằng loga của tỉ số giữa tổng số tài liệu cĩ trong tập hợp và số tài liệu trong tập hợp cĩ chứa it . IDF ( it ) = log ( D / iD ) Chú ý là hàm loga được áp dụng chỉ vì những lí do số học. Thuật ngữ thường xuyên xuất hiện trong tài liệu như là “the” vì vậy sẽ cĩ điểm IDF gần bằng 0 và thuật ngữ hiếm gặp sẽ cĩ IDF gần bằng 1. Điểm TF-IDF được tính bằng cách nhân điểm TF và điểm IDF: TF-IDF (d, it ) = TF (d, it ) × IDF ( it ) Qua cơng thức trên, ta cĩ thể thấy rằng TF-IDF sẽ cho điểm một thuật ngữ cao hơn nếu nĩ xuất hiện thường xuyên trong một tài liệu và khơng xuất hiện thường xuyên trong các tài liệu khác. Mơ hình khơng gian vec-tơ , thường xuyên sử dụng TF-IDF để đánh giá các thuật ngữ và hàm cosine là hàm đo mức độ giống nhau, thể hiện là một phương thức tính độ liên quan giữa một tài liệu và một câu truy vấn tin cậy hơn mơ hình boolean ở trên. Bên cạnh đĩ, VSM cĩ những hiện thực hiệu quả và thể hiện hiệu suất tốt trong thực tế. Nhược điểm chính của phương pháp này là nĩ giả định các thuật ngữ độc lập nhau. Trong thực tế, các thuật ngữ thường cĩ liên quan với nhau và hiểu được điều này cĩ thể dẫn đến việc tính độ liên quan tốt hơn. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 36 2.2. Đánh giá các hệ thống tìm kiếm thơng tin 2.2.1. Nền tảng đánh giá các hệ thống tìm kiếm thơng tin Một trong những giới thiệu tốt nhất về đánh giá các hệ thống tìm kiếm thơng tin cĩ trong chương 7 của [ 5 ] . Ở đây, chúng tơi tập trung chủ yếu vào những gì cĩ thể được đánh giá trong tìm kiếm thơng tin. Mức độ bao phủ của bộ ngữ liệu: mở rộng đến mức hệ thống bao gồm các thành phần liên quan. Vì vậy, mức độ bao phủ của tài liệu phải xử lý với vấn đề chất lượng của bộ ngữ liệu. Điều này quan trọng trong tìm kiếm thơng tin dạng Web vì mỗi phương tiện tìm kiếm (Search engine) được biết là cĩ thể bao phủ 16% khơng gian Web. Hiệu năng: Khoảng thời gian trung bình giữa thời gian một yêu cầu được đưa ra và câu trả lời được trả về. Hiệu năng được xem như thời gian thực hiện tìm kiếm, sử dụng bộ nhớ, v.v .. Biểu diễn của kết quả trả về. Kết quả liên quan đến người dùng trong việc lấy câu trả lời cho một yêu cầu. Độ bao phủ của hệ thống: tỉ lệ các tài liệu liên quan được trả về. Độ chính xác của hệ thống :tỉ lệ các tài liệu trả về thật sự liên quan. Cả độ bao phủ và độ chính xác đều liên quan đến hiệu quả tìm kiếm. Trong đề tài luận văn của chúng tơi, chúng tơi tập trung vào hai khía cạnh cuối cùng (độ bao phủ, độ chính xác của hệ thống) vì chúng chiếm ưu thế nhiều nhất trong đánh giá các hệ thống tìm kiếm thơng tin. Hai khía cạnh này là một phần của mơ hình đánh giá hướng hệ thống mà chúng tơi đã đề cập trong phần tổng quan. Chúng tơi xin được nĩi rõ hơn về mơ hình này. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 37 2.2.2. Mơ hình đánh giá hướng hệ thống Kỹ thuật của hướng đánh giá tìm kiếm hướng hệ thống và các độ đo khả năng thực thi kết hợp của nĩ được phát triển trong một số lượng các dự án nghiên cứu thời gian dài : Cranfield , MEDLARS, SMART, STAIRS và TREC. Ý tưởng chính là để đo khả năng thực hiện của hệ thống tìm kiếm thơng tin bằng cách chạy một tập các câu hỏi trong bộ ngữ liệu dùng để đánh giá, được chỉ mục bởi hệ thống và lưu lại kết quả. Đối với mỗi câu truy vấn, cĩ thể tính được độ chính xác và độ bao phủ của tập kết quả được lưu lại. Như đã được định nghĩa ở chương 1, độ chính xác (precision) là tỉ lệ của tập tài liệu liên quan được trả về so với tập tài liệu kết quả, độ bao phủ (recall) là tỉ lệ của tập tài liệu liên quan được trả về trên tổng số tài liệu liên quan. Những định nghĩa chính xác hơn của phần này và các độ đo liên quan sẽ được trình bày ở mục 2.2.3. 2.2.2.1. Từ Cranfield đến TREC Dự án Cranfield do Cleverdon thực hiện thường được đánh giá như là mơ hình chủ lực của TREC. Cleverdon tạo ra các cuộc kiểm thử Cranfield, Cranfield chủ yếu được dùng trong thí nghiệm với mục đích chính là xem xét, đánh giá các hàm, chức năng lập chỉ mục khác nhau thực hiện khác nhau như thế nào. Mục đích chính là xác định thuật tốn nào là tối ưu nhất, phù hợp nhất với các tiêu chuẩn đo lường và độ đo. Từ đĩ truyền thống nghiên cứu thử nghiệm hướng hệ thống ra đời. Salton ở Hoa Kỳ là người đầu tiên mở rộng phương pháp thử nghiệm cho đánh giá các thuật tốn tìm kiếm thơng tin theo mơ hình Khơng gian Vec-tơ [6] . Ơng bắt đầu nghiên cứu tìm kiếm thơng tin tại Đại học Harvard năm 1961. Ơng muốn phát triển một khung làm việc (framework) cho so sánh khả năng lập chỉ mục và các kỹ thuật tìm kiếm thơng tin của hệ thống. Khung làm việc được thực hiện bởi một loạt các thuật tốn và được biết đến như là hệ thống SMART. Dự án SMART cĩ lẽ là nghiên cứu tìm kiếm thơng tin kéo dài nhất cho đến ngày hơm nay, trong khoảng thời gian từ 1961 đến khi Salton mất năm 1996, nhĩm SMART đã thử nghiệm nhiều khía cạnh của tìm kiếm thơng tin: đánh giá thuật ngữ (term SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 38 weighting), mở rộng câu hỏ (query expansion), phản hồi tương quan (relevance feedback), phân lớp (clustering) v.v. Tất cả các thử nghiệm đều dựa trên hệ thống tìm kiếm thơng tin SMART, chi tiết của hệ thống này sẽ được trình bày ở mục 3.1.4.1. Dự án SMART đạt được kết quả tốt nhất trong mơ hình Khơng gian vec-tơ trực quan và hiệu quả. Chương trình TREC đang tiến hành hiện nay đã được thơi thúc bởi các nghiên cứu Cranfield và SMART. TREC bắt đầu năm 1992 với hai nhiệm vụ chính: nghiên cứu “ad-hoc” và nghiên cứu “routing”. Kể từ đĩ, nhiều nhiệm vụ mới được kiểm tra trong nhiều track khác nhau. Ưu điểm chính của TREC là kích thước của ngữ liệu dùng để đánh giá thực tế hơn những dự án khác và việc đánh giá thì mở cho bất kỳ nhĩm nghiên cứu nào. Những người tham gia vào TREC qua các năm tăng lên một cách nhanh chĩng. Số lượng cĩ ý nghĩa các nhĩm tham gia mỗi năm, bảo đảm sự ổn định và cĩ thể so sánh qua các năm. TREC sử dụng ủy ban đánh giá từ Viện Quốc gia về Tiêu chuẩn và Cơng nghệ Hoa Kỳ (National Institute of Standard and Technology - NIST) để thực hiện đánh giá. Nghiên cứu STAIR là một trong những nghiên cứu đầu tiên phát triển thủ tục mới để đo độ bao phủ, bởi vì kích thước lớn của ngữ liệu làm cho việc tạo bảng Đánh giá liên quan chuẩn quá tốn nhiều chi phí. TREC cũng bố trí các độ đo bao phủ của nĩ trên việc xem xét một tập nhỏ các tài liệu (pool - gọi là “hồ” hay tập hợp xác định) nhưng sử dụng các phương pháp khác nhau để tạo nĩ. Tập hợp xác định này được tạo từ một mẫu các việc chạy hệ thống tìm kiếm khác nhau (càng khác nhau càng tốt). Đối với mỗi câu truy vấn, danh sách các tài liệu trả về được kết hợp với nhau bằng cách trộn vào nhau và loại bỏ các tài liệu lặp lại. Kết quả là một danh sách các tài liệu thống nhất. Cuối cùng, người đánh giá xem lại để đánh giá là các tài liệu trong danh sách này (cĩ một danh sách các câu hỏi) cĩ thật sự liên quan đến câu hỏi tương ứng khơng. Ảnh hưởng của TREC trong tìm kiếm thơng tin là rất lớn và chất lượng của bộ ngữ liệu kiểm tra là rất tốt vì cĩ nhiều hệ thống tham gia đĩng gĩp vào tập hợp xác định các tài liệu và do tính chất tiếp tục của chương trình TREC. TREC đã tạo SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 39 ra một tài sản lớn bộ ngữ liệu dùng để đánh giá mà cĩ thể được dùng trong số lượng lớn các thử nghiệm được kiểm sốt. Ưu điểm lớn của các thử nghiệm được kiểm sốt là nĩ cĩ thể được lặp lại. Trước khi TREC ra đời, cĩ nhiều bộ ngữ liệu kiểm tra nhỏ, rất khĩ để so sánh các phương pháp giữa các nhĩm khác nhau. Tình trạng này ngăn cản sự phát triển của đánh giá các hệ thống tìm kiếm thơng tin. TREC cĩ mục tiêu là xây dựng một số lượng các bộ ngữ liệu đánh giá lớn cho tìm kiếm thơng tin, chủ yếu là để thực hiện đánh giá dưới các điều kiện được kiểm sốt và cho phép thực hiện lại việc đánh giá. Nhìn vào những kết quả mà các nhĩm tham gia TREC từ khi TREC bắt đầu, chúng ta cĩ thể thấy một sự tiến bộ đáng kể. Chi tiết về TREC sẽ được giới thiệu trong mục 2.2.4 . 2.2.2.2. Thủ tục đánh giá Phương pháp thử nghiệm hướng hệ thống được thực hiện qua các bước phân biệt sau: • Trước hết, xây dựng một bộ ngữ liệu dùng để đánh giá. Bộ ngữ liệu dùng để đánh giá gồm cĩ tập các tài liệu mẫu, tập câu truy vấn mẫu, và bảng đánh giá liên quan chuẩn. Theo lý thuyết, mỗi kết hợp câu truy vấn-tài liệu đều được kiểm tra liên quan. Nhưng trên thực tế, chỉ một phần tập tài liệu được xem xét cho mỗi câu truy vấn. • Các hệ thống tìm kiếm thực hiện tìm kiếm trên bộ ngữ dùng để đánh giá: lập chỉ mục tập tài liệu, tạo các câu hỏi từ chủ đề (topic), tạo bảng liên quan cĩ thứ tự các tài liệu cho mỗi câu hỏi. • Đánh giá các độ đo thực hiện: Các độ đo cổ điển là độ bao phủ và độ chính xác, nhưng cĩ một số lượng lớn các độ đo khác. Đĩ là độ đo trung bình nghiêm ngặt (Mean average precision). • Đánh giá tầm quan trọng của kết quả trả về bằng phương pháp thống kê. Các độ đo thực hiện tồn bộ hệ thống tìm kiếm chủ yếu được lấy trung bình SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 40 trên tập câu hỏi. Vì tính chất biến đổi của các câu hỏi là rất lớn, và sự thay đổi của các độ đo tính tốn là rất cao, nên địi hỏi một phương pháp phân tích thống kê thích hợp để đánh giá xem sự khác biệt được đo giữa các hệ thống cĩ phải là cĩ ý nghĩa thống kê đến một độ tin cậy nhất định khơng. 2.2.2.3. Đánh giá sự liên quan Trong đánh giá các hệ thống tìm kiếm thơng tin theo kiểu của TREC, cĩ hai giả định quan trọng, mà khơng cĩ trong các thiết lập ở thế giới thực : • Sự liên quan hồn tồn theo khái niệm: một tài liệu chỉ cĩ thể là liên quan hoặc khơng liên quan. • Sự liên quan của một tài liệu hồn tồn độc lập với các tài liệu khác. Các giả định này làm đơn giản việc đo các hệ thống tìm kiếm. Nhiều nhà nghiên cứu đã thử nghiệm với nhiều tỉ lệ khác nhau của sự liên quan. Các tỉ lệ này được trình bày rõ hơn trong mục 2.2.3.4. Giả định về sự liên quan của một tài liệu hồn tồn độc lập với các tài liệu khác khơng thực tế trong hầu hết các trường hợp. Trong hầu hết các trường hợp tìm kiếm thơng tin cơ bản, chẳng hạn tìm kiếm thơng tin trên web, những người tìm kiếm muốn tìm một câu trả lời cho một câu hỏi xác định hay một vài tham khảo. Giả sử rằng người sử dụng sẽ bắt đầu duyệt qua các tài liệu được tìm thấy bắt đầu từ những tài liệu liên quan nhất, các tài liệu ít liên quan hơn thì phụ thuộc vào tài liệu liên quan đã đọc. Xác suất cĩ tài liệu mới giảm dần theo danh sách tài liệu. Sự phụ thuộc này thường bị bỏ qua bởi các nhà nghiên cứu tìm kiếm thơng tin. Cĩ nhiều mối quan tâm về tính chủ quan của thủ tục đánh giá. Con ngừơi thường cĩ những ý kiến khác nhau về sự liên quan. Điều này cĩ ảnh hưởng xấu đến sự phát triển của các đánh giá của TREC. Tuy nhiên, đã cĩ nhiều nghiên cứu để giải quyết vấn đề này và thấy rằng ảnh hưởng trên tập các hệ thống cĩ kết quả sắp thứ tự liên quan thì cĩ thể bỏ qua. Một nghiên cứu gần đây liên quan đến bộ ngữ liệu để đánh giá của TREC kiểm thử nhiều vấn đề khác nhau: • Đánh giá bởi tác giả khác với khơng phải tác giả SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 41 • Đánh giá một bảng khác với đánh giá nhĩm bảng đánh giá • Đánh giá trong cùng một mơi trường khác với đánh giá nhiều mơi trường Những yếu tố này ảnh hưởng đến giá trị tuyệt đối của các độ đo khả năng thực hiện, nhưng thứ tự liên quan của các hệ thống vẫn ổn định. 2.2.3. Thực hiện đo khả năng tìm kiếm Các độ đo cổ điển cho khả năng tìm kiếm của các thử nghiệm hệ thống thơng tin là độ bao phủ và độ chính xác. Trong những phần tiếp theo, chúng tơi mơ tả các thủ tục để đo độ chính xác và độ bao phủ và tính độ đo cho các hệ thống tìm kiếm cĩ kết quả được sắp thứ tự trong tình huống khơng thể đánh giá tất cả các tài liệu trong bộ ngữ liệu kiểm tra. Từ độ bao phủ và độ chính xác, chúng tơi dùng phương pháp tính độ chính xác dựa trên 11 điểm của độ bao phủ để tính độ chính xác. Kết quả trả về từ phương pháp này là một bảng biến thiên của độ chính xác và độ bao phủ hay là một hàm số của độ chính xác dựa trên độ bao phủ. Cĩ thể biểu diễn đồ thị liên hệ giữa độ chính xác và độ bao phủ từ hàm số này để cho biết hiệu quả trả về của hệ thống một cách trực quan, và cĩ thể so sánh nhiều hệ thống với nhau dựa trên đồ thị. 2.2.3.1. Các khái niệm về độ đo và liên quan ƒ Tính liên quan của tài liệu (relevant ): Một tài liệu được gọi là cĩ liên quan khi nội dung của tài liệu đĩ cĩ đề cập đến vấn đề mà câu truy vấn của người dùng quan tâm. ƒ Độ bao phủ (Recall - R): Cho biết khả năng của hệ thống tìm kiếm được những tài liệu cĩ liên quan. ƒ Độ chính xác (Precision - P): Cho biết khả năng của hệ thống tìm được những tài liệu chính xác ƒ Khả năng loại bỏ: (Fall out - F): Cho biết khả năng của hệ thống loại bỏ những tài liệu khơng liên quan SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 42 2.2.3.2. Cách tính độ bao phủ (R) và độ chính xác (P) ƒ Độ bao phủ (R): ƒ Độ chính xác (P): ƒ Khả năng loại bỏ: (Fall out - F): Tập tài liệu trả về Tập tài liệu trả về cĩ liên quan Tập tài liệu cĩ liên quan Tập dữ liệu về tài liệu Cĩ liên quan Khơng liên quan (Relevant) (non- relevant) Tìm thấy (retrieved) Khơng tìm thấy (not retrieved) B A A ∩ B A ∩ ∩ ∩ B R = A ∩ B B ( 1 ) P = A ∩ B A ( 2 ) F = ∩B ( 3 ) A ∩ B A B SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 43 ™ Mối liên hệ giữa R, P, F: G : là nhân tố tổng quát đo độ dày đặc của tài liệu liên quan trong tập dữ liệu Ù G cho biết độ liên quan của tài liệu so với câu truy vấn là cao hay thấp ™ Vấn đề đo độ bao phủ: Tính độ bao phủ là một vấn đề khĩ khăn trong việc đánh giá hệ thống tìm kiếm thơng tin bởi vì nĩ liên quan đến việc định giá thủ cơng tổng số tài liệu liên quan trong tập tài liệu đối với mỗi câu truy vấn (vấn đề tạo bảng liên quan lý thuyết) , việc định giá như vậy rất tốn kém nếu tập dữ liệu lớn. Để giải quyết vấn đề này người ta đưa ra phương pháp “pooling”.Ý tưởng của phương pháp “pooling” là trong danh sách tài liệu trả về chỉ lấy n tài liệu đầu, n được gọi là chiều dài của “pool”. Việc tạo bảng liên quan lý thuyết áp dụng phương pháp “pooling” được tiến hành như sau: tiến hành tìm kiếm trên nhiều hệ thống áp dụng phương pháp “pooling”, cĩ thể tài liệu liên quan được trả về của một hệ thống là cao, ta tiến hành giao các tập tài liệu liên quan trả về của các hệ thống đĩ và chỉ lấy n tài liệu đầu. Bởi vì tập kết quả trả về được sắp xếp theo thứ tự nên độ chính xác và độ bao phủ cĩ thể tính được tại các ngưỡng vị trí thứ tự thứ i tài liệu. ™ Vấn đề bảng liên quan thực tế Đối với cách tính trên ta phải quan niệm về độ liên quan của tài liệu trên 2 mức độ : hoặc là tài liệu cĩ liên quan hoặc là tài liệu khơng liên quan. Cách G = A S Với S là tập tài liệu F = R * G R * G + F* (1-G) ( 4 ) ( 5 ) SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 44 quy ước như vậy nhằm làm đơn giản hố cách đánh giá. Trên thực tế , độ liên quan của tài liệu khơng chỉ là 2 mức độ mà cĩ thể cĩ nhiều mức độ. 2.2.3.3. Phương pháp tính độ chính xác dựa trên 11 điểm chuẩn của độ bao phủ 2.2.3.3.1. Đồ thị biểu diễn hiệu suất thực thi hệ thống tìm kiếm ƒ Ứng với 1 câu truy vấn được thực hiện bởi hệ thống sẽ cĩ 1 độ bao phủ (Ri) , độ chính xác (Pi) cụ thể . ƒ Với 1 cặp (Ri,Pi) biểu diễn trên hệ trục toạ độ ROP tương ứng với 1 điểm. ƒ Biểu diễn kết quả của tập câu truy vấn trên ROP ta sẽ cĩ 2 đường cong mơ tả hiệu suất thực thi của hệ thống. Đường cong cĩ dạng: ƒ Từ đồ thị ta cĩ thể rút ra kết luận: độ bao phủ vả độ chính xác cĩ mối quan hệ gần như tỷ lệ nghịch, khi R tăng thì P cĩ thể sẽ giảm và ngược lại. ƒ Khi ta cố gắng làm tăng R bằng cách tăng số tài liệu trả về (N), theo cơng thức (1) : N tăng nên cơ may số tài liệu cĩ liên quan sẽ tăng trên tổng số tài liệu cĩ liên quan so với câu truy vấn trong bảng liên quan chuẩn là khơng đổi SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 45 Ư R sẽ cĩ thể tăng ƒ Mặt khác theo cơng thức (2) do N tăng cĩ nghĩa là số tài liệu trả về tăng mặc dù số tài liệu cĩ liên quan tăng nhưng khơng đáng kể so với số tài liệu trả về (lúc này cũng tăng) nên P sẽ giảm. Nĩi cách khác, khi cho hệ thống thực thi 1 câu truy vấn mà ta tăng số tài liệu trả về thì kết quả sẽ cĩ được nhiều tài liệu cĩ ích nhiều hơn nhưng số tài liệu khơng liên quan (tài liệu rác) cũng sẽ tăng. 2.2.3.3.2. Đường cong độ bao phủ và độ chính xác RP Cơ sở tính bảng giá trị cho đường cong RP dựa vào bảng liên quan lý thuyết và danh sách tài liệu liên quan đã được sắp thứ tự do hệ thống tìm kiếm thơng tin trả về(cịn gọi là bảng liên quan thực tế). Xét ví dụ sau: Thực hiện kiểm tra hệ thống tìm kiếm thơng tin với tập câu hỏi. Xét câu hỏi thứ k, cách tính như sau: Tài liệu liên quan được trả về là phần giao của danh sách tài liệu liên quan theo lý thuyết và theo thực tế => Tổng số tài liệu liên quan được trả về : 5 Bảng giá trị R,P tính với n tài liệu được trả về n Doc ID Liên quan theo lý thuyết ? Số tài liệu liệu liên quan được trả về Số tài liệu trả về Độ bao phủ (R) Độ chính xác (P) 1 588 true 1 1 1/5=0.2 1/1=1.00 2 589 true 2 2 2/5=0.4 2/2=1.00 3 576 false 2 3 2/5=0.4 2/3=0.67 4 590 true 3 4 3/5=0.6 3/4=0.75 5 986 false 3 5 3/5=0.6 3/5=0.60 6 592 true 4 6 4/5=0.8 4/6=0.67 SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 46 7 984 false 4 7 4/5=0.8 4/7=0.57 8 988 false 4 8 4/5=0.8 4/8=0.50 9 578 false 4 9 4/5=0.8 4/9=0.44 10 985 false 4 10 4/5=0.8 4/10=0.40 11 103 false 4 11 4/5=0.8 4/11=0.36 12 591 false 4 12 4/5=0.8 4/12=0.33 13 772 true 5 13 5/5=1.0 5/13=0.38 14 990 false 5 14 5/5=1.0 5/14=0.36 Nhìn bảng giá trị trên, ta thấy tại giá trị R=0.6 cĩ 2 giá trị P (P=0.75 và P=0.6) và ngược lại tại giá trị P=1.0 cĩ 2 giá trị R (R=0.2, R=0.4) Để xây dựng đường cong cho một câu truy vấn ta dùng phương pháp tính nội suy độ chính xác dựa trên 11 điểm chuẩn của độ bao phủ: Xét các giá trị R tại các điểm chuẩn 0.0, 0.1, 0.2, 0.3, 0.4,0.5,0.6,0.7,0.8,0.9, 1.0, tại các vị trí tính giá trị P theo cơng thức sau: Ta cĩ bảng nội suy các giá trị P cho câu hỏi thứ k như sau: N Doc ID Độ bao phủ (R) Độ chính xác (P) Độ bao phủ chuẩn hố Độ chính xác đã nội suy 1 588 1/5=0.2 1/1=1.00 0.0 1.00 2 589 2/5=0.4 2/2=1.00 0.1 1.00 3 576 2/5=0.4 2/3=0.67 0.2 1.00 4 590 3/5=0.6 3/4=0.75 0.3 1.00 5 986 3/5=0.6 3/5=0.60 0.4 1.00 6 592 4/5=0.8 4/6=0.67 0.5 0.75 7 984 4/5=0.8 4/7=0.57 0.6 0.75 P = max P với j ≥ i R( i ) R( j ) SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 47 8 988 4/5=0.8 4/8=0.50 0.7 0.67 9 578 4/5=0.8 4/9=0.44 0.8 0.67 10 985 4/5=0.8 4/10=0.40 0.9 0.38 11 103 4/5=0.8 4/11=0.36 1.0 0.38 12 591 4/5=0.8 4/12=0.33 13 772 5/5=1.0 5/13=0.38 14 990 5/5=1.0 5/14=0.36 Đồ thị RP cho câu hỏi thứ k: P re ci si on 0. 2 0. 4 0. 6 0. 8 1. 0 2.2.3.3.3. Đường cong RP cho tập truy vấn Xét tập câu truy vần gổm N câu truy vấn - Lần lượt tính bảng giá trị RP nội suy như trên (tính P dựa trên 11 điểm chuẩn của R) - Tính giá trị trung bình P tại các điểm chuẩn của R như sau: SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 48 Nhận xét: Phương pháp đánh giá hệ thống dựa vào bảng giá trị RP nội suy khơng đánh giá một cách chính xác hiệu suất tìm kiếm thơng tin của hệ thống tìm kiếm thơng tin bởi vì các giá trị của R,P là các giá trị nội suy. 2.2.3.3.4. Đánh giá hệ thống tìm kiếm thơng tin dựa vào đồ thị Ta tiến hành kiểm tra 2 hệ thống với cùng 1 tập tài liệu mẫu và tập câu truy vấn mẫu. Giả sử đồ thị diễn của 2 hệ thống như sau: Nhìn trên đồ thị : Đường cong A biểu diễn hiệu suất thực thi của hệ thống A Đường cong B biểu diễn hiệu suất thực thi của hệ thống B Do đường A nằm trên đường B nên hiệu suất của hệ thống A lớn hơn hệ thống B Ư Một cách tổng quát : đường cong nào càng gần về phía gĩc trên bên phải của hệ trục toạ độ (cĩ nghĩa là độ chính xác và độ bao phủ là lớn nhất) thì đĩ chính là đường cong biểu diễn hiệu suất thực thi tốt nhất. Với cách biểu diễn trên đồ thị như vậy ta cĩ thể đánh giá nhiều hệ thống hoặc đánh giá 1 hệ thống trong những điều kiện thực thi khác nhau. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 49 2.2.3.4. Sự liên quan giữa câu hỏi và tài liệu 2.2.3.4.1. Các độ liên quan Các độ liên quan được nĩi đến rất rõ trong [ 7 ]. ƒ Độ liên quan nhị phân (binary relevance): là độ liên quan chỉ cĩ 2 giá trị : hoặc là cĩ liên quan (relevant _ 1), hoặc khơng liên quan (not relevant _ 0). ƒ Độ liên quan nhiều mức độ (độ liên quan đa cấp độ) : (multiple degree relevance, multiple level relevance): độ liên quan được xét ở nhiều mức độ ,cĩ nhiều giá trị . Ví dụ độ liên quan 3 mức độ : - Mức độ cĩ liên quan (relevant): 2 - Mức độ liên quan bộ phận (partically relevant): 1 - Khơng liên quan (not relevant) : 0 2.2.3.4.2. Các vấn đề về độ liên quan Cơ sở đánh giá hệ thống tìm kiếm thơng tin: ƒ một tập tài liệu (document) đại diện ƒ một tập chủ đề (topic) đại diện ƒ một vài câu truy vấn cho mỗi chủ đề ƒ bảng đánh giá độ liên quan của mỗi tài liệu với mỗi chủ đề Do đĩ vấn đề cơ bản của việc đánh giá là phải thống nhất quan điểm về mức độ liên quan. Độ liên quan là một khái niệm đa khía cạnh (multifaceted), đa chiều (multidimensional). Khái niệm về độ liên quan đến nay vẫn là một vấn đề khĩ khăn trong lĩnh vực khoa học thơng tin.Những cuộc nghiên cứu gần đây đã tập trung vào nhân tố ảnh hưởng lên việc đánh giá độ liên quan và chiều (hoặc tiêu chuấn) của độ liên quan. Cĩ nhiều loại độ liên quan: độ liên quan thuật tốn, độ liên quan chủ đề, độ liên quan nhận thức, độ liên quan tình huống, độ liên quan động cơ. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 50 Độ liên quan vốn mang tính chủ quan, đánh giá độ liên quan thường khơng thống nhất do tính cá nhân và nhân tố thời gian : - Một tài liệu được đánh giá là cĩ liên quan với tỉ lệ nào đĩ nhưng đồi với người khác tỉ lệ này sẽ khác => độ liên quan phủ thuộc tính cá nhân - Một tài liệu được đánh giá là cĩ liên quan với tỉ lệ nào đĩ tại thời điểm t , nhưng tại thời điểm t’ tỉ lệ đĩ sẽ thay đổi => độ liên quan phụ thuộc nhân tố thời gian . Tuy nhiên sự thay đổi này cĩ thể chấp nhận được do nĩ tương đối thấp Trong hầu hết các thử nghiệm đánh giá hệ thống tìm kiếm thơng tin (bao gồm cả những thử nghiệm của TREC) người ta thường quan tâm độ liên quan nhị phân (cĩ nghĩa là tài liệu hoặc là được đánh giá là cĩ liên quan (1) hoặc khơng cĩ liên quan (0)). Ưu điểm của dộ liên quan nhị phân là việc tính tốn R, P đơn giản ; khuyết điểm là khơng thể phản ánh được khả năng liên quan của tài liệu ở nhiều mức độ đúng với thực tế. Trong cách đánh giá tìm kiếm thơng tin của TREC, khái niệm “liên quan” là một khái niệm tuyệt đối: một tài liệu hoặc là liên quan hoặc là khơng liên quan. Điều giả sử này nhằm làm đơn giản hĩa việc tính tốn các độ đo. Nhiều cuộc kiềm tra khác đã tiến hành đánh giá với tỷ lệ độ liên quan nhiều mức độ. Độ liên quan 3 cấp độ đã được thực hiện ở Hội nghị NTCIR 1999 (NII- NACSIS Test Collection for IR systems), WEB track của TREC-9. Độ liên quan 4 cấp được dùng trong NTCIR 2000. Tỷ lệ độ liên quan của một tài liệu tại vị trí thứ N sẽ được trừ hao, điều này phản ánh một tình trạng là tài liệu trả về càng phía dưới danh sách càng cĩ ít giá trị hơn đối với người sử dụng : mặc dù do mức độ tương quan khơng giảm nhưng sự trùng lắp thống tin với những tài liệu phía trên cũng làm cho tài liệu phìa dưới kém phần giá trị hơn. Giả sử rằng sự liên quan của một tài liệu là độc lập với các tài liệu khác là khơng thực tế trong hầu hết các trường hợp. Trong hầu hết các nhiệm vụ tìm kiếm SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 51 thơng tin cơ bản giống như tìm kiếm trên mạng, tìm kiếm câu trả lời cho một câu hỏi đặc biệt nào đĩ hoặc cho một vài sự tham khảo nào đĩ, giả sử rắng một người dùng đọc lướt qua các tài liệu được trả về sẽ bắt đầu với tài liệu dễ thấy nhất ,nổi bật nhất (ở phía trên danh sách) do đĩ độ liên quan của tài liệu phía dưới danh sách sẽ phụ thuộc vào những tài liệu đã được đọc. Khả năng một tài liệu chứa những thơng tin mới sẽ giảm xuống đến cuối danh sách tài liệu. Sự phụ thuộc này thường được bỏ qua trong những lần nghiên cứu tìm kiếm thơng tin. Ngồi ra việc định giá độ liên quan này mang tính chủ quan. Chúng ta thường cĩ nhiều ý kiến khác nhau về mức độ liên quan. Do đĩ mức độ liên quan của tài liệu được phân biệt: ƒ bảng liên quan đươc định giá do tác giả của tài liệu hay khơng phải tác giả ƒ bảng liên quan được định giá bởi một nhĩm đánh giá ƒ bảng liên quan được định giá trong cùng điều kiện hay được định giá trong các điều kiện khác nhau 2.2.3.4.3. Đánh giá với độ liên quan nhiều cấp độ (Multiple degree relevance or non-binary relevance) Trong một vài thử nghiệm về đánh giá độ liên quan nhiều cấp độ chỉ cĩ một vài thí nghiệm thực sự cho thấy lợi ích của việc đánh giá độ liên quan ở nhiều cấp độ khác nhau. Độ bao phủ (R) , độ chính xác (P) là phương pháp cổ điển để đánh giá khả năng thực thi của IR và thường được tính dựa trên việc đánh giá độ liên quan nhị phân. Do đĩ việc đánh giá độ liên quan nhiều cấp độ chỉ được tiến hành ở bước đầu , sau đĩ những giá trị mức độ sẽ được qui về 2 giá trị 0,1 để đánh giá Ví dụ : đánh giá độ liên quan được tiến hành 3 mức độ: o cĩ liên quan (relevant) => ký hiệu A o liên quan một phần (partically relevant ) => ký hiệu B o khơng liên quan (not relevant) => ký hiệu C SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 52 Mức độ liên quan sẽ được qui về 2 giá trị để tính R , P. Cĩ 2 cách tính: A, B mang giá trị 1 (cĩ liên quan) C mang giá trị 0 (khơng liên quan) hoặc A mang giá giá trị 1 (cĩ liên quan) B,C mang giá trị 0 (khơng liên quan) Với cách tiến hành như vậy để duy trì mức độ liên quan của tài liệu, định dạng một tập tin đánh giá độ liên quan (relevant judgement) như sau: topic-ID dumy doc-ID relevant assessment Trong đĩ : topic-ID : chỉ số của chủ đề (topic) dumy : là trường cho biết tài liệu đĩ cĩ mức độ liên quan là bao nhiêu (A,hoặc B ,hoặc C) doc-ID : chỉ số tài liệu relevant assessment: mang giá trị 0 hoặc 1 , giá trị đánh giá độ liên quan sau khi được qui về độ liên quan nhị phân. Một ví dụ khác về đo độ liên quan của tài liệu ở 4 mức độ: o độ liên quan cao (highly relevant) o độ liên quan vừa (fairly relevant) o độ liên quan trung bình (marginally relevant) o khơng liên quan (irrelevant) Tuy nhiên trong các Hội nghị về Đánh giá các hệ thống thơng tin gần đây, độ liên quan nhị phân vẫn cịn được xem là một cách đánh giá chuẩn, thậm chí nhiều trường hợp đánh giá độ liên quan ở nhiều cấp độ nhưng cũng được qui về đánh giá nhị phân để tính độ bao phủ và độ chính xác. Cách tiến hành này cĩ khuyết điểm là nĩ khơng kiểm tra được từng mức độ cụ thể của độ liên quan. Một số người cĩ quan điểm là cách đo độ R và P dựa vào việc đánh giá nhị phân là nên tránh vì cách tính như vậy khơng quan tâm đến sự thay đổi và độ SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 53 phức tạp của mức độ liên quan, làm sai lệch tính tự nhiên và thực tế của độ liên quan. Một giải pháp để giải quyết vấn đề này là tổng quát hố độ R và P. Dựa vào lý thuyết, thực nghiệm, nghiên cứu, mức độ liên quan của tài liệu thay đổi một cách rõ ràng, một vài tài liệu thì liên quan nhiều hơn, một số khác thì ít hơn. Thật là khĩ để xác định mức độ liên quan khi tiến hành đánh giá. Điều này cịn tuỳ thuộc vào tình huống đánh giá hệ thống của chúng ta. 2.2.3.4.4. Phương pháp đo độ bao phủ (R), độ chính xác (P) dựa trên độ liên quan nhiều cấp độ Phương pháp đo dựa vào độ bao phủ (R ) và độ chính xác (P) là một phương pháp truyền thống nhưng độ đo R,P chỉ được tính dựa vào độ liên quan nhị phân Đối với trường hợp độ liên quan nhiều cấp độ ta cĩ 2 cách giải quyết sau: - qui tất cả mức độ liên quan về 2 giá trị 0,1 (giống như đưa về dộ liên quan nhị phân ) => cách này theo Schamber là nên tránh - tổng quát hố R và P ™ Độ bao phủ tổng quát và độ chính xác tổng quát: (generalized , non-binary recall and precision) Gọi R là tập n tài liệu được phục hồi từ cơ sở dữ liệu tài liệu D= { d1, d2, …, dN } với một câu truy vấn thuộc về một chủ đề nào đĩ , R ≤ D Gọi tài liệu di trong cơ sở dữ liệ tài liệu cĩ tỉ lệ độ liên quan là r(di) Độ bao phủ tổng quát gR và độ chính xác tổng quát gP được tính theo cơng thức như sau: d є R n ∑ r(d) gP = d є R d є D ∑r(d) ∑r(d) gR= SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 54 Cách tính này cũng tương tự tính R, P nhị phân truyền thống , nĩ cũng cho phép tính R trung bình và P trung bình của tập câu truy vấn, tính P dựa trên R, hoặc tính dựa trên ngưỡng giới hạn số tài liệu trả về và cũng cho phép biểu diễn đường cong PR Ghi chú : r(d) là một con số thực cĩ giá trị trong khoảng (0.0, 1.0) Ví dụ với mức độ liên quan là 4. Tính r(d) o Mức độ liên quan cao : 3 => r(d)=3/4 o Mức độ liên quan vừa : 2 => r(d)=2/4 o Mức độ liên quan trung bình : 1 => r(d)=1/4 Khơng liên quan :0 => r(d)=0 2.2.4. TREC và đánh giá theo chuẩn TREC 2.2.4.1. TREC là gì? TREC là viết tắt của Text REtrieval Conference, cĩ nghĩa là Hội nghị về Tìm kiếm Thơng tin Văn bản, được tổ chức hằng năm tại Viện Quốc gia về Tiêu chuẩn và Cơng nghệ Hoa Kỳ (NIST _ National Institute Standard and Technology) [ 8]. TREC là một loạt Hội nghị chuyên cung cấp cơ sở hạ tầng cho việc kiểm tra, đánh giá quy mơ lớn về cơng nghệ tìm kiếm (chủ yếu là tìm kiếm văn bản). Hội nghị TREC được tạo ra để thúc đẩy nghiên cứu về các cơng nghệ tìm kiếm thơng tin. Các mục tiêu chính của TREC là : • Khuyến khích các nghiên cứu trong tìm kiếm thơng tin dựa trên ngữ liệu đánh giá qui mơ lớn. • Phát triển giao tiếp, liên lạc giữa các ngành cơng nghiệp, giáo dục và chính phủ bằng cách cung cấp một diễn đàn mở để trao đổi các ý kiến nghiên cứu. • Hỗ trợ trao đổi cơng nghệ từ những phịng thí nghiệm nghiên cứu thành những sản phẩm thương mại. • Cải thiện vượt bật các phương pháp luận tìm kiếm trên các vấn đề thế giới thực và các độ đo cho tìm kiếm thơng tin. SV ne t.vn Luận văn : Đánh giá các hệ thống tìm kiếm thơng tin Trang 55 • Tạo ra một loạt ngữ liệu đánh giá liên quan các khía cạnh khác nhau của tìm kiếm thơng tin. • Phát triển các cơng nghệ đánh giá thích hợp sẵn cĩ mà được sử dụng bởi ngành cơng nghệp và giáo dục, bao gồm cả việc phát triển các cơng nghệ đánh giá mới thích hợp hơn với các hệ thống hiện tại. Chu trình Hội nghị hằng năm của TREC : TREC gồm các lĩnh vực tập trung khác nhau gọi là TRACK. Nhiệm vụ của các TRACK chủ yếu là tập trung vào vấn đề con của tìm kiếm thơng tin văn bản. Chính những T