基于改進(jìn)的LogitBoost算法的垃圾網(wǎng)頁檢測研究

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

（山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014）

0 引言

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

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

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

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

1.1 垃圾網(wǎng)頁

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

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

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

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

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

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

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

1.3 垃圾網(wǎng)頁數(shù)據(jù)集及其評(píng)價(jià)指標(biāo)

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

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

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

1.3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

2 集成學(xué)習(xí)算法

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

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

2.1 Adaboost算法

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

2.2 Logitboost算法

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

2.3 重采樣算法

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

2.4 集成學(xué)習(xí)有效性的條件

集成學(xué)習(xí)的分類效果[8]并不是絕對(duì)有效的，要想取得更好的分類效果需要滿足一定的條件，即分類器保證一定的準(zhǔn)確率且具有一定的差異性。根據(jù)PAC學(xué)習(xí)模型，集成學(xué)習(xí)是用弱分類器來產(chǎn)生強(qiáng)分類器的機(jī)器學(xué)習(xí)方法，分類器的準(zhǔn)確率就是指分類器的分類結(jié)果要比隨機(jī)猜測效果好，對(duì)于二分類問題，單個(gè)分類器的準(zhǔn)確率要高于50%，否則集成后分類的錯(cuò)誤率會(huì)上升。分類器的差異性是因?yàn)榧赏耆嗤姆诸惼鞯姆诸愋Ч瑔我环诸惼鞯姆诸愋Ч顒e不大，因此為提高集成學(xué)習(xí)的效果應(yīng)選用不同的分類器作為基分類器或選用參數(shù)不同的同一分類器作為基分類器。

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

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

3.1 Weka簡介

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

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

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

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

表2 單一分類器與集成分類器的對(duì)比實(shí)驗(yàn)

3.3 不同預(yù)處理的logitboost算法實(shí)驗(yàn)（以DecisionStump算法為基分類器）

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

表3 不同預(yù)處理方法的logitboost算法實(shí)驗(yàn)

3.4 不同基分類器的logitboost算法實(shí)驗(yàn)（采用重取樣的預(yù)處理方法）

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

表4 不同基分類器的logitboost算法的對(duì)比實(shí)驗(yàn)

3.5 實(shí)驗(yàn)結(jié)論

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

4 結(jié)束語

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

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

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

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

［4］周濟(jì),文志強(qiáng),林海龍.集成學(xué)習(xí)有效性的研究[J].軟件導(dǎo)刊,2014,13（6）.

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

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

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

［8］周濟(jì),文志強(qiáng),林海龍.集成學(xué)習(xí)有效性的研究[J].軟件導(dǎo)刊,2014,13（6）.