PageRank – Wikipedia tiếng Việt

Pagerank là thuật toán phân tích các liên kết được dùng trong Google Search để xếp hạng các trang web.

  • Thuật toán này chỉ định giá trị nhất định cho mỗi thành phần của một tập hợp các văn bản liên kết với nhau, ví dụ như World Wide Web.
  • Mục đích “đo” tầm quan trọng tương đối của các liên kết trong tập hợp đó.
  • Áp dụng cho bất kỳ tập hợp văn bản nào có trích dẫn đối ứng và liên kết cụ thể.
  • giá trị (weight) mà nó gán cho bất kỳ thành phần E được gọi là PageRank của E và ký hiệu là P R ( E ). { \ displaystyle PR ( E ). }{\displaystyle PR(E).}

PageRanks đối với một hệ thống liên kết đơn giản, sẽ được hiển thị tỷ lệ bằng %. Trang C có một PageRank cao hơn so với trang E, mặc dù có ít liên kết (links) đến trang C; một link duy nhất dẫn tới C từ một trang quan trọng và chính vì thế mà C có giá trị cao. Nếu như một người lướt web bắt đầu từ một trang bất kỳ thì có 85% xác suất chọn một link ngẫu nhiên trên trang mà họ đang xem, và 15% họ sẽ chọn chuyển sang một trang web bất kỳ từ toàn bộ hệ thống các liên kết. Người dùng sẽ truy cập vào trang E với xác suất 8.1%. (Xác suất 15% truy cập tới một trang bất kỳ tương ứng với yếu tố damping là 85%.) Nếu không có yếu tố damping, người dùng cuối cùng cũng sẽ kết thúc quá trình lướt web tại trang A, B, hoặc C, và các trang khác sẽ có PageRank bằng 0. Nếu như tính cả yếu tố damping, trang A vẫn liến kết đến tất cả các trang trong hệ thống, mặc dù chỉ có 1 link trỏ đi.Thuật toán toán họcđối với một mạng lưới hệ thống link đơn thuần, sẽ được hiển thị tỷ suất bằng %. Trang C có một PageRank cao hơn so với trang E, mặc dầu có ít link ( link ) đến trang C ; một link duy nhất dẫn tới C từ một trang quan trọng và chính cho nên vì thế mà C có giá trị cao. Nếu như một người lướt web mở màn từ một trang bất kể thì có 85 % Tỷ Lệ chọn một link ngẫu nhiên trên trang mà họ đang xem, và 15 % họ sẽ chọn chuyển sang một trang web bất kể từ hàng loạt mạng lưới hệ thống những link. Người dùng sẽ truy vấn vào trang E với Phần Trăm 8.1 %. ( Xác suất 15 % truy vấn tới một trang bất kể tương ứng với yếu tố damping là 85 %. ) Nếu không có yếu tố damping, người dùng sau cuối cũng sẽ kết thúc quy trình lướt web tại trang A, B, hoặc C, và những trang khác sẽ có PageRank bằng 0. Nếu như tính cả yếu tố damping, trang A vẫn liến kết đến toàn bộ những trang trong mạng lưới hệ thống, mặc dầu chỉ có 1 link trỏ đi .

Giá trị Pagerank hình thành từ thuật toán toán học dựa trên webgraph: các trang world wide web được coi như các đỉnh và các đường link là các cạnh.
Khi hình thành webgraph người ta có tính đến những trang của các cơ quan có thẩm quyền như cnn.com hay usa.gov. Giá trị xếp hạng cho thấy tầm quan trọng của từng trang cụ thể. Mỗi đường link tới trang web sẽ được tính như 1 sự hỗ trợ làm tăng thêm giá trị Pagerank. Giá trị Pagerank của trang được định nghĩa đệ quy và phụ thuộc vào số lượng và giá trị của các trang mà có link dẫn đến trang đó (incoming links).
Một trang web có chứa nhiều link liên kết từ các trang web có giá trị PageRank cao thì giá trị PageRank của trang đó cũng sẽ cao.
Có rất nhiều bài viết đã được xuất bản ra công chúng dựa trên nghiên cứu gốc của Page và Brin. Trên thực tế khái niệm PageRank rất khó để thao tác. Đã có nhiều nghiên cứu tiến hành xác định những ảnh hưởng sai tới PageRank ranking. Mục đích là tìm một cách loại bỏ hiệu quả những link từ các văn bản với những ảnh hưởng sai tới PageRank.

