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

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 toá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

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

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

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. Ngoà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ìmkiế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ệudùng để đánh giá gồm có kho ngữ liệu mẫu bằng tiếng Việt (a VietnameseCorpus 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.