盧曉勇 陳木生 吳政隆 張百棧

摘要：為解決垃圾網(wǎng)頁(yè)檢測(cè)過程中的“維數(shù)災(zāi)難”和不平衡分類問題，提出一種基于免疫克隆特征選擇和欠采樣（US）集成的二元分類器算法。首先，使用欠采樣技術(shù)將訓(xùn)練樣本集大類抽樣成多個(gè)與小類樣本數(shù)相近的樣本集，再將其分別與小類樣本合并構(gòu)成多個(gè)平衡的子訓(xùn)練樣本集；然后，設(shè)計(jì)一種免疫克隆算法遴選出多個(gè)最優(yōu)的特征子集；基于最優(yōu)特征子集對(duì)平衡的子樣本集進(jìn)行投影操作，生成平衡數(shù)據(jù)集的多個(gè)視圖；最后，用隨機(jī)森林（RF）分類器對(duì)測(cè)試樣本進(jìn)行分類，采用簡(jiǎn)單投票法確定測(cè)試樣本的最終類別。在WEBSPAM UK2006數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該集成分類器算法應(yīng)用于垃圾網(wǎng)頁(yè)檢測(cè)：與隨機(jī)森林算法及其Bagging和AdaBoost集成分類器算法相比，準(zhǔn)確率、F1測(cè)度、AUC等指標(biāo)均提高11%以上；與其他最優(yōu)的研究結(jié)果相比，該集成分類器算法在F1測(cè)度上提高2%，在AUC上達(dá)到最優(yōu)。

關(guān)鍵詞：

垃圾網(wǎng)頁(yè)檢測(cè)；集成學(xué)習(xí)；免疫克隆算法；特征選擇；欠采樣；隨機(jī)森林

中圖分類號(hào)： TP391.1； TP393.098； TP181 文獻(xiàn)標(biāo)志碼：A

0引言

垃圾網(wǎng)頁(yè)指的是那些在搜索引擎查詢結(jié)果中具有良好的排名而實(shí)際價(jià)值卻較差的網(wǎng)站和網(wǎng)頁(yè)。垃圾網(wǎng)頁(yè)之所以會(huì)出現(xiàn)，是由于搜索引擎用戶傾向于只點(diǎn)擊那些排名靠前的鏈接。為了取得靠前的排名，各網(wǎng)站便想方設(shè)法采取各種手段優(yōu)化網(wǎng)站。而通過正當(dāng)手段提高網(wǎng)站排名，成本極其高昂，于是各種網(wǎng)頁(yè)作弊手段輪番上陣。據(jù)估計(jì)，整個(gè)互聯(lián)網(wǎng)的垃圾網(wǎng)頁(yè)占到15%左右[1]。垃圾網(wǎng)頁(yè)削弱了搜索引擎的權(quán)威性，浪費(fèi)了大量計(jì)算與存儲(chǔ)資源，剝奪損害了合法網(wǎng)站的正當(dāng)利益，降低了搜索結(jié)果的質(zhì)量[1]。垃圾網(wǎng)頁(yè)檢測(cè)已成為搜索引擎最為重要的任務(wù)之一。

一般可將垃圾網(wǎng)頁(yè)分為3種類型：內(nèi)容垃圾（content spam）、鏈接垃圾（link spam）和使用垃圾（usage spam）。相應(yīng)地，搜索引擎也可以從網(wǎng)頁(yè)的內(nèi)容、鏈接以及搜索引擎使用情況3個(gè)方面提取特征以識(shí)別垃圾網(wǎng)頁(yè)[2]。然而作弊手段變化多端，一旦針對(duì)某種特征設(shè)計(jì)出特定的算法以檢測(cè)某種特定種類的垃圾網(wǎng)頁(yè)，一種繞過該檢測(cè)算法的新作弊手段又會(huì)出現(xiàn)，使得該特定的檢測(cè)算法失效。機(jī)器學(xué)習(xí)技術(shù)可充分利用各種已提取的特征訓(xùn)練出檢測(cè)模型以應(yīng)對(duì)作弊手段的無窮變化。

