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

第 20 卷 第 3 期 2011 年 5 月 云南民族大学学报(自然科学版) Journal of Yunnan University of Nationalities(Natural Sciences Edition) Vol． 20 No． 3 May 2011 收稿日期:2010 － 12 － 12． 基金项目:国家自然科学基金 (60903131) ;云南省教育厅科学研究基金(2010Y108)． 作者简介:贾志洋(1980 －) ，男，硕士，讲师．主要研究方向:网络信息挖掘． doi:10． 3969 / j． issn． 1672 － 8513． 2011． 03． 004 基于支持向量机的搜索引擎垃圾网页检测研究 贾志洋1，李伟伟2，高 炜3，夏幼明3 (1． 云南大学 旅游文化学院，云南 丽江 674100;2． 宁德职业技术学院 计算机科学系， 福建 宁德 352000;3． 云南师范大学 信息学院，云南 昆明 650040) 摘要:搜索引擎垃圾网页作弊的检测问题一般被视为一个二元分类问题，基于机器学习的分类 算法建立分类器，将网页分成正常网页和垃圾网页 2 类．现有的基于特征的垃圾网页检测模 型忽略了网页之间的链接关系，故构建了软间隔支持向量机分类器，以网页的内容特征作为支持 向量，根据网页之间的链接具有相似性的特点定义了惩罚函数，使用样本集学习，得出了线性支 持向量机网页分类器，并对分类器的分类效果进行了测试．实验结果表明基于支持向量机的分类 器的效果明显好于使用内容特征构建的决策树分类器． 关键词:垃圾网页;垃圾网页检测;机器学习;网页分类;支持向量机 中图分类号:TP 391． 3 文献标志码:A 文章编号:1672 － 8513(2011)03 － 0173 － 04 Study of the Web Spam Detection Based on the Support Vector Machine JIA Zhi-yang1，LI Wei-wei2，GAO Wei3，XIA You-ming3 (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 en- gines 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 ma- chine learning classification algorithms，which include two categories:Normal and Spam． Content-based 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 classifi- cation effect of the model is also studied． The experimental results have showed that the effect of the support vector machine-based 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中抓取一定数量的网页并手工识别已 下载的网页是否为垃圾网页． 下载的网页集被划分 为训练网页集和测试网页集，根据机器学习的算法， 使用训练网页集学习分类器，然后使用分类器对测 试网页集对所有网页进行分类预测以测试分类器的 分类效果． 网页内容与查询关键词的匹配程度通常被作为 网页排名的关键因素，垃圾网页通过堆积大量流行 关键词，从而达到与更多的网页匹配的目的，或者通 过大量重复堆积某些热门关键词，从而达到与这些 关键词的高度匹配的目的． 基于网页内容特征分析 的检测模型的目标就是检测此类垃圾网页，Al- exandros Ntoulas等［4］将垃圾网页的检测看成一个二 元分类问题，通过训练一个分类器，将测试集中的网 页分成“正常网页”和“垃圾网页”2 个类别，根据网 页内容进行分析和特征的提取，使用 C4． 5 决策树 算法构建网页分类器． 这种基于网页内容的垃圾网 页检测的模型在检测“关键词堆积”类型的垃圾网 页时具有较好的效果，而对“链接堆积”类型的垃圾 网页检测效果则不佳，由于忽略了网页之间的链接 关系，故此基于内容的垃圾网页检测准确率有限． 为了改进基于内容特征分析的垃圾网页检测模 型没有利用网页之间的链接结构的缺点，本文首先 提取了网页的内容特征，并根据内容特征向量设计 了线性支持向量机，为了充分利用网页之间的链接 信息，根据相互链接的网页之间的相似性这一特点 定义了惩罚函数，构造了软间隔支持向量机分类器， 并针对已构建的实验网页集对分类器的垃圾网页检 测效果并进行了分类测试． 1 分类器的构建 网络爬虫是搜索引擎中非常重要的一部分，垃 圾网页的检测一般是在搜索引擎抓取网页之后，建 立索引之前的工作，故本文需要模拟搜索引擎的网 络爬行［5］，抓取大量网页，从而构建试验数据集． 为 了设计和评估本文的垃圾网页检测算法，基于尽可 能选用 Web中的“随机样本”以及网页在相关搜索 结果排名靠前的原则，本文以广度优先的爬行策略， 于 2010 年 4 月抓取了较具代表性的 137 640 个中文 网页．通过人工判别，数据集中共有垃圾网页 9 634 个(7%) ，正常网页 128 006 个(93%)． 虽然垃圾网页与正常网页在视觉效果上具有明 显差别，但是难以根据视觉特征进行检测． 因此，本 文根据网页内容，分析、提取垃圾网页的特征，并结 合网页之间的链接关系构造一个线性支持向量机分 类器，把垃圾网页的检测视为二元分类问题，学习出 的分类器可以预测网页的类别． 1. 1 网页内容特征的提取 为了检测网页是否采取了“关键词堆积”的作 弊技术，在网页的内容特征提取阶段，普遍根据垃圾 网页特点提取了特征，诸如常用词出现率、网页压缩 率、网页长度，网页标题长度、网页 URL长度等等特 征［6］．本文提取了网页标题长度、网页压缩率、网页 “＜ META ＞”标签数量与长度、网页 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 ． (1) 式(1)中的 λ 为参数，目标函数用来保证 w 能 够正确对训练集中的样本进行分类，同时保证分类 471 云南民族大学学报(自然科学版) 第 20 卷 间隔最大． 本文采用 Hinge 损失函数 R(u，y) = max(0，1 － uy)来表示训练集的损失［8］，还需要加 入某些凸损失函数，w·w代表分类间隔．式(1)也可 以写成: min∑ m i = 1 ξi + λm w 2， st． yi(w，xi)≥ 1 － ξi i = 1，…，m ξ≥  0 ． (2) 对网页的分类问题来说，网页之间的链接关 系包含了一些对分类有用的信息． 网页之间的链 接可以视作有向图的边，数据集中所有网页的链 接结构就可以用一个边集合E来表示．网页之间的 链接结构是不能被忽略的，至少它们表示了链接 起来的网页之间具有一定的相似性这一信息，基 于这样的假设，可以在目标函数中加入一个额外 的正则化因子: Ω(w) = 1l∑ l i = 1 R(w · xi，yi) + λw · w + γ∑ (i，j)∈E αijΦ(w·xi，w·xj) ， (3) 其中 αij 为网页 i指向网页 j的链接的权重，公式(3) 中的前 2 项为 1 个标准的具有正则化因子的支持向 量机的目标函数，第 3 项为新加入的正则化因子，函 数 Φ表示惩罚函数，本文的惩罚函数与网页的链接 结构有关．公式(1) ，(2) ，(3)已经被 Zhang等［9］证 明，其中惩罚函数 Φ为: Φ(u，v)= (u － v)2 ． (4) 公式(4)表示相互链接的网页之间有一定的相 似性，Zhang等采用公式(3) ，(4)构建网页分类器． 本文主要针对垃圾网页的检测问题［10］，将网页视作 图中的结点，网页之间的链接视作图中的边，整个链 接结构视作一个“非对称图”，只考虑网页中的出链 接，这样考虑是因为垃圾网页经常指向正常网页，而 正常网页几乎不指向垃圾网页．即可以假定:正常网 页的出链接只指向正常网页，正常网页的出链接几 乎不指向垃圾网页．本文将惩罚函数 Φ改进为: Φ(u，v)= max(0，v － u槡 )． (5) 如果特征空间不丰富的话，可能学习出来的分 类器会不够灵活，为此可加入一个变量 zi，对每一个 网页结点 i学习出一个分类器 ，这个新加入的变量 可以视作额外的松弛因子，使得学习出来的分类器 更具有灵活性，目标函数就变化为: Ω(w)= 1l∑ l i =1 R(w·xi，yi)+ λ1w·w + λ2z·z + γ∑ (i，j)∈E αijΦ(w·xi，w·xj)． (6) 公式(6)中引入 2 个正则化因子 λ1 和 λ2 用来 控制 w和 z的值． 因为目标函数是凸函数，那么就需要对目标函 数进行优化，即优化 w和 z，使 w和 z最小(在目标函 数的约束条件下) ，这个优化过程为:运行回归算法 求w的最小值;在图上运行迭代增殖算法计算 z的最 小值． 对每对网页结点 i和 j，在使用支持向量机算法 预测其类别前，应先计算得出所有网页的可信度，并 将这些可信度存储起来，以计算其正则化因子的值． 假设已经计算出网页 i的可信度 fi，网页 j的可信度 fj，，可信度越高表示网页为正常网页的可能性就越 大，而可信度越低表示网页为垃圾网页的可能性就 越大．那么本文将惩罚函数 Φ定义为: Φsqrt(fi，fj)= fi － f槡 j ． (7) Φ +sqrt(fi，fj)= max(0，fi － fj槡 )． (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)， (9) 式中α为一个调整因子，α∈［0，1］，当α为0时公式 (9)退化成公式(8) ，当 α 为 1 时公式退化成公式 (7) ，本文令 α = 0. 5． 1. 3 垃圾网页可信度迭代计算模型 网页的可信度需在训练支持向量机之前计算得 出，以便为图正则化使用，这个计算算法为迭代算 法，通过数据集中的所有网页的链接结构进行计算． 已知数据集中的部分网页的类标号(垃圾网 页、正常网页) ，而一部分网页的类标号未知，数据 571第 3 期 贾志洋，李伟伟，高 炜，等:基于支持向量机的搜索引擎垃圾网页检测研究 集中网页之间的相互链接结构是已知的． 公式(10) 就是通过多次迭代以计算网页数据集中所有网页可 信度模型: Trust(p)= (1 － d)E(A)+ d∑ Ti→A Trust(Ti) C(Ti) ，(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) ，用来修正支持向量机的分类错误．这 样网页的内容特征作为支持向量，同时网页之间的 链接结构信息也得到了利用． 表 1 基于决策树的分类器与基于 SVM 的分类器的分类效果比较 分类器 网页类别 准确率 召回率 F1 值 基于决策 树分类器 正常网页 0. 991 0. 994 0. 993 基于决策 树分类器 垃圾网页 0. 903 0. 816 0. 857 基于 SVM 分类器 正常网页 0. 993 0. 995 0. 994 基于 SVM 分类器 垃圾网页 0. 912 0. 906 0. 909 为了测试模型的分类效果，本文分别使用基于网 页内容的决策树分类器和本文的利用了网页间的链接 信息的基于 SVM的分类器，其分类效果如表 1所示． 实验结果表明基于 SVM 的分类器的效果则明 显好于使用内容特征构建的决策树分类器，这与本 文的初衷基本吻合，即结合了网页的内容特征和网 页之间的链接结构信息的检测模型能够获得相对较 好的检测结果． 参考文献: ［1］ EIRON N，MCCURLEY K S． Analysis of anchor text for web search［C］ / / Proceedings of the 26th annual interna- tional ACM SIGIR conference on Research and develop- ment in information retrieval． July 28 － August 1，2003， Toronto，Canada． New York:ACM，2003:459 － 460． ［2］王利刚，赵政文，赵鑫鑫． 搜索引擎中的反 SEO 作弊研 究［J］．计算机应用研究，2009，26(6) :2 035 － 2 037． ［3］ GYNGYI Z，GARCIA － MOLINA H． Web spam taxono- my［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． Detec- ting Spam Web Pages through Content Analysis［C］/ /Pro- ceedings 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］祝伟华，刘期勇．基于 Lucene． Net具有用户权限的全文 检索系统的应用［J］．云南民族大学学报:自然科学版， 2009，18(1) :73 － 76． ［7］徐启华，杨瑞． 一种新的软间隔支持向量机分类算法 ［J］．计算机工程与设计，2005，26(9) :2 316 － 2 318． ［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) : 1 143 － 1 175 ． ［9］ ZHANG Tong，POPESCUL A，DOM B． Linear prediction models with graph regularization for web － page categoriza- tion［C］ / /Proceedings of the 12th ACM SIGKDD interna- tional conference on Knowledge discovery and data mining． August 20 － 23，2006，Philadelphia，USA． New York: ACM，2006:821 － 826． ［10］ ABERNETHY J，CHAPELLE O，CASTILLO C． Graph regularization methods for Web spam detection［J］． Ma- chine Learning，2010，81(2) :207 － 225． (编辑 庄红林) 671 云南民族大学学报(自然科学版) 第 20 卷