Pagerank là phân bổ Xác Suất, được sử dụng để biểu lộ năng lực khi một người click chuột ngẫu nhiên vào đường link và sẽ tới được website đơn cử. Pagerank hoàn toàn có thể được tính cho những tập văn bản với tài liệu có độ dài bất kể. Khi khởi đầu đo lường và thống kê thì sự phân chia đó được chia đều cho toàn bộ những văn bản trong tập văn bản. Các thống kê giám sát Pagerank cần một số ít lần ” lặp đi tái diễn ” qua những văn bản trong tập để hoàn toàn có thể đạt được giá trị trong thực tiễn một cách thiết thực hơn. Xác suất có giá trị từ 0 đến 1. Với giá trị 0.5, thường được hiểu là ” 50 % thời cơ ” của một việc gì đó có thê xảy ra. Trong Pagerank, 0.5 có nghĩa là 50 % thời cơ một người nào đó click vào một link ngẫu nhiên để được chuyển đến văn bản đó ( giá trị pagerank = 0.5 )

Thuật toán được đơn giản hóa[sửa|sửa mã nguồn]

Giả sử một nhóm gồm 4 trang web: A, B, C, D.
những liên kết từ một trang đến chính nó không được tính, mỗi trang web có 1 đường dẫn duy nhất đến 1 trang web khác. Giá trị Pagerank của các trang ban đầu được cho là bằng nhau. Tổng giá trị Pagerank trên tất cả các trang là tổng số trang web tại thời điểm đó, do đó mỗi trang trong ví dụ này sẽ có một pagerank ban đầu tương đương với 1. Tuy nhiên trong phần còn lại và các ví dụ của bài này sẽ có giá trị tương đối từ 0 đến 1. Do đó giá trị ban đầu cho mỗi trang là 0.25. Pagerank chuyển từ một trang đến các trang khác bằng các đường link, trong những bước tính tiếp theo giá trị sẽ được chia đều cho tất cả các liên kết đi. Nếu các liên kết duy nhất trong hệ thống từ các trang B, CD tới A, mỗi liên kết sẽ chuyển giá trị bằng 0.25 Pagerank A khi tính trong lần tiếp theo, tổng cộng là 0,75.

P R ( A ) = P R ( B ) + P R ( C ) + P R ( D ). { \ displaystyle PR ( A ) = PR ( B ) + PR ( C ) + PR ( D ). \, }{\displaystyle PR(A)=PR(B)+PR(C)+PR(D).\,}

Khác với ví dụ trên, B có liên kết đến trang CA, trong khi D có các link đến cả ba trang. Như vậy trong bước tiếp theo, trang B sẽ chuyển tải một nửa giá trị của mình, tương đương với 0.125 tới trang A và 0.125 tới trang C. Khi trang D có 3 liên kết trỏ đi, có nghĩa nó sẽ chuyển 1/3 giá trị của mình, tương đương với 0.083 tới A.

P R ( A ) = P R ( B ) 2 + P R ( C ) 1 + P R ( D ) 3. { \ displaystyle PR ( A ) = { \ frac { PR ( B ) } { 2 } } + { \ frac { PR ( C ) } { 1 } } + { \ frac { PR ( D ) } { 3 } }. \, }{\displaystyle PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.\,}

PageRank được tính cho 1 outbound link sẽ bằng số score pagerank của document đó chia cho số outbound link L()

P
R
(
A
)
=

P
R
(
B
)

L
(
B
)

+

P
R
(
C
)

L
(
C
)

+

P
R
(
D
)

L
(
D
)

.

{\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\,}

{\displaystyle PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\,}

Công thức chung, giá trị Pagerank đối với bất kỳ trang u có thể tính như sau:

