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

周爽等

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

【關(guān)鍵詞】垃圾網(wǎng)頁識別；集成學(xué)習(xí)；Weka logitboost

0 引言

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

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

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

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

1.1 垃圾網(wǎng)頁

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

內(nèi)容作弊通過改變文本內(nèi)容的相關(guān)性來提升網(wǎng)頁的排序值，內(nèi)容作弊的實(shí)現(xiàn)方式主要有兩種：一種是在一個小關(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)對用戶和搜索引擎不可見。

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

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

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

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

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

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

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

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

1.3.2 評價標(biāo)準(zhǔn)

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

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

集成學(xué)習(xí)方法[4]又稱多重學(xué)習(xí)或分類器組合學(xué)習(xí)，是從弱分類器產(chǎn)生強(qiáng)分類器的機(jī)器學(xué)習(xí)方法，其使用一系列的學(xué)習(xí)器對訓(xùn)練集進(jìn)行學(xué)習(xí)，通過某種規(guī)則整合各種學(xué)習(xí)器的學(xué)習(xí)結(jié)果，從而獲得比單個學(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í)的方法可以有效減小選錯分類器的風(fēng)險，從而是集成的結(jié)果在一般情況下好于單一分類器的結(jié)果。

2.1 Adaboost算法

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

2.2 Logitboost算法

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

2.3 重采樣算法

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

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

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

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

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

3.1 Weka簡介

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

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

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

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

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

本實(shí)驗通過對垃圾網(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.4 不同基分類器的logitboost算法實(shí)驗（采用重取樣的預(yù)處理方法）

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

3.5 實(shí)驗結(jié)論

本文通過實(shí)驗發(fā)現(xiàn)在用resample過濾器對垃圾網(wǎng)頁進(jìn)行預(yù)處理的前提下，用REPTree作為基分類器的logitboost算法對于垃圾網(wǎng)頁數(shù)據(jù)集的分類方面，查準(zhǔn)率、查全率、F1測度及AUC均有得到了較為明顯的提高，因而基于改進(jìn)的logitboost算法對于垃圾網(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ù)的變化對分類效果的影響，找出分類效果更好的分類方法。由于集成學(xué)習(xí)算法的分類效果同基分類器的迭代次數(shù)有關(guān)，迭代次數(shù)不夠時將會使數(shù)據(jù)不能得到充分的挖掘，造成分類效果較差，迭代次數(shù)太多會造成過度擬合現(xiàn)象，因而需要對logitboost的迭代次數(shù)進(jìn)行分析，找出合適的迭代次數(shù)，提高分類器的分類效果。

【參考文獻(xiàn)】

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

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

[3]房曉南，張化祥，高爽.基于SMOTE和隨機(jī)森林的web spam檢測[J].山東大學(xué)學(xué)報：工學(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ù)會議論文集.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）.

[責(zé)任編輯：劉展]