基于支持向量机的搜索引擎垃圾网页检测研究

摘要: 搜索引擎垃圾网页作弊的检测问题一般被视为一个二元分类问题，基于机器学习的分类算法建立分类器，将网页分成正常网页和垃圾网页2类.现有的基于内容特征的垃圾网页检测模型忽略了网页之间的链接关系，故构建了软间隔支持向量机分类器，以网页的内容特征作为支持向量，根据网页之间的链接具有相似性的特点定义了惩罚函数，使用样本集学习,得出了线性支持向量机网页分类器，并对分类器的分类效果进行了测试.实验结果表明基于支持向量机的分类器的效果明显好于使用内容特征构建的决策树分类器.

关键词: 垃圾网页；垃圾网页检测；机器学习；网页分类；支持向量机

中图分类号:TP 391.3 文献标志码:A 文章编号:1672-8513(2011)03-0173-04

Study of the Web Spam Detection Based on the Support Vector Machine

JIA Zhiyang1,LI Weiwei2,GAO Wei3, XIA Youming3

(1. School of Tourism and Culture, Yunnan University,Lijiang 674100, China;2. Department of Computer Science, Ningde Vocational and Technical College, Ningde 352000, China;3. Department of Information, Yunnan Normal University, Kunming 650040, China)

Abstract: With the widespread application of search engines, some web pages often carry out cheating the search engines for the purpose of increasing rankings in the search results. These web pages are called web spam. The web spam detection problem is viewed as a classification problem, and that means classification models are created by machine learning classification algorithms, which include two categories: Normal and Spam. Contentbased classification models usually ignore the link structures of web pages. So the soft margin support vector machine classification model which takes the content features as the support vector has been developed by learning the sample set, and penalty functions are defined according to the links between web pages that seems to have similar characteristics. The classification effect of the model is also studied. The experimental results have showed that the effect of the support vector machinebased classifier is significantly better than the decision tree classifier built by content features.

Key words: web spam; web spam detection; machine learning; web page classification; support vector machine

研究显示，大多数用户在查看搜索引擎返回的结果时，一般不会超过3页［1］.很多的网站管理者会通过提高网站质量和更新频率等搜索引擎优化（SEO）［2］手段提升网站在搜索引擎搜索结果中的排名.而有些网站则通过一些“不道德”的方式来提升在搜索引擎的搜索结果中的排名，如“手动”或“自动”地制造一些网页，这些网页没有提供给用户任何有效的信息，是直接针对搜索引擎的，却在搜索引擎的搜索结果中获得了较高的排名，当用户查询某些关键词的时候，就有可能访问这些搜索引擎垃圾网页（又称垃圾网页或作弊网页）［3］.垃圾网页的目标是吸引搜索引擎的用户访问某些搜索结果中列出的网页链接，故此垃圾网页的制造者希望通过在搜索的搜索结果里进行作弊以骗取用户的点击.

虽然人工可以识别出垃圾网页，但是由于搜索引擎索引网页数量巨大，手工识别将会产生巨大的费用和时间.故此构造一个机器自动识别或者人工少量参与的半自动识别系统将会很好地解决这一问题，国内外的学者提出了各种基于机器学习的检测模型.大多数基于机器学习的检测方法将垃圾网页的检测视为一个二元分类问题，首先需要学习出一个网页分类器，这个网页分类器可以预测网页的类别：正常网页或垃圾网页.首先模拟搜索引擎的网络爬虫从Web中抓取一定数量的网页并手工识别已下载的网页是否为垃圾网页.下载的网页集被划分为训练网页集和测试网页集，根据机器学习的算法，使用训练网页集学习分类器，然后使用分类器对测试网页集对所有网页进行分类预测以测试分类器的分类效果.

网页内容与查询关键词的匹配程度通常被作为网页排名的关键因素，垃圾网页通过堆积大量流行关键词，从而达到与更多的网页匹配的目的，或者通过大量重复堆积某些热门关键词，从而达到与这些关键词的高度匹配的目的.基于网页内容特征分析的检测模型设计的目标就是检测此类垃圾网页，Alexandros Ntoulas等［4］将垃圾网页的检测看成一个二元分类问题，通过训练一个分类器，将测试集中的网页分成“正常网页”和“垃圾网页”2个类别，根据网页内容进行分析和特征的提取，使用C4.5决策树算法构建网页分类器.这种基于网页内容的垃圾网页检测的模型在检测“关键词堆积”类型的垃圾网页时具有较好的效果，而对“链接堆积”类型的垃圾网页检测效果则不佳，由于忽略了网页之间的链接关系，故此基于内容的垃圾网页检测准确率有限.

