三種用于垃圾網頁檢測的隨機欠采樣集成分類器

陳木生，盧曉勇

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

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

三種用于垃圾網頁檢測的隨機欠采樣集成分類器

陳木生1*，盧曉勇2

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

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

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

垃圾網頁檢測；不平衡分類；集成學習；欠采樣；分類回歸樹

0 引言

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

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

1 隨機欠采樣集成分類比較

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

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

1.1 一次不放回隨機欠采樣

本文將垃圾網頁檢測視為一個二元分類問題。在一個二元分類問題中，假設小類樣本集S和大類樣本集N，隨機欠采樣方法從大類樣本集N中隨機地抽取出樣本子集N′，使得N′的樣本數n′遠遠小于N的樣本數n，即n′?n，但約等于小類樣本集S的樣本數s，即n′≈s。將大類樣本子集N′與小類樣本集S合并到一起構成一個新的平衡樣本集D，使用此平衡的樣本集D訓練分類器模型要比原來不平衡的樣本集無論是在運行性能還是分類準確率上都要更好。然而D只利用了大類樣本集的小部分樣本，其他樣本未得到利用，造成浪費。為充分利用所有大類樣本，將大類樣本采用不放回抽樣平均分成k等份可得到k個樣本子集：N1′,N2′, …,Nk′，其中k=n/s。這樣得到每份大類樣本子集N′的樣本數n′也約等于小類樣本集S的樣本數s。分別組合N′與S，得到k個均衡的樣本子集Di={S,Ni′}(i=1, 2, …,k)，每個平衡的樣本集Di均可用于訓練一個分類器。算法1列出了此一次不放回隨機欠采樣技術將不平衡數據集轉換為平衡數據集的偽代碼。

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

輸入 不平衡數據集，內含小類樣本集S和大類樣本集N；

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

1)

s=小類樣本個數;

2)

n=大類樣本個數;

3)

k=n/s;

4)

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

5)

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

6)

返回Di。

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

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

(1)

其中：x為測試樣本；C是子分類器，即為一個CART分類器；Score(x，C)為使用C對x進行分類后分類結果對應的分數。匯總所有子分類器得到的分數并取平均值，即得到一個范圍在[-1,1]的實數，該值可稱為樣本x的垃圾值(spamicity)，該值越大則樣本越可能為垃圾網頁，越小則越不可能為垃圾網頁?？蓪⑺袠颖镜膕pamicity值直接用于計算集成分類器的AUC(AreaUnderthereceiveroperatingcharacteristicCurve)值。同時，樣本的最終分類結果也可通過式(2)計算得到。

(2)

如果最終的分類結果值為1，則表示樣本為垃圾網頁，否則為正常網頁。

1.2 多次不放回隨機欠采樣

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

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

輸入 不平衡數據集，內含小類樣本集S和大類樣本集N，隨機欠采樣重復次數t；

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

1)

s=小類樣本個數；

2)

n=大類樣本個數；

3)

k=n/s；

4)

fori=1tot

a)

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

b)

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

5)

endfor

6)

返回Dij。

該算法與RUS-once算法非常類似，只是多了一個參數：重復次數t。即除了小類樣本要重復更多次外，大類樣本也要重復出現t次。因為每次大類重復時，隨機采樣得到的樣本并不相同，最終學習得到的分類器模型也就不盡相同。這就保證了分類器的多樣性，一定程度上提高了其分類性能。當然，該算法所需訓練的分類器數是RUS-once的t倍，訓練學習以及最終分類的時間都要更長。

1.3 有放回隨機欠采樣

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

算法3 有放回隨機欠采樣算法RUS-replacement。

輸入 不平衡數據集，內含小類樣本集S和大類樣本集N，采樣次數(平衡數據集個數)t；

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

1)

s=小類樣本個數；

2)

n=大類樣本個數；

3)

fori=1tot

a)

從n個大類樣本中隨機采樣出1個大類樣本；

b)

將步驟a)重復s次，即通過有放回的隨機欠采樣得到s個大類樣本，構成大類子樣本集Ni′；

c)

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

4)

endfor

5)

返回Di。

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

2 實驗與分析

2.1 數據集及評價指標

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

表1 實驗數據集

