Link spam với đồ thị web và hạng trang web

ử tại thời điểm k, người dùng u đang duyệt trang web p thì tại bước tiếp theo, thời điểm (k + 1), người dùng đó có thể chọn một trong các liên kết ra từ p: out = {q|(p, q) ∈ E} để xem tiếp một cách ngẫu nhiên. Tức là tại thời điểm (k + 1), xác suất để người dùng u tới trang q ∈ out là 1/B(p). 1.4. TỔNG KẾT CHƯƠNG 1 12 Giả thiết chuỗi Markov được tạo ra bởi các bước duyệt ngẫu nhiên liên tiếp trên đồ thị Web G. Khi đó mô hình Markov được biểu diễn bởi ma trận xác suất chuyển P, là ma trận vuông cấp n (với n là số node trong đồ thị G) với thành phần pij là xác suất chuyển từ trạng thái i (trang i) tới trạng thái j (trang j ) chỉ với một bước chuyển. Từ đó, ma trận xác suất chuyển P của mô hình Markov tương đương ma trận chuyển P trong biểu diễn đồ thị Web (xem mục 1.3.1). Với p kij là xác suất chuyển từ trạng thái i đến j sau k bước chuyển. Theo tính chất ergodic của xích Markov suy ra có: nếu mini,j p k ij > 0 thì tồn tại phân phối dừng (hay bất biến) của xích Markov với ma trận xác suất chuyển P. Với giả thiết đồ thị web là liên thông, khi đó tính chất trên được thỏa mãn. Tức xác suất được duyệt tới của các trang trong đồ thị web là ổ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 tôi 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 hoặc 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 phải 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[i] ← αP Tpi[i−1] + (1− α)v 6: until ‖ pi[i] − pi[i−1] ‖<  7: pi = pi[i] 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 tôi [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 ma trận với độ hội tụ của các trang như vậy, quá trình tính toán đã thực sự cải thiện đáng kể. 1Đánh giá của Google 2.2. PHƯƠNG PHÁP HITS 18 2.1.3 Đánh giá PageRank là một phương pháp tính hạng khá tốt và quá trình tính toán độc lập với người dùng. Do vậy quá trình tính toán được thực hiện ngoại tuyến (offline) nên không ảnh hưởng đến tốc độ tìm kiếm. Tuy nhiên, vì thuật toán PageRank không quan tâm đến nội dung của trang web mà chỉ dựa vào các liên kết giữa các trang web, cụ thể là số lượng lên kết đến mỗi trang. Do đó, với sự ra đời của các công nghệ spam thì giá trị hạng trang sử dụng phương pháp PageRank không còn chính xác. 2.2 Phương pháp HITS Phương pháp HITS, do Kleinberg đưa ra [6], tính hạng của một trang web không chỉ dựa trên một giá trị độ quan trọng như PageRank mà nỗi trang web được xác định hai trọng số khác nhau: authority và hub. Thuật toán đưa ra dựa trên ý tưởng một trang có giá trị hub tốt là trang mà có nhiều liên kết ra, và một trang có authority tốt là trang được nhiều trang liên kết tới (hình 2.2). Trong đó các trọng số hub và authority có quan hệ qua lại với nhau: một trang có giá trị hub tốt hơn nếu trỏ tới nhiều trang có authority tốt, và những trang được càng nhiều trang hub tốt trỏ tới thì càng có giá trị authority tốt hơn. Hình 2.2: Mô tả tính chất authority và hub 2.2.1 Thuật toán Thuật toán chỉ làm việc trên một tập nhỏ các trang web, gọi là đồ thị con, chứ không phải toàn bộ đồ thị Web. Và tùy thuộc vào câu truy vấn của người dùng tức phương pháp tính này không hoàn toàn độc lập người dùng, với mỗi truy vấn 2.2. PHƯƠNG PHÁP HITS 19 Hình 2.3: Mở rộng tập cơ sở T từ tập nhân S khác nhau công việc tính toán phải được thực hiện lại. Tuy nhiên câu truy vấn chỉ có vai trò trong việc tạo đồ thị con chứ không ảnh hưởng tới phương pháp tính toán. Vì vậy trước tiên phải xây dựng đồ thị con các trang tùy theo truy vấn và sau đó dự vào liên kết giữa các trang trong đồ thị để xác định các giá trị authority và hub của các trang đến khi hai giá trị đó hội tụ (bằng nhau). • Tạo đồ thị con hay còn gọi là tập cơ sở S: từ tập nhân gồm các trang chứa, liên quan nhiều đến truy vấn, dựa vào các liên kết đến và liên kết ra của các trang trong tập nhân đó để mở rộng đồ thị. Việc mở rộng dừng lại khi đồ thị con đã đủ lớn hoặc đã loang hết tất cả các trang có liên kết đến, hoặc được liên kết ra từ tập nhân. Việc tìm tập nhân liên quan đến truy vấn có thể xác định dựa vào kết quả tìm kiếm của các máy tìm kiếm khác như Google: tập nhân được lấy từ các trang đầu tiên có thể là 10 địa chỉ trang web đầu tiên được trả về tương ứng với truy vấn. Hoặc là các trang có địa chỉ chứa nội dung truy vấn, ví dụ với truy vấn “java” thì trang chủ là Các trang web trong đồ thị con S cũng được đánh chỉ số từ 1 đến n và đồ thị được biểu diễn bởi ma trận kề A. • Tính giá trị authority và hub của các trang trong tập S. Các trọng số au- thority ai và hub hi của mỗi trang web được khởi tạo bằng 1 và sau đó sẽ được tính dựa theo công thức: ai = ∑ j∈B(i) hj và hi = ∑ j∈N(i) aj (2.6) 2.2. PHƯƠNG PHÁP HITS 20 Biểu diễn theo ma trận ta có: ~a = AT~h và ~h = A~a (2.7) Trong đó: ~a = (a1, a2, . . . an), ~h = (h1, h2, . . . hn) lần lượt là véc tơ trọng số authority, hub của các trang trong tập S. Từ 2.7 biến đổi ta được: ~a = AAT~a và ~h = ATA~h Vậy cũng tương tự như phương pháp PageRank, véc tơ a, h lần lượt là véc tơ riêng của các ma trận AAT và ATA. Do vậy tương tự phương pháp tính PageRank, có thể áp dụng tính chất hội tụ để tính véc tơ a, h. Véc tơ a, h thường được chuẩn Thuật toán 2 Tính HITS theo phương pháp lặp 1: a← (1, 1 . . . 1) 2: h← (1, 1 . . . 1) 3: k ← 0 4: repeat 5: k ← k + 1 6: for i = 1 to n do 7: a [k] i = ∑ j∈B(i) h [k−1] j 8: h [k] i = ∑ j∈N(i) a [k−1] j 9: end for 10: until ‖ a[k] − a[k−1] ‖<  11: a = a[k] 12: h = h[k] hóa: ∑ i a = ∑ i h = 1. Kleinberg [6] đã chỉ ra sự hội tụ của các trọng số authority và hub tức thuật toán thỏa mãn tính dừng nhưng chưa đưa ra được giới hạn số vòng lặp cần tính. Tuy nghiên thực nghiệm đã cho thấy thuật toán nhanh chóng hội tụ. 2.2.2 Đánh giá Thuật toán HITS có phần hướng người dùng do sử dụng thông tin truy vấn để xây dựng tập con S các trang web. Thuật toán đã thể hiện mối quan hệ chặt chẽ giữa các trang chủ (authority) và trang trung tâm (hub). 2.3. PHƯƠNG PHÁP CCP 21 Tuy nhiên thuật toán HITS lại cần tính toán trực tuyến (online), tức nhận được câu truy vấn rồi đồ thị con mới được xây dựng và sau đó các trọng số authority, hub được tính. Điều này làm chậm thời gian trả kết quả về cho người dùng. Nhưng có thể ứng dụng thuật toán HITS trong các phương pháp có xác định link spam sau này nhằm đánh tính độ ảnh hưởng của các trang xấu tới các trang khác khi đã xác định được tập nhân các trang xấu. 2.3 Phương pháp CCP Tuy phương pháp tính hạng trang PageRank không tính hạng trực tuyến nên không trực tiếp ảnh hưởng đến thời gian tìm kiếm của người dùng, nhưng độ trễ do thời gian tính hạng ảnh hưởng đến việc cập nhật thông tin. Như với Google quá trình crawl thực hiện hàng tháng do vậy thông tin về các trang web đặc biệt các liên kết giữa các trang thay đổi và cần tính lại hạng trang. Do đó thời gian tính hạng sẽ ảnh hưởng tới thời gian cập nhật thông tin mới của máy tìm kiếm. Trong thực tế đồ thị Web không liên thông và tồn tại rất nhiều trang web không có liên kết đến hoặc liên kết ra. Do vậy ma trận kề biểu diễn đồ thị Web thường là ma trận thưa. Do vậy với các phương pháp tính hạng trên, dù dựa vào tốc độ hội tụ của các trang nhưng quá trình tính toán trên toàn đồ thị Web vẫn chưa tối ưu. Chúng tôi đã nghiên cứu và đề xuất một phương pháp tính hạng với việc phân tích các thành phần liên thông nhằm giảm bớt công việc tính toán, giảm thời gian tính hạng trang [2, 12]. 2.3.1 Thuật toán Qua khảo sát mô hình Markov, các trạng thái có thể phân thành các lớp khác nhau và trong cùng một lớp các trạng thái có thể chuyển qua nhau. Khái niệm lớp các trạng thái trong mô hình Markov rất gần với khái niệm thành phần liên thông trong lý thuyết đồ thị. Do vậy việc phân lớp hay thành phần liên thông trong đồ thị Web để tính hạng trang là hoàn toàn khả thi. 2.3. PHƯƠNG PHÁP CCP 22 Giả sử đồ thị G có k thành phần liên thông, đồ thị được sắp xếp lại như sau: P =  P1 0 · · · 0 0 P2 · · · 0 ... ... . . . ... 0 0 · · · Pk  (2.8) Với: - Pi là ma trận kề kích thước ni × ni của thành phần liên thông thứ i - ∑k i=1 ni = n Chúng tôi định nghĩa: P˜i = αPi + (1− α) ni Ji i = 1, k (2.9) Với: Ji là ma trận J của thành phần liên thông i kích thước ni × ni Khi đó, véc tơ riêng ứng với từng khối ma trận Pi, i = 1, k: pii = piiP˜i (2.10) Và véc tơ hạng trang ˜ được tính: ˜ = (n1 n pi1, n2 n pi2, . . . , nk n pik ) (2.11) Trong [12] chúng tôi đã chứng minh ˜ chính là véc tơ riêng của ma trận P˜ . Do vậy˜ là véc tơ hạng của các trang web. Mỗi thành phần liên thông gọi là một khối. Nhằm nâng cao hiệu quả tính toán, chúng tôi đề xuất đặt giới hạn về độ lớn Max, Min cho các khối. Do vậy sau khi phân tách thành phần liên thông, các khối có độ lớn nhỏ hơn giới hạn dưới Min sẽ được gộp lại và các khối có độ lớn vượt quá Max sẽ được chia thành các khối nhỏ hơn có độ lớn phù hợp. Quá trình tính hạng gồm ba bước chính: • Chia đồ thị Web thành các thành phần liên thông (khối) với các ma trận kề tương ứng. • Tính véc tơ riêng PageRank của các trang trong mỗi thành phần liên thông, theo thuật toán PageRank. • Tổ hợp hạng trang cuối cùng theo công thức 2.11. 2.3. PHƯƠNG PHÁP CCP 23 2.3.2 Đánh giá Khi chúng ta sử dụng toàn bộ ma trận P để tính toán véc tơ riêng như trong phương pháp PageRank, thì với phép nhân ma trận thời gian tính toán là O(n2) trong đó n là số trang web. Mà thực tế đồ thị Web có tới hàng tỉ trang. Nhưng khi chúng ta đưa ma trận kề biểu diễn đồ thị về dạng các khối biểu diễn cho từng thành phần liên thông thì thời gian tính toán sẽ giảm đi rất nhiều. Giả sử chúng ta sẽ có k thành phần liên thông, khi đó với mỗi khối thời gian tính toán nhỏ hơn O(n2i max) và tổng thời gian tính toán sẽ nhỏ hơn k×O(n2imax) nhỏ hơn nhiều so với khi sử dụng cả ma trận lớn để tính toán. Đồng thời, việc tìm thành phần liên thông của đồ thị có thể tiến hành dễ dàng với thời gian đa thức O(n+m) với n là số đỉnh và m là số cạnh của đồ thị nên thời gian chi phí với việc tìm kiếm thành phần liên thông là không đáng kể. Như vậy, phương pháp do chúng tôi đề xuất có thời gian tính toán lý thuyết hiệu quả hơn đối với phương pháp PageRank. Hơn nữa, nếu kết hợp phương pháp này với những phương pháp hỗ trợ tính toán như MAP thì thời gian tính toán được giảm đi đáng kể. Sử dụng thành phần liên thông chúng ta có thể làm giảm đi số vòng lặp tính toán do kích thước ma trận giảm nên tốc độ giảm của véc tơ hạng càng nhanh. Ngoài ra với chúng ta còn có thể tiến hành song song hoá quá trình tính hạng. Với phương pháp chia ma trận thành các thành phần theo tiêu chí cùng host cũng làm giảm số vòng lặp nhưng lại được chia làm hai bước tính hạng, mất thời gian tính toán hạng cho khối. Do vậy độ phức tạp tính toán vẫn lớn. Như vậy, phương pháp đề xuất có một số ưu điểm cơ bản sau: - Giảm thời gian tính toán do việc tính lặp trên ma trận cỡ nhỏ. - Tích hợp dễ dàng với các phương pháp hỗ trợ tính toán trên ma trận. - Có thể dễ dàng áp dụng song song hoá cho quá trình tính hạng. Kết quả thực nghiệm khi thi hành đối với máy tìm kiếm Nutch [16] đã được chúng tôi gửi công bố trong [12]. Chương 3 Các phương pháp xác định LinkSpam 3.1 Giới thiệu Các phương pháp tính hạng trang được trình bày trong chương trước là khá tốt nhưng hoàn toàn không đề cập đến vấn đề spam, và coi liên kết giữa các trang thực sự hàm chứa mối quan hệ độ quan trọng. Ngày nay, với sự ra đời của các công nghệ spam link nhằm nâng cao hạng trạng thì các phương pháp đó không còn phù hợp mà cần cải tiến, thực hiện xác định, loại bỏ các link spam để có được đánh giá hạng chính xác hơn. Trong hai năm gần đây có nhiều bài báo tập trung vào việc đưa ra phương pháp xác định link spam. Qua nghiên cứu [3, 4, 5, 8, 14, 13, 15] cho thấy các phương pháp có thể chia thành các hướng tiếp cận: 1. Nhận dạng LinkSpam dựa vào cấu trúc liên kết: Với nhận định các trang web có số liên kết đến và liên kết ra tuân theo luật số lớn và do đó các trang web có trọng số PageRank tuân theo luật số lớn, nhóm của Benezur [3] đã cho rằng mỗi trang web được phân phối trọng số PageRank từ các trang liên kết tới tuân theo luật số lớn. Do đó các phân phối trọng số PageRank không tuân theo luật đó được nhận định là link spam. Ngoài ra, D. Fetterly, M. Manasse, và M. Najork cũng phân tích các mô hình phân phối liên kết trên web để xác định các trang spam. Phương pháp này chỉ thích hợp với những dạng link spam đơn giản với cấu trúc liên kết lớn 3.2. PHƯƠNG PHÁP TRUSTRANK 25 được sinh tự động. Và với sự phát triển của công nghệ spam hiện nay thì các phương pháp đó không hiệu quả. Tạo nhóm các trang có liên kết mạnh với nhau, còn gọi là các trang có cấu kết với nhau, là một phương pháp nâng cao hạng trang rất hiệu quả và thường được sử dụng bởi những người tạo spam. Baoning Wu và Brian D.Davion [4] đã đưa ra một thuật toán hiệu quả để nhận diện nhóm các trang đó và Z. Gyongyi, H. Garcia-Molina [15] cũng đưa ra các cải tiến trong công thức tính hạng trang tùy theo cấu trúc liên kết trong các nhóm đó. Các phương pháp này tập trung vào phân tích các cấu trúc liên kết tức các trang liên kết với nhau như thế nào để quyết định một trang là spam hay không và thay đổi giá trị hạng trang của chúng. 2. Xác định spam bằng cách đánh giá độ tốt của các trang thay vì tìm các trang xấu, và hạng các trang web được phân phối từ hạng của các trang trong tập nhân các trang web tốt cho trước. Nhóm tác giả Z.Gyongyi, H. Garcia-Molina, J. Pedersen [13] đã đưa ra phương pháp này dựa trên quan niệm: các trang tốt thường chỉ liên kết đến các trang tốt, và các trang xấu (spam) thường chỉ được các trang xấu liên kết đến. 3. Ngoài ra, với sự ra đời của các trang web cho phép viết bài phương pháp xác định các link spam hay cụ thể là blog spam do Gilad Mishne, David Carmel và Ronny Lempel [5] đưa ra nhằm xác định các bài viết xấu (comment spam) chứa liên kết tới các trang web có chủ đề không phù hợp với chủ đề của bài viết. Chương này tập trung phân tích hai thuật toán xác định Link Spam quan trọng là phương pháp xác định Link Farm của Baoning Wu và Brian D. Davison [4] và phương pháp xác định các trang tốt của nhóm Z.Gyongyi [13], từ đó đưa ra giải pháp kết hợp hai phương pháp xác định link spam ứng dụng vào máy tìm kiếm. 3.2 Phương pháp TrustRank Thay vì xác định các trang spam tức trang xấu, phương pháp đánh giá độ tốt của các trang web. Do mục đích của phương pháp là chọn ra những trang tốt nhất nên cũng tương đương với việc loại bỏ các trang xấu. Các trang tốt thường chỉ liên kết 3.2. PHƯƠNG PHÁP TRUSTRANK 26 đến các trang tốt và hiếm khi liên kết đến các trang xấu (spam). Đó là ý tưởng để nhóm của Z. Gyongyi đưa ra thuật toán TrustRank [13]. 3.2.1 Nội dung phương pháp Phương pháp không tự động xác định các trang tốt và xấu mà cần có tập nhân các trang tốt được xác định trước, và các trang đó phân phối độ tốt tới các trang khác dựa vào mối liên kết giữa chúng. Do vậy việc đầu tiên là chọn một tập nhân các trang tốt, và gán trọng số về độ tốt trust lớn. Sau đó dựa vào thuật toán tính hạng PageRank để phân phối giá trị trust, tìm các trang tốt khác. Những trang có giá trị trust cao được tin tưởng đó là các trang tốt. Trong thuật toán, việc chọn tập nhân rất quan trọng và có ảnh hưởng quyết định tới độ tin cậy của phương pháp, nên trước tiên cần dựa vào kiến thức chuyên gia (kiến thức của con người) xác định một tập nhỏ các trang tốt, xấu trong đồ thị Web, rồi kết hợp với phương pháp xác định trọng số trust của các trang để lựa chọn những trang tốt có trọng số trust cao nhất đưa vào tập nhân. Thuật toán 3 TrustRank 1: s← SelectSeed(. . .) . Tính giá trị trust của N trang trong toàn đồ thị web 2: σ ← Sort({1, . . . , N}, s) . Sắp xếp các trang theo thứ tự trust giảm dần 3: v = 0N . v là véc tơ các trang tốt ban đầu 4: for i = 1 to L do . Chọn L trang tốt có trust cao nhất vào tập nhân 5: if O(σ(i)) = 1 then . O(p) = 1 xác định trang p là tốt 6: v(σ(i))← 1 7: end if 8: end for 9: v ← v/ | v | . Chuẩn hóa véc tơ v 10: pi ← v 11: for i = 1 to MB do . Tính hạng theo PageRank với MB vòng lặp 12: pi = αB.P.pi + (1− α)v 13: end for Các tác giả đã xác định các trang tốt (có trust cao) là các trang có nhiều liên kết ra. Do vậy để tính trust của các trang, các tác giả sử dụng thuật toán tính PageRank với hệ số hãm α và số vòng lặp M nhưng thay vì sử dụng ma trận 3.2. PHƯƠNG PHÁP TRUSTRANK 27 chuyển P của đồ thị G = (V,E), thuật toán sử dụng ma trận chuyển U của đồ thị G′ = (V,E ′). Trong đó: mỗi (p, q) ∈ E có (q, p) ∈ E ′ và ngược lại, hay U chính là ma trận chuyển ngược của P . Thuật toán 4 Tính trust hay PageRank ngược 1: function SelectSeed(. . . ) 2: s← 1N . N là số trang trong đồ thị Web 3: for i = 1 to M do . Tính hạng theo PageRank với M vòng lặp 4: s = α.U.s + (1− α). 1 N .1N 5: end for 6: return s 7: end function Thuật toán TrustRank sử dụng phương pháp tính hạng PageRank nguyên thủy để phân phối hạng từ các trang tốt trong tập nhân tới các trang khác. Tuy nhiên các tác giả cũng đưa ý tưởng về cách phân phối giá trị trust giảm dần theo khoảng cách (bước liên kết) từ các trang nhân với trang được liên kết tới, thay vì phương pháp phân phối đều như PageRank. Hình 3.1: Phương pháp phân phối giảm dần Hình 3.1 mô phỏng việc phân phối giá trị trust từ trang 1 tới trang 2 với giá trị β < 1, và từ đó giá trị trust do trang 2 phân phối cho trang 3 là β.β. Nếu có liên kết từ trang 1 tới trang 3 thì giá trị trust mà 3 nhận được sẽ được lấy trung bình: (β + β.β)/2. Hình 3.2 mô phỏng phương pháp phân phối đều giá trị trust, tương tự phương pháp tính PageRank nguyên thủy. Hơn nữa, có thể kết hợp cả hai cách trên để phân phối giá trị trust, ví dụ trang 3 trong hình 3.2 có thể nhận giá trị trust là β.(1/2+1/3). Mô phỏng thuật toán với một ví dụ cụ thể (theo ví dụ trong [13]): 3.2. PHƯƠNG PHÁP TRUSTRANK 28 Xét đồ thị web gồm 7 trang web hình 3.3, với các nút để trắng tương ứng với các trang tốt và các nút đen tương ứng với các trang xấu. Ta có véc tơ xác định các trang tốt xấu: O = [1, 1, 1, 1, 0, 0, 0]. Véc tơ trust: s = [0.08, 0.13, 0.08, 0.10, 0.09, 0.06, 0.02]. Sắp xếp trang theo giá trị trust giảm dần: σ = [2, 4, 5, 1, 3, 6, 7] Chọn L = 3 khi đó tập nhân gồm các trang {2, 4, 5 } nhưng trong đó trang 5 không phải trang tốt do thông tin ban đầu O [5] = 0. Nên có véc tơ v sau khi chuẩn hóa: v = [ 0, 1 2 , 0, 1 2 , 0, 0, 0, 0 ] Chọn hệ số hãm αB = 0.85 và số vòng lặp MB = 20, thuật toán TrustRank trả về giá trị hạng các trang: pi = [0, 0.18, 0.12, 0.15, 0.13, 0.05, 0.05] Ở đây, trang 1 là trang tốt nhưng có giá trị hạng bằng 0 là do trang 1 chỉ có liên kết ra nên không được phân phối giá trị trust từ các trang nhân. Trong khi đó Hình 3.2: Phương pháp chia đều giá trị trust Hình 3.3: Đồ thị gồm 7 trang web đã được đánh dấu trang tốt, xấu 3.2. PHƯƠNG PHÁP TRUSTRANK 29 Hình 3.4: Biểu đồ kết quả thử nghiệm TrustRank [13] trang 5 là trang xấu lại có hạng cao do có một liên kết trực tiếp từ trang tốt 4 trong tập nhân tới nó. Đây cũng chính là mặt hạn chế của phương pháp TrustRank. 3.2.2 Đánh giá phương pháp Phương pháp TrustRank đã nâng cao hạng của nhiều trang tốt và đồng thời do đó đã giảm hạng của các trang xấu như biểu đồ hình 3.4. Tuy nhiên khi xác định trang tốt thuật toán vẫn còn nhiều hạn chế, như ví dụ ở phần trước đã dẫn chứng hai lỗi điển hình của phương pháp. Vấn đề cốt lõi của phương pháp nằm ở quá trình lựa chọn tập nhân các trang tốt. Trong khi việc chọn tập nhân tốt với số lượng không quá lớn nhưng phải bao phủ được không gian web là vấn đề không đơn giản. Đồng thời phương pháp cần thông tin kiến thức chuyên gia để xác định các trang tốt ban đầu trước khi chọn tập nhân. Do vậy gây ra lỗi điển hình đó là nếu một trang tốt nhưng do tập nhân chưa được cập nhật hay không có liên kết tới từ tập nhân tốt đã được chọn trước thì trang đó không thể đạt được hạng cao, hay một trang xấu nếu có được liên kết từ trang tốt trong tập nhân đến thì lại được đánh giá hạng cao. Ngoài ra thuật toán cần hai lần tính hạng, đó là quá trình tính trọng số trust cho các trang để lựa chọn tập nhân và quá trình tính hạng trang sau khi đã có tập nhân tốt. Đó cũng là một hạn chế phải tính hạng nhiều lần của phương pháp. Do không gian Web rất lớn nên việc tính hạng đòi hỏi chi phí lớn, mà với máy tìm kiếm thì yêu cầu quá trình tính hạng phải đủ nhanh để kết quả trả về cho người dùng là cập nhật và tốt nhất. 3.3. PHƯƠNG PHÁP XÁC ĐỊNH LINK FARM 30 3.3 Phương pháp xác định spam dựa vào cấu trúc liên kết Với nhận định các trang spam link thường có nhiều liên kết đến và ra thuộc cùng các domain, phương pháp tự động nhận diện các trang web có khả năng là spam dựa vào phân tích tập các liên kết vào ra. Từ đó tạo tập nhân các trang spam rồi mở rộng không gian web để tìm các link farm. Sau khi nhận diện các link farm, cần phải xử lý các trang thuộc các link farm đó để loại bỏ ảnh hưởng của chúng tới kết quả tính hạng trang như: giảm trọng số của các liên kết là spam, xóa bỏ các liên kết spam hay thậm chí loại bỏ trang web spam khỏi không gian web. Sau đó có thể sử dụng các thuật toán tính hạng cơ bản như PageRank hoặc HITS để tính hạng của các trang web. 3.3.1 Nội dung phương pháp Baoning Wu và Brian D. Davison [4] đã đề xuất phương pháp với các bước thực hiện: • Xác định tập nhân các trang spam xét trên toàn bộ không gian web. • Mở rộng: thêm vào tập nhân các trang có liên kết chặt với các trang spam đã tìm được. • Tính hạng trang: kết hợp thông tin các trang spam với thuật toán tính hạng dựa trên liên kết để xác định hạng của các trang web. Trong đó bước mở rộng, các trang có liên kết chặt với các trang trong tập nhân được thêm vào tập nhân. Do đó đây là quá trình này lặp, và dừng khi không có trang spam mới nào được tìm thấy. Xây dựng tập nhân Một trang được đưa vào tập nhân S nếu có nhiều trang khác vừa có liên kết đến vừa được liên kết ra trang đó. Để xác định thế nào là nhiều, các tác giả đưa một tham số ngưỡng TIO: một trang có ít nhất TIO các trang có liên kết hai chiều với trang đó thì nó được coi là spam, thuộc một link farm, và được đưa vào S. 3.3. PHƯƠNG PHÁP XÁC ĐỊNH LINK FARM 31 Hình 3.5: Đồ thị Web nhỏ gồm 6 trang thuộc 6 domain khác nhau Tuy nhiên vấn đề đặt ra việc xác định độ tương đồng giữa hai liên kết vào ra để xác định hai trang web có liên kết tới nhau là không đơn giản, bởi các công nghệ tạo web như chuyển hướng (redirect). . . . Do vậy, thay vì xác định các trang web có liên kết tới nhau, thuật toán xác định ở cấp cao hơn đó là site hay domain. Đồng thời phương pháp cũng giúp loại trừ trường hợp các site được thiết kế theo dạng một trang chủ và nhiều trang thành viên, các trang thành viên có liên kết đến trang chủ và trang chủ có liên kết đến các trang thành viên. Ví dụ site của Đại Học Công Nghệ có các liên kết tới trang web của từng bộ môn, và tại trang web của mỗi bộ môn lại có liên kết tới trang chủ Đại Học Công Nghệ. Nhưng trang chủ không phải là trang spam. Xét ví dụ [4], có đồ thị Web nhỏ gồm có 6 trang web thuộc các domain khác nhau (hình 3.5) và chọn giá trị ngưỡng TIO bằng 2. Dễ dàng nhận thấy tập các liên kết đến A gồm [C,D,E] và tập các liên kết A liên kết ra gồm [B,C,D]. Do vậy A có 2 domain của [C,D] vừa có liên kết A vừa được A liên kết tới, thỏa mãn giá trị ngưỡng nên được tập nhân bao gồm [A,C,D]. Trong thuật toán xác định tập nhân định nghĩa: INdomain(p) là danh sách các domain có liên kết đến trang p, OUTdomain(p) là danh sách các domain mà p liên kết tới, và interDomain(p) là số domain trùng nhau giữa INdomain(p), OUTdomain(p). S là mảng đánh dấu các trang thuộc tập nhân, được khởi tạo bằng 0, S [i] = 1 nếu trang web i là trang spam thuộc tập nhân. 3.3. PHƯƠNG PHÁP XÁC ĐỊNH LINK FARM 32 Mở rộng Bước tiếp theo là mở rộng tập nhân, tìm các trang có nhiều liên kết tới các trang trong tập nhân, được coi là các trang spam và thuộc link farm. Để xác định các trang spam đó cần đưa ra một tham số ngưỡng mới xác định giới hạn số lượng liên kết spam tối thiểu cần có của một trang spam, gọi là TPP . Thuật toán ParentPenalty được đưa ra để mở rộng tập nhân. Tiếp tục với đồ thị Web nhỏ trên, thuật toán ParentPenalty mở rộng tập nhân thực hiện như sau: Tập nhân ban đầu gồm [A,C,D]. Số liên kết ra trỏ tới các trang trong tập nhân của trang B là 1, của trang E là 2 và trang F không có liên kết tới các trang trong tập nhân. Chọn ngưỡng TPP = 2, khi đó trang E thỏa mãn điều kiện giới hạn ngưỡng liên kết tới tập nhân nên được thêm vào tập nhân S. Xét tiếp, không có trang nào thỏa mãn điều kiện ngưỡng nên thuật toán dừng và tập các trang xấu nhận diện được là [A,C,D,E]. Tính hạng Sau khi nhận diện các trang spam, có nhiều giải pháp khác nhau để xử lý các trang đó trong quá trình tính hạng trang như: loại bỏ các trang spam khỏi đồ thị Web, giảm trọng số hoặc xóa các liên kết giữa các trang thuộc link farm. Trong đó việc loại bỏ hoàn toàn các trang spam là không thực tế, do mỗi trang web đều có ý nghĩa ít nhất là người tạo ra trang web đó và nhiều trang web tuy được thuật toán nhận diện là spam nhưng vẫn có độ quan trọng cao. Do vậy giải pháp được lựa chọn đó là loại bỏ hoặc giảm trọng số của các liên kết spam, tương ứng là sự biến đổi ma trận chuyển biểu diễn đồ thị Web. Các thuật toán tính hạng trang như PageRank, HITS có thể áp dụng để tính hạng trang sau khi ma trận chuyển được biến đổi, và phương pháp được các tác giả lựa chọn là phương pháp cải tiến HITS do Bharat và Henzinger đưa ra [4]. 3.3.2 Đánh giá Qua thực nghiệm, các tác giả đã chọn TIO = 3, TPP = 3. Bằng cách chia các trang web thành 10 nhóm với mỗi nhóm có tổng giá trị hạng chiếm 1/10 tổng hạng các trang trong toàn đồ thị Web, biểu đồ 3.6 biểu diễn tỉ lệ xuất hiện của các trang spam trong mỗi nhóm. Trong đó các cột màu sáng tương ứng với trường hợp không 3.3. PHƯƠNG PHÁP XÁC ĐỊNH LINK FARM 33 Thuật toán 5 Xác định tập nhân 1: for all p ∈ G do . p là một trang web trong đồ thị Web G 2: for all i ∈ B(p) do 3: if d(i) 6= d(p) then . d(i) là domain của trang i 4: INdomain(p)← INdomain(p) + d(i) 5: end if 6: end for 7: for all k ∈ N(p) do 8: if d(k) 6= d(p) then 9: OUTdomain(p)← OUTdomain(p) + d(k) 10: end if 11: end for 12: interDomain(p)←‖ OUTdomain(p) ∩ INdomain(p) ‖ 13: if interDomain(p) ≥ TIO then 14: S [p]← 1 15: end if 16: end for Thuật toán 6 Mở rộng tập nhân 1: loop ← 0 2: repeat 3: for all (p ∈ G & S [p] = 0) do 4: badnum ← 0 . badnum là số liên kết tới các trang spam 5: for all i ∈ N(p) do 6: if S [i] = 1 then 7: badnum ← badnum +1 8: end if 9: end for 10: if badnum ≥ TPP then 11: S [p]← 1 12: loop ← 1 13: end if 14: end for 15: until loop = 1 3.4. ĐỀ XUẤT PHƯƠNG PHÁP CẢI TIẾN 34 Hình 3.6: Biểu đồ kết quả phân phối các trang spam [4] xác định link farm và các cột màu sẫm tương ứng với trường hợp sau khi xác định, loại bỏ các trang thuộc link farm. Dễ dàng nhận thấy với kết quả thực nghiệm của Baoning Wu và Brian D. Davion [4], thuật toán xác định các trang spam dựa vào cấu trúc liên kết chặt giữa các trang trong link farm có hiệu quả và đã giảm hạng của nhiều trang spam. Nhưng qua thực nghiệm các tác giả cũng thấy có nhiều trang được nhận diện là spam nhưng vẫn có giá trị hạng trang cao. Và điều đó được chấp nhận với lý giải các trang đó có nhiều liên kết tốt từ các trang khác ngoài link farm. Với việc chọn giá trị ngưỡng TIO, TPP cố định đối với tất cả các trang trên đồ thị Web như các tác giả chưa hẳn hợp lý, do mỗi trang web có số lượng liên kết đến và ra không giống nhau. Vì vậy có thể cải tiến phương pháp với việc lựa chọn giá trị ngưỡng là tỉ lệ liên kết thay vì số lượng liên kết. Ví dụ chọn TPP = 0, 5, tức những trang có ít nhất một nửa số liên kết ra trỏ tới các trang spam sẽ được chọn là spam. 3.4 Đề xuất phương pháp cải tiến Mỗi phương pháp trên có hướng tiếp cận riêng và đã góp phần cải thiện kết quả tính hạng trang, có loại bỏ một phần ảnh hưởng của spam. Sau khi nghiên cứu đánh giá các phương pháp, tôi đưa ra một vài cải tiến, tận dụng ưu điểm của mỗi phương pháp để áp dụng hiệu quả vào máy tìm kiếm 3.4. ĐỀ XUẤT PHƯƠNG PHÁP CẢI TIẾN 35 NUTCH. Phương pháp được thực hiện như sau: 1. Sử dụng phương pháp LinkFarm, với tham số ngưỡng được lựa chọn là tỉ lệ liên kết spam thay cho số lượng liên kết spam như thuật toán gốc, để nhận diện các trang spam. 2. Từ danh sách các trang spam tìm được, kết hợp tri thức con người tạo nên danh sách đen (black list) các trang xấu, và từ lần crawl sau máy tìm kiếm có thể bỏ qua không cập nhật nội dung các trang spam. Từ đó tiết kiệm không gian và thời gian xử lý cho máy tìm kiếm. 3. Sau khi xác định các trang spam, biến đổi ma trận chuyển biển diễn đồ thị Web, tiếp tục áp dụng thuật toán CCP để tính hạng các trang web. Chương 4 Thử nghiệm 4.1 Giới thiệu hệ thống NUTCH Nutch [16]là một phần mềm mã mở của máy tìm kiếm trên mạng. Nutch được phát triển từ Lucene, một bộ tìm kiếm (searcher), với việc xây dựng các module phục vụ tìm kiếm web như crawler, cơ sở dữ liệu lưu trữ đồ thị web với, các bộ phân tích tài liệu HTML,. . . . Hệ thống được phát triển trên nền JAVA, và tổ chức một hệ thống file lưu trữ riêng gọi là NFS(Nutch File System) có khả năng xử lý phân tán nên có tính chất độc lập cao. Ngoài ra, hệ thống có kiến trúc môđun hóa cao cho phép phát triển, tích hợp thêm các môđun mới như tính hạng, phân lớp,. . .một cách dễ dàng. Do sử dụng hệ mã UTF-8 trong xử lý và lưu trữ dữ liệu nên hệ thống Nutch có khả năng hỗ trợ nhiều ngôn ngữ khác nhau. Chỉ với một số thay đổi thông tin cấu hình, hệ thống hoàn toàn có thể tìm kiếm với tiếng Việt. Với tính chất mở và tương thích cao của hệ thống như vậy nên đã có rất nhiều máy tìm kiếm trên mạng 1 là sản phẩm phát triển từ hệ thống Nutch. Sau khi nghiên cứu, đánh giá về khả năng phát triển của hệ thống Nutch nên tôi đã quyết định chọn hệ thống Nutch để tích hợp môđun tính hạng trang, lọc spam của mình và tiến hành thử nghiệm trên đó. Hiện nay, hệ thống Nutch đã phát triển và công bố phiên bản 0.8 cùng những ưu điểm vượt trội hơn các phiên bản trước về khả năng tính toán phân tán. Tuy nhiên do vấn đề thời gian nên khóa luận sử dụng Nutch với phiên bản 0.7.2 (công bố ngày 31 tháng 3 năm 2006). 1 4.2. THỬ NGHIỆM 37 4.2 Thử nghiệm Hệ thống Nutch chưa có một môđun tính hạng trang tốt (sử dụng phương pháp PageRank nguyên thủy) và chưa có môđun nhận diện spam mà chỉ có một môđul lọc URL dựa vào một danh sách URL cho trước. 4.2.1 Môi trường thử nghiệm Phần cứng: máy IBM cluster 1350 có cấu hình 3.2GHz, 2GB RAM. Dữ liệu: Tiến hành crawl các trang web với tập nhân lấy từ nguồn dữ liệu URL của Dmoz. Lấy ngẫu nhiên 3000 URL từ Dmoz để tạo nhân và tiến hành crawl với độ sâu liên kết là 30. Sau khi hệ thống crawl và xóa bỏ các trang trùng nhau, được dữ liệu gồm: 2,5 triệu trang web với 4,6 triệu liên kết. Môđun: Các môđun đã tích hợp vào hệ thống Nutch • SpamFilter: nhận diện link farm, thử nghiệm với tham số ngưỡng THRESH- OLD thay đổi trong khoảng 0,3 - 0,5 và thử nghiệm với với phương pháp xác định LinkFarm cũ với ngưỡng T = 3 và để tồn tại tỉ số liên kết xấu trên tổng số liên kết thì phương pháp chỉ xét các trang có liên kết vào, ra. • PageRankTool: tính hạng trang với phương pháp CCP. 4.2.2 Kết quả Với phương pháp cải tiến: • Thời gian trung bình cho quá trình nhận diện spam : 210.000 ms • Số site được nhận diện là nhân của link farm: 6 Bảng 4.1 so sánh kết quả nhận diện link farm của phương pháp cũ sử dụng số lượng liên kết và phương pháp cải tiến dựa theo tỉ lệ liên kết. 4.2. THỬ NGHIỆM 38 B ản g 4. 1: T ập cá c si te n h ân củ a li n k fa rm P h ư ơn g p h áp lấ y số lư ợn g P h ư ơn g p h áp lấ y tỉ lệ ht tp :/ /b ag hd ad bl og .m sn bc .c om / ht tp :/ /b ag hd ad bl og .m sn bc .c om / ht tp :/ /w w w .b er lin on lin e. de /w m 20 06 /d eu ts ch es te am / ht tp :/ /w w w .b er lin on lin e. de /w m 20 06 /d eu ts ch es te am / ht tp :/ /w w w .g eo rg et ow n. ed u/ de pa rt m en ts /- ht tp :/ /w w w .g eo rg et ow n. ed u/ de pa rt m en ts /- ec on om ic s/ fa cu lt y. ht m l ec on om ic s/ fa cu lt y. ht m l ht tp :/ /w w w .u n. or g/ la w / ht tp :/ /w w w .u n. or g/ la w / ht tp :/ /w w w .o re ill y. co m /p ub /t op ic /c pr og ht tp :/ /w w w .o re ill y. co m /p ub /t op ic /c pr og ht tp :/ /p eo pl e. tr ib e. ne t/ el le nc at al in a - - ht tp :/ /w w w .g rd c. co m .a u/ gr ow er s/ re su pd /n or th /n 05 /m ur ra y. ht m ht tp :/ /g ab ri el om eu an jin ho .b lo gs po t. co m / - ht tp :/ /e n. w ik ip ed ia .o rg /w ik i/ K an sh i- R am - ht tp :/ /w w w .e ng ad ge t. co m /2 00 6/ 04 /2 7/ ni nt en do - -w ii- th e- re vo lu ti on -g et s- a- re al -n am e/ ht tp :/ /w w w .r ef or um .c om / - ht tp :/ /s lu gg on ee ds an ap .b lo gs po t. co m / - 4.2. THỬ NGHIỆM 39 Từ bảng 4.1 nhận thấy với hai phương pháp, tập các trang link farm có sự khác biệt. Gọi phương pháp lấy ngưỡng theo số lượng liên kết là phương pháp 1 và phương pháp lấy ngưỡng theo tỉ lệ là phương pháp 2. Ta thấy, có nhiều trang trong phương pháp 1 được xác định là spam nhưng trong phương pháp 2 thì không, điều đó có thể lý giải bởi những trang đó có tổng số liên kết vào, ra lớn nên dù đạt ngưỡng có T liên kết xấu nhưng xét về tỉ lệ số liên kết xấu trên tổng liên kết vào ra thì vẫn có thể nhỏ. Tuy nhiên có một trường hợp đặc biệt xảy ra, đó là trường hợp một trang chỉ được xác định là spam trong phương pháp 2: -supd/north/n05/murray.htm. Điều này xảy ra khi số liên kết vào và ra từ trang này đến các trang có tên miền (domain) khác quá ít, do đó dẫn đến dù có ít liên kết xấu nhưng xét về tỉ lệ thì cao nên bị đưa vào nhóm các trang thuộc link farm. Việc này hoàn toàn chấp nhận được, nhưng cũng có thể khắc phục bằng cách kết hợp thêm giới hạn về số lượng liên kết xấu thay vì chỉ dùng tỉ lệ. Sau khi thêm thông tin về giới hạn số lượng liên kết cho phương pháp 2, trang đã được loại khỏi danh sách spam. Do đồ thị Web được mở rộng từ tập nhân các trang tốt trích từ Dmoz, đồng thời do tập nhân lớn và giới hạn mở rộng đồ thị (độ sâu 30) nên mật độ liên kết trong đồ thị Web thu được rất thưa (trung bình có 2 liên kết vào ra cho mỗi trang) nên với cả hai phương pháp đều chỉ nhận diện được rất ít các trang thuộc link farm. Kết luận Tính hạng trang là một quá trình quan trọng trong xây dựng máy tìm kiếm. Vấn đề xác định chính xác hạng của các tài liệu, cụ thể là các trang web có một vai trò to lớn bởi nó giúp định hướng, chỉ dẫn người dùng đến với những thông tin phù hợp theo nhu cầu. Cùng với sự phát triển của các thuật toán tính hạng trang là các công nghệ tạo spam nhằm đánh lừa máy tìm kiếm đưa ra các đánh giá hạng trang có lợi cho một nhóm các trang chứa ít thông tin có ích nhưng mong muốn được nhiều người dùng ghé thăm. Khóa luận này đã tiếp cận vấn đề nói trên và nghiên cứu giải pháp chống lại các công nghệ spam. Từ đó đưa ra phương pháp áp dụng vào máy tìm kiếm NUTCH để nâng cao chất lượng tính hạng trang. Khóa luận đã đạt được những kết quả: • Phân tích các vấn đề thời sự nhất về bài toán tính hạng trang. Trình bày các thuật toán cải tiến nâng cao tốc độ tính hạng trang trong một vài năm gần đây, trong đó có hai kết quả đã được công bố mà tác giả khóa luận đã tham gia [1, 2]. • Xây dựng modul nhận diện link farm dựa vào cấu trúc liên kết. • Cải tiến phương pháp và nâng cao chất lượng tính hạng trang trong máy tìm kiếm NUTCH. Kết quả nghiên cứu này sẽ được trình bày tại Hội thảo quốc tế ICMOCCA 2006, 16-17 August, 2006, Seoul, Korea [12]. Do giới hạn về thời gian và kiến thức nên qua thực nghiệm phương pháp LinkSpam vẫn còn có hạn chế về thời gian tính toán, cần được tiếp tục nghiên cứu và cải tiến để khẳng định tính hiệu quả của phương pháp. Tài liệu tham khảo Tiếng Việt [1] Đỗ Thị Diệu Ngọc, Nguyễn Hoài Nam, Nguyễn Thu Trang, Nguyễn Yến Ngọc.Giải pháp tính hạng trang Modified Adaptive PageRank trong máy tìm kiếm. Chuyên san "Các công trình nghiên cứu về CNTT và Truyền thông", Tạp chí Bưu chính Viễn thông, 14 , 4-2005, 65-71. [2] Nguyễn Hoài Nam, Nguyễn Thu Trang, Nguyễn Yến Ngọc, Nguyễn Trung Kiên, Bùi Việt Hải. Sử dụng thành phần liên thông nâng cao hiệu năng tính toán PageRank trong máy tìm kiếm Vinahoo. Hội thảo quốc gia lần thứ VIII “Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông”, Hải Phòng, 24-26/8/2005 Tiếng Anh [3] András A. Benczúr, Károly Csalogány, Tamás Sarlós and Máté Uher. Spam- Rank – Fully Automatic Link Spam. In First International Workshop on Ad- versarial Information Retrieval on the Web, WWW2005, 2005. [4] Baoning Wu and Brian D. Davison. Identifying Link Farm Spam Pages. In Proceedings of the 14th International World Wide Web Conference, Industrial Track, May 2005. [5] Gilad Mishne, David Carmel, Ronny Lempel. Blocking Blog Spam with Lan- guage Model Disagreement. AIRWeb ’05 - First International Workshop on Adversarial Information Retrieval on the Web, at the 14th International World Wide Web Conference (WWW2005), 2005 TÀI LIỆU THAM KHẢO 42 [6] Jon Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604-632, November 1999. [7] Monika Henzinger, Rajeev Motwani, and Craig Silverstein. Challenges in web search engines.SIGIR Forum, 36(2), 2002. [8] Panagiotis T. Metaxas, Joseph DeStefano. Web Spam, Propaganda and Trust. Proceedings of the 1st International. Workshop on Adversarial Information Retrieval on the Web (AIRWeb). [9] Page, L., Brin, S., Motwani, R. and Winograd, T. The PageRank citation rank- ing: bringing order to the Web. Technical report, Stanford University, 1998. [10] Sebastiano Vigna. TruRank: Taking PageRank to the Limit. In Proc. of the Fourteenth International World Wide Web Conference (Poster Session), Chiba, Japan, 2005. ACM Press [11] Sepandar Kamvar, Taher Haveliwala, and Gene Golub. Adaptive Methods for the Computation of PageRank. Technical report, Stanford University, 2003. [12] Thuy Q. Ha, Nam H. Nguyen, and Trang T. Nguyen. Improve Performance of PageRank Computation with Connected-Component PageRank. First Interna- tional Conference on Mobile Computing, Communications and Applications, 16-17 August, 2006, ICMOCCA 2006, Seoul, Korea (submitted). [13] Z. Gyongyi, H. Garcia-Molina, and J. Pendersen. Combating Web Spam with TrustRank. In Proceedings of the 30th International VLDB Conference, 2004. [14] Z. Gyongyi and H. Garcia-Molina. Web Spam Taxonomy. Proc. of the Four- teenth International World Wide Web Conference, Chiba, Japan, 2005 [15] Zoltan Gyongyi and Hector Garcia-Molina. Link spam alliances. Technical report, Stanford University, 2005. [16] Phụ lục A Mã chương trình A.1 Phân tích liên kết public void Init() throws IOException { long linkCount = 0; try { IWebDBReader reader = new WebDBReader(nfs, dbDir); MD5Hash lastHash = null; try { for (Enumeration e = reader.pagesByMD5(); e.hasMoreElements();) { Page curPage = (Page) e.nextElement(); MD5Hash newHash = curPage.getMD5(); if (newHash.equals(lastHash)) continue; lastHash = newHash; Link outLinks[] = reader.getLinks(curPage.getMD5()); linkCount += outLinks.length; // // invert links // for (int i = 0; i < outLinks.length; i++) { if (Inlinks.containsKey(outLinks[i].getURL())){ inlink in= (inlink) Inlinks.get( outLinks[i].getURL()); A.2. LỌC SPAM 44 in.links.add(curPage.getURL()); Inlinks.put(outLinks[i].getURL(),in); }else{ inlink in = new inlink(); in.links.add(curPage.getURL()); Inlinks.put(outLinks[i].getURL(),in); } } } } finally { reader.close(); } }catch(Exception e){} System.out.println("So luong lien ket:" + linkCount); } A.2 Lọc Spam public void Filter(File spamFile) throws IOException { int linkCount =0; try { DataOutputStream out = new DataOutputStream(new BufferedOutputStream(nfs.create(new File(spamFile,"spam")))); IWebDBReader reader = new WebDBReader(nfs, dbDir); WebDBWriter webdb = new WebDBWriter(nfs, dbDir); MD5Hash lastHash = null; String lastHost = new String(""); spamlinkSet.clear(); try { for (Enumeration e = reader.pagesByMD5(); e.hasMoreElements();) { Page curPage = (Page) e.nextElement(); MD5Hash newHash = curPage.getMD5(); A.2. LỌC SPAM 45 if (newHash.equals(lastHash)) continue; lastHash = newHash; String newHost =new URL(curPage.getURL(). toString()).getHost().toLowerCase(); if (newHost.equals(lastHost)) continue; Link outLinks[] = reader.getLinks(curPage.getMD5()); linkCount = outLinks.length; inlink inLinks = (inlink)Inlinks.get(curPage.getURL()); linkCount += inLinks.links.size(); int insectLinks = 0; int delLink =0; int change = 0; //insection links if( (linkCount >2) & (outLinks.length >1)){ for (int i = 0; i < outLinks.length; i++) { String sourceHost= new URL(outLinks[i]. getURL().toString()).getHost().toLowerCase(); Iterator iter = inLinks.links.iterator(); while(iter.hasNext()){ String destHost= new URL( ((UTF8)iter.next() ).toString()).getHost().toLowerCase(); if(destHost.equals(sourceHost)) insectLinks++; } } if ((linkCount>0) & (2*insectLinks/linkCount >= THRESHOLD)){ lastHost= newHost; // Luu spam out.writeBytes("-"+curPage.getURL().toString()+"\n"); spamlinkSet.add(curPage.getURL()); // Xoa lien ket A.2. LỌC SPAM 46 for (int k = 0; k < outLinks.length; k++) { String sourceHost= new URL(outLinks[k].getURL(). toString()).getHost().toLowerCase(); Object[] links = inLinks.links.toArray(); int len = inLinks.links.size(); for( int ci =0; ci < len; ci++){ String destHost= new URL( links[ci]. toString()).getHost().toLowerCase(); if(destHost.equals(sourceHost)){ try{ ((inlink)Inlinks.get(curPage.getURL()) ).links.remove((UTF8)links[ci]); }catch(Exception x){} } }//endfor ci }//endfor k }//end if } }//end for System.out.println("Loai bo spam cap 1"); for (Enumeration e = reader.pagesByMD5(); e.hasMoreElements();){ Page curPage = (Page) e.nextElement(); MD5Hash newHash = curPage.getMD5(); if (newHash.equals(lastHash)) continue; lastHash = newHash; Link outLinks[] = reader.getLinks(curPage.getMD5()); linkCount = outLinks.length; int insectLinks = 0; int delLink =0; int change = 0; //insection links if( (linkCount >2) & (!spamlinkSet.contains(curPage.getURL()))){ for (int i = 0; i < outLinks.length; i++) { A.2. LỌC SPAM 47 outLinks[i].getURL().toString(); if (spamlinkSet.contains(outLinks[i].getURL())) insectLinks++; } if ((linkCount>0) & (2*insectLinks/linkCount >= THRESHOLD)) { // Luu spam out.writeBytes("--"+curPage.getURL().toString()+"\n"); spamlinkSet.add(curPage.getURL()); // Xoa lien ket for (int k = 0; k < outLinks.length; k++) { if (spamlinkSet.contains(outLinks[k].getURL())) ((inlink)Inlinks.get(outLinks[k].getURL()) ).links.remove(curPage.getURL()); } } }//endif linkcount }//endfor }catch(Exception e){ System.out.println("Loi spamfilter: "+e); } } finally { reader.close(); out.close(); } System.out.println("Ket thuc Spam Filter " ); }