搜索引擎垃圾网页检测模型研究

贾志洋，夏幼明，高 炜，王勇刚

(1.云南大学旅游文化学院，云南 丽江 674100;2.云南师范大学信息学院，云南 昆明 650092)

随着互联网各种网页数量爆炸式增长，用户使用搜索引擎查找信息已经成为了最近几年信息检索的主要方式.大多数网站管理者都希望他们的网站在搜索引擎的搜索结果中排名靠前，很多的网站管理者会采取合理的搜索引擎优化技术(SEO)［1］，通过在网页中提供给用户更多、更有效的信息，以提升他们的网站在搜索引擎的搜索结果中的排名.而有些网站则通过一些“不道德”的方式来提升在搜索引擎的搜索结果中的排名.更有甚者，为了吸引访问量，手动或自动地制造一些网页.这些网页没有提供给用户任何有效信息.这些网页是直接针对搜索引擎的，但是在搜索引擎的搜索结果中获得了很高的排名，当用户查询某些关键词的时候，就有可能访问这些搜索引擎垃圾网页(Web Spam)［2］.

搜索引擎垃圾网页导致的主要后果为:搜索引擎检索结果质量下降，搜索引擎公司的资源的消耗和用户体验的降低.为解决数量日益增长的垃圾网页产生的各种问题，国内外学者对垃圾网页及垃圾网页检测都进行了深入的研究.为方便各国学者进行对比研究，Castillo C.等［3］组织志愿者收集整理了WEBSPAM-UK2006垃圾网页集.WEBSPAM-UK2006于2006年5月开始，收集了150 000个UK域名下的总计77 900 000个网页，其中的垃圾网页都由志愿者手工挑选出，提供给相关实验研究免费使用.大量的学者都使用WEBSPAM-UK2006作为其实验样本集.

1 垃圾网页常见检测模型

国内外的学者提出了各种基于机器学习的垃圾网页检测模型.大多数基于机器学习的垃圾网页检测模型都将垃圾网页的检测视为一个二元分类问题.它首先需要学习一个网页分类器，这个网页分类器可以预测网页的类别:正常网页或垃圾网页.其分类原理为:首先模拟搜索引擎的网络爬虫从Web爬行一定数量的网页，然后手工识别已下载的网页是否为垃圾网页.下载的网页集被划分为训练网页集和测试网页集，根据机器学习的算法，使用训练网页集学习分类器，然后使用分类器对测试网页集中的每一个网页进行分类预测，以测试分类器的分类效果［4］.

1.1 基于内容的垃圾网页检测模型

基于网页内容特征分析的垃圾网页检测模型主要针对采用了关键词堆砌技术的垃圾网页，其典型为Alexandros Ntoulas等［5］设计的垃圾网页检测模型.Alexandros Ntoulas等根据正常网页和垃圾网页的内容差别，对网页的内容特征进行了提取，统计了数据集中网页的语言相关和语言无关的各种内容特征，并根据统计结果分析可以作为构建网页分类器的内容特征.为了检测网页中是否采用了关键词堆砌等作弊技术，Alexandros Ntoulas等将数据集中的网页压缩并计算其被压缩前后所占空间大小的比值，这个比值被称为网页压缩率(Compression ratio)［5］，并计算了数据集中每个网页的压缩率，统计得出网页压缩率的分布如图1［5］.从图1中可以观察到，网页压缩率的分布服从正态分布，在2.0位置达到最高点，在压缩率大于4.0时，网页是垃圾网页的可能性大于70%，故网页压缩率为判定网页是否作弊的一个较好的特征.除了网页压缩率特征外，Alexandros Ntoulas等还统计分析了网页单词数量、标题单词数量、单词平均长度、链接数量、可视文本率、常用词出现率、n-gram相似度、网页URL长度等内容特征.根据提取的网页内容特征，然后将垃圾网页的检测看成一个二元分类问题，基于C4.5决策树算法通过训练网页集学习一个分类器，对测试网页集的网页的类别进行预测.由于忽略了网页之间的链接关系，这种基于网页内容的垃圾网页检测模型在检测关键词堆砌类型的垃圾网页时具有较好的效果，而对链接堆砌类型的垃圾网页检测效果则不佳，故此基于内容特征的垃圾网页检测模型的准确率有限.

图1 网页压缩率的分布与垃圾网页

1.2 基于链接结构的垃圾网页检测模型

大多数垃圾网页都采用了链接堆砌技术以提高其在搜索结果中的排名.基于链接结构的垃圾网页检测模型可以有效地检测此类垃圾网页.这类垃圾网页检测模型都基于某一个假设:正常网页只指向(被指向)正常网页或垃圾网页指向(被指向)垃圾网页.这类算法的原理都很类似，都是可信度(不可信度)传播算法，从一个已经标定为可信(垃圾)网页的集合开始(种子网页集)，通过可信度或不可信度传播的原则对所有的网页节点进行可信度和不可信度的计算，其中经典模型为可信度正向传播的TrustRank算法［6］.

1.2.1 TrustRank检测模型

TrustRank 模型是 PageRank［7］算法的一个变形，区别在于TrustRank算法从种子集合起始向其他网页传播可信度，而PageRank算法在全局根据链接信息进行 PageRank值的计算.TrustRank算法的前提假设是:“可信网页的链接所指向的网页通常也是可信网页”［6］.TrustRank算法分为两个步骤:

第一步，它根据逆向PageRank计算的数值向量，对所有节点进行从高到低的排序，挑选出一定数量的PR值较高的网页节点，形成种子集合，通过专家评测这些种子网页节点，把他们标记为垃圾网页(spam)和可信网页(reputable).经过人工评测后的种子集合才可以作为真正的种子集合被TrustRank所使用.所有选出的种子节点在评测后形成向量d，如公式(1)［6］所示.

第二步，为了利用PageRank的算法传播信任值，需要对d进行归一化操作，如公式(2)［6］所示.

然后将d替换为均一向量ln，利用同样的算法进行迭代计算，直至算法收敛，TrustRank的计算公式为［6］:

公式(3)中，t是TrustRank值向量，d偏向于在种子集中的可信网页，而在PageRank算法中随机跳转的向量元素皆为1/N.因为在网络中普通的链接并不都具有可信任性，而TrustRank中评测的可信网页所发出的链接常具有可信任性，进而比PageRank算法更加的可靠，因为它利用了人工评测的可信信息，并将这些信息通过链接结构进行传播.与PankRank算法类似，TrustRank的可信度进行可信度传播时采取了衰减和分裂策略，即距离种子网页越远(从链接的层次考虑)，其从种子网页获取到的可信度就越小.假如一个网页从种子网页集中的一个网页的出链接获取到可信度β，那么这个网页的出链接指向的网页可以从这个网页获取到可信度为β×β，这种策略称之为可信度衰减(Trust dampening)［6］.假如一个可信网页只有一个出链接，那么这个链接指向的网页应具有较高的可信度;相反，如果一个可信网页具有上百个出链接，那么这些链接中的某一个就可能指向垃圾网页.这是基于这样一个假设:“TrustRank算法在网页的可信度进行传播的时候将自身的可信度分裂(Trust splitting).［6］”

TrustRank可以有效地区分垃圾网页和可信网页，因为它使用了人工评测的信息(种子网页集)，这些信息不容易被垃圾网页(制造者)所影响.因此同PageRank相比，TrustRank通过种子集合和链接结构能够赋予可信网页较高的TrustRank值，而给作弊节点较低的TrustRank值，从而有效地检测作弊行为.但是TrustRank所依赖的种子集合的质量和数量会对它的算法性能产生影响.首先，如果种子网页集合的可信网页数量比较小，或者其中可信网页的比例比较小，根据TrustRank定义的衰减传播方法，种子网页集合对于其他网页的影响会较小，因此就失去了TrustRank算法的传播可信度的意义.此外，如果种子网页集合只隶属于少数的话题或者领域，TrustRank的排序结果会把没有出现的话题和领域的网页排名靠后，而提升那些同种子集中相同话题或领域的网页.再次，如果网页集合中的网页含有从可信网页到垃圾网页的链接，这样的种子集合也不适用于做种子网页，因为它们不符合可信网页指向可信网页的前提.TrustRank算法的效率会依赖于种子集合的质量和数量，若要较好地发挥TrustRank算法的垃圾网页检测效果，就要能保证找到一个合适的种子集合.此外，此类基于链接结构的迭代算法都具有类似的弱点，即忽略了网页本身的内容信息，而且会对部分垃圾网页造成误判.针对以上问题，Baoning Wu等［8］提出了Topical TrustRank算法，其主要思想是:首先使用主题信息将种子子集进行分类，然后针对每个主题单独计算可信度.这一算法克服了TrustRank的缺点.

1.2.2 类TrustRank检测模型

BadRank［9］与 Anti-TrustRank［10］检测模型十分类似，皆为不可信度的传播算法.以BadRank为例，BadRank基于这样一个假设:如果一个网页的一个出链接指向了一个BadRank值较高的网页，那么这个网页的BadRank值也应该较高.如图2［9］所示，与 PageRank 和 TrustRank不同，BadRank的值是反向传播的.BadRank的计算公式如(4)［9］式所示.

其中 BR(A)为网页 A的 BadRank值，BR(Ti)为网页A的出链接所指向的网页Ti的BadRank值，C(Ti)为网页Ti的入链接数，d为阻尼因数，E(A)为网页A的初始化BadRank值.

图2 BadRank不可信度反向传播示意图

既然网页的可信度可以表明网页是正常网页的可能性，网页的不可信度可以表明网页是垃圾网页的可能性，那么将网页的可信度和不可信度结合起来就是个很自然的想法.Wu Baoning［11］等给网页同时赋予 Trust与 DisTrust两个属性，并认为它们都可以在网页间传播(如图3［11］所示)，可信度(Trust)是正向传播的，而不可信度(Distrust)是反向传播的.算法最终使用可信度和不可信度两个特征的结合作为其是否为垃圾网页的最终判断标准，其判断公式如(5)［11］式所示，

其中，Total(i)表示网页i的可信度与不可信度的差异，TR(i)表示网页 i的可信度，DIS_TR(i)表示网页i的不可信度，η和β分别是两个权重系数(0＜η＜1，0＜β＜1).在试验中，Baoning Wu等令η=1-β，并测试了各种η取值对垃圾网页检测效果的影响.实验表明，当η=0.1时的垃圾网页检测效果最佳.

图3 结合可信度正向传播与不可信度反向传播的模型

1.3 结合内容特征和链接信息垃圾网页检测模型

由于基于内容特征的垃圾网页检测模型忽略了网页之间的链接关系，基于链接结构的垃圾网页检测模型又忽略了网页的内容特征，Gan Qingqing等［12］设计了基于网页内容特征的改进模型.此模型不但利用了网页的内容特征，而且根据网页之间的链接结构对检测结果进行了修正，其垃圾网页的检测效果明显好于基于网页内容特征的检测模型.此模型首先根据网页的内容特征和链接特征构建了基准分类器，然后根据网页的邻居结点网页的分类结果对网页的分类进行修正.Gan Qingqing等对网页的内容特征进行了提取，提取的特征包括:网页包含单词数量、网页内所有单词的平均长度、常用词出现率、可视文本率、网页标题长度、网页包含的超级链接数量、网页HTML源代码的压缩率等.除了网页的内容特征，Gan Qingqing等也提取了网页的链接特征(网站级别链接特征).提取的链接特征包括:网页的平均出链接数量、网页的平均入链接数量、入链接平均层次、出链接平均层次、网页的平均层次等特征.根据以上的内容特征和链接特征，使用C4.5决策树算法训练分类器，并对数据集中的网页的类别进行了分类预测.为进一步使用网页的链接结构信息，Gan Qingqing等根据分类器的分类结果，结合网页之间的链接信息对分类结果进行了修正.Gan Qingqing等统计分析了网页的邻居结点(指向网页的邻居结点)的垃圾网页比率，如果网页的邻居结点的邻居网页中的垃圾网页大于0.5，那么就将这个网页标号为垃圾网页.

虽然Gan Qingqing等的检测模型利用了网页之间的链接结构信息，但其检测准确率受基准分类器的分类效果影响较大，故垃圾网页的检测准确率的提高有限.

现有的基于内容特征的垃圾网页检测模型忽略了网页之间的链接关系，故笔者［13］构建了软间隔支持向量机分类器，以网页的内容特征作为支持向量，根据网页之间的链接具有相似性的特点定义了惩罚函数，使用样本集学习出了线性支持向量机网页分类器，并对分类器的分类效果进行了测试.实验结果表明，基于支持向量机的分类器的效果明显好于使用内容特征构建的决策树分类器.但此模型基于一个假设［13］:“正常网页的出链接只指向正常网页，正常网页的出链接几乎不指向垃圾网页.”，而且构建了线性支持向量机，其对于样本的分布的依赖性过强，分类效果稳定性不强.

1.4 其他检测模型

