Luận văn Kỹ thuật tìm kiếm văn bản trên cơ sở nội dung trong cơ sở dữ liệu đa phương tiện

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 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 trên, 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 (nó làm thuật ngữ chỉ mục tốt). Tổng kết về chỉ mục tự động tài liệu Mục tiêu của việc 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: - Nhận biết các từ trong tiêu đề, tóm tắt, hoặc/và tài liệu - Loại bỏ từ dừng bằng cách tham khảo từ điển đặc biệt hay danh sách dừng. - Nhận biết các từ đồng nghĩa bằng tham khảo từ điển đồng nghĩa. Mọi thuật ngữ có ý nghĩa tương tự sẽ thay thế bằng từ chung. - Tìm từ gốc (stemming) bằng thuật toán loại bỏ các tiền tố và hậu tố (suffix và prefix). - Đếm tần số stem trong mỗi tài liệu 33 }) ),(|({1 }) ),()(|({1100 trueisdtrelevantDdcard trueisdtrelevanttAdDdcardxR test test t    )( test Tt t Tcard R R test   - Tính toán trọng số các thuật ngữ hay từ gốc. - Tạo tệp mục lục trên cơ sở các thuật ngữ và trọng số nói trên. 2.2 Thước đo hiệu năng [1] [5] [8] Giả sử D là tập hữu hạn các tài liệu, A là thuật toán lấy xâu chủ đề t làm dữ liệu đầu vào và cho lại tập tài liệu A(t) làm đầu ra, ta có A(t)  D. Hơn nữa, giả sử rằng tính chất phù hợp (relevant) có hai đối số: chủ đề t và tài liệu d. Nếu relevant(t,d) là true thì tài liệu d được xem như có liên quan đến chủ đề t. Ví dụ, tính chất phù hợp có thể được thực hiện bằng tay trên tập thử cụ thể Dtest D của các tài liệu và tập thử tương tự Ttest của các chủ đề. Thông thường hiệu năng truy tìm thông tin được đo bằng ba tham số speed, recall và precision như sau: - Speed: Tốc độ truy tìm càng cao hiệu năng càng cao - Recall: Đo công suất truy tìm các mục thông tin liên quan từ CSDL. Được xác định bởi tỷ lệ giữa tổng số mục liên quan được chỉ ra và toàn bộ số các mục liên quan trong CSDL. Recall càng cao thì hiệu năng càng cao. Hình 2.2 Mô tả recall Recall của thuật toán A là thước đo có bao nhiêu tài liệu được cho lại bởi câu truy vấn. Recall Rt kết hợp với chủ đề t cho bởi công thức sau: Rt = (number relevant that are retrieval)/(total number relevant) hay: Tỷ lệ recall R tổng thể kết hợp với tập tài liệu thử Dtest và tập chủ đề Ttest sẽ được cho bởi: Nói cách khác, đếm mọi tài liệu trong phần giao nhau của hai vùng (cộng thêm 1) rồi chia cho tổng số thành phần tổng vùng không tô (cộng thêm 1). - Precision: Đo độ truy tìm chính xác. Nó được xác định bởi tỷ lệ giữa số mục được chỉ ra là có liên quan với tổng số mục được tìm thấy. Độ chính xác càng cao hiệu năng hệ thống càng cao. 50 Tài liệu liên quan Tài liệu do thuật toán truy vấn tài liệu cho lại 20 150 Mọi tài liệu 34 Hình 2.3 Mô tả Precision Ta nói rằng độ chính xác (precision) của thuật toán A liên quan đến tính chất relevant và tập thử Dtest và chủ đề tTtest sẽ là: Cộng 1 vào tử số và mẫu số để tránh chia cho không. Ta nói rằng precision của thuật toán A tuân thủ vị ngữ relevant và tập thử Dtest và tập chủ đề Ttest sẽ là P%: hay: P = (number retrieved that are relevant)/(total number retrieved) Nói cách khác, độ chính xác của thuật toán A cùng truy vấn thông tin với thừa nhận các tập thử phù hợp, các khái niệm liên quan được cho bởi việc quyết định bao nhiêu câu trả lời thuật toán cho là thực sự đúng. Do đó, ta có thể đếm tổng số đối tượng trong phần giao trong hình 2.3, sau đó chia số này cho tổng số đối tượng trong vòng tròn được tô (các số này được cộng thêm 1). Ví dụ: Các số liệu được chỉ ra trong hình 2.2, recall của truy vấn chủ đề cụ thể là: Tương tự, precision của cùng chủ đề này được tính: Trong thực tế phải xem xét precision và recall đồng thời. Thông thường là recall càng cao thì precision càng thấp. Với hệ thống có recall cao và precision thấp có nghĩa rằng hệ thống cho lại danh sách nhiều kết quả, nhưng nhiều mục trong đó không liên quan. Ngược lại hệ thống có precision cao và recall thấp có nghĩa là còn nhiều mục liên quan câu truy vấn mà không tìm ra. Do vậy khi so sánh hiệu năng hai hệ thống thì phải so sánh cả recall và precision. Một kỹ thuật so sánh có thể là xác định các giá trị gán cho recall và precision trong khoảng 0 đến 1 và vẽ đồ thị cho chúng như hình 2.4. Hệ thống nào có đồ thị xa gốc tọa độ hơn thì có hiệu năng cao hơn. )( test Tt t Tcard P P test  )})(|({1 }) ),()(|({1 100 tAdDdcard trueisdtrelevanttAdDdcardxP test test t    Tài liệu do thuật toán truy vấn tài liệu cho lại Mọi tài liệu Tài liệu liên quan 71 21 15020 120    171 21 115020 120    35 (0,0) 1 1 Recall Precision Hình 2.4 Đồ thị so sánh hiệu năng Giả sử rằng CSDL có 1000 mục thông tin, trong đó có 10 mục liên quan đến câu truy vấn. Ví dụ truy vấn trong hệ thống cho lại danh sách như sau: R, R, I, I, R, R, I, I, R, I, R, R, I, I, R Trong đó, R là các mục liên quan đến câu truy vấn, I là các mục không liên quan đến câu truy vấn theo kết luận của người sử dụng. Chú ý rằng, chỉ người sử dụng mới biết được item nào liên quan (hệ thống không biết việc này). Bảng sau đây là các tính toán recall, precision dành cho các item khác nhau: Tổng số item cho lại Recall Precision 1 1/10 1/1 2 2/10 2/2 3 2/10 2/3 4 2/10 1/2 5 3/10 3/5 6 4/10 4/6 7 4/10 4/7 8 4/10 4/8 9 5/10 5/9 10 5/10 5/10 11 6/10 6/11 12 7/10 7/12 13 7/10 7/13 14 7/10 7/14 15 8/10 8/15 Bảng 2.1 Kết quả recall và precision Bảng này cho thấy càng nhiều item cho lại thì recall càng cao và precision càng thấp. Khi đánh giá hiệu năng ta thường tính precision với các giá trị recall cố định (Ví dụ: 0.1, 0.2, ...0.9, 1.0). Thực nghiệm cần thực hiện nhiều truy vấn, sau đó tính trung 36 bình cộng các giá trị precision tại cùng giá trị recall để có tập các cặp trung bình cộng recall-precision của hệ thống. Tại giá trị recall cố định, precision càng cao thì hiệu năng hệ thống càng cao. Chỉ mục ảnh hưởng đến recall và precision cũng như ảnh hưởng đến hiệu năng hệ thống. Nếu chỉ mục không bao phủ toàn bộ items thì hệ thống không thể tìm ra mọi item liên quan với câu truy vấn dẫn tới recall thấp. Nếu chỉ mục không chính xác, một số item không liên quan được lấy ra từ hệ thống, dẫn tới precision thấp. Thước đo tương tự đặc biệt quan trọng và phải phù hợp với kết luận của người sử dụng. Nếu không precision của hệ thống sẽ thấp. 2.3 Mô hình truy tìm không gian vectơ [1] [11] Mô hình truy tìm Bool khá đơ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, mô hình này tương đối khó hình thành các câu truy vấn 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 truy tìm khác có thể thay thế như không gian véctơ, thống kê và trên cơ sở cụm (cluster)... Trong mô hình không gian véctơ, giả sử rằng tồn tại cố định tập 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 Qj được biểu diễn như hai véctơ: 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), có thể là chỉ số tf-idf hay trọng số có được từ các cách khác. Việc truy tìm trong mô hình không gian véctơ đượ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 k jkikji QTQDS 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 véctơ (gọi là khoảng cách cosin) và được biểu diễn như sau:     N k jk N k ik N k jkik ji ji ji QT QT QD QD QDS 1 2 1 2 1 . . |||| . cos),(  37 Khi truy tìm, danh sách cho lại sẽ được xếp hạng theo thứ tự tính tương đồng giảm dần. Ví dụ, có 4 tài liệu và truy vấn được đại diện bởi các véctơ 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] 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 véctơ là nó coi các thuật 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) 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.4 Mô hình truy tìm theo xác suất [1] [6] Mô hình truy tìm theo xác suất xem xét các phụ thuộc và quan hệ của các thuật ngữ. Nó dựa trên bốn tham số sau đây: P(rel): Xác suất tính phù hợp của tài liệu. P(nonrel): Xác suất tính không phù hợp của tài liệu a1 : Giá trị kết hợp với việc truy tìm tài liệu không liên quan a2 : Giá trị kết hợp với việc không truy tìm tài liệu liên quan Vì việc truy tìm tài liệu không phù hợp hết a1P(nonrel) và loại bỏ các tài liệu phù hợp hết a2P(rel), tổng số thời gian truy tìm sẽ tối ưu nếu a2P(rel)  a1P(nonrel) Nhiệm vụ chính của mô hình truy tìm xác suất là dự báo P(rel) và P(nonrel) như thế nào. Thông thường, điều được thực hiện với giả sử rằng sự phân bổ xuất hiện một số thuật ngữ trong các tài liệu. Mô hình xác suất cung cấp chỉ dẫn quan trọng cho đặc trưng hóa tiến trình truy tìm. Tuy nhiên, hiệu quả truy tìm không được nâng cao là mấy, vì rất khó khăn để có được P(rel) và P(nonrel). 38 2.5 Mô hình truy tìm trên cơ sở cụm [1] [6] Trong các mô hình truy tìm thông tin đã khảo sát ở trên, 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 truy tì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 điều đó, ta nhóm các tài liệu tương đồng vào các cụm (cluster). Các cụm được biểu diễn bởi một vài thuộc tính nào đó, được gọi đại diện cụm. Đại diện cho một cụm giống như một truy vấn đầu vào, sẽ được phán đoán bên trong cụm chứa những tài liệu phù hợp với truy vấn. Nói cách khác, chúng ta hy vọng đại diện cụm để phân biệt những tài liệu phù hợp với những tài liệu không phù hợp khi đối sánh với bất kỳ truy vấn nào. 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, 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ư “véctơ tài liệu” trong mô hình không gian véctơ. 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 liệu 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ốn kém 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 cụm thô và tương đối “rẻ” so với 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ý. Truy tìm trên cơ sở cụm Khi các cụm được hình thành, tìm kiếm tài liệu sẽ đem lại hiệu quả. Mỗi cụm có véctơ đại diện, thường là tâm của chúng. Tâm của cụm được tính bằng véctơ trung 39 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 truy tìm tài liệu, các véctơ 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 véctơ 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ỏ. - Véctơ truy tìm được so sánh với từng véctơ 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ả. 2.6 Kỹ thuật phản hồi phù hợp [1] [11] 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. Đ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 phù 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 liệ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 để truy tìm tài liệu. Các quy tắc trên đây được diễn giải như sau:     lNonD i lD iii ii DDQQ ReRe )()1(  trong đó, Q(i+1) là truy vấn mới, Q(i) là truy vấn hiện hành, Di là tập hợp các tài liệu truy tì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 cách tiếp 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. Đ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 hưởng lợi từ việc đ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 40 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. Để điều chỉnh tài liệu, 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: - Thuật ngữ có trong truy vấn, nhưng không có 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. Hiệu năng tăng khi các truy vấn tiếp theo tương tự các truy vấn được sử dụng để hiệu chỉnh tài liệu đã đưa ra. Tuy nhiên, cách tiếp 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.7 Mô hình LSI (Latent semantic indexing) [1] [5] [6] [7] [8] [9] Truy tìm không gian vectơ có thể dẫn tới sự truy tìm “nghèo nàn”: Trong câu trả lời có thể bao gồm cả những tài liệu không liên quan; những tài liệu phù hợp mà không chứa ít nhất một thuật ngữ chỉ mục thì không được truy tìm. Lý do là việc truy tìm dựa vào những thuật ngữ chỉ mục mập mờ, không rõ ràng. Hơn nữa, nhu cầu thông tin của người sử dụng có liên quan đến những khái niệm và những ý tưởng nhiều hơn là những thuật ngữ chỉ mục. 2.7.1 Ý tưởng cơ bản của LSI Mặc dù mô hình vectơ cũng đã thành công nhưng nó vẫn tồn đọng một số vấn đề, tài liệu không liên quan có thể được truy tìm, đơn giản vì các thuật ngữ xuất hiện ngẫu nhiên trong nó. Mặt khác, những tài liệu có liên quan thì có thể bị bỏ qua bởi không có thuật ngữ trong tài liệu xuất hiện trong truy vấn (có thể coi đó là vấn đề về từ đồng nghĩa). Từ đó, một ý tưởng thú vị xét xem liệu việc truy tìm có thể dựa vào các khái niệm có hiệu quả hơn là trên các thuật ngữ? Trước tiên, bằng việc ánh xạ các thuật ngữ vào một “không gian khái niệm” và sau đó thiết lập việc xếp hạng các đối tượng tương đồng trong không gian khái niệm. Tức là, các thuật ngữ tương đồng (cùng phạm trù) được nhóm lại để hình thành khái niệm (concept) làm đại diện cho tài liệu. Ý tưởng được trình bày như sau: 41 Hình 2.5 Sử dụng các khái niệm cho truy vấn Trên đây là minh họa cách tiếp cận, tồn tại một tầng ở giữa tạo thành mối liên hệ giữa các truy vấn và các tài liệu. Cho thấy, không gian của các khái niệm có thể có kích thước nhỏ hơn. Chẳng hạn, xác định được truy vấn t3 với d2, d3, d4 trong tập trả lời dựa vào việc quan sát thấy chúng có liên quan đến khái niệm c2, ngoài việc d3 phải chứa thuật ngữ đó. Có thể có khả quan tìm được các biểu diễn phù hợp với chuẩn ngôn ngữ tự nhiên, nhưng đây là một công việc rất khó đạt được. Bằng cách đơn giản hơn, chúng ta có thể sử dụng những tính chất toán học để tính toán trong ma trận thuật ngữ - tài liệu (term – document) để xác định những khái niệm. Mục đích của mô hình là làm sao giảm được kích thước không gian, tăng khả năng tính toán mô hình các tài liệu và các truy vấn, gồm những khái niệm ở mức cao với số lượng ít hơn so với những thuật ngữ chỉ mục. Vì thế, truy tìm trên một không gian khái niệm đã được giảm lược sẽ đem lại hiệu quả tốt hơn, so với truy tìm trong không gian kích thước lớn của các thuật ngữ chỉ mục. Nhiệm vụ của LSI là sử dụng kỹ thuật SVD (Singular Value Decomposition) gọi là kỹ thuật tách giá trị số ít, được sử dụng nhiều trong lý thuyết ma trận nhằm giảm kích thước bảng tần số. Thông thường, bất kỳ giảm thiểu nào đều dẫn tới mất mát thông tin, do vậy ta phải đảm bảo rằng SVD phải có “năng lực thông tin” (information efficient) cao nhất có thể. Có nghĩa là, chúng chỉ mất phần bảng tần số ít ý nghĩa nhất. Nói cách khác, kỹ thuật LSI sử dụng ma trận thuật ngữ - tài liệu (td) để biểu diễn ma trận nhỏ hơn (kk). Nó được thực hiện bằng việc loại bỏ vài hàng và vài cột của ma trận tần số gốc. Các bước thực hiện cơ bản của LSI như sau: 1. Tạo bảng: Tạo ma trận tần số term-document (thuật ngữ-tài liệu) 2. Xây dựng SVD: Tính toán phân tích bảng tần số gốc thành ba ma trận khác có số chiều nhỏ hơn 3. Nhận dạng vectơ: Với mỗi tài liệu, tập các khái niệm tương ứng với các hàng không bị loại bỏ. 4. Tạo chỉ số: Lưu trữ các vectơ khái niệm được chỉ số bởi một kỹ thuật nào đó. 42 Khi khai thác tài liệu tương tự với truy vấn (cũng được xem như một tài liệu), ta chỉ đơn giản tìm cấu trúc chỉ số được tạo ra (ở bước 4) và tìm tài liệu trong tập hợp sao cho vectơ tài liệu gần với vectơ truy vấn, sử dụng thước đo đã chọn trên vectơ. 2.7.2 Một số khái niệm cơ bản Trước tiên, ta quan tâm tới một số khái niệm sau: Xét ma trận term – document: - Gọi X là một ma trận term – document (td) với t hàng (các thuật ngữ) và d cột (các tài liệu). Ví dụ, cho ma trận sau:        53 12 A        1431 6502 B Ta nói, ma trận A có bậc là (22), ma trận B có bậclà (24). Tích của hai ma trận được định nghĩa tổng quát như sau: Cho hai ma trận M1 và M2 Tích (M1M2) là ma trận: trong đó, Ví dụ:       53 12        1431 6502 =       23351511 131445 - Với mỗi phần tử của ma trận này được gán một trọng số wij, được tính bằng lược đồ tf-idf Một số khái niệm cơ bản về ma trận: - Ma trận chuyển vị (transpose) AT: chuyển hàng của ma trận A (mn) thành cột của AT(mn). Ví dụ: ... ............ ... ... ... ............ ... ... 2 2 2 2 2 1 2 2 2 2 2 1 1 2 1 2 1 1 2 1 1 1 2 1 1 2 1 2 2 2 1 1 1 1 2 1 1 1                               n m nn m m n m nn m m bbb bbb bbb M aaa aaa aaa M ... ............ ... ... )( 2 1 2 2 2 1 2 1 2 2 2 1 1 1 1 2 1 1 21                n m nn m m ccc ccc ccc xMM    1 1 )( n r r j i r i j xbac 43 T       1431 6502 =             16 45 30 12 - Hai vectơ x, y cùng bậc là trực giao khi và chỉ khi xTy = 0                         0 0 0 121 20 5 10 yxT - Ma trận A là trực giao khi và chỉ khi (ATA) là ma trận đơn vị (identity) ATA =                   10 01 10 01 10 01 - Ma trận chéo A: + Ma trận chéo (diagonal) A:  A có bậc (m x m)  i ≠ j → A(i,j) = 0, với 1 ≤ i, j ≤ m. ví dụ:        10 01 X            500 030 001 Y              2000 0400 0000 0001 Z Ma trận chéo phải là ma trận vuông và mọi phần tử nằm trên đường chéo của nó không nhất thiết phải khác 0. + Ma trận A bậc (m x m) không tăng (nonincreasing) khi và chỉ khi  i ≤ j → A(i,i) ≥ A(j,j) , với 1 ≤ i, j ≤ m. Ý tưởng thực hiện, tách các đặc trưng chủ yếu của ma trận term-doc và xấp xỉ nó bởi các ma trận nhỏ hơn, sử dụng kỹ thuật SVD (singular value decomposition). 2.7.3 Kỹ thuật SVD (singular value decomposition) Phân tích cấu trúc latent semantic bắt đầu với một ma trận các thuật ngữ - tài liệu. Ma trận này sau khi được phân tích bằng việc phân tích các giá trị số ít (Singular value decomposition – SVD) để nhận được mô hình cấu trúc latent semantic đặc biệt. SVD có mối quan hệ mật thiết với một số kỹ thuật toán học và thống kê, bao gồm việc phân tích các vectơ và phân tích các hệ số. Ví dụ, bảng 2.2 đưa ra một tập dữ liệu. Trong ví dụ này, tập tài liệu gồm có nhan đề của 9 bản ghi. Các từ xuất hiện trong nhiều hơn một nhan đề được lựa chọn để đánh chỉ mục (được in nghiêng). Chú ý rằng, có hai lớp nhan đề: 5 nhan đề về sự tương tác con người – máy tính (được gán c1- c5) và 4 nhan đề về lý thuyết đồ thị 44 (được gán m1- m4). Mỗi phần tử trong ma trận thuật ngữ-tài liệu thường là tần số xuất hiện mỗi thuật ngữ thực tế xuất hiện trong mỗi tài liệu. Ở đây, giống như một ma trận có thể được sử dụng trực tiếp các truy tìm dựa trên từ khóa hay đầu vào ban đầu của việc phân tích SVD. Trong ví dụ này, chúng ta lựa chọn cẩn thận các tài liệu và các thuật ngữ sao cho SVD sẽ đem lại một giải pháp tốt sử dụng đúng hai chiều. Tiêu đề: c1: Giao diện máy cho các ứng dụng máy tính Lab ABC với con người c2: Nghiên cứu sự đánh giá của người sử dụng về thời gian hệ thống máy tính trả lời c3: Hệ thống quản lý giao diện người sử dụng EPS c4: Kiểm thử kỹ thuật xây dựng hệ thống và con người EPS c5: Mối quan hệ của người sử dụng - thời gian trả lời thấy được độ sai lệch đo lường m1: Sinh các cây ngẫu nhiên, nhị phân, không có thứ bậc. m2: Đồ thị tác động qua lại của đường dẫn trong các cây m3: Thứ bậc đồ thị: Chiều rộng của cây và hầu như là được sắp thứ tự tốt m4: Thứ bậc đồ thị: Sự nghiên cứu Tài liệu Thuật ngữ c1 c2 c3 c4 c5 m1 M 2 m3 m4 con người 1 0 0 1 0 0 0 0 0 giao diện 1 0 1 0 0 0 0 0 0 máy tính 1 1 0 0 0 0 0 0 0 người sử dụng 0 1 1 0 1 0 0 0 0 hệ thống 0 1 1 2 0 0 0 0 0 trả lời 0 1 0 0 1 0 0 0 0 thời gian 0 1 0 0 1 0 0 0 0 EPS 0 0 1 1 0 0 0 0 0 nghiên cứu 0 1 0 0 0 0 0 0 1 cây 0 0 0 0 0 1 1 1 0 đồ thị 0 0 0 0 0 0 1 1 1 thứ bậc 0 0 0 0 0 0 0 1 1 Bảng 2.2 Số lần xuất hiện của thuật ngữ trong mỗi tài liệu Kiểm thử với việc tìm kiếm các tài liệu phù hợp với truy vấn: “sự tương tác giữa con người với máy tính”. Các kỹ thuật đối chiếu thuật ngữ đơn giản sẽ đưa ra được kết quả các tài liệu c1, c2 và c4 khi chúng có một hay nhiều thuật ngữ trong truy 45 vấn. Tuy nhiên, hai tài liệu khác cũng thích hợp là c3 và c5 bị bỏ sót bởi chúng không có các thuật ngữ chung nào với truy vấn. Hình sau biểu diễn hình học hai chiều cho các thuật ngữ và các tài liệu bởi việc phân tích SVD. Hình 2.6 Biểu đồ 2-D của 12 thuật ngữ và 9 tài liệu từ tập mẫu. Các thuật ngữ được biểu diễn bởi các hình tròn đậm. Các tài liệu được biểu diễn bằng những hình vuông rỗng, và các thuật ngữ thành phần nằm trong dấu ngoặc đơn. Truy vấn “sự tương tác giữa con người với máy tính” được biểu diễn như một “giả - tài liệu” tại q. Các trục được vẽ theo tỷ lệ cho các so sánh tài liệu với tài liệu hay thuật ngữ với thuật ngữ. Tất cả các tài liệu về con người- máy tính (từ c1 đến c5) là “gần” với truy vấn (giới hạn trong hình nón), không có các tài liệu về thuyết đồ thị (m1- m4) gần với truy vấn. Trong không giản giảm lược này, thậm chí các tài liệu c3 và c5 không đóng góp các thuật ngữ với truy vấn. Chi tiết kỹ thuật SVD Phần này trình bày chi tiết cơ sở toán học đặc trưng của mô hình latent là SVD. Ví dụ với ma trận hình chữ nhật t×d của các thuật ngữ và các tài liệu X, có thể được phân tích với tích số của ba ma trận khác nhau: X = T0S0D0T Trong đó - T0 và D0 là các ma trận có các cột trực giao - S0 là ma trận chéo (m×m) của các giá trị số ít được sắp xếp giảm dần, trong đó m = min(t, d), là hạng của X. - Phân rã như vậy luôn tồn tại và là duy nhất Cấu trúc của SVD: - T0 là ma trận của các vectơ riêng (giá trị số ít) nhận được từ ma trận X×XT - D0 là ma tận của các vectơ riêng (giá trị số ít) nhận được từ ma trận XT×X 46 - Các thuật toán xây dụng SVD của một ma trận t×d có độ phức tạp O(d3) nếu dt Hình 2.7 Sơ đồ SVD của một ma trận hình chữ nhật thuật ngữ- tài liệu. Ma trận gốc thuật ngữ - tài liệu được phân tích trong ba ma trận các thành phần phụ thuộc tuyến tính. Ví dụ, phân tích SVD của ma trận sau: X =        53 04 Trong đó: XXT =       3412 1216 ; XTX =         2515 1525 - Tính D0 dựa vào ma trận XTX: + Trước tiên, tính các giá trị riêng (giá trị số ít) dựa vào công thức Det(X-cI) = 0 với c là giá trị riêng và I là ma trận đơn vị: Det         c c 2515 1525 =0 tức là: (25-c)(25-c)-(-15)(-15) = 0 Nên ta có: c2 – 50c +400 = 0 Vậy, tính được c1 = 40 và c2 = 10 Dựa vào các giá trị riêng để tính các vecto riêng theo công thức: (X-cI)x = 0 với x là vecto riêng cần tìm. + Với c1 = 40:         402515 154025       2 1 x x =       0 0 -15x1 – 15x2 = 0 và -15x1 – 15x2 = 0, vậy x2 = -x1 Nên ta có:       2 1 x x =        1 1 x x Ta tính được: L = 22 2 1 xx  = x1 2 documents term X = T0 S0 D0T t × d t × m m × m m × d 47 Và x1 =            L x L x 1 1 =              2 1 2 1 =        707.0 707.0 + Với c2 = 10, ta cũng có x2 = x1 - Tương tự, tính T0 dựa vào ma trận XXT cũng với các giá trị riêng là 40 và 10 Vì thế, ta có ma trận với các giá trị riêng tăng dần tính được từ XTX và XXT - Ma trận chéo các giá trị riêng S0 được tính: S0 =                16.30 032.6 100 040 2 1 2 1 Vậy, từ ma trận A có thể phân tích SVD thành các ma trận sau:         447.0894.0 894.0447.0       16.30 032.6         707.0707.0 707.0707.0 Nói chung, với X = T0S0D0T, các ma trận T0, D0, và S0 tất cả phải được xếp hạng. Sử dụng SVD có thể nhận được một “xấp xỉ” của X bởi chỉ các giá trị số ít lớn nhất trong ma trận S0. Tích của các ma trận kết quả là một ma trận Xˆ xấp xỉ bằng X và có hạng là k. Việc lựa chọn k xác định bao nhiêu “các khái niệm quan trọng”, với giả định rằng các khái niệm với giá trị số ít nhỏ hơn trong S0 được xem như “nhiễu” và vì vậy có thể bỏ qua. Các giá trị số ít trong S0 được sắp xếp, đầu tiên k lớn nhất được giữ lại và những tập nhỏ hơn còn lại nhận giá trị 0. Khi đó, các số 0 được đưa vào S0, việc biểu diễn có thể được làm đơn giản hóa bằng việc xóa những hàng và các cột bằng 0 của S0 để thu được một ma trận đường chéo mới S, và sau đó xóa các cột tương ứng của T0 và D0 để nhận được T và D tương ứng. Kết quả là một mô hình đã giảm lược: X ≈ Xˆ = TSDT Mô hình được giảm lược, trình bày trong hình 2.8, sử dụng để xấp xỉ với dữ liệu. Hình 2.8 Sơ đồ của SVD được giảm lược của một ma trận thuật ngữ-tài liệu. Ma trận thuật ngữ tài liệu gốc gần đúng sử dụng k giá trị số ít lớn nhất và các vectơ số ít tương ứng Documents term Xˆ = T S DT t × d t × k k × k k × d 48 Giảm lược SVD của ma trận thuật ngữ- tài liệu X, trong đó: T, D là ma trận trực giao S là ma trận đường chéo các giá trị số ít t là số hàng của X d là số cột của X m là hạng của X (min(t,d)) k là số chiều được chọn trong mô hình giảm lược (km) Giảm lược số chiều, lựa chọn k là tới hạn với thực hiện này. Đúng như ý tưởng, chúng ta muốn một giá trị k đủ lớn để phù hợp với mọi đặc tính cấu trúc thực của dữ liệu, nhưng đủ nhỏ để lọc ra các chi tiết không phù hợp hay các chi tiết không quan trọng. Ví dụ, trong ví dụ trước thực hiện tính toán với 9 tài liệu (c1..c5, m1..m4) và 12 thuật ngữ, ma trận X (12×9) được cho bởi số lần xuất hiện của mỗi thuật ngữ trong mỗi tài liệu:                                        110000000 111000000 011100000 100000010 000001100 000010010 000010010 000002110 000010110 000000011 000000101 000001001 X Với ma trận 12×9 của các thuật ngữ và các tài liệu, X được phân tích thành ba ma trận khác là T0S0DT0, trong đó T0 và D0 có các cột trực giao. T0 gồm các vectơ giá trị số ít 9 chiều với 12 thuật ngữ S0 là ma trận đường chéo của 9 giá trị số ít D0 gồm các vectơ giá trị số ít 9 chiều với 9 tài liệu 49                                                    18.068.034.028.030.001.014.045.003.0 23.068.016.011.007.000.022.062.004.0 23.025.029.039.059.003.023.049.001.0 58.004.047.008.054.003.018.027.021.0 17.002.003.027.011.019.033.014.030.0 05.002.028.017.008.007.043.011.027.0 05.002.028.017.008.007.034.011.027.0 27.003.017.021.016.033.036.017.064.0 01.000.000.038.033.010.034.006.040.0 49.006.030.025.011.059.016.004.024.0 11.001.007.050.028.055.014.007.020.0 41.006.052.034.011.041.029.011.022.0 0T                              36.0 56.0 85.0 31.1 50.1 64.1 35.2 54.2 34.3 0S                                      45.007.004,036.060.003.008.053.008.0 52.045.025.000.015.001.025.062.002.0 02.076.015.021.035.002.019.044.001.0 62.045.034.030.039.002.010.019.000.0 26.006.067.003.033.015.051.011.028.0 08.002.026.037.021.027.057.023.054.0 02.001.024.072.038.004.021.003.046.0 24.005.043.026.021.003.050.017.061.0 06.001.018.008.005.095.011.006.020.0 0D Bây giờ, chúng ta tìm xấp xỉ X bằng việc chỉ giữ lại hai giá trị số ít đầu tiên trong S0 và các cột tương ứng của ma trận T0 và ma trận D0. (Chú ý rằng, sử dụng sự kết hợp của T0 và D0 để xác định vị trí 12 thuật ngữ và 9 tài liệu, theo thứ tự định sẵn trong biểu diễn 2-chiều). Mô hình đã được giảm lược như sau: X Xˆ = TSDT 50                                           45.003.0 62.004.0 49.001.0 27.021.0 14.030.0 11.027.0 11.027.0 17.064.0 06.040.0 04.024.0 07.020.0 11.022.0       54.2 34.3        53.062.044.019.011.023.013.017.006.0 08,002.002.000.028.054.046.061.020.0                                               62.071.050.022.015.021.010.025.004.0 85.098.069.031.020.030.015.034.006.0 66.077.055.024.014.027.014.023.006.0 42.044.031.014.027.021.023.053.010.0 11.020.014.007.024.063.051.055.022.0 22.019.013.006.028.042.038.058.016.0 22.019.013.006.028.042.038.058.016.0 05.021.015.007.056.027.105.123.145.0 19.012.008.003.039.070.061.084.026.0 12.009.006.002.024.041.036.051.015.0 04.010.007.003.016.040.033.037.014.0 09.016.012.005.018.047.038.040.016.0 Xˆ Thông thường, kích thước đơn trong miền lớn vừa phải là 200. Xét ý nghĩa của nó mang lại: 1. Kích thước của bảng tần số gốc giả sử là (t×d), trong đó t là tổng số thuật ngữ và d là tổng số tài liệu. Dễ có đến t = 1 triệu và d = 10,000 ngay trong CSDL tài liệu nhỏ. 2. Sau khi đã giảm thiểu, kích thước của ba ma trận đơn giả sử còn 200: - Kích thước của ma trận thứ nhất là t×k. Với các số trên đây ta có 1 triệu×200 = 200 triệu đầu vào - Kích thước ma trận đơn là 200×200 = 40,000 đầu vào (sự thật là trong 40,000 đầu vào thì chỉ 200 cần phải lưu trữ, còn lại nhận giá trị 0). - Kích thước ma trận cuối cùng là k×d. Với các số trên ta có 200×10,000 =2 triệu đầu vào Cuối cùng ta có khoảng 202 triệu đầu vào trong bảng sau khi áp dụng SVD 51 3. Ngược lại, (t×d) gần tới 10 tỷ, nói cách khác SVD làm giảm đáng kể không gian sử dụng khoảng 1/50 so với bảng gốc. Chú ý: Trong nhiều trường hợp, ma trận gốc t×d là ma trận rải rác, nó có thể lưu trữ được bởi vì số phần tử nhỏ hơn t×d rất nhiều. Trong trường hợp này phân tích SVD lại làm tăng tổng số lưu trữ. Các phép so sánh cơ bản trong kỹ thuật SVD Về cơ bản, có ba phép so sánh cần quan tâm: So sánh hai thuật ngữ (trả lời câu hỏi “tương tự giữa các thuật ngữ i và j như thế nào?”); so sánh hai tài liệu (“tương tự giữa tài liệu i và j ra sao?”); và so sánh một thuật ngữ với một tài liệu (“thuật ngữ i và tài liệu j có mối quan hệ như thế nào?”). Trong cách tiếp cận vấn đề truy tìm thông tin, số lượng tương ứng để so sánh hai hàng với nhau, hai cột với nhau hay xem xét các ô riêng lẻ của ma trận gốc, ở đây chính là ma trận dữ liệu term-document X. Trong trường hợp này, chúng ta sẽ tạo các so sánh tương tự sử dụng ma trận Xˆ , khi nó được coi là biểu diễn các mẫu quan trọng và xác thực dữ liệu cơ bản trong X. Với Xˆ =TSDT, sự tương đồng có thể được tính toán sử dụng các ma trận nhỏ hơn như T, D và S. So sánh hai thuật ngữ: Tích vô hướng giữa hai vectơ hàng của Xˆ xác định phạm vi của hai thuật ngữ có tương đồng qua tập các tài liệu. Ma trận ( Xˆ Xˆ T) là ma trận vuông đối xứng chứa mọi tích số của thuật ngữ với thuật ngữ. Với S là ma trận chéo và D là ma trận trực giao, dễ dàng xác định được: Xˆ Xˆ T = TS2TT Chú ý, điều này có nghĩa là ô (i,j) của ( Xˆ Xˆ T) thu được bằng việc lấy tích giữa hàng i và j của ma trận TS. Đó là, nếu xét các hàng của TS tương đương với các thuật ngữ thì tích giữa các điểm đó chính là sự so sánh giữa các thuật ngữ. So sánh hai tài liệu: Phân tích việc so sánh hai tài liệu là tương đồng, trong trường hợp này nó là tích giữa hai vectơ cột của ma trận Xˆ , cho biết khả năng đánh giá hai tài liệu tương đồng mô tả qua các thuật ngữ. Vì vậy, ma trận ( Xˆ Xˆ T) chứa các tích điểm tài liệu đến tài liệu. Việc định nghĩa các ma trận T, S và D được đảm bảo rằng: Xˆ T Xˆ = DS2DT Ở đây, ô (i,j) của ( Xˆ T Xˆ ) thu được bằng việc tính tích giữa hàng i và j của ma trận DS. Vì thế, có thể coi các hàng của ma trận DS tương ứng với các tài liệu. So sánh một thuật ngữ với một tài liệu: Sự so sánh này khác với hai so sánh trước. Thay việc cố gắng để đánh giá tích điểm giữa các hàng hay giữa các cột của Xˆ , sự so sánh chủ yếu giữa một thuật ngữ và một tài liệu dựa vào giá trị của từng ô riêng lẻ trong Xˆ . Xˆ được định nghĩa trong các thuật ngữ của các ma trận T, S và D. Xˆ = TSDT 52 Bởi vậy, ô (i,j) của Xˆ thu được bằng việc tính tích giữa hàng i của ma trận TS1/2 với hàng thứ j của ma trận DS1/2. Chú ý rằng, So sánh (như đối với thuật ngữ- thuật ngữ hay tài liêu-tài liệu) gồm việc sử dụng các hàng của TS và DS cho các toạ độ. Tìm kiếm p tài liệu phù hợp đầu tiên cho truy vấn q Với q là một truy vấn, ta coi q như tài liệu và tạo lập vectơ Xq. Tuy nhiên, có một đặc điểm là: chỉ k khái niệm quan trọng là được xét chứ không phải xét tất cả t thuật ngữ. Khi được yêu cầu tìm ra p tài liệu phù hợp nhất với q, ta sẽ phải tìm p tài liệu d1, ..., dp như sau: 1. Với mọi 1 i jp, tính tương tự giữa Xq và di lớn hơn hay bằng tính tương tự giữa Xq và dj, 2. không có tài liệu dz nào mà tính tương tự giữa dz và Xq vượt quá tính tương tự của dp. Hoặc, có thể tính toán độ tương đồng giữa truy vấn và các tài liệu dựa trên tính toán cosin - Chuyển véctơ truy vấn q trong không gian thuật ngữ sang véctơ qc trong không gian khái niệm: qc = DT  q - Mức độ tương tự giữa truy vấn với từng tài liệ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 T. Có thể biến đổi (ánh xạ từ X vào D): X = T0 * S0 * D0T  S0-1 * T0T * X = D0T (lúc đó T0* T0T = 1)  D0 = XT * T0 * S0-1 + Áp dụng cùng sự biến đổi với q: qc = qT * T * S-1 + Sau đó so sánh các vectơ đã thay đổi bằng việc sử dụng biện pháp cosin chuẩn. |)(||| )(* ),cos( i T c i T c ic Dq Dq dq  ( TD )i biểu diễn cột thứ i của ma trận TD - Làm việc với véctơ k chiều thay cho véctơ t chiều (k nhỏ hơn t nhiều lần) Đánh giá hiệu năng mô hình LSI Kiểm nghiệm thực tế với tập dữ liệu MED, là tập dữ liệu chuẩn đầu tiên được nghiên cứu trên lý thuyết tập hợp thuộc y học, gồm 1033 tài liệu và 30 truy vấn. Việc chỉ mục tự động trên tất cả các thuật ngữ xuất hiện nhiều hơn trong một tài liệu và kết quả là 5823 thuật ngữ được đánh chỉ mục. SVD hệ số 100 của ma trận 5823 thuật ngữ với 1033 tài liệu đã được sử dụng và truy tìm hiệu quả, được đánh giá dựa vào 30 câu 53 truy vấn có thể có với tập dữ liệu. Đánh giá mô hình LSI trên tập dữ liệu MED dựa vào chỉ số recall và precision được biểu diễn trong sơ đồ sau: Hình 2.9 Đồ thị Recall – Precision của thuật toán LSI Phương pháp LSI thực hiện tốt ở những mức thấp nhất của recall thể hiện ở hai nhân tố: thứ nhất, độ chính xác (precision) tương đối tốt trong mọi hệ thống ở mức recall thấp, mang lại khả năng cải tiến. Thứ hai, LSI được thiết kế chủ yếu để giải quyết vấn đề về tính đồng nghĩa (vì thế tăng recall); ít thành công hơn trong vấn đề về tính đa nghĩa (precision) Precision Recall 54 CHƯƠNG 3. CÀI ĐẶT THỰC NGHIỆM MÔ HÌNH LSI 3.1 Bài toán Cơ sở dữ liệu đa phương tiện bao gồm văn bản, hình ảnh, âm thanh và video. Mỗi loại dữ liệu đều có tính chất đặc trưng riêng, vì thế phạm vi nghiên cứu sự biểu diễn, tổ chức, lưu trữ và truy vấn trên dữ liệu đa phương tiện là rất lớn. Trong đó, tài liệu văn bản là một loại dữ liệu rất quan trọng, loại dữ liệu này không thể thiếu trong các cơ quan, tổ chức, thư viện… và người ta có thể dùng nó để mô tả các loại dữ liệu khác. Trong một máy tìm kiếm, các loại dữ liệu đều phải trài qua quy trình xử lý để tìm ra những đặc trưng riêng của từng đối tượng, sau đó đối sánh với yêu cầu để tìm ra những dữ liệu phù hợp. Hệ thống truy tìm tài liệu văn bản cũng không nằm ngoài quy trình đó, các tài liệu được xử lý tìm ra đại diện của tài liệu, đồng thời câu truy vấn của người sử dụng đưa vào cũng được xử lý để đưa ra đại diện của truy vấn. Quá trình tiền xử lý này yêu cầu cách thức tìm ra đặc trưng của tài liệu, cách thức tổ chức lưu trữ tài liệu, quá trình xử lý văn bản để loại đi những yếu tố không cần thiết và rất nhiều các bước xử lý khác. Bài toán tập trung vào bước đối sánh đại diện của câu truy vấn với đại diện của tài liệu, nghiên cứu các kỹ thuật đem lại hiệu quả so sánh để đưa ra được những tài liệu phù hợp nhất, nhanh nhất. Trong thực tế, có rất nhiều kỹ thuật tìm kiếm, có kỹ thuật hiệu quả không cao song cách thức đơn giản, dễ hiểu, có kỹ thuật đem lại hiểu quả tốt, giảm bớt phức tạp song chưa linh hoạt và có những kỹ thuật được xem là tốt hơn... Một số kỹ thuật được nghiên cứu trong phạm vi luận văn như mô hình Boolean; mô hình không gian vectơ; mô hình tìm kiếm trên cơ sở cụm; mô hình tìm kiếm theo xác xuất; mô hình phản hồi phù hợp và mô hình tìm kiếm LSI. Bài toán tập trung vào mô tả kỹ thuật LSI, cài đặt kỹ thuật này bằng ngôn ngữ lập trình C# và sử dụng hệ quản trị cơ sở dữ liệu Microsoft Access. Chương trình mô phỏng thuật toán tìm kiếm LSI, phương pháp này chủ yếu tính toán trên ma trận. Các ma trận được xây dựng từ các tài liệu và các thuật ngữ xuất hiện trong các tài liệu đó, từ việc phân tích SVD để có thể tính toán, tìm ra các tài liệu được quan tâm dựa vào câu truy vấn nào đó. Trong hệ thống tìm kiếm, số lượng tài liệu có thể rất lớn, mỗi tài liệu lại có rất nhiều các thuật ngữ khác nhau, vì thế ma trận thuật ngữ - tài liệu (term – document) là rất lớn và để trả về được những tài liệu phù hợp thì phải đem so sánh yêu cầu với các đối tượng này. Điều này có thể rất phức tạp và gây tốn kém về thời gian, dung lượng nhớ. Kỹ thuật LSI nhằm giảm bớt sự phức tạp trong giai đoạn này và đem lại hiểu quả tìm kiếm. 55 Bài toán không đi sâu vào quá trình tiền xử lý văn bản, chỉ mô phỏng kỹ thuật đối sánh LSI cho thấy sự giảm lược chiều trong không gian thuật ngữ - tài liệu, tức là giảm thiểu sự phức tạp khi đi đối sánh giữa câu truy vấn và tập dữ liệu. 3.2 Chức năng của chương trình Hình 3.1 Sơ đồ chức năng Tài liệu văn bản được đọc vào bảng chứa tài liệu trong CSDL và đưa ra trong mục danh sách tài liệu. Nội dung của tài liệu đang được chọn trong danh sách hiển thị các tài liệu sẽ được đưa ra, sau đó gọi đến hàm có chức năng lấy danh sách các từ phân tích được trong tài liệu từ cơ sở dữ liệu và hiển thị bằng bảng hai chiều gồm từ và số từ. Qua quá trình phân tích, các kí tự như dấu câu, kí tự nối... (như dấu , : ; /...) sẽ bị loại bỏ và đem lại các từ, số lượng từ lấy từ nội dung tài liệu và lưu vào CSDL theo bảng từ nếu xuất hiện từ mới và thêm vào bảng số lượng từ nếu có sự thay đổi. Sau khi tài liệu được phân tích và xử lý, ma trận A (ma trận thuật ngữ - tài liệu) và vecto câu truy vấn q (do người dùng đưa vào) được tạo lập. Dựa vào kỹ thuật phân tích SVD để phân tích ma trận A thành các ma trận U, S, V và thiết lập chỉ số k (k≤ số tài liệu) để xây dựng các ma trận Uk, Sk và Vk theo kỹ thuật tìm kiếm LSI. Từ các ma trận xây dựng được, tính q và khoảng cách giữa mỗi tài liệu với q để đưa ra kết quả là các tài liệu được xem là “gần” với câu truy vấn q nhất. Chức năng xử lý việc kết nối với cơ sở dữ liệu Access thông qua giao thức kết nối OLEDB, chứa các hàm xử lý việc truy xuất, cập nhật, xóa dữ liệu. Chương trình tìm kiếm Tài liệu Phân tích và tìm kiếm Thêm tài liệu Xóa tài liệu Bước 1: Tìm ma trận (txd) và q Bước 2: Phân tích SVD Bước 3: Không gian giảm lược Bước cuối: Tìm tài liệu phù hợp và xếp hạng 56 3.3 Hoạt động cơ bản trong chương trình Giao diện chương trình gồm các chức năng chính: chức năng nhập thêm file; chức năng phân tích và tìm kiếm. Trong cửa sổ giao diện này gồm: khung bên trái chứa các file dạng text đã được đưa vào, bên phải chứa các thuật ngữ đã được đánh chỉ mục và tần số xuất hiện của thuật ngữ trong từng tài liệu được chọn, ở giữa là nội dung của file đang được chọn. Hình 3.2 Chức năng thêm tài liệu Lớp Tài liệu cho phép thêm file mới vào danh sách file bằng chức năng Thêm. Chức năng Xóa tài liêu cho phép bỏ đi những file không mong muốn. Hình 3.3 Chức năng xóa tài liệu Lớp Phân tích và tìm kiếm mô tả các bước tìm kiếm bằng phương pháp LSI. Trong lớp này, người dùng đưa ra một câu truy vấn đề tìm kiếm những tài liệu phù hợp. Bước 1 biểu diễn được ma trận thuật ngữ - tài liệu và ma trận câu truy vấn. 57 Hình 3.4 Chức năng phân tích và tìm kiếm tại bước 1 Sử dụng kỹ thuật phân tích SVD trong Bước 2 để được các ma trận mới. Hình 3.5 Chức năng phân tích và tìm kiếm tại bước 2 58 Hình 3.6 Chức năng phân tích và tìm kiếm tại bước 3 Trong Bước 3, chọn hệ số k – không gian giảm lược k chiều (giả sử ở ví dụ trên, chọn k =2) để giảm kích thước các ma trận tính được ở Bước 2. Các bước cuối cùng, tài liệu đã được sắp xếp giảm dần theo tính phù hợp của mỗi tài liệu với câu truy vấn. Dựa vào Bước 4, 5, 6 và kết quả xác định được vectơ các tài liệu và vectơ câu truy vấn trong không gian giảm lược k chiều. Bước này giúp việc tính toán khoảng cách giữa các vecto tài liệu và vecto câu truy vấn, nhằm xác định tài liệu nào là phù hợp hơn dựa vào giá trị tính được là lớn hơn. Ví dụ này cho thấy, vecto tài liệu document_1 là “gần” với câu truy vấn nhất rồi đến document_3, document_2. Độ phù hợp của tài liệu với câu truy vấn thể hiện góc tạo bởi mỗi vecto tài liệu với vecto câu truy vấn (góc nhỏ hơn được xem là gần với yêu cầu truy vấn hơn) – hình 3.8. 59 0.2 Document_1 (-0.4945,0.6492) Document_2 (-0.6458,-0.7194) Document_3 (-0.5817,0.2469) q (-0.1666,0.1923) 0.4 0.6 0.8 -0.4 -0.6 -0.8 -0.2 -0.2 Hình 3.7 Chức năng phân tích và tìm kiếm ở những bước cuối cùng Hình 3.8 Đồ thị biểu diễn các vecto tài liệu và vecto truy vấn 60 KẾT LUẬN Qua tìm hiểu và nghiên cứu, cho thấy tính ứng dụng, tính thiết thực của các hệ thống truy tìm thông tin (IR) đa phương tiện nói chung và truy tìm thông tin văn bản nói riêng. Luận văn đi sâu nghiên cứu vấn đề truy tìm văn bản trên cơ sở nội dung qua một số mô hình cụ thể. Qua một quá trình nghiên cứu, luận văn đã đạt được những kết quả sau: - Tìm hiểu tổng quan về cơ sở dữ liệu đa phương tiện, tầm quan trọng của cơ sở dữ liệu trong xã hội thông tin ngày nay. Hiểu được nguyên lý thiết kế CSDL đa phương tiện thông qua các nhiệm vụ thiết kế. - Nghiên cứu cách thức hoạt động của hệ thống truy tìm thông tin nói chung và nghiên cứu một số vấn đề chỉ mục, tìm kiếm tài liệu văn bản trên cơ sở nội dung nói riêng. - Tìm hiểu một số mô hình tìm kiếm như: Mô hình Boolean cơ sở, mở rộng; mô hình không gian vectơ; mô hình tìm kiếm trên cơ sở cụm; mô hình tìm kiếm theo xác xuất; mô hình phản hồi phù hợp và mô hình tìm kiếm LSI. - Cài đặt thử nghiệm chương trình mô phỏng thuật toán tìm kiếm bằng mô hình LSI. Bên cạnh đó, luận văn còn một số nhược điểm như: Chương trình mới chỉ mô tả được thuật toán tìm kiếm, chưa mô tả được hoàn thiện một chương trình tìm kiếm. Chưa so sánh được chi tiết các phương pháp tìm kiếm nêu ra; chưa đánh giá được hiệu năng tìm kiếm của từng phương pháp trên một tập dữ liệu cụ thể. Hướng nghiên cứu: Hoàn thiện chương trình tìm kiếm bằng mô hình LSI để có thể đưa vào ứng dụng. Tiếp tục tìm hiểu về các kỹ thuật tìm kiếm nâng cao dựa trên cơ sở nội dung đối với tài liệu văn bản nói riêng và tìm kiếm đối với cơ sở dữ liệu đa phương tiện nói chung. Đánh giá được khả năng tìm kiếm của các mô hình trên từng dữ liệu cụ thể. 61 TÀI LIỆU THAM KHẢO Tiếng Việt 1. PGS.TS. Đặng Văn Đức (2004-2008), Bài giảng Cơ sở dữ liệu đa phương tiện. Tiếng Anh 2. Karl Aberer (2003), Data Mining, Laboratoire de systèmeses d’informations répartis. 3. Ricardo Baeza, Berthier Ribeiro (1999), Modern Information Retrieval, ACM Press New York. 4. Jamie Callan (2008), Information Retrieval, Carnegie Mellon University. 5. Soumen Chakrabarti (2003), Mining the Web, Morgan Kaufmann Publishers. 6. Scott Deerwester et al (1990), Indexing by Latent Semantic Analysis, Journal of The American Society for Information Science. 7. Edel Garcia (2006), Latent Semantic Indexing (LSI) A Fast Track Tutorial, Grossman and Frieder’s Information Retrieval, Algorithms and Heuristics. 8. David Hand, Heikki Mannila & Padhraic Smyth (2001), Principles of Data Mining, The MIT Press, pp. 267-287. 9. Chris Manning et al (2007), Information Retrieval and Lantent Semantic Indexing, Lecture Notes, Marcus Uneson. 10. E.G.M Petrakis, Multimedia Information Retrieval, University of Maryland. 11. Gerard Salton, Chris Buckley (1988), Parallel text search methods, Communications of the ACM. 12. Marcel Worring, Multimedia Information Systems, Lecture Notes, University of Amsterdam. 13. Justin Zobel, Alistair Moffat (2006), Inverted File for Text Search Engines, ACM Computing Surveys, Volume. 38. Các trang web tham khảo: 1. full-svd.html 2.