Cùng với sự phát triển nhanh chóng của công nghệ tin học thì khối lượng dữ
liệu đa phương tiện (Multimedia) được thu thập và lưu trữ dưới dạng số ngày càng
nhiều dẫn tới việc tìm kiếm dữ liệu đa phương tiện trở nên khó khăn vì vậy cần có
các hệ thống tìm kiếm thông tin (Information Retrieval) hỗ trợ người dùng tìm kiếm
một cách chính xác và nhanh chóng các thông tin mà họ cần trên kho tư liệu khổng
lồ này.
Hiện nay có một số hệ thống tìm kiếm như GoogleDesktop, DTSearch,
Lucene, tuy nhiên các hệ thống này sử dung các kỹ thuật tìm kiếm đơn giản nên
hiệu quả còn chưa cao. Vì vậy mục tiêu của luận văn này nhằm tìm hiểu một số kỹ
thuật nâng cao tìm kiếm thông tin, cụ thể ở đây là tìm kiếm văn bản theo nội dung
trong cơ sở dữ liệu đa phương tiện nhằm đáp ứng nhu cầu cấp thiết của thời đại
bùng nổ thông tin điện tử hiện nay.
Bố cục của luận văn gồm các phần sau:
+ CHƯƠNG 1: TỔNG QUAN VỀ HỆ QUẢN TRỊ CSDL ĐA PHƯƠNG TIỆN:
Phần này sẽ giới thiệu tổng quan về hệ quản trị CSDL đa phương tiện.
+ CHƯƠNG 2: MỘT SỐ KỸ THUẬT CHỈ MỤC VÀ TÌM KIẾM VĂN BẢN
- Trình bày các v ấn đềvề hệ tìm kiếm thông tin.
- Trình bày kỹ thuật cơ sở chỉ mục văn bản trên cơ sở mô hình Bool và mô
hình vector.
+ CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM
VĂN
- Trình bày cơ sở lý thuyết về một số kỹ thuật chỉ mục nâng cao.
- Giới thiệu kỹ thuật chỉ mục nâng cao LSI.
+ CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM: Chương này
phát triển chương trình thử nghiệm áp dụng kỹ thuật chỉ mục và kỹ thuật tìm kiếm
văn bản theo nội dung trong cơ sở dữ liệu đa phương tiện.
+ KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: Trình bày các kết quả đạt được trong
luận văn và nêu phương hướng phát triển của đề tài trong tương lai.
+ TÀI LIỆU THAM KHẢO và PHỤ LỤC: Trình bày các thông tin liên quan đến
luận văn.
MỤC LỤC
MỤC LỤC 2
DANH MỤC CÁC TỪ TIẾNG ANH VÀ VIẾT TẮT . 5
DANH MỤC CÁC BẢNG . 6
DANH MỤC CÁC HÌNH, ĐỒ THỊ 6
MỞ ĐẦU . 7
CHƯƠNG 1: TỔNG QUAN HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ĐA PHƯƠNG
TIỆN (MDBMS) . 8
1.1 Mục đích của MDBMS 8
1.2 Các yêu cầu của một MDBMS 11
1.2.1 Khả năng quản trị lưu trữ lớn 13
1.2.2 Hỗ trợ truy vấn và khai thác dữ liệu 14
1.2.3 Tích hợp các phương tiện, tổng hợp và thể hiện 14
1.2.4 Giao diện và tương tác. 15
1.2.5 Hiệu suất. .15
1.3 Các vấn đề của MDBMS .16
1.3.1 Mô hình hoá dữ liệu MULTIMEDIA 16
1.3.2 Lưu trữ đối tượng MULTIMEDIA .17
1.3.3 Tích hợp Multimedia, thể hiện và chất lượng của dịch vụ (QoS) 19
1.3.4 Chỉ số hoá Multimedia 20
1.3.5 Hỗ trợ truy vấn Multimedia, khai thác và duyệt qua. 21
1.3.6 Quản trị CSDL Multimedia phân tán 22
1.3.7 Sự hỗ trợ của hệ thống 23
1.4 Kết luận 23
CHƯƠNG 2: MỘT SỐ KỸ THUẬT CHỈ MỤC VÀ TÌM KIẾM VĂN BẢN THEO
NỘI DUNG 25
2.1 Giới thiệu hệ tìm kiếm thông tin 25
2.1.1 Kỹ thuật tìm kiếm thông tin 25
2.1.2 Một số vấn đề trong tìm kiếm thông tin 26
2.1.3 Hệ thống tìm kiếm thông tin – IR 27
2.1.4 Sự khác biệt giữa các hệ thống IR và các hệ thống thông tin khác .32
2.1.5 Các hệ tìm kiếm văn bản thường được sử dụng hiện nay 34
2.2 Một số kỹ thuật tìm kiếm văn bản theo nội dung 35
2.2.1 Chỉ mục tự động văn bản và mô hình tìm kiếm Bool 35
2.2.1.1. Mô hình tìm kiếm Bool cơ sở 35
2.2.1.2 Tìm kiếm Bool mở rộng .37
2.2.1.3 Các bước để xây dựng hệ thống tìm kiếm thông tin – IR 39
2.2.1.4 Lập chỉ mục tài liệu 40
2.2.2 Mô hình tìm kiếm không gian vector 51
2.2.2.1 Mô hình tìm kiếm không gian vector cơ sở 51
2.2.2.2. Kỹ thuật phản hồi phù hợp (Relevance Feedback Technique) .53
2.2.3. Thước đo hiệu năng 55
2.3 Ví dụ 56
2.4 Kết luận .58
CHƯƠNG 3: MỘT SỐ KỸ THUẬT NÂNG CAO HIỆU NĂNG TÌM KIẾM VĂN
BẢN .59
3.1 Giới thiệu .59
3.2 Một số kỹ thuật nâng cao hiệu năng tìm kiếm đa phương tiện 60
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 .60
3.2.2 Các phương pháp trên cơ sở tính không đều tam giác 61
3.2.3 Mô hình tìm kiếm trên cơ sở cụm (cluster-based) .63
3.2.3.1 Sinh cụm .63
3.2.3.2 Tìm kiếm trên cơ sở cụm .64
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 64
3.3 Kỹ thuật LSI 66
3.3.1 Giới thiệu LSI 66
3.3.2 Phương pháp luận LSI .67
CHƯƠNG 4: PHÁT TRIỂN CHƯƠNG TRÌNH THỬ NGHIỆM 79
4.1 Giới thiệu bài toán .79
4.2 Chức năng chương trình .79
4.3 Quy trình phát triển ứng dụng 79
4.3.1 Xây dựng ma trận Term – Doc .80
4.3.2 Lập chỉ mục tài liệu 80
4.3.3 Xây dựng ma trận trọng số 80
4.3.4 Tìm kiếm theo mô hình vector 81
4.3.5 Phương pháp LSI .81
4.2 Cài đặt thử nghiệm .82
4.2.1 Giao diện màn hình lập chỉ mục 82
4.2.2 Giao diện màn hình cập nhập chỉ mục .83
4.2.2 Tìm kiếm tài liệu theo mô hình vector 83
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 84
TÀI LIỆU THAM KHẢO 86
86 trang |
Chia sẻ: maiphuongtl | Lượt xem: 2178 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm kiếm văn bản theo nội dung trong cơ sở dữ liệu đa phương tiện, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 50 -
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 51 -
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 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 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]
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 52 -
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
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 vector (gọi là khoảng
cách cosin) và được biểu diễn như dưới đây:
∑∑
∑
==
====
N
k
jk
N
k
ik
N
k
jkik
ji
ji
ji
QT
QT
QD
QD
QDS
1
2
1
2
1
.
.
||||
.
cos),( θ
Đâ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ố hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 53 -
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 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) 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 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 để tìm kiế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( βα
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 54 -
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 55 -
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
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):
[ ]1,0
P
RP
∈
∩
+Độ chính xác (Precision):
[ ]1,0
R
RP
∈
∩
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:
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)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 56 -
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:
(0,0)
Độ chính xác
Khả năng tìm thấy
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 57 -
• 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:
∴ ∑=
i
2
ji,WiD
7192.05173.01761.01761.04771.04771.0 22221 ==+++=D
0955.12001.11761.09541.04771.01761.0 22222 ==+++=D
3522.01240.01761.01761.01761.01761.0 22223 ==+++=D
5382.02896.01761.04771.01761.0W 222
i
2
jQ, ==++== ∑Q
Tiếp theo tính tất cả các tích điểm (bỏ qua các tích 0):
∴Q•Di=∑
i
ji,jQ, WW
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:
∴CosθDi = S(Q,Di) =
∑∑
∑
i
ji
j
jQ
i
jijQ
WW
WW
2
,
2
,
,,
Cos 0801.0
7192.0*5382.0
0310.0
* 1
1
1
==
•
=
DQ
DQ
Dθ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 58 -
Cos 8246.0
0955.1*5382.0
4862.0
* 2
2
2
==
•
=
DQ
DQ
Dθ
Cos 3271.0
3522.0*5382.0
0620.0
* 3
3
3
==
•
=
DQ
DQ
Dθ
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 59 -
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 60 -
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ủ đề đó.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 61 -
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ó:
|),(),(|max),( 1 jjmj kqdkidqid −≥ ≤≤
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 tiệ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 |),(),(|max)( 1 jjmj kqdkidil −= ≤≤ 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 để
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 62 -
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 63 -
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 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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 64 -
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 cụm 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 65 -
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 66 -
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 67 -
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 68 -
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
i,j
được tính từ lược đồ tf-idf.
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.
At • q
query•doc1
query•doc2
...
query•doc6
At
t
q
doc1
doc2
doc3
doc4
doc5
doc6
N t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 69 -
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.
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 trận
tương tự thuật ngữ - khái niệm. Thí dụ, u2,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. Tổng số không gian lưu trữ đòi hỏi sẽ là
1.000.000x500+500x500+10.000x500=505.25 MB. Giá trị này nhỏ hơn nhiều so
với 10 GB để lưu trữ A.
N
M =
MxN Mxs
sxN sxs
A
U
S
VT
Document vectors
Term vectors
N s
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 70 -
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 VT 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.
Cosθdi = S(q,d)= dq
dq *
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 71 -
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
a
arrived
damaged
delivery
fire
gold
in
of
shipment
silver
truck
d1 d2 d3
=
110
020
101
111
111
101
001
010
001
110
111
A
q
=
1
1
0
0
0
1
0
0
0
0
0
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 72 -
−−
−−−
−−
−−
−−
−
−−
−−−
−−
−−
−−
=
4078.02001.02995.0
4013.06093.03151.0
1547.03794.02626.0
0460.00748.04201.0
0460.00748.04201.0
1547.03794.02626.0
4538.02749.01206.0
2006.03046.01576.0
4538.02749.01206.0
4078.02001.02995.0
0460.00748.04201.0
U
=
2737.10000.00000.0
0000.03616.20000.0
0000.00000.00989.4
S
−
−−−
−−
=
7750.02469.05817.0
2556.07194.06458.0
5780.06492.04945.0
V
−−
−
−−−
=
7750.02556.05780.0
2469.07194.06492.0
5817.06458.04945.0
TV
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.
−−
−−
−−
−
−
−
−
−−
−
−−
−
=≈
2001.02995.0
6093.03151.0
3794.02626.0
0748.04201.0
0748.04201.0
3794.02626.0
2749.01206.0
3046.01576.0
2749.01206.0
2001.02995.0
0748.04201.0
sUU
=≈
3616.20000.0
0000.00989.4
sSS
−
−−
−
=≈
2469.05817.0
7194.06458.0
6492.04945.0
sVV
−
−−−
=≈
2469.07194.06492.0
5817.06458.04945.0T
s
T VV
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 73 -
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
q= [ ]11000100000
−−
−−
−
−
−
−
−−
−−
−
−−
−
2001.02995.0
6093.03151.0
3794.02626.0
0748.04201.0
0748.04201.0
3794.02626.0
274901206.0
3046.01576.0
2749.01206.0
2001.02995.0
0748.04201.0
3616.2
10000.0
0000.0
0989.4
1
q = [ ]1821.02140.0 −−
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)=
dq
dq *
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 74 -
S(q,d1)= 0541.0
)6492.0()4945.0()1821.0()2140.0(
)6492.0)(1821.0()4945.0)(2140.0(
2222
−=
+−−+−
−+−−
S(q,d2)= 9910.0
)7194.0()6458.0()1821.0()2140.0(
)7194.0)(1821.0()6458.0)(2140.0(
2222
=
−+−−+−
−+−−
S(q,d3)= 4478.0
)2469.0()5817.0()1821.0()2140.0(
)2469.0)(1821.0()5817.0)(2140.0(
2222
=
+−−+−
−+−−
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 75 -
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.
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 .
Documents
Terms =
MxN M x r
r x N r x r
A U
S V
T N
r r r
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 76 -
Ví dụ: Tính SVD đầy đủ cho ma trận sau đây:
−
=
53
04
A
Bước 1: Tính hoán vị của A: AT và ATA
Ma trận hoán vị
−
=
50
34TA
−
=
50
34
AAT
−53
04
−
−
=
2515
1525
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
−−
−−
=−
c
c
clAAT
2515
1525
| 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= 3245.640 = > s2 = 1622.310 =
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
=
1622.30
03245.6
S
=−
3162.00
01581.01S
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 77 -
Với c1=40 Với c2=10
−−
−−
=
−−
−−
=−
1515
1515
402515
154025
clAAT
−−
−−
=
−−
−−
=−
1515
1515
102515
151025
clAAT
(ATA – cl) x1 = 0 (ATA – cl) x2 = 0
=
−−
−−
0
0
1515
1515
2
1
x
x
=
−
−
0
0
1515
1515
2
1
x
x
-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
−
=
=
1
1
2
1
1 x
x
x
x
x
=
=
1
1
2
1
2 x
x
x
x
x
Chia bởi chiều dài của nó,
21
2
2
2
1 xxxL =+= 212221 xxxL =+=
−
=
−=
−
=
7071.0
7071.0
2
1
2
1
/
/
1
1
1 Lx
Lx
x
=
=
=
7071.0
7071.0
2
1
2
1
/
/
1
1
1 Lx
Lx
x
[ ]
−
==
7071.07071.0
7071.07071.0
21 xxV
−
=
7071.07071.0
7071.07071.0TV
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
−
−
== −
3162.00
01581.0
7071.07071.0
7071.07071.0
53
041AVSU
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 78 -
−
−
== −
2236.01118.0
2236.01118.0
53
041AVSU
−
== −
4472.08944.0
8944.04472.01AVSU
−
−
==
7071.07071.0
7071.07071.0
1622.30
03245.6
4472.08944.0
8944.04472.0
SVTUA
−
−
==
2360.22360.2
4721.44721.4
4472.08944.0
8944.04472.0
SVTUA
−
≈
−
==
523
04
9997.49999.2
09998.3
SVTUA
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.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 79 -
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:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 80 -
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)].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 81 -
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
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 vector (gọi là khoảng
cách cosin) và được tính theo công thức:
∑∑
∑
==
====
N
k
jk
N
k
ik
N
k
jkik
ji
ji
ji
QT
QT
QD
QD
QDS
1
2
1
2
1
.
.
||||
.
cos),( θ
Đâ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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 82 -
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.
Cosθdi = S(q,d)= dq
dq *
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 83 -
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 84 -
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;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 85 -
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ố).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 86 -
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ở:
Các file đính kèm theo tài liệu này:
- 1LV08_CNTTPhamThiNgoc.pdf