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
AP
Cơ sở dữ liệu
Average Precision
Google CSE
HIST
Google Custom Search Engine
Hypertext Induced Topic Search
Mean Average Precision
MAP
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
Content-based visual query
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
hiển thị
2
3
Display interface
Edge
Thành phần hiển thị
Cạnh
4
5
Image tag
Thẻ ảnh
6
Inter-image Context Modeling
Intra-mage Context Modeling
Local features
Mô hình ngữ cảnh ngoại ảnh
Mô hình ngữ cảnh nội ảnh
Các thuộc tính cục bộ
Ngoại tuyến
7
8
9
Offline
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Online
Trực tuyến
Performance database
Performance score
Query dispatcher
Query translator
Random surfer model
Re-rank
Cơ sở dữ liệu hiệu suất
Điểm số hiệu suất
Bộ điều vận truy vấn
Bộ dịch truy vấn
Mô hình duyệt ngẫu nhiên
Xếp hạng lại
Scoring module
Text-based Image Ranking
Texture
Mô đun tính hạng
Xếp hạng ảnh dựa trên văn bản
Kết cấu
Title
Tiêu đề
Topic Sensitive PageRank
Visual hyperlink
Visual vocabulary
PageRank theo chủ đề
Siêu liên kết trực quan
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
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
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ị ꢮ ꢁ ꢯꢄꢃꢰ
.
ꢄꢢꢃ
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.
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
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ꢐ
11
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
12
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ì
số từ 1 đến n và đồ thị được biểu diễn bởi ma trận kề ꣅ.
13
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.
14
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
15
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
ꢕếꢤ ꢇ ꢜ ꣗
ꢛ
ꢮ ꢁ ꣙
ꢛꢏ
ꢎ1.17ꢐ
꣗
ꢛ
0
ꢕꢧượꢥ ꢉạꢇ
꣖꣖꣖꣕
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:
ꢛ
16
꣒꣡꣠ ꢁ ꢙ ꢞꢎꢥ |ꢅꢳꢐ . ꢋꢊꢕꢦꢛ꣠
ꢎ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 (<thuộc tính>,<giá trị>). Đị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 (<thuộc tính>,<giá trị>). 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 (<thuộc tính>,<giá trị>) 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
ꢊꢃ, … , ꢊꢄ.
17
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: http://www.flickr.com
2 Photobucket: http://www.photobucket.com
3 Facebook: http://www.facebook.com
18
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.
19
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
20
Tải về để xem bản đầy đủ
75 trang
02/01/2025
150
Bạn đang xem 30 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_mot_so_thuat_toan_phan_hang_anh_pho_bien_va_ap_dun.pdf