为了改进基于内容特征分析的垃圾网页检测模型没有利用网页之间的链接结构的缺点，本文首先提取了网页的内容特征，并根据内容特征向量设计了线性支持向量机，为了充分利用网页之间的链接信息，根据相互链接的网页之间的相似性这一特点定义了惩罚函数，构造了软间隔支持向量机分类器，并针对已构建的实验网页集对分类器的垃圾网页检测效果并进行了分类测试.

1 分类器的构建

网络爬虫是搜索引擎中非常重要的一部分，垃圾网页的检测一般是在搜索引擎抓取网页之后，建立索引之前的工作，故本文需要模拟搜索引擎的网络爬行［5］，抓取大量网页，从而构建试验数据集.为了设计和评估本文的垃圾网页检测算法，基于尽可能选用Web中的“随机样本”以及网页在相关搜索结果排名靠前的原则，本文以广度优先的爬行策略，于2010年4月抓取了较具代表性的137640个中文网页.通过人工判别，数据集中共有垃圾网页9634个(7%)，正常网页128006个(93%).

虽然垃圾网页与正常网页在视觉效果上具有明显差别，但是难以根据视觉特征进行检测.因此，本文根据网页内容，分析、提取垃圾网页的特征，并结合网页之间的链接关系构造一个线性支持向量机分类器，把垃圾网页的检测视为二元分类问题，学习出的分类器可以预测网页的类别.

1.1 网页内容特征的提取

为了检测网页是否采取了“关键词堆积”的作弊技术，在网页的内容特征提取阶段，普遍根据垃圾网页特点提取了特征，诸如常用词出现率、网页压缩率、网页长度，网页标题长度、网页URL长度等等特征［6］.本文提取了网页标题长度、网页压缩率、网页“”标签数量与长度、网页URL长度、网页长度、停用词与标点符号使用率、常用词出现率、可视文本率、基于知网的网页主题与网页正文相关度等基于内容分析的特征.

1.2 基于软间隔的线性支持向量机的分类器

支持向量机(SVM)已经成为一种应用广泛的分类技术.根据已经选取的网页的内容特征，可以基于支持向量机建立一个分类器，学习到支持向量机的最优分类面，最优分类面不但能将2类正确分开，即训练错误率为0，并且分类间隔最大.但是正常网页与垃圾网页分类问题一般为线性不可分的情况，针对这种情况可以采用2种方法构造支持向量机，一种方法是将线性SVM拓展为软间隔分类器(Soft Margin Classifier)［7］，另一种方法是构造非线性的SVM.前者通过引入松弛因子，允许分类错误；后者通过核函数将一个非线性问题转化为高维特征空间的线性问题.

本文主要讨论线性不可分的情况下，通过引入松弛因子，构造软间隔分类器.假设要学习出一个线性分类器f(x)=w•x，其目标函数为：

Ω(w)=1l∑R(w•xi,yi)+λw•w .[JY](1)

式(1)中的λ为参数，目标函数用来保证w能够正确对训练集中的样本进行分类，同时保证分类间隔最大.本文采用Hinge损失函数R(u,y)=max(0,1-uy)来表示训练集的损失［8］，还需要加入某些凸损失函数，w•w代表分类间隔.式(1)也可以写成：

min∑mi=1ξi+λmw2,

st.yi(w,xi)≥1－ξii=1,…,mξ≥0.[JY](2)

对网页的分类问题来说，网页之间的链接关系包含了一些对分类有用的信息.网页之间的链接可以视作有向图的边，数据集中所有网页的链接结构就可以用一个边集合E来表示.网页之间的链接结构是不能被忽略的，至少它们表示了链接起来的网页之间具有一定的相似性这一信息，基于这样的假设，可以在目标函数中加入一个额外的正则化因子：