研究人員已提取出大量的特征用于檢測(cè)垃圾網(wǎng)頁(yè)。當(dāng)使用這些特征訓(xùn)練傳統(tǒng)的分類器比如決策樹分類器時(shí)，極易陷入“維數(shù)災(zāi)難”問題，如果特征數(shù)較少分類性能尚佳，當(dāng)特征數(shù)增加時(shí)，分類器性能反而下降。這種現(xiàn)象也被稱為“休斯現(xiàn)象”[3]，那么該如何組合眾多的特征以訓(xùn)練出性能更好的分類器呢？一種可行的辦法是使用特征選擇遴選出最優(yōu)的特征子集，將該特征子集用于訓(xùn)練分類器可能提高分類器性能。根據(jù)特征子集評(píng)價(jià)方法的不同，特征選擇方法可分為兩種：過濾式（filter）方法[4]和封裝式（wrapper）方法[5]。找出最優(yōu)的特征子集是一種NP難（Nondeterministic Polynomial hard）問題。模擬退火[6]、蟻群優(yōu)化[7]、遺傳算法[8]、人工免疫系統(tǒng)算法[9-10]等諸多啟發(fā)式智能算法常用來尋找最優(yōu)特征子集。

互聯(lián)網(wǎng)中的垃圾網(wǎng)頁(yè)雖然數(shù)量巨大，但與正常網(wǎng)頁(yè)相比，依然是少數(shù)。由此可知，垃圾網(wǎng)頁(yè)檢測(cè)是一個(gè)不平衡分類問題。然而，大多數(shù)傳統(tǒng)分類器，包括決策樹分類器，不太適用于不平衡分類。重采樣[11]（包括欠采樣和過采樣）、代價(jià)敏感分析[12]、核分類器[13]等方法常用于解決不平衡分類問題。

盧曉勇等[14]采用一種將隨機(jī)森林（Random Forest， RF）與欠采樣（UnderSampling， US）技術(shù)相結(jié)合的算法解決垃圾網(wǎng)頁(yè)檢測(cè)中的“維數(shù)災(zāi)難”和不平衡分類問題，但其分類性能仍有待改善。本文首先基于人工免疫系統(tǒng)的克隆增殖、高頻變異以及免疫耐受等思想，設(shè)計(jì)了一種免疫克隆算法用于特征選擇，并結(jié)合隨機(jī)森林和欠采樣技術(shù)用于垃圾網(wǎng)頁(yè)檢測(cè)，取得了更好的分類性能。

1本文方法

本文提出的用于檢測(cè)垃圾網(wǎng)頁(yè)的集成分類器模型框架如圖1所示。其中訓(xùn)練階段包括3個(gè)過程3、這里改為：4個(gè)步驟4個(gè)步驟：首先使用欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為多個(gè)平衡數(shù)據(jù)集；再次使用免疫克隆算法進(jìn)行特征選擇選取多個(gè)最優(yōu)特征子集對(duì)每個(gè)平衡數(shù)據(jù)集進(jìn)行投影操作，產(chǎn)生多個(gè)平衡數(shù)據(jù)集；最后使用上述所得每個(gè)平衡數(shù)據(jù)集訓(xùn)練隨機(jī)森林分類器并按投票法簡(jiǎn)單集成。

首先使用欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為多個(gè)平衡數(shù)據(jù)集；再次使用免疫克隆算法進(jìn)行特征選擇，得到多個(gè)最優(yōu)特征子集；然后基于這些最優(yōu)特征子集對(duì)每個(gè)平衡數(shù)據(jù)集進(jìn)行投影操作，產(chǎn)生多個(gè)平衡數(shù)據(jù)集；最后使用上述所得每個(gè)平衡數(shù)據(jù)集訓(xùn)練隨機(jī)森林分類器并按投票法簡(jiǎn)單集成。

4、這整句話改為：

首先使用欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為多個(gè)平衡數(shù)據(jù)集；再次使用免疫克隆算法進(jìn)行特征選擇，得到多個(gè)最優(yōu)特征子集；然后基于這些最優(yōu)特征子集對(duì)每個(gè)平衡數(shù)據(jù)集進(jìn)行投影操作，產(chǎn)生多個(gè)平衡數(shù)據(jù)集；最后使用上述所得每個(gè)平衡數(shù)據(jù)集訓(xùn)練隨機(jī)森林分類器并按投票法簡(jiǎn)單集成。

本文將此集成分類器命名為免疫克隆特征選擇和欠采樣集成隨機(jī)森林（Immune Clonal Feature Selection and UnderSampling Ensemble Random Forests， ICFSUSERF）分類器。在測(cè)試階段，使用ICFSUSERF分類器估計(jì)測(cè)試樣本的分類，確定其是否為垃圾網(wǎng)頁(yè)。

1.1欠采樣

