Download miễn phí Khóa luận Link spam với đồ thị web và hạng trang web
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
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
Danh sách bảng
4.1 Tập các site nhân của link farm . . . . . . . . . . . . . . . . . . . . 38
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-07-khoa_luan_link_spam_voi_do_thi_web_va_hang_trang_w.XicHE71sad.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54134/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
à ổn định, và giá trị
đó được coi là hạng trang theo phương pháp PageRank[9].
1.4 Tổng kết chương 1
Xác định và loại bỏ ảnh hưởng của web spam đối với bài toán tính hạng trang là
một vấn đề quan trọng trong máy tìm kiếm. Chương này đã giới thiệu về các công
nghệ tạo spam chính hiện nay, trong đó link spam là kỹ thuật đáng quan tâm vì
có ảnh hưởng lớn, trực tiếp đến kết quả tính hạng trang của máy tìm kiếm. Các
chương tiếp theo sẽ trình bày các thuật toán tính hạng trang cơ bản và các phương
pháp cải tiến nhằm nâng cao chất lượng tính hạng trang với việc nhận diện và xử
lý link spam.
Chương 2
Một số phương pháp tính hạng
trang cơ bản
Để đánh giá độ quan trọng của các trang web, máy tìm kiếm có thể sử dụng các
thuật toán tính hạng độc lập yêu cầu người dùng tức là chỉ dựa vào số lượng các
liên kết giữa các trang web. Nhiều thuật toán tính hạng trang đang được sử dụng
đều tính toán dựa trên liên kết giữa các trang web với nhau, trong đó các thuật
toán điển hình là PageRank, HITS [6, 9]. Kết quả nghiên cứu của chúng tui nhằm
tăng tốc tính hạng trang và cài đặt vào máy tìm kiếm cũng được trình bày [2, 12].
2.1 Phương pháp PageRank
2.1.1 Phương pháp
Đây là một trong các phương pháp tính hạng đầu tiên dựa vào mối liên kết giữa
các trang. Page và các đồng tác giả [9] đã đưa ra ý tưởng: độ quang trọng của một
trang chịu ảnh hưởng của độ quan trọng từ các trang liên kết đến nó. Và công thức
tính PageRank cho một trang u, gọi là piu được tính như sau:
piu =
∑
i∈BI(i)
pii
Ni
(2.1)
Với BI(i) là tập hợp các trang có liên kết đến trang i.
2.1. PHƯƠNG PHÁP PAGERANK 14
Biểu diễn đồ thị Web bởi ma trận chuyển P , khi đó phương trình (2.1) được
viết lại dưới dạng ma trận:
pi = piP (2.2)
Trong đó: pi = (pi1, pi2, . . . pin) là véctơ hạng các trang web, với thành phần pii
là hạng của trang i.
Từ (2.2) cho thấy véctơ hạng trang pi chính là véctơ riêng của ma trận chuyển
P tương ứng với giá trị riêng λ = 1.
Do tính chất của chuỗi Markov, để tính véctơ riêng của P thuật toán giả thiết
rằng đồ thị trang Web là liên thông, tức với cặp hai trang Web i, j bất kì luôn có
đường đi từ i tới j và ngược lại. Tuy nhiên thực tế trên World Wide Web (WWW)
vẫn tồn tại không ít các trang web không có liên kết đến hay liên kết ra nên việc
giả thiết đồ thị Web liên thông là không hợp lý. Và trong ma trận P vẫn tồn tại
hàng chỉ toàn số 0, nên không tồn tại một phân phối xác suất dừng ổn định của
P hay chính là véctơ hạng trang. Vậy cần biến đổi ma trận P thành P ′ cho
phù hợp.
Định nghĩa véctơ v, được chuẩn hóa ‖ v ‖= 1, xác định xác suất phân phối với
vi là xác suất trang web i được gọi đến ở lần duyệt web đầu tiên. Véctơ v có vai trò
trong việc hướng kết quả PageRank theo chủ đề, lĩnh vực mong muốn. Khi không
xét đến ngữ cảnh đó có thể chọn vi =
1
n
với ∀i = 1, 2..n .
Gọi d là véctơ n× 1 xác định các dangling nút:
di =
{
1 nếuN(i) = 0
0 ngược lại
Ma trận P ′ được xác định:
P ′ = P + dv (2.3)
Khi thay đổi ma trận P như vậy tức thêm các liên kết ảo từ các dangling nút
tới tất cả các nút khác trong đồ thị Web theo phân phối xác suất v. Điều đó giúp
tránh việc khi duyệt các trang không có liên kết ra sẽ không duyệt tiếp được.
Để đảm bảo phân phối dừng ổn định (duy nhất), chuỗi Markov tương ứng với
quá trình duyệt Web của người dùng cần có tính chất ergodic, tức từ một trang
2.1. PHƯƠNG PHÁP PAGERANK 15
web người dùng có thể chuyển tới một trang bất kì khác. Do vậy ma trận Markov
P˜ được xác định như sau:
P˜ = αP ′ +
(1− α)
J
(2.4)
Với: J = [1]n×1 v
α: là hệ số hãm
Qua thực nghiệm, α thường được chọn giá trị 0.85. Với ý nghĩa, tại mỗi bước
duyệt Web người dùng có thể chuyển tới một trang trong các liên kết ra từ trang
hiện tại với xác suất α và chuyển tới các trang khác trong đồ thị Web với xác suất
(1− α) theo phân phối v.
Khi đó, thay vì tính vector riêng của ma trận P ta tính vector riêng pi của ma
trận P˜ :
pi = piP˜ (2.5)
Theo tính chất của chuỗi Markov, tổng các thành phần của véctơ pi bằng 1:
n∑
i=1
pii = 1
Véctơ hạng trang được tính toán dựa theo liên kết, hạng của một trang web
phụ thuộc giá trị hạng của các trang liên kết đến, nên việc tính hạng có thể dẫn
tới vòng lặp vô hạn. Tuy nhiên với công thức 2.5, véctơ hạng trang có thể được
tính một cách đơn giản đó là tính véctơ riêng của ma trận P˜ .
Có nhiều phương pháp tính véctơ riêng của ma trận nhưng với ma trận rất lớn
của đồ thị các trang web thì không phải phương pháp nào cũng phù hợp. Phần
sau sẽ giới thiệu phương pháp lặp tính véctơ riêng của ma trận, tính hạng
2.1.2 Tính hạng trang dựa vào tính chất hội tụ
Page và Brin [9] đã sử dụng phương pháp lặp để tính hạng trang và qua thực
nghiệm họ đưa ra đồ thị hình 2.1 biểu diễn mối quan hệ giữa bước lặp và độ sai
lệch giữa hai vòng lặp liên tiếp.
Từ đồ thị, các tác giả thấy độ sai khác giá trị hạng trang giữa hai vòng lặp liên
tiếp giảm tuyến tính theo hàm log n, và tốc độ hội tụ khá nhanh sau khoảng 50
vòng lặp. Phương pháp tính hạng bằng cách thực hiện các vòng lặp, và từ tính hội
2.1. PHƯƠNG PHÁP PAGERANK 16
Hình 2.1: Tốc độ hội tụ
Thuật toán 1 Tính PageRank theo phương pháp lặp
1: i← 0
2: pi[0] ← v
3: repeat
4: i← i + 1
5: pi
← αP Tpi[i−1] + (1− α)v
6: until ‖ pi − pi[i−1] ‖<
7: pi = pi
2.1. PHƯƠNG PHÁP PAGERANK 17
tụ xác định ngưỡng , là sai số chấp nhật được của giá trị hạng trang, làm điều
kiện dừng (xem thuật toán 1).
Phương pháp PageRank khá tốt, được áp dụng trong rất nhiều máy tìm kiếm
trên Internet. Nhưng do dựa trên vòng lặp, trong khi đồ thị Web có kích thước rất
lớn (khoảng 11,5 tỉ trang web)1 nên thời gian tính toán có thể lên tới nhiều ngày.
Điều này ảnh hưởng đến chất lượng của máy tìm kiếm. Do vậy, Sepandar Kamvar
và các đồng tác giả [?] đã đưa ra ý tưởng cải tiến để tăng tốc độ tính toán, gọi
là phương pháp Modified Adaptive PageRank hay MAP. Và chúng tui [1] đã tiến
hành thử nghiệm, đưa ra những đánh giá khá tốt về phương pháp này.
Qua thực nghiệm tính hạng, các tác giả nhận thấy tốc độ hội tụ của các trang
là không giống nhau. Do đó có thể giảm bớt tính toán, tận dụng những trang hội
tụ trước bằng cách không tính lại hạng cho các trang đó ở các vòng lặp tiếp sau.
Giả sử tại vòng lặp thứ k, có các tập hợp C các trang có hạng hội tụ theo và N
là tập các trang có hạng chưa hội tụ. Sắp xếp lại ma trận P và véc tơ pi ta có:
pi[k] = (pi
[k]
N pi
[k]
C )và P =
(
PNN PNC
PCN PCC
)
Trong đó:
PNN : là ma trận kề của các trang chưa hội tụ có liên kết đến các trang
chưa hội tụ.
PNC : là ma trận kề của các trang chưa hội tụ có liên kết đến các trang
đã hội tụ.
PCN : là ma trận kề của các trang đã hội tụ có liên kết đến các trang
chưa hội tụ.
PCC : là ma trận kề của các trang đã hội tụ có liên kết đến các trang
đã hội tụ.
Vì piC đã hội tụ nên ở vòng lặp thứ k không cần tính lại, ta chỉ tính thành phần
chưa hội tụ: pi
(k+1)
N = PNNpi
(k)
N + PCNpi
(k)
C
Với việc biến đổi m...
