Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
DANH MỤC CÁC TỪ TIẾNG ANH VÀ VIẾT TẮT
Từ gốc Nghĩa
IR (Information Retrieval) Truy tìm thông tin
MIRS (MultiMedia Information
Retrieval System)
Hệ truy tìm thông tin đa phương tiện
MM (MultiMedia) Truyền thông da phương tiện
Exact match Đối sánh chính xác
Cluster-based Cơ sở cụm
DBMS
(DatabaseManagementSystem)
Hệ quản trị cơ sở dữ liệu
Term Từ
Doc Tài liệu
Docs Nhiều tài liệu
Query Truy vấn
DSS (DecisionSupportSystems) Hệ hỗ trợ ra quyết định
IMS (InfomationManagementSystem) Hệ quản lý thông tin
QAS (QuestionAnserSystem) Hệ trả lời câu hỏi
Text-partern Mẫu văn bản
Ranking Xếp loại
SC (Similarity Coeficient) Độ tương quan
Index Chỉ mục
Precision Độ chính xác
Recall Khả năng tìm thấy
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
LỜI NÓI ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT và ngành công
nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ
thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hoá một
cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh
vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Với
một lượng thông tin như vậy thì vấn đề đặt ra là phải làm sao sử dụng chúng vào
đúng mục đích và hiệu quả nhất thì cũng là một vấn đề đặt ra hiện nay. Mặt khác,
trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ
nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất
định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với
những lý do như vậy, cần phải có các công cụ hỗ trợ để giúp cho việc tìm kiếm
thông tin được nhanh và hiệu quả. Vì vậy mục tiêu của luận văn này nhằm tìm hiểu
và xây dựng một hệ thống tìm kiếm thông tin cụ thể là tìm kiếm tài liệu văn bản trên
cơ sở phân cụm dữ liệu. Nhằm đáp ứng nhu cầu cấp thiết của thời đại.
Bố cục của luận văn gồm các phần sau:
+ CHƯƠNG 1 - TỔNG QUAN: Giới thiệu chung về hệ thống thông tin đa
phương tiện.
+ CHƯƠNG 2 - HỆ TÌM KIẾM THÔNG TIN: Giới thiệu về hệ thống tìm
kiếm thông tin (IR), sự khác nhau giữa hệ thống tìm kiếm thông tin và các hệ thống
thông tin khác, các mô hình th ường gặp trong hệ thống tìm kiếm thông tin.
+ CHƯƠNG 3 - KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG :
Khái quát chung về phân cụm, các kiểu dữ liệu trong phân cụm và ứng dụng kỹ
thuật phân cụm dữ liệu trong tìm kiếm thông tin.
+ CHƯƠNG 4 - CHƯƠNG TRÌNH DEMO: Cài đặt một chương trình tìm
kiếm thông tin trên cơ sở lý thuyết đã trình bày.
+ KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: Trình bày các kết quả đạt được
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
và nêu phương hướng phát triển của đề án trong tương lai.
+ TÀI LIỆU THAM KHẢO
CHƯƠNG 1: TỔNG QUAN
1.1. ĐẶT VẤN ĐỀ
Vài năm trước đây, các nghiên cứu và phát triển thuộc lĩnh vực đa phương
tiện (MultiMedia) tập trung vào các vấn đề như: truyền thông, authoring và trình
diễn đa phương tiện.
Trải qua nhiều năm đã có khối lượng lớn dữ liệu Multimedia (ảnh, video, âm
thanh) được thu thập và lưu trữ dưới dạng số, thí dụ:
• Ảnh X quang,
• Các băng hình dạy học…
• Điều tra cảnh sát về các giọng nói trong điện thoại…
• Tài liệu văn bản, …
Nghiên cứu của những năm gần đây tập trung chủ yếu vào: lưu trữ và tìm
kiếm hiệu quả dữ liệu đa phương tiện. Tình hình tương tự như hơn 30 năm trước
đây khi nhiều dữ liệu text được lưu trữ dưới khuôn dạng máy tính có thể đọc được.
Từ đó dẫn tới việc phát triển các hệ thống quản trị cơ sở dữ liệu
(DatabaseManagmentSystem) mà ngày nay được sử dụng trong hầu hết các cơ
quan, tổ chức. Tuy nhiên hệ quản trị cơ sở dữ liệu không thể quản lý dữ liệu đa
phương tiện một cách hiệu quả bởi vì các tính chất dữ liệu văn bản và dữ liệu đa
phương tiện là khác nhau. Do vậy, dẫn tới việc nghiên cứu phát triển các kỹ thuật
truy tìm và chỉ mục mới trong hệ thống quản trị cơ sơ dữ liệu và việc phát triển hệ
thống truy tìm tài liệu văn bản – một phần của dữ liệu đa phương tiện cũng không
nằm ngoài xu thế đó.
Luận văn tập trung nghiên cứu cách tìm kiếm văn bản trên cơ sở phân cụm dữ
liệu. Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là
tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.
1.2. HỆ THỐNG THÔNG TIN ĐA PHƯƠNG TIỆN:
Đa phương tiện là gì? Đa phương tiện là tích hợp của văn bản, âm thanh, hình
ảnh của tất cả các loại và phần mềm có điều khiển trong một môi trường thông tin số.
Dữ liệu đa phương tiện gồm dữ liệu về :
Văn bản;
Hình ảnh;
Âm thanh;
Hình động.
1.2.1. Khái niệm về đa phương tiện
Con người có nhu cầu diễn tả các trạng thái của mình; và họ có nhiều loại
hình thể hiện. Con người có nhu cầu truyền thông, do đó cách thể hiện trên đường
truyền rất quan trọng. Trên Internet thông dụng với mọi người, cái đẹp của trang
Web phải được thể hiện cả ở nội dung và hình thức.
Đa phương tiện có nhiều loại, những phương tiện công cộng về đa phương
tiện: Radio, vô tuyến, quảng cáo, phim, ảnh
Nhu cầu về tương tác người - máy luôn đặt ra trong hệ thống thông tin. Vấn
đề chính về tương tác người - máy không là quan hệ giữa con người với máy tính
mà là con người với con người. Con người có vai trò quan trọng trong hệ thống
thông tin.
Môi trường
Xử lý thông tin
Thông tin ra
Phản hồi
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
Hình 1.1: Hệ thống thông tin
Định nghĩa
Định nghĩa đa phương tiện (theo nghĩa rộng) là bao gồm các phương tiện:
văn bản, hình vẽ tĩnh (vẽ, chụp), hoạt hình (hình ảnh động), âm thanh.
Hay có thể định nghĩa đa phương tiện; đa phương tiện là kỹ thuật mô phỏng
và sử dụng đồng thời nhiều dạng phương tiện chuyển hoá thông tin và các tác phẩm
từ các kỹ thuật đó.
1.2.2. Media
Media (tiếng Latin: medius, tiếng Anh: means, intermediary) là đề cập đến các
loại thông tin hay loại trình diễn thông tin như dữ liệu văn bản, ảnh, âm thanh và
video.
Phân loại media: Có nhiều cách phân loại, nhưng cách chung nhất là phân
loại trên cơ sở khuôn mẫu (format) vật lý hay các quan hệ media với thời gian. Qui
định này dẫn tới hai lớp media: tĩnh (static) và động (dynamic).
• Static media: Không có chiều thời gian, nôi dung và ý nghĩa của chúng
không phụ thuộc vào thời gian trình diễn. Media tĩnh bao gồm dữ liệu văn bản, đồ
họa.
• Dynamic media: Có chiều thời gian, ý nghĩa và độ chính xác của chúng
phụ thuộc vào tốc độ trình diễn. Dynamic media bao gồm annimation, video, audio.
Media động phụ thuộc chặt chẽ vào tốc độ trình diễn. Thí dụ để cảm nhận chuyển
động trơn tru, video phải được trình chiếu với tốc độ 25 frame/sec (hay 30
frame/sec phụ thuộc vào loại hệ thống video). Tương tự, khi ta trình diễn (play) tiếng
nói, âm nhạc, chúng chỉ được cảm nhận tự nhiên khi đạt được tốc độ nhất định, nếu
không chúng làm giảm chất lượng và ý nghĩa của âm thanh. Vì các media này phải
được trình diễn liên tục và ở tốc độ cố định cho nên chúng còn được gọi là media liên
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
tục. Hay còn gọi chúng là media đẳng thời (isochronous media) vì quan hệ giữa các
đơn vị media và thời gian là cố định.
1.2.3. Multimedia
Khái niệm multimedia (tiếng Latin: multus- tiếng Anh: numerous) đề cập đến
tập hợp các kiểu media được sử dụng chung, trong đó ít nhất có một kiểu media
không phải là văn bản (nói cách khác là ít nhất có một media trong đó là ảnh, audio
hay video). Khái niệm multimedia hiểu theo nghĩa tính từ: thông tin đa phương tiện,
dữ liệu đa phương tiện, hệ thống đa phương tiện, truyền thông đa phương tiện, ứng
dụng đa phương tiện Khái niệm dữ liệu đa phương tiện đề cập đến sự biểu diễn
các kiểu media khác nhau mà máy tính có thể đọc được. Thông tin đa phương tiện
đề cập đến thông tin được truyền đạt bởi các kiểu media. Đôi khi khái niệm dữ liệu
đa phương tiện và thông tin đa phương tiện được sử dụng thay thế cho nhau.
1.2.4. CSDL và Hệ quản trị CSDL
Trong nhiều tài liệu thì hai khái niệm CSDL và hệ quản trị CSDL hay được
sử dụng thay cho nhau. Ở đây ta sử dụng hai thuật ngữ này như sau:
• Cơ sở dữ liệu - Database: Tập hợp bản ghi data hay các mục media.
• Hệ quản trị cơ sở dữ liệu - DBMS: Toàn bộ hệ thống quản trị Database
1.2.5. Truy tìm thông tin tài liệu văn bản
Các hệ thống tự động truy tìm thông tin (IR - Information Retrieval) đã được
phát triển để quản lý khối lượng lớn tài liệu khoa học từ những năm 40 của thế kỷ
XX. Chức năng chính của hệ thống IR là lưu trữ và quản trị khối lượng văn bản lớn
theo cách sao cho dễ dàng truy vấn ( query) tài liệu mà người sử dụng quan tâ m.
Chú ý rằng đồng nghĩa với IR là text IR dù rằng ý nghĩa đầy đủ của khái niệm IR là
đề cập đến truy tìm bất kỳ loại thông tin nào.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
1.2.6. Chỉ mục và truy tìm đa phương tiện
DBMS truy tìm thông tin trên cơ sở dữ liệu có cấu trúc nhờ đối sánh chính
xác (exact matching). IR còn được gọi là truy tìm trên cơ sở văn bản.
Truy tìm theo nội dung: Đề cập đến truy tìm trên cơ sở các đặc trưng media
như màu, hình dạng thay cho mô tả văn bản các media item. Thông thường truy tìm
này dựa trên tính tương tự thay cho đối sánh chính xác giữa truy vấn và tập các
items trong CSDL.
MIRS: Đề cập đến hệ thống cơ sở, cung cấp khả năng truy tìm thông tin đa
phương tiện nhờ tổ hợp các kỹ thuật DBMS, IR và truy tìm trên cơ sở nội dung.
Trong MIRS một số nhiệm vụ như versioning và security control không được cài
đặt đầy đủ.
Một hệ thống MIRS đầy đủ được gọi là Hệ quản trị CSDL đa phương tiện
(MMDBMS – Multimedia DBMS).
1.2.7. Trích chọn đặc trưng, Biểu diễn nội dung và Xây dựng chỉ mục
Một trong những nhiệm vụ quan trọng của MIRS là trích chọn đặc trưng hay
biểu diễn nội dung. Trích chọn đặc trưng là tiến trình tự động hay bán tự động.
Trong một số tài liệu còn gọi tiến trình trích chọn đặc trưng là làm chỉ mục (chỉ số
hóa).
Ta qui định sử dụng thuật ngữ “index” (chỉ mục) là danh từ, đề cập đến cấu
trúc dữ liệu hay đề cập đến tổ chức các đặc trưng đã trích chọn để tìm kiếm hiệu
quả.
1.3. SỰ CẦN THIẾT PHẢI CÓ MIRS
Ngày càng nhiều dữ liệu đa phương tiện được thu thập và lưu trữ, đòi hỏi hệ
thống truy tìm và chỉ số hóa đủ tốt để sử dụng dữ liệu hiệu quả.
Dữ liệu đa phương tiện có tính chất và yêu cầu đặc biệt, khác xa với loại dữ
liệu chữ và số. CSDL truyền thống không phù hợp trong việc quản lý dữ liệu đa
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
phương tiện.
Các kỹ thuật truy tìm thông tin có thể giúp truy tìm các đối tượng đa phương
tiện nhưng chúng chưa có khả năng quản lý hiệu quả dữ liệu đa phương tiện.
1.3.1. Mô tả sơ lược dữ liệu MM và các tính chất của chúng
Chúng ta đang đối mặt với sự bùng nổ thông tin đa phương tiện. Thí dụ tồn tại
một số lượng lớn ảnh và video trên Internet. Rất nhiều tranh vẽ, ảnh chụp đang được
chuyển sang dạng số để dễ xử lý và phân tán hay bảo quản. Các bức ảnh từ bản tin TV
và trên báo c ũng đang được chuyển sang dạng số để dễ dàng quản lý. Lượng lớn ảnh y
tế, ảnh vệ tinh đang được thu thập hàng ngày. Xu thế này đã thúc đẩy phát triển công
nghệ số lưu trữ và trình diễn. Không thể sử dụng nhanh và hiệu quả các thông tin đa
phương ti ện này nếu chúng không được tổ chức tốt để có khả năng truy tìm nhanh.
Không chỉ khối lượng dữ liệu đa phương tiện lưu trữ tăng nhanh mà các kiểu
dữ liệu và đặc tính của chúng khác xa dữ liệu chữ và số. Sau đây là một vài tính
chất chính của dữ liệu đa phương tiện:
• Khối lượng khổng lồ (đặc biệt với dữ liệu audio và video). Thí dụ 10 phút
video không nén có dung lượng 1,5 GB.
• Audio và video có thêm chiều thời gian.
• Dữ liệu ảnh, audio và video được thể hiện bởi dãy các giá trị mẫu, không có
cấu trúc nhất định để máy tính tự động nhận biết.
• Rất nhiều ứng dụng đa phương tiện đòi hỏi trình diễn đồng thời các loại
media khác nhau. Thí dụ, phim bao gồm các ảnh đồng bộ với âm thanh.
• Ý nghĩa của dữ liệu đa phương tiện đôi khi rất mờ.
• Dữ liệu đa phương tiện rất giàu thông tin. Đòi hỏi nhiều tham số để biểu diễn
nội dung của chúng.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
1.3.2. Hệ thống IR và vai trò của chúng trong truy tìm đa phương tiện
Bổ sung vào DBMS còn có kiểu hệ thống quản trị thông tin khác mà nó tập
trung vào truy tìm tài liệu văn bản. Kiểu hệ thống thông tin này được gọi là hệ
thống truy tìm thông tin. Kỹ thuật IR rất quan trọng trong hệ thống quản trị thông
tin đa phương tiện vì hai lý do chính sau. Thứ nhất, khối lượng văn bản rất lớn đang
có sẵn trong các cơ quan như thư viện. Văn bản là nguồn thông tin quan trọng của
mọi tổ chức. Để sử dụng hiệu quả thông tin trong các tài liệu này cần có hệ thống IR
hiệu quả. Thứ hai, văn bản còn được sử dụng để mô tả các loại media khác như
audio, ảnh và video. Các kỹ thuật IR quen thuộc có thể được sử dụng để truy tìm
thông tin đa phương tiện. Tuy nhiên việc sử dụng IR để quản lý dữ liệu đa phương
tiện có các hạn chế sau:
• Mô tả thường là tiến trình thủ công và tốn kém thời gian.
• Mô tả bằng văn bản không đầy đủ và chủ quan.
• Kỹ thuật IR không áp dụng được cho truy vấn các loại dữ liệu khác văn bản.
• Một vài đặc trưng như kết cấu ảnh (image texture) và hình dạng ảnh rất
khó mô tả bằng văn bản.
1.3.3. Tích hợp truy tìm và chỉ số hóa thông tin đa phương tiện
DBMS và IR đề cập trên đây không đáp ứng đầy đủ yêu cầu truy tìm và chỉ
số hóa đa phương tiện, do vậy, đòi hỏi kỹ thuật mới để quản lý các tính chất đặc biệt
của dữ liệu đa phương tiện. Tuy nhiên ta nhận ra rằng DBMS và IR có thể đóng vai
trò quan trọng trong MMDBMS.
Nhiều phần dữ liệu đa phương tiện như ngày tạo lập, tác giả, v.v là có cấu
trúc. Chúng có thể được quản lý bằng các kỹ thuật DBMS. Mô tả (annotation) bằng
văn bản vẫn còn là phương pháp hiệu quả để thu thập nội dung dữ liệu đa phương
tiện, do vậy các kỹ thuật IR vẫn đóng vai trò quan trọng.
Tóm lại, cần phải tích hợp DBMS, IR và các kỹ thuật đặc biệt khác quản lý
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
dữ liệu đa phương tiện để phát triển MIRS phù hợp và hiệu quả.
1.4. KHÁI QUÁT VỀ MIRS
Các thao tác MIRS được mô tả trên hình 1. 2. Dữ liệu (các mục thông tin)
trong CSDL được tiền xử lý để trích chọn đặc trưng và nội dung ngữ nghĩa. Sau đó
chúng được chỉ số hóa trên cơ sở đặc trưng và ngữ nghĩa.
Trong khi truy tìm thông tin, câu truy vấn của người sử dụng được xử lý và
các đặc trưng chính của nó được trích chọn. Các đặc trưng này sau đó được so sánh
với các đặc trưng hay chỉ mục của mỗi mục thông tin trong CSDL. Các mục thông
tin nào có đặc trưng gần giống nhất với các đặc trưng của câu truy vấn thì được tìm
ra và trình diễn cho người sử dụng.
Mẫu truy vấn có thể mô tả như sau:
Chỉ mục:
Ảnh (I) > véctơ đặc trưng f(I): (f
1
, f
2
, f
k
)
Truy vấn:
Véctơ truy vấn q: (q
1
, q
2
, q
k
)
Tính tương tự:
Đo khoảng cách: d(f,q)
Kết quả:
Không có nhận xét nào:
Đăng nhận xét