假設(shè)小類樣本集S和大類樣本集N，欠采樣從大類樣本集N中隨機(jī)地抽取出樣本子集N′，使得N′的樣本數(shù)n′遠(yuǎn)遠(yuǎn)小于N的樣本數(shù)n，即n′n，但約等于小類樣本集S的樣本數(shù)s，即n′≈s。將大類樣本子集N′與小類樣本集S合并一起構(gòu)成一個(gè)新的平衡樣本集D。使用此平衡的樣本集D訓(xùn)練分類器模型要比原來不平衡的樣本集無論是在運(yùn)行性能還是分類準(zhǔn)確率上都要更好。然而D只利用了大類樣本集的小部分樣本，其他樣本未得到使用，白白浪費(fèi)。為充分利用所有大類樣本，將大類樣本采用不放回抽樣平均分成k等份可得到k個(gè)樣本子集，N1′，N2′，…，Nk′，其中k=round（n/s）。這樣得到每份大類樣本子集N′的樣本數(shù)n′也約等于小類樣本集S的樣本數(shù)s，即n′=round（n/k）≈s。分別組合N′與S，得到k個(gè)均衡的樣本子集Di={S，Ni}，i=1，2，…，k。每個(gè)平衡的樣本集D均可用于訓(xùn)練一個(gè)分類器。算法1列出了欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集的偽代碼。

算法1欠采樣算法。

輸入：不平衡數(shù)據(jù)集，內(nèi)含小類樣本集S和大類樣本集N。

輸出：多個(gè)平衡的樣本子集Di（i=1，2，…，k）。

1）s=小類樣本個(gè)數(shù)；

2）n=大類樣本個(gè)數(shù)；

3）k=round（n/s）；

4）將大類樣本平均分成k個(gè)樣本子集N1′，N2′，…，Nk′，其中Ni′的樣本個(gè)數(shù)ni′約等于小類樣本集S的樣本個(gè)數(shù)s；

5）分別組合樣本子集Ni′和小類樣本集S構(gòu)成新的平衡樣本子集Di；

6）返回Di{D1，D2，…，Dk}（i=1，2，…，k）。此處的書寫不太妥當(dāng)？是否應(yīng)該改為“6）返回Di（i=1，2，…，k）。”，請(qǐng)明確。

1.2免疫克隆特征選擇

在免疫克隆特征選擇算法中，B細(xì)胞和抗體對(duì)應(yīng)最優(yōu)特征子集，抗原對(duì)應(yīng)搜索最優(yōu)特征子集問題本身。抗體由二進(jìn)制位串表示。位串長(zhǎng)度是總的特征個(gè)數(shù)。某位值為1表示相應(yīng)特征被選中，為0則表示相應(yīng)特征不被選中。例如抗體[1 0 1 0 0]表示僅第1個(gè)和第3個(gè)特征被選中。該免疫克隆特征選擇算法流程如圖32所示。首先產(chǎn)生初始抗體群，抗體群包含若干抗體。若未達(dá)到最大迭代次數(shù)則進(jìn)入迭代。每次迭代時(shí)首先計(jì)算抗體與抗原之間的親和度，根據(jù)親和度大小不同克隆出不同數(shù)量的抗體，再對(duì)克隆抗體進(jìn)行高頻變異操作。最后進(jìn)行抑制操作，產(chǎn)生新抗體補(bǔ)充到抗體群中，保證抗體的多樣性。下面詳細(xì)描述每個(gè)步驟。

步驟1產(chǎn)生初始抗體群。

首先，隨機(jī)產(chǎn)生一個(gè)抗體群，產(chǎn)生方式如式（1）所示：

P=round（rand（p， f））（1）

其中：P表示抗體群；p表示抗體的個(gè)數(shù)； f表示特征的個(gè)數(shù)；

rand（p， f）將返回p行f列的值為0至1的實(shí)數(shù)矩陣rand（p， f）是一個(gè)數(shù)值，還是實(shí)數(shù)矩陣？請(qǐng)明確一下；round為四舍五入操作，使得所有的實(shí)數(shù)取整為0或1。

rand（p， f）將返回一個(gè)p行f列的實(shí)數(shù)矩陣，其中每個(gè)元素的取值范圍在[0，1]區(qū)間；round為四舍五入操作，使得矩陣中的所有元素取整為0或1。

這樣便返回p個(gè)抗體，每個(gè)抗體由f位二進(jìn)制位串組成。

步驟2計(jì)算親和度。

抗體與抗原的親和度對(duì)應(yīng)最優(yōu)特征子集用來分類的準(zhǔn)確性。在垃圾網(wǎng)頁(yè)檢測(cè)中，使用AUC（Area Under ROC Curve）指標(biāo)衡量分類準(zhǔn)確性。其中封裝的分類器算法即為基于欠采樣集成的隨機(jī)森林算法?？贵w與抗原之間親和度計(jì)算的偽代碼如算法2所示。該算法體現(xiàn)了交叉驗(yàn)證和欠采樣集成的結(jié)合使用。