本文使用三種指標評估分類模型，分別是準確率(Accuracy)，F1-測度(F1-Measure)和AUC值。對于二元分類問題，其表達測試樣本集分類結果的混淆矩陣由TP(TruePositive)、TN(TrueNegative)、FP(FalsePositive)和FN(FalseNegative)四個值構成，其中TP為被正確分類的正例，TN為正確分類的負例，FP為錯誤分類的正例，FN為錯誤分類的負例。于是準確率和F1-測度值可分別用式(3)、式(4)計算得到。

(3)

(4)

對于二元分類而言，隨機挑選一個正例樣本以及一個負例樣本，分類算法根據計算得到的分數(Score)值將正例樣本排在負例樣本前面的概率即為AUC值[17]。在垃圾網頁檢測中，最終得到的spamicity值即可作為Score值。AUC值越大表明當前的分類算法越有可能將正例樣本排在負例樣本前面，即能夠更好地分類。AUC值相比準確率和F1-測度而言，更適合于不平衡數據集的分類性能評價[18]。

2.2 子分類器和參數設置

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

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

2.3 不同欠采樣方法的比較

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

表3和表4分別列出了2007、2008年垃圾網頁挑戰競賽各優勝團隊的分類結果。因為WEBSPAM-UK2007中測試數據集也是不平衡的，而準確率和F1測度兩個指標不適合于評價不平衡分類的性能，因此只能通過AUC指標來評判各分類器的優劣，所以2008年垃圾網頁挑戰賽(Webspamchallenge2008)優勝團隊的分類結果中就只列出了AUC的值。將其與本文提出的三種隨機欠采樣集成分類器中較優的RUS-multiple和RUS-replacement兩種方法就AUC指標進行比較可以發現，在WEBSPAM-UK2006中，RUS-replacement方法的AUC值為0.943 4，高于最優團隊匈牙利科學院的結果值；在WEBSPAM-UK2007中，RUS-multiple方法的AUC值為0.854 4，達到最優團隊中國科學院的結果值。這反映出本文提出的RUS-multiple和RUS-replacement兩種集成分類器具有良好的分類性能。

Scarselli等[15]提出一種包含概率映射圖自組織映射(ProbabilisticMappingGraphself-organizingmap,PM-G)和圖神經網絡(GraphNeuralNetwork,GNN)的圖層疊架構用于垃圾網頁檢測，同樣基于WEBSPAMUK-2006進行實驗。表5列出了其所提方法的實驗結果，其中的FNN、PM-G+GNN(3)+GNN(1)算法表現出最好的檢測效果。本文提出的RUS-replacement方法與其相比，除了準確率稍微低一些外，F1-測度明顯更優，AUC指標值也略勝一籌。

表2 CART、CART+Bagging、CART+Adaboost及本文方法的檢測結果

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

表3 2007年垃圾網頁挑戰賽優勝團隊分類結果

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

表6 本文作者設計的其他算法的分類結果

2.4 討論

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

3 結語

針對垃圾網頁檢測中輕微的類不平衡現象，從數據方面著手，本文設計了三種隨機欠采樣算法，以CART分類器作為子分類器，構建集成分類器，對垃圾網頁數據集進行分類。這三種隨機欠采樣集成分類器中，除一次不放回隨機欠樣性能稍差外，多次不放回隨機欠采樣分類器和有放回隨機欠采樣分類器都表現出優良的分類性能，與當前最優秀的垃圾網頁檢測算法相比，仍然有其優勢。可將本文提出的三種隨機欠采樣集成分類方法用于其他輕微類不平衡的應用領域，以檢驗它們的泛化能力，探索其適用范圍。

)

[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].計算機應用,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] 盧曉勇,陳木生,吳政隆,等.基于免疫克隆特征選擇和欠采樣集成的垃圾網頁檢測[J].計算機應用,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。 基金項目:江西省科技支撐計劃項目(20131102040039)。

陳木生(1977—)，男，江西于都人，博士研究生，主要研究方向：數據挖掘與知識發現、信息管理與信息系統； 盧曉勇(1957—)，男，江西高安人，教授，博士，主要研究方向：信息管理與信息系統、工業工程。

1001- 9081(2017)02- 0535- 05

10.11772/j.issn.1001- 9081.2017.02.0535

TP391.1; TP393.098; TP181

A