Khóa luận Link spam với đồ thị web và hạng trang web

ĐẠ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 Danh sách bảng 4.1 Tập các site nhân của link farm . . . . . . . . . . . . . . . . . . . . 38 vi Danh sách hình vẽ 1.1 Một cấu trúc liên kết tối ưu nhằm tăng hạng trang . . . . . . . . . 6 1.2 Một dạng spam với trang gốc p0 . . . . . . . . . . . . . . . . . . . . 8 1.3 Một cấu trúc liên kết giữa nhiều spam farm không theo quy luật . . 8 1.4 Hai spam farm có chia sẻ liên kết với nhau . . . . . . . . . . . . . . 9 1.5 Một cấu trúc gồm 3 spam farm liên kết theo dạng vòng . . . . . . . 9 1.6 Một đồ thị web đơn giản gồm 4 đỉnh, 4 cung . . . . . . . . . . . . . 10 2.1 Tốc độ hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Mô tả tính chất authority và hub . . . . . . . . . . . . . . . . . . . 18 2.3 Mở rộng tập cơ sở T từ tập nhân S . . . . . . . . . . . . . . . . . . 19 3.1 Phương pháp phân phối giảm dần . . . . . . . . . . . . . . . . . . . 27 3.2 Phương pháp chia đều giá trị trust . . . . . . . . . . . . . . . . . . 28 3.3 Đồ thị gồm 7 trang web đã được đánh dấu trang tốt, xấu . . . . . . 28 3.4 Biểu đồ kết quả thử nghiệm TrustRank [13] . . . . . . . . . . . . . 29 3.5 Đồ thị Web nhỏ gồm 6 trang thuộc 6 domain khác nhau . . . . . . 31 3.6 Biểu đồ kết quả phân phối các trang spam [4] . . . . . . . . . . . . 34 vii Bảng ký hiệu và từ viết tắt Ký hiệu Ý nghĩa MAP Modified Adaptive PageRank HITS Hypertext Induced Topic Search CCP Connected Component in PageRank SEOs Search Engine Optimizes viii Lời mở đầu Bài toán tính hạng các đối tượng trên Web (trang Web, tác giả, chủ đề...) nói chung, và bài toán tính hạng trang Web nói riêng, có ý nghĩa quan trọng trong lĩnh vực khai phá Web. Trong thời gian gần đây, nhiều công trình nghiên cứu trên thế giới giải quyết bài toán tính hạng trang Web, chẳng hạn như [3-17], đã được công bố. Lớp thuật toán tính hạng trang điển hình nhất là lớp thuật toán khai thác mối liên kết giữa các trang Web trong một đồ thị Web. Một số kết quả nghiên cứu của chúng tôi về tính hạng trang web trong máy tìm kiếm tập trung vào việc đề xuất các cải tiến nhằm tăng tốc thuật toán tính hạng trang và thi hành trên một máy tìm kiếm tiếng Việt đã được công bố trong [1, 2, 12]. Hướng người dùng đã trở thành xu hướng nghiên cứu nổi bật về hạng trang trong thời gian gần đây. Trong hai năm gần đây nhất, theo xu hướng đó là một số lượng đáng kể các công trình nghiên cứu liên quan tới khái niệm spam, điển hình nhất là [3, 4, 5, 8, 13, 14] , đã được công bố. Các công trình nghiên cứu này được phân thành hai lớp chính. Lớp thứ nhất đề cập tới các giải pháp nhằm làm tăng giá trị cơ sở của hạng trang khi tăng cường ngữ nghĩa của các liên kết giữa các trang Web nhằm làm phù hợp hơn với ngữ cảnh ứng dụng. Lớp thứ hai quan tâm tới các giải pháp tính hạng trang hiển thị khi trình diễn kết quả phù hợp hơn với ngữ cảnh tìm kiếm của người sử dụng. Khóa luận tốt nghiệp với đề tài LinkSpam với đồ thị web và hạng trang web tiến hành việc khảo sát, phân tích các giải pháp xác định LinkSpam đã được đề xuất trong hai năm gần đây để từ đó đề xuất các cải tiến giải pháp vào việc tính hạng trang trong máy tìm kiếm. Khóa luận này gồm bốn chương nội dung được mô tả sơ bộ như dưới đây. Chương 1. Tổng quan về hạng trang và spam giới thiệu những nội dung cơ bản nhất về bài toán tính hạng web và sự xuất hiện của các công nghệ spam nhằm nâng cao hạng trang. Ngoài ra, chương này cũng giới thiệu về đồ thị web và cơ sở của thuật toán tính hạng trang. Chương 2. Một số phương pháp tăng tốc tính hạng trang trình bày hai phương pháp tính hạng trang cơ bản, được đề xuất sớm nhất, đã trở thành cơ sở cho các thuật toán tính hạng và xác định WebSpam sau này. Đồng thời, chương này cũng giới thiệu thuật toán tính hạng trang theo khối dựa vào tính chất liên thông, một kết quả nghiên cứu đã được công bố của chúng tôi. Chương 3. Các phương pháp xác định LinkSpam khảo sát và phân tích kỹ lưỡng các phương pháp xác định LinkSpam và đưa ra những đánh giá về ưu nhược điểm của chúng trong việc xác định các trang web là spam hay không. Đồng thời, chương này cũng trình bày phương pháp xác định LinkSpam do tôi đề xuất dựa trên cơ sở các phân tích đánh giá nói trên. Chương 4. Thử nghiệm trên hệ thống NUTCH phân tích hệ thống NUTCH (một máy tìm kiếm mã nguồn mở) và một số cài đặt cải tiến của chúng tôi, đặc biệt đối với thành phần tính hạng trang Web. Kết quả thử nghiệm đánh giá phương pháp cho thấy tính khả dụng của nói. . . . Phần kết luận tổng kết và tóm lược nội dung chính của khóa luận. Chương 1 Tổng quan về hạng trang và web spam 1.1 Giới thiệu hạng trang và spam Ngày nay, sự phát triển nhanh chóng của mạng Internet đã tạo ra một khối lượng khổng lồ các tài liệu web chứa đựng thông tin đa dạng và thường xuyên được thay đổi từng ngày từng giờ. Tuy nhiên chỉ một phần nhỏ những thông tin đó là hữu ích với mỗi người dùng, do vậy một nhu cầu được đặt ra là cần phải xây dựng công cụ tìm kiếm có chức năng cung cấp các trang web có nội dung đáp ứng yêu cầu tìm kiếm của người dùng với thời gian cho phép. Công cụ tìm kiếm trên Internet, mà cụ thể là các máy tìm kiếm, cho phép tìm kiếm từ một tập rất lớn các tài liệu web các trang web liên quan tới câu hỏi của người dùng. Câu hỏi thường là từ khóa hoặc tập các từ khóa. Thông thường, kết quả tìm kiếm các trang Web liên quan đến từ khoá có thể lên tới hàng vạn trang, trong khi người dùng chỉ quan tâm đến một số trong đó. Do vậy cần tìm ra các trang đáp ứng tốt nhất đối với yêu cầu người dùng để đưa lên trước. Việc làm như vậy được gọi là tính hạng trang Web của máy tìm kiếm. Phương án nguyên thủy nhất tính hạng trang Web là tính độ quan trọng của nó. Độ quan trọng hay còn gọi hạng trang (PageRank) là đại lượng cơ sở để xếp hạng các trang web. Các phương pháp tính hạng trang đều thừa nhận một giả thiết là nếu một trang web mà được nhiều trang khác trỏ (link) tới thì trang web đó là quan trọng. Do vậy giá trị cơ sở của hạng trang được tính toán dựa trên mối liên kết giữa các trang web. Phương pháp tính hạng PageRank và HITS [6, 9] là những thuật toán tính hạng cơ bản, 1.1. GIỚI THIỆU HẠNG TRANG VÀ SPAM 4 nền tảng và đã được áp dụng hiệu quả vào các máy tìm kiếm như Google,Yahoo!. Chúng tôi [1, 2, 12] đã đề xuất một số cải tiến tính hạng trang Web trong [9] và áp dụng thử nghiệm cho máy tìm kiếm Vinahoo, một máy tìm kiếm tiếng Việt được phát triển từ phần mềm nguồn mở máy tìm kiếm ASPseek. Người dùng thường chỉ tập trung vào trang kết quả trả về đầu tiên của máy tìm kiếm, tức là trang chứa địa chỉ của 10 trang web đầu tiên tương ứng với truy vấn của người dùng. Điều đó có nghĩa là chỉ một phần nhỏ các trang kết quả được người dùng duyệt, xem nội dung. Trong khi tạo ra các trang web, đặc biệt là các trang thương mại điện tử và quảng cáo, người tạo ra chúng mong muốn và chú trọng tới việc tăng số lượng truy cập vào trang đó. Hướng tới mục tiêu như vậy, người tạo trang web cố gắng đưa ra các công nghệ để cải thiện thứ hạng của trang trong máy tìm kiếm. Vì vậy đã xuất hiện khái niệm spam đối với máy tìm kiếm hay web spam 1, được Monika Henzinger, Rajeev Motwani và Craig Silverstein đưa ra trong [7], và trang web sử dụng các kỹ thuật spam đó được gọi là web spam. Đồng thời, các dịch vụ tối ưu hạng trang web và tương ứng, một ngành mới đã ra đời - đó là tối ưu máy tìm kiếm (SEOs 2). Vấn đề web spam còn phải nói đến các trang web với thông tin không đúng, mang những nội dung sai trái. . . . Tuy nhiên, khóa luận này chỉ đề cập đến vấn đề spam đối với máy tìm kiếm. Trong giới hạn ngữ cảnh như vậy, công nghệ spam là các kỹ thuật nhằm mục đích nâng cao hạng của các trang web. Ngày nay, spam đã trở thành phổ biến và được thương mại hóa nên một trong những vấn đề đặt ra cho máy tìm kiếm là đưa ra độ đo để xác định, loại bỏ spam, nhằm đảm bảo sự chính xác và phù hợp của hạng trang. Các máy tìm kiếm trên mạng đã phát triển và cải tiến công nghệ để nhận diện và loại bỏ spam. Nhưng khi công nghệ tìm kiếm được phát triển thì các kỹ thuật spam mới cũng được tạo ra tương ứng. Do vậy các công nghệ chống spam ở các máy tìm kiếm thực tế thường không công khai để hạn chế thông tin nhằm ngăn chặn sự phá hoại của những người tạo spam. Tuy nhiên, các công nghệ spam đang và sẽ vẫn tiếp tục được phát triển. Vì vậy nghiên cứu vấn đề nhận diện spam và phát triển các thuật toán tính hạng trang có loại trừ ảnh hưởng của spam là rất cần thiết và có ý nghĩa. Nắm bắt được cách thức tạo spam là tiền đề cần thiết để nhận diện spam và phát triển các thuật toán tính hạng trang có loại trừ ảnh 1Trong tài liệu gọi đơn giản là spam 2Search Engines Optimizers 1.2. CÁC CÔNG NGHỆ TẠO SPAM 5 hưởng của nó. Phần dưới đây trình bày các cách thức như vậy. 1.2 Các công nghệ tạo Spam Theo Monika Henzinger, Rajeev Motwani, và Craig Silverstein [7], công nghệ spam có thể được chia thành 3 loại chính: spam văn bản (text spam), spam liên kết (link spam) và giả dạng (cloaking). 1.2.1 Spam văn bản Tất cả các máy tìm kiếm đều dựa vào nội dung văn bản để quyết định độ phù hợp của từng trang theo câu truy vấn (độ đo TFIDF). Từ đó, công nghệ spam văn bản hướng vào việc thay đổi nội dung văn bản nhằm nâng cao hạng trang theo một số cách sau đây: 1. Dựa vào các đặc điểm của máy tìm kiếm, tập trung vào một tập nhỏ các từ khóa và cố gắng nâng cao chất lượng của tập từ khóa đó trong văn bản: • Lặp các từ khóa ở cuối trang để không ảnh hưởng nhiều tới người dùng nhưng lại có ý nghĩa đối với máy tìm kiếm. Để không ảnh hưởng nhiều tới người dùng, phần văn bản được lặp đó có thể được tạo với phông chữ nhỏ, hay được ẩn đi bằng cách sử dụng màu chữ cùng màu nền . . . . • Đưa từ khóa vào phần tiêu đề của trang hay các mục lớn của trang web. Vì các máy tìm kiếm thường đánh giá cao các từ khóa ở tiêu đề. • Thêm các từ khóa vào phần nội dung thẻ META 3, nội dung trong đó được máy tìm kiếm đánh giá cao do ngầm định ở đó chứa các thông tin quan trọng của trang web. Do vậy những người tạo spam có thể lạm dụng thẻ này. Ví dụ: <meta name=“keywords” content=“ máy ảnh, máy quay, máy in, Sony, Canon, Epson, Xerox”> • Ngoài ra có thể thêm từ khóa vào nội dung của các liên kết (anchor text). Một ví dụ đơn giản: máy tính, máy in, PC, Laptop, ổ cứng, HDD, thiết bị, giá rẻ, miễn phí, bảo hành, tiết kiệm 3Một thẻ hay tag của ngôn ngữ HTML 1.2. CÁC CÔNG NGHỆ TẠO SPAM 6 Hình 1.1: Một cấu trúc liên kết tối ưu nhằm tăng hạng trang 2. Cố gắng tăng số lượng từ khóa của văn bản được đánh giá: • Cách đơn giản nhất là thêm một tập lớn từ (có thể là cả từ điển) ở cuối trang web để tăng khả năng được hiển thị cho nhiều truy vấn khác nhau khả năng trang web đặc biệt với các câu truy vấn không rõ nghĩa. • Thậm chí có thể lặp nội dung của cả văn bản, và đồng thời lặp các từ khóa ở nhiều vị trí trong văn bản . . . . 1.2.2 Spam liên kết Giả thiết được thừa nhận là độ quan trọng của trang phụ thuộc vào số lượng liên kết trỏ tới trang đó là nền tảng của các phương pháp tính hạng trang dựa vào liên kết. Đối với các phương pháp tính hạng trang như vậy, máy tìm kiếm có khả năng xác định hạng của trang web độc lập với yêu cầu của người dùng vì chỉ căn cứ vào liên kết trong đồ thị Web. Tuy nhiên, điều đó cũng được những người tạo spam lợi dụng để nâng cao hạng trang theo cách thay đổi cấu trúc đồ thị web. Đó là công nghệ link spam 4 hay spam liên kết. Mục đích nhằm vào các hệ thống dùng phương pháp tính hạng thô dựa trên số liên kết vào để quyết định độ quan trọng của trang web như các thuật toán PageRank, HITS (sẽ được trình bày chi tiết ở chương 2). Chúng ta xem xét mô hình cấu trúc liên kết nhằm nâng cao hạng trang được tính theo PageRank hình 1.1, theo Z. Gyongyi và H. Garcia-Molina [14]. Trong mô hình có: 4LinkSpam và link spam là cùng nghĩa 1.2. CÁC CÔNG NGHỆ TẠO SPAM 7 - Các trang "inaccessible" là các trang mà người tạo spam không có quyền thay đổi, thêm nội dung mới. - Các trang own là các trang do người tạo spam làm chủ, có toàn quyền sửa đổi, tạo mới. . . - Các trang accessible là các trang không phải own nhưng cho phép viết thêm nội dung (như viết bài trong các blog) Mục tiêu của người tạo spam là tạo các liên kết có lợi để tăng hạng của một hay nhiều trang trong nhóm own, nhóm các trang own đó được gọi là spam farm. Như trong mô hình trên là cấu trúc liên kết nhằm nâng cao độ quan trọng của trang t. Z. Gyongyi và H. Garcia-Molina [14] đã đưa ra một số kỹ thuật tạo link spam nhằm tăng số liên kết đến và liên kết ra của các trang spam: 1. Những người tạo spam có thể dễ dàng thêm các liên kết ra từ các trang web của họ tới các trang tốt, với hi vọng tăng trọng số hub 5 của trang. Trên các site dmoz.org, Yahoo!... có danh sách địa chỉ các web site được phân theo các chủ đề từ lớn đến nhỏ đề rất cụ thể. Do vậy những người tạo spam dễ dàng lấy thông tin đó đưa vào trang web của mình, từ đó tạo ra một cấu trúc liên kết ngoài rất lớn. 2. Việc tăng số liên kết đến của một trang web không đơn như việc thêm các liên kết ra, những người tạo spam có thể dựa vào một số kỹ thuật: • Tạo một nhóm các trang web cung cấp các thông tin hữu ích (như các tài liệu hướng dẫn lập trình Java bằng Tiếng Việt) gọi là trang gốc6, và từ các trang đó tạo các liên kết đến các trang spam. Ví dụ hình 1.2 với p0 là trang gốc, p1 là trang spam. Các trang gốc chứa thông tin hữu ích nên có khả năng sẽ được nhiều trang khác trỏ tới và sẽ có hạng cao. Những trang gốc này không nhất thiết trùng chủ đề với các trang spam do mục tiêu nhằm có được các trang có hạng cao và phân chia hạng đó cho các trang spam qua các liên kết ra. 5Một độ đo tính theo thuật toán HITS 6Chỉ dùng trong tài liệu này 1.2. CÁC CÔNG NGHỆ TẠO SPAM 8 Hình 1.2: Một dạng spam với trang gốc p0 Hình 1.3: Một cấu trúc liên kết giữa nhiều spam farm không theo quy luật • Tạo các bài viết chứa các liên kết tới trang muốn spam tại các trang cho phép viết bài như các trang blog, wiki. . . . Để tránh việc kiểm soát của những người quản lý, những người tạo spam có thể sử dụng các kỹ thuật để che dấu các liên kết đó với người xem nhưng vẫn được xử lý bởi các máy tìm kiếm (như việc sử dụng linh hoạt màu sắc). • Mua các tên miền đã hết hạn và tận dụng các liên kết sẵn có tới các trang web trong đó. • Một kỹ thuật quan trọng đó là việc tạo spam farm (nhóm các trang web spam có liên kết với nhau). Những người tạo spam có thể nắm giữ một số lượng lớn các site vì vậy họ dễ dàng tạo cấu trúc liên kết tùy ý giữa các trang trong các site của họ nhằm nâng cao hạng của các trang đó. Ví dụ: hình 1.3 với các nút màu xám là các trang spam. • Một nhóm những người tạo spam liên kết lại với nhau và tạo các liên 1.2. CÁC CÔNG NGHỆ TẠO SPAM 9 Hình 1.4: Hai spam farm có chia sẻ liên kết với nhau Hình 1.5: Một cấu trúc gồm 3 spam farm liên kết theo dạng vòng kết tới các site của nhau. Hình 1.4 là ví dụ với các trang p, q thuộc là hai spam farm. Một phương pháp cơ bản tạo link spam là người tạo spam đặt link farm, một tập hợp các liên kết trỏ tới tất cả các trang trong cùng site nào đó mà họ muốn, ở cuối mọi trang web. Đây là trường hợp đơn giản của spam farm, do vậy dễ dàng được máy tìm kiếm nhận ra, nhưng còn có những kỹ thuật khác tinh vi hơn, như việc tạo các web vòng (web-ring) như hình 1.5 với các trang spam r0,p0,q0 có liên kết tạo vòng, hay tạo nhóm các trang web có mật độ liên kết lớn. . . 1.2.3 Công nghệ giả dạng Bên cạnh hai kỹ thuật tạo spam trên, giả dạng (cloaking) là kỹ thuật tạo ra nội dung hoàn toàn khác giữa những gì máy tìm kiếm crawl về với những gì sẽ được 1.3. ĐỒ THỊ WEB 10 hiển thị cho người dùng. Hơn nữa, kỹ thuật này cũng hướng tới sự khác nhau giữa các lần crawl khác nhau của máy tìm kiếm. Việc kết hợp với các kỹ thuật spam văn bản và spam liên kết cũng được áp dụng cho các trang web trả về cho máy tìm kiếm để nâng cao hạng trang. Vì vậy máy tìm kiếm bị đánh lừa về nội dung của trang web và đưa ra đánh giá hạng trang không chính xác. 1.3 Đồ thị Web 1.3.1 Biểu diễn đồ thị Web Web có thể được mô hình như là một đồ thị có hướng G = (V , E) với tập các đỉnh V là các trang web (V có n trang, được đánh chỉ số từ 1 tới n) , và tập các cung E là tập các cạnh mà mỗi cạnh ứng với một siêu liên kết giữa hai trang web: E={(i, j) |nếu có liên kết từ i trỏ đến j}. Hình 1.6: Một đồ thị web đơn giản gồm 4 đỉnh, 4 cung Trong thực tế từ một trang web p có thể có nhiều liên kết hướng tới một trang q khác. Nhưng khi biểu diễn mối liên kết ta chỉ biểu diễn bởi một cung (p, q) ∈ E , đồng thời cũng bỏ qua các liên kết trong cùng một trang tức là tự liên kết. Hình 1.6 biểu diễn một đồ thị đơn giản với 4 trang web và có 5 liên kết.(Tuy nhiên có thể mô hình đồ thị Web với các đỉnh là các site thay vì các trang web, và các liên kết giữa các trang khi đó sẽ thay bởi các liên kết giữa các site). Mỗi trang có các liên kết vào và các liên kết ra, gọi N(p) là số liên kết vào của trang p và B(p) là số liên kết ra từ trang p. Ví dụ trong hình 1.6 số liên kết vào của trang 3 là 1 và số liên kết ra là 2. Trên World Wide Web có nhiều trang không có liên đến đến hoặc không có liên kết ra, những trang không có liên kết đến gọi là các trang không được tham chiếu, những trang không có liên kết ra gọi là các trang không tham chiếu và trong đồ thị Web nó trở thành các dangling node7. 7Node có bậc bằng 0, không có cung đi ra 1.3. ĐỒ THỊ WEB 11 Có nhiều cách để biểu diễn một đồ thị có hướng G, ở đây tôi xin giới thiệu hai cách biểu diễn đơn giản được sử dụng trong các thuật toán sẽ trình bày ở chương sau. Biểu diễn đồ thị Web bởi ma trận kề A: A = (aij)n×n Trong đó: aij = { 1 nếu (i, j) ∈ E 0 nếu (i, j) /∈ E Biểu diễn đồ thị Web bởi ma trận chuyển P: P = (pij)n×n Trong đó: pij = { 1/B(i) nếu (i, j) ∈ E 0 nếu (i, j) /∈ E Đặc điểm của ma trận P : các dòng tương ứng với các nút có liên kết ra luôn có tổng bằng 1, còn các dòng tương ứng với các dangling nút sẽ toàn 0. Với ví dụ hình 1.6 có: A =  0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0  và P =  0 1 0 0 0 0 1 0 0 1 2 0 1 2 0 0 0 0  1.3.2 Mô hình Markov Giả sử 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 " ); }