1)基于图挖掘的检测模型.Hiroo Saito等［14］将整个Web视为一个有向图，将其分解成强连通分支(Strongly Connected Component)，除了最大的强连通分支以外，其他的比较大的强连通分支基本上都是链接工厂(垃圾网页的一种)，根据图论的算法计算出较大团，并将它们作为垃圾网页种子集，然后将种子集继续扩充，直到得到最终的垃圾网页集.这种检测模型实际上还是对网页之间的链接结构进行分析挖掘，同样忽略了网页的内容信息，处理海量网页数据的效率较佳.

2)武磊等［15］从多个网络链接图中提取结构信息与时域信息，并且提出了一种将结构信息与时域信息结合起来的检测模型.武磊等使用了由某商业搜索引擎提供的从2006年3月至2006年6月连续4个月的网络链接图的抽样子图，每张子图均包含网站的URL以及网站之间的链接数等信息.根据对数据集中的网站数据进行统计分析，将网站分为三类，武磊等针对数据信息量的不同抽取不同数量的信息特征，并训练不同的分类器加以预测其类别.该检测模型的优点在于充分利用了垃圾网站的域名等信息变化比较频繁且与正常网站的变化具有较大的差别这一特点，能够比较好地检测大部分垃圾网页.但由于垃圾网站的变化规律不稳定，故此模型需要不间断地学习垃圾网站的域名等信息的变化规律以调整其网站分类方式.

3)清华大学的刘奕群等［16］通过对搜索引擎的用户访问日志进行了统计和分析，其数据集共收集了2007年7月1日至2007年8月26日之间，27.4亿人次在搜狗搜索引擎的8亿个网页访问记录和221 000万个用户会话(session).刘奕群等的研究基于这样一个假设:垃圾网页的内容对用户毫无价值，故此很少有用户主动直接访问垃圾网页，所以网页的访问量一般都是由搜索引擎而来.刘奕群等根据用户的访问记录统计分析了网站3种访问模式，第一种为网页来自搜索引擎的访问率(SEOV rate)，第二种为网页作为其他网页的来路率(SP)，第三种为用户在网站的网页访问量.通过这3种访问模式以学习训练其对垃圾网页的分类预测.

4)为了从另一个角度了解web的结构，Yang Haixuan等提出了一个名为DiffusionRank的检测模型［17］.DiffusionRank的思想来源于物理学中的热扩散现象.热内核(Heatkemel)［17］用来描述介质中一点从另外一点处所吸收到的热量.近来，热内核的思想被借鉴到诸如降维和分类等应用中.DiffusionRank算法把网页间的链接看作热量流动的管道，把Web上的活动看作热量的扩散，利用热内核解决Web网页排名问题.Yang Haixuan等的研究发现，DiffusionRank算法不仅具有检测垃圾网页的能力，而且还可以用来发现Web上关系密切的社区.

5)针对垃圾博客(splog)［18］，刘纬等［19］和Lin Yu-Ru等［20］根据垃圾博客和正常博客在统计特征上的差异，对多种针对博客分类有效的统计特征进行了分析，提出基于博客网页统计特征的过滤方法.

6)基于目的分析的垃圾网页分类方法.于佳慧［21］等人根据垃圾网页的作弊目的，将垃圾网页分成若干个热门的主题类别，以方便根据不同类别进行精确检测.

2 结语

基于内容特征的垃圾网页检测模型可以快速有效地检测早期的垃圾网页，但由于作弊技术的不断更新和改进，其垃圾网页检测效果有限，改进的余地较小.基于链接结构的垃圾网页检测模型仍旧是垃圾网页检测研究领域的主流，其可信度/不可信度的传播算法不易受到作弊者的影响，但种子网页集的选择为其瓶颈，也是今后的研究热点.基于内容和链接结构的垃圾网页检测模型利用了网页的链接信息，其垃圾网页检测效果明显要高于基于内容的垃圾网页检测模型，但其垃圾网页检测效果仍旧依赖于基于内容的垃圾网页检测模型.

垃圾网页检测的研究仍旧有很多问题待解决［22］，结合网页的链接结构和搜索引擎用户的使用与反馈信息的垃圾网页检测技术更具有实用前景.

［1］谭龙江.基于搜索引擎优化的网络宣传机模型［J］.计算机应用，2010，30(8):2232-2234.

