随着互联网的快速成长，搜索引擎也逐渐发展起来，如今人人都需要使用搜索网站来找到自己需要的信息.但是有研究发现，85%的用户只会去查看第一页的内容，甚至只是查看搜索引擎中排名前十的网页^[1-2].可以看出，排名靠前的网站就会拥有更大的访问量.因此有些网站的所有者就会试图以不正当的手段和技术欺骗搜索引擎，从而提高网站排名，使他们的网站排名高于他们应得的，这些网页被称为垃圾网页.

目前垃圾网页分为链接垃圾网页、内容垃圾网页^[3]和伪装垃圾网页3种.垃圾网页降低了搜索引擎的搜索结果质量，也浪费了用户的时间，因此，有很多人研究检测垃圾网页的方法^[4].目前检测垃圾网页主要有2种方法：第1种是基于web图，根据页面有效性估计网页信任程度，从而识别出垃圾网页^[5-6]；第2种方法是基于网页内容和组件，属于分类和监督学习问题^[7-9]，一方面人们强调从网页中提取特征^[10-11]；另一方面，用一些性能较优的分类算法进行垃圾网页检测，属于数据不平衡分类中的典型问题. Singh T等^[12]提出了一个基于模糊逻辑的框架来检测web垃圾页面. Fdez-Glez J等^[13]提出了一个使用增量学习检测web垃圾网页的框架.此外，神经网络、深度学习、支持向量机等方法也被用来检测垃圾网页^[14-15].

在实际应用中，垃圾网页检测通常都会遇到类似数据量大、数据含不平衡类、高计算成本和内存消耗等问题.本研究将从不平衡数据和特征选择两方面入手研究：一方面通过重采样技术获得平衡数据集；另一方面通过降低特征空间的维度提高分类器的准确率.

1 相关工作 1.1 不平衡数据

在不平衡数据集中，每一类样本数据的分布都是不平衡的.在垃圾网页分类中，样本较多的一类是正常网页，较少的一类是垃圾网页.通常人们更关心的是样本少的那一类，例如垃圾网页检测.如果在分类过程中使用典型常用的分类器，分类结果往往会更加倾向于样本数多的一类，即少数类样本不容易被识别出来.因此要改变这种情况，就要设法使数据集样本均衡，在这基础之上对其分类.也有人根据其数据集的特征专门设计出适用于不平衡数据集的分类算法.

1.2 重采样

重采样指的是可以得到平衡数据集，使得样本分布均匀的一种技术，它可以用来减缓在模型训练过程中样本的不平衡问题，从而提高分类性能，且重采样是独立于所选分类器的，更加通用.重采样技术主要分为过采样技术和欠采样技术^[16].过采样技术指的是通过在数据集中增添少数类样本的方式来平衡数据集，其中最典型的方法就是简单地复制少数类样本.也有人提出少数类样本合成过采样技术(SMOTE, synthetic minority over-sampling technique)^[17]，它创造出了新的少数类样本，从而扩充了少数类样本的数量，这种方法如今也被很多人运用.欠采样指的是通过删掉部分多数类样本来达到平衡数据集的目的.其中最早被提出来的就是随机欠采样技术(RUS, random under-sampling)，在很多用来消除多数类样本的例子中都应用到了RUS.混合方法是过抽样技术与欠采样的结合.

1.3 特征选择和提取

在数据集不平衡的情景下，少数类样本很容易作为噪音被丢弃，但是如果删除了样本空间中不相关的特征，就会降低这一风险.通常，特征选择的目标是从整个特征空间中选择k个特征的子集，优化分类器的结果.

处理特征的第2种方法就是特征提取，将数据转为更低维的空间.特征选择与特征提取的区别在于特征提取是从原始特征使用功能映射创建新特征，特征选择是返回原始特征的子集.

1.4 分类算法

人们尝试构建一种分类算法，使其适用于不平衡数据集，比传统的分类器效果更好.通常有2个方向，分别是集成方法和对算法分类器的改进.本研究使用的是集成方法.

