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 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