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


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.

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

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


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


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

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

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

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ố


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.   

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

 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








|


 







 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







.

9

4. Tính 












,


.
5. Tổng hợp 



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


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.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 ế 


ượ ạ





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 



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

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