算法2親和度計(jì)算算法。

輸入：訓(xùn)練集D，二進(jìn)制位串S，表示選中的特征子集，整數(shù)n，表示n折交叉驗(yàn)證。

輸出：AUC值。

1）根據(jù)二進(jìn)制位串S表示的特征子集對(duì)訓(xùn)練樣本集D進(jìn)行投影操作，得到新的訓(xùn)練樣本子集D′。

2）將新訓(xùn)練樣本子集D′劃分為小類樣本集DS和大類樣本集DN兩部分。

3）將小類樣本集DS平均分成n等份DSi{DS1，DS2，…，DSn}，同樣將大類樣本集DN平均分成n等份DNi{DN1，DN2，…，DNn}。

4）分別合并DSi和DNi構(gòu)成新的數(shù)據(jù)集DMi{DM1，DM2，…，DMn}。

5）針對(duì)DMi中的每一個(gè)平衡數(shù)據(jù)集執(zhí)行如下操作：

①將DMi視為測(cè)試集DMte，DM中的其他所有樣本視為訓(xùn)練集DMtr。

②對(duì)DMtr進(jìn)行欠采樣抽樣，得到k個(gè)平衡的樣本子集DBi{DB1，DB2，…，DBk}。

③初始化DMte中每個(gè)樣本的spamicity值：spamicity=0。

④針對(duì)每一個(gè)平衡樣本子集執(zhí)行如下操作：

a）使用DBi訓(xùn)練隨機(jī)森林分類器。

b）使用隨機(jī)森林分類器對(duì)DMte中的樣本進(jìn)行分類，如果為正常網(wǎng)頁(yè)，則分類結(jié)果值result為-1，否則為1。

c）將分類結(jié)果累加到spamicity：spamicity=spamicity+result。

6）計(jì)算spmicity的均值：spamicity=spamicity/k。

7）根據(jù)每個(gè)樣本的spamicity值計(jì)算AUC。

步驟3克隆選擇。

將所有抗體按親和度值從大到小進(jìn)行排序，選擇最優(yōu)的前l(fā)個(gè)抗體L進(jìn)行克隆以產(chǎn)生新的抗體。其他未被選中用于克隆的抗體由于親和度值不好直接被刪除。每個(gè)抗體克隆出的新抗體個(gè)數(shù)與其適應(yīng)度值成正向關(guān)系此處的書寫是否正確？是正比嗎？請(qǐng)明確。答：是正向關(guān)系，并非正比關(guān)系。即新抗體個(gè)數(shù)與適應(yīng)度值的排序正相關(guān)。非常感謝！。所有被選中抗體克隆的抗體個(gè)數(shù)如式（2）所示：

lc=∑li=1round（βl/i）（2）

其中： β為乘數(shù)因子；l為被選中的用于克隆的抗體個(gè)數(shù)；i為前l(fā)個(gè)抗體的序號(hào)；lc是克隆產(chǎn)生的抗體總數(shù)。例如，如果l為7， β為2，則第1個(gè)抗體將產(chǎn)生lc1=round（（2×7）/1）=14個(gè)抗體，第2個(gè)抗體將克隆產(chǎn)生lc2=round（（2×7）/2）=7個(gè)抗體，依此類推。

步驟4高頻變異。

每一個(gè)克隆產(chǎn)生的抗體在進(jìn)入下一次迭代之前都要經(jīng)歷一次高頻變異操作。本算法的高頻變異操作通過改變二進(jìn)制串的位值而實(shí)現(xiàn)。某位值由0改變?yōu)?表示某個(gè)未被選中的特征被選中；反之，若由1改變?yōu)?表示被選中的特征不再被選中。本算法按以下啟發(fā)式規(guī)則實(shí)行變異：

1）新增少量新特征可能比原有特征子集獲得更好的分類性能。

2）刪減少量特征可能比原有特征子集獲得更好的分類性能。

為保持抗體的多樣性，應(yīng)避免抗體種類的重復(fù)，因此每次變異抗體時(shí)，應(yīng)保證新抗體尚未出現(xiàn)在候選抗體群中。

步驟5抑制操作。

抑制操作的目的是保持抗體群的多樣化。抑制操作與初始化類似，只是隨機(jī)產(chǎn)生一定數(shù)量的抗體加入候選抗體群。同樣，新產(chǎn)生的抗體必須保證尚未出現(xiàn)在候選抗體群中。

