基于改進的LogitBoost算法的垃圾網頁檢測研究

周 爽 王洪鈺 李 曉 孫 磊 龐建萍

（山東師范大學信息科學與工程學院，山東 濟南250014）

0 引言

大數據時代，信息的指數式增長使得信息在人們的生活中發揮著越來越重要的作用，而信息技術的發展使搜索引擎成為互聯網用戶查詢資料、搜索有效信息的有效工具。同時，電子商務的飛速發展讓商家看到了互聯網上存在的巨大的利潤，據中國電子商務發布的數據顯示，2014年中國電子商務交易規模已達13.4萬億元，上漲31.4%，其中B2B電子商務市場規模已達10萬億。對商業網站而言，網頁的排名越靠前，該網頁瀏覽量也會相應增加，網站流量的增加就意味著利潤的增加。

然而，多數的互聯網用戶習慣關注搜索引擎排序靠前的少數網站，據統計95%的用戶只對前五頁的搜索結果有興趣，大量排序靠后的網站被用戶選擇性忽視[1]。因此，在利益因素的驅動下，有些網站的制作者和管理者采用不道德的方式迷惑搜索引擎排序算法，使網頁獲得高于其實際的虛假排名，這種網頁被稱為垃圾網頁。

垃圾網頁嚴重惡化了搜索引擎搜索結果的質量，使用戶在信息獲取過程中遇到阻礙，降低了用戶對搜索引擎的信任度，同時還會助長更多的互聯網作弊行為，嚴重影響了互聯網檢索環境。因此，垃圾網頁的識別成為搜索引擎的重要挑戰之一，實現對垃圾網頁的有效檢測成為現今互聯網產業發展一個亟待解決的問題。

1 垃圾網頁識別

1.1 垃圾網頁

垃圾網頁是指專為搜索引擎設計，而非用戶設計，其通過不道德的手段欺騙搜索引擎，獲得高于實際的排序結果以增加訪問量的網頁，其主要的作弊方式有內容作弊、鏈接作弊和隱藏作弊[2]三種形式，達到欺騙搜索排序算法的效果。

內容作弊通過改變文本內容的相關性來提升網頁的排序值，內容作弊的實現方式主要有兩種：一種是在一個小關鍵詞集合中設法提高關鍵詞之間的相關性；另一種增加搜索引擎查詢關鍵詞的數目。鏈接作弊是通過創建大量出鏈到另一網頁或聚集大量入鏈指向單一目標網頁或組頁面等創建鏈接結構來增加頁面的重要性，從而實現搜索排名的提高。隱藏作弊就是通過某種方式隱藏垃圾網頁的一些內容和鏈接，實現對用戶和搜索引擎不可見。

垃圾網頁具有多樣性、隱藏性、融合性和進化型的特點，這些特點讓垃圾網頁對于用戶和搜索引擎都有嚴重的危害。對于用戶，大大增加了查找信息的難度，產生較差的用戶體驗，使降低了用戶對搜索引擎的信任度；對于搜索引擎，垃圾網頁會導致搜索引擎的鏈接中堆砌大量無用的垃圾信息，消耗大量索引時間和存儲空間，令搜索引擎的檢索速度大大減慢；同時垃圾網頁還會助長更多的互聯網作弊行為，偏離面向用戶設計的基本目的。

1.2 垃圾網頁檢測識別技術及現狀

垃圾網頁的檢測技術可分為基于內容分析法、基于鏈接分析法和基于阻止隱藏技術分析法，由于正常網頁和垃圾網頁所面向的對象不同，因而正常網頁和垃圾網頁在特征上也存在差別，采用機器學習的方法通過增加、刪減相應特征以保持系統作弊檢測的有效性，因此可以更有效的實現垃圾網頁的檢測。

基于內容分析法是通過對網頁的文本、URL屬性、錨文本及超鏈接分布等內容特征分析統計，通過抓取網頁的一些特征向量構建決策樹過濾器，從而實現對正常網頁和垃圾網頁的區分。

基于鏈接分析法對垃圾網頁的檢測主要依靠一種信用機制，即指向正常網頁的網頁是垃圾網頁的概率較低，通過這種信用機制，可以實現對網頁的鏈接分析：正常網頁經過K個鏈接所指向的網頁都是正常網頁或距離正常網頁較遠的網頁是垃圾網頁的概率較大。Trust Rank算法是其中最具影響力的算法，其通過建立一個高信任度的種子集合，對集合中的站點的出鏈進行分析，對網頁是否是垃圾網頁做出判斷。

