Một số kỹ thuật nâng cao hiệu năng tìm kiếm văn bản

g vì những mục đầu tiên là có ích nhất cho người sử dụng. Họ chỉ cần quan sát vài mục đầu tiên thay cho duyệt toàn bộ kết quả. Việc gán các thuật ngữ chỉ mục cho tài liệu và câu truy vấn là để phân biệt các tài liệu mà người sử dụng quan tâm với các tài liệu khác. Trong một tài liệu cụ thể, thuật ngữ nào xuất hiện thường xuyên hơn thì nó quan trọng hơn, nên nó có trọng số lớn hơn. Trong ngữ cảnh tập hợp toàn bộ tài liệu, nếu thuật ngữ xuất hiện hầu hết trong các tài liệu thì nó không phải là lựa chọn tốt làm thuật ngữ chỉ mục vì nó không giúp phân biệt các tài liệu người sử dụng quan tâm với tài liệu khác. Do vậy, thuật ngữ được chỉ mục tốt là thuật ngữ xuất hiện thường xuyên trong vài tài liệu nhưng không xuất hiện trong các tài liệu khác. Khi gán trọng số thuật ngữ, cần phải quan tâm đến cả hai: tần số thuật ngữ (tfij) và tần số tài liệu (dfj). Công thức chung để tính trọng số thuật ngữ là: Wij = tfij * log (N/dfj) trong đó, Wij là trọng số của thuật ngữ j trong tài liệu i, tfij là tần số của thuật ngữ j trong tài liệu i, N là tổng số tài liệu trong tập hợp, dfj là số tài liệu chứa thuật ngữ j. Trọng số trên đây tỷ lệ với tần số thuật ngữ và tỷ lệ nghịch với tần số tài liệu, công thức này thường được gọi là tf.idf. [idf=log(N/dfi)] Trên cơ sở công thức Wij = tfij * log (N/dfj), nếu thuật ngữ xuất hiện trong toàn bộ tài liệu (dfj = N) thì trọng số của thuật ngữ bằng 0 (thuật ngữ không thể sử dụng làm thuật ngữ chỉ mục). Mặt khác, nếu thuật ngữ xuất hiện thường xuyên chỉ trong vài tài liệu, trọng số của thuật ngữ sẽ rất cao (thuật ngữ này làm thuật ngữ chỉ mục tốt). Ví dụ có 5 tài liệu D1 đến D5, và 1 thuật ngữ “CAR”. Hình 2.6 dưới đây minh hoạ cho mối quan hệ giữa 5 tài liệu và thuật ngữ “CAR” và chỉ có 3 tài liệu có chứa thuật ngữ “CAR”. Truy vấn hệ thống cho thuật ngữ này cho giá trị IDF=log(N/dfi)=log(5/3)=0.2218. Hình 2.6: Mô hình minh hoạ mối quan hệ giữa 5 tài liệu D1 đến D5 và thuật ngữ “CAR” Khi đó ta có bảng trọng số Wij tính theo công thức tf.idf: tfi Wij=tfi*IDFi Term D1 D2 D3 D1 D2 D3 CAR 1 4 5 0.2218 0.8872 1.109 d. Lập chỉ mục tự động cho tài liệu tiếng Anh sau: Một quá trình đơn giản để lập chỉ mục cho tài liệu có thể được mô tả như Trước hết, xác định tất cả các từ tạo thành tài liệu. Trong tiếng Anh, chỉ đơn giản là tách từ dựa vào khoảng trắng. Loại bỏ các từ có tần số xuất hiện cao. Những từ này chiếm khoảng 40-50% các từ, như đã đề cập trước đây, chúng có độ phân biệt kém do đó không thể sử dụng để đại diện cho nội dung của tài liệu. Trong tiếng Anh, các từ này có khoảng 250 từ, do đó, để đơn giản có thể lưu chúng vào từ điển, gọi là stop list. Trích dẫn các từ dừng của tiếng Anh như trong Bảng 2.5. Bảng 2.5: Danh sách từ dừng của tiếng Anh A ALTHOUGH ANYONE ABOUT ALWAYS ANYTHING ACROSS AMONG ANYWHERE AFTER AMONGST ARE AFTERWARDS AN AROUND AGAIN AND AS AGAINST ANOTHER AT ALL ANY BE ALSO ANYHOW BECOME Sau khi loại bỏ các từ có trong stop list, xác định các từ chỉ mục “tốt”. Trước hết cần loại bỏ các hậu tố để đưa về từ gốc, ví dụ các từ như: analysis, analyzing, analyzer, analyzed, analysing có thể chuyển về từ gốc là “analy.” Từ gốc sẽ có tần số xuất hiện cao hơn so với các dạng thông thường của nó. Nếu sử dụng từ gốc làm chỉ mục, ta có thể thu được nhiều tài liệu có liên quan hơn là sử dụng từ ban đầu của nó. Đối với tiếng Anh, việc loại bỏ hậu tố có thể được thực hiện dễ dàng bằng cách sử dụng danh sách các hậu tố có sẵn (Suffix List). Sau khi có đợưc danh sách các từ gốc, sử dụng phương pháp dựa vào tần số (frequency – based) để xác định tầm quan trọng của các từ gốc này. Chúng ta có thể sử dụng một trong các phương pháp đã được đề cập ở trên như: tần số tài liệu nghịch đảo (inverse document frequency), độ tín hiệu ( SIGNALk), độ phân biệt từ (DISVALUEk). Trong hệ thống chỉ mục có trọng số, trọng số của một từ được sử dụng để xác định tầm quan trọng của từ đó. Mỗi tài liệu được biễu diễn là một vector: Di = (di1, di2, …, dit) trong đó dij là trọng số của từ j trong tài liệu Di. Giả sử có 1033 tài liệu nói về y học. Quá trình lập chỉ mục đơn giản được thực hiện như sau (trong đó chỉ loại bỏ hậu tố tận cùng là s): Hình 2.7 Quá trình chọn từ làm chỉ mục e. Lập chỉ mục cho tài liệu tiếng Việt Lập chỉ mục cho tài liệu tiếng Việt cũng tương tự như cho tiếng Anh. Tuy nhiên có vài điểm khác biệt sau: • Giai đoạn tách từ trong tiếng Anh chỉ đơn giản dựa vào khoảng trắng, còn tiếng Việt là ngôn ngữ đơn lập, một từ có thể có nhiều tiếng. Giả sử sau giai đoạn tách từ, ta sẽ thu được một danh sách các từ riêng biệt. • Đối với tiếng Việt, không phải qua giai đoạn loại bỏ hậu tố. • Nói chung, lập chỉ mục cho tài liệu tiếng Việt gồm các bước sau: o Xác định các từ riêng biệt trong tài liệu; o Loại bỏ các từ có tần số cao. (Trong tiếng Việt, cũng như tiếng Anh, ta có một danh sách Stop List chứa những từ không thể là nội dung của văn bản như: và, với, những, gì, sao, nào, …); o Loại bỏ các từ có trọng số thấp. • Các từ thu được sẽ được chọn làm các từ chỉ mục. 2.2.2 Mô hình tìm kiếm không gian vector 2.2.2.1 Mô hình tìm kiếm không gian vector cơ sở Khái niệm mô hình tìm kiếm Bool đơn giản và được sử dụng trong hầu hết các hệ thống thương mại. Tuy nhiên tương đối kh ó hình thành các câu truyấvn Bool và kết quả truy vấn rất nhậy cảm với công thức truy vấn. Trọng số thuật ngữ truy vấn thường không được sử dụng vì các câu truy vấn thường rất ngắn. Để tránh vấn đề này, các mô hình tìm kiếm khác như không gian vector, thống kê và trên cơ sở cụm (cluster) được sử dụng để thay thế. Mô hình không gian vector giả sử rằng tồn tại tập cố định các thuật ngữ chỉ mục để đại diện tài liệu và câu truy vấn. Tài liệu Di và câu truy vấn Q j được biểu diễn như hai vector: Di = [Ti1, Ti2,..., Tik, ... , TiN] Qj = [Qj1, Qj2,..., Qjk, ... , QjN] trong đó, Tik là trọng số của thuật ngữ k trong tài liệu i, Qjk là trọng số của thuật ngữ k trong truy vấn j, và N là tổng số thuật ngữ sử dụng trong các tài liệu và truy vấn. Các trọng số thuật ngữ Tik và Qjk có thể là nhị phân (1 hoặc 0) họăc sử dụng phương pháp đánh trọng số tf.idf hoặc các phương pháp khác. Việc tìm kiếm trong mô hình không gian vector được thực hiện dựa trên cơ sở tính tương đồng giữa câu truy vấn và các tài liệu. Độ tương đồng giữa tài liệu Di và câu truy vấn Qj được tính như sau: N S (Di , Q j ) = ∑Tik .Q jk k =1 Để bù vào độ chênh lệch giữa kích thước tài liệu và kích thước câu truy vấn, tính tương đồng nói trên có thể chuẩn hóa với è là góc của hai vector (gọi là khoảng cách cosin) và được biểu diễn như dưới đây: i j S (D , Q  ) = cosè =  Di .Q j N ∑Tik .Q jk = k =1 | Di || Q j | N 2 N 2 ∑Tik . k =1 ∑ Q jk k =1 Đây là hệ số cosine quen thuộc giữa vector Di và Qj. Khi tìm kiếm , danh sách xếp hạng theo thứ tự tính tương đồng giảm dần sẽ được cho lại. Thí dụ, có 4 tài liệu và truy vấn được đại diện bởi các vector sau: D1 = [0.2, 0.1, 0.4, 0.5] D2 = [0.5, 0.6, 0.3, 0] D3 = [0.4, 0.5, 0.8, 0.3] D4 = [0.1, 0, 0.7, 0.8] Q = [0.5, 0.5, 0, 0] thì tính tương đồng giữa câu truy vấn và từng tài liệu như sau: S(D1, Q) = 0.31 S(D2, Q) = 0.931 S(D3, Q) = 0.66 S(D4, Q) = 0.07 Hệ thống sẽ cho lại danh sách tài liệu theo thứ tự D2, D3, D1 và D4. Hạn chế chính của mô hình không gian vector là nó coi các thậut ngữ không có quan hệ với nhau và nó chỉ làm việc tốt với tài liệu và câu truy vấn ngắn. Nếu M là tổng số tài liệu, cần O(M) thời gian so sánh trong trường hợp tồi nhất. Nếu có N thuật ngữ, cần O(N) thời gian so sánh. Vậy tổng số thời gian đòi hỏi tính toán sẽ là O(N x M). Thông thường N x M là một số rất lớn, do vậy, người ta phải phát triển các kỹ thuật khác để tìm kiếm thuật ngữ trong tập tài liệu. 2.2.2.2. Kỹ thuật phản hồi phù hợp (Relevance Feedback Technique) Các kỹ thuật áp dụng thông tin phản hồi phù hợp của người sử dụng được phát triển để nâng cao hiệu năng hệ thống. Phản hồi phù hợp lấy quyết định của người sử dụng về tính thích hợp của tài liệu và sử dụng chúng để điều chỉnh câu truy vấn hay chỉ mục tài liệu. a. Điều chỉnh câu truy vấn Điều chỉnh câu truy vấn trên cơ sở phản hồi thích hợp của người sử dụng sẽ sử dụng quy tắc sau: • Các thuật ngữ xuất hiện trong tài l iệu nhận ra trước đây là thích hợp thì được bổ sung vào câu truy vấn gốc, hay làm tăng trọng số của thuật ngữ. • Các thuật ngữ xuất hiện trong các tài liệu nhận ra trước đây không thích hợp thì hủy khỏi câu truy vấn hay làm giảm trọng số của thuật ngữ. Câu truy vấn mới được thay thế lần nữa để tìm kiếm tài liệu. Các quy tắc trên đây được diễn giải như sau: Q (i +1) = Q (i ) + á ∑ D i − â Di ∈Re l ∑ D i Di ∈Non Re l trong đó, Q(i+1) là truy vấn mới, Q (i) là truy vấn hiện hành, D i là tập hợp các tài liệu tìm kiếm được từ câu truy vấn Q(i), α và β là các trọng số, tổng thứ nhất được thực hiện với tất cả tài liệu phù hợp trong D(i), và tổng thứ hai thực hiện trên tài liệu không phù hợp D(i). Thực nghiệm cho thấy rằng hiệu năng sẽ được nâng cao nhờ sử dụng kỹ thuật này. Tóm lại, nguyên tắc của tiệm cận trên là tìm ra các tài liệu tương đồng với tài liệu đã kết luận là phù hợp với câu truy vấn. Các tài liệu thích hợp với câu truy vấn phải tương tự với nhau. b. Điều chỉnh tài liệu Trong điều chỉnh câu truy vấn trên cơ sở phản hồi phù hợp ( relevance) củ a người sử dụng, các câu truy vấn được điều chỉnh nhờ các thuật ngữ trong tài liệu phù hợp. Người sử dụng khác không có lợi từ điều chỉnh này. Trong điều chỉnh tài liệu trên cơ sở phản hồi phù hợp của người sử dụng, các thuật ngữ chỉ mục tài liệu được điều chỉnh bằng các thuật ngữ truy vấn để sự thay đổi này tác động đến người sử dụng. Sử dụng các qui tắc trên cơ sở phản hồi phù hợp của người sử dụng như sau đây để điều chỉnh tài liệu: • Thuật ngữ trong truy vấn, nhưng không trong các tài liệu mà người sử dụng kết luận là phù hợp, sẽ được bổ sung vào danh sách chỉ mục tài liệu với trọng số khởi đầu. • Các trọng số của thuật ngữ chỉ mục trong câu truy vấn và trong các tài liệu phù hợp đều được tăng lên với giá trị nhất định. • Các trọng số của các thuật ngữ chỉ mục ngoài câu truy vấn nhưng trong tài liệu liên quan được giảm đi một giá trị nhất định. Khi các truy vấn tiếp theo sau tương tự các truy vấn sử dụng để hiệu chỉnh tài liệu được đưa ra thì hiệu năng được tăng cường. Tuy nhiên tiệm cận này có thể làm giảm hiệu năng nếu các truy vấn tiếp theo khác xa với cái được sử dụng để điều chỉnh tài liệu. 2.2.3. Thước đo hiệu năng Giả sử trong tập tài liệu khi chúng ta tìm kiếm với câu truy vấn Q chúng ta có kết quả như sau: Pert: Tập con tài liệu đúng với câu truy vấn Q trong thực tế Retr: Tập con tài liệu mà hệ thống tìm ra Tập hợp tài liệu Các tài liệu phù hợp (đối với người sử dụng) Các tài liệu tìm thấy (của hệ thống) Hình 2.8. Mô hình thước đo hiệu năng Để đánh giá hiệu năng của hệ tìm kiếm thông tin dựa vào 2 tiêu chuẩn sau: +Khả năng tìm thấy (Recall): P ∩ R P  ∈ [0,1] +Độ chính xác (Precision):  P ∩ R R  ∈ [0,1] Cả hai tiêu chuẩn đều có giá trị trong khoảng [0,1]. Khi Recall có giá trị càng sát 1 thì khả năng tìm thấy tài liệu càng cao. Khi recall=1 thì khả năng tìm thấy hết tài liệu liên quan. Đối với Precision cũng tương tự Recall, khi Precision càng tiến sát 1 thì độ chính xác càng cao Khi Recall = Precision = 1 thì hệ thống cho kết quả tuyệt đối Để so sánh hiệu năng của hệ thống này với hệ thống khác cùng chức năng chúng ta có thể dựa vào đồ thị sau: Độ chính xác Khả năng tìm thấy (0,0)  Hình 2.9. Đồ thị so sánh hiệu năng Theo tính chất của 2 tiêu chuẩn Recall và Precision thì đồ thị của hệ thống nào càng xa gốc thì đạt hiệu năng càng cao. 2.3 Ví dụ Giả sử cho câu truy vấn “gold silver truck” và 3 tài liệu: D1: "Shipment of gold damaged in a fire" D2: "Delivery of silver arrived in a silver truck" D3: "Shipment of gold arrived in a truck" Các kết quả tính trọng số được tổng kết trong bảng 2.5: Tần số tfi Trọng số wij=tfi*IDFi Terms Q D1 D2 D3 dfi D/dfi IDFi Q D1 D2 D3 A 0 1 1 1 3 3/3=1 0 0 0 0 0 arrived 0 0 1 1 2 3/2=1.5 0.1761 0 0 0.1761 0.1761 damaged 0 1 0 0 1 3/1=3 0.4771 0 0.4771 0 0 delivery 0 0 1 0 1 3/1=3 0.4771 0 0 0.4771 0 Fire 0 1 0 0 1 3/1=3 0.4771 0 0.4771 0 0 Gold 1 1 0 1 2 3/2=1.5 0.1761 0.1761 0.1761 0 0.1761 In 0 1 1 1 3 3/3=1 0 0 0 0 0 Of 0 1 1 1 3 3/3=1 0 0 0 0 0 silver 1 0 2 0 1 3/1=3 0.4771 0.4771 0 0.9542 0 shipment 0 1 0 1 2 3/2=1.5 0.1761 0 0.1761 0 0.1761 truck 1 0 1 1 2 3/2=1.5 0.1761 0.1761 0 0.1761 0.1761 Các cột trong bảng kết quả thể hiện: • Cột 1 đến cột 5: Danh mục các thuật ngữ được xây dựng từ các tài liệu và tính tần số tfi cho câu truy vấn trong mỗi tài liệu Dj. • Cột 6 đến cột 8: Là tần số tài liệu di của từng tài liệu. Từ đó tính IDFi = log(D/dfi) và D = 3. • Cột 9 đế cột 12: Là trọng số thuật ngữ được xác định bằng cách lấy tích tfi * IDFi. Các cột này có thể được xem như là một ma trận thưa, trong đó hầu hết các mục bằng 0. Tính độ tương đồng: Để tính độ tương đồng, trước tiên tính tất cả các chiều dài vector cho mỗi tài liệu và câu truy vấn: ∴ Di = 2 i, j ∑ W i D1 = 0.47712 + 0.47712 + 0.17612 + 0.17612 = 0.5173 = 0.7192 D2 = 0.17612 + 0.47712 + 0.95412 + 0.17612 = 1.2001 = 1.0955 D3 = 0.17612 + 0.17612 + 0.17612 + 0.17612 = 0.1240 = 0.3522 2 Q = ∑ i WQ, j = 0.17612 + 0.47712 + 0.17612 = 0.2896 = 0.5382 Tiếp theo tính tất cả các tích điểm (bỏ qua các tích 0): ∴Q•Di= ∑ WQ, j Wi, j i Q•D1 = 0.1761*0.1761=0.0310 Q•D2 = 0.4771*0.9542*0.1761*0.1761=0.4862 Q•D3 = 0.1761*0.1761*0.1761*0.1761=0.0620 => Các giá trị tương đồng: ∑WQ , jWi , j ∑Wi j ∴CosèDi = S(Q,Di) = i 2 2 ∑WQ , j , D Cosè = 1  Q • D1 = j 0.0310 i = 0.0801 Q * D1 0.5382 * 0.7192 Cosè D 2 Cosè D 3  = Q • D2 Q * D2 = Q • D3 Q * D3  = 0.4862 0.5382 *1.0955 = 0.0620 0.5382 * 0.3522  = 0.8246 = 0.3271 Cuối cùng sắp xếp thứ tự cho các tài liệu theo thứ tự giảm dần theo giá trị tương đồng: Rank 1: Doc2 = 0.8246 Rank 2: Doc 3= 0.3271 Rank 3: Doc 1= 0.0801 2.4 Kết luận Với lượng thông tin khổng lồ như hiện nay thì lựa chọn các kỹ thuật tìm kiếm thông tin sao cho vừa nhanh chóng, vừa chính xác là một điều hết sức cần thiết. Trong chương này của luận văn, tác giả đã trình bày hai kỹ thuật đơn giản, dễ hiểu nhất trong số các kỹ thuật tìm kiếm thông tin đã được nghiên cứu và phát triển. Tuy nhiên, hai kỹ thuật này chưa thực sự hiệu quả do vậy cần phải có nh ững kỹ thuật tốt hơn, hiệu quả h ơn nhằm đáp ứng nhu cầu truy vấn của ng ười sử dụng. Trong chương tiếp theo của luận văn này sẽ trình bày một số kỹ thuật nâng cao tìm kiếm văn bản. CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM VĂN BẢN 3.1 Giới thiệu Trong chương 2 đã giới thiệu cách tìm kiếm các vector đặc trưng cho tài liệu văn bản. Các vector đặc trưng thông thường là đa chiều. Thí dụ, trong mô hình không gian vector, tổng số chiều đặc trưng hay vector tài liệu bằng tổng số mục (items), thường hàng trăm hay hàng ngàn, được sử dụng trong tập hợp tài liệu. Tổng số chiều phụ thuộc vào phương pháp lựa chọn. Trong khi tìm kiếm , câu truy vấn cũng được biểu diễn bởi vector đa chiều. Tìm kiếm trên cơ sở mức độ tương đồng hay khoảng cách giữa vector truy vấn và vector đặc trưng của các đối tượng lưu trữ. Khi tổng số đối tượng lưu trữ hoặc/và tổng số chiều của vector đặc trưng lớn, chúng sẽ chậm khi tìm kiếm tuyến tính mọi vector đặc trưng lưu trữ để tìm ra cái thỏa mãn tiêu trí truy vấn. Do vậy, đòi hỏi có các kỹ thuật và cấu trúc dữ liệu để tổ chức các vector đặc trưng và quản lý tiến trình tìm kiếm sao cho các vector đặc trưng liên quan đến truy vấn được định vị nhanh. Mục tiêu chính của các kỹ thuật để nâng cao hiệu năng tìm kiếm tương tự là chia không gian đặc trưng đa chiều thành nhiều vùng nhỏ sao cho việc tìm kiếm chỉ được thực hiện trong một hay trong một vài vùng nhỏ. Các kỹ thuật và cấu trúc dữ liệu khác nhau thì khác nhau về cách phân chia và lựa chọn vùng nhỏ cho mỗi truy vấn. Có ba loại truy vấn thường được sử dụng: truy vấn điểm, truy vấn dải (range) và truy vấn k láng giềng gần nhất. Trong truy vấn điểm : Câu truy vấn của người sử dụng được biểu diễn bởi vector, các đối tượng có vector đặc trưng đối sánh chính xác với vector truy vấn thì được xem như kết quả ở đầu ra. Trong truy vấn dải: Câu truy vấn được biểu diễn bởi vector đặc trưng và dải khoảng cách. Mọi đối tượng mà khoảng cách từ chúng đến vector truy vấn nhỏ hơn hay bằng dải khoảng cách cho trước thì là kết quả. Tồn tại rất nhiều thước đo khoảng cách khác nhau, trong đó chuẩn L1 và L2 (khoảng cách Euclid) là hay được sử dụng nhất. Loại khác của truy vấn dải được đặc tả bởi dải giá trị cho mỗi chiều của vector đặc trưng. Trong truy vấn k láng giềng gần nhất , câu truy vấn của người sử dụng đư ợc đặc tả bởi một vector và một số nguyên k. Hệ thống sẽ tìm ra k đối tượng mà nó thỏa mãn điều kiện là những khoảng cách từ chúng đến vector truy vấn là nhỏ nhất. Cần có kỹ thuật và cấu trúc dữ liệu hữu hiệu để hỗ trợ cả ba loại truy vấn nói trên. Có thể tối ưu các cấu trúc dữ liệu cho một loại truy vấn nhất định nếu biết rằng chỉ một loại truy vấn đó hay được sử dụng cho loại ứng dụng cụ thể. 3.2 Một số kỹ thuật nâng cao hiệu năng tìm kiếm đa phương tiện Thông thường có thể giảm không gian tìm kiếm bằng tiến trình lọc trên cơ sở các tiêu chí nào đó. Có một số tiêu chí và tiến trình lọc phụ thuộc vào ứng dụng hay đặc trưng cụ thể. Các tiêu chí khác không phụ thuộc vào ứng dụng mà có thể được sử dụng cho nhiều tiến trình tìm kiếm. Ý tưởng cơ sở của chúng được trình bày như sau đây. Các tiến trình lọc, thí dụ việc lọc trên cơ sở thuộc tính, được thực hiện rất hiệu quả để chọn các mục thỏa mãn tiêu chí nào đó. Việc tìm kiếm trên cơ sở đặc trưng phức tạp (biểu diễn bởi các vector đa chiều) sau đó chỉ được thực hiện trên các mục đã được chọn lựa. Vì tổng số các mục lựa chọn là rất nhỏ so với tổng số mục trong CSDL, cho nên tiến trình tìm kiếm sẽ nhanh. Có các phương pháp lọc sau: 3.2.1 Lọc bằng phân lớp, thuộc tính có cấu trúc và các từ khóa Một số thuộc tính có cấu trúc, thí dụ như ngày tháng, được kết hợp với hầu hết các đối tượng đa phương tiện. Nếu người sử dụng chỉ quan tâm đến các đối tượng mà thỏa mãn một vài thuộc tính thì chúng ta sẽ sử dụng các thuộc tính này để lựa chọn sơ bộ, sau đó thực hiện tìm kiếm trên cơ sở các đặc trưng phức tạp hơn từ chúng. Thí dụ, khi có sẵn phân lớp chủ đề thì người sử dụng chọn các chủ đề quan tâm và việc tìm kiếm các đối tượng chỉ cần thực hiện trong chủ đề đó. Các tiệm cận trên đây thường được áp dụng, nó không bị giới hạn trên các đặc trưng nào được sử dụng. Với vài đặc trưng cụ thể, có thể sử dụng một số thuộc tính đặc biệt để giảm không gian tìm kiếm. Thí dụ, trong phương pháp chỉ mục và tìm kiếm hình dạng ảnh trên cơ sở vùng, chúng ta sử dụng độ lệch ( eccentricity) hình dạng làm tiêu chí lọc – chỉ cần tìm kiếm các hình dạng trong dải lệch xác định trước. 3.2.2 Các phương pháp trên cơ sở tính không đều tam giác Phần lớn thước đo khoảng cách đặc trưng, thí dụ khoảng cách Euclid, là metrics. Metrics có tính chất gọi là tính không đều tam giác ( triangle inequality). Berman và Shapiro đã sử dụng tính chất này để làm giảm số lần so sánh trực tiếp đặc trưng trong CSDL. Tính không đều của tam giác phát biểu rằng khoảng cách giữa hai đối tượng không nhỏ hơn hiệu khoảng cách của nó đến đối tượng khác (đối tượng thứ ba). Về toán học, tính chất không đều của tam giác được viết như sau: d(i,q) ≥ |d(i, k) - d(q, k)| trong đó, d là khoảng cách, i, q và k là các đối tượng (k là đối tượng khóa). Bất đẳng thức trên đúng với mọi k. Vậy khi sử dụng tập các đối tượng (k1,..., km) thay cho k làm các đối tượng so sánh thì ta có: d (i, q) ≥ max1≤ j ≤m | d (i, k j ) − d (q, k j ) | trong đó m là tổng số đối tượng so sánh. Chúng ta áp dụng tính không đều tam giác vào tìm kiếm thông tin đa phương tệi n như sau: • Chọn m vector đặc trưng (như đối tượng khóa) làm cơ sở so sánh. Thông thường, m nhỏ hơn nhiều so với tổng số n các đối tượng (i1, ..., in) trong CSDL. • Với mỗi đối tượng i trong CSDL và mỗi vector so sánh kj, chúng ta tính trước giá trị d(i,kj) và lưu trữ chúng trong CSDL. • Trong khi tìm kiếm , ta tính khoảng cách d(q, k j) giữa câu truy vấn q với mỗi vector so sánh kj. • Tìm l (i) = max1≤ j ≤m | d (i, k j ) − d (q, k j ) | cho mỗi đối tượng i trong CSDL. • Chỉ những đối tượng có l(i) nhỏ hơn ngưỡng T chọn trước thì được lựa chọn để tính toán khoảng cách từ nó tới q, gọi là d(q,i). Chúng ta không cần tính toán khoảng cách giữa q và các đối tượng khác trong CSDL vì chúng được đảm bảo là lớn hơn ngưỡng T, nó được lựa chọn theo đặc trưng sử dụng và theo yêu cầu của người sử dụng. Chú ý rằng các đối tượng kh ông được lựa chọn trên cơ sở l(i) thì có khoảng cách tới q lớn hơn T. Tuy nhiên, không phải mọi đối tượng được lựa chọn đều có khoảng cách tới q nhỏ hơn T. Thí dụ sau đây mô tả tiến trình này. Giả sử CSDL có 8 đối tượng ảnh được biểu diễn bởi các vector đặc trưng i1 đến i8. Hai vector so sánh là k1 và k2. Khoảng cách của từng đối tượng trong CSDL đến vector so sánh được tính toán trước như trong bảng 3.1: Bảng 3.1: Bảng khoảng cách của từng đối tượng trong CSDL đến từng vector so sánh Database items d(i, k1) d(i, k2) |d(i, k1)- d(q, k1)| |d(i, k2)- d(q, k2)| l(i) i1 2 5 1 1 1 i2 4 9 1 5 5 i3 7 2 4 2 4 i4 9 3 6 1 6 i5 3 8 0 4 4 i6 2 9 1 5 5 i7 1 4 2 2 2 i8 4 10 1 6 6 Giả sử ta muốn tìm các đối tượng ảnh trong CSDL mà khoảng cách của chúng đến câu truy vấn q nhỏ hơn 3, và khoảng cách giữa q đến từng vector so sánh là 3 và 4. Cột thứ tư của bảng trên cho biết giá trị |d(i, k 1)-d(q, k1)| và cột thứ năm chỉ ra |d(i, k2)-d(q, k2)| cho mỗi đối tượng ảnh trong CSDL. Cột cuối cùng trong bảng là giá trị l(i). Từ các giá trị của cột này ta thấy chỉ đối tượng i1 và i7 là có khoảng cách đến q nhỏ hơn 3, do vậy nó cần so sánh trực tiếp với q. Thí dụ này chỉ cần tính toán trực tuyến 4 khoảng cách giữa các vector đa chiều thay cho việc tính toán 8 khoảng cách nếu không sử dụng tiến trình lọc trên cơ sở tính không đều tam giác. Tiến trình lọc trên cơ sở tính không đều tam giác được sử dụng trong mọi kỹ thuật tìm kiếm mà thước đo khoảng cách của chúng là metric. 3.2.3 Mô hình tìm kiếm trên cơ sở cụm (cluster-based) Trong các mô hình tìm kiếm thông tin đã khảo sát trong Ch ương 2 cũng như đầu Chương 3, các tài liệu tương tự có thể không gần kề trong hệ thống tệp. Với loại tổ chức tệp này, rất khó cài đặt khả năng duyệt (browsing). Hiệu quả của tìm kiếm sẽ thấp vì không thể tìm ra mọi mục phù hợp và phải tìm kiếm trên toàn bộ không gian tài liệu. Để khắc phục nhược điểm này, ta thực hiện cụm (nhóm) các tài liệu tương đồng vào các cụm (cluster). 3.2.3.1 Sinh cụm Hai tiệm cận tổng quát khi sinh cụm là: • Tiệm cận thứ nhất: Trên cơ sở tính tương tự mọi cặp ( pairwise) tài liệu, hãy nhóm các mục tương tự vào cụm chung. Trong tiệm cận trên cơ sở tính tương tự từng cặp, mỗi tài liệu được đại diện như “vector tài liệu” trong mô hình không gian vector. Sau đó mức độ tương đồng giữa cặp tài liệu được tính toán. Trong tiến trình cụm, mỗi tài liệu được khởi đầu trong một lớp ( class) và sau đó hai tài ệliu tương tự nhau nhất trên cơ sở tính tương tự của cặp được tổ hợp trong một cụm. Tính tương đồng giữa cụm mới hình thành và các tài liệu kh ác được tính toán, sau đó tài liệu tương đồng nhất (kể cả cụm) được tổ hợp vào cụm mới. Tiến trình tổ hợp tiếp tục cho mọi tài liệu được nhóm vào cụm cao hơn. Đó là tiến trình cụm phân cấp. Các phương pháp cụm phân cấp trên cơ sở tính tương đồng giữa các t ài liệu là khá đắt khi thực hiện. Nhưng phương pháp này sinh ra tập duy nhất các cụm cho mỗi tập tài liệu. • Tiệm cận thứ hai: Sử dụng phương pháp Heuristic không đòi hỏi tính toán tính tương tự cặp tài liệu. Phương pháp này sinh ra nhanh cácụcm thô và tươn g đối rẻ hơn phương pháp trên. Tiến trình heuristic đơn giản nhất (tiến trình một bước) lấy các tài liệu sẽ cụm theo thứ tự tùy ý. Lấy tài liệu thứ nhất để đặt vào cụm. Mỗi tài liệu tiếp theo sẽ so sánh với các cụm trước đó, rồi đặt vào cụm tồn tại nếu đủ tính tương đồng với cụm đó. Nếu tài liệu không đủ tính tương đồng với các cụm có sẵn thì để vào cụm mới. Tiến trình này tiếp tục cho đến khi mọi tài liệu được cụm. Cấu trúc cụm được sinh ra theo cách này phụ thuộc vào thứ tự trong đó tài liệu được xử lý. 3.2.3.2 Tìm kiếm trên cơ sở cụm Khi các cụm (nhóm) được hình thành, tìm kiếm tài liệu sẽ hiệu quả. Mỗi cụm có vector đại diện, thường là tâm của chúng. Tâm của cụm được tính bằng vector trung bình của mọi tài liệu trong nhóm (trọng số của thuật ngữ tâm i đư ợc xác định bằng trọng số trung bình của mọi thuật ngữ i trong mọi tài liệu). Trong khi tìm kiếm tài liệu, các vector câu truy vấn được so sánh với tâm của các cụm. Sau khi nhận ra cụm có tính tương đồng cao nhất với vector truy vấn, sẽ có hai khả năng: • Mọi tài liệu trong cụm được tìm ra. Điều này xảy ra khi các cụm đều nhỏ. • Vector tìm kiếm được so sánh với từng vector tài liệu trong cụm và chỉ tài liệu nào có tính tương đồng cao nhất thì được tìm ra làm kết quả. 3.2.4 Chỉ mục ngữ nghĩa tiềm ẩn (LSI) để tìm kiếm thông tin trên cơ sở không gian vector Một kỹ thuật khác được áp dụng để tìm kiếm thông tin đa phương tiện đó là kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (Latent Semantic Indexing – LSI). Ý tưởng cơ bản của kỹ thuật này là sử dụng một ma trận phân tích để xác định những thành phần chính của vector không gian được xác định bởi tập tài liệu, và sau đó chiếu vector lên không gian được mở rộng bởi những thành phần chính đó. Trong kỹ thuật LSI, những thành phần chính được xem là thể hiện cho những khái niệm quan trọng, trong khi những thành phần ít quan trọng hơn được xem là những biến đổi trong cách sử dụng khác nhau của từ. Vì thế LSI nhấn mạnh khía cạnh quan trọng của tfi.df và bỏ qua hiệu quả của cách sử dụng từ ngữ khác nhau. Sau đó, các tài liệu được so sánh bằng cách sử dụng phép đo độ tương đồng bằng hàm số cosin và kết quả sẽ được sắp xếp theo độ tương đồng để hiển thị. LSI là một kỹ thuật khá hiệu quả trong tìm kiếm văn bản, nên tác giả luận văn sẽ đi sâu nghiên cứu về kỹ thuật này và chi tiết sẽ được trình bày trong mục tiếp theo của chương. 3.3 Kỹ thuật LSI 3.3.1 Giới thiệu LSI Trong mô hình không gian vector, mỗi tài liệu được biểu diễn bởi một vector trọng số thuật ngữ N chiều, mỗi thành phần của vector là trọng số của từng thuật ngữ trong số N thuật ngữ của tài liệu. Nếu tập tài liệu có M tài liệu, thì tập tài liệu này được biểu diễn bằng ma trận A kích thước MxN. Trong khi tìm kiếm , câu truy vấn cũng được biểu diễn bằng vector trọng số thuật ngữ N chiều. Tính tương đồng giữa truy vấn và từng tài liệu lưu trữ được tính bằng tích vô hướng hay hệ số cosin giữa vector truy vấn và vector tài liệu. Tiệm cận trực tiếp trên đây có hai yếu điểm sau đây: • Yếu điểm thứ nhất: Tập hợp tài liệu (thí dụ thư viện) có thể chứa đến hàng triệu tài liệu với nhiều ngàn khái niệm (M và N rất lớn). Vậy đòi hỏi tổng số bộ nhớ rất lớn để lưu trữ. Thí dụ, nếu thư viện có 1 triệu tài liệu với 10 000 thuật ngữ thì chúng ta cần đến 10GB bộ nhớ lưu trữ với mỗi phần tử chiếm 1 byte. • Yếu điểm thứ hai: Ít nhất cần M phép nhân vector N chiều khi tìm kiếm nếu sử dụng thước đo tương tự tích vô hướng và đòi hỏi nhiều hơn thế nếu sử dụng thước đo tương tự hệ số cosin. Khi M và N lớn, thời gian đòi hỏi để tính toán sẽ không đáp ứng với việc tìm kiếm trực tuyến. Chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent Semantic Indexing) được Falotsos, Foltz, Dumais và Bently phát triển để giải quyết một phần khó khăn trên. Ý tưởng cơ bản của LSI là thực hiện nhóm các thuật ngữ tương đương để hình thành “khái niệm” hay “chủ đề” và tài liệu sẽ được đại diện bởi các khái niệm hay chủ đề này. Vì tổng số khái niệm sẽ nhỏ hơn nhiều so với tổng số thuật ngữ, do vậy đòi hỏi ít bộ nhớ lưu trữ hơn và thời gian tính toán sẽ nhanh hơn. Mô hình LSI Mô hình không gian Term – Doc Mô hình term – topic - doc Hình 3.1. Mô hình LSI Mô hình này minh hoạ một cách tiếp cận trực tiếp hơn mối liên quan giữa các tài liệu và các thuật ngữ như trong truy tìm vector, trong đó tồn tại một lớp giữa trong đó bao gồm cả lược đồ câu truy vấn và lược đồ tài liệu. Không gian của khái niệm có thể có kích thước nhỏ hơn. Chẳng hạn, chúng ta có thể xác định rằng câu truy vấn t3 trả lại kết quả là d2, d3,d4 trong tập các câu hỏi, dựa vào sự quan sát cho thấy chúng có liên quan đến khái niệm C2, không yêu cầu tài liệu đó phải chứa term t3. Câu hỏi đặt ra là làm thế nào để thu được không gian khái niệm?. Một cách khả quan để có thể tìm thấy những miêu tả chính tắc của ngôn ngữ tự nhiên, nhưng đây là một nhiệm vụ khó đạt được. Đ ể đơn giản hơn, chúng ta có thể sử dụng nhữ ng thuộc tính toán học của ma trận term – doc, ví dụ, xác định những khái n iệm bằng cách tính toán ma trận. 3.3.2 Phương pháp luận LSI Chỉ mục ngữ nghĩa tiềm ẩn (LSI) là một kỹ thuật được thiết kế để giải quyết vấn đề đồng nghĩa và các vấn đề đa nghĩa của từ ngữ. Kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn giả thiết rằng có một số cấu trúc tiềm ẩn trong các mẫu có các từ đồng thời xuất hiện, thông qua các tập và các phép thử tài liệu để mô hình hóa những phần phụ thuộc giữa các từ và tài liệu. LSI dùng kỹ thuật tách các giá trị đơn (SVD- Singular Value Decomposition) để giảm bớt kích thước ma trận term - doc, không gian r chiều xuống một không gian s chiều, s<<r, không gian mới này được gọi là không gian khái niệm. Tất cả các thuật ngữ M và các tài liệu N có thể được thể hiện dưới dạng các vector trong không gian s chiều. Do vậy, các từ không còn độc lập nhau, và những từ đồng nghĩa sẽ tương ứng cùng kích thước hoặc có cùng độ tương đồng trong không gian này. Các tài liệu với những mẫu từ tương tự sẽ gần nhau dù chúng không chia sẻ những từ chung, điều này cho thấy rằng kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn có thể phát hiện ra những mối quan hệ ngữ nghĩa học tiềm ẩn giữa những tài liệu. Ví dụ, chỉ mục ngữ nghĩa tiềm ẩn sẽ thấy được “laptop” và “portable” xuất hiện nhiều trong cùng ngữ cảnh và có vectơ tương tự. Xét ma trận term – doc - Gọi A là ma trận term-doc với M cột (Terms) và N hàng (Docs). - Các phần tử của ma trận là trọng số w t  i,j  được tính từ lược đồ tf-idf. At • q At q query•doc1 query•doc2 ... N query•doc6 doc1 doc2 doc3 t doc4 doc5 doc6 Hình 3.2. Mô hình tính toán và xếp thứ hạng cho các tài liệu Hình 3.2 minh hoạ ma trận term –doc A có thể được dùng để tính toán thứ hạng của các tài liệu đối với câu truy vấn q như thế nào. Kỹ thuật LSI sử dụng kỹ thuật SVD bằng cách trong ma trận S chỉ lựa chọn những giá trị đơn lớn nhất, giữ lại những cột tương ứng U và VT. Ma trận kết quả được gọi là As và được cho bởi: - As = Us x Ss x VsT trong đó s, s < r là kích thước của không gian khái niệm. - Tham số s cần phải: o Đủ lớn để phù hợp với đặc trưng của dữ liệu; o Đủ nhỏ để lọc ra những chi tiết không liên quan. N s N M A = U S VT MxN Mxs Term vectors sxs sxN Document vectors Hình 3.3. Minh hoạ kỹ thuật Chỉ số hoá ngữ nghĩa tiềm ẩn (LSI) Trong trường hợp tìm kiếm tài liệu văn bản, hạng r của ma trận A bằng tổng khái niệm. U được xem như ma trận tương tự tài liệu – khái niệm, V là ma tậr n tương tự thuật ngữ - khái niệm. Thí dụ, u 2,3 = 0.6 có nghĩa là khái niệm 3 có trọng số 0.6 trong tài liệu 2 và v1,2 = 0.4 có nghĩa rằng độ tương đồng giữa thuật ngữ 1 và khái niệm 2 là 0.4. Trên cơ sở SVD, chúng ta lưu trữ các ma trận U, S và V thay cho A, làm giảm đáng kể vùng nhớ cần lưu trữ. Thí dụ, giả sử M=1.000.000, N=10.000 và r=500.  ổnTg số không gian lưu trữ đòi hỏi sẽ là 1.000.000x500+500x500+10.000x500=505.25 MB. Giá tịr này nhỏ hơn nhiều so với 10 GB để lưu trữ A. Trong khi tìm kiếm , độ tương đồng giữa tài liệu và câu truy vấn được tính như sau: vector tìm kiếm q trong không gian thuật ngữ được chuyển sang vector qc trong không gian khái niệm bằng cách nhân nó với V T như sau: qc = VT x q Độ tương đồng giữa câu truy vấn với từng tài l iệu được tính bằng tích vô hướng hay hệ số cosin giữa qc và mỗi hàng của U. Do vậy, với việc sử dụng LSI, chúng ta sẽ làm việc với vector s chiều thay cho vector r chiều khi tính độ tương đồng. Vì s nhỏ hơn r nhiều lần, cho nên tính toán sử dụng LSI sẽ nhanh hơn nhiều lần so với phương pháp trực tiếp. * Các bước sắp xếp tài liệu sử dụng kỹ thuật LSI: Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn Q; Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss có chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N và ma trận Us có chiều là M x s tương ứng Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này; Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều: q=qTUsSs-1 Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa câu truy vấn và tài liệu. Công thức tính toán để t ính các giá trị tương đồng cosin trong mô hình không gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu. q * d Cosèdi = S(q,d)= q d Ví dụ: cho 3 tài liệu sau: d1: Shipment of gold damaged in a fire. d2: Delivery of silver arrived in a silver truck. d3: Shipment of gold arrived in a truck. Sử dụng kỹ thuật LSI để sắp xếp các tài liệu này cho truy vấn “gold silver truck”. Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn: Terms d1 d2 d3 q a 1 1 1 0     arrived damaged 0 1 1 1 0 0 0 0     delivery fire 0 1 0 1 0 0 0 0     gold in A = 1 1 0 1 1 1 q = 1 0     of 1 1 1 0 1    shipment silver  0 1 0 2 0 0 1 truck 0 1 1     1 Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT   U = − 0.2626 − 0.4201  − 0.4201 − 0.2626  − 0.3151  − 0.2995  0.3794 0.0748 0.0748 − 0.3794 − 0.6093 − 0.2001  − 0.4201 0.0748 − 0.0460 − 0.2995 − 0.1206  − 0.1576 − 0.1206  − 0.2001 0.2749 − 0.3046 0.2749 0.4078  − 0.4538 − 0.2006  − 0.4538  4.0989 0.0000 0.0000 0.1547  − 0.0460  − 0.0460 0.1547   − 0.4013  0.4078  S = 0.0000  0.0000  2.3616 0.0000 0.0000  1.2737  − 0.4945 0.6492 − 0.5780 − 0.4945 − 0.6458 − 0.5817 − 0.6458  − 0.7194 0.2469 − 0.2556 V 0.7750  T =  0.6492  − 0.7194 − 0.2556 0.2469  0.7750  V =      Bước 3: Thực hiện giảm chiều vector bằng cách giữ lại các cột đầu tiên của U và V và các cột và hàng đầu tiên của S. − 0.4201  − 0.2995 − 0.1206  − 0.1576 − 0.1206  U ≈ U s = − 0.2626 − 0.4201  − 0.4201 − 0.2626  − 0.3151  − 0.2995 0.0748   − 0.2001 0.2749   − 0.3046 0.2749   0.3794  0.0748   0.0748  − 0.3794  − 0.6093 − 0.  2001  4.0989  S ≈ S s = 0.0000  0.0000  2.3616 V ≈ Vs − 0.4945  = − 0.6458 − 0.5817 0.6492   − 0.7194 0.2469   s V T ≈ V T  − 0.4945 =   0.6492  − 0.6458 − 0.7194  − 0.5817  0.2469  Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian 2 chiều rút gọn này. Các hàng của V giữ các giá trị vector đặc trưng. Đây là các tọa độ của các vectors tài liệu riêng, vì vậy d1(-0.4945, 0.6492) d2(-0.6458, -0.7194) d3(-0.5817, 0.2469) Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian 2 chiều rút gọn q=qTUsSs-1 Lưu ý: Đây là các toạ độ mới của vector truy vấn trong không gian hai chiều. Chú ý xem ma trận này và ma trận truy vấn q ban đầu đã cho ở Bước 1 khác nhau như thế nào. q=qTUsSs-1 − 0.4201  − 0.2995 − 0.1206  − 0.1576 − 0.1206  0.0748   − 0.2001 0.2749   − 0.3046 0 − 2749  1     0.0000  q= [0 0 0 0 0 1 0 0 0 1 1] − 0.2626 − 0.4201 0.3794   4.0989 1  0.0748   0.0000  q = [− 0.2140  − 0.1821]  − 0.4201 − 0.2626  − 0.3151  − 0. − 0.2995   0.0748  0.3794   − 0.6093  2001 2.3616  Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa câu truy vấn và tài liệu. S(q,d)= q * d q d S(q,d1)=  (−0.2140)(−0.4945) + (−0.1821)(0.6492)  = −0.0541 (−0.2140) 2 + (−0.1821) 2 (−0.4945) 2 + (0.6492) 2 S(q,d2)= (−0.2140)(−0.6458) + (−0.1821)(0.7194)  = 0.9910 (−0.2140) 2 + (−0.1821) 2 (−0.6458) 2 + (−0.7194) 2 S(q,d3)= (−0.2140)(−0.5817) + (−0.1821)(0.2469)  = 0.4478 (−0.2140) 2 + (−0.1821) 2 (−0.5817) 2 + (0.2469) 2 Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng: d2>d3>d1 Chúng ta có thể thấy rằng tài liệu d 2 có giá trị tương đồng cao hơn d3 và d1. Vector của nó gần với vector truy vấn hơn các vector khác. * Kỹ thuật tách giá trị đơn (SVD): Ý tưởng của kỹ thuật tách giá trị đơn (SVD) là tách các đặc trưng chủ yếu của ma trận term-doc AT và xấp xỉ nó bởi các ma trận nhỏ hơn. Định lý SVD được phát biểu như sau: Ma trận bất kỳ A với kích thước MxN số thực có thể biểu diễn như sau: A = U * S * VT trong đó, U là ma trận trực giao cột M * r với r là hạng (rank) của ma trận A, S là ma trận đường chéo và V là ma trận trực giao cột N * r. Ma trận trực giao cột U có nghĩa là UT * U = I, I là ma trận đồng nhất. Nếu S không tăng (các phần tử được s ắp xếp theo thứ tự giảm dần) thì phân tách trên đây là duy nhất. Như vậy, kỹ thuật SVD tách một ma trận thành tích của 3 ma trận. Việc tách có thể có độ phức tạp tính toán là O(n3), độ phức tạp này là đáng kể, nó tạo ra sự ước tính gần đúng. Documents r r r Terms A = U S VT N r x r r x N MxN M x r Hình 3.4. Mô hình minh hoạ tách giá trị đơn (SVD) * Các bước tính SVD đầy đủ cho một ma trận A: Bước 1: Tính hoán vị của A: AT và ATA. Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần. Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1. Bước 4: Sử dụng thứ tự các giá trị đặc trưng ở bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT. Bước 5: Tính U với U=AVS -1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT . Ví dụ: Tính SVD đầy đủ cho ma trận sau đây: 4 A =  3 Bước 1: Tính hoán vị của A: AT và ATA 0   − 5 Ma trận hoán vị AT =  − 5  4 3  4 3  4 0   25 − 15  0  è AT A =  0    =   − 5 3  − 5  − 15  25  Bước 2: Xác định các giá trị đặc trưng của ATA và sắp xếp theo thứ tự giảm dần. Căn bậc hai lúc này để tính giá trị đơn của A 25 − c AT A − cl =   − 15 − 15   25 − c  | ATA – cl | = (25-c)(25-c) – (-15)(-15) = 0 phương trình đặc trưng c2 – 50c+400=0 Phương trình bậc 2 cho 2 giá trị Theo thứ tự giảm dần, có | 40 | > | 10 | Các giá trị đặc trưng c1 = 40; c2 = 10 Các giá trị đơn s1=   40 = 6.3245  > s2 =  10 = 3.1622 Bước 3: Xây dựng ma trận đường chéo S bằng cách đặt các giá trị đơn theo thứ tự  giảm dần dọc theo đường chéo của nó. Tính nghịch đảo S-1   S = 6.3245 0  S −1 = 0.1581 0   0 3.1622  0 0.3162 Bước 4: Sử dụng thứ tự các giá trị đặc trưng từ bước 2 và tính các vector đặc trưng của ATA. Đặt các giá trị đặc trưng đó dọc theo cột của V và tính hoán vị VT Với c1=40 Với c2=10 25 − 40  − 15   −15  −15  25 − 10  − 15   − 15  − 15 AT A − cl =   =   AT A − cl =   =    − 15 25 − 40 −15 −15  − 15 25 − 10 − 15 − 15 (ATA – cl) x1 = 0 (ATA – cl) x2 = 0 − 15 − 15  x1  = 0  15 − 15  x1  = 0             − 15 − 15  x2  0 − 15 15   x2  0 -15x1 + -15x2 = 0 -15x1 + -15x2 = 0 -15x1 + -15x2 = 0 15x1 + 15x2 = 0 Giải thích cho x2 cho bởi công thức Giải thích cho x2 cho bởi công thức khác: x2=x1 khác: x2=x1 x  x1   x1   x1   x1  x 2 1 x = = 1 =  x  =  x  2  x   x   2  − 1   2   1  Chia bởi chiều dài của nó, x 2 1 L = 2 + x 2 = x1 2 L = 2 + x 2 = x1 2  1   1  x  x1 / L   2   0.7071   x1 / L  x = = 2  = 0.7071 1 =   =   =   1       − x1 / L = − 1   2  − 0.7071   0.7071  x1 / L 0.7071 = 1   2  0.7071 V = [x1 x2 ] =  − 0.7071   0.7071 T 0.7071  V = 0.7071 − 0.7071  0.7071  Bước 5: Tính U với U=AVS-1. Để hoàn thành việc chứng minh, tính SVD đầy đủ sử dụng công thức A=USVT 4 U = AVS −1 =  0   0.7071   0.7071 0.1581 0     3 − 5 − 0.7071 0.7071  0 0.3162 4 U = AVS −1 =  3  0   0.1118   − 5 − 0.1118  0.2236  0.2236 0.4472 U = AVS −1 =  0.8944 0.8944   − 0.4472 0.4472 A = USV T =  0.8944  6.3245   0  0.7071   − 0.7071  0.8944 − 0.4472  0 3.1622 0.7071 0.7071  0.4472 A = USV T =  0.8944 0.8944  4.4721   − 0.4472 2.2360 − 4.4721  2.2360  3.9998 0  4 0  A = USV T =   ≈   2.9999 − 4.9997 3 2 − 5 Tính trực giao của các ma trận V và U có được bằng cách xem xét các vector đặc trưng của chúng. Điều này có thể được chứng minh bởi các tích điểm giữa các vector cột. Tất cả các tích điểm đều được cho = 0. Ngoài ra, chúng ta có thể vẽ và thấy được tất cả các trực giao. CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM 4.1 Giới thiệu bài toán Chương trình xây dựng nhằm giải quyết bài toán có đầu vào và đầu ra như sau: Input: tập gồm rất nhiều dữ liệu văn bản được lưu trữ trong máy tính dưới dạng không nén. Output: Danh sách các tệp văn bản chứa từ hay cụm từ trong câu truy vấn. Với đầu vào và đầu ra của bài toán như trên thì chương trình phải đáp ứng các yêu cầu sau: • Chương trình cho phép thu thập và tạo chỉ mục tài liệu; • Cho phép cập nhật lại chỉ mục mỗi khi có tài liệu mới được đưa vào hệ thống; • Cho phép người dùng nhập vào câu truy vấn, sau đó thực hiện tìm kiếm các tài liệu liên quan đến câu truy vấn; • Sắp xếp các tài liệu theo thứ tự giảm dần về độ tương quan của tài liệu và câu truy vấn, sau đó hiển thị kết quả cho người dùng. 4.2 Chức năng chương trình Chương trình được xây dựng với các chức năng chính sau: - Tập hợp tài liệu - Tách từ từ các tài liệu - Tính trọng số của các từ ứng với mỗi tài liệu - Chọn lọc các từ có giá trị phân biệt cao làm chỉ mục - Lập chỉ mục cho các từ tạo nên tài liệu - Cập nhật lại chỉ mục khi thêm tài liệu mới - Hiển thị kết quả tìm kiếm cho người dùng. 4.3 Quy trình phát triển ứng dụng Để xây dựng một chương trình đáp ứng các chức năng trên, cần thực hiện các bước sau đây: 4.3.1 Xây dựng ma trận Term – Doc Xây dựng ma trận Term – Doc A có kích thước MxN (M thuật ngữ, N tài liệu) bao gồm các tần số tfij của thuật ngữ i trong tài liệu j. Ma trận này là ma trận chỉ chứa những thuật ngữ xuất hiện tập trung trong một số tài liệu. 4.3.2 Lập chỉ mục tài liệu Mục tiêu của làm chỉ mục là tìm ra các thuật ngữ tốt nhất để đại diện tài liệu sao cho các tài liệu được truy tìm chính xác trong tiến trình truy vấn. Tiến trình chỉ mục tự động bao gồm các bước sau: • Tách các từ từ các tài liệu; • Loại bỏ từ dừng; • Nhận biết các từ đồng nghĩa. Mọi thuật ngữ có ý nghĩa tương tự sẽ thay thế bằng từ chung; • Tính trọng số các thuật ngữ trong tài liệu bằng công thức: Wij = tfij * log (N/dfj); • Tạo tệp mục lục trên cơ sở các thuật ngữ và trọng số của thuật ngữ nói trên. 4.3.3 Xây dựng ma trận trọng số Ma trận trọng số được xây dựng bằng cách tính trọng số của các từ ứng với mỗi tài liệu. Trọng số của một thuật ngữ phản ánh tầm quan trọng của thuật ngữ đó trong tài liệu. Khi gán trọng số thuật ngữ, cần phải quan tâm đến cả hai: tần số thuật ngữ (tfij) và tần số tài liệu (dfj). Công thức chung để tính trọng số thuật ngữ là: Wij = tfij * log (N/dfj) trong đó, Wij là trọng số của thuật ngữ j trong tài liệu i, tfij là tần số của thuật ngữ j trong tài liệu i, N là tổng số tài liệu trong tập tài liệu, dfj là tần số tài liệu chứa thuật ngữ j. Trọng số trên đây tỷ lệ với tần số thuật ngữ và tỷ lệ nghịch với tần số tài liệu, công thức này thường được gọi là tf.idf. [idf=log(N/dfi)]. 4.3.4 Tìm kiếm theo mô hình vector Việc tìm kiếm trong mô hình không gian vector được thực hiện dựa trên cơ sở tính tương đồng giữa câu truy vấn Qj và các tài liệu Di. Độ tương đồng giữa tài liệu Di và câu truy vấn Qj được tính như sau: N S (Di , Q j ) = ∑Tik .Q jk k =1 Để bù vào độ chênh lệch giữa kích thước tài liệu và kích thước câu truy vấn, tính tương đồng nói trên có thể chuẩn hóa với è là góc của hai vector (gọi là khoảng cách cosin) và được tính theo công thức: i j S (D , Q  ) = cosè =  Di .Q j N ∑Tik .Q jk = k =1 | Di || Q j | N 2 N 2 ∑Tik . k =1 ∑ Q jk k =1 Đây là hệ số cosine quen thuộc giữa vector Di và Qj. Khi tìm kiếm , danh sách trả về được sắp xếp theo thứ tự giảm dần của độ tương đồng. 4.3.5 Phương pháp LSI Bước1: Đánh trọng số thuật ngữ và xây dựng ma trận term-doc A và ma trận truy vấn Q; Bước 2: Tách ma trận A thành tích của các ma trận và tìm các ma trận U, S, V, trong đó: A = USVT Bước 3: Thực hiện giảm chiều ma trận bằng cách tạo một ma trận vuông Ss có chiều là s x s từ ma trận S. Tương tự như vậy cho ma trận Vs có chiều là s x N và ma trận Us có chiều là M x s tương ứng Bước 4: Tìm các toạ độ vector tài liệu mới trong không gian giảm chiều này; Bước 5: Tìm các tọa độ véc tơ truy vấn mới trong không gian giảm chiều: q=qTUsSs-1 Bước 6: Sắp xếp các tài liệu theo thứ tự giảm dần của giá trị tương đồng cosin giữa câu truy vấn và tài liệu. Công thức tính toán để tính các giá trị tương đồng cosin trong mô hình không gian vector cơ sở. Thực chất là tính tích điểm giữa các toạ độ vector câu truy vấn và tài liệu chia cho tích của độ dài vector truy vấn và vector tài liệu. q * d Cosèdi = S(q,d)= q d 4.2 Cài đặt thử nghiệm Chương trình được cài đặt trên nền C#. Chương trình gồm 2 phần: phần lập chỉ mục và phần tìm kiếm. Phần tìm kiếm được chia ra làm 2 modul: tìm kiếm theo mô hình vector và tìm kiếm theo kỹ thuật LSI. 4.2.1 Giao diện màn hình lập chỉ mục Hình 4.1: Giao diện màn hình lập chỉ mục 4.2.2 Giao diện màn hình cập nhập chỉ mục Hình 4.2: Giao diện màn hình cập nhập chỉ mục 4.2.2 Tìm kiếm tài liệu theo mô hình vector Giao diện màn hình tìm kiếm theo mô hình vector và kết quả tìm kiếm: Hình 4.3. Giao diện tìm kiếm theo mô hình vector KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 1. KẾT LUẬN Kỹ thuật tìm kiếm thông tin trong hệ thống cơ sở dữ liệu đa phương tiện đã và đang là một vấn đề mang tính thời sự của Công nghệ thông tin. Bản luận văn này đã đề cập được một số vấn đề mang tính chất cơ sở của CSDL đa phương tiện và một số kỹ thuật tìm kiếm văn bản theo nội dung trong CSDL đa phương tiện như mô hình Bool cơ sở, mô hình không gian vector, và một số kỹ thuật nâng cao tìm kiếm như: lọc bằng phân lớp, phương pháp tính không đều tam giác, kỹ thuật phân cụm và đặc biệt đi sâu vào tìm hiểu kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (LSI - Latent Semantic Indexing). Bản luận văn cũng đã xây dựng chương trình thử nghiệm, demo chức năng lập chỉ mục và một số kỹ thuật tìm kiếm văn bản đơn giản như mô hình không gian vector. Đây cũng là cơ sở cho việc tiếp tục xây dựng và đánh giá tính hiệu quả của các kỹ thuật nâng cao tìm kiếm sau này. Do sự eo hẹp về thời gian cũng như hạn chế về tài liệu và trình độ lập trình còn yếu kém nên bản luận văn chưa thể đi sâu vào việc xây dựng và cài đặt một chương trình thử nghiệm áp dụng kỹ thuật nâng cao trong tìm kiếm văn bản theo nội dung như mong muốn. 2. HƯỚNG PHÁT TRIỂN Đây là một đề tài có tính thực tế cao. Với nhiệm vụ là nghiên cứu, luận văn đã đáp ứng được một số yêu cầu cơ bản đặt ra.Tuy nhiên để áp dụng kỹ thuật nâng cao tìm kiếm vào một chương trình ứng dụng cụ thể cho người sử dụng thì đòi hỏi phải có thêm thời gian nghiên cứu không chỉ với các kỹ thuật tìm kiếm mà còn một số kỹ thuật khác liên quan đến việc truy tìm sao cho đạt hiệu quả tốt nhất. Do đó hướng phát triển của luận văn như sau: ü Thêm chức năng tự thu thập tài liệu định kì và tự động cập nhập chỉ mục; ü Cài đặt chương trình tìm kiếm văn bản sử dụng kỹ thuật nâng cao; ü Phát triển ứng dụng có áp dụng kỹ thuật nâng cao tìm kiếm để cung cấp một bộ máy tìm kiếm hiệu quả cho người sử dụng (cụ thể là áp dụng vào hệ thống thư viện số). TÀI LIỆU THAM KHẢO Tiếng Việt [1] Đặng Văn Đức (2004/2005), “Multimedia Database Management System” Chương 1,Chương 4, Chương 9. [2] Đặng Văn Đức (2007), “Nâng cao hiệu năng MMDMS (Multimedia Database Management System)”, Bài 8. Tiếng Anh [1] Guojun Lu, “Multimedia Database Management Systems”, Artech House, Boston, London, 1999. [2] Subrahmanian V.S., “Principles of Multimedia Database Systems”, Morgan Kaufmann Publishers, Inc., California, 1998. [3] David Hand, Heikki Mannila, Padhraic Smyth, Principles of Data Mining, A Bradford Book The MIT Press Cambridge, Massachusetts LondonEngland, 2001. [4] Xu, Feilong, Latent Semantic Indexing. [5] Witten I.H, Moffat A., Bell C.T., “Managing Gigabytes, Compressing and Indexing Documents and Images”, Second Edition, Morrgan Kaufman Publishers, 1999. [6] Theory of Information Retrieval, Florida State University LIS-5263 (Fall, 2003): “Vector Model Information Retrieval”, Written by Rich Ackerman, September 25. 2003. [7] Thomas K Lundauer,Peter W. Foltz,Darrel Laham, “Introduction to Latent Semantic Analysis”. [8] Karl Aberer(2003/4), EPFL-SSC, “Latent Semantic Indexing”, Tr 36-67. [9] Deerwater, Dumais, Furnas, Landauer, Harshman, “Latent Semantic Indexing” Website [1] Từ điển bách khoa toàn thư: [2] Trang [3] Trang mã nguồn mở: