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ườ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 toán nan giải về tốc
độ. Trong đó có bài toán về tốc
độ tính toán hạng cho các trang Web, thực thi nhiệm
vụ tính toá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à
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 toà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ì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ề
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ỷ
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
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ả.
ấ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ệ
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ố hoặc 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
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 ngoà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 = A
T
r trong đó:
A là ma trận kích thước n x n trong đó các phần tử
14
a
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 toán trên như sau: bước đầu tiên ta sẽ gán cho vectơ PageRank
toàn cục một giá trị bất kì, sau đó lấy vectơ đó nhân với ma trận A
T
đượ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 A
T
, 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
5
Hình 4: Một ví dụ liên kết Web
16
2.3. Một số thuật toá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 toán của
thuật toán PageRank bao gồm khả năng tăng tốc độ tính toán và một trong các phương
pháp tăng tốc độ tính toán hiện nay là Modified Adaptive PageRank.
2.3.1. Nhu cầu tăng tốc độ tính toá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 toá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 toán này tốn rất nhiều ngày. Cần phải tăng
được tốc độ tính toá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 toá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 toán nhiều
vectơ PageRank, mỗi vectơ hướng tới một tiêu đề khác nhau. Việc tính toán nhiều
vectơ này cũng đòi hỏi mỗi vectơ thành phần được tính toán nhanh chóng.
Việc tăng cường tốc độ tính toá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
toá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ó
k
N
)(
tương ứng với những
thành phần của x
(k)
đã hội tụ còn
x
k
C
)(
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
x
x
k
⎝
⎛
•
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
+
x
x
A
A
x
x
k
C
nữa mà chỉ
cần thực hiện x
N
(k+1)
= A
N
x
(k)
2.3.2.2 . Thuật toán Modified Adaptive PageRank
Trong thuật toán Adaptive PageRank tốc độ tính toán được tăng nhanh lên do ta
đã giảm đi được những tính toá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 toá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
AA
A
CCCN
NCNN
NN
k
N
)()()1(
+=
+
Ma trận A đã được chia nhỏ ra do vậy công việc tính toá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 toán có
thể được cải thiện khoảng 30%.
Theo [11], việc giảm những tính toán của phương pháp PageRank giúp chúng ta
có thể tính toá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 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.
j
vv
=
r
uur
trong đó
(1)
Gọi
→
j
D là vector các từ khoá, gồm tất cả các từ khoá trong các tài liệu của các
chủ đề;
D
jt
là số lần xuất hiện của từ khoá t trong tất cả các tài liệu của chủ đề c
j
.
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ừ khoá
q trong trang Web u thì q’ sẽ chứa các từ khoá 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
toá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
qP
cqP
cP
qcP
(2)
Trong đó
(
)
'
|
ij
P
qc được tính từ vector các từ khoá
→
j
D
được xác định tại bước 1.
Giá trị P(c
j
) đượ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 toá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
rank
jd
là hạng của văn bản d cho bởi vector PR(d,
→
j
v ) -
⎨
⎪
⎩
j
iT
∈
j
iT
∉
20
Chương 3. Thuật toá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 toá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 toán PageRank
Chương 2 của khoá luận đã trình bày phương pháp tính toán hạng trang
PageRank. Phần này chúng tôi sẽ đi sâu phân tích thuật toá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
)(uB
I
=
(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
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
=
∑
=
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
toán hạng trang với một số lợi thế sau:
- Khi chúng ta sử dụng toàn bộ ma trận P để tính toá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 toán là O(n
3
) 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 toá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 toán nhỏ hơn
)(
3
max
nO
trong đó nmax=max{n1,…,nk}và tổng thời gian tính toán sẽ nhỏ hơn
)(
3
max
nkO
, nhỏ
hơn nhiều so với thời gian tính toán khi ta sử dụng toàn bộ ma trận lớn. Như vậy,
phương pháp đề xuất có thời gian tính toá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 toán như MAP hay phương pháp ngoại suy [9,10] thì thời gian tính toá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
đượ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 toán trên
ma trận.
• Có thể được áp dụng song song hoá 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 toán chúng ta phải giải
quyết một số vấn đề sau:
- Tính toán hạng trang như thế nào để kết quả đạt được là đúng đắn?
- Việc tính toá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 toá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 toá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:
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
n
PP
)1(
~
α
α
−
+=
với
ki ,1=
và J
i
là ma trận cỡ n
i
x n
i
(9)
Công thức tính vector riêng với từng khối ma trận Pi là
i
ii
P
~
ππ
= (10)
Định lý
πππ
=
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:
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
−
+
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
L
25(12)
trong đó
ji
xnnij
J )1(= là ma trận gồm toàn phần tử 1 và có cỡ n
i
xn
j
.
Nhân vế phải của (12), và xét thành phần thứ nhất, ta được:
121
2
2
111
α
αππ
−
++
−
+
−
+=
(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
n
n
α
αππ
1
(15)
Xét trường hợp cụ thể i=1, ta được: ⎥
⎦
⎤
⎢
⎣
⎡
−
+=⇔
1
1
1
1
1
1
1
1
J
n
P
n
J
nn
n
J
nn
n
J
n
P
n
n
J
n
P
n
n
α
π
α
π
α
απ
α
απ
−
++
−
+
−
+=
++=⇔
=n
n
k
i
i
nn
∑
=
=⇔
1
.11
11
mà
nn
k
i
i
=
∑
=1
,
1
1
n
là vector hàng n
1
+
−
−−−
+
=⇔
kkkk
k
k
k
k
k
k
J
n
PJ
n
J
n
J
n
PJ
n
J
n
J
n
J
n
P
n
L
Copyright: Tài liệu đại học ©