集成分类器就是一个多分类器系统，它将性能较优的几个基分类器进行组合，从而提高其分类效果^[18]，现在已成为解决类不平衡问题的常用方法.现在常用的方法有袋装算法(Bagging)、提升算法(Boosting)和混合集成(Bagging和Boosting混合).集成一般分为两类，分别为基于迭代的集成和基于并行的集成.

1) 基于迭代的集成. Boosting是集成学习中最常见且有效的方法.第一个被提出使用的Boosting算法就是自适应增强算法(Adaboost). Adaboost在使用时能够将更高的权重赋予给被分配到正确类的样本，使得之后的分类器更多关注于学习分类失败的这些样本.其他典型的迭代集成方法包括梯度增强决策树，基于进化算法的集成算法.

2) 基于并行的集成.基于并行的集成能够并行训练每个基分类器，主要有基于Bagging的集成、基于重采样的集成和基于特征选择的集成.其中，Bagging算法代表就是随机森林算法.并行集成具有节省时间和易于开发的优点，因此常被用来解决实际问题.

在实现迭代或是并行集成模型时，需要一个基分类器，它可以是支持向量机和决策树等任何经典模型.每种分类器都有自己的优缺点，要根据实际需求进行选择.

1.5 评价指标

对不平衡数据的处理在数据挖掘中一直是有难度的问题，尤其是以垃圾网页检测为首的二元分类问题.由于样本分布不均，分类过程中很容易将样本归为多数类，但是目标样本往往属于少数类.因此选择能够体现出分类效果好坏的评价指标尤为重要.

为了对数据集分类效果的好坏有一致的评价标准，本研究采用3个评价指标，分别是准确率、F₁测度和A_UC值.由于垃圾网页检测属于二元分类，其中，垃圾网页属于目标类.对于二元分类来说，样本分为正例与负例，构成混淆矩阵如表 1所示.其中T_P为被正确分类的正例数，F_P为被错分为正例的负例数，F_N为被错分为负例的正例数，T_N为被正确分类的负例数.

F₁测度值全面反映了整体的分类性能，而且对不平衡数据集的分类也有效果，其计算如式(1)所示.准确率即为被正确分类的样本数占所有样本数的比值，其计算如式(2)所示.人们经常用A_UC值来评价二元分类模型训练效果的好坏^[19]，A_UC评估的是分类器避免错误分类的能力，其计算如式(3)所示，A_UC值越大，分类效果越好.

$ {F_1} = \frac{{2{T_P}}}{{2{T_P} + {F_N} + {F_P}}} $

(1)

$ {A_{{\rm{ccuracy}}}} = \frac{{{T_P} + {T_N}}}{{{T_P} + {F_P} + {T_N} + {T_N}}} $

(2)

$ {A_{{\rm{UC}}}} = \frac{1}{2}\left( {\frac{{{T_P}}}{{{T_P} + {F_N}}} + \frac{{{T_N}}}{{{T_N} + {F_P}}}} \right) $

(3)

2 算法分析 2.1 随机混合采样

提出一种随机的欠采样与过采样结合的混合方法(RUOS, random under-over-sampling)对样本进行采样，得到一个平衡数据集，具体算法如下.

输入数据集，包含正常网页样本集N和垃圾网页样本集S；

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

1) 计算：

s=少数类样本个数

n=多数类样本个数

z=设定的n与s的比值

$ k = {\rm{round}}\left( {\frac{n}{{zs}}} \right) $

其中round为四舍五入操作.

2) 将N随机平均地分为k个样本子集N′₁, N′₂, …, N′_k，其中N′_i的样本个数约等于z倍的s；

3) 分别将N′_i与S组合为一个新的不平衡数据集，且N′_i的样本数与S的样本数比值为z:1；

4) 分别将N′_i与S组成的不平衡样本集通过SMOTE方法生成一个新的平衡数据集D′_i，打乱数据集内样本顺序；

