陳木生，盧曉勇

(1.南昌大學(xué) 信息工程學(xué)院，江西 南昌 330031； 2.南昌大學(xué) 軟件學(xué)院，江西 南昌 330047)

(*通信作者電子郵箱dreaminit@163.com)

三種用于垃圾網(wǎng)頁檢測(cè)的隨機(jī)欠采樣集成分類器

陳木生1*，盧曉勇2

(1.南昌大學(xué) 信息工程學(xué)院，江西 南昌 330031； 2.南昌大學(xué) 軟件學(xué)院，江西 南昌 330047)

(*通信作者電子郵箱dreaminit@163.com)

針對(duì)垃圾網(wǎng)頁檢測(cè)過程中輕微的不平衡分類問題，提出三種隨機(jī)欠采樣集成分類器算法，分別為一次不放回隨機(jī)欠采樣(RUS-once)、多次不放回隨機(jī)欠采樣(RUS-multiple)和有放回隨機(jī)欠采樣(RUS-replacement)算法。首先使用其中一種隨機(jī)欠采樣技術(shù)將訓(xùn)練樣本集轉(zhuǎn)換成平衡樣本集，然后對(duì)每個(gè)平衡樣本集使用分類回歸樹(CART)分類器算法進(jìn)行分類，最后采用簡單投票法構(gòu)建集成分類器對(duì)測(cè)試樣本進(jìn)行分類。實(shí)驗(yàn)表明，三種隨機(jī)欠采樣集成分類器均取得了良好的分類效果，其中RUS-multiple和RUS-replacement比RUS-once的分類效果更好。與CART及其Bagging和Adaboost集成分類器相比，在WEBSPAM UK-2006數(shù)據(jù)集上，RUS-multiple和RUS-replacement方法的AUC指標(biāo)值提高了10%左右，在WEBSPAM UK-2007數(shù)據(jù)集上，提高了25%左右；與其他最優(yōu)研究結(jié)果相比，RUS-multiple和RUS-replacement方法在AUC指標(biāo)上能達(dá)到最優(yōu)分類結(jié)果。

垃圾網(wǎng)頁檢測(cè)；不平衡分類；集成學(xué)習(xí)；欠采樣；分類回歸樹

0 引言

隨機(jī)欠采樣方法是一種從數(shù)據(jù)方面解決類不平衡問題的有效有段。近年來，類不平衡問題已成為數(shù)據(jù)挖掘領(lǐng)域的重要挑戰(zhàn)之一[1]。許多現(xiàn)實(shí)世界的分類問題，比如故障診斷[2]、異常檢測(cè)[3]、醫(yī)療診斷[4]、人臉識(shí)別[5]等，都屬于類不平衡分類問題。為解決類不平衡分類問題，許多技術(shù)相繼被提出。根據(jù)其處理類不平衡的方式不同，這些方法大體可劃分為三類：算法層面的方法是創(chuàng)立或修訂已存在的算法以特別考慮少數(shù)類的重要性[6-8]；數(shù)據(jù)層面的方法則是采用重采樣技術(shù)以消除類分類偏置所帶來的影響[9-10]，有欠采樣[11]和過采樣[12]兩種方式；最后一種方法則是同時(shí)結(jié)合算法和數(shù)據(jù)層面的代價(jià)敏感方法，通過調(diào)整不同類別的誤分類成本提高分類性能[13-14]。本文設(shè)計(jì)三種隨機(jī)欠采樣方法以解決類不平衡分類問題，分別為一次不放回隨機(jī)欠采樣(Random Under-Sampling once without replacement, RUS-once)、多次不放回隨機(jī)欠采樣(Random Under-Sampling multiple times without replacement, RUS-multiple)和有放回隨機(jī)欠采樣(Random Under-Sampling with replacement, RUS-replacement)。

垃圾網(wǎng)頁指的是那些在搜索引擎查詢結(jié)果中具有良好的排名而實(shí)際價(jià)值卻較差的網(wǎng)站和網(wǎng)頁。垃圾網(wǎng)頁削弱了搜索引擎的權(quán)威性，浪費(fèi)了大量計(jì)算與存儲(chǔ)資源，剝奪了合法網(wǎng)站的正當(dāng)利益，降低了搜索結(jié)果的質(zhì)量[15]。為此，搜索引擎公司和研究人員都在設(shè)計(jì)出各種算法以檢測(cè)垃圾網(wǎng)頁，降低其搜索引擎查詢結(jié)果排名。據(jù)估計(jì)，整個(gè)互聯(lián)網(wǎng)的垃圾網(wǎng)頁占到15%左右[15]。由此可知，垃圾網(wǎng)頁檢測(cè)是一個(gè)不平衡分類問題。但是與異常檢測(cè)、故障診斷等問題相比，其不平衡程度是較為輕微的，正負(fù)類比例在1∶6左右。對(duì)于這種輕微的類不平衡分類問題，本文假設(shè)可以從數(shù)據(jù)方面著手采用隨機(jī)欠采樣方法得到解決。為此，本文選擇分類回歸樹(Classification And Regression Tree, CART)作為子分類器，結(jié)合設(shè)計(jì)的三種隨機(jī)欠采樣方法進(jìn)行垃圾網(wǎng)頁檢測(cè)，并比較其分類性能差異。

