Tài liệu 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: 2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ THU TRANG
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
LUẬN VĂN THẠC SỸ
Hà Nội - 2010
3
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 5
DANH MỤC CÁC BẢNG 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ 7
MỞ ĐẦU 8
CHƯƠNG 1- TỔNG QUAN 11
1.1 Khái quát về cơ sở dữ liệu (CSDL) đa phương tiện [1] [10] [12] 11
1.1.1 Giới thiệu 11
1.1.2 Mục tiêu chính 13
1.1.3 Mô hình dữ liệu đa phương tiện 13
1.2 Trích chọn đặc trưng, chỉ mục và đo tính tương tự [1] 14
1.2.1 Trích chọn đặc trưng 15
1.2.2 Chỉ số hóa cấu trúc 16
1.2.3 Đo tính tương tự 17
1.3 Hệ thống truy tìm thông tin (IR-Information retrieval) [1] [3] [4] [9] [13] 17
1.3.1 Khái quát 17
1.3.2 Vấn đề truy tìm tài liệu văn bản (Text retrieval) 18
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System) 20
1.4 xếp hạng tài liệu (Ranking) [1] [8] 21
CHƯƠNG 2- MỘT SỐ KỸ THUẬT TÌM KIẾM 25
2.1 Các tru...
60 trang |
Chia sẻ: haohao | Lượt xem: 1217 | Lượt tải: 3
Bạn đang xem trước 20 trang mẫu tài liệu 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ THU TRANG
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
LUẬN VĂN THẠC SỸ
Hà Nội - 2010
3
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 5
DANH MỤC CÁC BẢNG 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ 7
MỞ ĐẦU 8
CHƯƠNG 1- TỔNG QUAN 11
1.1 Khái quát về cơ sở dữ liệu (CSDL) đa phương tiện [1] [10] [12] 11
1.1.1 Giới thiệu 11
1.1.2 Mục tiêu chính 13
1.1.3 Mô hình dữ liệu đa phương tiện 13
1.2 Trích chọn đặc trưng, chỉ mục và đo tính tương tự [1] 14
1.2.1 Trích chọn đặc trưng 15
1.2.2 Chỉ số hóa cấu trúc 16
1.2.3 Đo tính tương tự 17
1.3 Hệ thống truy tìm thông tin (IR-Information retrieval) [1] [3] [4] [9] [13] 17
1.3.1 Khái quát 17
1.3.2 Vấn đề truy tìm tài liệu văn bản (Text retrieval) 18
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System) 20
1.4 xếp hạng tài liệu (Ranking) [1] [8] 21
CHƯƠNG 2- MỘT SỐ KỸ THUẬT TÌM KIẾM 25
2.1 Các truy vấn Boolean và chỉ mục tài liệu [1] [5] [11] 25
2.1.1 Truy vấn Boolean 25
2.1.2 Cấu trúc tệp 26
2.1.3 Các từ dừng và từ gốc 27
2.1.4 Chỉ số hoá và bổ sung 28
2.1.5 Kỹ thuật nén chỉ số (index compression) 29
2.1.6 Chỉ mục tự động 31
2.2 Thước đo hiệu năng [1] [5] [8] 33
2.3 Mô hình truy tìm không gian vectơ [1] [11] 36
2.4 Mô hình truy tìm theo xác suất [1] [6] 37
2.5 Mô hình truy tìm trên cơ sở cụm [1] [6] 38
2.6 Kỹ thuật phản hồi phù hợp [1] [11] 39
2.7 Mô hình LSI (Latent semantic indexing) [1] [5] [6] [7] [8] [9] 40
2.7.1 Ý tưởng cơ bản của LSI 40
2.7.2 Một số khái niệm cơ bản 42
4
2.7.3 Kỹ thuật SVD (singular value decomposition) 43
CHƯƠNG 3- CÀI ĐẶT THỰC NGHIỆM MÔ HÌNH LSI 54
3.1 Bài toán 54
3.2 Chức năng của chương trình 55
3.3 Hoạt động cơ bản trong chương trình 56
KẾT LUẬN 60
TÀI LIỆU THAM KHẢO 61
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu viết tắt Tiếng Anh Tiếng Việt
CSDL DataBase Cơ sở dữ liệu
DBMS DataBase Manager System Hệ quản trị Cơ sở dữ liệu
IDF Inverse Document Frequency Tần số xuất hiện tài liệu
IR Information retrieval Truy tìm thông tin
LSI Latent Semantic Indexing Chỉ số hóa ngữ nghĩa ẩn
MIRS Multimedia Information Retrieval
System
Hệ thống truy tìm thông tin đa
phương tiện
SVD Singular Value Decomposition Tách giá trị riêng
TF Term Frequency Tần số xuất hiện thuật ngữ
6
DANH MỤC CÁC BẢNG
Bảng 1.1 Ma trận tài liệu - thuật ngữ..............................................................................23
Bảng 1.2 Ma trận kết quả tài liệu - thuật ngữ TF-IDF ....................................................24
Bảng 1.3 Kết quả khoảng cách từ truy vấn Q với các tài liệu..........................................24
Bảng 2.1 Kết quả recall và precision ..............................................................................35
Bảng 2.2 Số lần xuất hiện của thuật ngữ trong mỗi tài liệu .............................................44
7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hinh 1.1 Mô hình dữ liệu đa phương tiện .......................................................................14
Hình 1.2 Hệ thống IR tiêu biểu .......................................................................................19
Hình 1.3 Tiến trình truy vấn tài liệu................................................................................21
Hình 2.1 Sơ đồ duy trì các chỉ số trong tập hợp động .....................................................29
Hình 2.2 Mô tả recall......................................................................................................33
Hình 2.3 Mô tả Precision ................................................................................................34
Hình 2.4 Đồ thị so sánh hiệu năng ..................................................................................35
Hình 2.5 Sử dụng các khái niệm cho truy vấn .................................................................41
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......................................45
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 ..........................46
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 .................47
Hình 2.9 Đồ thị Recall – Precision của thuật toán LSI....................................................53
Hình 3.1 Sơ đồ chức năng...............................................................................................55
Hình 3.2 Chức năng thêm tài liệu ...................................................................................56
Hình 3.3 Chức năng xóa tài liệu .....................................................................................56
Hình 3.4 Chức năng phân tích và tìm kiếm tại bước 1.....................................................57
Hình 3.5 Chức năng phân tích và tìm kiếm tại bước 2.....................................................57
Hình 3.6 Chức năng phân tích và tìm kiếm tại bước 3.....................................................58
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...............................59
Hình 3.8 Đồ thị biểu diễn các vecto tài liệu và vecto truy vấn .........................................59
8
MỞ ĐẦU
Hàng nghìn năm trước con người đã nhận thức được tầm quan trọng của việc
lưu trữ và tìm kiếm thông tin. Với sự phát triển của máy tính, việc máy tính có khả
năng lưu trữ thông tin với số lượng lớn và tìm kiếm thông tin có ích từ các tập hợp trở
nên cần thiết. Lĩnh vực truy tìm thông tin (Information Retrieval - IR) ra đời vào
những năm 1950 vì nhu cầu thiết yếu này. Hơn 40 năm sau, lĩnh vực đó trưởng thành
đáng kể, nhiều hệ thống IR được sử dụng phổ biến với sự đa dạng trạng thái của người
sử dụng. Sự phát triển của lĩnh vực này trong những năm 1970 đến những năm 1980
dựa trên nền tảng của những năm trước đó, nhiều mô hình thực hiện truy tìm tài liệu
khác nhau được phát triển và tiến bộ theo mọi khía cạnh của quá trình truy tìm. Những
mô hình kỹ thuật mới được chứng minh qua thực nghiệm, có hiệu quả trong những tập
hợp văn bản nhỏ, có thể dùng cho các nhà nghiên cứu ở thời gian đó. Tuy nhiên, vì
không có hiệu quả đối với những tập hợp văn bản lớn, câu hỏi có hay không những mô
hình và những kỹ thuật có thể đáp ứng được với thể lớn hơn vẫn chưa được trả lời. Sự
thay đổi lớn vào năm 1992, với sự khởi đầu bằng cuộc thảo luận về truy tìm văn bản,
sau đó một loạt thảo luận kiểm định đứng đầu bởi nhiều hãng khác nhau của Mỹ dưới
sự bảo hộ của Viện Tiêu chuẩn và Công nghệ quốc gia (NIST), nhằm vào việc khuyến
khích nghiên cứu về hệ thống IR với những tập hợp văn bản lớn. Những thuật toán IR
đã phát triển trong những năm từ năm 1996 đến năm 1998, là những kỹ thuật đầu tiên
được dùng cho việc tìm kiếm trên mạng toàn cầu.
Ngày nay, sự phát triển nhanh chóng của lĩnh vực thông tin và Internet đã tạo ra
một khối lượng thông tin vô cùng lớn với sự phong phú, đa dạng và phức tạp của loại
hình thông tin như: văn bản, hình ảnh, video, siêu văn bản, đa phương tiện… Tương
ứng với khối lượng dữ liệu khổng lồ đó, người ta quan tâm nhiều đến cơ sở dữ liệu đa
phương tiện (Mutimedia Database) trong khoa học công nghệ và trong thực tiễn. Với
hệ thống cơ sở dữ liệu đa phương tiện, bao gồm dữ liệu dạng hình ảnh, video, audio và
văn bản (text) đang có xu thế thâm nhập vào rất nhiều lĩnh vực và đang dần trở thành
hệ cơ sở dữ liệu được quan tâm từ người sử dụng và các chuyên gia trong vấn đề lưu
trữ, xử lý và ứng dụng.
Cho đến nay, vấn đề tìm kiếm thông tin đa phương tiện vẫn được các chuyên
gia nghiên cứu, trong việc truy tìm thông tin phù hợp với yêu cầu của một truy vấn đưa
ra từ người sử dụng. Người sử dụng có xu hướng tìm kiếm chủ yếu trong hệ cơ sở dữ
liệu đa phương tiện, ví dụ như tìm kiếm một loạt hình ảnh cổ vật liên quan đến nền văn
hoá cổ Việt Nam, tìm kiếm dữ liệu âm thanh có bản text kèm theo, tìm kiếm video bài
giảng cho học sinh ôn thi đại học... Để thực hiện được việc tìm kiếm đó trong cơ sở dữ
liệu đa phương tiện thì những người làm khoa học đã nghiên cứu ra các công cụ,
9
phương pháp, kỹ thuật tìm kiếm sao cho thuận tiện, chính xác và nhanh chóng đem lại
được thông tin phù hợp với yêu cầu của người sử dụng.
Văn bản là một trong số các dạng của dữ liệu đa phương tiện, nó được quan tâm
từ hàng nghìn năm trước trong việc tổ chức sắp xếp và lưu trữ, điển hình như bảng nội
dung của một cuốn sách. Ngày nay, sự lớn mạnh của thông tin với phần lớn là dạng
văn bản, hơn nữa nó xuất phát từ nhu cầu thực tế sử dụng của con người. Tài liệu văn
bản chiếm đa số trong mọi cơ quan tổ chức, đặc biệt là trong thư viện và còn được sử
dụng để mô tả các dạng khác của dữ liệu đa phương tiện như video, audio, hình ảnh.
Số lượng tài liệu văn bản ngày càng lớn và có vai trò vô cùng quan trọng, vì thế việc
việc lưu trữ, xử lý và truy tìm thủ công trước đây không thể hoặc khó có thể thực hiện
được. Cùng với sự ra đời và phát triển của máy tính, các công cụ xử lý cũng ngày càng
hoàn thiện dựa trên những kỹ thuật hiện đại phục vụ cho nhu cầu đó.
Các mô hình truy tìm hay được sử dụng trong phạm vi này, đó là: Đối sánh
chính xác, không gian vectơ, xác suất và trên cơ sở cụm. Song, nhược điểm cơ bản của
các mô hình truy tìm thông tin hiện nay là những từ mà người tìm kiếm sử dụng,
thường không giống với những từ đã được đánh chỉ mục trong thông tin tìm kiếm. Vấn
đề này liên quan nhiều đến hai khía cạnh thực tế, đó là tính đồng nghĩa (synonymy)-
cùng một thông tin nhưng được miêu tả bằng các từ khác nhau, phụ thuộc vào ngữ
cảnh hay mức độ cần thiết, ví dụ như: nhìn, xem, trông, thấy có cùng ý nghĩa; và tính
đa nghĩa (polysemy) – cùng một từ có nhiều ý nghĩa khác nhau trong ngữ cành khác
nhau, ví dụ như: đi (có thể là chỉ chuyển động hay chỉ sự mất mát). Kết quả truy tìm có
thể gồm những tài liệu không liên quan, đơn giản vì những thuật ngữ xuất hiện ngẫu
nhiên trong nó giống với thuật ngữ trong truy vấn và mặt khác, những tài liệu liên
quan có thể bị bỏ qua bởi không chứa các thuật ngữ xuất hiện trong truy vấn (do tính
đồng nghĩa). Một ý tưởng thú vị 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 so với truy tìm trực tiếp trên các thuật ngữ. Mô hình LSI (Latent
Semantic Indexing) ra đời, là một giải pháp hữu hiệu cho vấn đề truy tìm thông tin dựa
trên cơ sở nội dung tài liệu văn bản, tìm kiếm trên cơ sở những khái niệm (không phải
trên các thuật ngữ đơn).
Trước khi truy tìm, các tài liệu được coi như danh sách các từ và chúng phải
được đánh chỉ mục. Có một thực tế là không phải tất cả các từ đều có ý nghĩa, vì vậy
việc loại đi danh sách các từ không có nghĩa vô cùng quan trọng và các từ không có ý
nghĩa sẽ không được đánh chỉ mục. Từ thông tin tóm lược của người sử dụng biểu thị
qua truy vấn, thuật toán truy tìm phải đảm bảo rằng, chiến lược xếp hạng tập các tài
liệu trong câu trả lời luôn ưu tiên cho những thông tin có ích và phù hợp với truy vấn
người sử dụng đưa ra. Hơn thế nữa, một kỹ thuật được đánh giá là tốt phải dựa trên
việc xếp hạng các tài liệu này, tức là những tài liệu phù hợp và được coi là “gần” với
10
câu truy vấn nhất sẽ được xếp lên trên các tài liệu ít phù hợp hơn trong danh sách tài
liệu trả lời. Đánh giá chất lượng IR còn phụ thuộc vào thước đo hiệu năng thực hiện
của kỹ thuật đó dựa vào các tham số chủ yếu là độ chính xác (precison) và số tài liệu
được gọi lại (recall).
Trên cơ sở đó, cấu trúc luận văn gồm phần mở đầu, kết luận, tài liệu tham khảo
và phần nội dung gồm ba chương và được trình bày theo thứ tự sau:
Chương 1. Giới thiệu tổng quan về cơ sở dữ liệu đa phương tiện, xếp hạng tài
liệu và các yếu tố cơ bản phục vụ cho việc tìm kiếm thông tin. Khái quát về một hệ
thống truy tìm thông tin (IR) tiêu biểu và cụ thể là truy tìm tài liệu văn bản.
Chương 2. Đề cập đến vấn đề chỉ mục tài liệu và thước đo hiệu năng. Nghiên
cứu một số mô hình tìm kiếm như: Boolean, không gian vectơ, phân cụm, dựa trên xác
suất, phản hồi phù hợp và LSI.
Chương 3. Cài đặt thực nghiệm mô hình LSI.
Nội dung luận văn đi từ tổng quan về cơ sở dữ liệu đa phương tiện, hệ thống
tìm kiếm đa phương tiện đến kỹ thuật chỉ mục, xử lý tài liệu, trích lọc thông tin đến chi
tiết vấn đề tìm kiếm trên tài liệu văn bản. Đặc biệt, nghiên cứu các mô hình tìm kiếm
và đi sâu nghiên cứu mô hình LSI- tìm kiếm văn bản trên cơ sở nội dung.
11
CHƯƠNG 1 - TỔNG QUAN
1.1 Khái quát về cơ sở dữ liệu (CSDL) đa phương tiện [1] [10] [12]
1.1.1 Giới thiệu
Trên thế giới tồn tại một lượng rất lớn dữ liệu số, các dữ liệu từ tivi, internet,
qua phương tiện truyền thông hay có được từ nhiều phương tiện khác nhau như máy
quay (video) kỹ thuật số... Các dòng dữ liệu số càng ngày càng tăng, các loại dữ liệu
đa phương tiện kết hợp của dữ liệu hình ảnh, âm thanh, văn bản…
Hiện nay, chúng ta đều biết internet đang được phát triển như thế nào, rõ ràng
trong quá trình tương tác và trao đổi thông tin, người sử dụng có xu hướng chủ yếu xử
lý trên kiểu dữ liệu đa phương tiện và chúng ta thấy được sự phát triển của kiểu dữ liệu
này trong cuộc sống hiện đại. Tầm quan trọng của việc sử dụng thông tin sẽ dần dần
thay đổi từ thông tin dạng số và rõ tới thông tin ở dạng đa phương tiện: dữ liệu hình
ảnh, âm thanh và tài liệu văn bản. Vì thế, đa phương tiện là thông điệp cho xã hội
thông tin ngày nay.
Sự tương tác của người sử dụng tự nhiên hơn với thông tin và các thiết bị
truyền thông, trong phạm vi rộng sẽ tạo ra một xã hội có giá trị về mọi mặt. Vì thế, có
thể dự đoán được đa phương tiện sẽ thâm nhập vào tất cả các hệ thống thông tin, từ
công việc hàng ngày tới thương mại, công việc văn phòng chuyên nghiệp, giao tiếp với
khách hàng, giáo dục, khoa học, trong nghệ thuật và được truyền đi rộng rãi qua
internet.
Đa phương tiện có thể trở thành dạng giao tiếp tự nhiên, nhưng nó không hoàn
toàn tự do. Ngữ nghĩa của một thông điệp trong thông tin số và xác thực hơn là dòng
bit của hình ảnh và âm thanh. Trong đó, tín hiệu hình ảnh biểu thị cái gì, ý nghĩa của
văn bản và nói gì về âm thanh là không dễ dàng lập luận với một máy tính. Những
điều thuộc về ngữ nghĩa đó cần được xử lý từ dữ liệu thô bằng việc tổ chức, chuyển
đổi, phân tích và phân lớp.
Khai thác đa phương tiện (multimedia) đầy đủ yêu cầu sử dụng video, tranh
ảnh, âm thanh và ngôn ngữ. Nó bao gồm sự tương tác của máy với dạng đa phương
thức. Thêm vào đó, kiến thức và sự hiểu biết về các dạng đa phương tiện sẽ có được
hiểu biết về bản chất của các dòng thông tin đa phương tiện. Các hệ thống thông tin đa
phương tiện sẽ lưu và cung cấp truy cập đến các dòng dữ liệu, hệ thống ứng dụng
thông tin trên tất cả các dạng. Trong phạm vi vấn đề này, đa phương tiện có thể được
mô tả như mọi ứng dụng của dữ liệu thông tin trên một máy tính qua các dạng như
hình ảnh, ngôn ngữ tự nhiên và âm thanh.
Một số mô hình ứng dụng đa phương tiện như các thiết bị điện tử, hệ thống lưu
trữ các kho chứa đa phương tiện lớn, sử dụng các tài liệu điện tử của đa phương tiện, y
12
tế điện tử và chính phủ điện tử. Ứng dụng đa phương tiện trở thành một phần không
thể thiếu của các công việc trong nhiều cụm kinh tế. Ví dụ: phân tích hệ thống thông
tin đa phương tiện sử dụng để giám sát, thu thập chứng cớ tòa án và an ninh chung…
Việc phát sinh khối kiến thức đa phương tiện và kiến thức kỹ thuật được dùng để lưu
trữ việc tạo hình ảnh, phim và âm thanh có thể được sử dụng trong di sản văn hóa và
nền công nghiệp giải trí...
Có rất nhiều định nghĩa khác nhau về CSDL đa phương tiện: Theo nghiên cứu
EURESCOM thì CSDL đa phương tiện là một CSDL có hiệu năng cao, sức chứa lớn
với khả năng hỗ trợ các kiểu dữ liệu đa phương tiện cũng như các kiểu dữ liệu chữ số
cơ bản khác và nó có thể quản lý một khối lượng rất lớn thông tin đa phương tiện.
Dữ liệu âm thanh (audio data): Tín hiệu âm thanh bao gồm tiếng nói, âm nhạc,
tiếng động và mọi sự kết hợp các âm thanh khác nhau. Việc lưu lại một bài diễn
thuyết, một cuộc đàm thoại, các đoạn audio theo một chủ đề nào đó có ý nghĩa rất lớn
trong thực tế. Ví dụ, qua đài phát thanh chúng ta có thể thu thập được nhiều thông tin
với các chủ đề khác nhau, có thể tìm kiếm các bài hát trên internet, thu thập các đoạn
audio bài giảng trong đào tạo từ xa, học ngoại ngữ qua các đoạn audio...
Dữ liệu hình ảnh (image data): Dữ liệu ảnh có thể được dùng để lưu trữ dấu
vân tay, nhận dạng khuôn mặt trong điều tra tội phạm; ảnh thẻ trong quản lý nhân sự;
trong những yêu cầu lưu lại hình ảnh như dữ liệu ảnh cổ vật, hiện tượng thiên nhiên,
trái đất… Hơn nữa, trong y học cần có một cơ sở dữ liệu ảnh để có thể truy vấn các
triệu trứng để tìm ra những căn bệnh tương tự không chỉ bằng văn bản mà bằng cả
hình ảnh, ảnh chụp X quang, ảnh chụp cắt lớp... Trong thời gian gần đây, việc sử dụng
CSDL ảnh đã mang lại hiệu quả to lớn trong nhiều lĩnh vực khác nhau của đời sống,
kinh tế và xã hội.
Dữ liệu video (video data): Video giống như một tập các hình ảnh ở các thời
điểm được sắp xếp, biểu diễn theo một chuỗi thời gian nhất định. Trên thực tế chính là
chuyển động của các điểm ảnh từ trạng thái này sang trạng thái khác, hay là sự chuyển
động của mỗi đối tượng riêng lẻ được phân tách từ dữ liệu video. Dữ liệu video được
ứng dụng nhiều trong công nghệ giải trí (phim ảnh, clip âm nhạc..), trong đào tạo từ xa
(qua những video bài giảng)... Nhiều phòng chức năng có nhiệm vụ lưu trữ và thu thập
các video (tư liệu lịch sử, tư liệu khai quật khảo cổ học của địa phương hay quốc gia...)
để nhằm phát triển khả năng trở thành bộ nhớ tiểu sử tự động (autobiographic
memory).
Dữ liệu văn bản (text data): Sự biểu diễn cơ bản của văn bản là cách tiếp cận
với “túi các từ” (bag – of – words). Theo thống kê, đến năm 2005 toàn bộ văn bản trên
mạng có thể đã lên tới hàng chục TB. Các dữ liệu văn bản tiêu biểu như: Các trang
web, tiêu đề bài viết, các bản báo cáo, bài báo được công bố hàn lâm, các ứng dụng hỗ
13
trợ nghiên cứu, các trang tài liệu, bách khoa toàn thư, thư mục, chép sử, thư điện tử,
các bản sao xét xử của toà án, kho thư viện... Điều quan trọng là khối lượng dữ liệu
văn bản ngày càng lớn và được sử dụng lưu trữ tài liệu trong mọi cơ quan tổ chức. Vì
thế, quan tâm đến xử lý văn bản là rất cần thiết. Thực tế, tập văn bản sách trong một
thư viện của một trường đại học nhỏ cũng có thể chứa đến 100GB lưu trữ, hay một nhà
nghiên cứu trong 10 năm có đến 10MB tập văn bản, và cũng nhà nghiên cứu đó trong
10 năm lưu trữ tài liệu thư điện tử có thể chiếm đến 100MB. Ngoài ra còn dùng các
miêu tả bằng văn bản cho hình ảnh hay video, người ta có thể chèn các thuộc tính, các
đoạn thuyết minh, chú thích cho các đối tượng đó.
1.1.2 Mục tiêu chính
Theo cách nhìn trên đây ta nhận thấy CSDL đa phương tiện bao gồm năm mục
tiêu chính như sau:
- Hỗ trợ các kiểu dữ liệu (Type=Structure+Operations) đa phương tiện: các
phương tiện (media) khác nhau và các thao tác thông thường cũng như các thao tác
đặc biệt mà kiểu dữ liệu thông thường không có như tiến, lùi, dừng...
- Có khả năng quản lý số lượng lớn các đối tượng đa phương tiện: đề cập đến
không gian lưu trữ của CSDL.
- Hỗ trợ hiệu năng cao, sức chứa cao và quản trị lưu trữ hiệu quả
- Có các khả năng của hệ CSDL truyền thống
- Có khả năng truy tìm thông tin đa phương tiện.
1.1.3 Mô hình dữ liệu đa phương tiện
Mô hình dữ liệu MIRS (Multimedia Information Retrieval System) hình thành
trên nền tảng nguyên tắc hướng đối tượng và phân cấp đa tầng.
Tầng đối tượng
Đối tượng bao gồm một hay nhiều mục media với các quan hệ không gian và
thời gian xác định, như với một đối tượng đa phương tiện là một trang bao gồm một
vài hình ảnh và âm thanh kèm theo.
Nhiệm vụ mấu chốt là làm thế nào để chỉ ra các quan hệ không gian và thời
gian. Quan hệ không gian được đặc tả bởi kích thước và vị trí cửa sổ hiển thị của mỗi
mục. Phương pháp chung đặc tả thời gian là đặc tả trên cơ sở trục thời gian, trong đó
thời gian bắt đầu và độ dài mỗi mục được xác định trên cơ sở đồng hồ chung. Phương
pháp khác là mô hình điều khiển theo sự kiện.
14
Hinh 1.1 Mô hình dữ liệu đa phương tiện
Tầng loại media
Tầng này bao gồm các loại media như văn bản, hình ảnh, audio và video. Các
loại này được suy diễn từ lớp media trừu tượng chung.
Tại mức này, các đặc trưng và thuộc tính được đặc tả. Ví dụ loại media ảnh:
kích thước, biểu đồ màu, các đối tượng chính chứa trong nó... được đặc tả. Các đặc
trưng này được sử dụng trực tiếp vào tìm kiếm và tính toán khoảng cách.
Tầng khuôn mẫu media
Tầng này đặc tả khuôn mẫu, trong đó dữ liệu được lưu trữ. Thông thường,
media có nhiều khuôn mẫu, ví dụ ảnh có thể là nén hay ảnh thô. Hơn nữa có rất nhiều
kỹ thuật và chuẩn nén khác nhau. Thông tin chứa trong tầng này được sử dụng để giải
mã, phân tích và trình diễn.
Các nhiệm vụ khác
Chú ý rằng, các ứng dụng khác nhau có thể cần các mô hình dữ liệu khác nhau.
Tuy nhiên nhiều ứng dụng cùng chia sẻ mô hình cơ sở chung, nếu được thiết kế tốt thì
có thể bổ sung các đặc trưng và đối tượng mới để đáp ứng yêu cầu ứng dụng cụ thể.
Đến nay, chưa có chuẩn chung cho các tầng mô hình dữ liệu mô tả trên, các ứng
dụng MIRS hiện nay chủ yếu là đặc thù, chỉ tập trung vào giới hạn số đặc trưng và loại
media. Rất nhiều công việc phải làm khi mô hình hóa dữ liệu đa phương tiện để phát
triển MIRS và MMDBMS (MultiMedia DataBase Manager System) lớn nhất quán.
1.2 Trích chọn đặc trưng, chỉ mục và đo tính tương tự [1]
Các đặc trưng và thuộc tính của dữ liệu (items) trong MIRS được trích chọn,
tham số hóa và lưu trữ chung với chính các dữ liệu. Các đặc trưng và thuộc tính của
Hình ảnh
Không gian Thời gian Tổng hợp
Văn bản Âm thanh
Thô Nén
Đa mức
xám
Màu JPEG JPIG DPCM
Video
Tầng đối
tượng
Tầng kiểu
media
Tầng
khuôn
mẫu
media
15
truy vấn cũng được trích chọn theo cùng cách thức nếu nó không được xác định rõ
ràng trước. Hệ thống tìm kiếm các items trong CSDL với các thuộc tính và đặc trưng
tương tự trên cơ sở thước đo tính tương tự nhất định. Để tìm kiếm hiệu quả, các đặc
trưng và thuộc tính phải được tổ chức thành các cấu trúc có chỉ mục.
1.2.1 Trích chọn đặc trưng
Các mục thông tin đa phương tiện trong CSDL được tiền xử lý để trích chọn
đặc trưng và thuộc tính.
Trong tiến trình tìm kiếm, các đặc trưng và thuộc tính này được so sánh thay
cho chính các mục thông tin. Do vậy, chất lượng của trích chọn đặc trưng xác định
hiệu quả tìm kiếm. Nếu đặc trưng không được tách ra từ item thì không thể tìm thấy
chúng từ CSDL theo đặc trưng đó. Đó là một trong sự khác biệt lớn nhất giữa MIRS
và DBMS. Trong DBMS thì mọi thuộc tính là có sẵn và đầy đủ, trong khi đó các đặc
trưng và thuộc tính phải được trích chọn theo loại truy vấn và thường là không đầy đủ
trong MIRS.
Trích chọn đặc trưng phải thỏa mãn các yêu cầu sau:
Đặc trưng và thuộc tính trích chọn phải đầy đủ nhất có thể để biểu diễn nội
dung của các mục thông tin.
Các đặc trưng phải được trình diễn và lưu trữ một cách chặt chẽ, mạch lạc. Mục
đích của việc trích chọn đặc trưng không phải là các đặc trưng phức tạp và đặc
trưng lớn, quan trọng là nó phải có khả năng tìm kiếm và so sánh nhanh các
mục thông tin với nhau.
Tính toán khoảng cách giữa các đặc trưng phải hiệu quả, nếu không thời gian
đáp ứng của hệ thống rất lớn.
Tổng thể có 4 mức đặc trưng và thuộc tính như sau:
Metadata: bao gồm các thuộc tính của các đối tượng đa phương tiện như tên tác
giả, ngày tạo lập, tiêu đề đối tượng. Không mô tả hay diễn giải nội dung của đối tượng.
Các thuộc tính này được quản lý bằng kỹ thuật DBMS. (Trong một số tài liệu cho rằng
metadata bao gồm toàn bộ các mức đặc trưng và thuộc tính đang mô tả tại đây).
Mô tả bằng văn bản: Mô tả nội dung đối tượng bằng văn bản. Mô tả dưới hình
thức nhiều từ khóa hay văn bản thông thường. Chỉ mục và tìm kiếm trên cơ sở mô tả
bằng văn bản được quản lý bằng kỹ thuật IR. Mặc dù mô tả bằng văn bản có hạn chế là
còn tính chủ quan và chưa đầy đủ, nhưng đây vẫn là phương pháp hay được sử dụng
và hiệu quả. Nên sử dụng mô tả bằng văn bản kết hợp với các đặc trưng khác trong
ứng dụng đa phương tiện. Hiện tại, mô tả văn bản là tiến trình bằng tay, khá vất vả.
Cần phát triển các công cụ bán tự động để hỗ trợ tiến trình này. Tri thức lĩnh vực và từ
điển liệt kê luôn có ích trong việc đem lại hiệu quả truy vấn.
Đặc trưng nội dung mức thấp: Thu thập các mẫu và thống kê đối tượng đa
16
phương tiện và các quan hệ không gian, thời gian giữa các phần đối tượng. Mỗi media
khác nhau có các đặc trưng nội dung mức thấp khác nhau.
- Với âm thanh, đặc trưng mức thấp bao gồm âm lượng trung bình, phân bổ tần số
và tỷ lệ câm.
- Các đặc trưng mức thấp của ảnh bao gồm phân bổ màu, texture, hình dạng đối
tượng và cấu trúc không gian.
- Đặc trưng mức thấp của video bao gồm cấu trúc thời gian.
Lợi thế chính của việc sử dụng đặc trưng mức thấp là có thể tự động trích chọn
chúng.
Đặc trưng nội dung mức cao: Cố gắng nhận biết và hiểu đối tượng. Ngoài nhận
dạng văn bản và tiếng nói, việc nhận dạng và hiểu đoạn âm thanh hay các đối tượng
nhìn là rất khó khăn. Trong ứng dụng với hữu hạn các đối tượng, việc mô tả và nhận
biết các đặc trưng chung là rất hiệu quả. Ví dụ, dự báo tới 95% các video có mục tiêu
chính là quay người hay nhóm người. Nó hữu ích cho các hệ thống để nhận biết và
diễn giải liên quan đến con người. Hiện tại, tiến trình nhận dạng và diễn giải được thực
hiện bán tự động.
Việc truy vấn trên cơ sở hai loại đặc trưng nội dung mức thấp và mức cao gọi là
truy vấn trên cơ sở nội dung. Một hệ thống cần sử dụng toàn bộ bốn mức đặc trưng sao
cho hỗ trợ được các câu truy vấn mềm dẻo của người sử dụng. Các kỹ thuật này hỗ trợ
nhau để hình thành mô tả đầy đủ về đối tượng. Ví dụ, mô tả văn bản tốt cho việc thu
thập các khái niệm trừu tượng như cảm giác (vui, buồn...) nhưng không có khả năng
mô tả mẫu dữ liệu đầy đủ về các hình dạng không đều hay texture. Mặt khác, các đặc
trưng nội dung mức thấp có thể thu thập các mẫu dữ liệu này nhưng không mô tả được
các khái niệm trừu tượng.
Khi đối tượng đa phương tiện có nhiều kiểu media, các quan hệ và tương tác
giữa các media phải được sử dụng để trích chọn đặc trưng, diễn giải và truy tìm. Có
một vài kiểu media dễ hiểu và dễ diễn giải hơn vài kiểu khác. Việc áp dụng sự hiểu
biết có được về một hay vài kiểu nào đó, giúp ta hiểu và trích chọn đặc trưng cho các
kiểu khác. Ví dụ, nếu đối tượng đa phương tiện bao gồm rãnh hình (video) và rãnh
tiếng, ta có thể áp dụng nhận dạng tiếng nói để lấy ra tri thức về đối tượng và sử dụng
tri thức này để phân đoạn, trích chọn các đặc trưng và đối tượng trên rãnh hình
(video).
1.2.2 Chỉ số hóa cấu trúc
Sau khi trích chọn đặc trưng, chúng ta phải chỉ số hóa cấu trúc để tổ chức các
đặc trưng sao cho truy vấn được hiệu quả. Như đã biết, phải cần rất nhiều đặc trưng và
nhiều tham số để trình diễn. Ví dụ, phân bổ màu thường được biểu diễn bằng biểu đồ
với nhiều bins màu khác nhau.
17
Chỉ số hóa trong MIRS phải là phân cấp và nhiều mức:
Mức cao nhất là phân lớp ứng dụng.
Mức chỉ số hóa thứ hai hình thành trên các mức đặc trưng khác nhau. Các đặc
trưng khác nhau cần chỉ số hóa khác nhau.
Mức thứ ba hình thành trên quan hệ không gian và thời gian giữa các đối tượng.
1.2.3 Đo tính tương tự
Truy vấn đa phương tiện trên cơ sở tính tương tự thay cho đối sánh chính xác
giữa các item truy vấn và các item trong CSDL. Tính tương tự được tính toán trên cơ
sở các đặc trưng, thuộc tính trích chọn và dưới dạng một hay nhiều giá trị. Tuy nhiên,
tương quan của kết quả truy vấn do con người quyết định. Các kiểu đặc trưng được sử
dụng để mô tả các đối tượng đóng vai trò quan trọng để phù hợp với yêu cầu này.
Thước đo tính tương tự rất phức tạp vì quyết định của người sử dụng là chủ quan và
phụ thuộc ngữ cảnh.
1.3 Hệ thống truy tìm thông tin (IR-Information retrieval) [1] [3] [4] [9] [13]
Với sự phát triển mạnh mẽ của CSDL đa phương tiện và mạng máy tính, hệ
thống IR (Information retrieval) ngày càng được quan tâm .
1.3.1 Khái quát
Từ những năm 1940, vấn đề lưu trữ và truy tìm thông tin đã thu hút sự chú ý
của các nhà nghiên cứu. Hệ thống tìm kiếm đang trở nên cần thiết, vấn đề đó là: chúng
ta có lượng thông tin rất lớn, yêu cầu truy tìm thông tin một cách chính xác và nhanh
chóng. Yếu tố được quan tâm là thông tin liên quan có thể bị bỏ qua, quá trình và kết
quả tìm kiếm đó có thể bị lặp lại nhiều lần dẫn đến hiệu quả tìm kiếm thấp. Với sự
xuất hiện của máy tính điện tử, rất nhiều ý tưởng về việc sử dụng chúng để cung cấp
những hệ thống truy tìm thông tin nhanh chóng và thông minh. Ví dụ: trong thư viện
luôn có bài toán về tìm kiếm và lưu trữ thông tin, hay một số nhiệm vụ thông thường
như việc lập danh mục, việc quản lý chung và đã có cách thực hiện đem lại kết quả tốt
bằng việc sử dụng những chiếc máy tính. Tuy nhiên, vấn đề về hiệu quả truy tìm phần
lớn vẫn chưa được giải quyết.
Nói chung, việc lưu trữ và truy tìm thông tin là đơn giản theo một khía cạnh nào
đó. Ví dụ: Có một kho các tài liệu và một người sử dụng, một câu hỏi được đưa ra mà
câu trả lời là một tập các tài liệu thoả mãn thông tin yêu cầu được hiển thị. Người sử
dụng có thể thu được tập kết quả bằng việc đọc tất cả các tài liệu trong kho, giữ lại
những tài liệu có liên quan và vứt bỏ toàn bộ những cái khác. Trong một ý nghĩa nào
đó, việc này tạo nên truy tìm “hoàn hảo”. Song, giải pháp này rõ ràng không thể thực
hiện được. Người sử dụng hoặc không có thời gian hoặc không muốn tiêu phí thời gian
đọc toàn bộ tập hợp tài liệu, trừ khi anh ta không theo quy luật tự nhiên.
18
Khi những chiếc máy tính tốc độ cao sẵn sàng cho công việc không thuộc số
hóa (non-numerical), nhiều người cho rằng một máy tính có thể đọc toàn bộ tập hợp
tài liệu để trích lọc những tài liệu có liên quan. Hiển nhiên rằng, vấn đề về sử dụng
ngôn ngữ tự nhiên trong một tài liệu không chỉ là đầu vào (input) và kho lưu trữ mà
còn vấn đề về tri thức, thuộc đặc trưng nội dung tài liệu chưa được giải quyết. Có thể
hy vọng sự phát triển trong tương lai có thể tạo đầu vào (input) và kho ngôn ngữ tự
nhiên khả thi hơn. Các phần mềm đang cố gắng tự động hóa trong việc “sao” lại quá
trình “đọc” của con người, quả thực đó là một vấn đề hết sức khó khăn. Khó khăn hơn,
việc “đọc” bao gồm việc rút trích thông tin, cú pháp và ngữ nghĩa từ văn bản và sử
dụng nó để quyết định xem là mỗi tài liệu có liên quan hay không đến một yêu cầu cụ
thể. Nghĩa là, khó khăn không chỉ là làm thế nào để rút trích thông tin mà còn làm sao
để sử dụng nó quyết định sự phù hợp.
“Sự phù hợp”, đó là khái niệm trung tâm của truy tìm thông tin. Mục đích của
một chiến lược truy tìm tự động là truy tìm tất cả các tài liệu phù hợp ở cùng thời điểm
truy tìm, có thể bao gồm một vài tài liệu không thỏa mãn. Tìm ra các đặc trưng của tài
liệu để khi tài liệu phù hợp với truy vấn, nó cho phép tài liệu được truy tìm để trả lời
truy vấn. Khi chỉ mục được làm tự động, nó được giả thiết bằng việc đưa tài liệu văn
bản và câu truy vấn vào cùng bộ phân tích tự động, output sẽ là biểu diễn nội dung của
chúng và nếu tài liệu là phù hợp với truy vấn thì một thủ tục tính toán sẽ cho thấy điều
này.
Truy tìm dựa trên cơ sở nội dung (Content- based retrieval): Người sử dụng có
thể chỉ rõ các điều kiện lựa chọn dựa trên những nội dung của các đối tượng đa
phương tiện. Ví dụ, người sử dụng tìm kiếm ảnh, sử dụng truy vấn như: “Tìm tất cả
các ảnh giống với ảnh này” và “Tìm tất cả các ảnh chứa ít nhất 3 máy bay”. Các hình
ảnh được thêm vào cơ sở dữ liệu, DBMS (DataBase Manager System) phải phân tích
chúng và tự động trích chọn các đặc điểm (extract features) để đưa ra câu trả lời giống
với các truy vấn. Thông tin này có thể được sử dụng để tìm kiếm các hình ảnh thoả
mãn với một truy vấn đưa ra. Một cách tiếp cận khác, người sử dụng muốn tìm các tài
liệu mà mình quan tâm có thể sử dụng các kỹ thuật truy tìm thông tin và tìm kiếm từ
khoá. Nó vẫn không thực sự rõ ràng là làm thế nào để truy tìm các miền cụ thể đó và
các kỹ thuật tìm kiếm có thể được kết hợp hiệu quả với các truy vấn DBMS truyền
thống.
1.3.2 Vấn đề truy tìm tài liệu văn bản (Text retrieval)
Kỹ thuật truy vấn tài liệu văn bản được gọi chung là kỹ thuật truy tìm thông tin
(IR). Các hệ thống IR cổ điển chủ yếu là làm việc trên văn bản (text) và kỹ thuật IR
trong hệ thống đa phương tiện rất quan trọng vì hai lý do chính sau đây:
19
- Đang tồn tại số lượng lớn tài liệu văn bản trong các thư viện. Văn bản là tài
nguyên rất quan trọng đối với các cơ quan, tổ chức. Điều đó cho thấy, cần có một hệ
thống IR đủ tốt để có thể truy xuất có hiệu quả các thông tin lưu trữ trong các tài liệu.
- Văn bản còn được sử dụng để mô tả các phương tiện khác như video, audio,
hình ảnh.
Mục đích của người sử dụng hệ truy tìm:
- Độ chính xác: Truy tìm đúng thông tin mà người sử dụng mong muốn, đúng
với truy vấn. Có thể có một vài tài liệu trong câu trả lời là không chính xác song tất cả
các câu trả lời phù hợp đều được truy vấn.
- Tốc độ truy tìm: Việc truy tìm phải được thực hiện nhanh chóng
Nhiệm vụ chính của thiết kế hệ thống IR là để nhằm giải quyết hai vấn đề:
- Biểu diễn và truy vấn tài liệu như thế nào.
- So sánh tính tương đồng giữa các tài liệu và biểu diễn truy vấn ra sao.
Các mô hình truy vấn sẽ xác định hai khía cạnh này. Để nâng cao hiệu năng
truy vấn, việc xử lý ngôn ngữ tự nhiên và các kỹ thuật trí tuệ nhân tạo được áp dụng.
Vì tính nhập nhằng và tồn tại nhiều biến thể của ngôn ngữ tự nhiên, hầu như không thể
truy vấn mọi tài liệu liên quan hay loại đi mọi tài liệu không liên quan. Do vậy, thước
đo hiệu năng IR là rất quan trọng.
Một hệ thống truy tìm thông tin tiêu biểu
Một hệ thống IR tiêu biểu được minh hoạ bằng phương pháp hộp đen. Gồm ba
thành phần: input, bộ xử lý và output.
Bắt đầu với đầu vào (input), vấn đề chính ở đây là có được biểu diễn của tài liệu
và truy vấn thích hợp qua máy tính. Có thể nói, các hệ thống truy tìm hầu hết dựa trên
máy tính với việc chỉ lưu trữ biểu diễn đặc trưng của tài liệu (hoặc truy vấn), có nghĩa
là một tài liệu văn bản không được sử dụng nữa khi nó đã được xử lý để đưa ra các đặc
trưng. Ví dụ, một biểu diễn đặc trưng tài liệu có thể là một danh sách các từ được xem
là quan trọng được trích ra.
Hình 1.2 Hệ thống IR tiêu biểu
Khi một hệ thống truy tìm trực tuyến (on-line), người sử dụng có khả năng thay
đổi yêu cầu trong một phiên tìm kiếm ở trạng thái truy tìm mẫu, do đó hy vọng cải
20
thiện được quá trình truy tìm xảy ra sau. Một thủ tục như vậy thông thường cho phép
phản hồi (Feedback).
Hơn nữa, bộ xử lý, một phần của hệ thống truy tìm có liên quan tới quá trình
truy tìm. Bộ xử lý có thể bao gồm cấu trúc thông tin theo cách thích hợp nào đó, giống
như phân loại. Trên thực tế, nó cũng bao gồm cả việc biểu diễn chức năng truy tìm, đó
là thực hiện chiến lược tìm kiếm câu trả lời cho một truy vấn. Trong biểu đồ, các tài
liệu được đặt vào một ô riêng biệt để nhấn mạnh thực tế là không có đầu vào (input) rõ
ràng nhưng có thể sử dụng trong suốt quá trình truy tìm.
Cuối cùng, chúng ta xét đến đầu ra (output) thường là một tập trích dẫn hoặc
các tài liệu. Trong một hệ thống hoạt động, đây là phần còn lại. Tuy nhiên, một hệ
thống thực nghiệm có thể cho phép thực hiện việc đánh giá.
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System)
Phân biệt được sự khác nhau giữa hai hệ thống truy tìm văn bản (IR) và DBMS
giúp ta hiểu rõ các kỹ thuật truy tìm văn bản.
- DBMS: Chứa các bản ghi có cấu trúc đồng nhất. Mỗi bản ghi được đặc trưng
bởi tập các thuộc tính. Các giá trị thuộc tính được gán cho bản ghi để mô tả bản ghi
này một cách rõ ràng và đầy đủ.
Truy vấn ở đây dựa trên cơ sở đối sánh chính xác giữa câu truy vấn và các giá
trị thuộc tính trong bản ghi. Mỗi bản ghi truy vấn chứa các giá trị thuộc tính chính xác
được đặc tả trong câu truy vấn (có thể cả giá trị thuộc tính không được đề cập đến
trong câu truy vấn).
- Hệ thống IR: Các bản ghi không có cấu trúc. Chúng không chứa các thuộc tính
cố định, chỉ đơn thuần là tài liệu văn bản. Các tài liệu này có thể chỉ mục bằng các từ
khóa, bộ mô tả tài liệu, hay các thuật ngữ (term) chỉ mục. Mỗi thuật ngữ chỉ mục được
sử dụng để mô tả nội dung văn bản chỉ theo một khía cạnh nào đó, không đầy đủ và
không rõ ràng cho toàn bộ nội dung văn bản. Nhiều thuật ngữ chỉ mục được gắn theo
tài liệu hay văn bản cụ thể. Bởi vì các thao tác truy vấn văn bản phụ thuộc trực tiếp
vào nội dung đại diện, sử dụng để mô tả các bản ghi lưu trữ, do vậy cần phải có nhiều
cố gắng để tập trung vào phân tích nội dung của các tài liệu lưu trữ và vấn đề sinh từ
khóa, chỉ mục.
Ở đây, sẽ không thực tế nếu coi trọng truy vấn trên cơ sở đối sánh chính xác
giữa câu truy vấn và các thuật ngữ tài liệu để tìm ra tài liệu kết quả. Thay vì, truy vấn
các mục liên quan với đủ mức độ tương đồng giữa tập thuật ngữ gắn theo câu truy vấn
và tài liệu, được sinh ra bởi phương pháp xấp xỉ hay đối sánh từng phần. Hơn nữa
cùng thuật ngữ có thể có nhiều ý nghĩa khác nhau.
Tóm lại, các tài liệu kết quả truy vấn trong DBMS là hoàn toàn liên quan đến
câu truy vấn và hầu như có ích với người sử dụng. Nhưng trong hệ thống IR, các tài
21
liệu được xem là liên quan đến câu truy vấn nhưng có thể không liên quan và không có
ích với người sử dụng
Hình 1.3 Tiến trình truy vấn tài liệu
Bên phải hình 1.3 chỉ ra các tài liệu được xử lý off-line để có đại diện (mô tả).
Các đại diện này được lưu trữ cùng với các tài liệu.
Bên trái hình 1.3 chỉ ra quá trình truy vấn. Người sử dụng đưa ra câu truy vấn
và được xử lý on-line để có đại diện của câu truy vấn. Sau đó đối sánh đại diện truy
vấn với đại diện tài liệu, các tài liệu được xem như tương đồng sẽ được trình diễn cho
người sử dụng. Sau đó, họ đánh giá tài liệu cho lại và quyết định tài liệu nào thực sự
tương đồng và có ích. Một hệ thống IR tốt cho phép người sử dụng cung cấp phản hồi
về sự thích hợp của tập tài liệu kết quả cho hệ thống. Hệ thống sử dụng thông tin này
để điều chỉnh truy vấn, đại diện truy vấn, đại diện tài liệu. Phiên tìm kiếm khác tiếp
theo được thực hiện trên cơ sở câu truy vấn đại diện tài liệu đã được hiệu chỉnh. Nếu
cần, tiến trình phản hồi truy tìm được thực hiện lặp vài lần. Chú ý rằng, không phải tất
cả các hệ thống IR đều có tiến trình phản hồi thích hợp.
1.4 xếp hạng tài liệu (Ranking) [1] [8]
Một máy tìm kiếm có thể cho lại tới hàng vài nghìn tài liệu phù hợp, nhưng một
người sử dụng thông thường sẽ chỉ có thể xem xét được một số lượng nhỏ các tài liệu
tìm được đó. Vì thế, xếp hạng các tài liệu phù hợp theo mức độ tương thích với người
dùng là một vấn đề quan trọng, cũng là tiêu điểm trong việc đánh giá một phương
pháp truy tìm.
Chỉ qua một phần thông tin của người sử dụng được trích lọc biểu thị qua truy
vấn, hệ thống sẽ tìm kiếm và trả lời bằng một tập các tài liệu phù hợp. Yêu cầu đó
Câu truy vấn Tài liệu văn bản
Đại diện câu
truy vấn
Đại diện tài
liệu
Xử lý Xử lý
Đối sánh
(tính toán độ
tương đồng)
Kết quả truy vấn
Đánh giá mức
độ thích hợp
22
không có thuật toán cụ thể, nhưng được đảm bảo chiến lược xếp hạng luôn ưu tiên cho
những tài liệu hữu ích, tài liệu được coi là “gần” với truy vấn hơn sẽ được xếp lên trên
tài liệu khác trong danh sách tài liệu trả lời. Trên thực tế, thuật toán xếp hạng trong hệ
thống IR phần lớn dựa trên mô hình không gian vectơ - một cách tiếp cận cổ điển để
so sánh truy vấn với các tài liệu:
- Biểu diễn các truy vấn như các vectơ thuật ngữ, thành phần vectơ nhận giá trị 1
nếu thuật ngữ xuất hiện trong truy vấn và 0 trong trường hợp ngược lại.
- Biểu diễn vectơ thuật ngữ với các tài liệu sử dụng trọng số TF-IDF cho các
thành phần trong vectơ
- Sử dụng thước đo khoảng cách cosin để xếp hạng các tài liệu theo khoảng cách
thuật ngữ với truy vấn.
Mô hình trọng số TF-IDF được chứng minh rất hữu ích trong thực tế. Trong đó,
TF (Term Frequency) là tần số xuất hiện thuật ngữ, nghĩa là mỗi thành phần trong một
vectơ thuật ngữ được tính bởi số lần thuật ngữ đó xuất hiện trong tài liệu; IDF (Inverse
Document Frequency) được tính bằng công thức IDF = log(N/ni), với N là toàn bộ tài
liệu trong tập hợp và ni là số các tài liệu chứa thuật ngữ i. Với chỉ TF, nếu một thuật
ngữ xuất hiện thường xuyên trong các tài liệu thì nó chưa chắc đã là lựa chọn tốt làm
thuật ngữ chỉ mục, vì nó không giúp phân biệt các tài liệu người sử dụng quan tâm với
các tài liệu khác, tức là số lượng tài liệu được truy tìm lớn nhưng độ chính xác không
cao. IDF giúp cải thiện vấn đề này, trọng số của thuật ngữ sẽ rất cao nếu nó xuất hiện
thường xuyên chỉ trong một vài tài liệu, tức là giúp tăng cường sự phân biệt.
Cho Di = (di1, di2, …, diM) là tập hợp các tài liệu, với truy vấn Q biểu diễn như
một tài liệu. Trong đó, dij là trọng số thuật ngữ j trong tài liệu i, Q(j) biểu thị trọng số
của thuật ngữ j trong truy vấn Q (i =1, 2.., N; j = 1, 2, .., M). Các trọng số dij và Q(j) có
thể là 1 (nếu chứa thuật ngữ) hay 0 (nếu không chứa thuật ngữ) trong đại số quan hệ;
hoặc tính bằng TF-IDF hoặc có thể bằng nhiều cách khác. Tài liệu Di được đánh giá là
“gần” với truy vấn Q dựa vào thước đo sau:
1. Khoảng cách thuật ngữ (term distance):
2
1
))((
M
j
ijdjQ
2. Khoảng cách cosin (cosin distance): Thước đo này được sử dụng khá phổ biến
trong các mô hình thực tế và được mô tả như sau:
M
j
ij
M
j
M
j
ij
djQ
djQ
1
2
1
2
1
)(
))(((
23
Trong trường hợp xấu nhất, cần đến O(N) phép so sánh, mỗi so sánh cho một
tài liệu và mỗi so sánh cần O(M) thời gian cho từng thuật ngữ. Vậy, sẽ cần O(M×N)
thời gian để tìm giải pháp tốt nhất. Kỹ thuật chỉ số ngữ nghĩa tiềm tàng (LSI) sẽ làm
giảm đáng kể thời gian nói trên.
Xét ví dụ, với 10 tài liệu (ký hiệu: d1, d2,.., d10); và 6 thuật ngữ (ký hiệu: t1, t2,
.., t6). Trong đó:
t1 = database t2 = SQL t3 = index
t4 = regression t5 = likelihood t6 = linear
Ta sẽ lập được một ma trận tần số tài liệu - thuật ngữ M (106), trong đó mỗi
phần tử ij (hàng i, cột j) chứa số lần xuất hiện của thuật ngữ j trong tài liệu i.
t1 t2 t3 t4 t5 t6
d1 24 21 9 0 0 3
d2 32 10 5 0 3 0
d3 12 16 5 0 0 0
d4 6 7 2 0 0 0
d5 43 31 20 0 3 0
d6 2 0 0 18 7 16
d7 0 0 1 32 12 0
d8 3 0 0 22 4 2
d9 1 0 0 34 27 25
D10 6 0 0 17 4 23
Bảng 1.1 Ma trận tài liệu - thuật ngữ
Giả sử, với một câu truy vấn Q chứa các thuật ngữ database và index, ta có thể
biểu diễn truy vấn dưới dạng vectơ Q = (1, 0, 1, 0, 0, 0), tức là thuật ngữ t1 và t3 xuất
hiện trong truy vấn nên có giá trị là 1, còn lại nhận giá trị là 0.
Dựa vào ma trận tài liệu - thuật ngữ (bảng 1.1), ta tính được ma trận thuật ngữ -
tài liệu với các thành phần trọng số TF-IDF, được biểu diễn trong bảng sau. Giả sử
trong ví dụ này, thuật ngữ database có trọng số thấp hơn các thuật ngữ khác và ít có ý
nghĩa vì nó xuất hiện trong hầu hết các tài liệu.
2.53 14.56 4.60 0 0 2.07
3.37 6.93 2.55 0 1.07 0
1.26 11.09 2.55 0 0 0
0.63 4.85 1.02 0 0 0
4.53 21.48 10.21 0 1.07 0
0.63 0 0 11.78 1.42 15.94
0.21 0 0 22.18 4.28 0
24
0.31 0 0 15.24 1.42 1.38
0.10 0 0 23.56 9.63 17.33
Bảng 1.2 Ma trận kết quả tài liệu - thuật ngữ TF-IDF
Sử dụng đơn vị đo khoảng cách cosin, tính độ tương đồng hay “gần” giữa truy
vấn với các tài liệu. Không giống với kết quả truy tìm trong đại số quan hệ, đây là đại
lượng đo khoảng cách mang lại sự xếp hạng cho mọi tài liệu, gồm ít nhất có một thuật
ngữ phù hợp. Dựa vào bảng 1.1 và 1.2 tính khoảng cách tương ứng theo TF và TF-
IDF.
Document
khoảng cách
TF
Khoảng cách
TF-IDF
d1 0.70 0.32
d2 0.77 0.51
d3 0.58 0.24
d4 0.60 0.23
d5 0.79 0.43
d6 0.14 0.02
d7 0.06 0.01
d8 0.02 0.02
d9 0.09 0.01
d10 0.01 0.00
Bảng 1.3 Kết quả khoảng cách từ truy vấn Q với các tài liệu
Kết quả tính được xếp hạng các tài liệu theo mức độ phù hợp. Kết quả trên cho
thấy, sử dụng ma trận TF tài liệu d5 là “gần” nhất, còn với ma trận TF-IDF thì d2 được
xem là “gần” nhất.
25
CHƯƠNG 2. MỘT SỐ KỸ THUẬT TÌM KIẾM
Tất cả các chiến lược tìm kiếm được dựa vào việc so sánh giữa truy vấn với các
tài liệu được lưu trữ. Đôi khi, việc so sánh này chỉ là gián tiếp khi truy vấn được so
sánh với các cụm (hoặc chính xác hơn với những đặc điểm đại diện cho các cụm).
Tạo sự phân biệt giữa các kiểu chiến lược tìm kiếm khác nhau đôi khi có thể
được hiểu qua việc xét ngôn ngữ truy vấn, đó là ngôn ngữ để biểu diễn thông tin. Tính
tự nhiên của ngôn ngữ truy vấn thường yêu cầu tính tự nhiên trong chiến lược tìm
kiếm. Ví dụ, một ngôn ngữ truy vấn được biểu diễn bằng việc kết hợp theo logic các từ
khóa cho phép tìm kiếm, thông thường được yêu cầu kiểu tìm kiếm Boolean. Đây là
mô hình tìm kiếm mà kết quả mang lại là kiểu logic qua việc so sánh truy vấn với các
tài liệu. Tuy nhiên, ở đây ta không kiểm tra các ngôn ngữ truy vấn nhưng thay vào đó
nhận biết được sự khác nhau qua việc đưa vào các máy tìm kiếm.
2.1 Các truy vấn Boolean và chỉ mục tài liệu [1] [5] [11]
2.1.1 Truy vấn Boolean
Loại đơn giản nhất của truy vấn yêu cầu gồm mối quan hệ giữa các thuật ngữ
và các tài liệu, các truy vấn giống như:
1. Những tài liệu chứa từ “Java”
2. Những tài liệu chứa từ “Java” nhưng không chứa từ “coffee”
3. Các tài liệu chứa cụm “Java beans” hoặc thuật ngữ “API”
4. Các tài liệu mà “Java” và “Island” xuất hiện trong cùng một câu.
Hai truy vấn đầu được gọi là những truy vấn “gần” (proximity queries) bởi
chúng bao gồm khoảng cách từ vựng giữa các dấu hiệu. Các câu hỏi này có thể được
trả lời sử dụng chỉ số ngược. Phần sau sẽ mô tả việc các chỉ số được xây dựng từ một
tập hợp các tài liệu ngược như thế nào.
Các câu truy vấn được biểu diễn bởi tập từ khóa kết nối với tập phép toán Bool.
Ba loại toán tử hay được sử dụng là OR, AND và NOT. Quy tắc truy tìm kiếm như
sau:
- Toán tử OR: Xem xét hai thuật ngữ đồng nghĩa. Ví dụ, cho trước câu truy vấn
(term1 OR term2) thì hiện diện của một trong hai thuật ngữ trong bản ghi (hay trong
tài liệu) đủ để đáp ứng truy tìm bản ghi này.
- Toán tử AND: Tổ hợp các thuật ngữ (hay từ khóa) vào một câu thuật ngữ.
Vậy, truy vấn (term1 AND term2) chỉ ra cả hai thuật ngữ phải đồng thời hiện diện
trong tài liệu để đem lại kết quả.
- Toán tử NOT: Là hạn chế hay thuật ngữ hẹp, thông thường nó được sử dụng
với toán tử AND. Câu truy vấn (term1 AND NOT term2) dẫn tới truy tìm bản ghi có
26
term1 nhưng không có term2.
2.1.2 Cấu trúc tệp
Một trong các vấn đề cơ bản trong thiết kế hệ thống IR là quyết định sử dụng
loại cấu trúc tệp nào để lưu trữ CSDL tài liệu. Cấu trúc tệp sử dụng trong các hệ thống
IR bao gồm các tệp phẳng, tệp mục lục (inverted), tệp chữ ký và các tệp khác như cây
và đồ thị.
Với quan điểm tệp phẳng, một hay nhiều tài liệu lưu trữ trong tệp, thông thường
trong mã ASCII hay EBCDIC, không chỉ mục tài liệu. Tìm kiếm tệp phẳng thông qua
tìm kiếm mẫu. Trong UNIX, khi lưu trữ tập hợp các tài liệu người ta lưu trữ mỗi tài
liệu trong một tệp, trong danh mục. Các tệp này có thể tìm kiếm nhờ các công cụ tìm
kiếm theo mẫu như “grep”, “awk”. Tiệm cận này không hiệu quả vì mỗi lần truy vấn
thì toàn bộ tập hợp tài liệu phải được duyệt để tìm ra mẫu văn bản.
Các tệp chữ ký (signature files): chứa các chữ ký (mẫu bit) đại diện cho tài liệu.
Có nhiều cách để sinh chữ ký tài liệu. Câu truy vấn được đại diện bởi chữ ký mà nó sẽ
được so sánh với chữ ký tài liệu trong khi truy tìm.
Cách sử dụng chung nhất là tệp mục lục (inverted). Đó là loại tệp chỉ mục.
Các tệp mục lục (Inverted Files)
Trong tệp mục lục, chỉ mục được xây dựng cho mỗi thuật ngữ để lưu trữ chỉ số
định danh (ID) bản ghi cho toàn bộ bản ghi chứa thuật ngữ này. Một đầu vào tệp mục
lục thông thường chứa từ khóa (thuật ngữ) và một số ID tài liệu. Mỗi từ khóa và các
ID tài liệu (mà nó chứa từ khóa) được tổ chức thành một hàng. Ví dụ tệp mục lục như
sau:
Term1: Record1, Record3
Term2: Record1, Record2
Term3: Record2, Record3, Record4
Term4: Record1, Record2, Record3, Record4
trong đó, Termi (i = 1,2,3,4) là số ID của thuật ngữ chỉ mục i, Recordi (i = 1, 2, 3, 4)
là số ID của bản ghi (record) i hay tài liệu i.
Dòng 1 có nghĩa rằng Record1 và Record3 chứa Term1. Các dòng khác có ý
nghĩa tương tự. Việc tìm kiếm sẽ được thực hiện nhanh chóng trong các tệp mục lục.
Chỉ các hàng chứa thuật ngữ tìm kiếm mới được truy tìm. Không cần tìm mọi bản ghi
trong CSDL.
Quy tắc tìm kiếm bằng mô hình Bool trên cơ sở các tệp mục lục như sau:
Truy vấn AND: Ví dụ (Termi AND Termj), cho danh sách trộn hàng i với hàng j
trong tệp mục lục và mọi bản ghi đều chứa Termi và Termj sẽ là kết quả truy
tìm ở đầu ra. Ví dụ: (Term1 AND Term2) cho kết quả là Record1.
Truy vấn OR: Ví dụ (Termi OR Term j), cho danh sách trộn cho hàng i và j, mọi
27
mục trong danh sách trộn là đầu ra kết quả. Ví dụ truy vấn (Term1 OR Term2)
sẽ cho kết quả là Record1, Record2 và Record3.
Truy vấn NOT: Ví dụ (Termi AND NOT Termj) sẽ cho kết quả là các mục xuất
hiện trong hàng i nhưng không trong hàng j. Truy vấn (Term4 AND NOT
Term1) cho kết quả là Record2, Record4. Truy vấn (Term1 AND NOT Term4)
sẽ cho đầu ra là rỗng.
Mở rộng thao tác tệp mục lục
Cho đến thời điểm hiện tại ta đã bỏ qua hai yếu tố quan trọng khi chỉ mục và
truy tìm tài liệu, đó là vị trí của các thuật ngữ và ý nghĩa các thuật ngữ (tần số thuật
ngữ) trong tài liệu. Trong các truy vấn AND, mọi bản ghi chứa cả hai thuật ngữ được
tìm thấy, không quan tâm đến vị trí của chúng trong tài liệu. Các thuật ngữ có tầm
quan trọng như nhau, không quan tâm đến tần số xuất hiện trong tài liệu. Để nâng cao
hiệu quả truy vấn, hai yếu tố này cần được xem xét.
Các quan hệ đặc tả giữa hai hay nhiều thuật ngữ được tăng cường bằng cách bổ
sung các tham số “tính gần kề” vào đặc tả truy vấn. Khi tham số gần kề được bổ sung,
chủ điểm được xác định cụ thể hơn, tính phù hợp của mục truy vấn được sẽ cao hơn.
Hai tham số thuộc nhóm này có thể là đặc tả “within sentence” và “adjacency”:
(Termi within sentence Termj) có nghĩa rằng thuật ngữ i và thuật ngữ j cùng
xuất hiện trong câu của bản ghi vừa tìm ra.
(Termi adjacency Termj) có nghĩa các thuật ngữ i và j xuất hiện liền kề trong
các tài liệu tìm ra.
Để hỗ trợ loại truy vấn này, thông tin vị trí thuật ngữ phải gộp vào tệp mục lục.
Cấu trúc tổng quát của file này sẽ như sau:
Termi: Record no., Paragraph no., Sentence no., Word no.
Ví dụ, nếu tệp mục lục có các đầu vào sau:
information: R99, 10, 8, 3; R15, 15, 3, 6; R166, 2, 3, 1
retrieval: R77, 9, 7, 2; R99, 10, 8, 4; R166, 10, 2, 5
thì kết quả truy vấn (information within sentence retrieval) là R99.
Trong ví dụ trên, các thuật ngữ “information” và “retrieval” xuất hiện trong
cùng câu R99 của tài liệu. Mặt khác, dù R166 đều chứa cả hai thuật ngữ này nhưng lại
ở vị trí khác nhau của tài liệu, do vậy truy vấn không cho lại kết quả (không phải là
“information retrieval”). Có thể hai thuật ngữ này được sử dụng trong các ngữ cảnh
khác nhau.
2.1.3 Các từ dừng và từ gốc
Đa số ngôn ngữ tự nhiên có những từ chức năng, những liên từ, giới từ xuất
hiện với số lượng lớn trong các tài liệu và điển hình là ít được sử dụng trong việc xác
28
định các tài liệu thoả mãn thông tin tìm kiếm. Các từ như vậy (ví dụ a, an, the, on
trong tiếng Anh) được gọi là từ dừng (stopword).
Các kỹ thuật tìm kiếm thông thường không chỉ số hoá các từ dừng, nhưng có ý
tưởng thay thế chúng với một đối tượng thay thế để ghi nhớ sự xuất hiện của các từ
dừng. Điều này cho phép tìm kiếm những cụm từ chứa các từ dừng, ví dụ như “gone
with the wind”. Việc giảm bớt không gian chỉ số và cải thiện thực hiện là những lý do
quan trọng để loại trừ các từ dừng. Tuy nhiên, như vậy một số câu truy vấn như “to be
or not to be” có thể không còn được hỏi. Một điều nữa là từ nhiều nghĩa (một từ có
nhiều nghĩa phụ thuộc vào văn cảnh hoặc cách nói): “can” là một động từ thì không có
ích cho các truy vấn từ khoá, nhưng “can” là một danh từ có thể là trung tâm đối với
một câu truy vấn, vì vậy nó không nằm trong danh sách từ dừng.
Stemming (từ gốc) hay conflating là phương thức hỗ trợ sự phù hợp của một
thuật ngữ truy vấn với biến đổi hình thái trong kho dữ liệu. Trong tiếng Anh, cũng như
trong một số ngôn ngữ khác, các phần của văn nói, thời và số lượng được chuyển từ
những biến tố của từ. Có thể muốn một truy vấn chứa từ “gaining” phù hợp với một tài
liệu chứa từ “gains”, hay tài liệu chứa đựng từ “went” dùng để trả lời cho một truy vấn
chứa từ “goes”. Các phương pháp stemming nhìn chung sử dụng sự kết hợp việc phân
tích hình thái (chẳng hạn, thuật toán của Porter và tra cứu từ điển như WordNet).
Stemming có thể làm tăng số lượng các tài liệu trả lời, nhưng có thể bao gồm cả các tài
liệu không thích hợp. Chẳng hạn, giải thuật của Porter không chấp nhận “university”
và “universal” cùng là “univers”. Conflating, xác định các thuật ngữ liên quan qua việc
sử dụng từ điển, trong đó liệt kê các thuật ngữ đồng nghĩa và đôi khi liệt kê cả quan hệ
giữa chúng. Ví dụ, các từ “study”, “learning”, “schoolwork”, “reading” có ý nghĩa
tương tự nhau. Thay vì sử dụng 4 thuật ngữ chỉ mục, có thể chỉ sử dụng một thuật ngữ
“study” tổng quát để đại diện bốn thuật ngữ này.
2.1.4 Chỉ số hoá và bổ sung
Các tài liệu được duyệt và phân loại để được mệnh đề (d, t), gồm tài liệu d với
thuật ngữ t. Thao tác cơ bản của việc chỉ mục “ngược” (inverting) bao gồm việc đổi
chỗ thứ tự sắp xếp theo (t, d) như biểu diễn sau.
Chúng ta dễ dàng tạo tập (t, d) trong cấu trúc dữ liệu. Với một tập hợp động có
các tài liệu được thêm vào, sửa đổi hay xoá đi, một sự thay đổi tài liệu ở mức đơn giản
cần cập nhật hàng trăm tới hàng nghìn các bản ghi.
Hình 2.1 đưa ra một giải pháp đơn giản hơn. Đầu tiên, một chỉ số chuẩn tĩnh
được tạo ngoài (t, d) được phân loại. Đây là chỉ mục chính được dùng để trả lời các
câu truy vấn. Trong đó, các tài liệu được thêm vào hay xoá đi được gọi là “documents
in flux” (ở đây, chúng ta có thể mô tả sự thay đổi dữ liệu với việc xoá thực hiện sau
việc chèn cho đơn giản). Các tài liệu thay đổi liên tục (flux) được biểu diễn bởi một
29
bản ghi được kí hiệu (d, t) biểu diễn bằng (d, t, s), trong đó s là một bit cho biết tài liệu
đã được xoá hay được chèn.
Hình 2.1 Sơ đồ duy trì các chỉ số trong tập hợp động
Các bản ghi (d, t, s) được đánh chỉ mục để tạo một chỉ mục phụ. Truy vấn của
người sử dụng được gửi cho cả chỉ mục chính và chỉ mục phụ. Mục đích chỉ mục
chính là trả lại một tập tài liệu D0. Chỉ mục phụ trả lại hai tập tài liệu: một là D+, là tập
các tài liệu vẫn chưa được đánh chỉ mục trong D0 mà được đối sánh với truy vấn và tập
khác là D-, là tập đối sánh các tài liệu với truy vấn đã được loại bỏ khỏi tập hợp từ khi
D0 được xây dựng. Câu trả lời cuối cùng cho truy vấn là D0 D+ \ D-
Chỉ số phụ được tạo nhanh chóng, bởi vậy có thể không được xây dựng cẩn
thận và chuẩn như chỉ số chính. Khi chỉ số phụ trở nên quá lớn, kí hiệu các bản ghi (d,
t, s) được phân loại trong (t, d, s) và trộn-lọc (merge – purged) trong các bản ghi (t, d)
chính. Kết quả được sử dụng để xây dựng lại chỉ mục chính và khi đó chỉ số phụ có
thể được làm rỗng. Thông thường, điều này bao gồm việc phân tích các log truy vấn
cho những từ khoá thường xuyên và ưu tiên các bản ghi ngược.
2.1.5 Kỹ thuật nén chỉ số (index compression)
Trường hợp các modul thiếu từ dừng và dấu chấm câu, một chỉ số ngược với
thông tin vị trí có thể được sử dụng để xây dựng lại các tài liệu trong một tập hợp. Bởi
vậy, kích thước của chỉ mục thực tế so sánh được với kích thước của kho dữ liệu. Mặc
30
dù, việc lưu trữ đem lại một số lợi ích nhưng chỉ số chương trình điều khiển lớn sẽ dẫn
tới một số lượng lớn I/O ngẫu nhiên. Bởi vậy, cài đặt IR lớn, hiệu năng cao thì việc
nén chỉ số càng nhiều càng tốt là thực sự quan trọng và nó có thể được lưu giữ trong
bộ nhớ.
Một phần chính của không gian chỉ mục bị chiếm bởi các ID tài liệu. Một ID tài
liệu cần một tập hợp lớn hơn, số lượng các bit lớn hơn để biểu diễn. Trên Internet,
phần lớn cần ít nhất 32 bit để biểu diễn các ID tài liệu trong một hệ thống truy xuất
trên 2 tỉ trang.
Cách dễ hơn trong việc lưu trữ các ID tài liệu là sắp xếp chúng tăng dần và lưu
trữ đầy đủ ID đầu tiên, rồi sau đó chỉ lưu sự khác nhau với ID trước mà chúng ta gọi là
gap. Điều này được gọi là mã hoá delta (delta encoding).
Chẳng hạn, nếu từ bottle xuất hiện trong các tài liệu được đánh số 5, 30 và 47,
bản ghi cho bottle là vectơ (5, 25, 17).
Với ví dụ này có thể không giống như việc lưu trữ tài liệu với số lượng lớn,
nhưng đã cho thấy các thuật ngữ thường xuyên thì ID gap trung bình sẽ nhỏ hơn và
những thuật ngữ hiếm xuất hiện dù sao cũng không chiếm quá nhiều không gian, vì
vậy cả hai trường hợp đó đều có lợi.
Vấn đề tiếp theo là mã hoá những gap này với số lượng các bit hay biến đổi, vì
vậy một gap nhỏ yêu cầu số các bit ít hơn nhiều so với một ID tài liệu. Mã hoá nhị
phân chuẩn gán cùng chiều dài cho tất cả các ký hiệu hay những giá trị sẽ được mã
hoá, là tối ưu (nếu số các bit trong mã hoá giá trị x là L(x), yêu cầu của mã này là
x xLx )()Pr( số các bit yêu cầu để truyền một kí hiệu. Một mã tối ưu giảm đến mức
tối thiểu giá trị này) khi tất cả các giá trị có thể tương đương, trừ các gap. Cách khác
với mã đơn nguyên (một gap x được biểu diễn bởi x-1 những dấu hiệu theo sau), ưu
tiên những gap ngắn khá mạnh (nó là tối ưu nếu gap theo sau được đưa ra bởi Pr(X
=x)=2-x, xác suất của việc làm mất các gap lớn).
Có nhiều phương pháp cũng sử dụng các kỹ thuật giảm bớt chi phí thời gian.
Cách tiếp cận đơn giản là tập hợp các tài liệu trong các kho (buckets). Giả sử chúng ta
có một triệu tài liệu, mỗi tài liệu với ID 20-bit. Chúng ta có thể tập hợp chúng vào một
nghìn bucket với một nghìn tài liệu trong mỗi bucket. Các ID bucket sẽ yêu cầu chi phí
chỉ 10 bit.
Cách khác đơn giản hơn, một chỉ mục ngược được thiết lập từ các thuật ngữ
đến các ID bucket, tiết kiệm được rất nhiều không gian vì các ID tài liệu rút ngắn lại
đến một nửa kích thước. Khi một bucket trả lời một truy vấn, tất cả các tài liệu trong
bucket đó cần được duyệt, tốn nhiều thời gian hơn. Tránh điều đó, cách tiếp cận thứ
hai của ý tưởng là chỉ mục các tài liệu trong mỗi bucket riêng rẽ. Ý tưởng sơ bộ sử
dụng các kỹ thuật như vậy để giới hạn không gian thực hiện.
31
Thông thường, một chỉ mục bị nén tới giới hạn thì việc nâng cấp rất hỗn độn
khi thêm, xoá hoặc sửa đổi các tài liệu. Ví dụ, nếu có các tài liệu mới thì phải thêm vào
chỉ mục ngược, các bản ghi của một vài thuật ngữ sẽ tăng kích thước. Điều đó chỉ có
thể được giải quyết với nhiều I/O ngẫu nhiên tạo ra những việc cập nhật thay đổi lớn.
2.1.6 Chỉ mục tự động
Trong tiến trình chỉ mục, tài liệu được coi như danh sách các từ, trong đó các từ
dừng đã được loại khỏi danh sách. Các thuật ngữ hay từ còn lại được xử lý tiếp để
nâng cao hiệu quả chỉ mục và truy tìm. Các thao tác chung nhất thực hiện trên các
thuật ngữ này là tìm từ gốc (stemming), tìm từ đồng nghĩa và xác định trọng số.
Với stemming, tệp chỉ mục sẽ đầy đủ hơn và việc truy tìm thông tin sẽ hiệu quả
hơn. Recall thông tin sẽ được nâng cao bởi vì gốc từ (root) tổng quát hơn và nhiều tài
liệu liên quan sẽ được tìm ra để đáp ứng câu truy vấn. Nhưng precision có thể giảm vì
thuật ngữ gốc từ ít tính cụ thể.
Các thuật ngữ chỉ mục khác nhau có các tần số xuất hiện và tầm quan trọng
khác nhau trong tài liệu. Chú ý rằng, tần số xuất hiện của các thuật ngữ sau khi thực
hiện stemming và thực hiện thesaurus sẽ là tổng tần số của mọi biến đổi (variantions).
Ví dụ, tần số khái niệm “retriev” sẽ là tổng tần số xuất hiện của các thuật ngữ
“retrieve”, “retrieval”, “retrieving” và “retrieved”. Việc đề xuất các trọng số “thuật
ngữ quan trọng” cho thuật ngữ tài liệu và thuật ngữ câu truy vấn có thể giúp phân biệt
mức độ quan trọng của các thuật ngữ trong kết quả tìm kiếm. Khi bổ sung trọng số cho
các thuật ngữ trong tệp mục lục, các tài liệu khác nhau với tính tương đồng khác nhau
có thể xếp hạng theo dãy thứ tự độ tương đồng giảm dần, vào thời điểm truy vấn.
Ví dụ một tệp mục lục với trọng số thuật ngữ như sau:
Term1: R1, 0.3; R3, 0.5; R6, 0.8; R7, 0.2; R11, 1
Term2: R2, 0.7; R3, 0.6; R7, 0.5; R9, 0.5
Term3: R1, 0.8; R2, 0.4; R9, 0.7
Dòng đầu tiên có nghĩa rằng trọng số của thuật ngữ 1 (Term1) là 0.3 trong bản
ghi 1 (R1), 0.5 trong bản ghi 3 (R3), 0.8 trong bản ghi 6 (R6), 0.2 trong bản ghi 7 (R7)
và 1 trong bản ghi 11 (R11). Tương tự trong các dòng khác.
Các thao tác Bool với trọng số thuật ngữ có thể thực hiện như sau:
- Truy vấn OR: Trọng số cao hơn giữa các bản ghi chứa các thuật ngữ truy vấn
được sử dụng làm độ tương đồng giữa câu truy vấn và tài liệu. Danh sách kết quả xếp
theo thứ tự độ tương đồng giảm dần. Ví dụ, truy vấn (Term2 OR Term3) có thứ tự đầu
ra là R1 (0.8), R2 (0.7), R9 (0.7), R3 (0.6) và R7 (0.5).
- Truy vấn AND: Trọng số thấp hơn giữa các bản ghi chung, phù hợp thuật ngữ
truy vấn được sử dụng làm độ tương đồng giữa câu truy vấn và tài liệu. Ví dụ, truy vấn
(Term2 AND Term3) có thứ tự đầu ra là R9 và R2.
32
- Truy vấn NOT: Độ tương đồng giữa câu truy vấn và các tài liệu là khác nhau
giữa các đầu vào trong tệp mục lục. Ví dụ, truy vấn (Term2 AND NOT Term3) có thứ
tự đầu ra là R3, R7.
Việc sắp xếp kết quả cho lại theo thứ tự rất quan trọng vì những mục đầu tiên
phải là có ích nhất cho người sử dụng. Họ chỉ cần quan sát vài mục đầu tiên thay cho
duyệt toàn bộ kết quả.
Việc gán các thuật ngữ chỉ mục cho tài liệu và câu truy vấn để phân biệt các tài
liệu mà người sử dụng quan tâm với các tài liệu khác.
Trong một tài liệu cụ thể, thuật ngữ nào xuất hiện thường xuyên hơn thì nó quan
trọng hơn, nên nó có trọng số lớn hơn.
Trong ngữ cảnh tập hợp toàn bộ tài liệu, nếu thuật ngữ xuất hiện hầu hết trong
các tài liệu thì nó không phải là lựa chọn tốt làm thuật ngữ chỉ mục, vì nó không giúp
phân biệt các tài liệu người sử dụng quan tâm với tài liệu khác.
Do vậy, thuật ngữ được chỉ mục tốt là thuật ngữ xuất hiện thường xuyên trong
vài tài liệu nhưng không xuất hiện trong các tài liệu khác. Khi gán trọng số thuật ngữ,
cần phải quan tâm đến cả hai: tần số thuật ngữ (tfij) và tần số tài liệu (dfj). Công thức
chung để tính trọng số thuật ngữ là:
Wij = tfij * log (N/dfj)
trong đó, Wij là trọng số của thuật ngữ j trong tài liệu i, tfij là tần số của thuật ngữ j
trong tài liệu i, N là tổng số tài liệu trong tập hợp, dfj là số tài liệu chứa thuật ngữ j.
Trọng số trên 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ủ đề tTtest 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 (td) để biểu diễn ma
trận nhỏ hơn (kk). 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 (td) 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à (22), ma trận B có bậclà (24).
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 (M1M2) 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 (mn) thành
cột của AT(mn). 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
dt
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 (km)
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
Các file đính kèm theo tài liệu này:
- 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.pdf