5) 返回D′_i.

基于上述的RUOS方法得到了k个平衡数据集，然后就可以训练出多个分类器，使用简单投票法对多个分类器进行集成，得到一个新的集成分类器.

2.2 基于改进的遗传算法的特征选择

在遗传算法(GA，genetic algorithm)^[20]中，子代为最优特征子集，遗传产生子代的过程就是搜索最优特征子集的过程.每个个体由二进制位串表示，“1”表示选中该特征，“0”则未选中该特征，位串长度即为特征的总数.首先对种群进行初始化，种群包含若干个体，若没有达到最大迭代次数就进入迭代.在迭代过程中，先计算出种群中个体的适应值，根据适应值的大小来判断是否进入交配池形成父代子群.再根据交叉、变异概率进行交叉、变异操作，使种群保证其多样性.最终产生优异的子代.

具体算法如下.

1) 种群初始化：随机生成一个种群，这个种群中含m个个体.产生方式如下.

$ R = {\rm{round}}\left( {{\rm{rand}}\left( {m,g} \right)} \right) $

其中：R为种群，m为个体，g为特征的个数，rand(m, g)返回一个m行g列的矩阵，其中每个元素取值的范围都在[0, 1]区间中，使得得到的矩阵所有元素为0或1，从而返回m个个体，每个个体由g位的二进制位串组成.

2) 个体评价：遗传的过程就是迭代产生最优特征子集的过程，在本研究中使用F₁值来衡量分类器的效果，也代表种群中个体的适应值.其中，封装的分类器为基于混合采样的XGBoost算法.

个体适应值算法如下.

输入：训练集B，二进制位串Q，整数n代表n折交叉验证.

输出：F₁值.

① 根据Q表示的特征子集对训练集样本B投影，得到新的样本集B′，并且划分为多数类样本集M′与少数类样本集S′.

② 分别将M′与S′平均分为n等份，得到M′₁, M′₂, …, M′_n与S′₁, S′₂, …, S′_n，分别合并S′_i, M′_i(i=1, 2, …, n)，得到n个新的数据集N:N₁, …, N_n.

③ 对每一个N_i进行操作，将N_i作为测试集，N中其他的数据集作为训练集，对训练集进行混合采样，使用XGBoost进行训练，对N_i进行测试，得到N_i的分类结果.

④ 将每一个N_i的结果合并，得到整个样本集B′的分类结果，然后计算出F₁值.

经过上述计算得到每个位串的F₁值，即个体适应值.

3) 迭代设置：设种群的最大迭代次数为g_max，且令g=1；

4) 个体选择：所有个体按照适应值进行降序排序，选择前a个个体进入交配池形成父代，且每个个体进入交配池的数目按照下式计算.

$ {l_i} = \alpha \left( {a + 1 - i} \right) $

l_i表示第i个个体进入交配池的数目，α为乘数因子.进入交配池的个体总数目为∑ l_i，它们作为父代来产生新的个体.

5) 交叉算子：设置交叉概率，依据交叉概率进行父代个体交叉操作，且保证交叉后得到的个体不在父代种群中；

6) 变异算子：为了使种群保证其多样性，设置了变异概率，依据变异概率对个体进行随机变异操作，变异即二进制位串中由“0”变为“1”或者由“1”变为“0”，且保证变异后得到的个体不在父代种群中；

7) 父代种群生成新的子代，令g=g+1，跳到步骤4)进行新一轮迭代，直到g=g_max.

迭代后得到的子代即为最优特征子集.

2.3 极端梯度算法

本实验通过比较最终使用的是基于迭代的集成方法——极端梯度算法(XGBoost)^[21]，它是梯度下降树的高效实现，相比之下，它生成决策树时考虑了树的复杂度，准确性更高，在满足相同训练效果的情况下，XGBoost所需迭代次数更少，并且它可以多线程同时进行，运行速度更快.

