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

Chia sẻ: Codon_02 Codon_02 | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

77
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ở;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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: 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. 5
Ví 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ốc Tậ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ốc Cá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ốc Cá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ốc Tậ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()! 13
Cập nhật giá trị 1 2 4 a4 = h1 + h2 + h3 3 5 h4 = 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 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! 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