周爽等

【摘 要】實現(xiàn)垃圾網(wǎng)頁的有效檢測可以有效提高搜索引擎檢索質(zhì)量，促使網(wǎng)頁的設計向著面向用戶的方向發(fā)展。由于垃圾網(wǎng)頁是面向搜索引擎設計的，正常網(wǎng)頁是面向用戶設計的，因而兩者在特征方面存在眾多區(qū)別，通過機器學習方法可以根據(jù)垃圾網(wǎng)頁與正常網(wǎng)頁在特征方面的不同對垃圾網(wǎng)頁進行有效識別。通過對常見單分類器和集成學習分類器處理垃圾網(wǎng)頁數(shù)據(jù)集的對比實驗，發(fā)現(xiàn)集成學習方法logitboost較為突出，所得結(jié)果明顯優(yōu)于單一分類器和常用集成學習算法，所得結(jié)果也更接近真實值，并通過對logitboost所用的預處理方法和基分類器進行改進，發(fā)現(xiàn)用resample對垃圾網(wǎng)頁進行預處理，以REPTree算法為基分類器的logitboost算法對垃圾網(wǎng)頁數(shù)據(jù)集的分類有較高的精確度。

【關鍵詞】垃圾網(wǎng)頁識別；集成學習；Weka logitboost

0 引言

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

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

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

1 垃圾網(wǎng)頁識別

1.1 垃圾網(wǎng)頁

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

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

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

1.2 垃圾網(wǎng)頁檢測識別技術及現(xiàn)狀

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

基于內(nèi)容分析法是通過對網(wǎng)頁的文本、URL屬性、錨文本及超鏈接分布等內(nèi)容特征分析統(tǒng)計，通過抓取網(wǎng)頁的一些特征向量構(gòu)建決策樹過濾器，從而實現(xiàn)對正常網(wǎng)頁和垃圾網(wǎng)頁的區(qū)分。

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

1.3 垃圾網(wǎng)頁數(shù)據(jù)集及其評價指標

1.3.1 垃圾網(wǎng)頁數(shù)據(jù)集

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

1.3.2 評價標準

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

2 集成學習算法

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

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

2.1 Adaboost算法

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

2.2 Logitboost算法

Logitboost算法[6]是基于機器學習的判別分類算法，它根據(jù)樣本數(shù)據(jù)集構(gòu)建弱分類器，通過負對數(shù)似然函數(shù)計算樣本權重，調(diào)用分類器檢測樣本的分類，并在下一輪的迭代過程中增加判錯樣本的權重，經(jīng)過反復調(diào)用該弱分類器，賦予判錯樣本較大的權重，增加其關注度，最終使得弱分類器在迭代過程中變?yōu)閺姺诸惼?。Logitboost算法對于多因素、二分類及多分類數(shù)據(jù)的分析效果尤為明顯，還可以發(fā)掘數(shù)據(jù)間潛在的規(guī)律。

2.3 重采樣算法

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

2.4 集成學習有效性的條件

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

3 垃圾網(wǎng)頁數(shù)據(jù)集分類實驗

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

3.1 Weka簡介

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

本文基于weka平臺對垃圾網(wǎng)頁數(shù)據(jù)集進行分析，可以充分利用該工具在數(shù)據(jù)集處理方面的優(yōu)勢，直接使用其集成學習算法，實現(xiàn)對垃圾網(wǎng)頁數(shù)據(jù)集分類任務的有效改進。

3.2 基于weka平臺的集成算法對垃圾網(wǎng)頁數(shù)據(jù)集的分類

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

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

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

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

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

3.5 實驗結(jié)論

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

4 結(jié)束語

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

【參考文獻】

[1]邱齊輝.基于決策樹和貝葉斯算法的垃圾網(wǎng)頁檢測的研究與實現(xiàn)[D].北京：北京工業(yè)大學，2012.

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

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

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

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

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

[7]謝娜娜.基于不平衡數(shù)據(jù)集的文本分類算法研究[D].重慶：重慶大學，2013.

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

[責任編輯：劉展]