XGBoost在目标函数中加上了正则化项，如式(4)所示，损失函数不仅用到了一阶导数，还使用了二阶导数，如式(5)所示.

$ L\left( \phi \right) = \sum\limits_i l \left( {{{\hat y}_i},{y_i}} \right) + \sum\limits_k \mathit{\Omega } \left( {{f_k}} \right) $

(4)

$ \begin{array}{*{20}{c}} {{\rm{where}}\;\mathit{\Omega }\left( {{f_k}} \right) = \gamma T + \frac{1}{2}\lambda {{\left\| \omega \right\|}^2}}\\ {{L^{(t)}} \cong \sum\limits_{i = 1}^n {\left[ {l\left( {{y_i},{{\hat y}^{(t - 1)}}} \right) + {g_i}{f_t}\left( {{x_i}} \right) + \frac{1}{2}{h_i}f_t^2\left( {{x_i}} \right)} \right]} + }\\ {\mathit{\Omega }\left( {{f_t}} \right)}\\ {{g_i} = {\partial _{\hat y\left( {t - 1} \right)}}l\left( {{y_i},{{\hat y}^{\left( {t - 1} \right)}}} \right)}\\ {{h_i} = \partial _{\hat y\left( {t - 1} \right)}^2l\left( {{y_i},{{\hat y}^{\left( {t - 1} \right)}}} \right)} \end{array} $

(5)

定义I_j={i|q(x_i)=j}为叶节点j的实例集，然后以扩展Ω的方式将损失函数改写为

$ {{\tilde L}^{(t)}} = \sum\limits_{j = 1}^T {\left[ {\left( {\sum\limits_{i \in {I_j}} {{g_j}} } \right){\omega _j} + \frac{1}{2}\left( {\sum\limits_{i \in {I_j}} {{h_j}} + \lambda } \right)\omega _j^2} \right]} + \gamma T $

(6)

叶节点j的最优权值ω_j^*计算式为

$ \omega _j^* = \frac{{\sum\limits_{i \in {I_j}} {{g_i}} }}{{\sum\limits_{i \in {I_j}} {{h_i}} + \lambda }} $

(7)

并且通过式(8)计算相应的最优值.

$ {{\tilde L}^{(t)}}(q) = - \frac{1}{2}\sum\limits_{j = 1}^T {\frac{{{{\left( {\sum\limits_{i \in {I_j}} {{g_i}} } \right)}^2}}}{{\sum\limits_{i \in {I_j}} {{h_i}} + \lambda }}} + \gamma T $

(8)

式(9)可以作为评分函数来衡量一个树结构的质量，类似于评价决策树的结构分数，只针对更大范围的目标函数推导出来.

通常不可能枚举所有的决策树结构，因此采用贪婪算法，从单个叶节点开始，迭代地向树添加分支，假设I_L和I_R分别是拆分后左右节点的实例集，令I=I_L∪I_R，则分割后的损失减少量如式(9).在实际中，这个公式通常用于评估分割后的候选项.

$ \begin{array}{*{20}{c}} {{L_{{\rm{split}}}} = \frac{1}{2}\left[ {\frac{{{{\left( {\sum\limits_{i \in {I_L}} {{g_i}} } \right)}^2}}}{{\sum\limits_{i \in {I_L}} {{h_i}} + \lambda }} + \frac{{{{\left( {\sum\limits_{i \in {I_R}} {{g_i}} } \right)}^2}}}{{\sum\limits_{i \in {I_R}} {{h_i}} + \lambda }} - } \right.}\\ {\left. {\frac{{{{\left( {\sum\limits_{i \in I} {{g_i}} } \right)}^2}}}{{\sum\limits_{i \in I} {{h_i}} + \lambda }}} \right] - \gamma } \end{array} $

(9)

3 实验 3.1 数据集