1.3 垃圾網頁數據集及其評價指標

1.3.1 垃圾網頁數據集

本文采用web spam UK2007數據集[3]進行相關對比實驗，其垃圾網頁訓練數據集和測試集的具體情況如下圖所示，從下圖可以看出垃圾網頁與非垃圾網頁樣本數的比率約為1：18，垃圾網頁數據集存在不平衡問題，較大的數量差異會導致標準分類器分類性能的下降。

表1 垃圾網頁數據集

1.3.2 評價標準

本文采用一套結合垃圾網頁特點的評價標準，包括查準率、查全率、F1測度及AUC,其中AUC是指ROC曲線下方的面積，是反映敏感性和特異性連續變量的綜合指標，可以更好地處理垃圾網頁數據集的不平衡問題，能更加公平的對待稀有類和大類，因此這套評價標準對于評價垃圾網頁十分適合。

2 集成學習算法

集成學習方法[4]又稱多重學習或分類器組合學習，是從弱分類器產生強分類器的機器學習方法，其使用一系列的學習器對訓練集進行學習，通過某種規則整合各種學習器的學習結果，從而獲得比單個學習器更好的學習效果。一定條件下，集成學習的性能明顯好于單一分分類器的分類性能。根據學習器之間的關系集成學習可以分成并態集成學習和同態集成學習兩種，其中并態集成學習使用不同學習器進行集成，同態集成學習使用同一種學習器進行集成，但是基分類器之間的參數有所不同。

集成學習通過把不同起始點得到的分類器的結果進行集成，其所得結果更好的接近全局最優解，并且所得的近似假設函數較單一分類器獲得的近似函數效果更好；集成學習使用加權和擴展假設空間的方法擴大假設空間的規模，其所得的假設函數更接近真實函數；并且采用集成學習的方法可以有效減小選錯分類器的風險，從而是集成的結果在一般情況下好于單一分類器的結果。

2.1 Adaboost算法

Adaboost算法[5]是一種基于基分類器的迭代算法，它將多個弱分類器聯合起來對同一個訓練集進行分類，來提高準確率。該類算法中，每個預測參量都是有權重的，它反映了弱分類器一次分類的錯誤分類的頻繁，AdaBoost算法根據每次對訓練集樣本分類是否準確以及它的正確率來確定該次訓練集的權重，在該權重基礎上加減某個數值，來確定下個訓練集的權值。

2.2 Logitboost算法

Logitboost算法[6]是基于機器學習的判別分類算法，它根據樣本數據集構建弱分類器，通過負對數似然函數計算樣本權重，調用分類器檢測樣本的分類，并在下一輪的迭代過程中增加判錯樣本的權重，經過反復調用該弱分類器，賦予判錯樣本較大的權重，增加其關注度，最終使得弱分類器在迭代過程中變為強分類器。Logitboost算法對于多因素、二分類及多分類數據的分析效果尤為明顯，還可以發掘數據間潛在的規律。

2.3 重采樣算法

重采樣算法[7]可以實現對不平衡數據集分布的改變，減少各類別樣本數據間的不平衡程度。數據的重采樣方法從原理上可以分為：簡單隨機抽樣法、系統抽樣法、整群抽樣法及分層抽樣法。本文采用簡單隨機抽樣方法resample，即利用放回或不放回方法抽取特定數目的隨機樣本，每個參與抽樣的單元被選進樣本的概率均等，采用抽簽算法或隨機數字表進行隨機數據的抽樣構建新樣本。

2.4 集成學習有效性的條件

集成學習的分類效果[8]并不是絕對有效的，要想取得更好的分類效果需要滿足一定的條件，即分類器保證一定的準確率且具有一定的差異性。根據PAC學習模型，集成學習是用弱分類器來產生強分類器的機器學習方法，分類器的準確率就是指分類器的分類結果要比隨機猜測效果好，對于二分類問題，單個分類器的準確率要高于50%，否則集成后分類的錯誤率會上升。分類器的差異性是因為集成完全相同的分類器的分類效果同單一分類器的分類效果差別不大，因此為提高集成學習的效果應選用不同的分類器作為基分類器或選用參數不同的同一分類器作為基分類器。