1.3集成隨機(jī)森林分類器

使用免疫克隆特征選擇算法獲得n個(gè)最優(yōu)的特征子集以及使用欠采樣技術(shù)獲得k個(gè)平衡的訓(xùn)練樣本集之后，每個(gè)平衡的訓(xùn)練樣本集可根據(jù)不同的最優(yōu)特征子集采用投影操作獲得n個(gè)不同的訓(xùn)練樣本子集，這樣，共可以獲得n×k個(gè)平衡的訓(xùn)練樣本子集?；诖薾×k個(gè)平衡的訓(xùn)練樣本子集，可訓(xùn)練出n×k個(gè)隨機(jī)森林分類器，采用簡(jiǎn)單投票機(jī)制將n×k個(gè)隨機(jī)森林分類器集成起來，即為集成隨機(jī)森林分類器。

1.4測(cè)試階段

可將集成分類器的每個(gè)隨機(jī)森林分類器用于對(duì)測(cè)試樣本進(jìn)行分類，得到一個(gè)分類結(jié)果。分類結(jié)果不同其返回結(jié)果值也不同。其計(jì)算方法如式（3）所示：

Score（x，C）=1，分類為垃圾網(wǎng)頁(yè)-1，分類為正常網(wǎng)頁(yè) （3）

其中：x為測(cè)試樣本；C為一個(gè)隨機(jī)森林分類器；Score（x，C）為根據(jù)分類結(jié)果得到的返回值。將所有隨機(jī)森林分類器的分類結(jié)果返回值進(jìn)行累加后再取平均值，即得到最終的分類結(jié)果值，該值范圍在[-1，1]區(qū)間。在垃圾網(wǎng)頁(yè)檢測(cè)中，此值被稱為spamicity。測(cè)試樣本中所有樣本的spamicity值可直接用于計(jì)算AUC值以評(píng)估集成分類器的分類效果。測(cè)試樣本的最終分類結(jié)果可通過式（4）得到：

ClassificationResult=1，spamicity>0-1，spamicity≤0 （4）

如果ClassificationResult值為1，則為垃圾網(wǎng)站，否則為正常網(wǎng)站。

ICFSUSERF算法采用欠采樣集成技術(shù)，將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集，并充分利用所有樣本，提高了分類效果；用克隆選擇算法遴選最優(yōu)特征子集用于構(gòu)建集成分類器，充分發(fā)揮了最優(yōu)特征的作用，一定程度上避免了“維度災(zāi)難”問題。

2實(shí)驗(yàn)

2.1數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

本文實(shí)驗(yàn)所用數(shù)據(jù)集為WEBSPAMUK2006[12]，它是網(wǎng)絡(luò)對(duì)抗信息檢索研討會(huì)2007年用于垃圾網(wǎng)頁(yè)檢測(cè)競(jìng)賽使用的數(shù)據(jù)集，現(xiàn)已成為垃圾網(wǎng)頁(yè)檢測(cè)研究的公開數(shù)據(jù)集。數(shù)據(jù)集本身已按保留法（HoldOut）的要求，分為訓(xùn)練集和測(cè)試集兩個(gè)部分。數(shù)據(jù)集特征眾多，本文采納其中四種類型的特征，分別是：基于內(nèi)容的特征96個(gè)，基于鏈接的特征41個(gè)，基于鏈接轉(zhuǎn)換的特征135個(gè)，基于鄰接圖的特征2個(gè)。訓(xùn)練集和測(cè)試集的樣本數(shù)情況如表1所示。由表可知，訓(xùn)練集中正常網(wǎng)站與垃圾網(wǎng)站的比例約為7∶1，這表明訓(xùn)練集是不平衡的，與真實(shí)情況較為一致。

本文使用3種指標(biāo)評(píng)估分類模型，分別是準(zhǔn)確率（Accuracy）、F1測(cè)度（F1Measure）和AUC值。本文將垃圾網(wǎng)頁(yè)檢測(cè)視為二元分類問題。對(duì)于二元分類問題，其表達(dá)測(cè)試樣本集分類結(jié)果的混淆矩陣由TP（True Positive）、TN（True Negative）、FP（False Positive）和FN（False Negative）四個(gè)值構(gòu)成，其中：TP為被正確分類的正例，TN為正確分類的負(fù)例，F(xiàn)P為錯(cuò)誤分類的正例，F(xiàn)N為錯(cuò)誤分類的負(fù)例。于是準(zhǔn)確率和F1測(cè)度值可分別用式（5）和式（6）計(jì)算得到：