P R ( u ) = ∑ v ∈ B u P R ( v ) L ( v ) { \ displaystyle PR ( u ) = \ sum _ { v \ in B_ { u } } { \ frac { PR ( v ) } { L ( v ) } } }{\displaystyle PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}

Giá trị PageRank đối với trang u phụ thuộc vào giá trị Pagerank của từng trang v có chứa trong set Bu (tập hợp có chứa các trang có link đến trang u), chia cho số L (v) các link từ trang v.

Yếu tố damping[sửa|sửa mã nguồn]

Lý thuyết PageRank cho rằng, ngay cả một người dùng giả thiết click ngẫu nhiên vào những website sau cuối cũng sẽ dừng lại. Xác suất người dùng liên tục click trong bất kỳ bước nào được gọi là yếu tố damping. Có nhiều nghiên cứu và điều tra đã thử những giá trị yếu tố damping, giá trị ước đạt bằng 0.85 là người dùng sẽ liên tục lướt web. Công thức tính Pagerank có tính đến yếu tố damping sử dụng quy mô khi người dùng bất kể sẽ cảm thấy chán sau một vài lần click và chuyển đến vài trang web khác một cách ngẫu nhiên. Như vậy :

P R ( A ) = 1 − d N + d ( P R ( B ) L ( B ) + P R ( C ) L ( C ) + P R ( D ) L ( D ) + ⋯ ). { \ displaystyle PR ( A ) = { 1 – d \ over N } + d \ left ( { \ frac { PR ( B ) } { L ( B ) } } + { \ frac { PR ( C ) } { L ( C ) } } + { \ frac { PR ( D ) } { L ( D ) } } + \, \ cdots \ right ). }{\displaystyle PR(A)={1-d \over N}+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}

Công thức trên sử dụng quy mô khi người dùng ngẫu nhiên cảm thấy chán sau khi click và được chuyển đến một số ít trang ngẫu nhiên. Giá trị Pagerank biểu lộ những thời cơ mà người dùng ngẫu nhiên sẽ được chuyển đến trang đó bằng cách click vào những đường link. Mô hình này hoàn toàn có thể được hiểu tương tự như như Markov chain, trong đó những tỉnh là những website, quy trình chuyển dời có Phần Trăm ngang nhau được coi như những link giữa những website. Nếu như website không có đường link đến những trang khác, nó sẽ thành ngõ cụt và việc truy vấn ngẫu nhiên sẽ dừng lại. Nhưng nếu người dùng đến trang không có những link khác, thì người dùng sẽ chọn ngẫu nhiên một trang khác để liên tục truy vấn. Khi tính Pagerank, những trang không có link trỏ đi những trang khác sẽ được giả định có link trỏ đến toàn bộ những trang trong tập văn bản. Và như vậy giá trị Pagerank sẽ được chia đều cho những trang khác. Nói một cách khác, để công minh với những website có outbound link, thì những truy vấn ngẫu nhiên sẽ được thêm vào tổng thể những trang trong Web, với Phần Trăm d = 0.85, được ước tính từ tần số trung bình mà người dùng sử dụng khi ghi lại một tính năng bằng trình duyệt .

P
R
(
A
)
=
1

d
+
d

(

P
R
(
B
)

L
(
B
)

+

P
R
(
C
)

L
(
C
)

+

P
R
(
D
)

L
(
D
)

+

)

.

{\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}

{\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}

p

1

,

p

2

,
.
.
.
,

p

N

{\displaystyle p_{1},p_{2},…,p_{N}}

{\displaystyle p_{1},p_{2},...,p_{N}} – là các trang được cân nhắc,

M
(

p

i

)

{\displaystyle M(p_{i})}

{\displaystyle M(p_{i})} – tập hợp những trang có link đến

p

i

{\displaystyle p_{i}}

{\displaystyle p_{i}},

L
(

p

j

)

{\displaystyle L(p_{j})}

{\displaystyle L(p_{j})} – số lượng link trỏ ra trong

p

j

{\displaystyle p_{j}}

{\displaystyle p_{j}}, N– tổng số trang web.

Liên kết ngoài[sửa|sửa mã nguồn]

5/5 - (1 vote)

Bài viết liên quan

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments