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