ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thu Trang
Link spam với đồ thị web
và hạng trang web
Khoá luận tốt nghiệp đại học hệ chính quy
Ngành: Công Nghệ Thông Tin
Cán bộ hướng dẫn: TS. Hà Quang Thụy
Cán bộ đồng hướng dẫn: CN. Nguyễn Hoài Nam
HÀ NỘI, 2006
Tóm tắt
Bên cạnh sự phát triển của các máy tìm kiếm đặc biệt là các phương pháp tính
hạng trang thì công nghệ spam nhằm đánh lừa máy tìm kiếm để nâng cao hạng
của các trang web cũng phát triển không ngừng. Do vậy một vấn đề đặt ra là phải
nhận diện các trang web là spam, và đưa ra giải pháp tính hạng phù hợp chính
xác hơn có loại bỏ spam.
Khóa luận với đề tài LinkSpam với đồ thị web và hạng trang web tập trung
nghiên cứu các phương pháp nhận diện spam để nâng cao chất lượng hạng trang,
và đề xuất giải pháp tính hạng có xử lý link spam. Khóa luận đã tiến hành thử
nghiệm với máy tìm kiếm NUTCH cho các thuật toán LinkSpam và thu được
những kết quả khả quan ban đầu. Khóa luận cũng giới thiệu các kết quả nghiên
cứu của chúng tôi đã được công bố trong [1,2,12].
ii
Lời cảm ơn
Trước tiên, em xin gửi lời cảm ơn sâu sắc nhất đến thầy giáo TS.Hà
Quang Thụy và CN. Nguyễn Hoài Nam, người đã tận tình hướng dẫn
em trong quá trình thực hiện khóa luận tốt nghiệp.
Em chân thành cảm ơn các thầy cô và các cán bộ của trường Công
Nghệ đã tạo cho em những điều kiện thuận lợi để học tập và nghiên
cứu.
Em xin cảm ơn các thầy cô giáo trong bộ môn Các Hệ Thống Thông
Tin, và nhóm xemina Data Mining đã giúp đỡ, hỗ trợ em về kiến thức
chuyên môn.
Cuối cùng, em muốn cảm ơn gia đình và bạn bè, đặc biệt là bố và mẹ,
những người luôn giành cho em tình yêu, niềm tin và động viên giúp
em hoàn thành đề tài.
Sinh Viên
Nguyễn Thu Trang
iii
Mục lục
Tiêu đề i
Tóm tắt ii
Danh sách bảng vi
Danh sách hình vẽ vii
Danh sách các ký hiệu.. viii
1 Tổng quan về hạng trang và web spam 3
1.1 Giới thiệu hạng trang và spam ..................... 3
1.2 Các công nghệ tạo Spam ........................ 5
1.2.1 Spam văn bản .......................... 5
1.2.2 Spam liên kết .......................... 6
1.2.3 Công nghệ giả dạng ....................... 9
1.3 Đồ thị Web ............................... 10
1.3.1 Biểu diễn đồ thị Web ...................... 10
1.3.2 Mô hình Markov ........................ 11
1.4 Tổng kết chương 1 ........................... 12
2 Một số phương pháp tính hạng trang cơ bản 13
2.1 Phương pháp PageRank ........................ 13
2.1.1 Phương pháp .......................... 13
2.1.2 Tính hạng trang dựa vào tính chất hội tụ ........... 15
2.1.3 Đánh giá ............................. 18
2.2 Phương pháp HITS ........................... 18
2.2.1 Thuật toán ........................... 18
2.2.2 Đánh giá ............................. 20
iv
MỤC LỤC v
2.3 Phương pháp CCP ........................... 21
2.3.1 Thuật toán ........................... 21
2.3.2 Đánh giá ............................. 23
3 Các phương pháp xác định LinkSpam 24
3.1 Giới thiệu ................................ 24
3.2 Phương pháp TrustRank ........................ 25
3.2.1 Nội dung phương pháp ..................... 26
3.2.2 Đánh giá phương pháp ..................... 29
3.3 Phương pháp xác định Link Farm ................... 30
3.3.1 Nội dung phương pháp ..................... 30
3.3.2 Đánh giá ............................. 32
3.4 Đề xuất phương pháp cải tiến ..................... 34
4 Thử nghiệm 36
4.1 Giới thiệu hệ thống NUTCH ...................... 36
4.2 Thử nghiệm ............................... 37
4.2.1 Môi trường thử nghiệm ..................... 37
4.2.2 Kết quả ............................. 37
Kết luận 40
Tài liệu tham khảo 41
A Mã chương trình 43
A.1 Phân tích liên kết ............................ 43
A.2 Lọc Spam ................................ 44