［2］Zoltán Gyöngyi，Hector Garcia-Molina.Web spam taxonomy［M］.In Proceedings of the First International Workshop on Adversarial Information Retrieval on the Web，Chiba，Japan.New York:ACM，2005:39-48.

［3］Castillo C，Donato D，Becchetti L，et al.A reference collection forweb spam［J］.SIGIR Forum，2006，40(2):11-24.

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

［5］Alexandros Ntoulas，Marc Najork，Mark Manasse，etal.Detecting spam web pages through content analysis［M］.In Proceedings of the 15th International Conference on World Wide Web，Edinburgh，Scotland.New York:ACM，2006:83-92.

［6］Zoltán Gyöngyi，Hector Garcia-Molina，Jan Pedersen.Combating web spam with TrustRank［M］.In Proceedings of the 30st International Conference on Very Large Data Bases，Trondheim，Toronto，Canada.San Francisco:Morgan Kaufmann.，2004:576-583.

［7］Avier Ortega F，Craig Macdonald，Troyano JoséA，et al.spam detection with a content-based randomwalk algorithm［M］.Proceedings of the 2nd internationalworkshop on Search and mining user-generated contents，Toronto，Canada.New York:ACM，2010:45-51.

［8］Wu Bao-ning，Vinay Goel，Brian D Davison.Topical TrustRank:Using topicality to combat web spam［M］.In Proceedings of the 15th International World Wide Web Conference，Edinburgh，Scotland.New York:ACM，2006:63-72.

［9］Google.PR0-Google's PageRank 0 Penalty［J/OL］.2010-12-28(2011-03-21).http://pr.efactory.de/e-pr0.shtm l.

［10］Vijay Krishnan，RashmiRaj.Web spam detection with anti-trust rank［M］.In Proceedings of the Second International Workshop on Adversarial Information Retrieval on the Web，Washington，USA.New York:ACM，2006:37-43.

［11］Wu Baoning，Vinay Goel，Brian D D.Propagating trust and distrust to demote web spam［M］.In Proceedings of Models of Trust for the Web，Edinburgh，Scotland.New York:ACM，2006.

［12］Gan Qingqing，Torsten Suel.Improving web spam classifiers using link structure［M］.In Proceedings of the Third InternationalWorkshop on Adversarial Information Retrieval on the Web，Banff，Alberta，Cana-da.New York:ACM，2007:17-20.

［13］贾志洋，李伟伟，高炜，等.基于支持向量机的搜索引擎垃圾网页检测［J］.云南民族大学学报:自然科学版，2011，20(3):173-176.

［14］Hiroo Saito，Masashi Toyoda，Masaru Kitsuregawa，et al.A large-scale study of link spam detection by graph algorithms［M］.In Proceedings of the Third International Workshop on Adversarial Information Retrieval on the Web，Banff，Alberta，Canada.New York:ACM，2007:45-48.

［15］武磊，高斌，李京.基于结构信息和时域信息的垃圾网页检测技术［J］.计算机应用研究，2008，l25(4):57-60.

［16］Liu Yiqun，Cen Rongwei，Zhang Min，et al.Web Spam with user behavior analysis［M］.Proceedings os AIRWeb’08，Beijing，China，2008:108-110.

［17］Yang Haixuan，Irwin King，Michael R Lyu.Diffusion-Rank:a possible penicillin for web spamming［M］.In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval，Amsterdam，Netherlands.2007:431-438.

［18］Franco Salvetti，Nicolas Nicolov.Weblog classification for fast splog filtering:a URL languagemodel segmentation approach［M］.In Proceedings of the Human Language Technology Conference of the NAACL，New York，USA.Stroudsburg:Association for Computational Linguistics，2006:137-140.

［19］刘玮，廖祥文，许洪波，等.基于统计特征的垃圾博客过滤［J］. 中文信息学报，2008，22(6):86-91.

［20］Lin Yuru，Had Sundaram，Yun Chi.Splog detection using content，time and link structures［M］.In Proceedings of 2007 IEEE International Conference on Multimedia and Expo，Beijing，China.New York:IEEE，2007:2030-2033.

［21］余慧佳，刘奕群，张敏，等.基于目的分析的作弊页面分类［J］. 中文信息学报，2009，23(2):42-46.

［22］Hayati P，Potdar V.Toward Spam 2.0:an evaluation ofweb 2.0 anti-spam methods［M］.In Proceedings of the 7th IEEE International Conference on Industrial Informatics，Cardiff，Wales.New York:IEEE，2009:875-880.