Thuật toán page rank của google
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.21 MB, 38 trang )
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
PHÂN TÍCH
LINK
• GVHD:
- PGS. TS. Hồ Bảo Quốc
• Học Viên: - Phạm Thành Đạt – 16C12001
- Nguyễn Thị Huệ Minh – 16C12003
1
2
3
NỘI DUNG CHÍNH
1. PageRank
4. Hubs và
Authorities
2. Tính hiệu quả của
PageRank
3. PageRank
Topic-Sensitive
5. Link Spam
6. Thuật toán
PageRank hiện tại
4
Đối với một số web search trước đó:
blue sky blue sky
Sao
chép
nội
dung
SPAM
5
- Người dùng Web Search sẽ tự bỏ phiếu cho
trang web mà họ truy cập đến.
SPAM
Giải
pháp
- Dựa trên hành vi lướt web của người dùng
Web Search, trang web có nhiều người dùng
lướt qua hơn sẽ là trang quan trọng hơn và
nằm trên đầu danh sách tìm kiếm.
6
1. PAGERANK
PageRank là gì?
- Pagerank là phân bố xác suất khả năng khi một người
click chuột ngẫu nhiên vào đường link và sẽ tới đc
trang web cụ thể.
- PageRank gán một số cho mỗi trang web.
- Một trang có PageRank càng cao, thì "tính quan trọng"
của nó càng cao.
- Thuật toán PageRank không cố định, có nhiều biến thể
và chúng có thể làm thay đổi PageRank tương đối của
hai trang web bất kỳ.
7
1. PAGERANK
PageRank là gì?
Xác suất bắt đầu v0=
A
B
C
D
0
1/2
1
0
MaBtrận chuyển
đổi
1/3
0
0
1/2
A
C
1/3
0
0
1/2
D
1/3
1/2
0
0
8
1. PAGERANK
PageRank là gì?
V=V0.M
V0
V1
V2
V3
Xác suất bắt đầu v0=
A
B
C
D
0
1/2
1
0
MaBtrận chuyển
đổi
1/3
0
0
1/2
V50
Xác suất người dùng truy cập đến trang A
cao hơn so với những trang khác.
=> Trang A có tầm quan trọng cao hơn so
với những trang khác.
A
C
1/3
0
0
1/2
D
1/3
1/2
0
0
9
1. PAGERANK
Cấu trúc của web
Từ in SCC
liên kết đến
Chỉ liên
kết đến
SCC
(in SCC)
Liên kết đến
out SCC
Liên kết
mạnh mẽ
với nhau
(SCC)
Kết thúc chết
Chỉ SCC
liên kết
đến (out
SCC)
Bẫy nhện
Từ in SCC liên kết
đến out SCC
10
1. PAGERANK
Kết thúc chết
- Một trang không có liên kết ra được gọi là một kết thúc chết.
v0=
Không đánh giá được tầm quan trọng.
11
1. PAGERANK
Kết thúc chết
v0=
Giải
pháp
- Tính PageRank của C:
P(C) = [ P(A) / 3 ]+ [ P(D) / 2 ]
= [ 2/9 / 3 ]+ [ 3/9 / 2 ]
= 13/54
12
1. PAGERANK
Bẫy nhện
- Bẫy nhện là một tập hợp các nút không có kết thúc chết nhưng không có đường cung đi ra.
Nút bẫy nhện có tầm quan trọng tuyệt đối.
13
1. PAGERANK
Bẫy nhện
Giải
pháp
Thêm xác suất nhỏ người dùng chuyển đến trang
web khác một cách ngẫu nhiên.
Xác xuất người dùng chuyển đến trang ngẫu nhiên.
- Trong đó:
e
thường có giá trị từ 0.8 – 0.9
là vector có giá trị là 1
14
2. TÍNH HIỆU QUẢ CỦA PAGERANK
Đại diện cho các
ma trận chuyển tiếp
Hỗ trợ
phân tán
Đại diện cho các
ma trận
15
3. PAGERANK TOPIC-SENSITIVE
Topic-Sensitive là gì?
“Apple”
Tên công ty
1. Quyết định về các chủ đề cần phân loại.
Tên loại quả
2. Phân loại từng trang web thuộc loại chủ
đề nào.
Giải
pháp
Tênloạiloại
bánh
Tên
bánh
……………….
3. Xác định người dùng đang muốn tìm về
chủ đề nào.
+ Cho người dùng tự xác định.
+ Dựa trình lịch sử duyệt web của
người dùng.
4. Tính toán PageRank.
16
3. PAGERANK TOPIC-SENSITIVE
Topic-Sensitive là gì?
Trái cây
Công ty
A,C
B,D
1. Quyết định về các chủ đề cần phân loại.
+ Dựa trình lịch sử duyệt
web của người dùng
=> Tìm về “Công ty”
2. Phân loại từng trang web thuộc loại chủ
đề nào.
S là tập web trong chủ đề.
|S| là số phần tử trong tập S.
es là một vector có giá trị 0 hoặc 1.
3. Xác định người dùng đang muốn tìm về
chủ đề nào.
+ Cho người dùng tự xác định.
+ Dựa trình lịch sử duyệt web của
người dùng.
4. Tính toán PageRank.
17
3. PAGERANK TOPIC-SENSITIVE
Topic-Sensitive là gì?
Trái cây
Công ty
A,C
B,D
+ Dựa trình lịch sử duyệt
web của người dùng
=> Tìm về “Công ty”
S là tập web trong chủ đề.
|S| là số phần tử trong tập S.
es là một vector có giá trị 0 hoặc 1.
+ Chọn = 0.8 =>
+ Ta có: (1 - ) = 1/5, |S| là 2, và eS có giá trị là
1 cho B, D và 0 cho A, C.
=> (1 - ) eS / | S | có giá trị là 1/10 cho B, D và
0 cho A, c
Như vậy, phương trình cần phải lặp là:
18
4. HUBS AND AUTHORITIES
- Thuật toán Hubs and Authorities (HITS)
Hyperlink Induced Topic Search
Kleinberg
Tự động xác định Hubs/Authorities
Phụ thuộc vào truy vấn tìm kiếm
- Tiêu
chí: niệm quan trọng của HITS
Hai khái
• Hubs:
Một Hub
nếuchứa
nó liên
kết đến
các
các tốt
trang
các liên
kết đến
Authorities
tốt.có chủ đề đang tìm kiếm.
các
trang khác
• Authorities:
Một Authority
nếu chứa
nó được
liên kết
cáctốt
trang
nội dung
về
bởi các
Hubstìm
tốt.kiếm.
chủ
đề đang
19
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
- Ma trận liên kết của trang web (L):
Cho n trang web được liên kết với
nhau thì ma trận L là:
ma trận vuông cấp n x n
mỗi phần tử Lij = 1 nếu có liên
kết từ trang i đến trang j,
ngược lại Lij = 0.
20
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
Tìm ma trận liên kết các trang web (L)
A B C D E
A 0
B 1
L =C 0
D 0
E
0
1
1 1
0
0 0
0
0
1 1
1
1
0 0
0
0 0
0 0
0
21
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
- Ma trận chuyển vị của ma trận liên
kết trang web (LT): Cho n trang web
T
được liên kết với nhau thì ma trận L
là:
ma trận vuông cấp n x n
mỗi phần tử = 1 nếu có liên
kết từ trang j đến trang i,
ngược lại = 0.
22
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
Tìm ma trận chuyển vị của ma trận liên
T
kết các trang web (L )
A B C D E
A 0
1 0
0
0
B 1
LT =C 1
D 1
0 0
1
0
E
0
0 0 1 0
1 0 0 0
0 1
0
0
23
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
- Tiêu chí:
• Một Hub tốt nếu nó liên kết đến
các Authorities tốt.
• Một Authority tốt nếu nó được
liên kết bởi các Hubs tốt.
- h = La ( là hằng số)
- a = LTh ( là hằng số)
24
4. HUBS AND AUTHORITIES
- Ví dụ mô tả thuật toán
- h = La ( là hằng số)
- a = LTh ( là hằng số)
h, a đủ nhỏ thì
dừng
- Tính h = La
- Tính lại h
- h = LLTh
- a = LTLa
- Khởi tạo h là vector đơn vị
- Tính a = LTh
- Tính lại a với giá trị lớn nhất là 1 25