Ω(w)=1l∑li=1R(w•xi,yi)+λw•w+γ∑(i,j)∈EαijΦ(w•xi,w•xj)，[JY](3)

其中αij为网页i指向网页j的链接的权重，公式(3)中的前2项为1个标准的具有正则化因子的支持向量机的目标函数，第3项为新加入的正则化因子，函数Φ表示惩罚函数，本文的惩罚函数与网页的链接结构有关.公式(1)，(2)，(3)已经被Zhang等［9］证明，其中惩罚函数Φ为：

Φ(u,v)=(u－v)2.[JY](4)

公式(4)表示相互链接的网页之间有一定的相似性，Zhang等采用公式(3),(4)构建网页分类器.本文主要针对垃圾网页的检测问题［10］，将网页视作图中的结点，网页之间的链接视作图中的边，整个链接结构视作一个“非对称图”，只考虑网页中的出链接，这样考虑是因为垃圾网页经常指向正常网页，而正常网页几乎不指向垃圾网页.即可以假定：正常网页的出链接只指向正常网页，正常网页的出链接几乎不指向垃圾网页.本文将惩罚函数Φ改进为：

Φ(u,v)=max(0,v－u).[JY](5)

如果特征空间不丰富的话，可能学习出来的分类器会不够灵活，为此可加入一个变量zi，对每一个网页结点i学习出一个分类器 ，这个新加入的变量可以视作额外的松弛因子，使得学习出来的分类器更具有灵活性，目标函数就变化为：

Ω(w)=1l∑li=1R(w•xi,yi)+λ1w•w+λ2z•z+γ∑(i,j)∈EαijΦ(w•xi,w•xj).[JY](6)

公式(6)中引入2个正则化因子λ1和λ2用来控制w和z的值.

因为目标函数是凸函数，那么就需要对目标函数进行优化，即优化w和z，使w和z最小(在目标函数的约束条件下)，这个优化过程为：运行回归算法求w的最小值；在图上运行迭代增殖算法计算z的最小值.

对每对网页结点i和j，在使用支持向量机算法预测其类别前，应先计算得出所有网页的可信度，并将这些可信度存储起来，以计算其正则化因子的值.假设已经计算出网页i的可信度fi，网页j的可信度fj，，可信度越高表示网页为正常网页的可能性就越大，而可信度越低表示网页为垃圾网页的可能性就越大.那么本文将惩罚函数Φ定义为：

Φsqrt(fi,fj)=fi－fj .[JY](7)

Φ+sqrt(fi,fj)=max(0,fi－fj) .[JY](8)

惩罚函数Φ表示网页i的指向的网页j的出链接是否正常，在理想的状态下如果正常的话就是Φ(fi,fj)的值应为0，此时网页i和网页j的fi，fj值应该相等，表示相互链接的网页的可信度相等，即垃圾网页出链接指向的网页也应是垃圾网页，正常网页出链接指向的也应是正常网页，相互链接的网页之间的可信度应该相同.但实际情况是，由于误差等原因，相互链接的网页的可信度差异较大，公式(7)惩罚那些可信度不一致的网页，公式(8)只对满足这样条件的网页进行惩罚：网页i的出链接所指向的网页j的可信度低于网页i；即如果一个网页i指向了一个可信度比自己低的网页j，那么相应地对网页i的这个链接进行惩罚.

公式(7)、(8)都具有一定的弱点，那么结合公式(7)、(8)，可以定义一个更具有灵活性的惩罚函数：

Φα(a,b)=αΦsqrt(a,b)+(1－α)Φ+sqrt(a,b)，[JY](9)

式中α为一个调整因子，α∈［0，1］，当α为0时公式(9)退化成公式(8)，当α为1时公式退化成公式(7)，本文令α=0.5.

1.3 垃圾网页可信度迭代计算模型

网页的可信度需在训练支持向量机之前计算得出，以便为图正则化使用，这个计算算法为迭代算法，通过数据集中的所有网页的链接结构进行计算.

已知数据集中的部分网页的类标号(垃圾网页、正常网页)，而一部分网页的类标号未知，数据集中网页之间的相互链接结构是已知的.公式(10)就是通过多次迭代以计算网页数据集中所有网页可信度模型：

Trust(p)=(1－d)E(A)+d∑TiATrust(Ti)C(Ti)，[JY](10)

