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

IT4853 Tìm kiếm và trình diễn thông tin Phân tích liên kết, HITS 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  Giải thuật HITS  Tính hội tụ của giải thuật HITS 4Giải thuật HITS  Hyperlink-Induced Topic Search (HITS), Klei98  Có hai nhóm kết quả phù hợp trên Web:  Nhóm 1: Hubs: Trang giới thiệu: chứa danh sách liên kết có chất lượng cao, đáp ứng được nhu cầu thông tin.  Nhóm 2: Authorities: Trang uy tín: Có nội dung tốt, trực tiếp đáp ứng nhu cầu thông tin.  Hầu hết các phương pháp tìm kiếm không phân biệt hai nhóm kết quả phù hợp này. 5Điểm giới thiệu và điểm uy tín  Trang giới thiệu tốt cho một chủ đề phải chứa nhiều liên kết đến những trang uy tín của chủ đề đó.  Trang uy tín của một chủ đề phải được trích dẫn bởi nhiều trang giới thiệu tốt của chủ đề đó.  Định nghĩa quay vòng, sẽ sử dụng phương pháp lặp để tính điểm giới thiệu và điểm uy tín. 6Ví dụ trang giới thiệu và trang uy tín 7Tính điểm giới thiệu và điểm uy tín  Đầu tiên, thực hiện tìm kiếm như bình thường  Gọi tập kết quả là tập gốc  Mở rộng tập gốc với các trang có liên kết với các trang trong đó, gọi đây là tập cơ sở.  Cuối cùng, tính điểm giới thiệu và điểm uy tín cho các trang trong tập cơ sở. 8Tập gốc và tập cơ sở Tập gốc Tập gốc: Kết quả tìm kiếm thông thường 9Tập gốc và tập cơ sở Các trang với liên kết từ tập gốc Tập gốc 10 Tập gốc và tập cơ sở Các trang với liên kết đến tập gốc Tập gốc 11 Tập gốc và tập cơ sở Tập cơ sở = Tập gốc + Các trang có liên kết với tập gốc Tập gốc Tập cơ sở 12 Kích thước tập cơ sở [Klei98]  Tập gốc thường có 200-1000 nút.  Tập cơ sở có thể có tới 5000 nút.  Tìm các nút tập cơ sở bằng cách nào?  Theo liên kết đi ra bằng cách đọc các trang trong tập gốc.  Lấy liên kết đi vào (và liên kết đi ra) từ máy chủ liên kết. 13 Tìm trang giới thiệu và trang uy tín  Khởi tạo: với mọi x, h(x)1; a(x) 1;  Lặp cập nhật h(x), a(x);  Sau khi hội tụ  Đưa ra những trang với với điểm giới thiệu h() cao nhất  và , những trang với điểm uy tín a() cao nhất.   Hai danh sách kết quả: theo h() và theo a()! 14 Cập nhật giá trị 2 3 a4 = h1 + h2 + h3 1 5 7 6 4 4h4 = a5 + a6 + a7 15 Cập nhật giá trị  Với mỗi trang x :  yx yaxh  )()(  xy yhxa  )()( x x y’s y’s 16 Tỉ lệ  Để đảm bảo các giá trị h() và a() không phát triển quá lớn, có thể chia các giá trị cho các hằng số sau mỗi vòng lặp.  Giá trị cụ thể của hằng số tỉ lệ không quan trọng:  Chúng ta chỉ quan tâm tới kết quả xêp hạng. 17 Đặc điểm của giải thuật HITS  Gom những trang chất lượng theo tiêu trí độc lập với nội dung  Các trang trong tập cơ sở thường không chứa từ truy vấn  Về mặt lý thuyết, có thể trả về các trang tiếng Nhật cho truy vấn tiếng Anh Topic drift – Các trang mở rộng có thể hoàn toàn không liên quan đến câu truy vấn! 18 Nội dung chính  Giải thuật HITS  Tính hội tụ của giải thuật HITS 19 Tính hội tụ của giải thuật HITS  Ma trận kề A kích thước nn :  n là kích thước tập cơ sở.  Aij = 1 nếu tồn tại liên kết ij và = 0 trong trường hợp ngược lại. 1 2 1 2 3 1 2 3 0 1 0 1 1 1 1 0 0 A= 20 Viết lại dưới dạng ma trận  Gọi h và a là biểu diễn vec-tơ của điểm giới thiệu và điểm uy tín.  Có thể biểu diễn luật cập nhật như sau: h=Aa; a=Ath   h=AAth và a=AtAa.  Như vậy, h là vec-tơ riêng của AAt và a là vec-tơ riêng của AtA.  Có thể xác định các vec-tơ riêng này bằng phương pháp lũy thừa. 21 So sánh PageRank và HITS  PageRank có thể tính trước, HITS phải được tính trong quá trình thực hiện truy vấn  Hạn chế khả năng ứng dụng, khối lượng tính toán lớn.  tuy nhiên, có thể hoán đổi vị trí, áp dụng HITS cho toàn bộ Web và PageRank cho tập kết quả!  Cho rằng, trên Web một trang có điểm giới thiệu cao thường đồng thời có điểm uy tín cao!   Như vậy khác biệt giữa xếp hạng theo HITS và theo PageRank có thể không quá lớn. 22