Tài liệu Đề tài 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: 1
Mở đầu
Ngày nay, với những tác động to lớn và mạnh mẽ của mạng Internet tới đời
sống kinh tế, chính trị và văn hóa của con người, lĩnh vực khai phá dữ liệu Web đã và
đang trở thành lĩnh vực nghiên cứu thời sự, thu hút được sự quan tâm của rất nhiều nhà
nghiên cứu. Khai phá dữ liệu Web là điểm hội tụ của rất nhiều lĩnh vực nghiên cứu
như: cơ sở dữ liệu, truy xuất thông tin (information retrival), trí tuệ nhân tạo, nó còn là
một lĩnh vực nhỏ trong học máy (machine learning) và xử lý ngôn ngữ tự nhiên.
Một trong những lĩnh vực nghiên cứu đang rất được quan tâm hiện nay trong
khai phá Web là việc xây dựng các công cụ tìm kiếm trên Web. Bởi trong bối cảnh xã
hội thông tin ngày nay, nhu cầu nhận được các thông tin một cách nhanh chóng, chính
xác đang ngày càng trở nên cấp thiết. Để tìm ra được các thông tin có ích đối với mỗi
người dùng, đặc biệt là với những người dùng thiếu kinh nghiệm hoàn toàn không phải
là việc đơn giản. Với một công cụ tìm kiếm, khả năng ngư...
35 trang |
Chia sẻ: hunglv | Lượt xem: 1431 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
1
Mở đầu
Ngày nay, với những tác động to lớn và mạnh mẽ của mạng Internet tới đời
sống kinh tế, chính trị và văn hĩa của con người, lĩnh vực khai phá dữ liệu Web đã và
đang trở thành lĩnh vực nghiên cứu thời sự, thu hút được sự quan tâm của rất nhiều nhà
nghiên cứu. Khai phá dữ liệu Web là điểm hội tụ của rất nhiều lĩnh vực nghiên cứu
như: cơ sở dữ liệu, truy xuất thơng tin (information retrival), trí tuệ nhân tạo, nĩ cịn là
một lĩnh vực nhỏ trong học máy (machine learning) và xử lý ngơn ngữ tự nhiên.
Một trong những lĩnh vực nghiên cứu đang rất được quan tâm hiện nay trong
khai phá Web là việc xây dựng các cơng cụ tìm kiếm trên Web. Bởi trong bối cảnh xã
hội thơng tin ngày nay, nhu cầu nhận được các thơng tin một cách nhanh chĩng, chính
xác đang ngày càng trở nên cấp thiết. Để tìm ra được các thơng tin cĩ ích đối với mỗi
người dùng, đặc biệt là với những người dùng thiếu kinh nghiệm hồn tồn khơng phải
là việc đơn giản. Với một cơng cụ tìm kiếm, khả năng người dùng cĩ thể duyệt Web
và định vị được các trang Web mình quan tâm đã trở nên dễ dàng hơn nhiều.
Tuy nhiên hiện nay, do sự phát triển và thay đổi với tốc độ quá nhanh của
Internet, các cơng cụ tìm kiếm đang phải đối mặt với những bài tốn nan giải về tốc
độ. Trong đĩ cĩ bài tốn về tốc độ tính tốn hạng cho các trang Web, thực thi nhiệm
vụ tính tốn độ “quan trọng” cho các trang thơng tin kết quả tìm được so với yêu cầu
tìm kiếm của người dùng. Vì kích thước của World Wide Web là vơ cùng lớn, lên tới
hàng tỉ trang web, khơng những thế các trang Web này khơng ở trạng thái tĩnh mà luơn
luơn thay đổi. Do đĩ tính hiệu quả về thời gian càng trở nên quan trọng. Nếu phép tính
PageRank cho tập các trang web trong cơ sở dữ liệu khơng đủ nhanh, hệ thống tìm
kiếm sẽ khơng cung cấp được chất lượng tìm kiếm tốt cho người dùng.
Ý thức đây là một lĩnh vực nghiên cứu cĩ nhiều triển vọng, chúng tơi đã chọn
hướng nghiên cứu “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” cho đề tài khĩa luận tốt nghiệp của mình. Khĩa luận tập
trung nghiên cứu bài tốn tính hạng trang web (PageRank) trong các máy tìm kiếm:
cấu trúc, thuật tốn cũng như các tiêu chuẩn đánh giá quá trình này. Chúng tơi cũng đã
áp dụng các lý thuyết trên để đi sâu phân tích mã nguồn, tìm hiểu cơ chế thực thi quá
trình tính PageRank trong máy tìm kiếm Vinahoo, một máy tìm kiếm tiếng Việt mã
nguồn mở với nhiều tính năng ưu việt. Từ việc nghiên cứu này, chúng tơi đã đề xuất
một giải pháp áp dụng khái niệm thành phần liên thơng trong ma trận liên kết Web
trong Vinahoo, đồng thời thực hiện việc cài đặt thử nghiệm trên mã nguồn của máy
tìm kiếm này.
Nội dung của khĩa luận được tổ chức thành bốn chương với nội dung được
giới thiệu như dưới đây.
2
Chương 1 với tên gọi “Tổng quan về khai phá dữ liệu web và máy tìm kiếm”
trình bày về những nội dung nghiên cứu cơ bản của khai phá web, những thuận lợi và
khĩ khăn trong lĩnh vực này. Phần cuối của chương này trình bày các thành phần cơ
bản của một máy tìm kiếm.
“Một số thuật tốn tính hạng trang điển hình” là tiêu đề của chương 2. Phần
đầu chương này giới thiệu tổng quan về bài tốn xêp hạng trang Web trong máy tìm
kiếm và thuật tốn tính PageRank cơ bản. Việc phân tích nhu cầu tăng tốc độ tính tốn
PageRank trong máy tìm kiếm, một số thuật tốn cải tiến từ phương pháp PageRank
cùng với đánh giá được trình bày trong phần cuối của chương.
Chương 3 với tên gọi “Thuật tốn sử dụng cấu trúc Block theo thành phần
liên thơng” tập trung nghiên cứu về giải pháp khai thác cấu trúc Web. Chương này
giới thiệu khái niệm, một số vấn đề về lý thuyết, chứng minh và đánh giá thuật tốn
CCP sử dụng cấu trúc này.
Chương 4 với tiêu đề “Giải pháp tính hạng trang cải tiến cho máy tìm kiếm
Vinahoo” giới thiệu thành phần tính PageRank trong module đánh chỉ số của
Vinahoo, các cải tiến, cài đặt và đánh giá kết quả thực nghiệm.
3
Chương 1. Tổng quan về khai phá dữ liệu Web và máy
tìm kiếm
1.1. Khai phá dữ liệu Web
1.1.1. Tổng quan về khai phá dữ liệu Web
Ngày nay, sự phát triển nhanh chĩng của mạng Internet và Intranet đã sinh ra
một khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Trong những
năm gần đây Intrnet đã trở thành một trong những kênh về khoa học, thơng tin kinh tế,
thương mại và quảng cáo. Một trong những lý do cho sự phát triển này là chi phí thấp
để duy trì một trang Web trên Internet. So sánh với những dịch vụ khác như đăng tin
hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web "địi" rẻ hơn rất nhiều và
cập nhật nhanh chĩng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Cĩ
thể nĩi Internet như là cuốn từ điển Bách khoa tồn thư với nội dung và hình thức đa
dạng. Nĩ như một xã hội ảo, nĩ bao gồm các thơng tin về mọi mặt của đời sống kinh
tế, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh ...
Hình 1. Khai phá Web, cơng việc khơng dễ dàng
Tuy nhiên, Internet là một mơi trường đa phương tiện động bao gồm sự kết
hợp của các cơ sở dữ liệu khơng đồng nhất, các chương trình và các giao tiếp người
dùng. Rõ ràng, khai phá dữ liệu text chỉ là một lĩnh vực nhỏ trong mơi trường này.
Khai phá dữ liệu trên Internet, hay thường được gọi là khai phá web ngồi việc cần
khai phá được nội dung các trang văn bản, cịn phải khai thác được các nguồn lực nĩi
trên cũng như mối quan hệ giữa chúng. Khai phá Web, sự giao thoa giữa khai phá dữ
liệu và Word-Wide-Web, đang phát triển mạnh mẽ và bao gồm rất nhiều lĩnh vực
nghiên cứu như cơ sở dữ liệu, trí tuệ nhân tạo, truy xuất thơng tin (information
retrival) và nhiều lĩnh vực khác. Các cơng nghệ Agent-base, truy xuất thơng tin dựa
trên khái niệm (concept-based), truy xuất thơng tin sử dụng case-base reasoning và
Tri thức
WWW
4
tính hạng văn bản dựa trên các đặc trưng (features) siêu liên kết... thường được xem là
các lĩnh vực nhỏ trong khai phá web. Khai phá Web vẫn chưa được định nghĩa một
cách rõ ràng và các chủ đề trong đĩ vẫn tiếp tục được mở rộng. Tuy vậy, chúng ta cĩ
thể hiểu khai phá web như việc: trích ra các thành phần được quan tâm hay được
đánh giá là cĩ ích cùng các thơng tin tiềm năng từ các tài nguyên hoặc các hoạt động
liên quan tới World-Wide Web[9]. Hình 2 thể hiện một sự phân loại các lĩnh vực
nghiên cứu quen thuộc trong khai phá Web. Người ta thường phân khai phá web thành
3 lĩnh vực chính: khai phá nội dung web (web content mining), khai phá cấu trúc web
(web structure mining) và khai phá sử dụng web (web usage mining).
Hình 2: Các nội dung trong khai phá Web
1.1.2. Các lĩnh vực của khai phá dữ liệu Web
1.1.2.1 Khai phá nội dung Web
Phần lớn các tri thức của World-Wide Web được chứa trong nội dung văn bản.
Khai phá nội dung web (web content mining) là các quá trình xử lý để lấy ra các tri
thức từ nội dung các trang văn bản hoặc mơ tả của chúng. Cĩ hai chiến lược khai phá
nội dung web: một là khai phá trực tiếp nội dung của trang web, và một là nâng cao
khả năng tìm kiếm nội dung của các cơng cụ khác như máy tìm kiếm.
- Khai phá nội dung trang web(Web Page summarization): liên quan tới việc
truy xuất các thơng tin từ các văn bản cĩ cấu trúc, văn bản siêu liên kết, hay các văn
bản bán cấu trúc. Lĩnh vực này liên quan chủ yếu tới việc khai phá bản thân nội dung
các văn bản.
KHAI PHÁ DỮ
LIỆU WEB
Khai phá nội
dung Web
Khai phá cấu
trúc Web
Khai phá sử
dụng Web
Khai phá nội
dung trang Web
Tối ưu kết
quả trả về
Khai phá các
mẫu truy cập
Phân tích các xu
hướng cá nhân
5
- Tối ưu kết quả trả về (search engine result summarization): Tìm kiếm trong
kết quả. Trong các máy tìm kiếm, sau khi đã tìm ra những trang Web thoả mãn yêu
cầu người dùng, cịn một cơng việc khơng kém phần quan trọng, đĩ là phải sắp xếp,
chọn lọc kết quả theo mức độ hợp lệ với yêu cầu người dùng. Quá trình này thường sử
dụng các thơng tin như tiêu đề trang, URL, content-type, các liên kết trong trang web...
để tiến hành phân lớp và đưa ra tập con các kết quả tốt nhất cho người dùng.
1.1.2.2. Khai phá cấu trúc web
Nhờ vào các kết nối giữa các văn bản siêu liên kết, World-Wide Web cĩ thể
chứa đựng nhiều thơng tin hơn là chỉ các thơng tin ở bên trong văn bản. Ví dụ, các liên
kết trỏ tới một trang web chỉ ra mức độ quan trọng của trang web đĩ, trong khi các liên
kết đi ra từ một trang web thể hiện các trang cĩ liên quan tới chủ đề đề cập trong trang
hiện tại. Và nội dung của khai phá cấu trúc Web (web structure mining) là các quá
trình xử lý nhằm rút ra các tri thức từ cách tổ chức và liên kết giữa các tham chiếu của
các trang web.
1.1.2.3 Khai phá sử dụng web
Khai phá sử dụng web (web usage mining) hay khai phá hồ sơ web (web log
mining) là việc xử lý để lấy ra các thơng tin hữu ích trong các hồ sơ truy cập Web.
Thơng thường các web server thường ghi lại và tích lũy các dữ liệu về các tương tác
của người dùng mỗi khi nĩ nhận được một yêu cầu truy cập. Việc phân tích các hồ sơ
truy cập web của các web site khác nhau sẽ dự đốn các tương tác của người dùng khi
họ tương tác với Web cũng như tìm hiểu cấu trúc của Web, từ đĩ cải thiện các thiết kế
của các hệ thống liên quan. Cĩ hai xu hướng chính trong khai phá sử dụng web là
General Access Pattern Tracking và Customizied Usage tracking.
- Phân tích các mẫu truy cập (General Access Pattern tracking): phân tích các
hồ sơ web để biết được các mẫu và các xu hướng truy cập. Các phân tích này cĩ thể
giúp cấu trúc lại các site trong các phân nhĩm hiệu quả hơn, hay xác định các vị trí
quảng cáo hiệu quả nhất, cũng như gắn các quảng cáo sản phẩm nhất định cho những
người dùng nhất định để đạt được hiệu quả cao nhất...
- Phân tích các xu hướng cá nhân (Cusomized Usage tracking): Mục đích là để
chuyên biệt hĩa các web site cho các lớp đối tượng người dùng. Các thơng tin được
hiển thị, độ sâu của cấu trúc site và định dạng của các tài nguyên, tất cả đều cĩ thể
chuyên biệt hĩa một cách tự động cho mỗi người dùng theo thời gian dựa trên các mẫu
truy cập của họ.
6
1.1.3. Khĩ khăn của khai phá Web
World Wide Web là một hệ thống rất lớn phân bố rộng khắp, cung cấp thơng
tin trên mọi lĩnh vực khoa học, xã hội, thương mại, văn hĩa,... Web là một nguồn tài
nguyên giàu cĩ cho Khai phá dữ liệu. Những quan sát sau đây cho thấy Web đã đưa ra
những thách thức lớn cho cơng nghệ Khai phá dữ liệu [6].
1.1.3.1. Web quá lớn để tổ chức thành kho dữ liệu phục vụ Dataming
Các CSDL truyền thống thì cĩ kích thước khơng lớn lắm và thường được lưu
trữ tập trung, trong khi đĩ kích thước Web rất lớn, tới hàng terabytes và thay đổi liên
tục, khơng những thế cịn phân tán trên rất nhiều máy tính khắp nơi trên thế giới. Một
vài nghiên cứu về kích thước của Web[6] đã đưa ra các số liệu như sau: Hiện nay trên
Internet cĩ khoảng hơn một tỷ các trang Web được cung cấp cho người sử dụng. Kích
thước trung bình của mỗi trang là 5-10KB thì tổng kích thước của WWW ít nhất là 10
terabyte. Cịn tỷ lệ tăng của các trang Web thì thật sự gây ấn tượng. Hai năm gần đây
số các trang Web tăng gấp đơi và cịng tiếp tục tăng trong hai năm tới. Nhiều tổ chức
và xã hội đặt hầu hết những thơng tin cơng cộng của họ lên Web. Như vậy việc xây
dựng một kho dữ liệu (datawarehouse) để lưu trữ, sao chép hay tích hợp các dữ liệu
trên Web là gần như khơng thể.
1.1.3.2. Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài
liệu văn bản truyền thống khác
Các dữ liệu trong các CSDL truyền thống thì thường là loại dữ liệu đồng nhất
(về ngơn ngữ, định dạng,…), cịn dữ liệu Web thì hồn tồn khơng đồng nhất. Dữ liệu
Web bao gồm rất nhiều loại ngơn ngữ khác nhau (cả ngơn ngữ diễn tả nội dung lẫn
ngơn ngữ lập trình), nhiều loại định dạng khác nhau (text, HTML, PDF, hình ảnh, âm
thanh,…), nhiều loại từ vựng khác nhau (địa chỉ email, các liên kết, các mã nén
(zipcode), số điện thoại...). Nĩi cách khác, các trang Web thiếu một cấu trúc thống
nhất. Chúng được coi như một thư viện kỹ thuật số rộng lớn, tuy nhiên số lượng khổng
lồ các tài liệu trong thư viện thì khơng được sắp xếp theo một tiêu chuẩn đặc biệt nào,
khơng theo phạm trù nào,... Điều này là một thử thách rất lớn cho việc tìm kiếm thơng
tin cần thiết trong một thư viện như thế.
1.1.3.3. Web là một nguồn tài nguyên thơng tin cĩ độ thay đổi cao
Web khơng chỉ cĩ thay đổi về độ lớn mà thơng tin trong chính các trang Web
cũng được cập nhật liên tục. Theo kết quả nghiên cứu [6] hơn 500.000 trang Web
7
trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng hơn 10 ngày thì
50% các trang trong tên miền đĩ biến mất, nghĩa là địa chỉ URL của nĩ khơng cịn tồn
tại nữa. Tin tức, thị trường chứng khốn, các cơng ty quản cáo và trung tâm phục vụ
Web thường xuyên cập nhật trang Web của họ. Thêm vào đĩ sự kết nối thơng tin và sự
truy cập bản ghi cũng được cập nhật.
1.1.3.4. Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng
Internet hiện nay nối với khoảng 50 triệu trạm làm việc [6], và cộng đồng
người dùng vẫn đang nhanh chĩng lan rộng. Mỗi người dùng cĩ một kiến thức, mối
quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng khơng cĩ kiến thức tốt về
cấu trúc mạng thơng tin, hoặc khơng cĩ ý thức cho những tìm kiếm, rất dễ bị "lạc" khi
trong khối dữ liệu khổng lồ của mạng hoặc sẽ chán khi tìm kiếm mà chỉ nhận những
mảng thơng tin khơng mấy hữu ích.
1.1.3.5. Chỉ một phần rất nhỏ của thơng tin trên Web là thực sự hữu ích
Theo thống kê [6], 99% của thơng tin Web là vơ ích với 99% người dùng
Web. Trong khi những phần Web khơng được quan tâm lại bị búi vào kết quả nhận
được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web như thế nào để nhận được
trang web chất lượng cao nhất theo tiêu chuẩn của người dùng?
Như vậy chúng ta cĩ thể thấy các điểm khác nhau giữa việc tìm kiếm trong
một CSDL truyền thống với vviệc tìm kiếm trên Internet. Những thách thức trên đã
đẩy mạnh việc nghiên cứu khai phá và sử dụng tài nguyên trên Internet.
1.1.4. Thuận lợi của khai phá Web
Bên cạnh những thử thách trên, khai phá Web cũng cĩ những thuận lợi:
1. Web bao gồm khơng chỉ cĩ các trang mà cịn cĩ cả các liên kết trỏ từ trang
này tới trang khác. Khi một tác giả tạo một liên kết từ trang của ơng ta tới một trang A
cĩ nghĩa là A là trang cĩ hữu ích với vấn đề đang bàn luận. Nếu một trang càng nhiều
liên kết từ trang khác trỏ đến chứng tỏ trang đĩ quan trọng. Vì vậy các thơng tin liên
kết trang sẽ cung cấp một lượng thơng tin giàu cĩ về mối liên quan, chất lượng, và cấu
trúc của nội dung trang Web, và vì thế là một nguồn tài nguyên lớn cho khai phá Web.
2. Một máy chủ Web thường đăng ký một bản ghi đầu vào (Weblog entry) cho
mọi lần truy cập trang Web. Nĩ bao gồm địa chỉ URL, địa chỉ IP, timestamp. Dữ liệu
Weblog cung cấp lượng thơng tin giàu cĩ về những trang Web động. Thực hiện phân
8
tích các hồ sơ truy cập này ta cĩ thể rút ra những thống kê về xu hướng truy cập Web,
cấu trúc Web và nhiều thơng tin hữu ích khác.
1.2. Tổng quan về máy tìm kiếm
1.2.1. Nhu cầu
Như đã đề cập ở phần trên, Internet là một kho thơng tin khổng lồ và phức tạp.
Thơng tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Tuy nhiên
cùng với sự đa dạng và số lượng lớn thơng tin như vậy đã nảy sinh vấn đề quá tải
thơng tin. Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng như
số lượng của các trang Web trên Internet thì vấn đề tìm kiếm thơng tin đối với người
sử dụng lại ngày càng khĩ khăn. Đối với mỗi người dùng chỉ một phần rất nhỏ thơng
tin là cĩ ích, chẳng hạn cĩ người chỉ quan tâm đến trang Thể thao, Văn hĩa mà khơng
mấy khi quan tâm đến Kinh tế. Người ta khơng thể tìm tự kiếm địa chỉ trang Web chứa
thơng tin mà mình cần, do vậy địi hỏi cần phải cĩ một trình tiện ích quản lý nội dung
của các trang Web và cho phép tìm thấy các địa chỉ trang Web cĩ nội dung giống với
yêu cầu của người tìm kiếm.
Định nghĩa [14]:Máy tìm kiếm (search engine) là một hệ thống được xây dựng
nhằm tiếp nhận các yêu cầu tìm kiếm của người dùng (thường là một tập các từ khĩa),
sau đĩ phân tích yêu cầu này và tìm kiếm thơng tin trong cơ sở dữ liệu được tải xuống
từ Web và đưa ra kết quả là các trang web cĩ liên quan cho người dùng.
Cụ thể, người dùng gửi một truy vấn, dạng đơn giản nhất là một danh sách các
từ khĩa, và máy tìm kiếm sẽ làm việc để trả lại một danh sách các trang Web cĩ liên
quan hoặc cĩ chứa các từ khĩa đĩ. Phức tạp hơn, thì truy vấn là cả một văn bản hoặc
một đoạn văn bản hoặc nội dung tĩm tắt của văn bản. Một số máy tìm kiếm điển hình
hiện nay: Yahoo, Google, Alvista, ASPSeek...
1.2.2. Cấu trúc cơ bản và hoạt động của một máy tìm kiếm
Một máy tìm kiếm cĩ thể được xem như là một ví dụ của hệ thống truy xuất
thơng tin Information Retrival (IR)[14]. Một hệ thống truy xuất thơng tin IR thường
tập trung vào việc cải thiện hiệu quả thơng tin được lấy ra bằng cách sử dụng việc
đánh chỉ số dựa trên các từ khĩa (term-base indexing)[11] và kỹ thuật tổ chức lại các
câu truy vấn (query refomulation technique)[12]. Quá trình xử lý các văn bản dựa trên
từ khĩa ban đầu trích ra các từ khĩa trong văn bản sử dụng một từ điển được xây dựng
9
trước, một tập các từ dừng, và các qui tắc (stemming rule)[14] chuyển các hình thái
của từ về dạng từ gốc. Sau khi các từ khĩa đã được lấy ra, các hệ thống thường sử
dụng phương pháp TF-IDF (hoặc biến thể của nĩ) để xác định mức độ quan trọng của
các từ khĩa. Do đĩ, một văn bản cĩ thể được biểu diễn bởi một tập các từ khĩa và độ
quan trọng của chúng. Mức độ tương tự đo được giữa một câu truy vấn và một văn bản
chính bằng tích vơ hướng giữa hai vector các từ khĩa tương ứng. Để thể hiện mức độ
hợp lệ của các văn bản và câu truy vấn, các văn bản được lấy ra được biểu diễn dưới
dạng một danh sách được xếp hạng dựa trên độ đo mức độ tương tự giữa chúng và câu
truy vấn.
Hình 3 miêu tả cấu trúc cơ bản của một máy tìm kiếm. Mặc dù trong thực tế,
mỗi máy tìm kiếm cĩ cách thực thi riêng, nhưng về cơ bản vẫn dựa trên cơ chế hoạt
động như được mơ tả.
Hình 3: Mơ hình cấu trúc của một máy tìm kiếm
- Module dị tìm (crawler): là các chương trình cĩ chức năng cung cấp dữ liệu
cho các máy tìm kiếm hoạt động. Module này thực hiện cơng việc duyệt Web, nĩ đi
theo các liên kết trên các trên Web để thu thập nội dung các trang Web. Các chương
trình dị tìm được cung cấp các địa chỉ URL xuất phát, đọc các trang web tương ứng,
phân tích và tìm ra các URL cĩ trong các trang web đĩ. Sau đĩ bộ tìm duyệt cung cấp
các địa chỉ URL kết quả cho bộ điều khiển dị tìm (crawl control). Bộ điều khiển này
sẽ quyết định xem URL nào sẽ được duyệt tiếp theo và gửi lại kết quả cho bộ dị tìm.
Kho trang web
Bé t×m
duyƯt
10
Các bộ dị tìm sau khi tải các trang web sẽ lưu kết quả vào kho trang web (page
repository). Quá trình này lặp lại cho tới khi đạt tới điều kiện kết thúc.
- Module đánh chỉ mục (indexing): module này cĩ nhiệm vụ duyệt nội dung
các trang web đã được tải về, đánh chỉ mục cho các trang này bằng cách ghi lại địa chỉ
URL của các trang web cĩ chứa các từ trong cơ sở dữ liệu. Kết quả sinh ra một bảng
chỉ mục rất lớn. Nhờ cĩ bảng chỉ mục này, máy tìm kiếm cung cấp tất cả các địa chỉ
URL của các trang web theo các truy vấn bằng từ khĩa của người dùng. Thơng thường
bộ tạo chỉ mục tạo ra chỉ mục nội dung và chỉ mục cấu trúc (structure index). Chỉ mục
nội dung chứa thơng tin về các từ xuất hiện trong các trang web. Chỉ mục cấu trúc thể
hiện mối liên kết giữa các trang web, tận dụng được đặc tính quan trọng của dữ liệu
web là các liên kết. Nĩ là một dạng đồ thị gồm các nút và các cung, mỗi nút trong đồ
thị tương ứng với một trang web, mỗi cung nối từ nút A tới nút B tương ứng là siêu
liên kết từ trang web A đến trang web B.
- Module phân tích tập (Collection Analysis Module) hoạt động dựa vào
thuộc tính module truy vấn. Ví dụ nếu bộ truy vấn chỉ địi hỏi việc tìm kiếm hạn chế
trong một số website đặc biệt, hoặc giới hạn trong một tên miền thì cơng việc sẽ nhanh
và hiệu quả hơn. Module này sử dụng thơng tin từ hai loại chỉ mục cơ bản (chỉ mục
nội dung và chỉ mục cấu trúc) do module đánh chỉ số cung cấp cùng với thơng tin các
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 tốn tính hạng trang điển hình
2.1. Bài tốn xếp hạng trang Web trong máy tìm kiếm
Trong chương này, phần đầu chúng tơi sẽ giới thiệu tổng quan về bài tốn xếp
hạng trang Web trong các máy tìm kiếm, phần sau, chúng tơi sẽ tập trung phân tích nội
dung các thuật tốn PageRank, Modified Adaptive PageRank và Topic-sensitive
PageRank ứng dụng trong bài tố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 lồ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 tố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 tố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 tố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 tố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ố hoặc tất cả các từ khĩa trong câu truy vấn. Ngồ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 hoặc 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 (hoặc 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) hoặc 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 tốn như PageRank hoặc HITS, để cung cấp một sự đánh giá độ quan trọng của
mỗi trang web được duyệt. Hoặc đơ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 tố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 tố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 từ 1, 2,…,m.
Gọi N(i) là số liên kết ra ngồi của trang thứ i.
Gọi B(i) là số các trang Web cĩ liên kết đến trang i.
Khi đĩ giá trị PageRank r(i) ứng với trang i được tính như sau
∑∈= )( )()()( iBj jNjrir
Nếu gọi r = [r(1),r(2), ... , r(n)] là vector PageRank, trong đĩ các thành phần là
các hạng tương ứng của các trang Web, ta viết lại các phương trình này dưới dạng ma
trận r = ATr trong đĩ:
A là ma trận kích thước n x n trong đĩ các phần tử
14
aij = N j
1
nếu cĩ liên kết từ i đến j
aij = 0 nếu ngược lại
Như vậy ta cĩ thể thấy vectơ PageRank r chính là vectơ riêng của ma trận AT
Như ta đã thấy ỏ trên, việc tính tốn mức độ quan trọng hay hạng trang theo
phương pháp PageRank cĩ thể được thực hiện thơng qua việc phân tích các liên kết tới
trang Web đĩ. Nếu nĩ cĩ những liên kết quan trọng trỏ tới thì rất cĩ thể trang đĩ là
trang quan trọng. Tuy nhiên việc tính tốn hạng trang lại phụ thuộc vào việc biết được
hạng của các trang Web cĩ liên kết tới nĩ, và như vậy muốn tính hạng trang này ta
phải biết được hạng của trang liên kết tới nĩ, điều này cĩ thể gây ra việc lặp vơ hạn rất
tốn kém. Khắc phục bằng cách đưa về các vectơ hạng, ta cĩ thể tính tốn được các
hạng trang thơng qua việc tính tốn vectơ riêng của ma trận AT. Trong đại số tuyến
tính cĩ khá nhiều các phương pháp cĩ thể tính được vectơ riêng của ma trận tuy nhiên
cĩ một phương pháp khá tiện và cĩ thể được áp dụng vào việc tính tốn vectơ
PageRank là phương pháp lặp. Các cơng việc tính tốn sẽ được làm như sau:
1. s Å vector bất kì
2. r Å AT s
3. nếu ||r-s||<e thì kết thúc, khi đĩ ta nhận được r là vector PageRank
nếu khơng thì sÅr, quay lại bước 2.
Diễn giải thuật tốn trên như sau: bước đầu tiên ta sẽ gán cho vectơ PageRank
tồn cục một giá trị bất kì, sau đĩ lấy vectơ đĩ nhân với ma trận AT được một vectơ
mới giả sử là r(1), lại tiếp tục nhân r(1) với ma trận AT, tiếp tục quá trình này cho đến
khi dãy {r(i)} hội tụ – nghĩa là tất cả các phần tử của r(i) thay đổi với một sai số nhỏ hơn
một giá trị e bất kỳ. Khi đĩ ta cĩ thể nhận được một vectơ PageRank “tương đối” đại
diện cho các trang Web ta xét.
15
2.2.2. PageRank trong thực tế
Trong thực tế, khơng phải lúc nào chúng ta cũng gặp trường hợp các trang
Web lập thành một đồ thị liên thơng. Trên WWW cĩ rất nhiều các trang Web mà
chúng khơng hề cĩ trang nào liên kết tới (Web leak) hay khơng liên kết tới trang Web
nào khác (Web sink). Đối với những trang khơng cĩ liên kết tới trang khác, như ví dụ
ở hình vẽ 3, cụm (4,5) là Websink, người dùng khi đi đến nút (4,5) sẽ bị tắc, khi đĩ
các trang Web sẽ cĩ hạng r1=r2=r3=0, r4=r5=0.5, cịn nếu bỏ nút 5 cùng các liên kết
thì trang 4 là Web leak, dẫn đến hạng của mọi trang dẫn đến 4 đều = 0. Điều này
khơng phù hợp thực tế, vì bất kì trang Web nào ra đời cũng đều cĩ tính quan trọng của
nĩ, cho dù trang đĩ của một cá nhân thì nĩ cũng quan trọng với riêng người đĩ. Do
vậy cần phải sửa đổi cơng thức PageRank bằng cách thêm vào một hệ số hãm d, cơng
thức PageRank được sửa đổi cĩ dạng như sau:
nd
B
jNjrdir
i
j
/)1()()(*)( −+= ∑
∈
Việc thêm “ hệ số hãm “ d ( thường được chọn d=0.85 ) cĩ ý nghĩa như sau: bổ
sung thêm giá trị PageRank vào cho các trang khơng cĩ link ra ngồi. Ta cũng nhận
thấy khi d=1 thì cơng thức sẽ quay lại trường hợp PageRank thơ.
Page và Brin [8] cũng đã chỉ ra rằng các giá trị này cĩ thể hội tụ khá nhanh,
trong vịng khoảng 100 vịng lặp chúng ta cĩ thể nhận được kết quả với sai số khơng
lớn lắm.
1
4
2 3
5
Hình 4: Một ví dụ liên kết Web
16
2.3. Một số thuật tốn khác
Phần này chúng tơi xin đề cập tới vấn đề liên quan tới hiệu năng tính tốn của
thuật tốn PageRank bao gồm khả năng tăng tốc độ tính tốn và một trong các phương
pháp tăng tốc độ tính tốn hiện nay là Modified Adaptive PageRank.
2.3.1. Nhu cầu tăng tốc độ tính tốn PageRank
PageRank là một trong những phương pháp thịnh hành nhất và cĩ hiệu quả
nhất trong cơng việc tìm kiếm các thơng tin trên Internet. Như chúng ta đã xem xét ở
trên, PageRank sẽ tìm cách đánh giá hạng các trang thơng qua các liên kết giữa các
trang Web. Việc đánh giá này cĩ thể được thực hiện thơng qua việc tính tốn vectơ
riêng của ma trận kề biểu diễn cho các trang Web. Nhưng với kích cỡ khổng lồ của
mình, WWW cĩ thể làm cho cơng việc tính tốn này tốn rất nhiều ngày. Cần phải tăng
được tốc độ tính tốn này lên vì hai lí do:
- Cần cĩ được kết quả sớm để đưa được những thơng tin sang các bộ phận khác
trong cùng máy tìm kiếm, việc tính tốn nhanh vectơ PageRank cĩ thể giúp giảm thiểu
thời gian chết 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í do cả người dùng quan tâm, do vậy cần phải tính tốn nhiều
vectơ PageRank, mỗi vectơ hướng tới một tiêu đề khác nhau. Việc tính tốn nhiều
vectơ này cũng địi hỏi mỗi vectơ thành phần được tính tốn nhanh chĩng.
Việc tăng cường tốc độ tính tốn cĩ thể vấp phải nhiều khĩ khăn kích thước
của WWW. Vì vậy trong [11], đã giới thiệu một cách để giúp đỡ cho quá trình tính
tốn được nhanh hơn. Phương pháp này xuất phát từ ý tưởng sau: khi cài đặt chương
trình và chạy, độ quan trọng các trang Web cĩ tốc độ hội tụ khơng giống nhau, cĩ
những trang Web độ quan trọng hội tụ nhanh cĩ trang lại cĩ độ hội tụ chậm. Vậy
chúng ta cĩ thể tận dụng những trang hội tụ trước 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 nữa. Như vậy ta cĩ thể giảm được những
tính tốn dư thừa và làm tăng được hiệu suất tính tốn của hệ thống. Phương pháp này
là một cải tiến của phương pháp PageRank.
17
2.3.2. Thuật tốn Modified Adaptive PageRank
2.3.2.1. Thuật tốn Adaptive PageRank
Giả sử việc tính tốn vectơ PageRank của chúng ta đã được thực hiện đến vịng
lặp thứ k. Ta cần tính tốn x(k+1) = Ax(k), (*)
Gọi C là tập hợp các trang Web đã hội tụ đến mức e nào đĩ và N là tập hợp các
trang Web chưa hội tụ. Khi đĩ ta chia ma trận A ra làm hai ma trận con, AN cỡ mxn 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 AC cỡ (n-m)xn là
ma trận kề đại diện cho những liên kết của (n-m) trang đã hội tụ.
Tương tự, ta cũng chia vectơ x(k) ra thành 2 vectơ x kN )( tương ứng với những
thành phần của x(k) đã hội tụ cịn x kC )( tương ứng với những thành phần của x(k) chưa
hội tụ. Vậy ta cĩ thể viết lại ma trận A và x(k) dưới dạng như sau :
⎟⎟⎠
⎞
⎜⎜⎝
⎛
=
x
xx k
C
k
Nk
)(
)(
)( và ⎟⎟⎠
⎞
⎜⎜⎝
⎛=
A
AA
C
N
Ta cĩ thể viết lại phương trình (*) như sau:
⎟⎟⎠
⎞
⎜⎜⎝
⎛
•⎟⎟⎠
⎞
⎜⎜⎝
⎛=⎟⎟⎠
⎞
⎜⎜⎝
⎛
+
+
x
x
A
A
x
x
k
C
k
N
C
N
k
C
k
N
)(
)(
)1(
)1(
Do những thành phần của x kC )( đã hội tụ do vậy ta khơng cần tính x kC )1( + nữa và
như vậy việc tính tốn sẽ được giảm đi do khơng phải tính tốn xA kC )( nữa mà chỉ
cần thực hiện xN(k+1)= ANx(k)
2.3.2.2 . Thuật tốn Modified Adaptive PageRank
Trong thuật tốn Adaptive PageRank tốc độ tính tốn được tăng nhanh lên do ta
đã giảm đi được những tính tốn dư thừa bằng cách khơng tính những giá trị đã hội tụ.
Trong phần này ta sẽ nghiên cứu sâu hơn về cách giảm đi những tính tốn dư thừa.
Chúng ta cĩ thể viết ma trận A một cách rõ ràng hơn như sau
⎟⎟⎠
⎞
⎜⎜⎝
⎛=
AA
AAA
CCCN
NCNN
18
Với ANN là ma trận kề đại diện cho những liên kết của các trang chưa hội tụ tới
những trang chưa hội tụ, ACN là ma trận kề đại diện cho những liên kết của các trang
đã hội tụ tới những trang chưa hội tụ và tương tự cho các phần khác ANC,ACC.Vì xC và
ANCxC khơng thay đổi sau vịng lặp thứ k vì chúng đã hội tu, nên phương trình (*) cĩ
thể được viết lại :
xAxAx kCCNkNNNkN )()()1( +=+
Ma trận A đã được chia nhỏ ra do vậy cơng việc tính tốn cĩ thể được giảm đi
một cách đáng kể. Những kết quả thực nghiệm trong [11] cho thấy tốc độ tính tốn cĩ
thể được cải thiện khoảng 30%.
Theo [11], việc giảm những tính tốn của phương pháp PageRank giúp chúng ta
cĩ thể tính tốn nhanh hơn tuy nhiên đây chưa phải là đích đến cuối cùng cần đạt
được.
2.3.3. Topic-sensitive PageRank
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 phải đư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 tố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 tốn tìm kiếm.
Thuật tốn gồm hai bước được mơ tả sơ bộ như dưới đây.
Tại bước đầu tiên, các trang Web trong cơ sở dữ liệu được phân thành các lớp
theo các chủ đề c1,c2,...,cn ; gọi Tj là tập hợp những trang Web theo chủ đề cj. Mỗi lớp
19
tương ứng với một vector PageRank của chủ đề mà mỗi thành phần là giá trị
PageRank của mỗi trang trong lớp.
Vector PageRank của chủ đề được tính như bình thường tuy nhiên thay vì sử
dụng [ ]Nv n/1 1×→ = thuật tốn sử dụng vector jv v=
r uur
trong đĩ
(1)
Gọi
→
jD là vector các từ khố, gồm tất cả các từ khố trong các tài liệu của các
chủ đề; Djt là số lần xuất hiện của từ khố t trong tất cả các tài liệu của chủ đề cj.
Bước thứ hai được thực hiện trong thời gian hỏi-đáp. Giả sử cĩ truy vấn q, gọi
q’ là phạm vi ngữ cảnh của q. Mơ tả sơ bộ khái niệm phạm vi ngữ cảnh như sau. Với
truy vấn thơng thường (từ hộp thoại) thì q’ chính là q. Trường hợp truy vấn q được đặt
bằng cách tơ sáng từ khố q trong trang Web u thì q’ sẽ chứa các từ khố trong u bao
gồm cả q. Sau đĩ tính xác suất để q’ thuộc về các chủ đề khác nhau. Sử dụng thuật
tốn phân lớp Bayes với (i) Tập huấn luyện gồm những trang được liệt kê trong các
chủ đề; (ii) Đầu vào là câu truy vấn hoặc phạm vi ngữ cảnh của câu truy vấn; (iii) Đầu
ra là xác suất để đầu vào thuộc mỗi chủ đề.
Dưới đây là một số cơng thức của một số giá trị xác suất nĩi trên. Gọi 'q i là từ
khố thứ i trong ngữ cảnh q’. Với mỗi cj, xác suất để q’∈cj là:
)'()(
)'(
)'()(
)'( .
. ∏≈=
i
jij
jj
j cqPcPqP
cqPcP
qcP (2)
Trong đĩ ( )' |i jP q c được tính từ vector các từ khố →jD được xác định tại bước 1.
Giá trị P(cj) được xác định hoặc là các giá trị bằng nhau cho mọi chủ đề (các chủ đề
đồng khả năng) hoặc tính tốn thống kê qua tham chiếu tới các trang Web thuộc mỗi
chủ đề của tập hợp người dùng.
Theo [15,16], với ký hiệu rankjd là hạng của văn bản d cho bởi vector PR(d,
→
jv ) -
vector PageRank của chủ đề cj thì độ quan trọng sqd dựa theo câu truy vấn được tính
tốn như sau:
∑=
j
jdjqd rankqcPs .)'( (3)
1
| |
0
jT
jiv
⎧⎪= ⎨⎪⎩
ji T∈
ji T∉
20
Chương 3. Thuật tốn sử dụng cấu trúc Block theo thành
phần liên thơng
Phần đầu chương này trình bày một số khái niệm cơ bản trong tính tốn hạng
trang PageRank tại mục 2, từ đĩ đề xuất phương pháp mà chúng tơi gọi phương pháp
mới này là CCP (Connected Components in PageRank). Những lý thuyết, chứng minh
hình thành gắn liền với phương pháp sẽ được đề cập kĩ trong tại mục 3.
3.1. Khái niệm cấu trúc Block theo thành phần liên thơng
3.1.1.Phân tích thuật tốn PageRank
Chương 2 của khố luận đã trình bày phương pháp tính tốn hạng trang
PageRank. Phần này chúng tơi sẽ đi sâu phân tích thuật tốn PageRank diễn tả theo
ngơn ngữ đồ thị.
Phương pháp này dựa trên ý tưởng đã được thừa nhận là nếu 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 tới độ quan trọng của
trang B. Giả sử ta cĩ tập hợp gồm n trang Web trong cơ sở dữ liệu được đánh số từ 1
tới n. Đối với trang u bất kì, gọi )(uBI là tập hợp những liên kết tới trang u, gọi Nu là số
liên kết tới trang u. Gọi uπ là hạng trang của u (PageRank), khi đĩ cơng thức tính
PageRank cho trang u như sau:
∑
∈
=
)(uBi i
i
u
I
N
ππ (1)
Nếu diễn tả với ngơn ngữ đồ thị thì ta cĩ thể đặt G = (V, E) với V là tập các
trang Web cần tính hạng trang (V cĩ n trang, được đánh chỉ số 1, 2, ... n), cịn E là tập
cạnh đồ thị, E = {(i, j) | nếu cĩ liên kết từ trang i tới trang j}. Thuật tốn giả thiết rằng
đồ thị trang Web là liên thơng theo nghĩa với cặp hai trang Web i, j bất kì luơn cĩ
đường đi từ i tới j và ngược lại. Khi đĩ cĩ thể xây dựng được ma trận kề biểu diễn đồ
thị G như sau:
nxnijpP )(= (2)
Trong đĩ (3)
Khi đĩ phương trình (1) được viết lại dưới dạng ma trận sẽ được:
nếu cĩ liên kết từ i đến j
nếu khơng cĩ liên kết từ i đến j ⎩⎨
⎧=
0
1 i
ij
N
p
21
Pππ = (4)
Nĩi cách khác đây chính là việc tính vector riêng của ma trận P, và vector
riêng này ứng với giá trị riêng λ=1. Tuy nhiên việc tính vector riêng này chỉ được đảm
bảo khi ma trận P thoả mãn một số tính chất chặt chẽ đối với ma trận chuyển Markov.
Trong thực tế các trang Web, việc giả thiết đồ thị liên thơng là khơng hợp lí vì bao giờ
cũng tồn tại trang khơng cĩ liên kết tới trang nào khác. Do vậy, hàng ứng với trang
Web đĩ trong ma trận kề P sẽ bao gồm tồn những số 0, nên trong điều kiện đĩ khơng
tồn tại một phân phối xác suất dừng ổn định của P hay nĩi cách khác là vector riêng
PageRank. Chính vì vậy, để tồn tại một xác suất dừng ổn định đối với ma trận Markov
P (xem thêm trong [12]) thì cần phải sửa đổi ma trận P sao cho phù hợp.
Định nghĩa ma trận
J
n
PP )1(~ αα −+=
(5)
trong đĩ 10 << α (α thường được chọn là 0.85) và J là ma trận gồm tồn phần tử 1.
Khi đĩ, thay vì tính vector riêng của ma trận P ta tính vector riêng
),...,( 1 nπππ = của ma trận P~ được cho bởi cơng thức
P~ππ = (6)
Và tổng các thành phần của vector ),...,( 1 nπππ = :
1
1
=∑
=
n
i
iπ
(7)
Hay nĩi cách khác 11 =π trong đĩ 1 là vector cột gồm tồn phần tử 1. Ta cĩ
được điều này vì vector π chính là một phân bố xác suất dừng của ma trận chuyển
Markov, do vậy bắt buộc tổng các thành phần trong vector phải bằng 1. Trong quá
trình tính tốn vector riêng, phương pháp lặp đơn được sử dụng và phương pháp này
cĩ thể cho kết quả khả quan sau hơn 20 vịng lặp [1,2]. Với phương pháp ở trên, chúng
ta dễ dàng nhận thấy ma trận P là ma trận rất thưa, do vậy cơng việc tính tốn sẽ cĩ
nhiều thao tác thừa. Trong mục tiếp theo chúng ta sẽ bàn về khái niệm cấu trúc Block
theo thành phần liên thơng trong ma trận liên kết Web và việc sử dụng thành phần liên
thơng để giảm đi những tính tốn dư thừa này.
22
3.2. Một số vấn đề lý thuyết
Khi khảo sát mơ hình Markov [13], chúng tơi nhận thấy rằng trong lý thuyết
xác suất, các trạng thái cĩ thể được chia ra những lớp khác nhau. Những trạng thái cĩ
thể chuyển qua lại nhau được coi như là trong cùng một lớp. Khái niệm lớp các trạng
thái trong mơ hình Markov khá giống với khái niệm thành phần liên thơng trong lý
thuyết đồ thị.
Hơn nữa, việc sử dụng ma trận kề biểu diễn đồ thị các trang Web đã dẫn tới ý
tưởng sử dụng khái niệm cấu trúc Block (khối) theo thành phần liên thơng trong tính
tốn hạng trang với một số lợi thế sau:
- Khi chúng ta sử dụng tồn bộ ma trận P để tính tốn vector riêng như trong
phương pháp PageRank [1,2], số phép tính chi phí là khá lớn. Như đã biết, với phép
nhân ma trận thì thời gian tính tốn là O(n3) trong đĩ n là số trang Web. Nhưng khi
chúng ta đưa ma trận kề biểu diễn đồ thị về dạng các khối biểu diễn cho từng thành
phần liên thơng thì thời gian tính tốn sẽ giảm đi rất nhiều. Thật vậy, giả sử chúng ta
cĩ k thành phần liên thơng, khi đĩ với mỗi khối, thời gian tính tốn nhỏ hơn )(
3
maxnO
trong đĩ nmax=max{n1,…,nk}và tổng thời gian tính tốn sẽ nhỏ hơn )(
3
maxnkO , nhỏ
hơn nhiều so với thời gian tính tốn khi ta sử dụng tồn bộ ma trận lớn. Như vậy,
phương pháp đề xuất cĩ thời gian tính tốn lý thuyết hiệu quả hơn đối với phương
pháp PageRank. Hơn nữa, nếu kết hợp phương pháp này với những phương pháp hỗ
trợ tính tốn như MAP hay phương pháp ngoại suy [9,10] thì thời gian tính tốn sẽ
được giảm đi đáng kể.
- Sử dụng thành phần liên thơng chúng ta cĩ thể “thực sự” làm giảm đi số vịng
lặp tính tốn khơng giống như phương pháp tính tốn ma trận theo từng khối hoặc
phương pháp ma trận ra các thành phần nhỏ hơn dựa trên tiêu chí cùng host [11].
Phương pháp tính tốn ma trận theo khối giúp giảm được thời gian tính tốn do sử
dụng kĩ thuật tính tốn để cĩ thể song song hố mà khơng làm giảm được số vịng lặp.
Phương pháp chia ma trận thành các Block thành phần theo tiêu chí cùng host cĩ thể
giảm số vịng lặp nhưng lại được chia làm hai bước và mất thêm chi phí xử lý theo
khối, hơn nữa khối được chia theo host vẫn khá lớn. Phương pháp CCP khắc phục
được các điểm trên: cài đặt khơng cần sử dụng nhiều kĩ thuật như trong tính tốn ma
trận theo khối; hơn nữa, giảm được số vịng lặp do các khối thành phần liên thơng cĩ
cỡ nhỏ hơn khối được chia theo tiêu chí host [11].
23
- Trong phương pháp được đề xuất, cần phải tìm kiếm các thành phần liên
thơng và việc tìm thành phần liên thơng của đồ thị cĩ thể tiến hành dễ dàng với thời
gian đa thức O(n+m) với n là số đỉnh và m là số cạnh của đồ thị [8]. Do vậy, thời gian
chi phí với việc tìm kiếm thành phần liên thơng là khơng đáng kể.
- Khi chúng ta đưa về tính tốn với mỗi khối thành phần liên thơng thì chúng ta
cĩ thể song song hố quá trình tính tốn. Với những thành phần liên thơng khác nhau
được tính tốn, chúng ta cĩ thể giao cho những bộ xử lý khác nhau. Việc song song
hố này cĩ thể được tiến hành rất tự nhiên mà khơng cần phải áp dụng một kỹ thuật
nào phức tạp, hơn nữa, khi song song hố, chúng ta cĩ thể đẩy nhanh được thời gian
tính tốn lên.
Nhận xét
Như vậy, phương pháp đề xuất cĩ một số lợi điểm cơ bản sau (so với một số
phương pháp đã nghiên cứu):
• Giảm được thời gian tính tốn do việc lặp tính tốn trên ma trận
được giảm đi dựa trên việc phân chia đồ thị các trang Web ra các
thành phần liên thơng.
• Cĩ thể kết hợp dễ dàng với các phương pháp hỗ trợ tính tốn trên
ma trận.
• Cĩ thể được áp dụng song song hố một cách tự nhiên mà khơng
cần phải sử dụng quá nhiều những kĩ thuật lập trình.
Khi sử dụng phương pháp chia ma trận kề thành những khối ma trận nhỏ hơn
đại diện cho từng thành phần liên thơng thì trong quá trình tính tốn chúng ta phải giải
quyết một số vấn đề sau:
- Tính tốn hạng trang như thế nào để kết quả đạt được là đúng đắn?
- Việc tính tốn trên các thành phần liên thơng như thế nào là hiệu quả?
Chúng ta sẽ xem xét việc giải quyết những vấn đề trên trên khía cạnh lý thuyết
ở mục sau.
3.2.1. Tính tốn hạng trang với các Block theo thành phần liên thơng
Như đã đề cập ở trên, khi tính tốn trên các thành phần liên thơng thì giá trị
hạng trang PageRank hay nĩi cách khác là vector riêng đối với các trang được tính thế
nào?
24
Giả sử đồ thị G cĩ k thành phần liên thơng, khi đĩ ma trận P cĩ thể được viết
dưới dạng k khối được đặt trên đường chéo chính như sau:
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=
kP
P
P
L
MOM
L
0
01
(8)
trong đĩ Pi là ma trận kề cỡ nixni ứng với thành phân liên thơng thứ i, ki ,1= ;
nn
k
i
i =∑
=1
Định nghĩa các ma trận
i
i
ii Jn
PP )1(~ αα −+=
với ki ,1= và Ji là ma trận cỡ nix ni (9)
Cơng thức tính vector riêng với từng khối ma trận Pi là
iii P
~ππ = (10)
Định lý: Với những giả thiết ở trên (5,6,7,8,9,10), ta cĩ
),...,( 11 kk
n
n
n
n πππ =
(11)
chính là vector riêng của ma trận P
~
.
Chứng mình:
Để chứng minh
),...,( 11 kk
n
n
n
n πππ =
là vector riêng của ma trận P
~
thì ta
phải chứng minh: π thoả mãn phương trình vector riêng (6).
Thay (11) vào phương trình (6), ta được:
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡ −+
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
=⎥⎦
⎤⎢⎣
⎡ −+== J
n
P
P
J
n
PP
k
ααπααπππ 1
0
0
)1(~ 1
L
MOM
L
25
(12)
trong đĩ
ji xnnij
J )1(= là ma trận gồm tồn phần tử 1 và cĩ cỡ nixnj.
Nhân vế phải của (12), và xét thành phần thứ nhất, ta được:
121
22
111
1111 1...1)1( k
kk J
nn
n
J
nn
nJ
n
P
n
n
n
n απαπααππ −++−+−+= (13)
Mà với mỗi khối Pi cĩ vector riêng tương ứng là iπ thoả mãn phương trình (10)
⎥⎦
⎤⎢⎣
⎡ −+== i
i
i
i
i
ii J
n
PP ααπππ 1~ (14)
⎥⎦
⎤⎢⎣
⎡ −+=⇔ i
i
i
iiii J
n
P
n
n
n
n ααππ 1 (15)
Xét trường hợp cụ thể i=1, ta được:
⎥⎦
⎤⎢⎣
⎡ −+=⇔ 1
1
1
1111 1 J
n
P
n
n
n
n ααππ (16)
Từ (13,16) ta được:
121
22
111
11
1
1
1
11 1...1)1(1 k
kk J
nn
n
J
nn
nJ
n
P
n
nJ
n
P
n
n απαπααπααπ −++−+−+=⎥⎦
⎤⎢⎣
⎡ −+ (17)
111
11
11
1 ...
111
k
kk
JJ
J
n
n
J
n
nJ πππ ++=⇔=
n
n
k
i
i
nn
∑
==⇔ 1.11
11
mà nn
k
i
i =∑
=1
,
1
1n là vector hàng n1 cột gồm tồn phần tử 1 11 11 nn =⇔
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
−+−
−−+−
−−−+
=⇔
kkkk
k
k
kkkk
J
n
PJ
n
J
n
J
n
PJ
n
J
n
J
n
J
n
P
n
n
n
n
n
n
n
n
ααα
αααα
αααα
ππππ
11
111
111
),...,(),...,(
1
222221
112111
1111
LL
MOMM
L
L
26
Vậy ta được (13) đúng.
Tương tự, ta xét với các thành phần tiếp theo, iπ với ki ,2= cũng thoả mãn (đpcm)
3.2.2 Thuật tốn CCP
Phương pháp sử dụng cấu trúc Block theo thành phần liên thơng trong bài
tốn tính hạng trang cĩ thể được chia làm các bước:
- Bước 1: Chia đồ thị ra các thành phần liên thơng với các ma trận kề tương
ứng.
- Bước 2: Tính tốn PageRank cho các trang trong mỗi thành phần liên thơng
dựa trên việc tính tốn vector riêng của ma trận kề của thành phần liên thơng đĩ.
- Bước 3: Tổ hợp hạng trang cuối cùng dựa trên hạng trang nhận được sau
bước 2 như trong cơng thức (11).
Trong quá trình tính tốn, để được hiệu quả, chúng ta sẽ coi như chỉ làm việc
với trường hợp trung bình, cĩ nghĩa là xét các thành phần liên thơng với số đỉnh trung
bình. Do vậy chúng ta cần giải quyết hai trường hơp: đĩ là thành phần liên thơng cĩ số
đỉnh vượt quá hoặc nhỏ hơn ngưỡng trung bình. Để giải quyết các trường hợp này, cần
đưa ra hai số để làm ngưỡng, gọi là min và max. Khi đĩ, iP∀ ki ,1= ta cần
maxmin ≤≤ in ; nếu min≤in thì sẽ ghép những thành phần liên thơng cĩ số đỉnh tương
tự để được một thành phần liên thơng cĩ số đỉnh thỗ mãn điều kiện, nếu max≥in thì
cần phải tách thành phần liên thơng này ra thành những thành phần liên thơng nhỏ hơn
để thoả mãn điều kiện. Tuy nhiên khi tách và hợp các thành phần liên thơng, hạng của
các trang sẽ thay đổi và chúng ta sẽ phải xử lý vấn đề này. Từ đây đề xuất cách giải
quyết như sau đối với hai trường hợp:
- Trường hợp gộp: Đây là trường hơp đơn giản, PageRank của các trang sẽ
được tính tốn và lấy ra từ thành phần liên thơng sau khi được gộp. Trong trường hợp
này, chúng ta chỉ cần gộp sao cho số đỉnh của thành phần liên thơng vừa đủ lớn hơn
min. (min ở đây cĩ thể thử nghiệm với nhiều số để đưa ra được số min tối ưu nhất).
- Trường hợp tách: Đối với trường hợp này, vấn đề lý thuyết sẽ khĩ khăn hơn
so với trường hợp trên. Khi chúng ta tách một thành phần liên thơng lớn thành một
thành phần liên thơng nhỏ, thì giữa những thành phần nhỏ này cĩ những liên hệ nhất
định với nhau, và ta cần phải thể hiện hoặc sử dụng những liên hệ này để kết quả nhận
được cuối cùng là chính xác. Giả sử từ một thành phần liên thơng chúng ta tách ra
27
thành m khối (mỗi khối đều tự liên thơng) và giữa các khối này cĩ những liên kết nào
đĩ tới nhau (vì được tách ra từ một thành phần liên thơng lớn).
• Bước 1: Chúng ta tính hạng cho tất cả các trang trong mỗi thành
phần liên thơng nhỏ như bình thường.
• Bước 2: Coi mỗi thành phần liên thơng nhỏ như một nút của đồ
thị, chúng ta sẽ được một đồ thị gồm m nút và số liên kết tới mỗi
nút cũng như tổng số liên kết cĩ trong đồ thị. Hạng của mỗi nút
trong đồ thị mới được xây dựng này sẽ bằng số liên kết tới chính
nút đĩ chia cho tổng số liên kết trong đồ thị. Tại sao lại chọn hạng
trang cho mỗi nút trong đồ thị như vậy? Khi ta chọn giá trị như
vậy thì tổng tất cả các hạng trong đồ thị mới này sẽ bằng 1 (thoả
mãn điều kiện là tổng các xác suất).
• Bước 3: Do trong m khối, mỗi khối cĩ vector PageRank riêng, và
tổng các thành phần của vector PageRank của mỗi khối này đều
bằng 1, do vậy khi gộp lại tổng các thành phần của m vector ứng
với các khối sẽ bằng m. Do vậy, để tổng thành phần của các
vector PageRank của m khối bằng 1, ta sẽ lấy PageRank đại diện
của mỗi khối nhân với PageRank thành phần.
Hệ số min, max cũng như số đỉnh trung bình của mỗi khối sẽ được thử
nghiệm để tìm ra được hệ số tối ưu.
Chương tiếp theo giới thiệu mơ hình máy tìm kiếm Vinahoo và áp dụng thử
nghiệm thuật tốn Modified Adaptive PageRank cho bài tốn tính hạng trang trong
máy tìm kiếm Vinahoo.
28
Chương 4. Giải pháp tính hạng trang cải tiến cho máy
tìm kiếm Vinahoo
4.1. Tính tốn PageRank trong Vinahoo
Trong [1], tác giả đã trình bày kỹ về cấu trúc, CSDL, mã nguồn của máy tìm
kiếm Vinahoo. Ở đây, chúng tơi tập trung trình bày về module đánh chỉ số trong đĩ
thực thi tính tốn PageRank.
4.1.1. Mơ hình thực thi của module đánh chỉ số
Trong máy tìm kiếm Vinahoo, quá trình tính tốn PageRank cho các trang web
được tích hợp trong module index. Đầu tiên module này sẽ tiến hành quá trình crawler
để tải nội dung các trang web. Quá trình này cĩ tương tác với các đối tượng chính là
Internet, hệ quản trị cơ sở dữ liệu SQL và cơ sở dữ liệu chứa các file nhị phân tạm.
Sau đĩ, quá trình index sẽ tiến hành đánh chỉ số ngược cho các url mới tải về và lưu
trong các cấu trúc dữ liệu thuận tiện cho việc tìm kiếm các url theo từ khĩa của
module tìm kiếm sau này, cũng như tính giá trị PageRank cho các trang mới này. Quá
trình này sẽ sử dụng đầu vào là nội dung các trang web mới cập nhật trong file nhị
phân tạm, cùng các thơng tin đã cĩ trong file nhị phân cũ. Nĩ thực hiện việc sắp xếp
các url theo từ khĩa rồi kết hợp với nội dung cũ của các url trong file nhị phân, và cuối
cùng là tính hạng cho các trang Web dựa vào các liên kết giữa các trang.
4.1.2. Quá trình tính tốn PageRank trong Vinahoo
4.1.2.1. Cấu trúc hàng đợi các url trong Vinahoo
Vinahoo sử dụng một cấu trúc dữ liệu bảng băm để làm hàng đợi lưu các url
cần được index. Lý do vì cấu trúc bảng băm rất thuận tiện cho việc tìm kiếm một phần
tử trong danh sách. Vì vậy quá trình kiểm tra một URL đã cĩ mặt trong hàng đợi hay
chưa là rất dễ dàng. Các URL trong hàng đợi được nhĩm theo site, các url thuộc cùng
một site được nhĩm vào một danh sách FIFO gọi là CSiteUrls. Việc nhĩm các URL
theo site cĩ tác ưu điểm là làm giảm việc xử lý các tên miền DNS, giảm số lần phải kết
nối tới server, cũng như làm giảm số lần phải duyệt file robots.txt. Do đĩ làm giảm
đáng kể thời gian duyệt Web. Khi cĩ một url thuộc vào một site cần đưa vào hàng đợi,
url đĩ được thêm vào cuối danh sách url của site nĩ thuộc vào. Tồn bộ hàng đợi là
một bảng băm các CsiteUrls và cĩ một con trỏ trỏ tới site hiện tại đang được duyệt.
29
Khi cần lấy ra một url để duyệt tiếp, url ở đỉnh danh sách của site hiện tại sẽ được trích
ra. Cấu trúc của hàng đợi này như sau:
Hình6: Cấu trúc hàng đợi CSiteQueue trong Vinahoo
Trong đĩ: mỗi CsiteUrls là một danh sách một chiều các mảng chứa url thuộc
về cùng một site. Và CurlLinks là một mảng gồm 100 url liên tiếp.
Hình7: Cấu trúc một phần tử CSiteUrl
4.1.2.2. Qúa trình tính tốn PageRank trong Vinahoo
Đối với máy tìm kiếm Vinahoo, sau khi đánh chỉ mục các trang Web trong cơ
sở dữ liệu, quá trình tính tốn PageRank được thực hiện. Trong Vinahoo, đại lượng
PageRank được coi như chính giá trị hạng và giá trị PageRank được lấy trực tiếp để
làm tiêu chí hiển thị cĩ thứ tự các trang ra màn hình cho người dùng. Cơng thức tính
PageRank được sử dụng là cơng thức tính PageRank đơn giản. Các trang được tính
PageRank lần lượt, giá trị PageRank được lưu vào file nhị phân. Hạng trang trong
Vinahoo được tính theo cơng thức đệ qui. Hàm thực hiện PageRank là: CalsRanks(
CSQLDatabase *database)
4.1.2.3. Nhu cầu đẩy nhanh tốc dộ tính tốn PageRank
Như đã đề cập ở các chương trước, việc xếp hạng các trang Web trong CSDL
là một bộ phận rất quan trọng trong một hệ thống tìm kiếm. Chất lượng của module
này sẽ ảnh hưởng trực tiếp tới các bước sau của quá trình tìm kiếm. Một trong những
tính chất quan trọng nhất của module này là tính hiệu quả về thời gian. Nếu quá trình
tính PageRank khơng đủ nhanh, thì sẽ làm gia tăng thời gian chết của các bộ phận
khác trong máy tìm kiếm. Như vậy hệ thống tìm kiếm sẽ khơng cung cấp được chất
m_current
CSiteUrls CSiteUrls CSiteUrls .....
m_last m_first
CUrlLinks CUrlLinks CUrlLinks ......
30
lượng tìm kiếm tốt cho người dùng. Việc nâng cao được tốc độ tính tốn PageRank
cũng cĩ tác dụng tăng thêm mức độ tính tốn các vectơ thành phần, hướng tới việc xếp
hạng các trang Web quan tâm tới các tiêu chí của người dùng.
4.2.3. Đề xuất giải pháp
4.2.3.1. Cài đặt Modified Adaptive PageRank
Phần này trình bày các đề xuất cài đặt thuật tốn tính hạng Modified Adaptive
PageRank trên máy tìm kiếm Vinahoo. Hiện tại, trong modul index của Vinahoo chỉ
cài đặt thuật tốn tính PageRank đơn giản. Chúng tơi tiến hành thay modul tính tốn
PageRank bằng modul tương ứng với thuật tốn Modified Adaptive PageRank, vì một
số lý do sau:
- Modified Adaptive PageRank được phát triển dựa trên nền của thuật tốn
PageRank - thuật tốn đã được cài đặt trong phần mềm Vinahoo. Khả năng tích hợp
Modified Adaptive PageRank vào Vinahoo cĩ độ thành cơng cao.
- Modified Adaptive PageRank đẩy mạnh tốc độ tính tốn, giảm tính tốn dư
thừa.
Để tận dụng tối đa các lớp sẵn cĩ của Vinahoo[1], chúng tơi [2] khơng xây
dựng ma trận An x n như trong lý thuyết, mà vẫn áp dụng cơng thức đệ qui nhưng đưa
thêm vào phương pháp Modified Adaptive PageRank.
Để đánh dấu sự hội tụ của một trang, chúng ta cĩ hai cách:
- Cách thứ nhất: Thêm thuộc tính cho UrlRank cùng với tách các Url đã hội tụ-
chưa hội tụ ra hai file riêng biệt khi lưu trữ.
- Cách hai: Khi lưu trữ sẽ lưu thêm thuộc tính hội tụ converged bằng 1 nếu hội
tụ, bằng 0 nếu ngược lại.
Qua so sánh ưu nhược điểm của từng cách, chúng tơi thấy rằng việc lưu hạng
của các trang ra hai file cĩ vẻ sẽ tíết kiệm bộ nhớ hơn là lưu trữ thêm thuộc tính hội tụ.
Tuy nhiên, khi lưu trữ chúng ta cần lưu trữ tồn bộ PageRank của các URL theo thứ tự
lưu trữ là urlID, điều đĩ giúp quá trình đọc và ghi dữ liệu rất thuận tiện và đơn giản.
Do vậy, nếu lưu theo hai file khác nhau lại cần cĩ thơng số urlID đi kèm cùng với mỗi
giá trị RageRank. Điều đĩ khơng hề tíết kiệm bộ nhớ, tính tốn khơng đơn giản hơn
đồng thời cũng khơng tận dụng tốt nhất mã nguồn hiện cĩ của Vinahoo.
31
Do vậy, chúng tơi chọn cách thêm một thuộc tính đánh dấu sự hội tụ của một
UrlRank và khi lưu PageRank của các Url ta sẽ lưu thêm giá trị converged - để đánh
dấu nếu giá trị hạng của trang đĩ đã hội tụ.
nếu giá trị PageRank của trang đã hội tụ
ngược lại
4.2. Kết quả thực nghiệm và đánh giá
a. Cách thức tiến hành thực nghiệm
Thực nghiệm được tiến hành với máy tìm kiếm Vinahoo, trên máy tính cấu
hình Pentium 4HT 3.0GHz, 512MB RAM.
Các thực nghiệm được tiến hành trên mơi trường Internet thực sự, với các
trang Web được lấy từ website (đây là trang chủ của tổ chức giáo
dục phụ trách thi chứng chỉ tiếng Anh TOEFL). Sau khi crawl dữ liệu, cơ sở dữ liệu
lưu trữ 2368 trang Web với tổng số liên kết là 37490. Các thuật tốn được thử nghiệm
là PageRank bình thường, MAP và CCP.
b. Kết quả thử nghiệm
Sau đây là một số kết quả chạy thử nghiệm chương trình, các so sánh về thời
gian và số vịng lặp chi phí được chọn sau khi chia trung bình của 3 lần thử nghiệm đối
với mỗi thuật tốn.
1
0
Converged ⎧= ⎨⎩
2.59
1.65
0
0.5
1
1.5
2
2.5
3
Thời gian(s)
PageRank MAP CCPThuật tốn
Thời gian tính tốn PageRank
Hình 8: Biểu đồ thể hiện thời gian tính tốn PageRank của 3 thuật tốn
32
Qua biểu đồ trên ta thấy thời gian tính tốn PageRank theo thuật tốn MAP đã
giảm đi được 36% so với thuật tốn tốn PageRank thơng thường.
Tiến hành thử nghiệm các câu truy vấn đối với 3 thuật tốn, kết quả nhận
được sau hai câu truy vấn: “TOEFL” và “TEST” được cho trong bảng dưới.
PageRank MAP
TOEFL
1 ets.org/stoefl.html ets.org/stoefl.html
2 ets.org/ellrsc/css/twocolumns.css ets.org/ellrsc/css/twocolumns.css
3 ets.org/toefl/contact.html ets.org/toefl/contact.html
4 ets.org/ell/testpreparation/toeflindex.html ets.org/ell/testpreparation/toeflindex.html
5 ets.org/itp/ ets.org/itp/
6 ets.org/toefl/nextgen/index.html ets.org/toefl/nextgen/index.html
7 ets.org/legal/copyright.html ets.org/legal/copyright.html
8 ets.org/scoreitnow/index.html ets.org/scoreitnow/index.html
9 ets.org/itp/academics/ ets.org/itp/academics/
10 ets.org/criterion/ell/academics/index.html ets.org/ell/testpreparation/toefl/
TEST
1 ets.org/ell/testpreparation/toeflindex.html ets.org/ell/testpreparation/toeflindex.html
2 ets.org/etseurope/testinfo.html ets.org/etseurope/testinfo.html
3 ets.org/praxis/prxdsabl.html ets.org/praxis/prxdsabl.html
4 ets.org/praxis/prxorder.html ets.org/praxis/prxorder.html
5 ets.org/criterion/elementary.html ets.org/criterion/elementary.html
10
17
0
2
4
6
8
10
12
14
16
18
Số vịng lặp
PageRank MAP CCP Thuật tốn
Vịng lặp tính tốn PageRank
Hình 9: Biểu đồ thể hiện số vịng lặp cần thiết tính tốn PageRank của 3 thuật tốn
Bảng 7. Kết quả nhận được đối với hai truy vấn “TOEFL” và “TEST” ứng với các thuật tốn
33
Kết luận
1. Kết quả đạt được của khĩa luận
Thơng qua việc tìm hiểu, nghiên cứu các cơng trình nghiên cứu liên quan về
bài tốn tính hạng trang trong máy tìm kiếm, khĩa luận đã hồn thành một số kết quả
sau đây:
- Trình bày và phân tích chi tiết thuật tốn PageRank cơ bản áp dụng trong bài
tốn tính hạng trang trong máy tìm kiếm.
- Trình bày những nội dung cơ bản bao gồm cả việc phân tích hai thuật tốn
Modified Adaptive PageRank và Topic-sensitive PageRank nhằm nâng cao hiệu năng
tính tốn PageRank.
- Phân tích chi tiết cơ chế hoạt động của máy tìm kiếm tiếng Việt mã nguồn mở
Vinahoo.
- Một kết quả quan trọng của khĩa luận là đã đề xuất một giải pháp sử dụng
cấu trúc Block theo thành phần liên thơng trong ma trận liên kết Web trong việc tính
PageRank trong máy tìm kiếm Vinahoo.
- Hơn thế nữa, khĩa luận cài đặt thuật tốn Modified Adaptive PageRank trên
vào máy Vinahoo và đạt được một số kết quả bước đầu tương đối khả quan.
Tuy nhiên do hạn chế về thời gian hồn thành khĩa luận nên chương trình cài
đặt chưa cài đặt hồn chỉnh thuật tốn CCP sử dụng cấu trúc Block theo thành phần
liên thơng trong ma trận liên kết Web trong việc tính PageRank trong máy tìm kiếm
Vinahoo .
2. Hướng phát triển tiếp theo
Khai phá cấu trúc web vào máy tìm kiếm trong bài tốn tính hạng trang đang
ngày càng trở thành các lĩnh vực nghiên cứu đầy tiềm năng, hướng nghiên cứu tiếp
theo của khĩa luận là:
- Tiếp tục hồn thiện chương trình cài đặt thuật tốn CCP sử dụng cấu trúc
Block theo thành phần liên thơng trong ma trận liên kết Web trong việc tính PageRank
trong máy tìm kiếm Vinahoo.
- Nghiên cứu sâu về tối ưu min, max, trung bình, cách chia các block cũng như
phát triển phương pháp theo hướng song song hố.
34
Tài liệu tham khảo
[1]. Bùi Quang Minh. Máy tìm kiếm Vinahoo. Báo cáo kết quả nghiên cứu thuộc Đề
tài khoa học đặc biệt cấp ĐHQGHN mã số QG-02-02, 2002.
[2] Đỗ Thị Diệu Ngọc, Nguyễn Hồi Nam, Nguyễn Yến Ngọc, Nguyễn Thu Trang.
Giải pháp tính hạng trang cải tiến cho máy tìm kiếm Vinahoo. Chuyên san “Các
cơng trình nghiên cứu - triển khai Viễn thơng và CNTT”, Tạp chí Bưu chính -
Viễn thơng, 14, 4-2005, 65-71
[3] Phạm Thị Thanh Nam, Bùi Quang Minh, Hà Quang Thụy. Giải pháp tìm kiếm
trang Web tương tự trong máy tìm kiếm Vinahoo. Tạp chí Tin học và Điều khiển
học, 20(4), 293-304, 2004.
[4] Andrew Y. Ng, Alice X. Zheng, and Michael I. Jordan. Stable algorithms for link
analysis. In Proceedings of the 24th Annual International ACM SIGIR
Conference. ACM, 2001.
[5] Jon Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the
ACM, 46(5):604-632, November 1999.
[6] Jiawei Han, Micheline Kamber, Data Mining: Concepts and Techniques. Morgan
Kaufmann Publishers, 2001, trang 435-443.
[7] Kir Kolyshkin. Vinahoo Manual. Cung cấp tại 2002.The
Anatomy of large scale Hypertextual Web Search Engine.
[8] Page, L., Brin, S., Motwani, R. and Winograd, T. 1998 The PageRank citation
ranking: bringing order to the Web. Technical report, Stanford University.
[9] Raymond Kosala, Hendrik Blockeel. Web Mining Research: A Survey.
Department of Computer Science, Katholieke Uiniversiteit Leuven, Heuverlee,
Belgium, trang 601-602.
[10] Sepandar Kamvar, Taher Haveliwala, and Gene Golub (2003). Adaptive Methods
for the Computation of PageRank. Technical report, Stanford University.
[11] Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning Gene H.
Golub (2003). Exploiting the Block Structure of the Web for Computing
PageRank. Technical report, Stanford University
35
[12] S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub. Extrapolation
methods for accelerating PageRank computations. In Proceedings of the Twelfth
International World Wide Web Conference, 2003.
[13] Sheldon Ross. Introduction to probability models, 8th Edition. Academic Press,
January 2003.
[14] Shian - Hua Lin, Meng Chang Chen, Jan-Ming Ho, ACIRD: Intelligent Internet
Document Organization and Retrival. IEEE transaction on knowledge and data
engineering VOL 14, NO 3 May/June 2002.
[15] Taher H. Haveliwala. Topic-Sensitive PageRank. WWW2002, May 7–11, 2002,
Honolulu, Hawaii, USA (ACM 1581134495/02/0005).
[16] Taher H. Haveliwala. Topic-Sensitive PageRank: A Context-Sensitive Ranking
Algorithm for Web Search, 2003.
[17] Taher H. Haveliwala. Efficient Computation of PageRank. Technical report,
Stanford University, 1999.
[18]
Các file đính kèm theo tài liệu này:
- K46_Nguyen_Yen_Ngoc_Thesis.pdf