1 隨機(jī)欠采樣集成分類比較

本文提出的用于垃圾網(wǎng)頁檢測(cè)的隨機(jī)欠采樣集成分類的過程框架如圖1所示，共分訓(xùn)練階段和測(cè)試階段兩個(gè)階段。其中訓(xùn)練階段包括三個(gè)步驟：首先采用隨機(jī)欠采樣方法將不平衡數(shù)據(jù)集轉(zhuǎn)換成多個(gè)平衡數(shù)據(jù)集；然后，基于上個(gè)步驟得到的多個(gè)平衡數(shù)據(jù)集訓(xùn)練出多個(gè)CART分類器；最后采用簡單投票法將此多個(gè)決策樹分類器構(gòu)建一個(gè)集成分類器。在測(cè)試階段，使用此基于隨機(jī)欠采樣的集成分類器對(duì)測(cè)試數(shù)據(jù)集進(jìn)行分類。本文設(shè)計(jì)了三種隨機(jī)欠采樣方法RUS-onces、RUS-multiple和RUS-replacement，并比較了它們用于垃圾網(wǎng)頁檢測(cè)的性能差異。本文重點(diǎn)介紹這三種隨機(jī)欠采樣方法的設(shè)計(jì)及其性能比較，而CART分類、簡單投票法集成都是已得到充分研究的技術(shù)，在本文提出的三種方法中的使用方式都一樣，因此僅在1.1節(jié)中介紹它們?nèi)绾闻c隨機(jī)欠采樣方法一起構(gòu)建集成分類器。

圖1 隨機(jī)欠采樣集成分類器過程框架

1.1 一次不放回隨機(jī)欠采樣

本文將垃圾網(wǎng)頁檢測(cè)視為一個(gè)二元分類問題。在一個(gè)二元分類問題中，假設(shè)小類樣本集S和大類樣本集N，隨機(jī)欠采樣方法從大類樣本集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=n/s。這樣得到每份大類樣本子集N′的樣本數(shù)n′也約等于小類樣本集S的樣本數(shù)s。分別組合N′與S，得到k個(gè)均衡的樣本子集Di={S,Ni′}(i=1, 2, …,k)，每個(gè)平衡的樣本集Di均可用于訓(xùn)練一個(gè)分類器。算法1列出了此一次不放回隨機(jī)欠采樣技術(shù)將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集的偽代碼。

算法1 一次不放回隨機(jī)欠采樣方法RUS-once。

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

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

1)

s=小類樣本個(gè)數(shù);

2)

n=大類樣本個(gè)數(shù);

3)

k=n/s;

4)

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

5)

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

6)

返回Di。

該算法實(shí)現(xiàn)較為簡單，小類樣本重復(fù)多次，大類樣本只使用一次，已充分利用所有樣本。與后面將要介紹的RUS-multiple和RUS-replacement方法相比，該方法生成的分類器數(shù)要少很多，但也可能正是這個(gè)原因，導(dǎo)致該集成分類器的分類性能比后兩種方法略差。

基于上述一次不放回隨機(jī)欠采樣方法得到的多個(gè)平衡數(shù)據(jù)集，可訓(xùn)練出多個(gè)CART分類器，采用簡單投票法集成所有分類器即得到一個(gè)集成決策樹分類器。在測(cè)試階段，每個(gè)集成分類器中的子分類器均將測(cè)試樣本分類為垃圾網(wǎng)頁或正常網(wǎng)頁，根據(jù)分類結(jié)果的不同，得到一個(gè)分?jǐn)?shù)。該分?jǐn)?shù)的計(jì)算如式(1)所示：

(1)

其中：x為測(cè)試樣本；C是子分類器，即為一個(gè)CART分類器；Score(x，C)為使用C對(duì)x進(jìn)行分類后分類結(jié)果對(duì)應(yīng)的分?jǐn)?shù)。匯總所有子分類器得到的分?jǐn)?shù)并取平均值，即得到一個(gè)范圍在[-1,1]的實(shí)數(shù)，該值可稱為樣本x的垃圾值(spamicity)，該值越大則樣本越可能為垃圾網(wǎng)頁，越小則越不可能為垃圾網(wǎng)頁。可將所有樣本的spamicity值直接用于計(jì)算集成分類器的AUC(AreaUnderthereceiveroperatingcharacteristicCurve)值。同時(shí)，樣本的最終分類結(jié)果也可通過式(2)計(jì)算得到。

