Luận văn Giải pháp tính hạng trang khai thác cấu trúc Block của Web và áp dụng vào máy tìm kiếm

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 toán tính hạng trang điển hình 2.1. Bài toán xếp hạng trang Web trong máy tìm kiếm Trong chương này, phần đầu chúng tôi sẽ giới thiệu tổng quan về bài toán xếp hạng trang Web trong các máy tìm kiếm, phần sau, chúng tôi sẽ tập trung phân tích nội dung các thuật toán PageRank, Modified Adaptive PageRank và Topic-sensitive PageRank ứng dụng trong bài toán tính hạng cho các trang Web. 2.1.1. Nhu cầu Ngày nay, người sử dụng có thể tìm kiếm thông tin đa dạng về mọi mặt của xã hội loài người trên Internet. Tuy nhiên, do lượng thông tin trên Internet là khổng lồ, đang từng ngày từng giờ tăng trưởng với tốc độ cao, cho nên việc giải bài toán tìm và cung cấp thông tin được người dùng thực sự quan tâm trong thời gian cho phép đã trở thành công việc hết sức cấp thiết. Công nghệ xây dựng công cụ tìm tin trên Internet (điển hình là máy tìm kiếm - search engine) cần không ngừng được cải tiến nhằm bảo đảm thoả mãn yêu cầu người dùng cả theo khía cạnh thời gian tìm kiếm nhanh lẫn tính sự phù hợp cao giữa các trang thông tin kết quả tìm được với yêu cầu tìm kiếm của người dùng. Khi người dùng nhập vào một nhóm từ khóa tìm kiếm, máy tìm kiếm sẽ thực hiện nhiệm vụ tìm kiếm và trả lại một số trang Web theo yêu cầu người dùng. Nhưng số các trang Web liên quan đến từ khóa tìm kiếm có thể lên tời hàng vạn trang, trong khi người dùng chỉ quan tâm đến một số ít trang trong đó, vậy việc tìm ra các trang đáp ứng nhiều nhất yêu cầu người dùng để đưa lên đầu là cần thiết. Đó chính là công việc tính hạng của máy tìm kiếm - sắp xếp các trang kết quả theo thứ tự giảm dần của độ quan trọng. Cần thiết phải xác định phép đo về "độ phù hợp" của một trang Web tìm được với yêu cầu người dùng [1,10]. Liên quan tới việc xác định phép đo như vậy, người ta quan tâm tới hai hướng giải quyết.. Hướng thứ nhất sử dụng độ quan trọng (được xác định qua một đại lượng được gọi là hạng trang - page rank) của trang Web làm độ phù hợp với yêu cầu người dùng. Hầu hết các nghiên cứu đều thừa nhận một giả thiết là nếu một trang Web mà có nhiều trang Web khác hướng (link) tới thì trang Web đó là trang Web quan trọng. Trong trường hợp này, hạng trang được tính toán chỉ dựa trên mối liên kết giữa các trang Web với nhau. Hầu hết các máy tìm kiếm sử dụng hạng trang làm độ phù hợp của kết quả tìm kiếm với các thuật toán điển hình là PageRank, 12 Modified Adaptive PageRank [10]. Hướng thứ hai coi độ phù hợp của trang Web với câu hỏi của người dùng không chỉ dựa trên giá trị hạng trang Web như trên mà còn phải tính đến mối liên quan giữa nội dung trang Web đó với nội dung câu hỏi theo yêu cầu của người dùng mà thuật toán điển hình là Topic-sensitive PageRank [15,16]. Một số nghiên cứu khai thác khía cạnh nội dung của trang Web đối với độ phù hợp của trang Web tìm kiếm với câu hỏi người dùng cũng được đề cập trong một số công trình [4,7]. 2.1.2. Độ quan trọng của trang web Một số phương pháp được sử dụng để đo độ quan trọng của các trang web. a. Các từ khóa trong văn bản: Một trang web được coi là hợp lệ nếu nó có chứa một số 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ớ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 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 ∑∈= )( )()()( 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 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 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 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 Å 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 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 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 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 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ó 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 toán dư thừa và làm tăng được hiệu suất tính toá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 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, 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 toán sẽ được giảm đi do không phải tính toán xA kC )( nữa mà chỉ cần thực hiện xN(k+1)= ANx(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 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 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. Thuật toá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 toán sử dụng vector jv v= r uur trong đó (1) Gọi → jD 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ủ đề; Djt 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ủ đề 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ừ 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 'q i là từ khoá 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ừ khoá →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 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 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 toán như sau: ∑= j jdjqd rankqcPs .)'( (3) 1 | | 0 jT jiv ⎧⎪= ⎨⎪⎩ ji T∈ ji T∉ 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 )(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 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: 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 toà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 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 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 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(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 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 maxnO trong đó nmax=max{n1,…,nk}và tổng thời gian tính toán sẽ nhỏ hơn )( 3 maxnkO , 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 lặp tính toán không giống như phương pháp tính toá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 toán ma trận theo khối giúp giảm được thời gian tính toán do sử dụng kĩ thuật tính toán để có thể song song hoá 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 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 đề