3 垃圾網頁數據集分類實驗

Weka（懷卡托智能分析環境）是基于Java的開源數據挖掘軟件，集合了大量承擔數據挖掘的機器學習算法，可以明顯提高算法對數據集的處理效果。

3.1 Weka簡介

Weka是懷卡托大學的weka小組完成的開放的數據挖掘平臺，被譽為“數據挖掘和機器學習歷史上的里程碑”，是現今最完備對的數據挖掘工具之一。Weka提供的多種機器學習方法可方便用戶發現數據集中隱藏的數據之間的關系；該工具還有多種適用于任意數據集的數據預處理功能；并且，用戶還可以實現對算法的性能進行評估。

本文基于weka平臺對垃圾網頁數據集進行分析，可以充分利用該工具在數據集處理方面的優勢，直接使用其集成學習算法，實現對垃圾網頁數據集分類任務的有效改進。

3.2 基于weka平臺的集成算法對垃圾網頁數據集的分類

本實驗采用單一分類器和集成學習分類器的對比試驗，單一分類器選用樸素貝葉斯、J48和隨機樹，集成學習算法采用logitboost和Adaboost，實驗證明集成學習算法較單一分類器有更好的分類效果，其中logitboost效果最好。

表2 單一分類器與集成分類器的對比實驗

3.3 不同預處理的logitboost算法實驗（以DecisionStump算法為基分類器）

本實驗通過對垃圾網頁數據集選用不同的過濾器進行預處理，發現resample過濾器進行預處理后的數據集有更好的分類效果，其查準率、查全率、F1測度及AUC的結果都明顯高于其他過濾器，因此采用resample作為數據集的預處理方法。

表3 不同預處理方法的logitboost算法實驗

3.4 不同基分類器的logitboost算法實驗（采用重取樣的預處理方法）

本實驗采用resample過濾器對垃圾網頁數據集進行處理，在迭代次數為10的條件下，改變基分類器的種類，發現以REPTree為基分類器時logitboost分類器的查準率、查全率、F1測度及AUC的值都高于其他基分類器的值。

表4 不同基分類器的logitboost算法的對比實驗

3.5 實驗結論

本文通過實驗發現在用resample過濾器對垃圾網頁進行預處理的前提下，用REPTree作為基分類器的logitboost算法對于垃圾網頁數據集的分類方面，查準率、查全率、F1測度及AUC均有得到了較為明顯的提高，因而基于改進的logitboost算法對于垃圾網頁數據集的檢測有較好的精確度。

4 結束語

本文通過將集成學習logitboost進行改進，并將其應用于垃圾網頁分類檢測，說明了在使用有一定準確率和差異性的分類器作為基分類器的條件下，集成學習方法可以明顯提高分類效果，下一步的工作是調整分類器的相關參數參數，觀察參數的變化對分類效果的影響，找出分類效果更好的分類方法。由于集成學習算法的分類效果同基分類器的迭代次數有關，迭代次數不夠時將會使數據不能得到充分的挖掘，造成分類效果較差，迭代次數太多會造成過度擬合現象，因而需要對logitboost的迭代次數進行分析，找出合適的迭代次數，提高分類器的分類效果。

［1］邱齊輝.基于決策樹和貝葉斯算法的垃圾網頁檢測的研究與實現[D].北京：北京工業大學,2012.

［2］賈志洋,李偉偉,高煒,夏幼明.基于支持向量機的搜索引擎垃圾網頁研究[J].計算機應用與軟件,2006,26（11）：165-167.

［3］房曉南,張化祥,高爽.基于SMOTE和隨機森林的web spam檢測[J].山東大學學報：工學版,2012,43（1）：24-27.

［4］周濟,文志強,林海龍.集成學習有效性的研究[J].軟件導刊,2014,13（6）.

［5］張松,周亞建,劉念.數據挖掘基本算法比較[C]//.2010全國通信安全學術會議論文集.2010：326-332.

［6］Takafumi Kanamoria、 Takashi Takenouchi，Improving Logitboost with prior knowledge[J].Information Fusion 14(2013)：208-219.

［7］謝娜娜.基于不平衡數據集的文本分類算法研究[D].重慶：重慶大學,2013.

［8］周濟,文志強,林海龍.集成學習有效性的研究[J].軟件導刊,2014,13（6）.