(2)

如果最終的分類結(jié)果值為1，則表示樣本為垃圾網(wǎng)頁，否則為正常網(wǎng)頁。

1.2 多次不放回隨機(jī)欠采樣

上述一次不放回隨機(jī)欠采樣方法將僅對(duì)大類樣本作一次不放回隨機(jī)欠采樣，這樣只能夠得到一種類型的平衡數(shù)據(jù)集。實(shí)際上，多次進(jìn)行隨機(jī)欠采樣可以得到多種類型的平衡數(shù)據(jù)集，將此多種類型的平衡數(shù)據(jù)集用于訓(xùn)練學(xué)習(xí)，可得到多種不同的決策樹分類器，將此決策樹分類器用于分類，可提升分類效果。如果同樣采用不放回隨機(jī)欠采樣，可將此方法稱為基于多次不放回隨機(jī)欠采樣的集成分類器。多次不放回隨機(jī)欠采樣跟一次不放回隨機(jī)欠采樣相比，需要多確定一個(gè)輸入?yún)?shù)，即重復(fù)欠采樣多少次為宜。一般而言，為了方便簡單投票法集成，應(yīng)該設(shè)置為奇數(shù)。因?yàn)樽罱K的子分類器個(gè)數(shù)(即平衡數(shù)據(jù)集個(gè)數(shù))為每次采樣產(chǎn)生的分類器個(gè)數(shù)和重復(fù)欠采樣次數(shù)的積，所以每次采樣產(chǎn)生的分類器個(gè)數(shù)也應(yīng)該為奇數(shù)。理論上，重復(fù)欠采樣的次數(shù)越多，得到不平衡數(shù)據(jù)集的種類也更多，相應(yīng)的子分類器的種類也更多，最終集成分類器的分類準(zhǔn)確率也可能更高；但是，重復(fù)次數(shù)越多，分類器之間的差異越小，運(yùn)行時(shí)間也越久。因此應(yīng)該權(quán)衡設(shè)置一個(gè)可兼顧二者的較為合理的重復(fù)次數(shù)。算法2列出了多次不放回隨機(jī)欠采樣方法將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集的偽代碼。

算法2 多次不放回隨機(jī)欠采樣算法RUS-multiple。

輸入 不平衡數(shù)據(jù)集，內(nèi)含小類樣本集S和大類樣本集N，隨機(jī)欠采樣重復(fù)次數(shù)t；

輸出 多個(gè)平衡的樣本子集Dij(i=1, 2, …,t,j=1, 2, …,k)。

1)

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

2)

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

3)

k=n/s；

4)

fori=1tot

a)

將大類樣本平均分成k個(gè)樣本子集Ni1′,Ni2′， …,Nik′，其中Nij′的樣本個(gè)數(shù)nij′約等于小類樣本集S的樣本個(gè)數(shù)s；

b)

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

5)

endfor

6)

返回Dij。

該算法與RUS-once算法非常類似，只是多了一個(gè)參數(shù)：重復(fù)次數(shù)t。即除了小類樣本要重復(fù)更多次外，大類樣本也要重復(fù)出現(xiàn)t次。因?yàn)槊看未箢愔貜?fù)時(shí)，隨機(jī)采樣得到的樣本并不相同，最終學(xué)習(xí)得到的分類器模型也就不盡相同。這就保證了分類器的多樣性，一定程度上提高了其分類性能。當(dāng)然，該算法所需訓(xùn)練的分類器數(shù)是RUS-once的t倍，訓(xùn)練學(xué)習(xí)以及最終分類的時(shí)間都要更長。

1.3 有放回隨機(jī)欠采樣

