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

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;...
Nội dung trích xuất từ tài liệu:
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 5Văn bản liên kết đến www.ibm.comchứ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 BCó 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 BCó nên chuẩn hóa theo tổng số tài liệu trích dẫnA 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 Y1 hoặc Y2.  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 16Ví dụ đồ thị WebMa 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 d6d0 0.00 0.00 1.00 0.00 0.00 0.00 0.00d1 0.00 0.50 0.50 0.00 0.00 0.00 0.00d2 0.33 0.00 0.33 0.33 0.00 0.00 0.00d3 0.00 0.00 0.00 0.50 0.50 0.00 0.00d4 0.00 0.00 0.00 0.00 0.00 0.00 1.00d5 0.00 0.00 0.00 0.00 0.00 0.50 0.50d6 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 ...