基于遺傳規(guī)劃和集成學(xué)習(xí)的Web Spam檢測(cè)關(guān)鍵技術(shù)研究.pdf

1、隨著網(wǎng)絡(luò)上的信息呈爆炸式增長，搜索引擎已成為日常生活中幫助人們發(fā)現(xiàn)其想要信息的重要工具。給定一個(gè)確定的查詢，搜索引擎通常能返回成千上萬個(gè)網(wǎng)頁，但是大部分用戶只讀前幾個(gè)，所以在搜索引擎中網(wǎng)頁排名非常重要。因此，許多人采用一些手段來欺騙搜索引擎排序算法，使一些網(wǎng)頁獲得不應(yīng)有的高排序值來吸引用戶的關(guān)注，從而達(dá)到獲取某方面利益的目的。所有試圖增加網(wǎng)頁在搜索引擎中排序的欺詐行為被稱為Web Spam(網(wǎng)絡(luò)作弊)。Web Spam嚴(yán)重降低了搜索引擎

2、檢索結(jié)果的質(zhì)量，使用戶在獲取信息的過程中遇到巨大障礙，產(chǎn)生較差的用戶體驗(yàn)。對(duì)于搜索引擎而言，即使這些作弊網(wǎng)頁沒有排得足夠靠前來擾亂用戶，抓取、索引和存儲(chǔ)這些網(wǎng)頁也需要成本。因此，識(shí)別Web Spam已成為搜索引擎的重要挑戰(zhàn)之一。
　　 本文根據(jù)Web Spam數(shù)據(jù)集的特點(diǎn)，圍繞基于網(wǎng)頁特征構(gòu)建分類器檢測(cè)Web Spam方面進(jìn)行了研究，主要工作包括以下三方面：
　　 (1)提出基于遺傳規(guī)劃學(xué)習(xí)判別函數(shù)檢測(cè)Web Spam的

3、方法
　　 將個(gè)體定義為檢測(cè)Web Spam的判別函數(shù)，經(jīng)過遺傳操作，遺傳規(guī)劃就可以找到優(yōu)化的判別函數(shù)來提高Web Spam的檢測(cè)性能。然而，使用遺傳規(guī)劃產(chǎn)生判別函數(shù)時(shí)會(huì)出現(xiàn)一個(gè)問題，因?yàn)闆]有關(guān)于最優(yōu)解的任何先驗(yàn)知識(shí)，所以很難知道個(gè)體的適當(dāng)長度，如果個(gè)體長度太短，則個(gè)體中所包含的特征就會(huì)很少，個(gè)體的辨別力不高，對(duì)應(yīng)函數(shù)表達(dá)式的分類性能就不好。要想充分利用Web Spam數(shù)據(jù)集中的內(nèi)容、鏈接等特征，需要較長的判別函數(shù)，對(duì)應(yīng)個(gè)體規(guī)模

4、較大。對(duì)于由較大規(guī)模個(gè)體組成的種群，構(gòu)造和搜索所需時(shí)間較長?；谳^長判別函數(shù)是由若干較短判別函數(shù)組成的這一原理，本文提出通過遺傳規(guī)劃學(xué)習(xí)判別函數(shù)檢測(cè)Web Spam，該方法先使用若干小規(guī)模的個(gè)體創(chuàng)建多個(gè)種群，每個(gè)種群經(jīng)過遺傳操作產(chǎn)生本種群的最好個(gè)體，然后再將每個(gè)種群所得的最好個(gè)體通過遺傳規(guī)劃進(jìn)行組合得到更好的判別函數(shù)，從而利用較短時(shí)間就能產(chǎn)生性能更好的較長判別函數(shù)來檢測(cè)Web Spam。本文還研究了表示個(gè)體的二叉樹深度在遺傳規(guī)劃進(jìn)化過程

5、中的影響以及組合的效率。
　　 在WEBSPAM-UK2006數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與單種群遺傳規(guī)劃相比，使用兩次組合的多種群遺傳規(guī)劃能將召回率提高5.6％，F(xiàn)度量提高2.25％，正確率提高2.83％。與SVM相比，新方法將召回率提高了26％，F(xiàn)度量提高了11％，精確度提高了4％。
　　 (2)提出利用基于遺傳規(guī)劃的集成學(xué)習(xí)檢測(cè)Web Spam的方法。
　　 目前多數(shù)基于分類檢測(cè)Web Spam的方法

