ĐỀ 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 "

Chia sẻ: Le Xuan Binh | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

129
lượt xem 30
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: ĐỀ 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 "

ĐẠ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ị Truy vấn trực quan dựa trên nội dung 2 Content-based visual query 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
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 1
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. 2
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 3
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 4
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 , 1, 2, … Gọi là một đồ thị các trang Web. Đặt vớ i 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 5
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. 6
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ị . 1 với: Gọi a là vector 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 0.85) có ý Việc thêm “hệ số hãm” (theo thực nghiệm thường được chọn 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ị 1. PageRank vừa nêu khi 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. 7
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 8
. 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 9
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 10