上述兩種不放回隨機(jī)欠采樣方法中，每次采樣得到的平衡數(shù)據(jù)集中，相互之間的大類樣本是完全不一樣的，這保證了讓盡可能多的大類樣本參與分類，同時(shí)確保平衡數(shù)據(jù)集的多樣性。然而不放回隨機(jī)欠采樣有一個(gè)缺陷，即在每個(gè)平衡數(shù)據(jù)集中大類樣本數(shù)與小類樣本數(shù)并不相等。在每個(gè)平衡數(shù)據(jù)集中，如果大類樣本數(shù)與小類樣本數(shù)完全相同，集成分類器的性能是否會(huì)提升？為驗(yàn)證此想法，提出一種有放回的隨機(jī)欠采樣方法。該方法確保每個(gè)平衡數(shù)據(jù)集中大類樣本數(shù)和小類樣本數(shù)完全相等，但在同一個(gè)數(shù)據(jù)集中，同一個(gè)大類樣本是否出現(xiàn)多次則不再考慮。為了確保數(shù)據(jù)集的多樣性，采樣的次數(shù)應(yīng)該足夠多。當(dāng)然，最終平衡數(shù)據(jù)集的個(gè)數(shù)同樣應(yīng)該為奇數(shù)。本文在將這些隨機(jī)欠采樣方法應(yīng)用于垃圾網(wǎng)頁檢測(cè)的過程中，為了使得該方法能更好地與上述多次不放回隨機(jī)欠采樣方法相比較，兩種方法得到平衡數(shù)據(jù)集個(gè)數(shù)應(yīng)該相同，即有放回隨機(jī)欠采樣的次數(shù)應(yīng)該等于多次不放回隨機(jī)欠采樣的重復(fù)次數(shù)乘以每次產(chǎn)生的平衡數(shù)據(jù)集個(gè)數(shù)。有放回隨機(jī)欠采樣的偽代碼如算法3所示。

算法3 有放回隨機(jī)欠采樣算法RUS-replacement。

輸入 不平衡數(shù)據(jù)集，內(nèi)含小類樣本集S和大類樣本集N，采樣次數(shù)(平衡數(shù)據(jù)集個(gè)數(shù))t；

輸出 多個(gè)平衡的樣本子集Di(i=1, 2, …,t)。

1)

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

2)

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

3)

fori=1tot

a)

從n個(gè)大類樣本中隨機(jī)采樣出1個(gè)大類樣本；

b)

將步驟a)重復(fù)s次，即通過有放回的隨機(jī)欠采樣得到s個(gè)大類樣本，構(gòu)成大類子樣本集Ni′；

c)

將采樣得到的大類子樣本集Ni′和小類樣本集S組合一起構(gòu)成新的平衡的樣本子集Di；

4)

endfor

5)

返回Di。

該算法與RUS-multiple相比，生成的子分類器個(gè)數(shù)相同，因此訓(xùn)練學(xué)習(xí)和最終分類的時(shí)間相差不大，是RUS-once算法的t倍。與RUS-multiple相比，該算法用于訓(xùn)練分類器的樣本集中，大小類樣本數(shù)完全相等。但后面的實(shí)驗(yàn)表明，這并不一定能使分類性能更好。

2 實(shí)驗(yàn)與分析

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

本文實(shí)驗(yàn)所用數(shù)據(jù)集為WEBSPAM-UK2006[16]和WEBSPAM-UK2007[16]，它們分別是網(wǎng)絡(luò)對(duì)抗信息檢索研討會(huì)2007年、2008年用于垃圾網(wǎng)頁檢測(cè)競賽使用的數(shù)據(jù)集，現(xiàn)已成為垃圾網(wǎng)頁檢測(cè)研究的公開數(shù)據(jù)集。數(shù)據(jù)集本身已按保持法的要求分為訓(xùn)練集和測(cè)試集兩個(gè)部分，擁有多種不同的特征。本文采納了其中四種特征，分別是基于內(nèi)容的特征96個(gè)，基于鏈接的特征41個(gè)，基于鏈接轉(zhuǎn)換的特征135個(gè)，基于鄰接圖的特征2個(gè)?；趦?nèi)容的特征包括網(wǎng)頁中含有的單詞數(shù)量、平均單詞長度、平均標(biāo)題長度、可見內(nèi)容比率、流行詞所占比率等；基于鏈接的特征主要通過分析主頁和最高PageRank值頁面的相關(guān)情況得到，包括主頁與最大PageRank值頁面是否為同一頁，主頁和最大PageRank值頁面的鏈入數(shù)(In-Degree)、鏈出數(shù) (Out-Degree)、PageRank、TrustRank等；基于鏈接轉(zhuǎn)換的特征則是通過基于鏈接的特征進(jìn)行不同的換算得到；基于鄰接圖的特征是通過對(duì)Stacked鏈接圖進(jìn)行學(xué)習(xí)而得到的，但WEBSPAM-UK2007未提供此特征。這些特征是進(jìn)行垃圾網(wǎng)頁檢測(cè)的常用特征，也是2007、2008兩年垃圾網(wǎng)頁檢測(cè)競賽各團(tuán)隊(duì)所使用的基本特征。除這些特征外，各團(tuán)隊(duì)還可以使用其他辦法提取更多的特征用于分類。訓(xùn)練集和測(cè)試集的樣本數(shù)情況如表1所示。由表1可知，WEBSPAM-UK2006訓(xùn)練集中正常網(wǎng)站與垃圾網(wǎng)站的比例約為7∶1，這表明訓(xùn)練集是不平衡的，與真實(shí)情況較為一致，但測(cè)試數(shù)據(jù)集未體現(xiàn)出不平衡性；WEBSPAM-UK2007訓(xùn)練集和測(cè)試集中正常網(wǎng)站與垃圾網(wǎng)站的比例都約為17∶1，體現(xiàn)了數(shù)據(jù)不平衡性。

