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 一次不放回随机欠采样

本文将垃圾网页检测视为一个二元分类问题。在一个二元分类问题中，假设小类样本集S和大类样本集N，随机欠采样方法从大类样本集N中随机地抽取出样本子集N′，使得N′的样本数n′远远小于N的样本数n，即n′$\ll $n，但约等于小类样本集S的样本数s，即n′≈s。将大类样本子集N′与小类样本集S合并到一起构成一个新的平衡样本集D，使用此平衡的样本集D训练分类器模型要比原来不平衡的样本集无论是在运行性能还是分类准确率上都要更好。然而D只利用了大类样本集的小部分样本，其他样本未得到利用，造成浪费。为充分利用所有大类样本，将大类样本采用不放回抽样平均分成k等份可得到k个样本子集：N₁′,N₂′,…,N_k′，其中k=n/s。这样得到每份大类样本子集N′的样本数n′也约等于小类样本集S的样本数s。分别组合N′与S，得到k个均衡的样本子集D_i={S,N_i′}(i=1,2,…,k)，每个平衡的样本集D_i均可用于训练一个分类器。算法1列出了此一次不放回随机欠采样技术将不平衡数据集转换为平衡数据集的伪代码。

算法1 一次不放回随机欠采样方法RUS-once。

输入 不平衡数据集，内含小类样本集S和大类样本集N；

输出 多个平衡的样本子集D_i(i=1,2,…,k)。

1)  s=小类样本个数;

2)  n=大类样本个数;

3)  k=n/s;

4)  将大类样本平均分成k个样本子集N₁′,N₂′,…,N_k′，其中N_i′的样本个数n_i′约等于小类样本集S的样本个数s;

5)  分别组合样本子集N_i′和小类样本集S构成新的平衡的样本子集D_i;

6)  返回D_i。

该算法实现较为简单，小类样本重复多次，大类样本只使用一次，已充分利用所有样本。与后面将要介绍的RUS-multiple和RUS-replacement方法相比，该方法生成的分类器数要少很多，但也可能正是这个原因，导致该集成分类器的分类性能比后两种方法略差。

基于上述一次不放回随机欠采样方法得到的多个平衡数据集，可训练出多个CART分类器，采用简单投票法集成所有分类器即得到一个集成决策树分类器。在测试阶段，每个集成分类器中的子分类器均将测试样本分类为垃圾网页或正常网页，根据分类结果的不同，得到一个分数。该分数的计算如式(1) 所示：

$Score(x,C)=\left\{ \begin{align} & 1,\text{ }测试样本为垃圾网页 \\ & -1,\text{ }测试样本为正常网页 \\ \end{align} \right.$

(1)

其中：x为测试样本；C是子分类器，即为一个CART分类器；Score(x，C)为使用C对x进行分类后分类结果对应的分数。汇总所有子分类器得到的分数并取平均值，即得到一个范围在[-1, 1]的实数，该值可称为样本x的垃圾值(spamicity)，该值越大则样本越可能为垃圾网页，越小则越不可能为垃圾网页。可将所有样本的spamicity值直接用于计算集成分类器的AUC(Area Under the receiver operating characteristic Curve)值。同时，样本的最终分类结果也可通过式(2) 计算得到。

$Classification\operatorname{Re}sult=\left\{ \begin{align} & 1,spamicity>0 \\ & -1,spamicity\le 0 \\ \end{align} \right.$

(2)

如果最终的分类结果值为1，则表示样本为垃圾网页，否则为正常网页。

1.2 多次不放回随机欠采样

上述一次不放回随机欠采样方法将仅对大类样本作一次不放回随机欠采样，这样只能够得到一种类型的平衡数据集。实际上，多次进行随机欠采样可以得到多种类型的平衡数据集，将此多种类型的平衡数据集用于训练学习，可得到多种不同的决策树分类器，将此决策树分类器用于分类，可提升分类效果。如果同样采用不放回随机欠采样，可将此方法称为基于多次不放回随机欠采样的集成分类器。多次不放回随机欠采样跟一次不放回随机欠采样相比，需要多确定一个输入参数，即重复欠采样多少次为宜。一般而言，为了方便简单投票法集成，应该设置为奇数。因为最终的子分类器个数(即平衡数据集个数)为每次采样产生的分类器个数和重复欠采样次数的积，所以每次采样产生的分类器个数也应该为奇数。理论上，重复欠采样的次数越多，得到不平衡数据集的种类也更多，相应的子分类器的种类也更多，最终集成分类器的分类准确率也可能更高；但是，重复次数越多，分类器之间的差异越小，运行时间也越久。因此应该权衡设置一个可兼顾二者的较为合理的重复次数。算法2列出了多次不放回随机欠采样方法将不平衡数据集转换为平衡数据集的伪代码。

算法2 多次不放回随机欠采样算法RUS-multiple。

输入 不平衡数据集，内含小类样本集S和大类样本集N，随机欠采样重复次数t；

输出 多个平衡的样本子集D_ij(i=1,2,…,t,j=1,2,…,k)。

1)  s=小类样本个数；

2)  n=大类样本个数；

3)  k=n/s；

4)  for i=1 to t

a)   将大类样本平均分成k个样本子集N_i1′,N_i2′，…,N_ik′，其中N_ij′的样本个数n_ij′约等于小类样本集S的样本个数s；

b)   分别组合样本子集N_ij′和小类样本集S构成新的平衡的样本子集D_ij；

5)  end for

6)  返回D_ij。

