Tìm kiếm và trình diễn thông tin - Phân tích liên kết, PageRank

(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: 2 3Nội dung chính  Dữ liệu liên kết  Phân tích trích dẫn  Giải thuật PageRank 4Web là đồ thị có hướng Trang A Siêu liên kết Trang BAnchor  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 5Vă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] www.ibm.com “ibm” “ibm.com” “Trang chủ của IBM” Hàng triệu văn bản liên kết chứa từ “ibm” 6Văn bản liên kết đến www.ibm.com chứa từ ibm 7Chỉ 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. 8Nội dung chính  Dữ liệu liên kết  Phân tích trích dẫn  Giải thuật PageRank 9Trướ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. 10 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? 11 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? 12 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. 13 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. 14 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 15 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 16 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ỳ, 11   N j ij P Ví dụ đồ thị Web 18 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 Ma trận kề 19 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 Ma trận xác suất chuyển trạng thái 20 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! 21 Điều kiện ergodic  Chuỗi Markov tương ứng sẽ là ergodic nếu:  Luôn tồn tại đường đi giữa hai đỉnh bất kỳ: Có thể di chuyển từ một trang bất kỳ tới một trang bất kỳ;  Không có chu trình: Không thể chia các đỉnh của đồ thị thành nhiều nhóm sao cho quá trình duyệt Web trở thành tiến trình tuần tự trên các nhóm này.  Chuỗi Markov của đồ thị sau không là ergodic 22 Điều kiện ergodic  Đồ thị Web không liên thông, có nhiều trang Web không có liên kết đi ra và có nhiều chu trình.  Tính PageRank bằng cách nào? Bổ xung bước nhảy để đảm bảo điều kiện ergodic của chuỗi Markov tương ứng! 23 Mô hình duyệt Web ngẫu nhiên với bước nhảy  Bước nhảy: Giả sử người dùng sẽ mở ngẫu nhiên một trang với xác suất 𝛼  Mô hình duyệt Web ngẫu nhiên với bước nhảy:  Bắt đầu với một trang được lựa chọn ngẫu nhiên  Sau mỗi bước, với xác suất 1- 𝛼 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).  Với xác suất 𝛼 mở ngẫu nhiên một trang bất kỳ.  Chuỗi Markov tương ứng là ergogic   Phân bố xác suất mở liên kết luôn trở nên ổn định sau số bước đủ lớn.   Luôn có thể xác định PageRank 24 Các ký hiệu  Gọi 𝑥 = (x1 , ..., xN) là vec-tơ tỉ lệ mở liên kết, với xi là tỉ lệ mở liên kết thứ i.  Xác suất người dùng đang xem trang i là xi;  S xi = 1  Cho biết ma trận xác suất chuyển trạng thái P, tỉ lệ mở liên kết ở bước tiếp theo là 𝑥P.  Gọi 𝜋= (p1, p2, , pN) là vec-tơ tỉ lệ mở liên kết ở trạng thái ổn định (đồng thời là vec-tơ PageRank)  𝜋 = 𝜋P Tính PageRank như thế nào? 25 Phương pháp lũy thừa  Hãy tính PageRank cho đồ thị với xác suất chuyển trạng thái như sau: 26 Phương pháp lũy thừa x1 Pt(d1) x2 Pt(d2) P11 = 0.1 P21 = 0.3 P12 = 0.9 P22 = 0.7 t0 0 1 0.3 0.7 = xP t1 0.3 0.7 0.24 0.76 = xP 2 t2 0.24 0.76 0.252 0.748 = xP 3 t3 0.252 0.748 0.2496 0.7504 = xP 4 . . . . . . t∞ 0.25 0.75 0.25 0.75 = xP ∞ Pt(d1) = Pt-1(d1) * P11 + Pt-1(d2) * P21 Pt(d2) = Pt-1(d1) * P12 + Pt-1(d2) * P22 𝜋= (p1, p2) = (0.25, 0.75) 27 Xác định ma trận xác suất chuyển trạng thái  Gọi A là ma trận kề của đồ thị, dòng i cột j bằng 1 nếu có cạnh từ i tới j; 𝛼 là xác suất nhảy ngẫu nhiên.  Giải thuật tổng quát xác định ma trận xác suất chuyển trạng thái gồm 4 bước sau:  1) Nếu hàng i của A không chứa 1 thì thay thế 0 bằng 1/N, với N là số đỉnh.  2) Đối với các hàng khác thực hiện chia các giá trị 1 cho số lượng trong hàng.  3) Nhân ma trận kết quả sau khi thực hiện 1) và 2) với 1 – 𝛼  4) Cộng mỗi phần tử của ma trận với 𝛼 / N 28 Nhược điểm của PageRank  Trong thực tế, người dung không duyệt Web theo cách ngẫu nhiên:  Nút Back, trang ưa thích, tìm kiếm, v.v.   Mô hình chuỗi Markov không diễn tả hết được các tình huống thực tế  Kết quá xếp hạng chỉ sử dụng PageRank có chất lượng thấp 29 Vai trò của PageRank  Trong thực tế điểm xếp hạng cuối cùng là tổng hợp của nhiều thành phần khác nhau, ngoài PageRank còn có văn bản liên kết, tần suất từ, khoảng cách v.v.  Còn nhiều cách cài đặt PageRank khác  Điểm PageRank là một tín hiệu xếp hạng quan trọng đối với tìm kiếm trên Web. 30