基于遺傳規(guī)劃和集成學習的Web Spam檢測關鍵技術研究.pdf

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

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

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

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

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

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

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

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

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

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