Accuracy=TP+FNTP+FP+FN+TN（5）

F1Measure=2TP2TP+FN+FP（6）

對(duì)于二元分類而言，隨機(jī)挑選一個(gè)正樣本以及一個(gè)負(fù)樣本，分類算法根據(jù)計(jì)算得到的分?jǐn)?shù)（Score）值將正樣本排在負(fù)樣本前面的概率即為AUC值[15]。在垃圾網(wǎng)頁(yè)檢測(cè)中，最終得到的spamicity值即可作為Score值。AUC值越大表明當(dāng)前的分類算法越有可能將正樣本排在負(fù)樣本前面，即能夠更好地分類。AUC值相比較準(zhǔn)確率和F1測(cè)度而言，更適合于不平衡數(shù)據(jù)集的分類性能評(píng)價(jià)[16]。

2.2參數(shù)設(shè)置

最早的克隆選擇算法是De Castro等提出的CLONALG（CLONal selection ALGorithm）算法[17]。本文提出的ICFSUSERF算法基本流程與其他克隆選擇算法類似，只是針對(duì)特征子集選擇應(yīng)用設(shè)計(jì)了一些初始化抗體種群、親和度計(jì)算、克隆選擇、高頻變異、抑制操作等算子。另外，ICFSUSERF算法需要得若干個(gè)而非一個(gè)最優(yōu)抗體個(gè)數(shù)（最優(yōu)特征子集）。每個(gè)最終生成的抗體將用于生成二元分類子分類器。對(duì)于集成二元分類，子分類器的個(gè)數(shù)為奇數(shù)更合適。如果個(gè)數(shù)太少，集成效果不明顯；如果個(gè)數(shù)太多，算法耗時(shí)明顯增加，而集成效果并不顯著增加。本實(shí)驗(yàn)依次選用3至13個(gè)最優(yōu)抗體，發(fā)現(xiàn)當(dāng)最優(yōu)抗體數(shù)為7時(shí)，分類準(zhǔn)確率、F1測(cè)度以及AUC等值處于全面較優(yōu)的狀態(tài)，因此，最終選擇7作為最優(yōu)抗體個(gè)數(shù)。在進(jìn)行最優(yōu)特征子集選擇的訓(xùn)練過程中，需要對(duì)訓(xùn)練集進(jìn)行n折交叉驗(yàn)證。交叉折數(shù)的設(shè)定與數(shù)據(jù)集的樣本個(gè)數(shù)是緊密相關(guān)的。在樣本個(gè)數(shù)確定的情況下，如果交叉折數(shù)太多，則每個(gè)訓(xùn)練樣本子集的樣本數(shù)太少，無法訓(xùn)練出足夠好的分類器；如果交叉折數(shù)太少，則分類器集成的性能將下降。本實(shí)驗(yàn)將交叉折數(shù)設(shè)為5，實(shí)驗(yàn)結(jié)果較為理想。一般而言，克隆選擇算法需要設(shè)置的參數(shù)有：初始化抗體種群中抗體的個(gè)數(shù)、克隆選擇抗體的比率、高頻變異抗體的比率、抑制操作的比率以及迭代次數(shù)等。為簡(jiǎn)化算法設(shè)計(jì)，ICFSUSERF算法將克隆選擇抗體的比率、抑制操作的比率等參數(shù)設(shè)計(jì)為克隆選擇抗體個(gè)數(shù)、抑制操作抗體個(gè)數(shù)等數(shù)量值，將高頻變異抗體比率設(shè)置為100%，即所有克隆產(chǎn)生抗體都要進(jìn)行變異。初始化抗體種群中抗體的個(gè)數(shù)、克隆選擇抗體個(gè)數(shù)和抑制操作抗體個(gè)數(shù)一般要大于最優(yōu)抗體個(gè)數(shù)，但如果個(gè)數(shù)太多，每次迭代耗時(shí)又將急劇增長(zhǎng)，應(yīng)設(shè)在20以內(nèi)為宜，本實(shí)驗(yàn)分別設(shè)為20，7，20。迭代次數(shù)是根據(jù)具體問題的收斂情況確定的。從多次實(shí)驗(yàn)結(jié)果看，本文實(shí)驗(yàn)一般會(huì)在400次左右收斂，故選擇迭代次數(shù)為500。

2.3不同方法的比較

