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 - 2015
3
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
MỞ ĐẦU
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
1.1.2 Mục tiêu chính
1.1.3 Mô hình dữ liệu đa phương tiện
1.2 Trích chọn đặc trưng, chỉ mục và đo tính tương tự [1]
1.2.1 Trích chọn đặc trưng
1.2.2 Chỉ số hóa cấu trúc
5
6
7
8
11
11
11
13
13
14
15
16
1.2.3 Đo tính tương tự
1.3 Hệ thống truy tìm thông tin (IR-Information retrieval) [1] [3] [4] [9] [13]
17
17
1.3.1 Khái quát
1.3.2 Vấn đề truy tìm tài liệu văn bản (Text retrieval)
1.3.3 Phân biệt các hệ thống IR và DBMS (DataBase Manager System)
1.4 xếp hạng tài liệu (Ranking) [1] [8]
17
18
20
21
CHƯƠNG 2- MỘT SỐ KỸ THUẬT 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
2.1.2 Cấu trúc tệp
2.1.3 Các từ dừng và từ gốc
25
25
25
26
27
2.1.4 Chỉ số hoá và bổ sung
2.1.5 Kỹ thuật nén chỉ số (index compression)
2.1.6 Chỉ mục tự động
2.2 Thước đo hiệu năng [1] [5] [8]
2.3 Mô hình truy tìm không gian vectơ [1] [11]
2.4 Mô hình truy tìm theo xác suất [1] [6]
2.5 Mô hình truy tìm trên cơ sở cụm [1] [6]
28
29
31
33
36
37
38
2.6 Kỹ thuật phản hồi phù hợp [1] [11]
2.7 Mô hình LSI (Latent semantic indexing) [1] [5] [6] [7] [8] [9]
2.7.1 Ý tưởng cơ bản của LSI
2.7.2 Một số khái niệm cơ bản
39
40
40
42
4
2.7.3 Kỹ thuật SVD (singular value decomposition)
CHƯƠNG 3- CÀI ĐẶT THỰC NGHIỆM MÔ HÌNH LSI
3.1 Bài toán
3.2 Chức năng của chương trình
3.3 Hoạt động cơ bản trong chương trình
43
54
54
55
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 Hệ thống truy tìm thông tin đa
phương tiện
System
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 ....................................................... 23
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.................................................................................. 36
Bảng 2.2 Số lần xuất hiện của thuật ngữ trong mỗi tài liệu ............................................... 46
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
7
Hình 3.8 Đồ thị biểu diễn các vecto tài liệu và vecto truy vấn.........................................59
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
8
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ụ, 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
9
đư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 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.
10
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 tế điện tử và
11
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ỗ 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
12
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.
13
Tầng đối
tượng
Tầng
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.
14
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 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à
15
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 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).
16
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.
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ả
17
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.
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 (nonnumerical), 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.
18
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:
- Đ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.
19
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 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
20
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 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
Câu truy vấn
Tài liệu văn bản
Xử lý
Xử lý
Đại diện c âu
truy v ấn
Đại diện tài
li ệu
Đối sánh
(tính toán độ
tương đồng)
Kết quả truy vấn
Đánh giá mức
độ thích hợp
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
21
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 đó 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
- Xem thêm -