Luận văn tốt nghiệp
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.
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 toá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 toán xêp hạng trang Web trong máy tìm
kiếm và thuật toán tính PageRank cơ bản. Việc phân tích nhu cầu tăng tốc độ tính toán
PageRank trong máy tìm kiếm, một số thuật toá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 toá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 toá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
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.
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ự đoá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à để
(về ngôn ngữ, định dạng,…), còn dữ liệu Web thì hoàn toà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 khoá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.
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
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 tran
g
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.
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,
(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 toá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 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 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
Như vậy ta có thể thấy vectơ PageRank r chính là vectơ riêng của ma trận A
T
Như ta đã thấy ỏ trên, việc tính toá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 toá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 toán được các
hạng trang thông qua việc tính toán vectơ riêng của ma trận A
T
. 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 toán vectơ
PageRank là phương pháp lặp. Các công việc tính toán sẽ được làm như sau:
1. s Å vector bất kì
2. r Å A
T
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 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
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 ngoà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 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
17
2.3.2. Thuật toán Modified Adaptive PageRank
2.3.2.1. Thuật toán Adaptive PageRank
Giả sử việc tính toá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 toá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, A
N
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 A
C
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
k
N
)(
tương ứng với những
thành phần của x
(k)
đã hội tụ còn
x
k
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
A
A
A
C
N
Ta có thể viết lại phương trình (*) như sau:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
•
⎟
⎟
⎠
⎞
⎜
⎜
)(
)1(
)1(
Do những thành phần của
x
k
C
)(
đã hội tụ do vậy ta không cần tính
x
k
C
)1( +
nữa và
như vậy việc tính toán sẽ được giảm đi do không phải tính toán
x
A
k
C
)(
nữa mà chỉ
cần thực hiện x
N
(k+1)
= A
N
x
(k)
,A
CC.
Vì x
C
và
A
NC
x
C
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 :
x
A
x
A
x
k
C
CN
k
N
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ó
; gọi T
j
là tập hợp những trang Web theo chủ đề c
j
. 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
[]
N
v
n
/1
1×
→
=
thuật toán sử dụng vector
j
vv
=
r
uur
trong đó
(1)
Gọi
c
j
là:
)'()(
)'(
)
'(
)(
)'(
.
.
∏
≈=
i
j
ij
j
j
j
c
qPcP
qP
cqP
cP
qcP
(2)
Trong đó
(
)
j
jd
j
qd
rank
qcP
s
.
)'(
(3)
1
||
0
j
T
ji
v
⎧
⎪
=
⎨
⎪
⎩
j
iT
∈
j
iT
∉
∈
=
)(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 toá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:
nxnij
pP )(
=
(2) Trong đó (3) Khi đó phương trình (1) được viết lại dưới dạng ma trận sẽ được:
Đị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 toà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
1
là vector cột gồm toà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 toá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 toá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 toá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
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
đượ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 toá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 toán với mỗi khối thành phần liên thông thì chúng ta
có thể song song hoá quá trình tính toán. Với những thành ph
ần liên thông khác nhau
được tính toán, chúng ta có thể giao cho những bộ xử lý khác nhau. Việc song song
hoá 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 hoá, chúng ta có thể đẩy nhanh được thời gian
tính toá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 toán do việc lặp tính toá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 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
L
0
0
1
(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
J
n
PP
)1(
~
α
α
−
+=
n
n
n
πππ
=
(11)
chính là vector riêng của ma trận
P
~
.
Chứng mình:
Để chứng minh
), ,(
1
1
k
k
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).
−
+== J
n
P
P
J
n
PP
k
α
απ
α
απππ
1
0
0
)1(
~
1
L
MOM
L
Copyright: Tài liệu đại học ©