將ICFSUSERF對(duì)WEBSPAM UK2006數(shù)據(jù)集進(jìn)行分類，將其結(jié)果與隨機(jī)森林及其他相關(guān)的分類器比較。這些分類器包括隨機(jī)森林、Bagging集成隨機(jī)森林（RF+Bagging）、AdaBoost集成隨機(jī)森林（RF+AdaBoost）以及文獻(xiàn)[14]提出的欠采樣集成隨機(jī)森林（RF+US）等。不同方法的實(shí)驗(yàn)結(jié)果如表2所示。從表2可看出，ICFSUSERF與RF+US分類器的分類效果遠(yuǎn)遠(yuǎn)優(yōu)于其他分類器，無論在準(zhǔn)確率、F1測(cè)度還是AUC指標(biāo)方面，都要比其他方法更優(yōu)，均提升11%左右，而本文提出的ICFSUSERF方法比RF+US方法又有所提升。

表3列出了本文所提算法的結(jié)果與2007年垃圾網(wǎng)頁(yè)挑戰(zhàn)競(jìng)賽各優(yōu)勝團(tuán)隊(duì)分類結(jié)果的比較情況。由表可知，ICFSUSERF分類器的分類性能在F1測(cè)度這個(gè)指標(biāo)上，其值為0.93，表現(xiàn)得比所有優(yōu)勢(shì)團(tuán)隊(duì)都好；而在AUC這個(gè)指標(biāo)上，其值為0.94此處為0.95，與表3中的0.94不一一致？是否書寫錯(cuò)誤？請(qǐng)明確。，僅次于Cormack團(tuán)隊(duì)的結(jié)果0.96。然而，Cormack團(tuán)隊(duì)的F1測(cè)度值僅為0.67，表明其分類準(zhǔn)確率并不高。

Scarselli等[18]5.將[15]改為：[18]提出一種包含概率映射圖自組織映射（Probabilistic Mapping Graph selforganizing map， PMG）和圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Network， GNN）的圖層疊架構(gòu)用于垃圾網(wǎng)頁(yè)檢測(cè)，同樣基于WEBSPAM UK2006數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。表4顯示其所提方法的實(shí)驗(yàn)結(jié)果，其中的FNN（Feedforward Neural Network），PMG+GNN（3）+GNN（1）算法表現(xiàn)出最好的檢測(cè)效果。本文提出的ICFSUSERF分類器與其相比，除了準(zhǔn)確率更低外，F(xiàn)1測(cè)度和AUC兩個(gè)指標(biāo)上則更優(yōu)，特別是F1測(cè)度提升顯著。

2.4討論

雖然實(shí)驗(yàn)結(jié)果并不表明，本文方法在所有的評(píng)價(jià)指標(biāo)上均優(yōu)于其他方法，但在F1測(cè)度和AUC兩個(gè)指標(biāo)上表現(xiàn)出來的優(yōu)良分類結(jié)果，依然表明ICFSUSERF算法用于垃圾網(wǎng)頁(yè)檢測(cè)效果良好。其良好效果的獲得，主要得益于以下3點(diǎn)：1）欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集，解決了不平衡分類問題；2）基于欠采樣的集成充分發(fā)揮所有訓(xùn)練樣本的作用；3）基于免疫克隆特征選擇的算法一定程度上解決了維數(shù)災(zāi)難問題，并充分發(fā)揮了所有特征子集的作用。

3結(jié)語(yǔ)

垃圾網(wǎng)頁(yè)檢測(cè)是對(duì)抗信息檢索領(lǐng)域的一個(gè)重要主題。因?yàn)橛糜谟?xùn)練分類器的垃圾網(wǎng)頁(yè)檢測(cè)數(shù)據(jù)集往往是特征眾多且正負(fù)類極其不平衡的，為解決其維數(shù)災(zāi)難和不平衡分類問題，本文提出一種基于欠采樣和免疫克隆特征選擇的集成隨機(jī)森林分類器ICFSUSERF用于垃圾網(wǎng)頁(yè)檢測(cè)。在WEBSPAMUK2006上的實(shí)驗(yàn)結(jié)果表明，ICFSUSERF的分類性能優(yōu)良。與其他最優(yōu)秀的分類器比較，雖然ICFSUSERF在準(zhǔn)確率指標(biāo)并不占優(yōu)；但在AUC和F1測(cè)度兩個(gè)指標(biāo)上明顯優(yōu)于其他方法。

