Bài giảng Tìm kiếm và trình diễn thông tin: Bài 22 - TS.Nguyễn Bá Ngọc

Phân tích liên kết, HITS của bài 22 thuộc bộ bài giảng Tìm kiếm và trình diễn thông tin với các nội dung chính như: Giải thuật HITS; điểm giới thiệu và điểm uy tín; tính điểm giới thiệu và điểm uy tín; tập gốc và tập cơ sở;...
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 22 - TS.Nguyễn Bá NgọcIT4853 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: http://is.hust.edu.vn/~ngocnb 2 Nội dung chính Giải thuật HITS Tính hội tụ của giải thuật HITS 3 Giả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. 4 Đ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. 5Ví dụ trang giới thiệu và trang uy tín 6 Tí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ở. 7 Tập gốc và tập cơ sở Tập gốcTập gốc: Kết quả tìm kiếm thông thường 8 Tập gốc và tập cơ sở Tập gốcCác trang với liên kết từ tập gốc 9 Tập gốc và tập cơ sở Tập gốcCác trang với liên kết đến tập gốc 10 Tập gốc và tập cơ sở Tập cơ sở Tập gốcTập cơ sở = Tập gốc + Các trang có liên kết với tập gốc 11 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. 12 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()! 13Cập nhật giá trị 1 2 4 a4 = h1 + h2 + h3 3 5h4 = a5 + a6 + a7 4 6 7 14 Cập nhật giá trị Với mỗi trang x : h( x )   a( y) x y x y’s a( x)   h( y ) y x y’s x 15 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. 16 Đặ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 AnhTopic drift – Các trang mở rộng có thể hoàn toàn không liên quan đến câu truy vấn! 17 Nội dung chính Giải thuật HITS Tính hội tụ của giải thuật HITS 18 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 3 1 2 1 0 1 0 A= 2 1 1 1 3 1 0 0 19 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. 20 ...