表1 實(shí)驗(yàn)數(shù)據(jù)集

本文使用三種指標(biāo)評(píng)估分類模型，分別是準(zhǔn)確率(Accuracy)，F(xiàn)1-測(cè)度(F1-Measure)和AUC值。對(duì)于二元分類問題，其表達(dá)測(cè)試樣本集分類結(jié)果的混淆矩陣由TP(TruePositive)、TN(TrueNegative)、FP(FalsePositive)和FN(FalseNegative)四個(gè)值構(gòu)成，其中TP為被正確分類的正例，TN為正確分類的負(fù)例，F(xiàn)P為錯(cuò)誤分類的正例，F(xiàn)N為錯(cuò)誤分類的負(fù)例。于是準(zhǔn)確率和F1-測(cè)度值可分別用式(3)、式(4)計(jì)算得到。

(3)

(4)

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

2.2 子分類器和參數(shù)設(shè)置

本文使用CART分類器作為子分類器。通過多次實(shí)驗(yàn)發(fā)現(xiàn)，基于隨機(jī)欠采樣集成的方法中，子分類器采用決策樹和隨機(jī)森林分類器中比其他分類器如支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、K近鄰、樸素貝葉斯等分類器更好。而隨機(jī)森林分類器本身就是使用Bootstrap采樣然后Bagging集成CART分類器得到的，為了更好地將本文設(shè)計(jì)的三種隨機(jī)欠采樣方法與Bagging、AdaBoost等集成方法進(jìn)行比較，使用CART分類器作為子分類器。

據(jù)前文介紹可知：一次不放回隨機(jī)欠采樣集成分類方法只需輸入訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集即可，不需要設(shè)置其他參數(shù)；而多次不放回隨機(jī)欠采樣集成分類方法則需要設(shè)置一個(gè)重復(fù)次數(shù)的參數(shù)，根據(jù)實(shí)驗(yàn)結(jié)果可知，將此參數(shù)設(shè)置為9更加合適。由于在每次不放回隨機(jī)欠采樣過程中，WEBSPAM-UK2006將產(chǎn)生7個(gè)平衡訓(xùn)練數(shù)據(jù)集，WEBSPAM-UK2007將產(chǎn)生17個(gè)平衡訓(xùn)練數(shù)據(jù)集，因此在有放回隨機(jī)欠采樣方法中，應(yīng)該將采樣次數(shù)t分別設(shè)置為7×9=63和17×9=153。

2.3 不同欠采樣方法的比較

表2列出了將一次不放回隨機(jī)欠采樣(CART+RUS-once)、多次不放回隨機(jī)欠采樣(CART+RUS-multiple)和有放回隨機(jī)欠采樣(CART+RUS-replacement)三種集成分類器用于對(duì)數(shù)據(jù)集WEBSPAM-2006和WEBSPAM-2007進(jìn)行垃圾網(wǎng)頁檢測(cè)后的分類結(jié)果值。為了更好地與其他傳統(tǒng)分類器比較，表2同時(shí)列出了CART、CART+Bagging和CART+Adaboost三種分類器的檢測(cè)結(jié)果。從表2中WEBSPAM-UK2006的結(jié)果可以看出，三種隨機(jī)欠采樣集成分類器跟決策樹及其Bagging、Adaboost集成分類器相比，無論在準(zhǔn)確率、F1-測(cè)度還是AUC指標(biāo)方面，都要明顯更優(yōu)。Bagging和Adaboost集成分類器與其子分類器CART分類器相比在分類準(zhǔn)確率、F1測(cè)度和AUC三個(gè)指標(biāo)上都有3～5個(gè)百分點(diǎn)的提升，而本文提出的隨機(jī)欠采樣集成分類器則又提升了10個(gè)百分點(diǎn)左右；而且本文提出的三種隨機(jī)欠采樣集成分類器中，有放回的隨機(jī)欠采樣集成分類器性能表現(xiàn)最優(yōu)。由表2中WEBSPAM-UK2007的結(jié)果可知，從準(zhǔn)確率和F1測(cè)度兩個(gè)指標(biāo)看，集成分類器并不比單一分類器表現(xiàn)更優(yōu)；但從AUC指標(biāo)看，本文提出的三種方法比其他方法明顯更優(yōu)，提高25個(gè)百分點(diǎn)左右。