笔者采用的数据集为WEBSPAM-UK2006^[22]，这是由垃圾网页检测挑战赛和对抗性信息检索Web讨论组于2006年收集的公开资料集.该数据集数据丰富，已被多个研究团体采纳.垃圾网页数和正常网页数的比值表明，数据集是不平衡的.在这些数据中，以四组形式提供了277个特征，分别是基于内容的特征、基于链接的特征、转换后的基于链接的特征和基于邻接图的特征.

基于内容的特性主要关注的是web页面的内容，包括页面上的字数、标题中的字数、平均字数、压缩率和页面的熵等特性.在该数据集中，提取了96个基于内容的特征.基于链接的特性主要关注的是web页面中的链接，包括诸如页面输出链接的数量、进入页面链接的数量以及到内部页面的输出链接数量与总输出链接的比例等特性.在这个数据集中，提取了41个基于链接的特征.转换后的基于链接的功能包括简单的数值转换和基于链接的功能的组合.在这些特征中，可以看出基于链接的特征的对数和它们之间的比值.在这个数据集中，提取到138个特征.基于邻接图的特征是学习Stacked链接图得到的，共提取到2个特征.

3.2 不同分类算法的比较

为了比较几种分类器对垃圾网页检测数据集分类效果的优劣，本实验中使用不同的分类器进行实验，分别有决策树、随机森林、Adaboost和XGBoost.此时的数据集是不平衡数据集，交叉验证是5折，迭代次数是1 000.从表 3中可以看出，不论是F₁值，准确度还是A_UC值，XGBoost都比其他分类器的评估指标值高，效果更好，因此接下来的实验使用XGBoost作为分类器.

3.3 基于遗传算法的垃圾网页检测

本实验采用基于随机混合采样和遗传算法的集成分类方法，其中分类器为XGBoost，交叉验证为5折，迭代次数是1 000.混合采样中，z值取2.遗传算法中，依次选用3~20个最优个体，多次实验发现最优个体数为9，即最后得到的最优特征子集为9个.实验结果如表 4所示，从结果中可以看出，基于随机混合采样与遗传算法的分类器分类效果最佳，准确率与XGBoost算法相比提高了19.25%，说明了算法的有效性，通过随机采样与遗传迭代，能够获得平衡且特征数较少的数据集，从而提高分类器性能. 表 5为2007年垃圾网页挑战赛中优胜团队的结果，可以看出，在F₁值这个评价指标上笔者提出的算法是优于其他队伍的，但是在A_UC这个指标上较低，然而A_UC值最高的Cormack团队的F₁值仅为0.67，说明其分类效果并不好.

Singh S等^[23]提出了基于关联的特征选择和粒子群优化策略的分类器，其实验的数据集分别为基于内容、链接、内容和链接、完整内容和转换链接的特征集，并不是将所有的特征放在一起进行选择，其F₁值并不如RUOS+GA+XGBoost高. Scarselli F等^[24]提出了包含概率映射图自组织映射和图神经网络的图层叠架构技术.由于数据集具有不平衡的特点，样本很容易被分到多数类样本中，准确率并不是评价分类器好坏的最优指标，而其F₁值明显低于RUOS+GA+XGBoost，因此所提出的算法在F₁值这个评价指标上提升显著，而准确率却较低.说明所提算法还有改善的空间，下一步将进一步研究特征工程，将特征工程与遗传算法相结合，提高分类器的准确率.

4 结束语

垃圾网页检测是搜索引擎中的一大难题，具有数据不平衡、特征维度高的特点，为此提出一种基于随机混合采样和遗传算法的极端梯度集成分类算法.实验结果表明，这种算法能够获得平衡且特征空间维度更低的数据集，建立更简单符合逻辑的模型，并减少了建立学习模型的时间，提高了分类性能，是一种较好的分类算法.在未来的工作中，会进一步研究特征工程，将其与遗传算法结合进行迭代，提高算法准确率.由于使用的是现有数据集，怎样将其投入实际应用，实现实时检测也是今后研究的目标.此外，还可以考虑将该算法应用到其他有类似问题的领域中.