式中Ti表示指向某个网页p的网页，C(Ti)表示网页Ti的链接数量，d为阻尼系数，Trust(p)为网页p的可信度.通过公式(10)可以发现：网页p的可信度是由指向p的网页的可信度所决定的，这个过程可以通过多次迭代运算出来.数据集中的部分网页的类标号是已知的，可以根据已知的类标号对部分网页的可信度赋初值（垃圾网页的可信度为0，正常网页的可信度为1），然后通过多次迭代计算出每个网页的可信度，可信度为的值分布在区间［0,1］，可信度为0时表示此网页为垃圾网页，可信度为1时表示此网页为正常网页，通过迭代计算得出的网页可信度一般趋近0或1.

2 实验与结果分析

本文的模型由2个部分组成，第1部分使用可信度迭代模型计算出数据集中所有网页的可信度，计算得出的可信度越小表示此网页为垃圾网页的可能性越大，可信度越大表示这个网页为正常网页可能性就越大，这些计算得出的可信度主要为第2部分的支持向量机使用；第2部分为训练基于支持向量机的分类器，使用数据集中的训练数据训练基于软间隔的支持向量机分类器，其中支持向量为已经提取的网页的各种内容特征，如网页的常用词使用率、网页压缩率、网页正文与网页标题的相关性等特征，正则化函数为本文提出的基于网页链接结构的惩罚函数Φ(fi,fj)，用来修正支持向量机的分类错误.这样网页的内容特征作为支持向量，同时网页之间的链接结构信息也得到了利用.

为了测试模型的分类效果，本文分别使用基于网页内容的决策树分类器和本文的利用了网页间的链接信息的基于SVM的分类器，其分类效果如表1所示.

实验结果表明基于SVM的分类器的效果则明显好于使用内容特征构建的决策树分类器，这与本文的初衷基本吻合，即结合了网页的内容特征和网页之间的链接结构信息的检测模型能够获得相对较好的检测结果.

参考文献:

［1］EIRON N, MCCURLEY K S. Analysis of anchor text for web search［C］ // Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval. July 28 - August 1, 2003, Toronto, Canada.New York:ACM,2003:459-460.

［2］王利刚,赵政文,赵鑫鑫.搜索引擎中的反SEO作弊研究［J］.计算机应用研究,2009,26(6):2035-2037.

［3］GYNGYI Z, GARCIA-MOLINA H. Web spam taxonomy［C］ //Proceedings of the First International Workshop on Adversarial Information Retrieval on the Web.May 10-14,2005,Chiba,Japan.2005:39-48.

［4］NTOULAS A, NAJORK M, MANASSE M, et al. Detecting Spam Web Pages through Content Analysis［C］//Proceedings of the 15th International Conference on World Wide Web.May 22 - 26, 2006,Edinburgh, Scotland, UK. New York:ACM,2006:83-92.

［5］贾志洋,李伟伟,张海燕.基于内容的搜索引擎垃圾网页检测［J］.计算机应用与软件,2009,26(11):165-167.

［6］祝伟华,刘期勇.基于具有用户权限的全文检索系统的应用［J］.云南民族大学学报:自然科学版,2009,18(1):73-76.

［7］徐启华,杨瑞.一种新的软间隔支持向量机分类算法［J］.计算机工程与设计,2005,26(9):2316-2318.

［8］CHEN Dirong, WU Qiang, YING Yiming. Support vector machine soft margin classifiers: Error analysis［J］.The Journal of Machine Learning Research, 2004, 12(5):1143-1175.

［9］ZHANG Tong, POPESCUL A,DOM B. Linear prediction models with graph regularization for web-page categorization［C］ //Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining.August 20 - 23, 2006,Philadelphia, USA. New York:ACM,2006:821-826.[ZK)]

［10］[ZK(#]ABERNETHY J, CHAPELLE O, CASTILLO C. Graph regularization methods for Web spam detection［J］. Machine Learning, 2010, 81(2):207-225.

收稿日期:2010-12-12.

基金项目:国家自然科学基金 (60903131)；云南省教育厅科学研究基金（2010Y108）.

作者简介:贾志洋(1980-),男,硕士,讲师.主要研究方向:网络信息挖掘.