表3和表4分別列出了2007、2008年垃圾網(wǎng)頁挑戰(zhàn)競賽各優(yōu)勝團(tuán)隊(duì)的分類結(jié)果。因?yàn)閃EBSPAM-UK2007中測(cè)試數(shù)據(jù)集也是不平衡的，而準(zhǔn)確率和F1測(cè)度兩個(gè)指標(biāo)不適合于評(píng)價(jià)不平衡分類的性能，因此只能通過AUC指標(biāo)來評(píng)判各分類器的優(yōu)劣，所以2008年垃圾網(wǎng)頁挑戰(zhàn)賽(Webspamchallenge2008)優(yōu)勝團(tuán)隊(duì)的分類結(jié)果中就只列出了AUC的值。將其與本文提出的三種隨機(jī)欠采樣集成分類器中較優(yōu)的RUS-multiple和RUS-replacement兩種方法就AUC指標(biāo)進(jìn)行比較可以發(fā)現(xiàn)，在WEBSPAM-UK2006中，RUS-replacement方法的AUC值為0.943 4，高于最優(yōu)團(tuán)隊(duì)匈牙利科學(xué)院的結(jié)果值；在WEBSPAM-UK2007中，RUS-multiple方法的AUC值為0.854 4，達(dá)到最優(yōu)團(tuán)隊(duì)中國科學(xué)院的結(jié)果值。這反映出本文提出的RUS-multiple和RUS-replacement兩種集成分類器具有良好的分類性能。

Scarselli等[15]提出一種包含概率映射圖自組織映射(ProbabilisticMappingGraphself-organizingmap,PM-G)和圖神經(jīng)網(wǎng)絡(luò)(GraphNeuralNetwork,GNN)的圖層疊架構(gòu)用于垃圾網(wǎng)頁檢測(cè)，同樣基于WEBSPAMUK-2006進(jìn)行實(shí)驗(yàn)。表5列出了其所提方法的實(shí)驗(yàn)結(jié)果，其中的FNN、PM-G+GNN(3)+GNN(1)算法表現(xiàn)出最好的檢測(cè)效果。本文提出的RUS-replacement方法與其相比，除了準(zhǔn)確率稍微低一些外，F(xiàn)1-測(cè)度明顯更優(yōu)，AUC指標(biāo)值也略勝一籌。

表2 CART、CART+Bagging、CART+Adaboost及本文方法的檢測(cè)結(jié)果

本文作者也曾提出結(jié)合隨機(jī)森林和欠采樣的方法(RandomForest+Under-Sampling，RF+US)[19]、結(jié)合免疫克隆特征選擇和欠采樣的方法(ImmuneClonalFeatureSelectionandUnder-Sampling+EnsembleRandomForest，ICFSUS+ERF)[20]針對(duì)數(shù)據(jù)集WEBSPAM-UK2006進(jìn)行垃圾網(wǎng)頁檢測(cè)，分類結(jié)果如表6所示。其中RF+US、ICFSUS+ERF算法中的欠采樣算法其實(shí)就是本文的RUS-once采樣算法。對(duì)照表2和表6可知，RF+US方法的分類效果比本文提出的CART+RUS-once更好，這正是因?yàn)镽F+US中除了使用RUS-once進(jìn)行欠采樣外，其中的隨機(jī)森林算法本身還采用了Bagging集成的緣故；但RF+US方法的分類效果比本文提出的CART+RUS-multiple和CART+RUS-replacement兩種方法在AUC指標(biāo)上略微差些。與ICFSUS-ERF相比，本文提出的三種方法還是略顯不足，但是ICFSUS-ERF需要耗費(fèi)大量的時(shí)間采用免疫遺傳算法進(jìn)行智能搜索選擇出最優(yōu)特征子集，在運(yùn)行性能上比本文提出的三種方法都要更差。

表3 2007年垃圾網(wǎng)頁挑戰(zhàn)賽優(yōu)勝團(tuán)隊(duì)分類結(jié)果

表5 Scarselli等[15]提出方法的分類結(jié)果

表6 本文作者設(shè)計(jì)的其他算法的分類結(jié)果

2.4 討論

