![](images/graphics/blank.gif)
Bài giảng Tìm kiếm và trình diễn thông tin: Bài 21 - TS.Nguyễn Bá Ngọc
lượt xem 8
download
![](https://tailieu.vn/static/b2013az/templates/version1/default/images/down16x21.png)
Bài giảng Tìm kiếm và trình diễn thông tin: Bài 21 - Phân tích liên kết, PageRank tập trung trình bày các vấn đề về dữ liệu liên kết; văn bản liên kết; chỉ mục văn bản liên kết; phân tích trích dẫn; trước PageRank: Phân tích trích dẫn;...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Tìm kiếm và trình diễn thông tin: Bài 21 - TS.Nguyễn Bá Ngọc
- (IT4853) Tìm kiếm và trình diễn thông tin Phân tích liên kết, PageRank
- Giảng viên TS. Nguyễn Bá Ngọc Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603 Email: ngocnb@soict.hust.edu.vn Website: http://is.hust.edu.vn/~ngocnb 2
- Nội dung chính Dữ liệu liên kết Phân tích trích dẫn Giải thuật PageRank 3
- Web là đồ thị có hướng Siêu liên kết Trang A Anchor Trang B Giả thuyết 1: Siêu liên kết là tín hiệu chất lượng Siêu liên kết A B là sự công nhận chất lượng trang B từ phía tác giả trang A. Giả thuyết 2: Văn bản liên kết mô tả trang B Văn bản liên kết là văn bản xung quanh thẻ Ví dụ, Xem tài liệu tham khảo ở đây “Xem tài liệu tham khảo ở đây” là văn bản liên kết 4
- Văn bản liên kết Ví dụ, trang www.ibm.com, đa phần là hình ảnh, rất ít từ ibm. Tìm kiếm trên [nội dung của d] + [văn bản liên kết d] sẽ hiệu quả hơn nếu chỉ tìm kiếm trên [nội dung của d] “ibm” “ibm.com” “Trang chủ của IBM” Hàng triệu văn bản liên kết chứa từ “ibm” www.ibm.com 5
- Văn bản liên kết đến www.ibm.com chứa từ ibm 6
- Chỉ mục văn bản liên kết Văn bản liên kết có thể mô tả trang web tốt hơn chính nội dung trang web đó. Có thể gán cho văn bản liên kết trọng số cao hơn chính nội dung trang web. 7
- Nội dung chính Dữ liệu liên kết Phân tích trích dẫn Giải thuật PageRank 8
- Trước PageRank: Phân tích trích dẫn Đối với tài liệu là sách, báo, tạp trí v.v. Một tài liệu có thể trích dẫn một tài liệu khác, ví dụ, trích dẫn tài liệu tham khảo. Trích dẫn trong những tài liệu này có vai trò tương tự siêu liên kết đối với nhứng trang web Ứng dụng phân tích trích dẫn Xác định độ tương đồng giữa các tài liệu Đánh giá điểm uy tín (impact factor) của tạp trí v.v. 9
- Phân tích trích dẫn: Mức đồng tham khảo Mức đồng tham khảo của hai tài liệu A và B là số tài liệu được trích dẫn bởi cả A và B. Được sử dụng để đo độ tương đồng giữa các tài liệu, tác giả Kessler, công bố năm 1963. A B Có nên chuẩn hóa theo số lượng trích dẫn? 10
- Phân tích trích dẫn: Mức đồng tham chiếu Mức đồng tham chiếu là số văn bản trích dẫn cùng lúc cả A và B. Tương tự mức đồng tham khảo, tác giả Small, công bố năm 1973. A B Có nên chuẩn hóa theo tổng số tài liệu trích dẫn A hoặc trích dẫn B? 11
- Phân tích trích dẫn: Độ uy tín Độ uy tín (impact factor) Tác giả Garfield, công bố năm 1972 Được tính và công bố thường niên bởi Institute for Scientific Information (ISI). Độ uy tín của một tạp trí J trong năm Y là số lượng trích dẫn trung bình từ các tài liệu được công bố trong năm Y tới tạp trí J trong năm Y1 hoặc Y2. Không tính chất lượng của báo cáo chứa trích dẫn. 12
- Phân tích trích dẫn: Xếp hạng Pinski và Narin [1976], xếp hạng báo cáo khoa học dựa trên phân tích trích dẫn. PageRank được phát triển theo phương pháp phân tích trích dẫn của Pinski và Narin. 13
- Nội dung chính Dữ liệu liên kết Phân tích trích dẫn Giải thuật PageRank 14
- Mô hình PageRank cơ bản Mô hình duyệt Web ngẫu nhiên Giả sử người dùng Web thực hiện mở các trang web theo quy luật sau: Bắt đầu với một trang được lựa chọn ngẫu nhiên Sau mỗi bước, mở ngẫu nhiên một liên kết trên trang hiện tại (xác suất lựa chọn liên kết được phân bố đồng đều). Tỉ lệ đã xem mỗi trang có xu hướng ổn định sau khi lặp thao tác mở liên kết với số lần đủ lớn. Tỉ lệ này là PageRank của trang Web. PageRank = tỉ lệ mở liên kết với số bước lớn = xác suất xem trang Web ở trạng thái ổn định 15
- Biểu diễn mô hình duyệt Web ngẫu nhiên: Chuỗi Markov Chuỗi Markov bao gồm N trạng thái, và ma trận xác suất chuyển trạng thái kích thước N x N Mỗi trạng thái ứng với một trang Web Với 1 ≤ i, j ≥ N , giá trị Pij là xác suất nếu trạng thái tiếp theo là j, biết rằng trạng thái hiện tại là i Với i bất kỳ, j 1 Pij 1 N 16
- Ví dụ đồ thị Web
- Ma trận kề d0 d1 d2 d3 d4 d5 d6 d0 0 0 1 0 0 0 0 d1 0 1 1 0 0 0 0 d2 1 0 1 1 0 0 0 d3 0 0 0 1 1 0 0 d4 0 0 0 0 0 0 1 d5 0 0 0 0 0 1 1 d6 0 0 0 1 1 0 1 18
- Ma trận xác suất chuyển trạng thái d0 d1 d2 d3 d4 d5 d6 d0 0.00 0.00 1.00 0.00 0.00 0.00 0.00 d1 0.00 0.50 0.50 0.00 0.00 0.00 0.00 d2 0.33 0.00 0.33 0.33 0.00 0.00 0.00 d3 0.00 0.00 0.00 0.50 0.50 0.00 0.00 d4 0.00 0.00 0.00 0.00 0.00 0.00 1.00 d5 0.00 0.00 0.00 0.00 0.00 0.50 0.50 d6 0.00 0.00 0.00 0.33 0.33 0.00 0.33 19
- Tỉ lệ mở liên kết Điều kiện để tỉ lệ mở liên kết ổn định với số bước đủ lớn? Chuỗi Markov của đồ thị Web phải là ergodic! 20
![](images/graphics/blank.gif)
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Tìm kiếm và trình diễn thông tin: Giới thiệu môn học
7 p |
8 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 17: Quảng cáo và SPAM
28 p |
3 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 15: Vấn đề tìm kiếm trên Web
27 p |
6 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 14: Phân cụm văn bản (2)
22 p |
7 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 13: Phân cụm văn bản
44 p |
12 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 12: Phân lớp văn bản (2)
24 p |
6 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 11: Phân lớp văn bản
31 p |
2 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 10: Các phương pháp xây dựng chỉ mục ngược
33 p |
8 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 9: Nén chỉ mục ngược
33 p |
9 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 8: Đánh giá kết quả tìm kiếm (2)
24 p |
13 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 7: Đánh giá kết quả tìm kiếm
42 p |
5 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 6: Mô hình ngôn ngữ
27 p |
6 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 5: Mô hình nhị phân độc lập
37 p |
9 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 4: Mô hình không gian vec-tơ
31 p |
6 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 3: Xử lý từ truy vấn
41 p |
15 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 2: Thực hiện truy vấn trên chỉ mục ngược
26 p |
4 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 1: Phương pháp tìm kiếm Boolean
30 p |
8 |
1
-
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 20: Phân tích liên kết, HITS
19 p |
6 |
1
![](images/icons/closefanbox.gif)
![](images/icons/closefanbox.gif)
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn
![](https://tailieu.vn/static/b2013az/templates/version1/default/js/fancybox2/source/ajax_loader.gif)