cauvongtuyet_mc
New Member
Download Luận văn Giải pháp tính hạng trang khai thác cấu trúc Block của Web và áp dụng vào máy tìm kiếm
PageRank là phương pháp tìm kiếm 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 đưa ra 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 thông qua "chủ đề" của nó. 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. Taher H. Haveliwala [15,16] đềxuất phương
pháp mới nhằm đáp ứng yêu cầu trên, đó là phương pháp PageRank theo chủ đề
(Topic sensitive PageRank). Các tác giả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. Trong [4], thuật toán tìm kiếm trang Web có
nội dung tương tựcho một cách tiếp cận khác khi đềcập tới xem xét khía cạnh nội
dung trang Web trong bài toán tìm kiếm
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
từ khóa trong trang web và các thông tin tính hạng để tạo ra các chỉ mục tiện ích.
- Module truy vấn (query engine): module này chịu trách nhiệm nhận các yêu
cầu tìm kiếm của người sử dụng. Module này thường xuyên truy vấn cơ sở dữ liệu đặc
biệt là các bảng chỉ mục để trả về danh sách các tài liệu thỏa mãn một yêu cầu của
người dùng. Do số lượng các trang web là rất lớn, và thông thường người dùng chỉ đưa
vào một vài từ khóa trong câu truy vấn nên tập kết quả thường rất lớn. Vì vậy bộ xếp
hạng (ranking) có nhiệm vụ sắp xếp các tài liệu này theo mức độ hợp lệ với yêu cầu
tìm kiếm và hiển thị kết quả cho người sử dụng. Khi muốn tìm kiếm các trang web về
một vấn đề nào đó, người sử dụng đưa vào một số từ khóa liên quan để tìm kiếm.
Module truy vấn dựa theo các từ khóa này để tìm kiếm trong bảng chỉ mục nội dung
địa chỉ các url có chứa từ khóa này. Sau đó, module truy vấn sẽ chuyển các trang web
cho module xếp hạng để sắp xếp các kết quả theo mức độ giảm dần của tính hợp lệ
giữa trang web và câu truy vấn rồi hiển thị kết quả cho người sử dụng.
11
Chương 2. Một số thuật toán tính hạng trang điển hình
2.1. Bài toán xếp hạng trang Web trong máy tìm kiếm
Trong chương này, phần đầu chúng tui sẽ giới thiệu tổng quan về bài toán xếp
hạng trang Web trong các máy tìm kiếm, phần sau, chúng tui sẽ tập trung phân tích nội
dung các thuật toán PageRank, Modified Adaptive PageRank và Topic-sensitive
PageRank ứng dụng trong bài toán tính hạng cho các trang Web.
2.1.1. Nhu cầu
Ngày nay, người sử dụng có thể tìm kiếm thông tin đa dạng về mọi mặt của xã
hội loài người trên Internet. Tuy nhiên, do lượng thông tin trên Internet là khổng lồ,
đang từng ngày từng giờ tăng trưởng với tốc độ cao, cho nên việc giải bài toán tìm và
cung cấp thông tin được người dùng thực sự quan tâm trong thời gian cho phép đã trở
thành công việc hết sức cấp thiết. Công nghệ xây dựng công cụ tìm tin trên Internet
(điển hình là máy tìm kiếm - search engine) cần không ngừng được cải tiến nhằm bảo
đảm thoả mãn yêu cầu người dùng cả theo khía cạnh thời gian tìm kiếm nhanh lẫn tính
sự phù hợp cao giữa các trang thông tin kết quả tìm được với yêu cầu tìm kiếm của
người dùng.
Khi người dùng nhập vào một nhóm từ khóa tìm kiếm, máy tìm kiếm sẽ thực
hiện nhiệm vụ tìm kiếm và trả lại một số trang Web theo yêu cầu người dùng. Nhưng
số các trang Web liên quan đến từ khóa tìm kiếm có thể lên tời hàng vạn trang, trong
khi người dùng chỉ quan tâm đến một số ít trang trong đó, vậy việc tìm ra các trang
đáp ứng nhiều nhất yêu cầu người dùng để đưa lên đầu là cần thiết. Đó chính là công
việc tính hạng của máy tìm kiếm - sắp xếp các trang kết quả theo thứ tự giảm dần của
độ quan trọng.
Cần thiết phải xác định phép đo về "độ phù hợp" của một trang Web tìm được
với yêu cầu người dùng [1,10]. Liên quan tới việc xác định phép đo như vậy, người ta
quan tâm tới hai hướng giải quyết.. Hướng thứ nhất sử dụng độ quan trọng (được xác
định qua một đại lượng được gọi là hạng trang - page rank) 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 hướng (link) 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. Hầu hết các máy tìm kiếm sử dụng hạng
trang làm độ phù hợp của kết quả tìm kiếm với các thuật toán điển hình là PageRank,
12
Modified Adaptive PageRank [10]. Hướng thứ hai coi độ phù hợp của trang Web với
câu hỏi của người dùng không chỉ dựa trên giá trị hạng trang Web như trên mà còn
phải tính đến mối liên quan giữa nội dung trang Web đó với nội dung câu hỏi theo yêu
cầu của người dùng mà thuật toán điển hình là Topic-sensitive PageRank [15,16]. Một
số nghiên cứu khai thác khía cạnh nội dung của trang Web đối với độ phù hợp của
trang Web tìm kiếm với câu hỏi người dùng cũng được đề cập trong một số công trình
[4,7].
2.1.2. Độ quan trọng của trang web
Một số phương pháp được sử dụng để đo độ quan trọng của các trang web.
a. Các từ khóa trong văn bản: Một trang web được coi là hợp lệ nếu nó có
chứa một số hay tất cả các từ khóa trong câu truy vấn. Ngoài ra, tần số xuất hiện của
từ khóa trong trang cũng được xem xét.
b. Mức độ tương tự với câu truy vấn: một người dùng có thể chỉ định một
thông tin cần tìm bởi một câu truy vấn ngắn hay bằng các cụm từ dài hơn. Mức độ
tương tự giữa các mô tả ngắn hay dài của người dùng với nội dung mỗi trang web
được tải về có thể sử dụng để xác định tính hợp lệ của trang web đó.
c. Mức độ tương tự với trang hạt nhân: Các trang tương ứng với các URL hạt
nhân được sử dụng để đo mức độ hợp lệ của mỗi trang được tải. Các trang hạt nhân
được kết hợp với nhau thành một văn bản lớn duy nhất và mức độ gần nhau của văn
bản này với các trang web đang được duyệt được sử dụng làm điểm số của trang đó.
d. Điểm số phân lớp: một bộ phân lớp có thể được huấn luyện để xác định các
trang phù hợp với thông tin hay nhiệm vụ cần làm. Việc huấn luyện được tiến hành
sử dụng các trang hạt nhân (hay các trang web hợp lệ được chỉ định trước) như là các
ví dụ dương. Các bộ phân lớp được huấn luyện sau đó sẽ gán các điểm số nhị phân
(0,1) hay liên tiếp cho các trang web được duyệt dựa trên các ví dụ huấn luyện.
e. Đánh giá độ quan trọng dựa trên liên kết: Một crawler có thể sử dụng các
thuật toán như PageRank hay HITS, để cung cấp một sự đánh giá độ quan trọng của
mỗi trang web được duyệt. hay đơn giản hơn là chỉ sử dụng số lượng các liên kết tới
trang web đó để xác định thông tin này.
13
2.2. Thuật toán PageRank cơ bản
Trong [8], Page và Brin đã đưa ra một phương pháp nhằm giúp cho công việc
tính toán hạng trang. Phương pháp này dựa trên ý tưởng rằng: nếu có liên kết (links) từ
trang A đến trang B thì độ quan trọng của trang A cũng ảnh hưởng đến độ quan trọng
của trang B. Điều này ta cũng có thể thấy được một cách trực quan rằng, nếu trang
Web bất kì được link đến bởi trang Yahoo! chắc chắn sẽ quan trọng hơn nếu nó được
link bởi một trang Web vô danh nào đó. Giả sử ta có một tập hợp các trang Web với
các liên kết giữa chúng, khi đó ta coi tập hợp các trang Web như là một đồ thị với các
đỉnh là các trang Web và các cạnh là các liên kết giữa chúng.
2.2.1. PageRank thô
Trước tiên ta sẽ giới thiệu một định nghĩa về PageRank đơn giản thể hiện độ
quan trọng của mỗi trang Web dựa vào các liên kết, trước khi tìm hiểu một phương
pháp được áp dụng trong thực tế. Giả sử rằng các trang Web tạo thành một đồ thị 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ị đó.
Công việc tính PageRank được tiến hành như sau:
Ta đánh số các trang Web có được ...
Download miễn phí Luận văn Giải pháp tính hạng trang khai thác cấu trúc Block của Web và áp dụng vào máy tìm kiếm
PageRank là phương pháp tìm kiếm 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 đưa ra 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 thông qua "chủ đề" của nó. 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. Taher H. Haveliwala [15,16] đềxuất phương
pháp mới nhằm đáp ứng yêu cầu trên, đó là phương pháp PageRank theo chủ đề
(Topic sensitive PageRank). Các tác giả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. Trong [4], thuật toán tìm kiếm trang Web có
nội dung tương tựcho một cách tiếp cận khác khi đềcập tới xem xét khía cạnh nội
dung trang Web trong bài toán tìm kiếm
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
cáctừ khóa trong trang web và các thông tin tính hạng để tạo ra các chỉ mục tiện ích.
- Module truy vấn (query engine): module này chịu trách nhiệm nhận các yêu
cầu tìm kiếm của người sử dụng. Module này thường xuyên truy vấn cơ sở dữ liệu đặc
biệt là các bảng chỉ mục để trả về danh sách các tài liệu thỏa mãn một yêu cầu của
người dùng. Do số lượng các trang web là rất lớn, và thông thường người dùng chỉ đưa
vào một vài từ khóa trong câu truy vấn nên tập kết quả thường rất lớn. Vì vậy bộ xếp
hạng (ranking) có nhiệm vụ sắp xếp các tài liệu này theo mức độ hợp lệ với yêu cầu
tìm kiếm và hiển thị kết quả cho người sử dụng. Khi muốn tìm kiếm các trang web về
một vấn đề nào đó, người sử dụng đưa vào một số từ khóa liên quan để tìm kiếm.
Module truy vấn dựa theo các từ khóa này để tìm kiếm trong bảng chỉ mục nội dung
địa chỉ các url có chứa từ khóa này. Sau đó, module truy vấn sẽ chuyển các trang web
cho module xếp hạng để sắp xếp các kết quả theo mức độ giảm dần của tính hợp lệ
giữa trang web và câu truy vấn rồi hiển thị kết quả cho người sử dụng.
11
Chương 2. Một số thuật toán tính hạng trang điển hình
2.1. Bài toán xếp hạng trang Web trong máy tìm kiếm
Trong chương này, phần đầu chúng tui sẽ giới thiệu tổng quan về bài toán xếp
hạng trang Web trong các máy tìm kiếm, phần sau, chúng tui sẽ tập trung phân tích nội
dung các thuật toán PageRank, Modified Adaptive PageRank và Topic-sensitive
PageRank ứng dụng trong bài toán tính hạng cho các trang Web.
2.1.1. Nhu cầu
Ngày nay, người sử dụng có thể tìm kiếm thông tin đa dạng về mọi mặt của xã
hội loài người trên Internet. Tuy nhiên, do lượng thông tin trên Internet là khổng lồ,
đang từng ngày từng giờ tăng trưởng với tốc độ cao, cho nên việc giải bài toán tìm và
cung cấp thông tin được người dùng thực sự quan tâm trong thời gian cho phép đã trở
thành công việc hết sức cấp thiết. Công nghệ xây dựng công cụ tìm tin trên Internet
(điển hình là máy tìm kiếm - search engine) cần không ngừng được cải tiến nhằm bảo
đảm thoả mãn yêu cầu người dùng cả theo khía cạnh thời gian tìm kiếm nhanh lẫn tính
sự phù hợp cao giữa các trang thông tin kết quả tìm được với yêu cầu tìm kiếm của
người dùng.
Khi người dùng nhập vào một nhóm từ khóa tìm kiếm, máy tìm kiếm sẽ thực
hiện nhiệm vụ tìm kiếm và trả lại một số trang Web theo yêu cầu người dùng. Nhưng
số các trang Web liên quan đến từ khóa tìm kiếm có thể lên tời hàng vạn trang, trong
khi người dùng chỉ quan tâm đến một số ít trang trong đó, vậy việc tìm ra các trang
đáp ứng nhiều nhất yêu cầu người dùng để đưa lên đầu là cần thiết. Đó chính là công
việc tính hạng của máy tìm kiếm - sắp xếp các trang kết quả theo thứ tự giảm dần của
độ quan trọng.
Cần thiết phải xác định phép đo về "độ phù hợp" của một trang Web tìm được
với yêu cầu người dùng [1,10]. Liên quan tới việc xác định phép đo như vậy, người ta
quan tâm tới hai hướng giải quyết.. Hướng thứ nhất sử dụng độ quan trọng (được xác
định qua một đại lượng được gọi là hạng trang - page rank) 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 hướng (link) 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. Hầu hết các máy tìm kiếm sử dụng hạng
trang làm độ phù hợp của kết quả tìm kiếm với các thuật toán điển hình là PageRank,
12
Modified Adaptive PageRank [10]. Hướng thứ hai coi độ phù hợp của trang Web với
câu hỏi của người dùng không chỉ dựa trên giá trị hạng trang Web như trên mà còn
phải tính đến mối liên quan giữa nội dung trang Web đó với nội dung câu hỏi theo yêu
cầu của người dùng mà thuật toán điển hình là Topic-sensitive PageRank [15,16]. Một
số nghiên cứu khai thác khía cạnh nội dung của trang Web đối với độ phù hợp của
trang Web tìm kiếm với câu hỏi người dùng cũng được đề cập trong một số công trình
[4,7].
2.1.2. Độ quan trọng của trang web
Một số phương pháp được sử dụng để đo độ quan trọng của các trang web.
a. Các từ khóa trong văn bản: Một trang web được coi là hợp lệ nếu nó có
chứa một số hay tất cả các từ khóa trong câu truy vấn. Ngoài ra, tần số xuất hiện của
từ khóa trong trang cũng được xem xét.
b. Mức độ tương tự với câu truy vấn: một người dùng có thể chỉ định một
thông tin cần tìm bởi một câu truy vấn ngắn hay bằng các cụm từ dài hơn. Mức độ
tương tự giữa các mô tả ngắn hay dài của người dùng với nội dung mỗi trang web
được tải về có thể sử dụng để xác định tính hợp lệ của trang web đó.
c. Mức độ tương tự với trang hạt nhân: Các trang tương ứng với các URL hạt
nhân được sử dụng để đo mức độ hợp lệ của mỗi trang được tải. Các trang hạt nhân
được kết hợp với nhau thành một văn bản lớn duy nhất và mức độ gần nhau của văn
bản này với các trang web đang được duyệt được sử dụng làm điểm số của trang đó.
d. Điểm số phân lớp: một bộ phân lớp có thể được huấn luyện để xác định các
trang phù hợp với thông tin hay nhiệm vụ cần làm. Việc huấn luyện được tiến hành
sử dụng các trang hạt nhân (hay các trang web hợp lệ được chỉ định trước) như là các
ví dụ dương. Các bộ phân lớp được huấn luyện sau đó sẽ gán các điểm số nhị phân
(0,1) hay liên tiếp cho các trang web được duyệt dựa trên các ví dụ huấn luyện.
e. Đánh giá độ quan trọng dựa trên liên kết: Một crawler có thể sử dụng các
thuật toán như PageRank hay HITS, để cung cấp một sự đánh giá độ quan trọng của
mỗi trang web được duyệt. hay đơn giản hơn là chỉ sử dụng số lượng các liên kết tới
trang web đó để xác định thông tin này.
13
2.2. Thuật toán PageRank cơ bản
Trong [8], Page và Brin đã đưa ra một phương pháp nhằm giúp cho công việc
tính toán hạng trang. Phương pháp này dựa trên ý tưởng rằng: nếu có liên kết (links) từ
trang A đến trang B thì độ quan trọng của trang A cũng ảnh hưởng đến độ quan trọng
của trang B. Điều này ta cũng có thể thấy được một cách trực quan rằng, nếu trang
Web bất kì được link đến bởi trang Yahoo! chắc chắn sẽ quan trọng hơn nếu nó được
link bởi một trang Web vô danh nào đó. Giả sử ta có một tập hợp các trang Web với
các liên kết giữa chúng, khi đó ta coi tập hợp các trang Web như là một đồ thị với các
đỉnh là các trang Web và các cạnh là các liên kết giữa chúng.
2.2.1. PageRank thô
Trước tiên ta sẽ giới thiệu một định nghĩa về PageRank đơn giản thể hiện độ
quan trọng của mỗi trang Web dựa vào các liên kết, trước khi tìm hiểu một phương
pháp được áp dụng trong thực tế. Giả sử rằng các trang Web tạo thành một đồ thị 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ị đó.
Công việc tính PageRank được tiến hành như sau:
Ta đánh số các trang Web có được ...