由實(shí)驗(yàn)結(jié)果可知，本文提出的三種以CART為子分類器的隨機(jī)欠采樣集成分類器用于正負(fù)類稍顯不平衡的垃圾網(wǎng)頁檢測(cè)的分類，得到了較為優(yōu)良的效果。三種方法中，多次不放回的隨機(jī)欠采樣集成分類器和有放回的隨機(jī)欠采樣集成分類器比一次不放回的隨機(jī)欠采樣集成分類器性能更優(yōu)，取得了更好的分類結(jié)果；跟其他最優(yōu)的分類結(jié)果相比，多次不放回的隨機(jī)欠采樣集成分類器和有放回的隨機(jī)欠采樣集成分類器在AUC指標(biāo)上達(dá)到最優(yōu)分類結(jié)果水平。這些優(yōu)良分類效果的取得，一方面要?dú)w因于決策樹分類器本身的優(yōu)異分類性能，另一方面則是讓正負(fù)類平衡的隨機(jī)欠采樣技術(shù)從數(shù)據(jù)方面在一定程度上解決了類不平衡分類問題，而集成方法又使得所有數(shù)據(jù)都得到了充分的利用，尤其是多次不放回隨機(jī)欠采樣和有放回隨機(jī)欠采樣兩種方法，使每一個(gè)樣本都參與了多個(gè)決策樹分類器的構(gòu)建，每個(gè)決策樹分類器又由于樣本不完全一樣而存在多樣性，多種決策分類器集成分類，分類性能提升極大。

3 結(jié)語

針對(duì)垃圾網(wǎng)頁檢測(cè)中輕微的類不平衡現(xiàn)象，從數(shù)據(jù)方面著手，本文設(shè)計(jì)了三種隨機(jī)欠采樣算法，以CART分類器作為子分類器，構(gòu)建集成分類器，對(duì)垃圾網(wǎng)頁數(shù)據(jù)集進(jìn)行分類。這三種隨機(jī)欠采樣集成分類器中，除一次不放回隨機(jī)欠樣性能稍差外，多次不放回隨機(jī)欠采樣分類器和有放回隨機(jī)欠采樣分類器都表現(xiàn)出優(yōu)良的分類性能，與當(dāng)前最優(yōu)秀的垃圾網(wǎng)頁檢測(cè)算法相比，仍然有其優(yōu)勢(shì)?？蓪⒈疚奶岢龅娜N隨機(jī)欠采樣集成分類方法用于其他輕微類不平衡的應(yīng)用領(lǐng)域，以檢驗(yàn)它們的泛化能力，探索其適用范圍。

)

[1]YANGQ,WUX.10challengingproblemsindataminingresearch[J].InternationalJournalofInformationTechnology&DecisionMaking.2006, 5(4): 597-604.

[2]YANGZ,TANGWH,SHINTEMIROVA,etal.Associationrulemining-baseddissolvedgasanalysisforfaultdiagnosisofpowertransformers[J].IEEETransactionsonSystems,Man,andCybernetics,PartC:ApplicationsandReviews, 2009, 39(6): 597-610.

[3]KHREICHW,GRANGERE,MIRIA,etal.IterativeBooleancombinationofclassifiersintheROCspace:anapplicationtoanomalydetectionwithHMMs[J].PatternRecognition.2010, 43(8): 2732-2752.

[4]MAZUROWSKIMA,HABASPA,ZURADAJM,etal.2008specialissue:trainingneuralnetworkclassifiersformedicaldecisionmaking:theeffectsofimbalanceddatasetsonclassificationperformance[J].NeuralNetworks.2008, 21(2/3): 427-436.

[5]LIUY-H,CHENY-T.Totalmarginbasedadaptivefuzzysupportvectormachinesformultiviewfacerecognition[C]//Proceedingsofthe2005IEEEInternationalConferenceonSystems,ManandCybernetics.Piscataway,NJ:IEEE, 2005: 1704-1711

[6]QUINLANJR.Improvedestimatesfortheaccuracyofsmalldisjuncts[J].MachineLearning, 1991, 6(1): 93-98.

[7]ZADROZNYB,ELKANC.Learningandmakingdecisionswhencostsandprobabilitiesarebothunknown[C]//ProceedingsoftheSeventhACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2001: 204-213.

[8]WUG,CHANGEY.KBA:kernelboundaryalignmentconsideringimbalanceddatadistribution[J].IEEETransactionsonKnowledgeandDataEngineering, 2005, 17(6): 786-795.

[9]BATISTAGEAPA,PRATIRC,MONARDMC.Astudyofthebehaviorofseveralmethodsforbalancingmachinelearningtrainingdata[J].ACMSIGKDDExplorationsNewsletter, 2004, 6(1): 20-29.

[10]CHAWLANV,JAPKOWICZN,KOTCZA.Editorial:specialissueonlearningfromimbalanceddatasets[J].ACMSIGKDDExplorationsNewsletter, 2004, 6(1): 1-6.

[11]GENGG-G,WANGC-H,LIQ-D,etal.BoostingtheperformanceofWebspamdetectionwithensembleunder-samplingclassification[C]//FSKD’07:ProceedingsoftheIEEEFourthInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.Piscataway,NJ:IEEE, 2007, 4: 583-587

