Luận văn:Link spam với đồ thị web và hạng trang web

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

65
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Google sử dụng hơn 200 yếu tố xếp hạng trang web của bạn. Google sẽ không bao giờ nói cho bạn biết những yếu tố có tầm quan trọng. Lý do cho điều này là mỗi năm Google thay đổi hơn 500 thuật toán. Tuy nhiên Google cung cấp cho bạn một số gợi ý những điều quan trọng. Google thậm chí còn cung cấp một tài liệu hướng dẫn SEO cho các quản trị trang web.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận vă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 cl 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 CL 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 M t d ng spam v i trang g c p0 . . . . . . . . . . . . . . . . . . . . 1.2 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 it .............................. 16 2.2 Mô t tính ch t authority và hub . . . . . . . . . . . . . . . . . . . 18 M r ng t p cơ s T t t p nhân S . . . . . . . . . . . . . . . . . . 2.3 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 im đ 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 1 Trong tài li u g i đơn gi n là spam 2 Search 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 : • 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 3 M 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ó: 4 LinkSpam 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 5 c a h t i các trang t t, v i hi v ng tăng tr ng s hub 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. 5 M t đ đo tính theo thu t toán HITS 6 Ch 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 node 7 . 7 Node 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 đó: 1 n u (i, j ) ∈ E aij = 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 đó: 1/B (i) n u (i, j ) ∈ E pij = n u (i, j ) ∈ E 0 / Đ 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ó:     0100 0100     0 0 1 0 0 0 1 0  A= P= và   0 1 0 1 0 1 0 1  2 2     0000 0000 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 pij k 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 pij k > 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.