该算法与RUS-once算法非常类似，只是多了一个参数：重复次数t。即除了小类样本要重复更多次外，大类样本也要重复出现t次。因为每次大类重复时，随机采样得到的样本并不相同，最终学习得到的分类器模型也就不尽相同。这就保证了分类器的多样性，一定程度上提高了其分类性能。当然，该算法所需训练的分类器数是RUS-once的t倍，训练学习以及最终分类的时间都要更长。

1.3 有放回随机欠采样

上述两种不放回随机欠采样方法中，每次采样得到的平衡数据集中，相互之间的大类样本是完全不一样的，这保证了让尽可能多的大类样本参与分类，同时确保平衡数据集的多样性。然而不放回随机欠采样有一个缺陷，即在每个平衡数据集中大类样本数与小类样本数并不相等。在每个平衡数据集中，如果大类样本数与小类样本数完全相同，集成分类器的性能是否会提升？为验证此想法，提出一种有放回的随机欠采样方法。该方法确保每个平衡数据集中大类样本数和小类样本数完全相等，但在同一个数据集中，同一个大类样本是否出现多次则不再考虑。为了确保数据集的多样性，采样的次数应该足够多。当然，最终平衡数据集的个数同样应该为奇数。本文在将这些随机欠采样方法应用于垃圾网页检测的过程中，为了使得该方法能更好地与上述多次不放回随机欠采样方法相比较，两种方法得到平衡数据集个数应该相同，即有放回随机欠采样的次数应该等于多次不放回随机欠采样的重复次数乘以每次产生的平衡数据集个数。有放回随机欠采样的伪代码如算法3所示。

算法3 有放回随机欠采样算法RUS-replacement。

输入 不平衡数据集，内含小类样本集S和大类样本集N，采样次数(平衡数据集个数)t；

输出 多个平衡的样本子集D_i(i=1,2,…,t)。

1)  s=小类样本个数；

2)  n=大类样本个数；

3)  for i=1 to t

a)   从n个大类样本中随机采样出1个大类样本；

b)   将步骤a)重复s次，即通过有放回的随机欠采样得到s个大类样本，构成大类子样本集N_i′；

c)   将采样得到的大类子样本集N_i′和小类样本集S组合一起构成新的平衡的样本子集D_i；

4)  end for

5)  返回D_i。

该算法与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，体现了数据不平衡性。

本文使用三种指标评估分类模型，分别是准确率(Accuracy)，F1-测度(F1-Measure)和AUC值。对于二元分类问题，其表达测试样本集分类结果的混淆矩阵由TP(True Positive)、TN(True Negative)、FP(False Positive)和FN(False Negative)四个值构成，其中TP为被正确分类的正例，TN为正确分类的负例，FP为错误分类的正例，FN为错误分类的负例。于是准确率和F1-测度值可分别用式(3) 、式(4) 计算得到。

$Accuracy=\frac{TP+FN}{TP+FP+FN+TN}$

(3)

$F1-Measure=\frac{2TP}{2TP+FN+FP}$

(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年垃圾网页挑战赛(Web spam challenge 2008) 优胜团队的分类结果中就只列出了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]提出一种包含概率映射图自组织映射(Probabilistic Mapping Graph self-organizing map,PM-G)和图神经网络(Graph Neural Network,GNN)的图层叠架构用于垃圾网页检测，同样基于WEBSPAM UK-2006进行实验。表 5列出了其所提方法的实验结果，其中的FNN、 PM-G+GNN(3) +GNN(1) 算法表现出最好的检测效果。本文提出的RUS-replacement方法与其相比，除了准确率稍微低一些外，F1-测度明显更优，AUC指标值也略胜一筹。

本文作者也曾提出结合随机森林和欠采样的方法(Random Forest+Under-Sampling，RF+US)^[19]、结合免疫克隆特征选择和欠采样的方法(Immune Clonal Feature Selection and Under-Sampling+Ensemble Random Forest，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需要耗费大量的时间采用免疫遗传算法进行智能搜索选择出最优特征子集，在运行性能上比本文提出的三种方法都要更差。

2.4 讨论

由实验结果可知，本文提出的三种以CART为子分类器的随机欠采样集成分类器用于正负类稍显不平衡的垃圾网页检测的分类，得到了较为优良的效果。三种方法中，多次不放回的随机欠采样集成分类器和有放回的随机欠采样集成分类器比一次不放回的随机欠采样集成分类器性能更优，取得了更好的分类结果；跟其他最优的分类结果相比，多次不放回的随机欠采样集成分类器和有放回的随机欠采样集成分类器在AUC指标上达到最优分类结果水平。这些优良分类效果的取得，一方面要归因于决策树分类器本身的优异分类性能，另一方面则是让正负类平衡的随机欠采样技术从数据方面在一定程度上解决了类不平衡分类问题，而集成方法又使得所有数据都得到了充分的利用，尤其是多次不放回随机欠采样和有放回随机欠采样两种方法，使每一个样本都参与了多个决策树分类器的构建，每个决策树分类器又由于样本不完全一样而存在多样性，多种决策分类器集成分类，分类性能提升极大。

3 结语

针对垃圾网页检测中轻微的类不平衡现象，从数据方面着手，本文设计了三种随机欠采样算法，以CART分类器作为子分类器，构建集成分类器，对垃圾网页数据集进行分类。这三种随机欠采样集成分类器中，除一次不放回随机欠样性能稍差外，多次不放回随机欠采样分类器和有放回随机欠采样分类器都表现出优良的分类性能，与当前最优秀的垃圾网页检测算法相比，仍然有其优势。 可将本文提出的三种随机欠采样集成分类方法用于其他轻微类不平衡的应用领域，以检验它们的泛化能力，探索其适用范围。