[12]CHAWLANV,BOWYERKW,HALLLO,etal.SMOTE:syntheticminorityover-samplingtechnique[J].JournalofArtificialIntelligenceResearch, 2002, 16(1): 321-357.

[13]CHAWLANV,CIESLAKDA,HALLLO,etal.Automaticallycounteringimbalanceanditsempiricalrelationshiptocost[J].DataMiningandKnowledgeDiscovery, 2008, 17(2): 225-252.

[14]FREITASA,COSTA-PEREIRAA,BRAZDILP.Cost-sensitivedecisiontreesappliedtomedicaldata[C]//DaWaK2007:Proceedingsofthe9thInternationalConferenceonDataWarehousingandKnowledgeDiscovery,LNCS4654.BerlinHeidelberg:Springer, 2007: 303-312.

[15] SPIRIN N, HAN J.Survey on Web spam detection: principles and algorithms[J].ACM SIGKDD Explorations Newsletter, 2012, 13(2): 50-64.

[16] CASTILLO C, DONATO D, BECCHETTI L, et al.A reference collection for Web spam[J].ACM SIGIR Forum.2006, 40(2): 11-24.

[17] FAWCETT T.An introduction to ROC analysis[J].Pattern Recognition Letters, 2006, 27(8): 861-874.

[18] DAVIS J, GOADRICH M.The relationship between precision-recall and ROC curves [C]// Proceedings of the 23rd International Conference on Machine Learning.New York: ACM, 2006: 233-240.

[19] 盧曉勇,陳木生.基于隨機(jī)森林和克隆選擇的垃圾網(wǎng)頁檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2016,36(1):156-159.(LU X Y, CHEN M S.Web spam detection based on random forests and under-sampling ensemble [J].Journal of Computer Applications, 2016, 36(1): 156-159.)

[20] 盧曉勇,陳木生,吳政隆,等.基于免疫克隆特征選擇和欠采樣集成的垃圾網(wǎng)頁檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2016,36(7):1899-1903.(LU X Y, CHEN M S, WU J L, et al.Web spam detection based on immune clonal feature selection and under-sampling ensemble [J].Journal of Computer Applications, 2016, 36(7): 1899-1903.)

This work is partially supported by the Sciences and Technology Support Program of Jiangxi Province (20131102040039).

CHEN Musheng, born in 1977, Ph.D.candidate.His research interests include data mining and knowledge discovery, information management and information system.

LU Xiaoyong, born in 1957, Ph.D., professor.His research interests include information management and information system, industry engineering.

Three random under-sampling based ensemble classifiers for Web spam detection

CHEN Musheng1*, LU Xiaoyong2

(1.SchoolofInformationEngineering,NanchangUniversity,NanchangJiangxi330031,China;2.SchoolofSoftware,NanchangUniversity,NanchangJiangxi330047,China)

In order to solve the problem of slighty imbalanced classification in Web spam detection, three ensemble classifiers based on random under-sampling techniques were proposed, including Random Under-Sampling once without replacement (RUS-once), Random Under-Sampling multiple times without replacement (RUS-multiple) and Random Under-Sampling with replacement (RUS-replacement).At first, the unbalanced training dataset was converted into several balanced datasets by using one of the under-sampling techniques.Secondly, the Classification And Regression Tree (CART) classifiers were trained based on the balanced datasets.Finally, an ensemble classifier was constructed with all of the CART classifiers based on simple voting rule and used to classify the test samples.The experimental results show that the three kinds of random under-sampling based ensemble classifiers achieve good classification results, the performance of RUS-multiple and RUS-replacement are better than RUS-once.Compared with CART, Bagging with CART and Adaboost with CART, the AUC values of RUS-multiple and RUS-replacement increase about 10% on WEBSPAM UK-2006 and about 25% on WEBSPAM UK-2007; compared with several state-of-the-art baseline classification models, RUS-multiple and RUS-replacement achieve the optimal results in AUC value.

Web spam detection; imbalanced classification; ensemble learning; under-sampling; Classification And Regression Tree (CART)

2016- 08- 01;

2016- 08- 22。 基金項(xiàng)目:江西省科技支撐計(jì)劃項(xiàng)目(20131102040039)。

陳木生(1977—)，男，江西于都人，博士研究生，主要研究方向：數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)、信息管理與信息系統(tǒng)； 盧曉勇(1957—)，男，江西高安人，教授，博士，主要研究方向：信息管理與信息系統(tǒng)、工業(yè)工程。

1001- 9081(2017)02- 0535- 05

10.11772/j.issn.1001- 9081.2017.02.0535

TP391.1; TP393.098; TP181

A