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

là phần không thể thiếu. Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 60 Khác với tiếng Anh, Pháp (thường được dùng trong các hệ thống tìm kiếm thống tin phổ biến), tiếng Việt có những đặc thù riêng, đặc biệt trong việc xác định từ tiếng Việt. 2.3.1. Từ 2.3.1.1. Quan niệm về từ Theo [10 ], thì tổng hợp từ các sách ngôn ngữ học đại cương, sách ngữ pháp và sách về từ vựng học, chúng tôi xin trình bày lại một số định nghĩa điển hình về từ như sau: ♦ Từ là một hình thái tự do nhỏ nhất. ♦ Từ là đơn vị ngôn ngữ có tính hai mặt : âm và nghĩa. Từ có khả năng độc lập về cú pháp khi sử dụng trong lời. ♦ Từ là đơn vị nhỏ nhất có nghĩa của ngôn ngữ, được vận dụng độc lập, tái hiện tự do trong lời nói để xây dựng nên câu”. Đây cũng chính là định nghĩa mà trong ngôn ngữ học đại cương hay sử dụng. Từ các định nghĩa trên, ta rút ra những nét đặc trưng chính của từ như sau: Về hình thức : từ phải là một khối về cấu tạo (mặt chính tả, ngữ âm) Về nội dung : từ phải có ý nghĩa hoàn chỉnh. Về khả năng : từ có khả năng hoạt động tự do và độc lập về cú pháp. Ngoài ra, ta còn gặp một số thuật ngữ khác trong ngôn ngữ học đại cương mà S.E.Jakhontov [ 11] đưa ra để nhận diện từ, như: 1. Từ ngữ âm: đó là những đơn vị được thống nhất với hiện tượng ngữ âm nào đó. Đối với Việt ngữ, đó chính là những âm tiết, hay còn gọi là “tiếng”, “tiếng một 2. Từ chính tả: đó là những khoảng cách giữa 2 chỗ trên văn tự; tức là những đơn vị được viết liền thành khối, đối với tiếng Việt, đó chính là “chữ” 3. Từ hoàn chỉnh: đó là những cấu trúc ổn định, không thể tách rời hay hoán vị các thành tố của chúng. Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 61 4. Từ từ điển học: đó là đơn vị mà căn cứ vào đặc điểm ý nghĩa của nó phải xếp riêng trong từ điển. 5. Từ biến tố: đó là những đơn vị luôn luôn gồm 2 phần: gốc từ (biểu thị ý nghĩa đối tượng) và phụ tố (biểu thị mối liên hệ với các từ khác trong câu). Đây còn gọi là từ ngữ pháp. Về phương diện xử lý tự động bằng máy tính, thì từ chính tả và từ từ điển là hai loại được nhận diện dễ nhất và được sử dụng nhiều nhất trong tài liệu này. 2.3.1.2. Quan niệm về hình vị Trong ngữ pháp truyền thống thì hình vị được xem là thành tố trực tiếp để tạo nên từ. Do đó, hình vị được xem như là đơn vị tế bào gốc, đơn vị tế bào của ngữ pháp, và còn được gọi là từ tố. Chính vì vậy, mà việc nhận diện hình vị phải là bước đi đầu tiên trong việc nhận diện từ. Để nhận diện hình vị, Jakhontov đưa ra cách phân xuất câu đến mức tối giản, gọi là từ câu, hay hình vị; ngoài ra, giới ngôn ngữ học hay sử dụng phương pháp lập hình vuông Greenberg để đối sánh. Ví dụ: đối sánh “có lý” và “có ý”, ta tách được thành 3 hình vị: “có”, “lý” và “ý”. Trước hết ta hãy xem lại quan niệm về hình vị (morpheme) trong ngôn ngữ học đại cương: theo Baudouin de Courtenay thì hình vị là bộ phận nhỏ nhất có nghĩa của từ, còn theo Bloomfield thì hình vị là đơn vị ngôn ngữ nhỏ nhất có nghĩa. Nhưng quan niệm thường thấy trong ngôn ngữ học đại cương là: “hình vị là đơn vị ngôn ngữ nhỏ nhất có nghĩa và/hoặc có giá trị (chức năng) về mặt ngữ pháp”. “Từ” được cấu tạo bằng một hình vị hay nhiều hình vị kết hợp với nhau theo những nguyên tắc nhất định. Ví dụ: anti-virus (chống vi rút). Hình vị bao gồm hai loại: hình vị tự do (như: work, home,…) và hình vị hạn chế (như: -ed, -less,…). Trong hình vị hạn chế gồm hình vị biến tố (như: work-ed) và hình vị phái sinh (như: home-less). 2.3.1.3. Khái niệm về cấu tạo từ Từ được cấu tạo nhờ các hình vị (morpheme). Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 62 Ví dụ: anti + poison = antipoison. Hình vị là đơn vị ngôn ngữ nhỏ nhất có nghĩa và/hoặc có giá trị (chức năng) về mặt ngữ pháp. Hình vị gồm các loại : - Hình vị tự do : tự nó xuất hiện với tư cách là một từ độc lập, ví dụ : house, man, black, nhà, người, đen... - Hình vị hạn chế : xuất hiện trong tư thế đi kèm, phụ thuộc vào hình vị khác, nó bao gồm các hình vị biến tố và hình vị phát sinh. Ví dụ : -ing, -ed, -s, -ness, ... Để cấu tạo từ, người ta dùng các phương thức : - Dùng một hình vị. - Tổ hợp 2 hay nhiều hình vị. - Thêm phụ tố (tiền, trung, hậu tố) vào. - Láy. 2.3.2. Ranh giới từ Nhận diện ranh giới từ (word boundary identification) hay còn gọi là phân đoạn từ (word segmentation) là một công đoạn tiên quyết đối với hầu hết các hệ xử lý ngôn ngữ tự nhiên. Đối với các ngôn ngữ biến hình (tiếng Anh, tiếng Nga,...) thì ranh giới từ được xác định chủ yếu bằng khoảng trắng hay dấu câu, còn đối với các ngôn ngữ đơn lập (trong đó có tiếng Việt) thì khoảng trắng không thể là tiêu chí để nhận diện từ. Muốn xác định được ranh giới từ trong các ngôn ngữ này, chúng ta phải dựa vào các thông tin ở mức cao hơn, như hình thái, từ pháp, cú pháp, hoặc ngữ nghĩa và thậm chí cả ngữ dụng. Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 63 Chương 3 : THIẾT KẾ VÀ CÀI ĐẶT 3.1. Xây dựng bộ ngữ liệu dùng để đánh giá Như chúng tôi đã trình bày trong các phần trên, chúng tôi xây dựng bộ ngữ liệu dùng để đánh giá theo tiêu chuẩn của TREC. Việc xây dựng gồm 3 phần sau : 3.1.1. Xây dựng kho ngữ liệu bằng tiếng Việt Chúng tôi xây dựng kho ngữ liệu dùng để đánh giá bằng cách thu thập tài liệu từ các báo điện tử, chẳng hạn : www.tuoitre.com.vn, www.thanhnien.com.vn, www.vnexpress.net . Các tài liệu này bao gồm rất nhiều lĩnh vực khác nhau gồm có khoa học kỹ thuật, kinh tế, giáo dục, văn hóa, thời sự … Kho ngữ liệu của chúng tôi cho đến nay đã có gần 15.000 tài liệu, với kích thước lưu trữ là 34 MB. Tuy nhiên, các tài liệu này ở dưới dạng thô, chưa được chuẩn hóa nên bước quan trọng nhất là chuẩn hóa ngữ liệu. 3.1.1.1. Chuẩn hóa ngữ liệu Chuẩn hóa ngữ liệu là chuẩn hoá thành một dạng, một tiêu chuẩn duy nhất. Việc chuẩn hoá ngữ liệu gồm các nhiệm vụ sau: 3.1.1.1.1. Chuẩn hóa dạng ngữ liệu Chuẩn hoá dạng ký tự: đưa về đúng dạng điện tử, định dạng tập tin (từ các định dạng tập tin khác nhau sẽ chuyển về txt, loại bỏ những thứ không phải là văn bản), đúng mã ký tự (chuyển về mã Unicode). Chuẩn hoá tập tin: mỗi tập tin ngữ liệu sẽ gồm một số câu (khoảng 2000 từ), mỗi câu có thể nằm trên một dòng, hết câu, ngắt xuống dòng cứng sau dấu chấm câu. Mỗi đầu câu, sẽ có một mã số định danh để cho biết thông tin về văn bản, như: ngôn ngữ (Anh, Việt, Pháp, Hoa, …), lĩnh vực của tập tin (văn học, tin học, kinh tế, thể thao,…), tiểu loại (như: trong văn học có truyện ngắn, tiểu thuyết, Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 64 thơ, ký, …) và thông tin về số hiệu câu (câu thứ mấy trong tập tin), số hiệu văn bản (văn bản thứ mấy trong tiểu loại/lĩnh vực đang xét). Chuẩn hoá chính tả: xem xét biến thể hình thái chính tả, như: quy tắc bỏ dấu thanh (với tiếng Việt: bỏ dấu trên nguyên âm chính theo nguyên tắc thẩm mỹ hay bỏ trên nguyên âm chính theo nguyên tắc ngữ âm học), các biến thể chữ viết, như: cách viết i/y trong tiếng Việt “hoá lý” và “hóa lí”. 3.1.1.1.2. Định dạng ngữ liệu Sau khi thu thập ngữ liệu và chuẩn hóa ngữ liệu về dạng văn bản, chúng tôi chuyển tất cả ngữ liệu sang định dạng XML với một thẻ định danh như DOCNO của TREC. Thẻ định danh của chúng tôi là DOCID. Sở dĩ chúng tôi chuyển sang định dạng XML là vì như thế chúng tôi có thể dễ dàng chuyển đổi định dạng để tìm kiếm cho tất cả các hệ thống tìm kiếm khác nhau. Định dạng ngữ liệu của chúng tôi có trong phần phụ lục. Chúng tôi có chương trình cho phép chuyển đổi định dạng từ text sang XML giống tài liệu của chúng tôi. Chương trình này rất hữu ích trong việc tạo thêm tài liệu cho kho ngữ liệu của chúng tôi. 3.1.2. Xây dựng tập câu hỏi bằng tiếng Việt Tập câu hỏi được xây dựng bằng cách đọc lướt qua một số tài liệu và tạo một tập X câu hỏi. Sau đó, chúng tôi tạo định dạng cho câu hỏi theo tiêu chuẩn của TREC, tức câu hỏi phải có phần định danh, tiêu đề, mô tả và tường thuật. Câu hỏi cũng được định dạng ở XML. Tiếp theo, chúng tôi chạy tập X các câu hỏi cho các hệ thống tìm kiếm. Rồi xem lại kết quả tìm kiếm của các hệ thống để lựa chọn những câu hỏi nào là tối ưu nhất để tạo tập Y câu hỏi chính thức. Vì vậy Y luôn nhỏ hơn hay bằng X. ™ Cả câu hỏi và ngữ liệu tiếng Việt đều phải được tách từ trong trường hợp đánh giá các hệ thống tìm kiếm tiếng Anh cho tiếng Việt vì hệ thống tiếng Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 65 Anh không thể nào được dùng để đánh giá hệ thống tiếng Việt. Do đó, chúng tôi cũng xây dựng một chương trình tách từ cho ngữ liệu tiếng Việt. 3.1.3. Tách từ tiếng Việt Để nhận diện ranh giới từ, chúng tôi đã sử dụng một số hình như: MM Maximum Matching: forward / backward ; LRMM: Left Right, RLMM: Right Left và phương pháp MMSEG : Maximum Matching Segmentation. Theo phương pháp LRMM để phân đoạn từ tiếng Việt trong một ngữ/câu, ta đi từ trái sang phải và chọn từ có nhiều âm tiết nhất mà có mặt trong từ điển, rồi cứ tiếp tục cho từ kế tiếp cho đến hết câu. Với cách này, ta dễ dàng tách được chính xác các ngữ/câu như: “hợp tác xã | mua bán”; “thành lập | nước | Việt Nam | dân chủ | cộng hoà”,…. Phương pháp RLMM thì ngược lại, trong một câu/ngữ, ta đi từ phải sang trái và chọn từ có nhiều âm tiết nhất mà có mặt trong từ điển, rồi cứ tiếp tục cho từ kế tiếp cho đến hết câu. Phương pháp MMSEG là sự kết hợp của cả hai phương pháp LRMM và RLMM, do đó MMSEG cho kết quả tốt hơn hai phương pháp trên. 3.1.4. Xây dựng bảng đánh giá Chúng tôi xây dựng bảng đánh giá theo phương pháp Pooling. Chúng tôi chạy các hệ thống khác nhau để đánh giá. Chúng tôi đã tìm hiểu các hệ thống sau: Hệ thống SMART [12 ] của Đại học Cornell phát triển, một hệ thống kinh điển về mô hình vec-tơ . Hệ thống XIOTA [ 13], hệ thống cho phép định dạng ngữ liệu theo XML, được phát triển tại Pháp. Hệ thống Terrier [14 ] của Đại học Glasgow, Scot-len. Hệ thống này được dùng để chạy các track Tetra, Robust của TREC. Hệ thống Lucene [15 ], do nhóm Jakarta Apache phát triển, đây là một search engine được dùng phổ biến. Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 66 Hệ thống Tìm kiếm Tiếng Việt hay Search4Vn của một nhóm làm luận văn khóa 2001 phát triển để tìm kiếm thông tin tiếng Việt. Tuy nhiên, đa số các hệ thống làm cho tiếng Anh nên mã hóa của các hệ thống này không hỗ trợ tiếng Việt (mặc dù tiếng Việt được mã hóa bằng mã Unicode), vì vậy muốn thực thi các hệ thống tìm kiếm cho tiếng Việt bắt buộc chúng tôi phải thực hiện chuyển mã cho chương trình tìm kiếm. Các hệ thống này được viết trên rất nhiều ngôn ngữ khác nhau, gồm có ngôn ngữ C trên Linux, ngôn ngữ BASH Shell, ngôn ngữ Java, JSP, ngôn ngữ DOT NET; và tài liệu cho các thành phần mã nguồn không đầy đủ nên chúng tôi khó có thể chỉnh sửa hết tất cả các hệ thống. Chúng tôi đã làm hết khả năng có thể để đọc mã nguồn và tìm cách sửa mã cho hệ thống tìm kiếm nhưng chúng tôi chỉ có thể chạy được vài hệ thống. Sau khi chạy các hệ thống, chúng tôi giao các bảng liên quan lại thành bảng liên quan chuẩn. Sau đó, chúng tôi đọc lại và tạo bảng đánh giá liên quan chuẩn hòan chỉnh. 3.1.4.1. Hệ thống SMART 3.1.4.1.1. Giới thiệu hệ thống SMART SMART là một hệ thống tìm kiếm thông tin dựa trên mô hình vector được đề xuất bởi Salton vào cuối những năm 60. Mục đích chính của SMART là cung cấp một nền tảng cho việc xây dựng tìm kiếm thông tin, lập chỉ mục, đánh giá tìm kiếm thông tin. Mục đích thứ hai là cung cấp cho người dùng thông tin cuối cùng vừa nhỏ thích hợp với người dùng. SMART có những ưu điểm và khuyết điểm của nó.SMART được thiết kế rất linh hoạt, nó cho phép thêm chỉnh sửa các đoạn mã và có thể chạy trên bất kỳ hệ thống UNIX với yêu cầu về kích thước bộ nhớ nhỏ. 3.1.4.1.2. Quá trình tìm kiếm thông tin của SMART SMART thực hiện qua 4 thủ tục: Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 67 1. lập chỉ mục tự động : trích dẫn và xác định các yếu tố thông tin là từ hay cụm từ (term) của tài liệu và câu truy vấn. 2. Phân loại tài liệu: tập hợp các tài liệu có liên quan với nhau để tạo thành những lớp tài liệu có cùng chủ đề, làm như vậy để hệ thống có thể tìm được nhiều tài liệu có chủ đề tương tự đồng thời cũng làm tăng tốc độ xử lý của hệ thống (xin xem giải thích phần dưới). 3. Xác định tài liệu được trả về bằng cách tính độ tương tự (similarity) giữa các yếu tố thông tin được lưu trữ và các yếu tố thông tin vừa được phân tích từ câu truy vấn mới nhập vào, sắp xép kết quả trả về theo thứ tự giảm dần độ tương tự. Quá trình này , hệ thống SMART dùng mô hình vec-tơ. 4. Cải tiến câu lệnh tìm kiếm (câu truy vấn) nhằm xây dựng lại câu truy vấn dựa vào những thông tin được lấy từ kết quả của quá trình phục hồi truy vấn trước. 3.1.4.1.3. Mô hình vec-tơ của hệ thống SMART Trong mô hình này, mỗi tài liệu được đặc trưng bởi 1 vector của tập các từ ngữ (term). Tập các từ ngữ này được xác định bởi quá trình lập chỉ mục của hệ thống. Có nghĩa là với mỗi tài liệu cụ thể DOCi sẽ được xác định bởi tập từ ngữ TERM1 ,TERM2,…..,TERMt (Từ ngữ ở đây có thể gọi 1 cách rộng hơn là yếu tố thông tin vì nó có thể là một từ, ngữ được trích dẫn từ các tài liệu hay một từ , cụm từ lấy từ các từ điển thuật ngữ đồng nghĩa). Một tập các tài liệu DOC1, DOC2, …., DOCn có thể được biểu diễn thành 1 ma trận trong đó mỗi dòng của ma trận là 1 tài liệu, mỗi cột biểu diễn 1 yếu tố thông tin của các atì liệu. TERM1 TERM2 … TERMt DOC1 TERM11 TERM12 … TERM1t DOC2 TERM21 TERM22 … TERM2t …. DOC3 TERM31 TERM32 … TERM3t Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 68 TERMij gọi là trọng số thông tin của yếu tố thông tin TEMj trong tài liệu DOCi , nó chính là tần số xuất hiện của TERMj trong tài liệu DOCi. TERMij=0 có nghĩa là trong tài liệu DOCi không tồn tại yếu tố thông tin TERMj => Tương tự như vậy các câu truy vấn khi được đưa vào hệ thống cũng sẽ được biểu diễn thành vector có t thành phần TERM có sẵn của tài liệu. Nhưng giá trị của các TERMij không phải là trọng số mà có giá trị trị nhị phân. - Khi TERMij=0 : từ (ngữ) của câu truy vấn không có trong tập yếu tố thông tin tài liệu - TERMij=1 : từ (ngữ) của câu truy vấn có trong tập yếu tố thông tin tài liệu ƒ Biểu diễn hình học của tập vec-tơ tài liệu: Tập tài liệu gồm n DOC : DOC1, DOC2,…,DOCn và t yếu tố thông tin TERM1, TERM2, …, TERMt. Theo mô hình vector : một tài liệu biểu diễn thành 1 vector trên không gian t chiều . Vậy ta có n vector tài liệu DOC1 (TERM11,TERM12,…..,TERM1t) DOC2 (TERM21,TERM22,…..,TERM2t) …. DOCn (TERMn1,TERMn2,…..,TERMnt) Lần lượt tính cos của góc tạo bởi 2 vector tài liệu DOCi,DOCj theo cộng thức sau: ∑ COS (DOCi, DOCj)= √ ∑ √ ∑ Ta thấy góc α tạo bởi 2 vector DOCi , DOCj càng nhỏ thì vector DOCi và DOCj càng gần nhau hay trọng số của các yếu tố thông tin so với tài liệu DOCi, DOCj gần bằng nhau Ù tài liệu DOCi và DOCj có cùng chủ đề Để thể hiện ý nghĩa trên ta có khái niệm độ tương tự (TERMik * TERMjk) k=1 t (TERMik)^2 k=1 t (TERMjk)^2 k=1 t Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 69 Ö Độ tương tự của các tài liệu chính là cos của góc tạo bởi 2 vector DOCi, DOCj Ö Đây chính là cách xác định phân loại tài liệu của hệ thống Một cách tương tự ta có thể định nghĩa độ tương tự của tài liệu và câu truy vấn: Xét 1 câu truy vấn Qj cụ thể , Qj có thể được biểu diễn dưới dạng vector như sau: Qj (QTERMj1, QTERMj2,…,QTERMjt) Vector Qj cũng được biểu diễn trong không gian t chiều như tập tài liệu Độ tương tự của câu truy vấn so với tài liệu DOCi chính là cos của góc α tạo bởi 2 vector Qj và DOCi . COS (DOCi, Qj) = ∑ √ ∑ √ ∑ Do giá trị của các vector Qj và DOCi luôn là 1 con số lớn hơn bằng 0, nên cosα >=0 => α là góc trong khoảng [0, ∏ ] . Do hàm số cos trong khoảng [ 0,∏ ] là hàm số nghịch biến nên cosα càng lớn thì α càng nhỏ có nghĩa là nếu 2 vector càng gần nhau thì độ tương tự càng lớn hay nội dung của tài liệu DOCi liên quan nhiều đến yêu cầu của câu truy vấn Qj. 3.1.4.1.4. Sử dụng mô hình vec-tơ Phân loại tài liệu: Dựa vào việc tính độ tương tự giữa các vector tài liệu ta có thể phân loại tài liệu, những tài liệu có độ tương tự gần nhau sẽ xếp vào 1 lớp • Mục đích của việc phân tài liệu: Là để tạo ra 1 tập tin cluster document. Dưới đây là ví dụ của tập tin cluster: (TERMik * QTERMjk) k=1 t (TERMik)^2 k=1 t (QTERMjk)^2 k=1 t Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 70 Mỗi 1 điểm x ký hiệu cho 1 vector tài liệu, khoảng cách giữa 2 điểm x tỷ lệ nghịch với độ tương tự (khoảng cách giữa 2 điểm x càng lớn có nghĩa là độ tương tự giữa 2 tài liệu càng nhỏ và ngược lại). Mỗi đường tròn đại diện cho lớp tài liệu. Để đặc trưng cho lớp đó người ta định nghĩa thêm 1 vector đặc biệt gọi là vector centroid , nó cũng giống như trọng tâm của tập các điểm x , được thể hiện trên hình vẽ là ‘o’. • Cách tính vector centroid Giả sử có m tài liệu thuộc lớp p, vector centroid của lớp p được biểu diễn như sau: CENTROIDp = CTERMp1 , CTERMp2,….,CTERMpt Trong đó : CTERMpk = ∑ TERMik với TERMik là trọng số của term k của tài liệu i trong lớp p • Mục đích của việc đưa ra vector centroid: Đầu tiên ,mỗi câu truy vấn sẽ được so sánh với các vector centroid để tính độ tương tự giữa vector truy vấn và vector centroid thay vì phải tính với tất cả các vector tài liệu . Nếu độ tương tự đó đủ lớn (có nghĩa là lớp tài liệu đó thích 1 m i=1 m x x x x x o x x x x o x x x o o x o o x x x Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 71 hợp) thì ta tiếp tục so sánh vector truy vấn với các vector tài liệu trong lớp mà vector centroid đó đại diện . Tài liệu nào có độ tương tự lớn sẽ được phục hồi Giả sử có n tài liệu trong tập cơ sở dữ liệu tài liệu được phân chia thành x lớp (nên có x vector centroid) , mỗi lớp có khả năng chứa n/x tài liệu Số lần so sánh giữa câu truy vấn và vector centroid là x lần. Sau khi đã so sánh x lần với các vector centroid ta chọn được 1 vector centroid có độ tương tự lớn nhất và tiến hành so sánh với n/x tài liệu trong lớp có vector centroid đó đại diện Ö Tổng số lần so sánh là x + n/x (*) Nếu không thiết lập tập tin cluster (tức là không định nghĩa vector centroid ) tổng số lần so sánh của 1 câu truy vấn với n tập tài liệu là n lần Áp dụng bất đẳng thức Cauchy cho biểu thức (*): x + ≥ 2√ n Dấu “=” xảy ra khi x = Ù x = √ n Vậy số lần so sánh ít nhất sẽ là 2√ n với số cluster trong tập tài liệu là x = √ n Đối với tập tài liệu lớn với các tài liệu có nhiều chủ đề khác nhau không đồng nhất thì số lượng cluster (lớp) sẽ lớn, lúc đó số lần so sánh giữa vector truy vấn và các vector centroid sẽ lớn . Để giải quyết trường hợp này , một lần nữa ta lại áp dụng phương pháp tính độ tương tự giữa các vector centroid như cách tính độ tương tự giữa các tài liệu để phân lớp cho tập vector centroid. Nói tóm lại việc tính độ tương tự giữa các tài liệu để phân lớp tài liệu tạo ra 1 vector đại diện cho lớp đó gọi là vector centroid , tương tự việc phân lớp vector centroid sẽ tạo ra 1 vector đại diện cho lớp vector centroid đó gọi là vector supercentroid và lớp đó được gọi là superclass Do đó việc tìm kiếm tài liệu sẽ được thực hiện qua 3 bước: i. Đầu tiên so sánh vector truy vấn với các vector supercentroid thuộc các superclass x n x n Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 72 ii. Sau đó so sánh câu truy vấn với các vector centroid của các superclass thoả ở bước 1 iii. Cuối cùng so sánh câu truy vấn với các vector tài liệu của các lớp mà vector centroid thoả ở bước 2 • Một ví dụ về cấu trúc của tập tin cluster: Việc tổ chức các file cluster phải thích hợp với sự phát triển của tập cơ sở dữ liệu tài liệu, bởi vì 1 tài liệu mới được thêm vào cơ sở dữ liệu cũng sẽ được thực hiện so sánh tương tự như đối với câu truy vấn. Các item của tài liệu sẽ được so sánh với các supercentroid và các centroid đã có , kết quả là tài liệu sẽ được thêm vào những cluster thích hợp mà độ tương tự giữa các cluster đủ lớn. Sau đó hệ thống phải tiến hành tính lại các vector supercentroid và centroid của những cluster vừa mới có thêm tài liệu mới SUPERCENTROIDk SCTERMk1 , SCTERMk2 , …… , SCTERMkt CENTROIDPOINTER i CENTROIDPOINTER j …. CENTROIDi CTERMi1 , CTERMi2 , …… , CTERMit DOCPOINTER i1 DOCPOINTER i2 ….. CENTROIDj CTERMj1 , CTERMj2 , …… , CTERMjt DOCPOINTER j1 DOCPOINTER j2 …. DOCi1 TERMi11 , TERMi12 , …… , TERMi1t DOCi2 TERMi21 , TERMi22 , …… , TERMi22 DOCj1 TERMj11 , TERMj12 , …… , TERMj1t DOCj2 TERMj21 , TERMj22 , …… , TERMj22 …… …… Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 73 Xác định tài liệu thích hợp trả về Cải tiến câu truy vấn: Thủ tục cải tiến câu truy vấn của hệ thống SMART còn được gọi là quá trình gửi thông tin phản hồi về tính liên quan của tài liệu (Relevance feedback) việc đánh giá độ liên quan mà người sử dụng cung cấp cho hệ thống dựa trên những tài liệu được phục hồi của câu truy vấn trước đó, để xây dựng lại mô hình vector truy vấn mới. Mục đích của quá trình này là xây dựng câu truy vấn mới có hiệu quả thực thi tốt hơn Thủ tục cải tiến câu truy vấn được thực thi như sau: i. Các từ ngữ xuất hiện trong tài liệu được người dùng xác định là có liên quan sẽ được thêm vào mô hình vector truy vấn ban đầu hoặc trọng số của những từ ngữ này (term) sẽ được tăng lên. ii. Các từ ngữ xuất hiện trong tài liệu được người dùng xác định là không có liên quan sẽ được xoá ra khỏi câu truy vấn ban đầu hoặc trọng số của nó sẽ được giảm lên.Thủ tục cải tiến câu truy vấn sẽ được thực thi một cách tự động dựa vào thông tin phản hồi từ phía người dùng. Quá trình này có thể được tiến hành nhiều lần để tìm ra câu truy vấn tối ưu nhất 3.1.4.2. Hệ thống Search4Vn Hệ thống này cũng sử dụng mô hình không gian vectơ để tìm kiếm. Mục đích hệ thống này là để tìm kiếm thông tin tiếng Việt. Mô hình tách từ được sử dụng là Longest Matching. Hệ thống được viết bằng ngôn ngữ C#. 3.1.4.3. Hệ thống TERRIER Hệ thống này cũng sử dụng mô hình không gian vectơ để tìm kiếm. Kết quả tìm kiếm có TF và IDF để các chuyên gia có thể biết hệ thống tìm theo mô hình đó tốt hay không. Tuy nhiên, hệ thống này chưa hỗ trợ Unicode,và các lớp được viết cho Unicode lại thuộc một thư viện chuẩn(thư viện antlr của Java) nên việc chuyển mã rất khó khăn. Muốn chuyển mã bắt buộc phải thay đổi cách viết Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 74 chương trình của hệ thống. Cho đến nay, chúng tôi chưa thể chuyển mã để tìm kiếm tiếng Việt. Hệ thống này được viết bằng Java và JSP nên độc lập môi trường. 3.1.4.4. Hệ thống X-IOTA Hệ thống XIOTA hay hệ thống IOTA là một khung làm việc XML mở cho thử nghiệm tìm kiếm thông tin. Vì sử dụng XML nên XIOTA rất linh hoạt trong xử lý ngữ liệu, hỗ trợ cài đặt nhanh nhiều thành phần thử nghiệm khác nhau mà dùng các xử lý ngôn ngữ tự nhiên tự động. Hệ thống XIOTA cũng tìm kiếm theo mô hình vec-tơ. Hệ thống X-IOTA được viết bằng C++ chạy trên môi trường Linux. Tuy nhiên, hệ thống này đang trong giai đoạn thử nghiệm nên thành phần mã nguồn chưa ổn định để tìm kiếm thông tin. 3.1.4.5. Hệ thống LUCENE Hệ thống này cũng sử dụng mô hình không gian vec-tơ để tìm kiếm. Hệ thống được viết bằng ngôn ngữ Java. Lucene cũng là một hệ thống mã nguồn mở, là một công cụ tìm kiếm mà người sử dụng có thể phát triển giao diện tìm kiếm theo ý riêng của mình. Chúng tôi cũng đã thêm giao diện và sửa mã của Lucene để có thể tìm kiếm được tiếng Việt. 3.2. Phân tích hệ thống đánh giá các hệ thống tìm kiếm thông tin 3.2.1. Mô tả hệ thống trợ giúp đánh giá 3.2.1.1. Phát biểu bài toán Như chúng tôi đã đề cập, chúng tôi thực hiện đánh giá dựa trên mô hình hướng hệ thống để đánh giá kết quả trả về của các hệ thống tìm kiếm thông tin (chúng tôi gọi tắt là hệ thống IR). Nhưng để việc đánh giá được thực hiện một cách rõ ràng, trực quan và đặc biệt là tự động hóa thì nhất thiết phải cần đến hệ Luận văn : Đánh giá các hệ thống tìm kiếm thông tin Trang 75 thống trợ giúp đánh giá các hệ tìm kiếm thông tin. Hệ thống trợ giúp đánh giá gồm có chương trình hỗ trợ đánh giá các hệ thống tìm kiếm tự động và bộ ngữ liệu dùng để đánh giá. 3.2.1.2. Mục tiêu Chương trình hỗ trợ đánh giá cho phép thực thi và xem cách thức hoạt động của các hệ thống tìm kiếm thông tin bất kỳ. Để thực thi tìm kiếm trên một hệ thống tìm kiếm thông tin bất kỳ, chương trình phải cho phép định dạng bộ ngữ liệu dùng để đánh giá của chương trình thành bộ ngữ liệu mà hệ thống tìm kiếm có thể hiểu và tìm kiếm được. Còn cách thức hoạt động của