6、只使用一種分類算法構(gòu)造一個(gè)分類器，并且大都忽略了數(shù)據(jù)集中作弊樣本和正常樣本的不平衡性，即正常樣本比作弊樣本多很多。由于存在多種不同類型的Web Spam技術(shù)，新類型的Spam技術(shù)也在不斷出現(xiàn)，期望發(fā)現(xiàn)一個(gè)萬能分類器來檢測(cè)所有類型的WebSpam是不可能的。所以，通過集成多個(gè)分類器的檢測(cè)結(jié)果來找到增強(qiáng)分類器用于檢測(cè)Web Spam是一種有效方法，并且集成學(xué)習(xí)也是解決非平衡數(shù)據(jù)集分類問題的有效方法之一。在集成學(xué)習(xí)中，如何產(chǎn)生多樣的基分類器和

7、如何組合它們的分類結(jié)果是兩個(gè)關(guān)鍵的問題。本文提出利用基于遺傳規(guī)劃的集成學(xué)習(xí)來檢測(cè)Web Spam，首先使用不同的分類算法分別在不同的樣本集和特征集上進(jìn)行訓(xùn)練產(chǎn)生多樣的基分類器，然后使用遺傳規(guī)劃學(xué)習(xí)得到一個(gè)新穎的分類器，由它基于多個(gè)基分類器的檢測(cè)結(jié)果給出最終檢測(cè)結(jié)果。
　　 該方法根據(jù)Web Spam數(shù)據(jù)集的特點(diǎn)，利用不同的數(shù)據(jù)集合和分類算法產(chǎn)生差異較大的基分類器，利用遺傳規(guī)劃對(duì)基分類器的結(jié)果進(jìn)行集成，不僅易于集成不同類型分類器的

8、結(jié)果，提高分類性能，還能選擇部分基分類器用于集成，降低預(yù)測(cè)時(shí)間。該方法還可以將欠抽樣技術(shù)和集成學(xué)習(xí)融合起來提高非平衡數(shù)據(jù)集的分類性能。為了驗(yàn)證遺傳規(guī)劃集成方法的有效性，分別在平衡數(shù)據(jù)集和非平衡數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。在平衡數(shù)據(jù)集的實(shí)驗(yàn)部分，首先分析了分類算法和特征集合對(duì)集成的影響，然后將其與已知集成學(xué)習(xí)算法進(jìn)行比較，結(jié)果顯示在準(zhǔn)確率、召回率、F-度量、精確度，錯(cuò)誤率和AUC方面，優(yōu)于一些已知的集成學(xué)習(xí)算法；在非平衡數(shù)據(jù)集上的實(shí)驗(yàn)表明無論是同

9、態(tài)集成還是異態(tài)集成，遺傳規(guī)劃集成均能提高分類的性能，且異態(tài)集成比同態(tài)集成更加有效；遺傳規(guī)劃集成比AdaBoost、Bagging、RandomForest、多數(shù)投票集成、EDKC算法和基于Prediction Spamicity的方法取得更高的F-度量值。
　　 (3)提出基于遺傳規(guī)劃產(chǎn)生新特征檢測(cè)Web Spam的方法。
　　 特征在分類中扮演著很重要的角色，Web Spam數(shù)據(jù)集中有96個(gè)內(nèi)容特征、41個(gè)鏈接特征和1

10、38個(gè)轉(zhuǎn)換鏈接特征，其中138個(gè)轉(zhuǎn)換鏈接特征是41個(gè)鏈接特征的簡單組合或?qū)?shù)操作，這些特征的產(chǎn)生不僅需要由專家來完成，還很耗費(fèi)人力，并且也不易把不同類型(如內(nèi)容特征和鏈接特征)的特征融合在一起。該方法提出利用遺傳規(guī)劃將已有特征進(jìn)行組合從而產(chǎn)生更有區(qū)別力的新特征，然后將這些新特征作為分類器的輸入來檢測(cè)Web Spam。在WEBSPAM-UK2006數(shù)據(jù)集上的實(shí)驗(yàn)顯示，使用10個(gè)新特征的分類器的分類結(jié)果好于使用原41個(gè)鏈接特征的分類器，與使