垃圾網(wǎng)頁(yè)檢測(cè)依然是對(duì)抗信息檢索領(lǐng)域中一項(xiàng)艱巨的任務(wù)，除了探索一些優(yōu)秀的機(jī)器學(xué)習(xí)算法在垃圾網(wǎng)頁(yè)檢測(cè)中的應(yīng)用外，從網(wǎng)頁(yè)內(nèi)容、鏈接以及搜索引擎使用信息方面提取特征以檢測(cè)垃圾網(wǎng)頁(yè)也是一個(gè)通常的研究領(lǐng)域。另外，將本文提出的ICFSUSERF方法應(yīng)用于其他領(lǐng)域，也是進(jìn)一步研究的方向。

參考文獻(xiàn)：

[1]

SPIRIN N， HAN J. Survey on Web spam detection： principles and algorithms [J]. ACM SIGKDD Explorations Newsletter， 2012， 13（2）： 50-64.

[2]

CHANDRA A， SUAIB M. A survey on Web spam and spam 2.0 [J]. International Journal of Advanced Computer Research， 2014， 4（2）： 634-644.

[3]

TAHIR M A， BOURIDANE A， KURUGOLLU F. Simultaneous feature selection and feature weighting using hybrid tabu search/Knearest neighbor classifier [J]. Pattern Recognition Letters， 2007， 28（4）： 438-446.

[4]

BONEV B， ESCOLANO F， CAZORLA M. Feature selection， mutual information， and the classification of highdimensional patterns [J]. Pattern Analysis and Applications， 2008， 11（3/4）： 309-319.

[5]

MOUSTAKIDIS S P， THEOCHARIS J B. A fast SVMbased wrapper feature selection method driven by a fuzzy complementary criterion [J]. Pattern Analysis and Applications， 2012， 15（4）： 379-397.

[6]

LIN S， LEE Z， CHEN S， et al. Parameter determination of support vector machine and feature selection using simulated annealing approach [J]. Applied Soft Computing， 2008， 8（4）： 1505-1512.

[7]

AHMED A. Feature subset selection using ant colony optimization [J]. International Journal of Computational Intelligence and Applications， 2005， 2（1）： 53-58.

[8]

AHMAD F， ISA N A M， HUSSAIN Z， et al. A GAbased feature selection and parameter optimization of an ANN in diagnosing breast cancer [J]. Pattern Analysis and Applications， 2014， 18（4）： 861-870.

[9]

MARINAKI M， MARINAKIS Y. A hybridization of clonal selection algorithm with iterated local search and variable neighborhood search for the feature selection problem [J]. Memetic Computing， 2015， 7（3）： 181-201.

[10]

SAMADZADEGAN F， NAMIN S R， RAJABI M A. Evaluating the potential of clonal selection optimization algorithm to hyperspectral image feature selection [J]. Key Engineering Materials， 2012， 500（1）： 799-805.

[11]

YEN S， LEE Y. Clusterbased undersampling approaches for imbalanced data distributions [J]. Expert Systems with Applications， 2009， 36（3）： 5718-5727.

[12]

SUN Y， KAMEL M S， WONG A K， et al. Costsensitive boosting for classification of imbalanced data [J]. Pattern Recognition， 2007， 40（12）： 3358-3378.

[13]

HONG X， CHEN S， HARRIS C J. A kernelbased twoclass classifier for imbalanced data sets [J]. IEEE Transactions on Neural Networks， 2007， 18（1）： 28-41.

[14]

盧曉勇，陳木生.基于隨機(jī)森林和欠采樣集成的垃圾網(wǎng)頁(yè)檢測(cè)[J].計(jì)算機(jī)應(yīng)用，2016，36（3）：731-734.（LU X Y， CHEN M S. Web spam detection based on random forest and undersampling ensemble [J]. Journal of Computer Applications， 2016， 36（3）： 731-734.）

[15]

FAWCETT T. An introduction to ROC analysis [J]. Pattern Recognition Letters， 2006， 27（8）： 861-874.

[16]

DAVIS J， GOADRICH M. The relationship between precisionrecall and ROC curves [C]// ICML 2006： Proceedings of the 23rd International Conference on Machine Learning. New York： ACM， 2006： 233-240.

[17]

DE CASTRO L N， VON ZUBEN F J. Learning and optimization using the clonal selection principle [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（3）： 239-251.

7、增加參考文獻(xiàn)：

[18] Scarselli F， Tsoi A C， Hagenbuchner M， et al. Solving graph data issues using a layered architecture approach with applications to web spam detection[J]. Neural Networks， 2013， 48： 78-90.

[18]

SCARSELLI F， TSOI A C， HAGENBUCHNER M， et al. Solving graph data issues using a layered architecture approach with applications to Web spam detection [J]. Neural Networks， 2013， 48： 78-90.無期