Khóa luận Một số thuật toán phân hạng ảnh phổ biến và áp dụng trong hệ thống tìm kiếm ảnh lớp trên thử nghiệm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thị Kim Dung MỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ BIẾN VÀ ÁP DỤNG TRONG HỆ THỐNG TÌM KIẾM ẢNH LỚP TRÊN THỬ NGHIỆM KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thị Kim Dung MỘT SỐ THUẬT TOÁN PHÂN HẠNG ẢNH PHỔ BIẾN VÀ ÁP DỤNG TRONG HỆ THỐNG TÌM KIẾM ẢNH LỚP TRÊN THỬ NGHIỆM KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: PGS.TS Hà Quang Thụy Cán bộ đồng hướng dẫn: ThS Nguyễn Cẩm Tú HÀ NỘI - 2010 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy và Thạc sĩ Nguyễn Cẩm Tú, người đã tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp. Tôi chân thành cảm ơn các thầy, cô đã tạo những điều kiện thuận lợi cho tôi học tập và nghiên cứu tại trường Đại học Công nghệ. Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong nhóm “Khai phá dữ liệu” đã giúp tôi rất nhiều trong việc hỗ trợ kiến thức chuyên môn để hoàn thành tốt khoá luận. Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn! Sinh viên Lê Thị Kim Dung Tóm tắt Sự tăng không ngừng về lượng ảnh trên Web tạo nguồn ảnh phong phú đáp ứng được nguồn cung ảnh cho nhu cầu của con người. Mặc dù một số máy tìm kiếm ảnh đã ra đời đáp ứng phần nào nhu cầu tìm kiếm ảnh, song nâng cao chất lượng tìm kiếm luôn là vấn đề được đặt ra. Bài toán xếp hạng ảnh là bài toán cốt lõi của các máy tìm kiếm ảnh, và nâng cao chất lượng xếp hạng ảnh đã và đang nhận được sự quan tâm đặc biệt. Đầu tiên, khóa luận khảo sát các thuật toán tính hạng ảnh, đặc biệt là VisualRank [39] theo độ đo tương đồng giữa các ảnh được tính theo các đặc trưng nội dung văn bản và nội dung hiển thị. Sau đó, khóa luận đề xuất một mô hình hệ thống tìm kiếm ảnh lớp trên (image meta-search engine [18] [11]), trong đó sử dụng thuật toán nói trên làm thành phần xếp hạng ảnh. Hệ thống tìm kiếm ảnh này sử dụng một cơ sở dữ liệu lưu trữ các câu truy vấn và các ảnh tương ứng với chúng như một giải pháp nhằm rút ngắn thời gian đáp ứng yêu cầu truy vấn. Đồng thời, hệ thống sử dụng một bộ từ điển dùng trong việc hỗ trợ các truy vấn dạng tiếng Việt. Thực nghiệm do khóa luận tiến hành bước đầu đã thu được những kết quả tương đối khả quan, độ chính xác của hệ thống khi áp dụng thuật toán với đặc trưng văn bản và đặc trưng hiển thị đạt 81.2%. Trong phạm vi các thử nghiệm của khóa luận, kết quả này là tốt hơn so với hai máy tìm kiếm ảnh lớn là Google và Yahoo và đã khẳng định được tính khả thi của mô hình. Mục lục Mở đầu ............................................................................................................................ 1  Chương 1. Khái quát về các thuật toán tính hạng ..................................................... 3  1.1.  Giới thiệu về bài toán tính hạng ......................................................................... 3  1.2.  Tính hạng trang Web ......................................................................................... 4  1.2.1.  Tính hạng theo liên kết ................................................................................ 4  1.2.2.  Tính hạng định hướng ngữ cảnh ............................................................... 15  1.3.  Tính hạng thực thể ........................................................................................... 17  1.4.  Sơ bộ về tính hạng ảnh ..................................................................................... 18  1.5.  Một số công trình nghiên cứu liên quan .......................................................... 20  Tóm tắt chương một..................................................................................................... 22  Chương 2. Một số thuật toán tính hạng ảnh phổ biến ............................................. 23  2.1.  Giới thiệu ......................................................................................................... 23  2.2.  VisualRank ....................................................................................................... 23  2.3.  Multiclass VisualRank ..................................................................................... 26  2.4.  Visual contextRank .......................................................................................... 28  2.5.  Nhận xét ........................................................................................................... 32  Tóm tắt chương hai ...................................................................................................... 32  Chương 3. Mô hình máy tìm kiếm ảnh lớp trên ....................................................... 34  3.1.  Kiến trúc chung của máy tìm kiếm lớp trên .................................................... 34  3.1.1.  Giao diện người dùng ................................................................................ 35  3.1.2.  Bộ điều vận ............................................................................................... 35  3.1.3.  Bộ xử lý kết quả ........................................................................................ 36  3.1.4.  Mô đun tính hạng ...................................................................................... 36  3.2.  Mô hình máy tìm kiếm ảnh lớp trên MetaSEEk .............................................. 37  3.2.1.  Truy vấn trực quan dựa trên nội dung ....................................................... 38  3.2.2.  Giao diện truy vấn ..................................................................................... 38  3.2.3.  Bộ điều vận ............................................................................................... 40  3.2.4.  Thành phần hiển thị ................................................................................... 42  3.2.5.  Đánh giá .................................................................................................... 43  3.3.  Xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên .............................................. 43  Tóm tắt chương ba ....................................................................................................... 45  Chương 4. Thử nghiệm ............................................................................................... 46  4.1.  Mô hình thử nghiệm ......................................................................................... 46  4.1.1.  Cách tiếp cận ............................................................................................. 46  4.1.2.  Mô hình đề xuất và các thành phần trong mô hình ................................... 47  4.2.  Môi trường và các thành phần trong hệ thống phần mềm ............................... 50  4.2.1.  Cấu hình phần cứng................................................................................... 50  4.2.2.  Các thành phần trong hệ thống phần mềm ................................................ 50  4.3.  Xây dựng tập dữ liệu ........................................................................................ 52  4.3.1.  Tập truy vấn .............................................................................................. 52  4.3.2.  Tập máy tìm kiếm nguồn .......................................................................... 53  4.3.3.  Từ điển ...................................................................................................... 53  4.4.  Quy trình, các phương án thử nghiệm ............................................................. 53  4.5.  Kết quả thử nghiệm và đánh giá ...................................................................... 54  Kết luận ........................................................................................................................ 60  Tài liệu tham khảo ....................................................................................................... 62  Danh sách các bảng Bảng 1. Ví dụ về bản ghi của một ảnh trong cơ sở dữ liệu ........................................... 42  Bảng 2. Cấu hình phần cứng sử dụng trong thực nghiệm ............................................. 50  Bảng 3. Một số phần mềm sử dụng ............................................................................... 50  Bảng 4. Một số thư viện sử dụng ................................................................................... 50  Bảng 5. Độ chính xác trung bình trên 35 truy vấn ........................................................ 56  Danh sách hình vẽ Hình 1. Mô tả tính chất authority và hub....................................................................... 13  Hình 2. Mở rộng tập cơ sở T từ tập nhân S ................................................................... 14  Hình 3. Một mô hình học xếp hạng trong máy tìm kiếm thực thể ................................ 18  Hình 4. Một minh họa về đồ thị độ tương đồng của ảnh ............................................... 24  Hình 5. Biến đổi ma trận kề ........................................................................................... 27  Hình 6. Kết quả xếp hạng của 3 phương pháp với truy vấn “Notre Dame”.................. 28  Hình 7. Mô hình xếp hạng ảnh sử dụng thuật toán ContextRank ................................. 29  Hình 8. Một ví dụ về biểu diễn visual words ................................................................ 32  Hình 9. Kiến trúc của một máy tìm kiếm lớp trên điển hình ........................................ 34  Hình 10. Một thiết kế của bộ điều vận ......................................................................... 35  Hình 11. Kiến trúc tổng thể của MetaSEEk ................................................................. 37  Hình 12. Giao diện hiển thị của MetaSEEk .................................................................. 39  Hình 13. Cấu trúc phân cấp của cơ sở dữ liệu ............................................................... 42  Hình 14. Mô hình đề xuất .............................................................................................. 48  Hình 15. Giao diện của chương trình ............................................................................ 52  Hình 16. Biểu đồ so sánh độ chính xác trung bình giữa các hệ thống .......................... 57  Hình 17. Biểu đồ độ chính xác mức K của một số truy vấn tiếng Việt ......................... 58  Hình 18. 10 kết quả đầu tiên của truy vấn “sun” trong các máy tìm kiếm .................... 59  Danh sách các từ viết tắt CSDL Cơ sở dữ liệu AP Average Precision Google CSE Google Custom Search Engine HIST Hypertext Induced Topic Search MAP Mean Average Precision SIFT Scale Invariant Feature Transform Danh sách các thuật ngữ STT Thuật ngữ tiếng Anh Nghĩa tiếng Việt 1 Content-based Image Ranking Xếp hạng ảnh dựa trên nội dung hiển thị 2 Content-based visual query Truy vấn trực quan dựa trên nội dung hiển thị 3 Display interface Thành phần hiển thị 4 Edge Cạnh 5 Image tag Thẻ ảnh 6 Inter-image Context Modeling Mô hình ngữ cảnh ngoại ảnh 7 Intra-mage Context Modeling Mô hình ngữ cảnh nội ảnh 8 Local features Các thuộc tính cục bộ 9 Offline Ngoại tuyến 10 Online Trực tuyến 11 Performance database Cơ sở dữ liệu hiệu suất 12 Performance score Điểm số hiệu suất 13 Query dispatcher Bộ điều vận truy vấn 14 Query translator Bộ dịch truy vấn 15 Random surfer model Mô hình duyệt ngẫu nhiên 16 Re-rank Xếp hạng lại 17 Scoring module Mô đun tính hạng 18 Text-based Image Ranking Xếp hạng ảnh dựa trên văn bản 19 Texture Kết cấu 20 Title Tiêu đề 21 Topic Sensitive PageRank PageRank theo chủ đề 22 Visual hyperlink Siêu liên kết trực quan 23 Visual vocabulary Tập từ vựng trực quan 1 Mở đầu Tính hạng các đối tượng trên Web (trang Web, thực thể... nói chung và tính hạng ảnh nói riêng) là bài toán có ý nghĩa quan trọng trong lĩnh vực tìm kiếm. Sự hình thành và phát triển không ngừng của máy tìm kiếm gần hai thập kỷ qua đã kéo theo một số lượng không nhỏ các công trình nghiên cứu về tính hạng trang Web được công bố, trong đó thuật toán PageRank đã trở thành một trong mười thuật toán khai phá dữ liệu điển hình nhất. Thời gian gần đây, các công bố công trình nghiên cứu về tính hạng thực thể cũng như tính hạng ảnh có xu thế tăng nhanh. Thuật toán tính hạng ảnh thường được phát triển trên cơ sở các thuật toán tính hạng trang Web, bao gồm cả các giải pháp hướng ngữ cảnh, hướng người dùng hoặc chỉ dựa trên đồ thị liên kết. Chúng tôi cũng đã tiến hành một số nghiên cứu liên quan trong công trình nghiên cứu khoa học sinh viên. Khóa luận tốt nghiệp với đề tài Một số thuật toán phân hạng ảnh phổ biến và áp dụng trong hệ thống tìm kiếm ảnh lớp trên thử nghiệm nhằm khảo sát, phân tích các giải pháp phân hạng ảnh, đồng thời trình bày một mô hình máy tìm kiếm ảnh lớp trên và thi hành giải pháp phân hạng ảnh trong máy tìm kiếm ảnh lớp trên thử nghiệm. Khóa luận gồm những nội dung chính cơ bản như sau: Chương 1: Khái quát về các thuật toán tính hạng trình bày một số thuật toán tính hạng trang điển hình đã và đang được sử dụng rộng rãi trong các máy tìm kiếm. Cùng với đó, chương này cũng nêu lên một số nét cơ bản về bài toán xếp hạng thực thể và xếp hạng ảnh. Đồng thời, chương 1 cũng đề cập đến một số công trình nghiên cứu liên quan ở trong nước và trên thế giới. Chương 2: Giới thiệu một số thuật toán tính hạng ảnh phổ biến tập trung trình bày một số thuật toán tính hạng ảnh dựa trên nội dung hiển thị của ảnh. Mỗi thuật toán đều được phân tích, đánh giá, đưa ra các ưu nhược điểm. Từ đó, khóa luận đề xuất thuật toán tính hạng ảnh áp dụng VisualRank cho các đặc trưng hiển thị và đặc trưng văn bản của ảnh. Chương 3: Mô hình máy tìm kiếm ảnh lớp trên trình bày mô hình tổng quan của một máy tìm kiếm lớp trên. Đồng thời, chương 3 đi chi tiết vào một mô hình tìm kiếm ảnh lớp trên MetaSEEk để tìm hiểu các thành phần cần thiết trong hệ thống máy tìm kiếm ảnh 2 lớp trên. Từ đó, định hình ra những thành phần cần phải xây dựng mô hình máy tìm kiếm ảnh lớp trên định xây dựng. Chương 4: Thực nghiệm đưa ra mô hình máy tìm kiếm ảnh lớp trên áp dụng thử nghiệm thuật toán đã được đề xuất ở chương 2. Chương này trình bày các thành phần của mô hình và các công việc thực nghiệm mà khóa luận đã tiến hành. Từ những kết quả đạt được, tiến hành đánh giá, so sánh với các hệ thống khác. Phần kết luận tóm lược các kết quả đã đạt được và nêu rõ đóng góp của khóa luận, đồng thời định hướng một số hướng nghiên cứu tiếp theo trong thời gian sắp tới. 3 Chương 1. Khái quát về các thuật toán tính hạng Xếp hạng là một bài toán phổ biến, có ý nghĩa quan trọng và có nhiều ứng dụng trong thực tế. Chương này tập trung làm rõ khái niệm về bài toán tính hạng tổng quát, đồng thời trình bày một số thuật toán tính hạng trang điển hình và giới thiệu sơ bộ về bài toán tính hạng ảnh. 1.1. Giới thiệu về bài toán tính hạng Xếp hạng các đối tượng theo tiêu chí nào đó (đơn giản như xếp hạng các học sinh trong một lớp theo điểm trung bình, xếp hạng các trường đại học…) là công việc hết sức cần thiết trong nhiều ứng dụng, đặc biệt là việc xếp hạng các kết quả trả về của máy tìm kiếm. Xếp hạng các đối tượng là sắp xếp các đối tượng theo độ phù hợp với tiêu chí tùy vào từng ứng dụng cụ thể. Do đó cần phải xác định phép đo về độ phù hợp của một đối tượng tìm được với yêu cầu của người dùng theo các tiêu chí đã đặt ra [1] [2] [3] [4]. Một điển hình của bài toán xếp hạng đối tượng là việc xếp hạng các đối tượng trả về của máy tìm kiếm. Trong các máy tìm kiếm thông thường (như Google, Yahoo) độ quan trọng hay còn gọi hạng trang (PageRank) là đại lượng cơ sở để xếp hạng. Giá trị cơ sở của hạng trang được tính toán dựa trên việc phân tích mối liên kết giữa các trang Web. Xếp hạng là công việc cuối cùng trong một máy tìm kiếm nhưng cũng không kém phần quan trọng. Với tập các tài liệu ܦ ൌ ݀ଵ,…݀௡ và truy vấn ݍ của người dùng, máy tìm kiếm cần tìm những tài liệu trong ܦ phù hợp với ݍ. Quá trình xếp hạng là quá trình sắp xếp các tài liệu mà máy tìm kiếm đã tìm được theo độ phù hợp với truy vấn và độ quan trọng giảm dần. Việc xác định hàm tính hạng đóng vai trò quan trọng và quyết định đối với chất lượng của máy tìm kiếm. Liên quan tới việc xác định hàm tính hạng, người ta quan tâm tới hai hướng giải quyết: • Hướng thứ nhất sử dụng hạng trang của trang Web làm độ phù hợp với yêu cầu người dùng. Hầu hết các nghiên cứu đều thừa nhận một giả thiết là nếu một trang Web mà có nhiều trang Web khác liên kết tới thì trang Web đó là trang Web quan trọng. Trong trường hợp này, hạng trang được tính toán chỉ dựa trên mối liên kết giữa các trang Web với nhau. Một số thuật toán điển hình theo hướng này là PageRank, Modified Adaptive PageRank. • Hướng thứ hai coi độ phù hợp của trang Web với câu truy vấn của người dùng không chỉ dựa trên giá trị hạng trang Web mà còn phải tính đến mối liên quan 4 giữa nội dung trang Web đó với nội dung truy vấn theo yêu cầu của người dùng. Khi đó, hàm tính hạng là hàm kết hợp của giá trị độ tương tự giữa tài liệu với truy vấn ݏ݈݅݉݅ܽݎ݅ݐݕሺݍ, ݀௜ሻ và hạng trang. Các thuật toán xếp hạng theo hướng này được gọi là các thuật toán xếp hạng định hướng ngữ cảnh. Một thuật toán xếp hạng định hướng ngữ cảnh điển hình là PageRank theo chủ đề (Topic Sensitive PageRank). Với các ứng dụng mà kết quả trả về là một danh sách các đối tượng cần được sắp xếp, xếp hạng giúp người dùng nhanh chóng tiếp cận với kết quả gần với yêu cầu của mình nhất có thể. Điều đó cho thấy, xếp hạng là một bài toán quan trọng và có ý nghĩa. Sau đây, chúng ta sẽ nghiên cứu một số phương pháp tính hạng trang Web, các phương pháp này hoặc là phương pháp cơ bản đầu tiên, hoặc là đang được áp dụng trên một số máy tìm kiếm điển hình trên Internet như Google, Yahoo! 1.2. Tính hạng trang Web Như đã nói ở trên, liên quan tới vấn đề xác định độ đo quan trọng của một trang Web với yêu cầu người dùng người ta quan tâm tới hai hướng giải quyết: hướng giải quyết thứ nhất không quan tâm tới vai trò của câu hỏi trong xếp hạng, ngược lại hướng giải quyết thứ hai liên quan trực tiếp với câu hỏi của người dùng. Tương ứng với hai hướng giải quyết trên là các thuật toán xếp hạng dựa theo liên kết giữa các trang Web và các thuật toán xếp hạng định hướng ngữ cảnh. Phần này sẽ trình bày một số thuật toán điển hình của cả hai hướng trên. 1.2.1. Tính hạng theo liên kết 1.2.1.1. PageRank PageRank [30] là một thuật toán phân tích liên kết (link) được Lary Page và cộng sự phát triển tại trường đại học Stanford (Mỹ) và được sử dụng cho máy tìm kiếm Google. Một cách trực giác, chúng ta có thể thấy rằng trang chủ của Yahoo! thì quan trọng hơn trang chủ của một cá nhân A nào đó. Điều này được phản ánh qua số lượng các trang có liên kết đến trang chủ của Yahoo! nhiều hơn số trang có liên kết tới trang chủ của cá nhân A. Do đó, ta có thể dùng số lượng các liên kết đến một trang để tính độ quan trọng của trang đó. Tuy nhiên, cách này sẽ không hoạt động tốt khi người ta có thể dễ dàng tạo ra các trang Web có liên kết đến một trang Web nào đó và như vậy hạng của trang này sẽ trở nên cao hơn. PageRank phát triển thêm vào ý tưởng cũ bằng cách chú ý đến độ quan trọng của các trang Web liên kết đến trang Web mà ta đang xét. Phương pháp này thừa nhận nếu 5 có liên kết từ trang A tới trang B thì độ quan trọng của trang A cũng ảnh hưởng (được san sẻ) tới độ quan trọng của trang B. PageRank đơn giản Gọi ܩ là một đồ thị các trang Web. Đặt ܩ ൌ ሺܸ, ܧሻ với ܸ ൌ ሼ1, 2, … ݊ሽ là tập n đỉnh của đồ thị ܩ (mỗi đỉnh là một trang Web cần tính hạng trang) còn ܧ là tập các cạnh, E = {(i, j) / nếu có siêu liên kết từ trang i tới trang j}. Chúng ta giả thiết rằng đồ thị trang Web là liên thông, nghĩa là từ một trang bất kì có thể có đường liên kết tới một trang Web khác trong đồ thị đó. Cho một đồ thị trang Web ܩ như trên. Với mỗi trang Web ݅, ký hiệu ܰሺ݅ሻ là số liên kết đi ra từ trang Web thứ ݅ và ܤሺ݅ሻ là số các trang Web có liên kết đến trang ݅. Khi đó hạng trang ݎሺ݅ሻ của trang Web ݅ được định nghĩa như sau: ݎሺ݅ሻ ൌ ෍ ݎሺ݆ሻ ܰሺ݆ሻ ௝א஻ሺ௜ሻ ሺ1.1ሻ Việc ta chia cho ܰሺ݆ሻ cho thấy rằng những trang có liên kết tới trang ݅ sẽ phân phối hạng của chúng cho các trang Web mà chúng liên kết tới. Các phương trình này được viết lại dưới dạng ma trận ݎ ൌ ݎܲ trong đó: ƒ ݎ ൌ ሾݎଵ, ݎଶ, … , ݎ௡ሿ là vector PageRank, với ݎ௜ là hạng của trang Web ݅ trong đồ thị trang Web. ƒ ܲ là ma trận chuyển ݊ ൈ ݊ với giá trị các phần tử được xác định: ܽ௜௝ ൌ ൜ 1/ ௜ܰ ݊ếݑ ܿó ݈݅ê݊ ݇ếݐ ݐừ ݅ đế݊ ݆ 0 ݊݃ượܿ ݈ạ݅ Từ đó công thức PageRank được viết lại: ݎ ൌ ݎܲ ሺ1.2ሻ Phương trình trên cho thấy vector PageRank ݎ chính là vector riêng của ma trận chuyển P tương ứng với giá trị riêng ߣ = 1. Trong đại số tuyến tính có một số phương pháp tính vector riêng của ma trận, tuy nhiên do kích thước quá lớn của ma trận đang xét, khi thi hành các tác giả [30] đã sử dụng phương pháp lặp để tính toán vector PageRank Tính toán PageRank Như đã nói ở trên, một trong những cách thức đơn giản nhất để tính vector riêng của ma trận có thể được thực hiện thông qua việc lặp phép nhân một vector bất kỳ với ma trận đã cho đến khi nào vector đó hội tụ. Đầu tiên, chúng ta sẽ gán cho vector PageRank một 6 giá trị khởi tạo bất kỳ. Sau đó, ta thực hiện phép nhân vector này với ma trận đã cho một cách liên tục cho tới khi nó đạt tới điều kiện hội tụ thì dừng lại. Vector thu được chính là vector PageRank cần tính. Quy trình tính toán được diễn tả như sau: 1. ݏ ՚ vector bất kì 2. ݎ ՚ ݏܲ 3. nếu ԡݎ െ ݏԡ ൏ ߝ thì kết thúc(ߝ là số dương rất bé, được gọi là sai số lặp). ݎ là vector PageRank nếu không ݏ ՚ ݎ, quay lại bước 2. Giá trị hội tụ của ma trận đối với vòng lặp tùy thuộc vào “khoảng cách” của hai giá trị riêng có giá trị lớn nhất (nói cách khác là hiệu của hai giá trị riêng lớn nhất). Page và Brin đã khẳng định rằng vòng lặp hội tụ khá nhanh, trong khoảng 100 vòng lặp. Mô hình duyệt ngẫu nhiên Quá trình tính toán PageRank có thể được xem như hành động của một người đang duyệt Web. Ta tưởng tượng rằng có một người dùng duyệt Web bằng cách đi theo các liên kết trên các trang Web mà họ viếng thăm một cách ngẫu nhiên. Cách duyệt ngẫu nhiên này tương đương với việc di chuyển ngẫu nhiên trên một đồ thị có hướng. Nó thể hiện rằng vector PageRank tỉ lệ với phân phối xác suất dừng của một quá trình ngẫu nhiên. PageRank của một trang Web chính là xác suất để một người ngẫu nhiên duyệt trang Web đó. PageRank trong thực tế Trên thực tế có nhiều trang Web không có liên kết đến hoặc không có liên kết ra. Các trang Web này có thể là các trang chỉ chứa một bức ảnh, một file pdf, một bảng dữ liệu … hay có thể là một trang mà các trang liên kết của nó chưa được máy tìm kiếm kéo về. Các trang độc lập như vậy được gọi là các “dangling nodes” [9]. Trong trường hợp đó, khi giải phương trình (1.2) các “dangling nodes” sẽ phải chịu một hạng bằng 0, và ta không thể tính được độ quan trọng của trang Web đó. Điều này là không phù hợp với thực tế, vì bất kỳ trang Web nào được xây dựng cũng mang một ngữ nghĩa nào đó, tức là có độ quan trọng dương. 7 Vì đồ thị Web trên thực tế là không liên thông nên trong ma trận P vẫn tồn tại hàng chỉ toàn số 0, do đó không tồn tại một phân phối xác suất dừng ổn định của P hay chính là vector hạng trang. Page và cộng sự [30] đề xuất xử lý các vấn đề này bằng cách thay thế các hàng chỉ toàn số 0 trong P bởi một vector xác định xác suất phân phối ݒ, với ݒ௜ là xác suất trang Web i được gọi đến ở lần duyệt đầu tiên. Khi không xét đến ngữ cảnh, ݒ có thể được chọn giá trị ݒ ൌ ቂଵ ௡ ቃ ௡ൈଵ . Gọi a là vector ݊ ൈ 1 với: ܽ௜ ൌ ൜ 1 ݊êሖ ݑ ܰሺ݅ሻ ൌ 0 0 ݊݃ươҽ ݈ܿܽҽ݅ Ma trận P được biến đổi thành ma trận ܲᇱ: ܲᇱ ൌ ܲ ൅ ܽݒ ሺ1.3ሻ Để đảm bảo phân phối dừng ổn định (duy nhất), công thức tính PageRank được điều chỉnh bằng việc thêm vào một hệ số hãm ݀ cho phù hợp, ݀ sẽ nhận giá trị trong khoảng [0,1]. Với định nghĩa mới này, chỉ một phần nhỏ là ݀ trong giá trị hạng của trang Web được phân phối giữa các nút có liên kết tới nó. Giá trị còn lại trong hạng trang sẽ được phân bố đều giữa các trang trên Web. Công thức PageRank được sửa đổi có dạng: ݎሺ݅ሻ ൌ ݀ כ෍ ݎሺ݆ሻ ܰሺ݆ሻ ൅ 1 െ ݀ ݊ ௝ఢ஻೔ ሺ1.4ሻ Ma trận Markov được xác định lại như sau: ܲᇱᇱ ൌ ݀ܲᇱ ൅ ሺ1 െ ݀ሻݒ ሺ1.5ሻ Việc thêm “hệ số hãm” ݀ (theo thực nghiệm thường được chọn ݀ ൌ 0.85) có ý nghĩa như việc bổ sung thêm giá trị hạng trang cho nhóm các trang không có liên kết ra ngoài. Công thức PageRank nguyên thủy chính là trường hợp đặc biệt của giá trị PageRank vừa nêu khi ݀ ൌ 1. Reodering PageRank Langville và Meyer [9] chỉ ra rằng, việc bỏ đi các “dangling nodes” trong quá trình tính hạng có thể làm cho kết quả tính hạng không còn chính xác nữa. Bởi vì một số “dangling nodes” có thể có PageRank cao. Ví dụ như một file pdf có nội dung tốt có thể có nhiều liên kết trỏ tới từ các nguồn và do đó nó có thể nhận được thứ hạng cao. 8 Langville và Meyer đã đề xuất một giải pháp khác giải pháp của Page và cộng sự [30] để giải quyết vấn đề trên gọi là thuật toán Reodering PageRank [8] [9]. Phương pháp của Langville và Meyer đưa ra là sử dụng một hệ thống tuyến tính trong việc khai thác các “dangling nodes” để giảm sự tính toán, và do đó tạo ra một ma trận có các phần tử được sắp xếp lại một cách thích hợp. Theo [9], vector PageRank được tính theo công thức sau: ݎሺܫ െ ݀ܲሻ ൌ ݒ ሺ1.6ሻ Trong đó I là ma trận đơn vị, ሺܫ െ ݀ܲሻ là một ma trận hệ số, các tính chất của ሺܫ െ ݀ܲሻ được trình bày chi tiết trong [8]. Chúng ta cần chú ý tính chất cuối cùng được phát biểu như sau: - Một hàng của ma trận nghịch đảo ሺܫ െ ݀ܲሻିଵ ứng với “dangling node” i là một vector chuyển vị ݁௜், với ݁௜ là cột thứ i của ma trận đơn vị I. Tính chất này làm cho các tính toán của vector PageRank đặc biệt hiệu quả. Chúng ta giả sử rằng các hàng và cột của ma trận P được biến đổi sao cho các hàng ứng với các “dangling nodes” nằm ở đáy của ma trận. Khi đó ma trận P có dạng: ܲ ൌ ܰܦ ܦ ܰܦ ܦ ቀ ଵܲଵ ଵܲଶ 0 0 ቁ Với ND là tập các nút không phải là “dangling nodes” và D là tập các “dangling nodes”. Từ đó, vector hạng trang PageRank có thể được tính bởi công thức: ݎ ൌ ሺݒଵሺܫ െ ݀ ଵܲଵሻିଵ |݀ݒଵሺܫ െ ݀ ଵܲଵሻିଵ ଵܲଶ ൅ ݒଶሻ ሺ1.7ሻ Với vector ݒ được tách thành hai phần: vector “nondangling” ݒଵ và vector “dangling” ݒଶ. Chúng ta tiếp tục thực hiện việc biến đổi để đưa các hàng bằng 0 về đáy của ma trận đối với các ma trận con ଵܲଵ và ଵܲଶ và tiếp tục chia nhỏ các ma trận này giống như đã làm với ma trận P. Việc biến đổi này được thực hiện lặp đi lặp lại đối với các ma trận con nhỏ hơn cho đến khi gặp các ma trận con không có hàng bằng 0. Khi việc biến đổi các ma trận đã kết thúc, vector hạng trang PageRank được tính một cách đệ quy như sau: 1. Tính ݎଵ trong phương trình ݎଵሺܫ െ ݀ ଵܲଵሻ ൌ ݒଵ 2. Tính ݎଶ ൌ ݀ݎଵ ଵܲଶ ൅ ݒଶ. 3. Tính ݎଷ ൌ ݀ݎଵ ଵܲଷ ൅ ݀ݎଶ ଶܲଷ ൅ ݒଷ. ڭ 9 4. Tính ݎ௕ ൌ ݀ݎଵ ଵܲ௕ ൅ ݀ݎଶ ଶܲ௕ ൅ ڮ൅ ݀ݎ௕ିଵ ௕ܲିଵ,௕ ൅ ݒ௕. 5. Tổng hợp ݎ ൌ ሾݎଵݎଶ … ݎ௕ሿ ԡݎଵݎଶ … ݎ௕ԡଵ⁄ . Phương pháp sắp xếp lại ma trận PageRank do Langville và Meyer đề xuất sử dụng các phép biến đổi đại số để chia ma trận P thành các ma trận con nhỏ hơn, và sau đó tính vector hạng trang cho từng ma trận con nên có thời gian tính toán khá nhanh, và do đó có thể áp dụng tốt cho một đồ thị Web rất lớn. Qua thực nghiệm cho thấy, phương pháp này có tốc độ hội tụ nhanh hơn hoặc bằng so với tốc độ hội tụ của phương pháp PageRank nguyên thủy. Đánh giá PageRank Theo [9] PageRank là một phương pháp tính hạng khá tốt và có quá trình tính toán độc lập với người dùng nên có thể thực hiện độc lập và không ảnh hưởng đến tốc độ tìm kiếm. Phương pháp PageRank được cài đặt trên máy tìm kiếm Google đã mang lại kết quả rất khả quan. Tuy nhiên, vì thuật toán chỉ quan tâm đến các liên kết giữa các trang Web mà không quan tâm đến nội dung trang Web nên có thể dễ bị đánh lừa bởi các công nghệ spam. Do vậy, yêu cầu đặt ra là cần phải cải tiến tốc độ tính toán PageRank và quan tâm hơn nữa tới nội dung của các trang Web đối với truy vấn của người dùng. 1.2.1.2. Modify Adaptive PageRank PageRank là một phương pháp tốt và hiệu quả nhằm đánh giá hạng các trang thông qua việc phân tích các liên kết giữa các trang Web. Việc tính toán giá trị PageRank cho toàn bộ các trang Web được thực hiện thông qua việc tính vector riêng của ma trận kề biểu diễn cho liên kết giữa các trang Web. Tuy nhiên, với kích cỡ khổng lồ của WWW, công việc tính toán này có thể tốn thời gian nhiều ngày. Vì vậy, yêu cầu đặt ra là cần phải tăng tốc độ tính toán hạng trang. Yêu cầu này là vì hai lí do: • Cần sớm có được kết quả tính toán để đưa những thông tin hạng trang sang các thành phần khác của máy tìm kiếm, việc tính toán nhanh vector PageRank có thể giúp tận dụng được thời gian rỗi của những bộ phận đó. • Hiện nay, các phương pháp nghiên cứu mới đều tập trung vào việc đánh giá dựa trên những tiêu chí có tính đến sự quan tâm của người dùng, do vậy cần phải tính toán nhiều vector PageRank, mỗi vector hướng tới một tiêu đề khác nhau. Việc tính toán nhiều vector này cũng đòi hỏi mỗi vector thành phần cần được tính toán nhanh chóng. Một số phương pháp tăng hiệu năng tính toán của thuật toán PageRank đã được đề xuất. Một trong các phương pháp tăng tốc độ tính toán phổ biến hiện nay là Modified 10 Adaptive PageRank đã được giới thiệu bởi Sepandar Kamvar và cộng sự [32]. Ý tưởng của đề xuất này dựa trên nhận xét: trong quá trình chạy chương trình, độ quan trọng các trang Web có tốc độ hội tụ không giống nhau, có những trang Web có tốc độ hội tụ nhanh, có trang lại có tốc độ hội tụ chậm. Vì vậy ta có thể tận dụng những trang hội tụ sớm, và kết quả độ quan trọng của những trang đã hội tụ đó có thể không cần phải tính tiếp nữa. Điều này cho phép giảm được những tính toán dư thừa, và do đó làm tăng được hiệu suất tính toán của hệ thống. Như vậy, phương pháp này thực chất là một cải tiến của phương pháp PageRank, phương pháp này có thể làm tăng tốc độ tính toán bằng cách giảm đi những tính toán dư thừa. Phương pháp Adaptive PageRank Như đã giới thiệu ở trên, việc tính toán vector toàn cục PageRank cho các trang Web được thực hiện bằng phương pháp lặp. Ta giả sử rằng việc tính toán vector PageRank đã được thực hiện đến vòng lặp thứ k và bước tính toán tiếp theo: ݔሺ௞ାଵሻ ൌ ܣݔሺ௞ሻ (1.8) Gọi C là tập hợp các trang Web có giá trị hạng trang đã hội tụ đến mức ߝ nào đó và ܰ là tập hợp các trang Web có giá trị hạng trang chưa hội tụ. Khi đó, ta chia ma trận ܣ ra làm hai ma trận con, ܣே cỡ ݉ ൈ ݊ là ma trận kề đại diện cho những liên kết của m trang chưa hội tụ, còn ܣ஼ cỡ ሺ݊ െ ݉ሻ ൈ ݊ là ma trận kề đại diện cho những liên kết của ሺ݊ െ ݉ሻ trang đã hội tụ. Tương tự, ta cũng chia vector ݔሺ௞ሻ tại vòng lặp thứ k ra thành 2 vector: ܺே ሺ௞ሻ tương ứng với những thành phần của ݔሺ௞ሻ đã hội tụ, còn ܺ஼ ሺ௞ሻ tương ứng với những thành phần của ݔሺ௞ሻ chưa hội tụ. Ma trận ܣ và vector ݔሺ௞ሻ được viết lại dưới dạng sau: ܺሺ௞ሻ ൌ ቆ ܺே ሺ௞ሻ ܺ஼ ሺ௞ሻቇ và ܣ ൌ ൬ ܣே ܣ஼ ൰ Và phương trình (1.8) được viết lại như sau: ቆ ܺே ሺ௞ାଵሻ ܺ஼ ሺ௞ାଵሻቇ ൌ ൬ ܣே ܣ஼ ൰ • ൭ ܺே ሺ௞ሻ ܺ஼ ሺ௞ሻ൱ ሺ1.9ሻ Do những thành phần của ܺ஼ ሺ௞ሻ đã hội tụ, do vậy ta không cần tính ܺ஼ ሺ௞ାଵሻ nữa và như vậy việc tính toán sẽ được giảm đi đáng kể do không phải tính toán ܣ஼ܺሺ௞ሻ nữa mà chỉ cần tính: ܺே ሺ௞ାଵሻ ൌ ܣே • ܺሺ௞ሻ ሺ1.10ሻ ܺ஼ ሺ௞ାଵሻ ൌ ܺ஼ ሺ௞ሻ ሺ1.11ሻ 11 Cải tiến Adaptive PageRank Vì kích thước của WWW rất lớn nên việc sắp xếp lại ma trận A để tạo ma trận con ܣே sẽ khó có thể thực hiện được trong mỗi vòng lặp. Hơn nữa, không có cách hiệu quả để phớt lờ đi những đầu vào không cần thiết (chính là những liên kết tới các trang đã hội tụ), do vậy trong thực tế việc cài đặt thuật toán có thể được thực hiện như sau: Định nghĩa ma trận ܣԢ như sau: ܣԢ ൌ ൜0 ݊ếݑ ݅ א ܥܣ௜௝ ݊݃ượܿ ݈ạ݅ ሺܺԢ஼ ሺ௞ሻሻ௜ ൌ ቊ ௜ܺ ሺ௞ሻ ݊ếݑ ݅ א ܥ 0 ݊݃ượܿ ݈ạ݅ Nghĩa là ta sẽ nhận được ma trận ܣԢ khi thay hàng thứ i của ma trận ܣ bởi 0 nếu ݅ א ܥ. Điều này có ý nghĩa như chúng ta sẽ lọc đi những phần tử của ܣ஼ vì chúng không còn cần thiết cho công việc tính toán nữa. Phương trình (1.8) được viết lại như sau: ܺሺ௞ାଵሻ ൌ ܣԢܺሺ௞ሻ ൅ ܺᇱ஼ ሺ௞ሻ ሺ1.12ሻ Ma trận ܣԢ mà chúng ta nhận được có số chiều giống như ma trận ܣ, tuy nhiên ma trận ܣԢ thưa hơn rất nhiều so với ma trận A (có nhiều phần tử 0 hơn mà công việc tính toán với số 0 rất đơn giản) nên thời gian tính toán sẽ trở nên nhanh hơn so với việc sắp xếp lại ma trận đại diện cho các liên kết giữa các trang Web để được ma trận con ܣே và ܣ஼ Ý tưởng chính của Adaptive PageRank là làm giảm những tính toán dư thừa bằng việc tính toán lại PageRank theo các phương trình (1.10) và (1.11). Tuy nhiên trong [32] đã giới thiệu chi tiết hơn về việc tăng tốc độ tính toán bằng cách chia nhỏ ma trận ܣ thành bốn ma trận con. Ma trận ܣ được viết lại như sau: ܣ ൌ ൬ܣேே ܣே஼ܣ஼ே ܣ஼஼ ൰ ሺ1.13ሻ Với ܣேே là ma trận kề đại diện cho những liên kết của các trang có giá trị PageRank chưa hội tụ tới những trang có giá trị PageRank chưa hội tụ, ܣ஼ே là ma trận kề đại diện cho những liên kết của các trang có giá trị PageRank đã hội tụ tới những trang có giá trị PageRank chưa hội tụ, và tương tự cho các thành phần khác ܣே஼, ܣ஼஼. Vì ܺ஼ và ܣே஼ܺ஼ không thay đổi sau vòng lặp thứ k do chúng đã hội tụ, nên phương trình (1.8) có thể được viết lại như sau: ܺே ሺ௞ାଵሻ ൌ ܣேேܺே ሺ௞ሻ ൅ ܣ஼ேܺ஼ ሺ௞ሻ ሺ1.14ሻ 12 Ma trận ܣ đã được chia nhỏ ra, đồng thời không phải tính lại giá trị một số ma trận con, do vậy công việc tính toán có thể được giảm đi đáng kể. Hơn nữa việc tính toán ܣ஼ே cũng không cần phải tiến hành thường xuyên mà có thể xem xét chúng một cách định kì. Đánh giá Việc chia nhỏ và lọc ma trận ܣ không những giảm đi được những tính toán dư thừa không cần thiết, mà còn giảm đi việc đọc các đầu vào và ghi các giá trị đầu ra không cần thiết, giúp nâng cao hơn hiệu suất tính toán. Hơn nữa phương pháp này còn giúp giảm được chi phí tốn kém về bộ nhớ khi thực hiện công việc tính toán. Những kết quả thực nghiệm trong [32] cho thấy thời gian tính hạng có thể được giảm đi tới hơn 20% so với thuật toán PageRank nguyên thủy. 1.2.1.3. HITS Phương pháp HITS (Hypertext Induced Topic Search), do Kleinberg đề xuất [23], tính hạng của một trang Web không chỉ dựa trên một giá trị độ quan trọng như PageRank mà mỗi trang Web được xác định hai trọng số khác nhau: authority và hub. Authority pages: Là những trang được xem là phù hợp nhất đối với mỗi câu truy vấn cụ thể nào đó. Ví dụ, trang chủ của Yahoo chính là trang “authority” của câu truy vấn “yahoo”. Hub pages: Là những trang không cần có đặc tính “authority” nhưng lại trỏ tới nhiều trang có đặc tính “authority”. Ví dụ như trang “Searchenginewatch.com” là một trang “hub” vì nó liên kết tới nhiều trang chủ của máy tìm kiếm. Trang “hub” có ý nghĩa khá quan trọng, thứ nhất bởi vì nó có những thông tin có thể được sử dụng trong việc tìm kiếm những thông tin hữu ích, thứ hai bởi vì nó được sử dụng trong thuật toán HIST để tính toán “authority”. Vì trang “hub” mang ý nghĩa là trang trỏ tới nhiều trang “authority” nên nếu một trang “authority” tốt có thể được coi là trang có nhiều “hub” chỉ tới. Giải thuật HITS Thuật toán HITS không làm việc trên toàn bộ đồ thị Web mà chỉ làm việc trên một tập nhỏ các trang Web và kết hợp chúng thành một đồ thị các trang Web (gọi là đồ thị con). Thuật toán không hoàn toàn độc lập với người dùng như phương pháp PageRank mà tùy thuộc vào câu truy vấn của người dùng, với mỗi câu truy vấn khác nhau công việc tính toán phải được thực hiện lại. Tuy nhiên, câu truy vấn chỉ có vai trò trong việc tạo đồ thị con chứ không ảnh hưởng tới phương pháp tính toán. Vì vậy, trước tiên phải xây dựng đồ thị con các trang tùy theo truy vấn và sau đó phân tích các 13 liên kết giữa các trang trong đồ thị để xác định các giá trị “authority” và “hub” của các trang. Hình 1. Mô tả tính chất authority và hub Xác định đồ thị con: Đồ thị con các trang Web hay còn gọi là tập cơ sở ܵ có thể được xây dựng theo giải thuật sau: 1. ܴ ՚ tập t trang Web có chứa xâu truy vấn (tập nhân) 2. ܵ ՚ ܴ 3. Với mỗi trang p thuộc R (a) Thêm các trang được liên kết đến bởi p vào S (b) Thêm các trang Web có liên kết đến p vào S (tối đa là d trang) 4. Đồ thị tạo bởi S chính là đồ thị con cần tìm. Việc tìm tập nhân liên quan đến truy vấn có thể xác định dựa vào kết quả tìm kiếm của các máy tìm kiếm khác như Google. Ví dụ, tập nhân có thể được lấy từ các trang đầu tiên, có thể là 10 địa chỉ trang Web đầu tiên được trả về tương ứng với truy vấn. Hoặc là các trang có địa chỉ chứa nội dung truy vấn, ví dụ với truy vấn “java” thì trang chủ là Các trang Web trong đồ thị con ܵ cũng được đánh chỉ số từ 1 đến n và đồ thị được biểu diễn bởi ma trận kề ܣ. 14 Hình 2. Mở rộng tập cơ sở T từ tập nhân S Tính authority và hub: Các trọng số authority ܽ௜ và hub ݄௜ của mỗi trang Web được khởi tạo bằng 1 và sau đó sẽ được tính dựa theo công thức: ܽ௜ ൌ ∑ ௝݄௝א஻ሺ௜ሻ và ݄௜ ൌ ∑ ௝ܽ௝אேሺ௜ሻ (1.15) Gọi ܣ là ma trận kề biểu diễn liên kết giữa các trang Web với: ܽ௜௝ ൌ ൜ 1 ݊ếݑ ܿó ݈݅ê݊ ݇ếݐ ݐừ ݐݎܽ݊݃ ݅ đế݊ ݐݎܽ݊݃ ݆ 0 ݊݃ượܿ ݈ạ݅ Biểu diễn 1.15 theo ma trận ta có: Ԧܽ ൌ ܣ் ሬ݄Ԧ và ሬ݄Ԧ ൌ ܣ Ԧܽ (1.16) Trong đó: Ԧܽ ൌ ሺܽଵ, ܽଶ, … ܽ௡ሻ, ሬ݄Ԧ ൌ ሺ݄ଵ, ݄ଶ, … ݄௡ሻ lần lượt là vector trọng số “authority” và “hub” của các trang trong tập ܵ. Từ 1.16 ta biến đổi được: Ԧܽ ൌ ܣܣ் Ԧܽ và ሬ݄Ԧ ൌ ܣ்ܣሬ݄Ԧ Vậy cũng tương tự như phương pháp PageRank, vector ܽ, ݄ lần lượt là vector riêng của các ma trận ܣܣ் và ܣ்ܣ. Do vậy, tương tự phương pháp tính PageRank, có thể áp dụng tính chất hội tụ để tính vector ܽ, ݄. Vector ܽ, ݄ thường được chuẩn hóa: ∑ ܽ ൌ௜ ∑ ݄ ൌ 1௜ . 15 Kleinberg [23] đã chỉ ra sự hội tụ của các trọng số “authority” và “hub” tức thuật toán thỏa mãn tính dừng nhưng chưa đưa ra được giới hạn số vòng lặp cần tính. Tuy nhiên, thực nghiệm đã cho thấy thuật toán nhanh chóng hội tụ. Đánh giá Theo [9], thuật toán HITS có phần hướng người dùng do sử dụng thông tin truy vấn chắt lọc những trang Web có nội dung liên quan đến xâu truy vấn để xây dựng tập con ܵ các trang Web. Thuật toán đã thể hiện mối quan hệ chặt chẽ giữa các trang mang tính chủ (authority) và trang trung tâm (hub). Tuy nhiên, thuật toán HITS lại gặp phải vấn đề khá khó khăn là cần tính toán trực tuyến (online), nghĩa là chỉ khi máy tìm kiếm nhận được câu truy vấn rồi đồ thị con mới được xây dựng và sau đó các trọng số “authority”, “hub” mới được tính. Điều này làm chậm thời gian trả kết quả về cho người dùng. Nhưng chúng ta có thể ứng dụng thuật toán HITS trong các phương pháp có xác định link spam sau này nhằm tính độ ảnh hưởng của các trang xấu tới các trang khác khi đã xác định được tập nhân các trang xấu. 1.2.2. Tính hạng định hướng ngữ cảnh 1.2.2.1. PageRank theo chủ đề PageRank là phương pháp xếp hạng hiệu quả và hiện đang được áp dụng trên máy tìm kiếm Google. Tuy nhiên, phương pháp này chỉ quan tâm đến các liên kết mà không quan tâm đến nội dung của trang Web có chứa liên kết đó, do vậy có thể dẫn tới những sai lạc trong thông tin tìm kiếm được. Yêu cầu đặt ra là cần phải tìm kiếm một phương pháp có tốc độ nhanh như phương pháp PageRank và lại có quan tâm đến nội dung của trang Web có chứa những liên kết cần thiết. Hơn nữa, nếu khai thác được mối quan tâm của người dùng đối với các trang Web trong việc tính độ phù hợp của trang Web với câu hỏi người dùng thì việc đó càng có ý nghĩa. Nhằm đáp ứng những yêu cầu trên, Taher H. Haveliwala [35] đã đề xuất phương pháp PageRank theo chủ đề (Topic sensitive PageRank) sử dụng khái niệm “phạm vi ngữ cảnh” để biểu thị mối quan tâm của người dùng. Phương pháp nắm được độ quan trọng của các trang Web, cho phép tìm kiếm theo ngữ cảnh, và điều quan trọng là có thể tìm kiếm những trang phù hợp với nội dung truy vấn của người dùng với tốc độ cho phép. Thuật toán gồm hai bước được mô tả sơ bộ như sau. o Bước đầu tiên được thực hiện ngoại tuyến (offline) trong suốt quá trình tiền xử lí của bộ tìm duyệt và hoàn toàn độc lập đối với những truy vấn như phương pháp 16 PageRank thông thường. Tại bước này, các trang Web trong cơ sở dữ liệu được phân thành các lớp theo các chủ đề ܿଵ, ܿଶ, … , ܿ௡; gọi ௝ܶ là tập hợp những trang Web theo chủ đề của ௝ܿ. Mỗi lớp tương ứng với một vector PageRank của mỗi trang trong lớp. Vector PageRank của chủ đề ௝ܿ được tính bằng ݒԦ ൌ ݒఫሬሬሬԦ trong đó ݒ௝௜ ൌ ቐ 1 ห ௝ܶห ݊ếݑ ݅ א ௝ܶ 0 ݊݃ượܿ ݈ạ݅ ሺ1.17ሻ Gọi ܦఫሬሬሬԦ là vector các từ khóa, gồm tất cả các từ khóa trong các tài liệu của các chủ đề; ܦ௝௧ là số lần xuất hiện của từ khóa t trong tất cả các tài liệu của chủ đề ௝ܿ. o Bước thứ hai của thuật toán được thực hiện trong thời gian truy vấn, nghĩa là khi máy tìm kiếm nhận được câu truy vấn của người dùng thì mới thực hiện công việc tính toán độ quan trọng cho các trang. Giả sử chúng ta có truy vấn ݍ, gọi ݍᇱ là phạm vi ngữ cảnh của ݍ. Phạm vi ngữ cảnh nghĩa là nếu truy vấn ݍ được yêu cầu bằng cách tô sáng từ khóa ݍ trong trang Web u nào đó thì ݍᇱ sẽ chứa các từ khóa trong u bao gồm cả ݍ. Với truy vấn bình thường không tìm theo ngữ cảnh thì ݍᇱ ൌ ݍ. Sau đó ta tính xác suất để ݍᇱ thuộc về các chủ đề khác nhau. Bước này có thể coi như là bước phân lớp xem xét ݍᇱ thuộc về lớp nào trong các lớp chủ đề. Sử dụng thuật toán phân lớp Bayes với: ƒ Tập huấn luyện: gồm những trang được liệt kê trong các chủ đề. ƒ Đầu vào: câu truy vấn hoặc phạm vi ngữ cảnh của câu truy vấn. ƒ Đầu ra: xác suất để đầu vào thuộc mỗi chủ đề. Gọi ݍ௜ᇱ là từ khóa thứ i trong ngữ cảnh ݍᇱ. Với mỗi lớp ௝ܿ, xác suất để ݍᇱ א ௝ܿ là: ܲ൫ ௝ܿหݍᇱ൯ ൌ ܲ൫ ௝ܿ൯. ܲሺݍᇱ| ௝ܿሻ ܲሺݍᇱሻ ൎ ܲ൫ ௝ܿ൯.ෑܲ൫ݍ௜ ᇱห ௝ܿ൯ ሺ1.18ሻ ௜ Trong đó ܲ൫ݍ௜ᇱห ௝ܿ൯ được tính từ vector các từ khóa ܦఫሬሬሬԦ được định nghĩa ở trên. Giá trị ܲ൫ ௝ܿ൯ được xác định hoặc là các giá trị bằng nhau cho mọi chủ đề hoặc có thể làm như sau: chúng ta giả sử rằng có k người dùng, ta sẽ biết được số lần mà người dùng này có câu truy vấn liên quan đến chủ đề nào, từ đó có thể tính được ௞ܲሺ ௝ܿሻ; rồi tổ hợp các giá trị này thì nhận được ܲ൫ ௝ܿ൯. Gọi ݎܽ݊ ௝݇ௗ là hạng của văn bản d cho bởi vector ܴܲሺ݀, ݒఫሬሬሬԦሻ – vector PageRank của chủ đề ௝ܿ thì độ quan trọng ܵ௤ௗ dựa theo câu truy vấn được tính như sau: 17 ܵ௤ௗ ൌ෍ܲሺ ௝ܿ|ݍᇱሻ ௝ . ݎܽ݊ ௝݇ௗ ሺ1.19ሻ Phương pháp PageRank theo chủ đề có thể cho những kết quả tính toán chính xác hơn vì nó dựa trên cả những liên kết và nội dung trang Web. Tuy nhiên, phương pháp này cũng gặp phải những trở ngại là: việc phân chia các chủ đề có thể không đầy đủ, không bao hàm được tất cả các chủ đề; vấn đề này có thể giải quyết bằng cách tăng thêm các chủ đề nhưng việc tăng thêm các chủ đề chắc chắn sẽ làm tăng thời gian tính toán... 1.3. Tính hạng thực thể Tìm kiếm thực thể trên Web là một hướng đi mới dựa trên tìm kiếm văn bản thông thường. Cùng với sự phát triển của các kỹ thuật trích rút thông tin, các máy tìm kiếm thực thể ngày càng nhận được nhiều sự quan tâm nghiên cứu của các nhà khoa học. Với máy tìm kiếm thực thể, người dùng có thể dễ dàng tìm được thông tin về một đối tượng nào đó. Ví dụ, đối với truy vấn “các trường đại học ở Việt Nam”, máy tìm kiếm thực thể sẽ trả về danh sách tên các trường đại học ở Việt Nam đúng như mong muốn của người dùng. Trong khi đó, các máy tìm kiếm thông thường sẽ trả về danh sách các trang Web có chứa từ khóa trong truy vấn. Do vậy, người dùng sẽ phải duyệt qua nội dung nhiều trang Web mà không chắc chắn sẽ có được thông tin mong muốn ở những kết quả đầu tiên. Kết quả trả về của máy tìm kiếm thực thể là các thực thể của đối tượng cần tìm, mỗi thực thể được xác định không chỉ xét trên một trang độc lập mà có thể được tổng hợp qua nhiều trang Web. Vì thế, vấn đề đưa các thực thể phù hợp với truy vấn nhất lên đầu tiên trong danh sách trả về cho người dùng là rất quan trọng. Hay nói cách khác, xếp hạng thực thể là vấn đề cốt lõi của máy tìm kiếm thực thể. Bài toán xếp hạng thực thể được phát biểu như sau: Gọi ܧ ൌ ሼ݁ଵ, ݁ଶ, … , ݁௡ሽ là tập các thực thể được trích ra từ các trang Web. Mỗi thực thể ݁௜ được biểu diễn bởi các cặp (,). Định nghĩa ݀ሺ݁௜ሻ ൌ ሼܫܦ௜, ܲ௜ሽ là một mô tả của thực thể ݁௜, trong đó ܫܦ௜ là định danh thực thể: ܫܦ௜ ൌ ݅݀ሺ݁௜ሻ và tập các đặc tính ܲ௜ ൌ ሼሺܽଵ௜ , ݒଵ௜ ሻ… ሺܽ௡௜ , ݒ௩௜ሻሽ là tập các cặp (,). Ví dụ, trường đại học Công Nghệ có ID là DHCN và các đặc tính như là (tên, đại học Công Nghệ), (năm_thành_lập, 2005)… Truy vấn ݍ ൌ ሼሺܽଵ, ݒଵሻ… ሺܽ௡, ݒ௡ሻሽ là một tập các cặp (,) thể hiện yêu cầu của người dùng tìm kiếm các thực thể có các giá trị ứng với các thuộc tính ܽଵ, … , ܽ௡. 18 Với đầu vào là một tập các mô tả thực thể ܦ ൌ ሼ݀ሺ݁ଵሻ…݀ሺ݁௡ሻሽ và một truy vấn q, đầu ra của một hệ thống xếp hạng thực thể là một danh sách các thực thể đã được xếp hạng ܧ ൌ ሼ݁௜ … ݁௝ሽ. Độ phù hợp của thực thể ݁௜ đối với truy vấn q được xác định bởi ݏܿ݋ݎ݅݊݃_݂ݑ݊ܿݐ݅݋݊׎ሺݍ, ݀ሺ݁௜ሻሻ. Giá trị của ׎ሺݍ, ݀ሺ݁௜ሻሻ được dùng để xếp hạng các kết quả trả về, do đó việc xác định hàm ׎ሺݍ, ݀ሺ݁௜ሻሻ là vấn đề quan trọng. Với mỗi bài toán xếp hạng thực thể cho mỗi loại đối tượng sẽ có một số thuật toán xếp hạng thực thể phù hợp với bài toán đó tùy thuộc vào các thuộc tính của đối tượng cần tìm. Hình 3. Một mô hình học xếp hạng trong máy tìm kiếm thực thể [4] 1.4. Sơ bộ về tính hạng ảnh Cùng với sự bùng nổ thông tin trên Web và sự phát triển của công nghệ kỹ thuật số, lượng ảnh lưu trữ trên Web cũng tăng một cách nhanh chóng. Mỗi ngày, có hàng triệu bức ảnh được đăng tải trên các trang ảnh trực tuyến như: Flickr1, Photobucket2, Facebook3…. Theo thống kê, có 10 tỉ ảnh trên Facebook (tính đến tháng 10/2008), 3 tỉ ảnh trên Flickr (tính đến tháng 11/2008), 6.2 tỉ ảnh trên Photobucket (tính đến tháng 10/2008) [19] Bên cạnh nhu cầu tìm kiếm thông tin thì tìm kiếm ảnh cũng là một nhu cầu đang nhận được sự quan tâm lớn của người sử dụng. Tuy nhiên, với một lượng ảnh trên 1 Flickr: 2 Photobucket: 3 Facebook: 19 Internet quá lớn công việc tìm kiếm sẽ trở nên vô cùng khó khăn. Để giải quyết vấn đề này, đã có các hệ thống tìm kiếm ảnh ra đời như: Yahoo, MSN, Google Image Search, Bing…. Cũng như đối với các hệ thống tìm kiếm thông thường và các hệ thống tìm kiếm thực thể khác, mô đun xếp hạng là một phần quan trọng cốt lõi trong máy tìm kiếm ảnh. Hiện nay, bài toán xếp hạng ảnh đã trở thành một trong những bài toán điển hình của lĩnh vực khai phá dữ liệu nói chung và lĩnh vực xếp hạng thực thể nói riêng. Để tìm kiếm và xếp hạng ảnh trên Web, các máy tìm kiếm thường dựa vào các thuộc tính sẵn có của ảnh. Các ảnh trên Web được nhận biết qua các thuộc tính được nhóm thành hai loại: văn bản và nội dung hiển thị. Các thuộc tính văn bản có thể là: tên ảnh, thẻ ảnh (tags1), vùng văn bản xung quanh ảnh, tên trang Web chứa ảnh, …. Nội dung hiển thị của ảnh có thể là: màu sắc, hình dạng, kết cấu, các thuộc tính cục bộ (local features), … hay bất cứ thông tin nào bắt nguồn từ chính nội dung của bức ảnh. Dựa vào hai loại đặc trưng này của các ảnh trên Web, các thuật toán xếp hạng ảnh cũng phân thành hai hướng là: xếp hạng ảnh dựa theo nội dung hiển thị và xếp hạng ảnh dựa theo văn bản. Các máy tìm kiếm ảnh thông dụng hiện nay như: Google Image Search, Yahoo! Image Search, MSN, AltaVista, … xếp hạng các ảnh trả về dựa trên vùng văn bản đi kèm với ảnh. Các hệ thống này cho phép người sử dụng nhập các chuỗi truy vấn về chủ đề ảnh mà họ cần tìm kiếm, thông qua việc phân tích các vùng văn bản đi kèm với các bức ảnh, hệ thống gửi trả lại các ảnh có nhãn tương ứng với chủ đề ảnh mà người sử dụng yêu cầu. Phương pháp này cho kết quả khả quan cũng như đáp ứng nhanh nhu cầu của người sử dụng. Tuy nhiên, đối với các câu truy vấn mang ý nghĩa nhập nhằng có thể sẽ có các kết quả trả về không đúng với yêu cầu đặt ra bởi vì vùng văn bản đi kèm ảnh không thể diễn tả được hết nội dung ảnh. Một hướng nghiên cứu khác là phân tích các đặc trưng hiển thị của ảnh và tiến hành xếp hạng theo các đặc trưng này. Một số công cụ tìm kiếm ảnh dựa trên nội dung điển hình như: Google Image Swirl, Tiltomo, Byo Image Search …. Các công cụ này nhận đầu vào là một chuỗi truy vấn dưới dạng văn bản hoặc một bức ảnh và cho phép người dùng tùy chỉnh lựa chọn tìm ảnh theo một số đặc trưng nào đó. Tuy nhiên, các máy tìm kiếm này thường chỉ tập trung khai thác vào một phần nội dung của ảnh và thường tốn khá nhiều thời gian do phải phân tích nội dung các bức ảnh. 1 Tags: là là các từ để đánh dấu một vùng trong ảnh mà khi di chuột qua vùng đó thì các từ đó sẽ hiển thị lên để chú thích cho bức ảnh. 20 Một trong các hướng nghiên cứu nhằm giải quyết và khắc phục vấn đề trên là kết hợp cả việc phân tích các đặc trưng của ảnh với các đặc trưng của chuỗi truy vấn vào quá trình tìm kiếm ảnh. Đây là một hướng nghiên cứu mới được sự quan tâm của nhiều hội nghị quốc tế như: International Journal of Computer Vision, IEEE conference… 1.5. Một số công trình nghiên cứu liên quan Các nghiên cứu về tìm kiếm Web đã bắt đầu từ những năm 1990. Cùng với sự cải tiến không ngừng của các công cụ tìm kiếm Web, các thuật toán tính hạng trang cũng nhận được sự quan tâm sâu sắc tại các hội nghị quốc tế. Sự ra đời của thuật toán PageRank [30] đã đánh dấu một bước phát triển nhảy vọt của các máy tìm kiếm Web mà điển hình của nó là Google, một trong số các máy tìm kiếm hàng đầu hiện nay. Kéo theo đó là sự ra đời của một loạt các thuật toán tính hạng trang khác [9] [23] [32] [35] nhằm cải tiến thuật toán PageRank. Phần lớn các nghiên cứu tìm kiếm Web là tập trung vào tìm kiếm các trang Web (tài liệu dạng văn bản) và chỉ một số ít trong đó là về tìm kiếm các thông tin đa phương tiện trên Web (ảnh, video, MP3…). Tuy nhiên, trong những năm gần đây, vấn đề tìm kiếm và xếp hạng các đối tượng đa phương tiện trên Web (đặc biệt là vấn đề tìm kiếm và xếp hạng ảnh) đang trở thành một vấn đề thu hút được rất nhiều sự quan tâm của các nhà khoa học trên thế giới. Bằng chứng là ngày càng có nhiều các công trình nghiên cứu về các thuật toán tính hạng ảnh được công bố [17] [29] [30] [34] [36] [38] [39][40]. Bên cạnh đó là sự ra đời của các máy tìm kiếm ảnh và các máy tìm kiếm thông thường cũng có xu hướng tích hợp thêm dịch vụ tìm kiếm ảnh. Một hướng phát triển mới cho các máy tìm kiếm Web đang rất được chú ý đó là các máy tìm kiếm lớp trên (Meta-search engine). Đã có một số công trình nghiên cứu về máy tìm kiếm lớp trên [11] [14] [18] [28] được công bố cũng như đã có một số máy tìm kiếm lớp trên (Dogpile, Clussty, KartOO, Google CSE…) được mang vào sử dụng trong thực tiễn. Tuy nhiên, những công cụ tìm kiếm này vẫn chưa mang lại được thành tựu nổi bật và chưa cạnh tranh được với Google. Ở Việt Nam, nghiên cứu và ứng dụng tìm kiếm và xếp hạng Web cũng đang nhận được nhiều sự quan tâm. Hiện tại, cũng có một số công ty làm về máy tìm kiếm như Bamboo, Zing, Xalo, Socbay…. Thứ trưởng Bộ TT-TT Nguyễn Minh Hồng1 cho rằng, các máy tìm kiếm trực tuyến ra đời là sự đóng góp lớn cho nền công nghiệp 1 21 CNTT Việt Nam. Tuy nhiên, những sản phẩm này vẫn chưa thể vượt qua các công cụ tìm kiếm của các “đại gia” nước ngoài trên thị trường nội địa. Theo ông Lê Ngọc Quang1, Giám đốc Phát triển Kinh doanh và Công nghệ của IDG Ventures Vietnam, công cụ tìm kiếm của Việt Nam hiện nay gần như bỏ không, không tạo doanh thu, rất ít người dùng và như vậy là một sự lãng phí. Ngoài các máy tìm kiếm còn có một số công trình nghiên cứu về tìm kiếm và xếp hạng đã được công bố. Một số công trình nghiên cứu bước đầu như cải tiến thuật toán tính hạng trang của Nguyễn Hoài Nam [2], mô hình học xếp hạng của Nguyễn Thu Trang [4], xây dựng công cụ tìm kiếm MP3 cho tiếng Việt của Nguyễn Hoàng Trung [5]. Công trình nghiên cứu của Nguyễn Hoài Nam [2] dựa trên cơ sở một số phương pháp tìm kiếm và xếp hạng trang cơ bản, từ đó đưa ra những đề xuất cải tiến cho thuật toán PageRank theo chủ đề. Phương pháp mà [2] đưa ra là gán các giá trị quan trọng khác nhau đối với các liên kết để làm chính xác hơn các kết quả tìm kiếm. Cụ thể như những liên kết từ các trang trong cùng chủ đề đối với trang được liên kết có thể mang tới cho trang đó giá trị nhiều hơn những trang không nằm trong cùng chủ đề. Phương pháp này đã được áp dụng thử nghiệm cho máy tìm kiếm Vietseek và bước đầu đã mang lại hiệu quả. Một nghiên cứu khác cũng về vấn đề xếp hạng là nghiên cứu về học xếp hạng trong tính hạng đối tượng và tạo nhãn cụm tài liệu của Nguyễn Thu Trang [4]. Công trình của [4] thực hiện khảo sát, phân tích các phương pháp học xếp hạng đang được quan tâm hiện nay và từ đó đưa ra mô hình xếp hạng thực thể áp dụng vào máy tìm kiếm thực thể trong tiếng Việt, cụ thể là tìm kiếm thực thể thuốc và học xếp hạng để tạo nhãn cho cụm tài liệu. Các kết quả thu được đã chứng minh vai trò và hiệu quả của học xếp hạng áp dụng vào máy tìm kiếm. Nguyễn Hoàng Trung [5] đã tiến hành xây dựng thử nghiệm một thành phần tìm kiếm MP3 cho tiếng Việt cho máy tìm kiếm Socbay. Hệ thống này tìm kiếm các file MP3 dựa vào các trường mô tả file. Phần mềm tìm kiếm này cho kết quả tương đối chính xác đối với cả những tìm kiếm tiếng Việt không dấu và có dấu trong thời gian cho phép. Qua quá trình tìm hiểu về tình hình nghiên cứu trong và ngoài nước, nhận thấy yêu cầu của thực tế đặt ra là rất cần thiết và cấp bách, trong khóa luận này, tôi tập trung nghiên cứu về các thuật toán tính hạng ảnh và sau đó áp dụng vào việc xây dựng 1 22 một mô hình máy tìm kiếm lớp trên thử nghiệm cho ảnh. Tôi tin rằng những nghiên cứu của mình là rất thiết thực và sẽ là nền tảng cho những nghiên cứu tiếp theo của mình. Tóm tắt chương một Trong chương một, khóa luận đã tập trung khảo sát, phân tích một số thuật toán tính hạng trang điển hình đang được sử dụng rộng rãi hiện nay. Đồng thời khóa luận cũng đã trình bày sơ bộ về vấn đề xếp hạng đối tượng nói chung và xếp hạng ảnh nói riêng. Trong chương tiếp theo, khóa luận sẽ giới thiệu chi tiết hơn về các thuật toán tính hạng ảnh theo nội dung hiển thị. 23 Chương 2. Một số thuật toán tính hạng ảnh phổ biến 2.1. Giới thiệu Như đã trình bày ở chương trước, xếp hạng ảnh là một bài toán điển hình trong lĩnh vực xếp hạng thực thể và đang nhận được nhiều sự quan tâm nghiên cứu của các nhà khoa học. Các nghiên cứu về xếp hạng ảnh hiện nay chủ yếu tập trung vào phân tích các đặc trưng về nội dung hiển thị của ảnh. Phương pháp phổ biến là dùng lý thuyết đồ thị để xây dựng mối quan hệ giữa các bức ảnh. Phương pháp tiếp cận này xây dựng một đồ thị kết nối các ảnh giống nhau, sau đó sử dụng vector đặc trưng để tìm các ảnh là “trung tâm” của đồ thị. Một hướng tiếp cận đơn giản và hiệu quả ứng dụng trong việc xử lý các thông tin về nội dung hiển thị của ảnh đã được đề xuất bởi Yushi Jing và Shumeet Baluja [39][40]. Phương pháp của Jing và Baluja sử dụng độ đo tương đồng giữa các bức ảnh để xây dựng một đồ thị tương đồng và dựa trên thuật toán PageRank để tính hạng cho các bức ảnh. Theo hướng tiếp cận này [34], [29] cũng có một số đề xuất để cải tiến thuật toán mà Jing và Baluja đưa ra. Một kỹ thuật khác là xây dựng các cụm các bức ảnh và sau đó sử dụng độ tương đồng trong cùng một cụm hoặc trung tâm cụm để tìm ảnh nổi bật nhất [27] [36]. Nghiên cứu của T.L.Berg và A.C.Berg mở rộng ý tưởng phân cụm bằng cách tìm các ảnh mà có một đối tượng nổi bật rõ ràng, và vì thế có nhiều khả năng đại diện nhất. Ngoài ra còn một số hướng tiếp cận theo hướng người dùng [38] hoặc học bán giám sát [17]. Các phương pháp này thường kết hợp cả các đặc trưng về văn bản của ảnh. Chương này sẽ tập trung giới thiệu chi tiết hơn một số thuật toán phổ biến xếp hạng ảnh dựa trên nội dung hiển thị. 2.2. VisualRank VisualRank là thuật toán tính hạng ảnh dựa vào việc phân tích độ tương đồng về nội dung giữa các bức ảnh do Yushi Jing và Shumeet Baluja [39][40] đề xuất. Phương pháp mà Jing và Baluja đưa ra lấy tư tưởng cơ bản từ thuật toán phân tích liên kết PageRank. Cũng giống như PageRank, thuật toán VisualRank sử dụng lý thuyết đồ thị để xây dựng đồ thị ảnh và dùng vector đặc trưng trung tâm để tính hạng cho các ảnh. Với nhận định trực quan rằng, nếu một người dùng xem một bức ảnh, thì người đó cũng có thể quan tâm đến các ảnh khác gần giống với ảnh vừa xem. Nghĩa là nếu giữa các ảnh có các liên kết biểu thị sự giống nhau giữa các ảnh đó thì sẽ có một xác suất nào đó để người dùng khi xem ảnh này sẽ chuyển sang xem một ảnh gần giống với nó. 24 Xây dựng đồ thị từ tập dữ liệu ảnh với các đỉnh của đồ thị biểu diễn các ảnh tương ứng trong tập dữ liệu. Các đỉnh được nối với nhau bởi các cạnh có trọng số là độ tương đồng giữa hai ảnh mà được biểu diễn bởi hai đỉnh của cạnh đó. Các cạnh này được gọi là các liên kết trực quan (visual hyperlinks) giữa các bức ảnh. VisualRank sử dụng quá trình duyệt ngẫu nhiên để xếp hạng các ảnh dựa vào các liên kết này. Nếu một ảnh u có liên kết tới ảnh v, thì sẽ có một xác suất để người dùng chuyển từ u sang v. Một cách trực quan ta có thể thấy các ảnh phù hợp với truy vấn sẽ có nhiều ảnh khác trỏ tới, và do đó chúng sẽ được thăm thường xuyên. Các ảnh được thăm thường xuyên thường được cho là quan trọng. Hơn nữa, nếu một ảnh v là quan trọng và nó có liên kết tới ảnh w, thì nó sẽ gộp độ quan trọng của nó cho độ quan trọng của w vì bản thân v là quan trọng. VisualRank được định nghĩa như sau: ܸܴ ൌ ܵכ ൈ ܸܴ ሺ2.1ሻ Trong đó, ܵכ là ma trận cắt giảm theo cột của ma trận ܵ, với ܵ௨,௩ là độ tương đồng giữa hai ảnh u và v. Việc lặp đi lặp lại phép nhân VR với ܵכ sẽ thu được vector đặc trưng của ma trận ܵכ. Mặc dù VR có kết quả cố định, nhưng theo thực nghiệm, nó có thể được ước lượng một cách hiệu quả hơn qua phương pháp tiếp cận lặp. Hình 4. Một minh họa về đồ thị độ tương đồng của ảnh 25 VisualRank hội tụ chỉ khi ma trận ܵכ là không tuần hoàn và tối giản. Cũng giống như PageRank, Jing đưa vào VisualRank một thừa số hãm d để đảm bảo đồ thị ảnh là đồ thị liên kết mạnh. Jing cũng chỉ ra rằng, ma trận tương đồng S cũng có thể là ma trận đối xứng. Trong trường hợp đó, sự xuất hiện của thừa số hãm có thể làm mất tính đối xứng của ma trận này. Với tập n ảnh, VisualRank được định nghĩa lại theo công thức sau: ܸܴ ൌ ݀ܵכ ൈ ܸܴ ൅ ሺ1 െ ݀ሻ݌ ݒớ݅ ݌ ൌ ൤ 1 ݊൨௡ൈଵ ሺ2.2ሻ Trong thực nghiệm, d thường được chọn giá trị d > 0.8. Một độ đo tin cậy của độ tương đồng là yếu tố quyết định tới tính hiệu quả của VisualRank bởi vì nó ảnh hưởng rất lớn tới cấu trúc của đồ thị. Qua phân tích các đặc tính của ảnh, Jing và Baluja cho rằng các đặc tính cục bộ của ảnh giàu thông tin hơn và vẫn giữ được tính ổn định khi qua các phép biến đổi khác nhau. Vì thế, trong nghiên cứu của mình, Jing và Baluja [40] chọn đặc trưng SIFT [24] [25] và biểu đồ hướng làm đặc trưng cho các đặc tính của ảnh. Ma trận tương đồng được xây dựng từ độ tương đồng của các cặp ảnh trong toàn bộ dữ liệu ảnh. Độ tương đồng của mỗi cặp ảnh có thể là số các thuộc tính cục bộ phù hợp của cặp ảnh đó. Với khối lượng ảnh khổng lồ trên Web hiện nay, lượng kết quả trả về của máy tìm kiếm ảnh đối với một truy vấn là rất lớn. Nhận thấy rằng việc tính toán để tạo ra đồ thị tương đồng S cho hàng tỉ bức ảnh là không thể, trong thực tế thi hành VisualRank, Jing và Baluja đề xuất phương pháp tiền phân cụm các ảnh Web dựa trên việc sử dụng các thuộc tính văn bản của ảnh để giảm bớt tập ảnh đầu vào. Việc này có thể thực hiện thông qua các máy tìm kiếm thương mại bằng cách trích rút tập N ảnh trả về đầu tiên khi truy vấn vào các máy tìm kiếm thương mại thông thường, sau đó tiến hành xây dựng đồ thị tương đồng và tính VisualRank chỉ trên tập con N ảnh này. Thuật toán VisualRank trình bày một kỹ thuật đơn giản để kết hợp các lợi điểm trong việc sử dụng liên kết và phân tích mạng cho tìm kiếm trang Web vào tìm kiếm ảnh. Thuật toán đã được các tác giả thử nghiệm và cho kết quả tốt hơn kết quả xếp hạng của máy tìm kiếm ảnh Google trong phần lớn các truy vấn trong khi vẫn duy trì được hiệu quả tính toán hợp lý cho việc triển khai quy mô lớn. 26 2.3. Multiclass VisualRank Multiclass VisualRank là thuật toán xếp hạng ảnh mở rộng ý tưởng từ phương pháp VisualRank của Jing và Baluja [39] [40] để xếp hạng ảnh cho nhiều phân loại ảnh, do Misur Ambai và Yuichi Yoshida [29] đề xuất. Multiclass VisualRank chia các ảnh được trả về từ máy tìm kiếm thành những phân loại khác nhau dựa vào các đặc trưng nội dung của ảnh và tiến hành xếp hạng trong từng phân loại đó. Multiclass VisualRank gồm ba bước sau: o Tính độ tương đồng về nội dung ảnh: Cũng giống như phương pháp VisualRank, Ambai sử dụng giải thuật SIFT để tính độ tương đồng ݓ௜,௝ giữa hai ảnh ܫ௜, ܫ௝. Thuật toán VisualRank nguyên thủy sử dụng tỉ số ܥ௜௝ là số các key points chung giữa hai ảnh ܫ௜ và ܫ௝ chia cho số key points trung bình lấy được từ ܫ௜, ܫ௝ làm độ đo tương đồng giữa hai ảnh đó. Tuy nhiên, các máy tìm kiếm ảnh thường trả về cùng một tập ảnh đối với cùng một truy vấn. Trong trường hợp này, giá trị ܥ௜௝ trở nên quá lớn so với các độ đo tương đồng khác, và có thể làm cho kết quả phân cụm không còn chính xác. Do đó, phương pháp Multiclass VisualRank áp dụng một hàm xích ma vào ܥ௜௝ để làm giảm các giá trị lớn. o Phân cụm: Bước này tiến hành phân tập các ảnh thành các phân loại khác nhau dựa vào việc phân cụm các độ đo tương đồng. Nhận thấy rằng, các ảnh càng gần giống nhau thì độ đo tương đồng càng lớn và đồ thị tương đồng chứa một số cụm ứng với các phân loại ảnh khác nhau. Do đó, [29] sử dụng kỹ thuật Nomarlized cut để phân cụm các bức ảnh trong tập dữ liệu bằng cách phân cụm các độ đo tương đồng trong ma trận tương đồng. Công thức phân cụm được tính như sau: ሺܦ െܹሻݒ ൌ λܦݒ ሺ2.3ሻ Với W là một ma trận kề có các phần tử là các độ đo tương đồng ݓ௜௝, D là một ma trận chéo, λ là giá trị riêng và ݒ là vector riêng. 27 Hình 5. Biến đổi ma trận kề o Tính hạng: Tương tự như phương pháp của Jing, Wang cũng sử dụng PageRank để tính hạng cho các ảnh: ݎ ՚ ሺ1 െ ߙሻܹݎ ൅ ߙ݌ ሺ2.4ሻ Với ݎ ൌ ሺݎଵ, … , ݎேሻ் là vector tính hạng của các ảnh, ߙ là thừa số hãm. Bởi vì các ảnh được chia thành các phân loại, điểm số tính hạng của một ảnh thuộc phân loại này không bị ảnh hưởng bởi điểm số tính hạng của các ảnh trong phân loại khác. Do đó, ta có thể bỏ đi độ đo tương đồng giữa các phân loại khác nhau, tức là bỏ đi liên kết giữa các ảnh thuộc về các phân loại khác nhau. Khi đó, ma trận kề W được sửa đổi như sau: ݓ௜௝ᇱ ൌ ቊ ݓ௜௝ ݊ếݑ ܫ௜ ݒà ܫ௝ ݐ݄ݑộܿ ݒề ܿù݊݃ ݉ộݐ ݌݄â݊ ݈݋ạ݅ 0 ݊݃ượܿ ݈ạ݅ ሺ2.5ሻ Bằng cách biến đổi ma trận kề W thành ma trận ܹᇱ, công việc tính toán đã được giảm đi đáng kể. Việc loại bỏ độ đo tương đồng giữa các ảnh thuộc về các phân loại khác nhau làm cho mỗi ảnh trong một phân loại càng giống với đại diện của phân loại đó thì có thứ hạng càng cao. Trong thực nghiệm, Multiclass VisualRank cho kết quả xếp hạng tốt với độ chính xác xấp xỉ bằng độ chính xác của VisualRank. Độ chính xác của 10 ảnh được xếp hạng đầu tiên bằng thuật toán Multiclass VisualRank là 0.949 trong khi đó độ chính xác của VisualRank là 0.953 [29]. Bỏ đi trọng số giữa các phân loại ảnh khác nhau 28 Hình 6. Kết quả xếp hạng của 3 phương pháp với truy vấn “Notre Dame” 2.4. Visual contextRank Phần trên đã trình bày một phương pháp xếp hạng ảnh khá hiệu quả được đề xuất bởi Jing và các đồng nghiệp, phương pháp này tiến hành xây dựng ma trận tương đồng của 1000 ảnh và sử dụng VisualRank để tính hạng cho mỗi bức ảnh. Tuy nhiên, phương pháp của Jing và cộng sự coi các đặc tính cục bộ có độ quan trọng là như nhau và không quan tâm đến các thông tin về ngữ cảnh. Do đó có thể sẽ gây ra nhiều sai sót trong việc tính độ tương đồng giữa các bức ảnh. Một phương pháp xếp hạng ảnh được trình bày dưới đây sử dụng thông tin ngữ cảnh để khắc phục các vấn đề trên. ContextRank là phương pháp do Shuhui Wang và cộng sự [34] đề xuất, sử dụng quá trình duyệt ngẫu nhiên Markov giữa các visual words1 trong cùng một ảnh và giữa các ảnh với nhau nhằm xếp hạng lại (re-ranking) các ảnh là kết quả trả về từ một máy tìm kiếm ảnh thương mại. Wang và cộng sự đưa ra hai giả định: i. Có thể di chuyển giữa các visual word lân cận nhau trong cùng một ảnh. ii. Có thể di chuyển từ một visual word A trong ảnh i tới visual word B trong ảnh j nếu tồn tại một liên kết giữa hai visual word này. 1 visual word: là một chỉ mục mô tả mẫu của một phân cụm các mô tả thuộc tính cục bộ của ảnh [33] 29 Phương pháp ContextRank coi mỗi visual word là một trạng thái trong không gian trạng thái Markov. Quá trình duyệt qua các visual word là sự chuyển trạng thái từ trạng thái hiện tại r đến trạng thái kết thúc s. Hình 7. Mô hình xếp hạng ảnh sử dụng thuật toán ContextRank Mô hình xếp hạng ContextRank mà Wang và cộng sự đề xuất gồm các thành phần như sau: o Chuẩn bị dữ liệu: Với đầu vào là một chuỗi truy vấn dạng từ khóa, ContextRank đưa chuỗi truy vấn này vào các máy tìm kiếm ảnh theo các thuộc tính văn bản của ảnh. Sau đó tiến hành trích rút N kết quả trả về đầu tiên từ máy tìm kiếm để thực hiện xếp hạng lại cho N ảnh này. o Mô hình ngữ cảnh nội ảnh (Intra-image Context Modeling): Thành phần này thực hiện việc xây dựng liên kết giữa các visual word trong cùng một ảnh với tập N ảnh lấy được từ dữ liệu. o Mô hình ngữ cảnh ngoại ảnh (Inter-image Context Modeling): Thành phần này thực hiện việc xây dựng liên kết giữa các visual word trong các ảnh khác nhau trong tập N ảnh. o Kết hợp ngữ cảnh nội ảnh (intra-image context) với ngữ cảnh ngoại ảnh (inter- image context) và dùng lý thuyết đồ thị duyệt ngẫu nhiên để mô hình hóa mối 30 quan hệ nội ảnh (intra-image) và ngoại ảnh (inter-image) của các visual word. Từ đó tiến hành tính hạng lại cho ảnh dựa vào điểm số (score) của các visual word trong một ảnh. Hạng của ảnh được tính theo phương pháp ContextRank như sau: Cho trước một tập từ vựng trực quan (visual vocabulary) với K visual keywords. Mỗi thuộc tính cục bộ của ảnh được gán một chỉ mục visual word. Với một tập chứa N ảnh kết quả trả về đầu tiên thu được từ các máy tìm kiếm ảnh dựa trên văn bản, biểu diễn các visual word trong tập N ảnh như một đồ thị, mỗi visual word xuất hiện trong mỗi ảnh được xem như là một đỉnh của đồ thị. Gọi ௜ܸ,௠ với ݅ ൌ 1,…ܰ; ݉ ൌ 1,…ܭ là biểu diễn của một đỉnh. Vậy ta có tất cả ܭ ൈ ܰ đỉnh. Mục đích của thuật toán là tìm điểm số ߨሺ ௠ܸ,௜ሻ của visual word thứ m trong ảnh i. Biểu diễn đồ thị các visual word bởi ma trận chuyển P, ߨ ൌ ሼߨሺ ௜ܸ,௠ሻሽ, ∑ ߨሺ ௜ܸ,௠ሻ௜,௠ , ݅ ൌ 1,…ܰ; ݉ ൌ 1,…ܭ, ߨ là vector riêng của ma trận P với giá trị riêng bằng 1, mỗi phần tử của ߨ là điểm số của một visual word. ߨ được tính theo công thức: ߨ ൌ ܲߨ ሺ2.6ሻ Do tính chất của chuỗi Markov, để tính vector riêng của P, đồ thị visual word phải là liên thông, tức là với cặp hai visual word i, j bất kì luôn có đường đi từ i tới j và ngược lại. Tuy nhiên, vẫn tồn tại không ít các visual word không có liên kết đến các visual word khác. Vì vậy cần phải biến đổi ma trận P để tránh việc khi duyệt các đỉnh không có liên kết sẽ không duyệt được tiếp. Hơn nữa, để đảm bảo tính phân phối dừng ổn định (duy nhất) của ߨ, tức là từ một đỉnh trong quá trình duyệt có thể chuyển tới một đỉnh bất kỳ khác, thì cần phải thêm một nhân tố hãm. Công thức (2.6) được viết lại như sau: ߨ ൌ ߙܲߨ ൅ ሺ1 െ ߙሻܦ ሺ2.7ሻ Trong đó: ߙ là hệ số hãm. Trong thực tế ߙ thường được chọn giá trị 0.8. D là vector ܭܰ ൈ 1 với tổng các phần tử bằng 1. D có thể được tính theo công thức: 31 ܦሾሺ݅ െ 1ሻ ൈ ܭ ൅݉ሿ ൌ ቐ ܫܵሺ݅ሻ ݊ݑ݉௡௭ሺ௠ሻ ݊ếݑ ݒݓሺ݉ሻ ؿ ݅݉݃ሺ݅ሻ 0 ݊݃ượܿ ݈ạ݅ ሺ2.8ሻ IS(i) là điểm số khởi tạo của ảnh i, num_nz(m) là số visual word với tần số không bằng 0. Nhận thấy rằng P là ma trận rất thưa, phép nhân với các phần tử bằng 0 trong P là rất đơn giản. Vì thế ta có thể chia P thành các ma trận con. Mỗi ma trận con là một ma trận dịch chuyển của các visual words trong ảnh i và các visual words trong ảnh j. Gọi ܤ௜,௝ là biểu diễn của ma trận con nói trên. P được tổ chức lại thành hai ma trận con: ܲ ൌ ܾܩ ൅ ሺ1 െ ܾሻܥ ሺ2.9ሻ G là một ma trận bao gồm các ma trận con ܤ௜,௜, ݅ ൌ 1,…ܰ và tất cả các ma trận con khác bằng 0. C là một ma trận bao gồm các ma trận con ܤ௜,௜, ݅ ൌ 1,…ܰ bằng 0 và tất cả các ma trận con khác khác 0. G đánh giá xác suất dịch chuyển của các visual word trong cùng một ảnh còn C đánh giá cho các visual word trong các ảnh khác nhau. Tham số b là nhân tố trọng số. Sau khi đã tính được vector riêng ߨ của các visual words trong mỗi ảnh, hạng của ảnh i được tính theo công thức: ܴሺ݅ሻ ൌ෍ ߨ ௄ ௠ୀଵ ൫ ௜ܸ,௠൯, ݅ ൌ 1,…ܰ ሺ2.10ሻ Với ߨሺ ௜ܸ,௠ሻ là điểm số của visual word thứ m trong ảnh i. Đối với các visual keyword mà không tồn tại trong ảnh i thì ߨ൫ ௜ܸ,௠൯ ൌ 0. 32 Hình 8. Một ví dụ về biểu diễn visual words Trong thực nghiệm, Wang trích xuất khoảng 200 đặc trưng SIFT cho mỗi bức ảnh và sử dụng một tập khoảng 400 từ vựng để tính toán. Thuật toán được áp dụng thử nghiệm cho hai tập dữ liệu khác nhau và đã cho kết quả tốt hơn đáng kể đối với phương pháp VisualRank trong việc xếp hạng lại ảnh. 2.5. Nhận xét Qua tìm hiểu các phương pháp xếp hạng ảnh ở trên, tôi nhận thấy các phương pháp này đều áp dụng kỹ thuật phân tích liên kết để phân tích mối quan hệ giữa các ảnh dựa vào đặc trưng hiển thị. Các phương pháp này là khá đơn giản và cho kết quả xếp hạng khả quan. Tuy nhiên, các phương pháp nói trên đều chỉ dựa vào nội dụng hiển thị của ảnh mà không quan tâm đến các dữ liệu dạng văn bản đi kèm với ảnh. Vì các dữ liệu văn bản này là do người dùng tạo ra nên chúng đều có một ý nghĩa nhất định đối với nội dung hiển thị của ảnh. Sự thành công của các máy tìm kiếm ảnh dựa trên văn bản đã khẳng định điều đó. Hơn nữa, những thành tựu trong lĩnh vực phân tích và xử lý văn bản đã mang lại nhiều thuận lợi trong việc tính độ tương đồng giữa các văn bản. Dựa vào những ưu điểm, nhược điểm trên, đối với khóa luận này, tôi quyết định sử dụng phương pháp xếp hạng ảnh áp dụng thuật toán VisualRank cho cả đặc trưng hiển thị và đặc trưng văn bản của ảnh mà đã được đề xuất trong báo cáo công trình nghiên cứu khoa học sinh viên của chúng tôi. Tóm tắt chương hai Trong chương hai, khóa luận đã giới thiệu chi tiết một số phương pháp xếp hạng ảnh điển hình dựa trên nội dung hiển thị. Đồng thời, chương này cũng đã đưa ra được một số nhận xét về ưu điểm, nhược điểm của các phương pháp này và đưa ra phương pháp xếp hạng ảnh kết hợp giữa nội dung hiển thị và dữ liệu văn bản đi kèm với ảnh sẽ 33 được sử dụng trong phần thực nghiệm của khóa luận. Trong chương tiếp theo, khóa luận sẽ giới thiệu mô hình chung của máy tìm kiếm lớp trên và một mô hình máy tìm kiếm ảnh lớp trên, đồng thời trình bày một số vấn đề trong việc xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên. 34 Chương 3. Mô hình máy tìm kiếm ảnh lớp trên Meta-search engine (tạm dịch là máy tìm kiếm lớp trên) [18] [28] là một máy tìm kiếm mà tìm kiếm thông tin dựa trên các máy tìm kiếm khác. Với mỗi truy vấn của người dùng, máy tìm kiếm lớp trên sẽ chuyển nó đến các máy tìm kiếm khác (gọi là các máy tìm kiếm nguồn) và sau đó xử lý kết quả trả về từ các máy tìm kiếm này trước khi đưa ra kết quả cho người dùng trên một giao diện duy nhất. Máy tìm kiếm lớp trên chủ yếu được sử dụng để mở rộng vùng tìm kiếm nhờ việc sử dụng kết quả tìm kiếm từ nhiều nguồn dữ liệu của các máy tìm kiếm khác nhau, giúp tăng cơ hội cho người dùng tìm được thông tin mong muốn. Chương này sẽ trình bày về kiến trúc chung của máy tìm kiếm lớp trên, đồng thời giới thiệu một mô hình máy tìm kiếm ảnh lớp trên và sau đó sẽ giới thiệu sơ bộ về vấn đề xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên. 3.1. Kiến trúc chung của máy tìm kiếm lớp trên Hình 9. Kiến trúc của một máy tìm kiếm lớp trên điển hình [18] Kiến trúc của một máy tìm kiếm Web lớp trên cũng gần giống với kiến trúc của một máy tìm kiếm Web thông thường [18]. Sự khác biệt cơ bản đó là máy tìm kiếm lớp trên không có thành phần cơ sở dữ liệu để lưu trữ các trang Web như máy tìm kiếm Web thông thường. Thay vào đó là một cơ sở dữ liệu ảo bao gồm: bộ điều vận (dispatcher), các máy tìm kiếm thông thường khác, và một bộ xử lý kết quả (result processor). Một máy tìm kiếm lớp trên bao gồm bốn thành phần chính: giao diện người dùng (user interface), bộ điều vận (dispatcher), bộ xử lý kết quả (result processor), và mô đun tính hạng (scoring module). 35 3.1.1. Giao diện người dùng Giao diện người dùng là bộ phận nhận truy vấn đầu vào của người dùng và hiển thị kết quả đầu ra. Giao diện thường là một trang Web có hộp thoại nhận các mô tả về thông tin mà người dùng cần tìm kiếm. Một máy tìm kiếm lớp trên thường có một số tùy chọn như là chọn danh sách các máy tìm kiếm mà máy tìm kiếm lớp trên sẽ lấy dữ liệu từ đó từ một danh sách các máy tìm kiếm thông thường cho trước, thiết lập độ sâu tìm kiếm, thời gian tìm kiếm…Một trong những hạn chế của máy tìm kiếm lớp trên là thời gian kiếm thường chậm vì phải chờ kết quả trả về từ các máy tìm kiếm khác. Nếu một máy tìm kiếm lớp trên gửi truy vấn đến càng nhiều máy tìm kiếm thì tốc độ của nó càng chậm. 3.1.2. Bộ điều vận Bộ điều vận của máy tìm kiếm lớp trên gần giống với bộ xử lý truy vấn của máy tìm kiếm thông thường. Bộ xử lý truy vấn tạo ra các truy vấn đến cơ sở dữ liệu dựa trên các truy vấn đầu vào còn bộ điều vận thì tạo ra các truy vấn đến máy tìm kiếm thông thường từ truy vấn của người dùng. Một bộ điều vận phải xác định được các máy tìm kiếm mà nó sẽ truy vấn và làm thế nào để truy vấn trên chúng. Hình 10. Một thiết kế của bộ điều vận [18] Một bộ điều vận có thể bao gồm bốn thành phần: Source Selector: Thành phần này sẽ lựa chọn các máy tìm kiếm thông thường để truy vấn trên nó. Nếu bộ điều vận gửi yêu cầu đến quá nhiều máy tìm kiếm thì có thể sẽ làm quá tải tài nguyên mạng và do đó sẽ mất nhiều thời gian để hoàn tất công việc tìm kiếm. Việc quyết định gửi yêu cầu đến máy tìm kiếm nào là rất quan trọng, bởi vì mỗi máy tìm kiếm khác nhau sẽ cho tập dữ liệu khác nhau và sẽ ảnh hưởng đến kết quả tìm kiếm của máy tìm kiếm lớp trên. Nếu máy tìm kiếm X cho kết quả trả về quá tốt, hơn hẳn máy tìm kiếm Y và Z, thì máy tìm kiếm lớp trên kết hợp cả ba máy này 36 chưa chắc đã có kết quả tìm kiếm tốt hơn kết quả của X. Tuy nhiên, nếu kết hợp các kết quả của các máy tìm kiếm khác không quá tốt lại có thể giúp cho kết quả tốt hơn. Query Generator: thực hiện việc sửa đổi các truy vấn sao cho phù hợp với mỗi máy tìm kiếm nguồn. Mỗi máy tìm kiếm thường chỉ làm việc hiệu quả trên một số dạng truy vấn nhất định. Do đó, một truy vấn không thích hợp sẽ mang lại kết quả tìm kiếm không tốt. Request Generator: Thành phần tạo yêu cầu kết hợp truy vấn của người dùng với máy tìm kiếm nguồn được lựa chọn và lựa chọn truy vấn sửa đổi để tạo một yêu cầu hợp lệ. Request Submitter: Thành phần này nhận các yêu cầu từ request generator và thực thi chúng. Request submitter phải tương tác với các giao thức cấp thấp và đảm bảo rằng các lỗi xảy ra được ghi lại một cách thích hợp. 3.1.3. Bộ xử lý kết quả Bộ xử lý kết quả của một máy tìm kiếm lớp trên nhận kết quả tìm kiếm của các máy tìm kiếm thông thường và xử lý chúng để chuyển sang cho mô đun tính hạng. Các kết quả gửi tới mô đun tính hạng từ bộ xử lý kết quả cũng giống với các kết quả nhận được từ cơ sở dữ liệu trong máy tìm kiếm thông thường. Bộ xử lý kết quả nhận các hồi đáp từ máy tìm kiếm và trích xuất chúng từ các kết quả đơn lẻ. Trang phản hồi từ một máy tìm kiếm chỉ chứa thông tin tối thiểu về mỗi kết quả. Và thông tin được cung cấp trong đầu ra của các máy tìm kiếm khác nhau cũng rất đa dạng, theo nghĩa mỗi máy tìm kiếm có một dạng đầu ra khác nhau. Ví dụ một máy tìm kiếm có thể cung cấp tên, địa chỉ URL, bản tóm tắt, trong khi một máy tìm kiếm khác có thể cung cấp tên, ngày tháng, địa chỉ URL, ngữ cảnh của truy vấn…. Cùng một trang Web được trả về từ hai máy tìm kiếm khác nhau có thể trông sẽ khác nhau. Một bộ xử lý kết quả tiên tiến có thể thực hiện hành động thu thập thông tin để bổ sung thêm dữ liệu vào mỗi kết quả nhằm làm giàu cho dữ liệu. Hơn nữa, trong các kết quả trả về từ các máy tìm kiếm nguồn khác nhau có thể có những kết quả giống nhau. Vì vậy, bộ xử lý kết quả cần phải nhận biết các kết quả trùng lặp này và loại bỏ bớt những kết quả thừa, chỉ giữ lại một kết quả duy nhất. 3.1.4. Mô đun tính hạng Cũng giống như mô đun tính hạng trong các máy tìm kiếm thông thường, mô đun tính hạng của một máy tìm kiếm lớp trên thực hiện việc tính hạng cho mỗi kết quả 37 trong nguồn dữ liệu nhận được từ bộ xử lý kết quả. Máy tìm kiếm lớp trên cần phải có các thuật toán hiệu quả để có thể hiểu được đâu là kết quả phù hợp nhất với người dùng trong tập hợp kết quả tìm kiếm từ nhiều nguồn khác nhau, từ đó trả về kết quả theo thứ tự xếp hạng mới. Không giống như các máy tìm kiếm thông thường, máy tìm kiếm lớp trên bị giới hạn thông tin về các kết quả nhận được. Sự thiếu thốn thông tin này làm cho việc tính hạng trở nên khó khăn hơn. 3.2. Mô hình máy tìm kiếm ảnh lớp trên MetaSEEk Trong những năm gần đây, cùng với sự phát triển không ngừng của các dịch vụ trên Internet, các máy tìm kiếm mới ra đời ngày càng nhiều với chức năng ngày càng phong phú và đa dạng. Đặc biệt trong đó có sự ra đời của các máy tìm kiếm lớp trên. Một số máy tìm kiếm lớp trên điển hình phải kể đến như là: Google CSE, Helios, Dogpile, VisualSEEk, WebSEEk, MetaSEEk, …. Trong đó MetaSEEk [11] là một máy tìm kiếm lớp trên chuyên tìm kiếm các ảnh trên Web dựa vào nội dung của ảnh. Phần này sẽ tập trung trình bày mô hình của máy tìm kiếm ảnh lớp trên MetaSEEk. Hình 11. Kiến trúc tổng thể của MetaSEEk [11] 38 Cũng giống như các máy tìm kiếm lớp trên khác, mô hình của MetaSEEk gồm có ba thành phần chính: bộ dịch truy vấn (query translator), bộ điều vận (query dispatcher) và giao diện hiển thị (display interface). Khi nhận được một câu truy vấn từ phía người dùng, bộ điều vận sẽ chọn các máy tìm kiếm nguồn thích hợp dựa trên cơ sở dữ liệu về khả năng thực thi của từng truy vấn đã thực hiện trước đó. Cơ sở dữ liệu này chứa các điểm số chỉ ra khả năng thực thi tốt hay kém của từng truy vấn trong quá khứ đối với mỗi tùy chọn tìm kiếm. Các điểm số này được gọi là các điểm số hiệu năng (performance score) của các tùy chọn tìm kiếm đối với mỗi truy vấn, và cơ sở dữ liệu chứa các điểm số như vậy được gọi là cơ sở dữ liệu hiệu năng (performance database). Sau khi đã chọn được các máy tìm kiếm nguồn, bộ dịch truy vấn chuyển các truy vấn sang dạng thích hợp và gửi tới các máy tìm kiếm nguồn đã được chọn. Cuối cùng, thành phần hiển thị kết hợp và xếp hạng lại các kết quả nhận được từ các máy tìm kiếm và hiển thị cho người dùng. MetaSEEk đánh giá chất lượng của các kết quả trả về bởi mỗi tùy chọn tìm kiếm dựa trên các phản hồi từ phía người sử dụng. 3.2.1. Truy vấn trực quan dựa trên nội dung Như đã nói ở các chương trước, đầu vào của một máy tìm kiếm ảnh có thể là một từ khóa hay một bức ảnh. Người sử dụng có thể đưa vào máy tìm kiếm ảnh một truy vấn có dạng là một ảnh được lấy từ một tập ảnh mẫu ngẫu nhiên hoặc từ một tập các ảnh trả về bởi một truy vấn dạng từ khóa, hoặc truy vấn có thể là một URL của một ảnh trên Web. Các truy vấn có dạng như vậy được gọi là các truy vấn trực quan dựa trên nội dung (Content-based visual query). Với truy vấn là một ảnh, máy tìm kiếm tính toán các đặc trưng của ảnh đầu vào này và sử dụng các đặc trưng này để tìm các ảnh gần giống với ảnh truy vấn nhất trong cơ sở dữ liệu. Tìm kiếm ảnh dựa trên từ khóa có thể được sử dụng để phân nhóm các ảnh theo chủ để và do đó làm giảm phạm vi tìm kiếm. Để có thể xử lý hiệu quả các truy vấn trực quan trong cơ sở dữ liệu ảnh lớn, các máy tìm kiếm cũng cần phải sử dụng các kỹ thuật phân cụm và đánh chỉ mục trên các vector đặc trưng của ảnh. 3.2.2. Giao diện truy vấn MetaSEEk tìm kiếm ảnh dựa trên bốn máy tìm kiếm nguồn là: VisualSEEk, WebSEEk, QBIC, và Virage. Mỗi máy tìm kiếm nguồn đều có các tính năng cũng như các hạn chế riêng. VisualSEEk, QBIC và Virage cung cấp các phương thức cho việc tìm kiếm ảnh số dựa trên các đặc trưng trực quan bằng việc sử dụng các mẫu. QBIC và 39 VisualSEEk cho phép tùy chỉnh các tìm kiếm bằng việc sử dụng các phác thảo trực quan (ví dụ như chỉ định bảng màu) hoặc đưa vào một ảnh mẫu, trong khi đó Virage cho phép người dùng xác định trọng số độ quan trọng của mỗi đặc trưng trong tìm kiếm. Ngoài ra, QBIC còn cung cấp dịch vụ tìm kiếm ảnh dựa trên từ khóa. WebSEEk là một máy tìm kiếm và phân loại ảnh bán tự động. Nó hỗ trợ tìm kiếm cả dựa trên nội dung hiển thị và dựa trên văn bản, tuy nhiên MetaSEEk chỉ sử dụng khả năng tìm kiếm ảnh dựa trên văn bản của WebSEEk. Hình 12. Giao diện hiển thị của MetaSEEk MetaSEEk cung cấp giao diện cho phép tìm kiếm ảnh dựa trên cả nội dung hiển thị và từ khóa. Với truy vấn trực quan dựa trên nội dung hiển thị, người dùng có thể chọn bất kỳ ảnh mẫu nào từ các cơ sở dữ liệu được hỗ trợ, hoặc đưa vào một URL của một ảnh trên Web. Giao diện của MetaSEEk cho phép người dùng tùy chọn các đặc trưng để tìm kiếm. Hai đặc trưng có sẵn cho người dùng lựa chọn là: màu sắc và kết cấu. Người dùng có thể lựa chọn tìm kiếm ảnh dựa trên màu sắc hoặc dựa trên kết cấu hoặc dựa trên cả hai đặc trưng này. Như đã nói ở trên, với mỗi tùy chọn sẽ chỉ có một số máy tìm kiếm nguồn được sử dụng. Bộ điều vận nhận biết được khả năng tìm kiếm của mỗi cơ sở dữ liệu và sẽ quyết định gửi truy vấn tới các máy tìm kiếm nào. Ngoài ra, người sử dụng còn có thể chỉ định thời gian tìm kiếm tối đa, số lượng các tùy chọn tìm kiếm, và thể loại quan tâm. Người sử dụng cũng có thể điểu chỉnh số lượng các truy vấn được gửi đến các công cụ tìm kiếm riêng rẽ tùy thuộc vào tải mạng. 40 Trong thời gian lưu lượng mạng thấp, người sử dụng có thể làm tăng các truy vấn đồng thời. Việc chờ đợi trong một khoảng thời gian tối đa ngăn không cho hệ thống bị chậm trễ từ việc hồi đáp chậm trễ của các máy tìm kiếm nguồn. 3.2.3. Bộ điều vận Mỗi khi nhận được một truy vấn từ phía người dùng, bộ điều vận chọn các máy tìm kiếm nguồn và tùy chọn tìm kiếm nguồn để gửi câu truy vấn đến. Một tùy chọn tìm kiếm là một phương pháp truy vấn trên một công cụ tìm kiếm cụ thể. Ví dụ, một truy vấn gửi tới VisualSEEk yêu cầu tìm kiếm ảnh dựa trên kết cấu là một tùy chọn tìm kiếm. Bộ điều vận tạo quyết định dựa trên loại truy vấn được gửi đến máy tìm kiếm lớp trên và cơ sở dữ liệu chứa điểm số chỉ khả năng thực thi của các truy vấn trong quá khứ. Nếu người dùng yêu cầu một ảnh mẫu ngẫu nhiên hay một từ khóa truy vấn, hệ thống đơn giản chỉ đặt ra các câu hỏi tới các máy tìm kiếm mà hỗ trợ những hành động này (QBIC, Virage và VisualSEEk hỗ trợ truy vấn mẫu ngẫu nhiên, QBIC và WebSEEk hỗ trợ truy vấn dạng từ khóa). Với các truy vấn trực quan dựa trên nội dung, việc lựa chọn máy tìm kiếm nguồn là dựa trên cơ sở dữ liệu hiệu năng. Cơ sở dữ liệu này chứa điểm số chỉ ra thế nào là tốt hay thế nào là xấu với mỗi tùy chọn tìm kiếm đã được thực hiện trong quá khứ trên các máy tìm kiếm với mọi ảnh truy vấn. Một truy vấn trực quan được xác định bởi một ảnh, một nhóm các đặc trưng, và một chủ đề. Khi nhận được một truy vấn, MetaSEEk tìm kiếm trong cơ sở dữ liệu hiệu năng và tìm kiếm điểm số hiệu năng của ảnh truy vấn. Trong cấu trúc của cơ sở dữ liệu nói trên, mỗi hàng tương ứng với một truy vấn đã được thực hiện trước đó. Mỗi cột điểm số tương ứng với một tùy chọn tìm kiếm. Bộ điều vận sẽ quyết định chọn các tùy chọn tìm kiếm có điểm số cao nhất mà phù hợp với những yêu cầu của người dùng. MetaSEEk đánh giá chất lượng của các kết quả trả về của mỗi tùy chọn tìm kiếm dựa trên phản hồi của người dùng. Một thủ tục thăm dò tự động được thực hiện để thiết lập điểm số hiệu năng ban đầu nhằm xây dựng một cơ sở dữ liệu hiệu năng dựa trên một số mẫu huấn luyện. Đối với các truy vấn mới không có điểm số hiệu năng được ghi trong cơ sở dữ liệu, các tác giả đưa ra một giải pháp đơn giản nhất là chọn ngẫu nhiên một tùy chọn tìm kiếm để thực hiện truy vấn. Ngoài ra, hệ thống còn xét tới một hướng tiếp cận khác là liên hệ các truy vấn mới với các truy vấn trong quá khứ mà ta đã có thông tin về hiệu suất thực thi. Các ảnh trong cơ sở dữ liệu được phân thành các chủ đề dựa trên nội dung hiển thị của chúng. Mỗi chủ đề gồm các nhóm đặc trưng: màu sắc, kết cấu và 41 cả hai loại đặc trưng trên. Khi truy vấn của người dùng là một truy vấn mới, hệ thống tải ảnh về và kết hợp nó với các cụm tương ứng để nhận được một danh sách các cụm phù hợp nhất. Các ảnh được chọn từ một số cụm gần giống nhất sẽ được hiển thị cho người dùng. Bộ điều vận có thể chọn các máy tìm kiếm phù hợp dựa trên điểm số hiệu năng trung bình của cụm được chọn bởi người sử dụng. Cuối cùng, ảnh mới sẽ được lưu vào cơ sở dữ liệu để sử dụng cho những truy vấn lần sau. MetaSEEk sử dụng thuật toán phân cụm K-means để phân cụm các ảnh trong cơ sở dữ liệu. Cứ sau mỗi khi có 10 ảnh mới được lưu vào cơ sở dữ liệu thì hệ thống sẽ thực hiện thuật toán phân cụm. Màu sắc và kết cấu là các đặc trưng được sử dụng cho việc phân cụm. Phân loại theo chủ đề Hệ thống phân nhóm các ảnh theo chủ đề để ràng buộc phạm vi tìm kiếm. Cơ sở dữ liệu của các máy tìm kiếm nguồn thường có một số loại riêng biệt. Ví dụ, cơ sở dữ liệu của QBIC bao gồm phần lớn là ảnh về con người, trong khi đó cơ sở dữ liệu của Virage có nhiều thể loại khác. Nếu người dùng quan tâm tìm kiếm ảnh của một em bé, có nhiều khả năng QBIC sẽ mang lại kết quả thích hợp hơn trong thời gian ngắn hơn. Hệ thống tận dụng lợi thế của thực tế này bằng cách cung cấp khả năng tìm kiếm trong một phạm vi của một chủ đề cụ thể. Nếu người sử dụng chọn một chù đề cụ thể, thì người đó giả định rằng chỉ tìm kiếm các ảnh trong chủ đề đó. Cấu trúc cơ sở dữ liệu Cơ sở dữ liệu của MetaSEEk chứa các vector đặc trưng (màu sắc và kết cấu), điểm số hiệu suất, các phân cụm, và các chủ đề cho tất cả các ảnh mà đã được truy vấn trên MetaSEEk. Tất cả những thông tin này là cần thiết cho bộ điều vận trong việc lựa chọn các máy tìm kiếm thích hợp cho các truy vấn đầu vào. Cơ sở dữ liệu được tổ chức theo cấu trúc phân cấp. Đầu tiên các ảnh được phân loại theo chủ đề dựa trên ngữ nghĩa của chúng (ví dụ như loài vật, con người). Việc phân loại ảnh vào chủ đề nào là do người dùng thực hiện. Thuật toán K-means được sử dụng để phân cụm các ảnh trong mỗi chủ đề vào các lớp dựa trên các đặc trưng về màu sắc, kết cấu hoặc cả hai loại đặc trưng. 42 Hình 13. Cấu trúc phân cấp của cơ sở dữ liệu Tại tầng thấp nhất của cơ sở dữ liệu, mỗi ảnh có một bản ghi chứa thông tin như trong bảng 1. Trong đó cột bên trái là các tùy chọn tìm kiếm còn cột bên phải là điểm số tương ứng đối với mỗi tùy chọn. Các điểm số này được cập nhật mỗi khi ảnh đó được truy vấn dựa vào phản hồi của người sử dụng. Bảng 1. Ví dụ về bản ghi của một ảnh trong cơ sở dữ liệu 3.2.4. Thành phần hiển thị Mỗi khi các kết quả được lấy về từ các máy tìm kiếm nguồn, chúng được tổ chức lại và hiển thị cho người dùng bởi thành phần hiển thị. Quá trình này phụ thuộc vào truy vấn của người sử dụng: truy vấn là một ảnh mẫu ngẫu nhiên, hay truy vấn là từ 43 khóa hay là ảnh. Nếu truy vấn là một ảnh mẫu ngẫu nhiên hoặc là từ khóa thì các kết quả trả về từ các máy tìm kiếm nguồn sẽ được trộn lẫn và hiển thị cho người sử dụng một cách ngẫu nhiên. Trong trường hợp này, thứ tự hiển thị của các kết quả là không quan trọng. Đối với các truy vấn trực quan dựa trên nội dung, các ảnh được xếp hạng trước khi hiển thị cho người dùng. Tìm kiếm ảnh dựa trên nội dung hiển thị trả về một danh sách các ảnh được sắp xếp theo thứ tự gần giống nhất đối với ảnh truy vấn. MetaSEEk thực hiện việc xếp hạng những ảnh này bằng cách sử dụng điểm số hiệu năng trong cơ sở dữ liệu. Các ảnh được trả về bởi mỗi tùy chọn tìm kiếm sẽ được xen vào trước khi hiển thị chúng cho người sử dụng. Điểm số hiệu năng của ảnh truy vấn sẽ xác định thứ tự hiển thị và số các ảnh trong mỗi nhóm xen vào kết quả của mỗi tùy chọn tìm kiếm. Ví dụ, chúng ta giả sử rằng các ảnh nhận được từ hai tùy chọn tìm kiếm với điểm số hiệu năng là 2 và 1. Thành phần hiển thị sẽ hiển thị 2 ảnh từ tùy chọn tìm kiếm có điểm số là 2, và 1 ảnh từ tùy chọn tìm kiếm với điểm số là 1 cho đến khi tất cả các ảnh trả về được hiển thị hết. 3.2.5. Đánh giá Hệ thống tìm kiếm ảnh lớp trên MetaSEEk đã được các tác giả tiến hành một số thử nghiệm để đánh giá hiệu suất thực hiện của nó [11]. Các thử nghiệm này được thực hiện với các loại câu truy vấn khác nhau và với mỗi thử nghiệm thì được thực hiện hai lần để đánh giá sự cải thiện của việc sử dụng điểm số hiệu năng trong tìm kiếm. Sau đó các kết quả thực nghiệm cũng được so sánh với phiên bản trước của MetaSEEk (phiên bản không phân loại ảnh theo chủ đề) và với một máy tìm kiếm lớp trên không sử dụng việc đánh giá hiệu năng. Kết quả so sánh cho thấy rằng MetaSEEk có khả năng tìm kiếm tốt hơn hai hệ thống còn lại. Qua các kết quả thực nghiệm, ta thấy rằng hiệu suất của một hệ thống tìm kiếm lớp trên có thể được cải thiện rất nhiều nếu công cụ tìm kiếm tích hợp và lựa chọn thông minh bởi việc đánh giá hiệu năng cho các lớp truy vấn khác nhau và sử dụng phản hồi của người dùng trong việc xếp hạng các kết quả trả về. 3.3. Xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên Sau khi nhận được các kết quả trả về từ các máy tìm kiếm nguồn, máy tìm kiếm lớp trên cần phải tổng hợp và sắp xếp các kết quả này thành một danh sách ảnh duy nhất và trả về cho người sử dụng. Danh sách này được sắp xếp theo thứ tự những ảnh phù hợp với 44 truy vấn của người dùng hơn thì có thứ hạng cao hơn. Việc sắp xếp các ảnh như vậy còn được gọi là xếp hạng lại. Tuy nhiên, việc xếp hạng lại các kết quả này là một thách thức lớn đối với máy tìm kiếm lớp trên bởi vì tính không đồng nhất giữa các máy tìm kiếm nguồn. Các kết quả nhận được từ mỗi máy tìm kiếm nguồn thường được xếp hạng dựa trên những đặc trưng khác nhau của ảnh. Một số máy tìm kiếm ảnh thông thường tìm kiếm và xếp hạng ảnh chỉ dựa trên các đặc trưng về văn bản của ảnh trong khi một số máy tìm kiếm khác tìm kiếm dựa vào các đặc trưng về nội dung hiển thị. Ví dụ Google Image Search, Yahoo Image Search và Bing tìm kiếm ảnh dựa trên văn bản trong khi Byo Image Search tìm kiếm ảnh dựa trên màu sắc còn Tiltomo thì tìm kiếm dựa trên màu sắc và kết cấu. Vì thế, tập các ảnh nhận được từ các máy tìm kiếm nguồn thường rất đa dạng. Do đó khó khăn ở đây là làm thế nào để tổng hợp các ảnh này trong một danh sách duy nhất và các ảnh được sắp xếp một cách hợp lý. Tuy nhiên, khó khăn này cũng chính là một lợi thế bởi vì các ảnh được trả về từ một máy tìm kiếm nguồn thường có xu hướng nhóm thành một cụm dựa theo đặc trưng tìm kiếm của máy tìm kiếm nguồn đó. Hơn nữa chúng ta còn có thể tận dụng được kết quả xếp hạng sẵn có của các ảnh này ở máy tìm kiếm nguồn. Một thách thức khác đối với việc xếp hạng trong máy tìm kiếm ảnh lớp trên chính là vấn đề thời gian. Bởi vì quá trình từ lúc nhận truy vấn của người dùng, gửi yêu cầu và nhận kết quả trả về từ các máy tìm kiếm nguồn, xếp hạng các kết quả nhận được đến lúc trả về một danh sách ảnh đã được sắp xếp cho người dùng là một quá trình được thực hiện trực tuyến nên các máy tìm kiếm ảnh lớp trên cần phải có các thuật toán xếp hạng hiệu quả, đảm bảo yêu cầu về mặt thời gian. Từ những phân tích về những khó khăn và thuận lợi ở trên, có một số phương pháp xếp hạng đã được áp dụng trong các máy tìm kiếm ảnh lớp trên. Một phương pháp đã được sử dụng trong máy tìm kiếm ảnh lớp trên MetaSEEk [11] là phân cụm các ảnh theo chủ đề và theo các đặc trưng hiển thị cùng với việc dựa vào các tùy chọn tìm kiếm và phản hồi của người dùng để tìm ra tập ảnh thích hợp nhất. Sau đó thứ hạng của một ảnh trong tập ảnh này được tính bằng cách kết hợp giữa thứ hạng của ảnh đó ở máy tìm kiếm nguồn với đánh giá về chất lượng của tập ảnh nhận được từ máy tìm kiếm nguồn mà chứa ảnh đó. Bo Luo và cộng sự trong nghiên cứu về việc sử dụng các đặc trưng của ảnh [14] cũng đã đề xuất hai phương pháp xếp hạng dựa trên cả đặc trưng văn bản và đặc trưng hiển thị của ảnh. Một phương pháp là phân cụm các ảnh dựa trên các đặc trưng về màu sắc, hình dáng từ tập ảnh khởi tạo thu được từ các máy tìm kiếm chỉ dựa trên văn bản. Phương pháp thứ hai sử dụng phản hồi của người sử dụng để xếp hạng các ảnh. Phương 45 pháp này chọn ra một số ảnh mẫu từ các cụm (các cụm này có thể thu được từ việc tìm kiếm ảnh dựa trên văn bản) và hiển thị cho người dùng lựa chọn. Dựa vào mối quan tâm của người sử dụng, hệ thống tiến hành tìm các ảnh gần giống nhất với ảnh đã được lựa chọn và sắp xếp chúng theo thứ tự giảm dần về độ tương đồng. Nhận thấy lợi ích từ việc kết hợp giữa nội dung hiển thị và văn bản của ảnh, trong khóa luận này, tôi sử dụng thuật toán xếp hạng ảnh VisualRank cho cả hai đặc trưng trên của ảnh như đã được đề cập đến ở chương hai. Tuy nhiên, quan tâm đến vấn đề thời gian thực hiện thuật toán, tôi phân các câu truy vấn thành hai trạng thái: các truy vấn cũ và truy vấn mới. Truy vấn cũ là truy vấn đã được truy vấn ở máy tìm kiếm lớp trên. Truy vấn mới là truy vấn chưa gặp bao giờ hoặc không gần giống với câu truy vấn nào có trước. Đối với một truy vấn mới, tôi tiến hành xếp hạng chỉ dựa trên văn bản rồi trả về kết quả cho người dùng. Sau đó, tôi xếp hạng lại cho các ảnh này dựa trên cả văn bản và nội dung hiển thị để sử dụng cho lần tìm kiếm sau. Quá trình xếp hạng lại này được thực hiện ngoại tuyến. Vì tận dụng được lợi thế về mặt tốc độ của việc phân tích và xử lý văn bản nên thời gian đáp ứng của hệ thống luôn ở mức cho phép. Tóm tắt chương ba Khóa luận đã trình bày về mô hình chung máy tìm kiếm lớp trên, đồng thời giới thiệu chi tiết một mô hình máy tìm kiếm ảnh lớp trên và một số phương pháp xếp hạng ảnh trong máy tìm kiếm ảnh lớp trên. Trong chương này, tôi cũng đã đưa ra một cách giải quyết vấn đề thời gian xếp hạng trong máy tìm kiếm ảnh lớp trên. Trong chương tiếp theo, khóa luận sẽ giới thiệu một mô hình tìm kiếm ảnh lớp trên ứng dụng thuật toán xếp hạng ảnh đã được trình bày ở trên và những vấn đề liên quan đến việc thử nghiệm mô hình này. 46 Chương 4. Thử nghiệm 4.1. Mô hình thử nghiệm 4.1.1. Cách tiếp cận Quá trình khảo sát và đánh giá các phương pháp xếp hạng ảnh cho thấy thuật toán VisualRank [39] [40] là một thuật toán xếp hạng ảnh đơn giản và cho hiệu quả khá cao. Tuy nhiên, cách làm của Jing và Baluja là chỉ dựa trên độ tương đồng về nội dung hiển thị của ảnh. Một cách trực quan, chúng ta có thể thấy rằng các ảnh có nội dung hiển thị gần giống nhau thì thường được người dùng đặt tên gần giống nhau, và các bình luận cũng thường về chủ đề mà nó hiển thị. Do đó, có thể thấy rằng vùng văn bản đi kèm ảnh có thể mô tả được phần nào nội dung hiển thị của ảnh. Vì vậy, trong khóa luận này, tôi sử dụng thuật toán xếp hạng ảnh VisualRank cho cả đặc trưng hiển thị và đặc trưng văn bản của ảnh. Tuy nhiên, nhận thấy rằng đặc trưng hiển thị của ảnh vẫn phản ánh nội dung ảnh một cách chân thực nhất nên trong thực nghiệm các đặc trưng hiển thị vẫn được gán cho một trọng số cao hơn. Hơn nữa, Y.Jing và S.Baluja [39] [40] chỉ ra rằng không thể tính ma trận tương đồng cho hàng tỉ bức ảnh trên web. Một cách giải quyết đơn giản là chỉ xây dựng ma trận tương đồng cho một tập N ảnh trả về đầu tiên của các máy tìm kiếm thương mại. Vì thế, tôi thực hiện áp dụng thuật toán VisulRank cho mô hình máy tìm kiếm ảnh lớp trên được đề xuất trong khóa luận. Mô hình mà khóa luận trình bày dưới đây sẽ tìm kiếm ảnh dựa trên một số máy tìm kiếm ảnh thông thường, sau đó trích xuất N ảnh trả về đầu tiên từ các máy tìm kiếm nguồn này và sử dụng thuật toán nói trên để xếp hạng lại cho chúng. Một nhược điểm lớn của việc xếp hạng dựa trên nội dung hiển thị của ảnh là thời gian tính hạng. Bởi vì việc tải các ảnh từ Web về, trích xuất các thành thành phần đặc trưng, xây dựng đồ thị tương đồng là tốn rất nhiều thời gian. Do đó, để có thể áp dụng thuật toán một cách hiệu quả vào máy tìm kiếm lớp trên, khóa luận sử dụng các cách xếp hạng khác nhau đối với mỗi trạng thái khác nhau của câu truy vấn người dùng. Câu truy vấn của người dùng được chia thành hai trạng thái: câu truy vấn mới và câu truy vấn cũ. Một câu truy vấn được xem là mới nếu nó chưa được bất kỳ người dùng nào truy vấn một lần nào trên máy tìm kiếm. Hay nói cách khác là câu truy vấn đó chưa có trong cơ sở dữ liệu. Ngược lại, câu truy là cũ nếu nó đã tồn tại trong cơ sở dữ liệu của máy tìm kiếm. Đối với câu truy vấn mới, máy tìm kiếm xếp hạng các ảnh chỉ dựa trên đặc trưng văn bản. Sau 47 đó, máy tìm kiếm lưu câu truy vấn này vào cơ sở dữ liệu và tiến hành xếp hạng lại cho các ảnh tìm được ứng với câu truy vấn dựa trên cả nội dung hiển thị và nội dung văn bản của ảnh để sử dụng cho các lần truy vấn sau. Với cách làm như vậy, máy tìm kiếm lớp trên luôn đảm bảo yêu cầu về mặt thời gian tìm kiếm cho người dùng. Để đảm bảo kết quả trả về cho người dùng luôn được cập nhật, sau một khoảng thời gian nhất định, máy tìm kiếm sẽ lấy tất cả các câu truy vấn đã có trong cơ sở dữ liệu và gửi đến các máy tìm kiếm nguồn để cập nhật cơ sở dữ liệu ảnh. Sau đó tiến hành tính hạng lại cho tập các ảnh này. Khi tính lại ma trận tương đồng cho các ảnh, để tối ưu hóa việc tính toán, ta chỉ tính ma trận tương đồng cho các ảnh mới tải về với nhau và cho các ảnh mới tải về với các ảnh đã sẵn có trong cơ sở dữ liệu. Sau đó kết hợp các ma trận này với ma trận tương đồng của các ảnh đã có từ trước thành một ma trận duy nhất. Như vậy, chúng ta đã tiết kiệm được thời gian tính ma trận tương đồng cho các ảnh đã có trong cơ sở dữ liệu. Khi số lượng câu truy vấn của người dùng là rất nhiều, việc lưu trữ các truy vấn trở thành một vấn đề cần phải được quan tâm. Nếu lưu trữ tất cả các câu truy vấn thì chi phí cho việc lưu trữ là rất lớn và việc xếp hạng lại cho tất cả các câu truy vấn có thể sẽ tốn quá nhiều thời gian và không thể kiểm soát nổi. Hơn nữa, việc lưu trữ mãi một câu truy vấn rất ít khi được sử dụng là không hiệu quả. Do đó, một giải pháp được đề ra là chỉ lưu các câu truy vấn được cho là phổ biến và cơ sở dữ liệu các câu truy vấn sẽ thường xuyên được làm mới. Có thể đặt ra một ngưỡng về số lần được sử dụng trong một khoảng thời gian của một câu truy vấn để xác định xem nó có là phổ biến hay không. Trong thời gian đầu, khi số lượng các câu truy vấn còn ít, tất cả các câu truy vấn có thể đều được coi là phổ biến. Nhằm mục đích hướng tới nhóm người dùng Việt Nam, mô hình máy tìm kiếm ảnh mà khóa luận đề xuất có tích hợp một bộ từ điển để hỗ trợ cho các truy vấn tiếng Việt. Với các truy vấn tiếng Việt, máy tìm kiếm sẽ dịch nó sang tiếng Anh rồi mới gửi đến các máy tìm kiếm nguồn. Với việc hỗ trợ cho cả truy vấn tiếng Việt và tiếng Anh, mô hình máy tìm kiếm ảnh mà khóa luận đề xuất là rất thân thiện với người dùng Việt Nam. Dưới đây là mô hình máy tìm kiếm ảnh lớp trên áp dụng phương pháp và các kỹ thuật đã đ