反Link Spam的算法策略研究

VIP免费
3.0 牛悦 2024-11-19 6 4 2.44MB 65 页 15积分
侵权投诉
i
摘要
互联网自出现以来，经过短短几年已经发展成为一个巨大的全球化信息空间，
网络用户的信息定位成本也急剧提高。搜索引擎出现并迅速发展成为互联网的入
口，网络信息检索的重要工具。搜索结果的排序中蕴含的利润，使得 SPAM（搜索
引擎作弊行为）出现并成为了搜索引擎的巨大挑战，
SPAM 浪费了巨大的信息资源，
更为严重的是影响了信息定位的效果。
文章简述了搜索引擎常用的算法，指出了其中可能被作弊者利用的地方。在分
类的基础上简单介绍了一些常用的作弊方式。对于这些问题网站的处理目前都是
加以人工参与，这种方式准确率高，但是成本也很高，不能推广，无法批量处理。
这在海里信息的今天己经成为成为了瓶颈，这使得研究高效的作弊行为处理机制
和算法成为必然。本文的内容主要是针对其中的链接类型的作弊行为，研究并提
出成套的解决方案。
笔者首先分析了 Link Farm 各种连接模式的最有化结构，并分析得出站点水平
的最优化结构特征。在结构分析的基础上，笔者提出了站点粒度挖掘作弊社区的
方法，并在社区的范围内，提出了以主题信息的异常，页面入度的异常判别等算
法来发现作弊社区以及作弊目标页面。在页面粒度上的处理过程中，本文在分析
原有可信度算法的基础上，针对算法有效利用范围小，惩罚过程出现无辜显现等
问题，提出了基于时间的可信度算法，并整合了权威度与可信度共同对页面的质
量进行量化。针对 SPAM 处理过程中页面抓取与判别工作量巨大的问题，笔者提
出了将增量搜索的技术与 SPAM 判别相结合的方案。
笔者利用搜狗实验室提供的数据对本文提出的算法策略进行了本地索引与实
验验证，实验结果显示降级 SPAM 页面效果良好。
关键词：搜索引擎、Link Spam、Link Farm、可信度
ii
ABSTRACT
Internet has already become an enormous globalization information space through a
few years. The cost for users to locate useful information is increasing rapidly. Search
Engine appeared and turned out to be the gateway of web and one important
information search tool. The profit buried in search engine result rank draw spammers
to make spam be the challenge that search engine needs to dell with. SPAM wastes huge
information resources and make the effect of locating information worse.
This article firstly briefs on the search engine commonly used algorithm, and presents
the possibly classified way used by spammer. To the processing of these problem
websites currently all is take into artificial to participate, this method accuracy is high,
but the cost is also very high. This method has already become bottle neck today; this
made to develop some SPAM detecting algorithms by all means.
After that, the author analyzed the optimized link structure of all kinds Link Farms
with different link models. Analyzed and get the optimized link structure of Link Farm
at site level. The author raised a method that grub spam community at site level; and
proposed algorithm used topic abnormal and algorithm based in-degree abnormal to
find spam community and spam target page. At page level, this paper optimized
TrustRank, targeted at the phenomenon that valid area is small, penalty process influent
a few innocent pages. The author proposed time trust algorithm, and integrated
PageRank and TrustRank to measure web page quality. The author proposed to integrate
incremental crawling and spam detecting to reduce workload of spam detecting and
handling.
The author used the data provided by Sougou Lab to local indexed and checked
algorithms. The outcome of experiment showed excellent.
Key Words: Search Engine, Link Spam, Link Farm, TrustRank
iii
目录
摘要
ABSTRACT
第一章 绪论.....................................................................................................................1
§1.1 搜索引擎技术的历史、现状及发展...............................................................1
§1.1.1 搜索引擎的历史.......................................................错误！未定义书签。
§1.1.2 搜索引擎技术的现状...............................................错误！未定义书签。
§1.1.2.1 搜索引擎的分类....................................................错误！未定义书签。
§1.1.2.2 搜索引擎计算模型................................................错误！未定义书签。
§1.1.3 搜索引擎技术的局限................................................错误！未定义书签。
§1.1.4 搜索引擎技术的发展趋势.......................................错误！未定义书签。
§1.2 课题的意义和主要工作内容.............................................错误！未定义书签。
第二章 搜索引擎技术的基本概念和方法.....................................................................4
§2.1 网页搜集...........................................................................................................4
§2.1.1 网络蜘蛛基本原理...................................................错误！未定义书签。
§2.1.2 索引更新周期...........................................................错误！未定义书签。
§2.2 预处理...............................................................................................................5
§2.2.1 建立倒排索引.........................................................................................6
§2.2.2 网页重要度计算.......................................................错误！未定义书签。
§2.2.2.1 PageRank 算法 ........................................................错误！未定义书签。
§2.2.2.2 HITS 算法.............................................................................................6
§2.3 查询服务...........................................................................................................8
§2.3.1 查询方式和匹配.......................................................错误！未定义书签。
§2.3.2 结果排序...................................................................错误！未定义书签。
§2.3.3 文档摘要...................................................................错误！未定义书签。
§2.4 本章小结...........................................................................................................9
第三章 Intranet 智能搜索引擎设计思路和体系结构................................................. 10
§3.1 Intranet 搜索和 Internet 搜索的异同 ..............................................................10
§3.2 体系结构和设计思路......................................................................................12
§3.2.1 Nutch 和Lucene .................................................................................... 16
§3.3 本章小结.........................................................................................................17
第四章 中文分词技术及其实现...................................................................................18
§4.1 常见中文分词技术..........................................................................................18
§4.2 双向最大匹配中文分词技术的实现.............................................................21
§4.2.1 Lucene 中的分词技术 ...........................................................................21
§4.2.2 正向最大匹配(MM)分词算法.............................................................21
§4.2.2 双向最大匹配分词算法.......................................................................25
§4.2.3 实现.......................................................................................................25
§4.3 中文分词评测.................................................................................................31
§4.4 本章小结.........................................................................................................34
第五章 网页分类技术及其实现...................................................................................36
iv
§5.1 网页分类技术..................................................................................................36
§5.1.1 文本分类技术...........................................................错误！未定义书签。
§5.1.2 网页分类的特点.......................................................错误！未定义书签。
§5.1.3 网页分类的相关研究...............................................错误！未定义书签。
§5.2 网页分类模块的设计......................................................................................37
§5.2.1 模块框架...................................................................错误！未定义书签。
§5.2.2 网页预处理...............................................................错误！未定义书签。
§5.2.2.1 HTML 解析.............................................................错误！未定义书签。
§5.2.2.2 英文文法分析和中文分词....................................错误！未定义书签。
§5.2.2.3 停用词删除............................................................错误！未定义书签。
§5.2.2.4 词条频率计算及倒排索引建立............................错误！未定义书签。
§5.2.3 类别特征词库抽取...................................................错误！未定义书签。
§5.2.3.1 类别文档建模........................................................错误！未定义书签。
§5.2.3.2 平凡词过滤............................................................错误！未定义书签。
§5.2.3.3 归类可信度计算....................................................错误！未定义书签。
§5.2.3.3 抽取类别特征词....................................................错误！未定义书签。
§5.2.4 分类器.......................................................................错误！未定义书签。
§5.3 网页分类实验..................................................................................................40
§5.3.1 训练网页集...............................................................错误！未定义书签。
§5.3.2 构建类别特征词库...................................................错误！未定义书签。
§5.3.3 类别阈值的确定........................................................错误！未定义书签。
§5.3.3.1 四类训练集网页类别可信度计算........................错误！未定义书签。
§5.3.3.2 其它类训练集网页类别可信度计算....................错误！未定义书签。
§5.3.3.3 阈值计算................................................................错误！未定义书签。
§5.4 本章小结.........................................................................................................41
第六章 搜索引擎的个性化技术及其实现...................................................................42
§6.1 Web 信息检索个性化的相关技术 ................................................................. 42
§6.1.1 个性化网页权重....................................................................................42
§6.1.2 查询改进................................................................................................43
§6.2 增加 IP 影响因子的页面排序算法 ................................... 错误！未定义书签。
§6.2.1 Lucene 的页面排序算法 ........................................... 错误！未定义书签。
§6.2.2 算法改进...................................................................错误！未定义书签。
§6.3 个性化搜索实现.............................................................................................43
§6.4 本章小结.........................................................................................................48
第七章 系统集成...........................................................................................................49
§7.1 Java 后台应用程序 ......................................................................................... 49
§7.1.1 Nutch09Dev 主工程 ...................................................错误！未定义书签。
§7.1.2 WordSegmentation 工程和 MyLucene 工程 .............错误！未定义书签。
§7.2 Web 应用程序 ................................................................................................. 51
§7.3 本章小结.........................................................................................................53
第八章 总结和展望.......................................................................................................57
§8.1 本文工作总结.................................................................................................57
§8.2 Intranet 搜索的未来展望 ................................................................................ 58
第一章 绪论
1
第一章 绪论
§1.1 搜索引擎的重要性
人们越来越依赖互联网带来的信息财富,希望互联网给个人或者企业带来明显
的经济利益的呼声也越发的强烈.大多情况下,搜索引擎是网络的入口.如果没有搜
索引擎,那么我们要在信息的海洋里定位感兴趣的信息是十分困难的,随机浏览不
利于信息的获取,并且会浪费大量的时间.搜索引擎提供了快捷,方便的互联网信息
获取途径.可以这么说,搜索引擎在网络中扮演的角色是无可替代的.
搜索引擎在互联网中的角色,决定了它对网站或者个人网页的访问量有很大
的影响.以搜索引擎中著名的 Google 为例.美国市场调研公司 WebSideStory 统计
了2005 年6月6日这天他们跟踪的所有商业网站流量的来源网址（referrers）。这
些网站从大型企业如电子零售商 Best Buy 到成千上万的小型企业网站。结果发现
搜索引擎 Google 对美国网站访问量贡献率（来自 google 的访问量占网站总访问
量的比例）为 52%，这一数字比 2004 年同期的同一调查结果上升了 10%。该调
查数据表明，对网站访问量贡献率较高的搜索引擎还包括 Yahoo 和MSN 等，通
过Yahoo 进入这些网站的流量占 25%，比 2004 年降低了 2%，MSN 占10%，比
去年下降了 6%。由此可见，Google 仍然是为商业网站带来主要访问量的搜索引
擎。
搜索引擎通过结果排序来显示针对用户查询匹配的最佳结果，而这个结果也
隐含着经济利益，因为统计发现[1]，对于大部分的查询来说，只有第一页结果，
TOP10 才被察看浏览。这也就是一些人试图误导搜索引擎使他们自己的网页获得
高的搜索结果排序的原因,目的只有一个,获取用户的注意,增加点击量,进而获得更
多的利益.
§1.2 搜索引擎结果排序
搜索引擎在网络中的重要的地位如此重要,维护搜索引擎查询结果的准确性,
有重要意义.可以说搜索引擎商现在除了要承担一定的商业信誉，还承担很大的社
会责任。最近，由于三鹿奶粉事件，引发了百度搜索引擎的信任危机。搜索结果
排名已经成为公众议论的话题，特别的，因为商业利益，而给公正提供失真的信
息，屏蔽赞助商不利信息等行为，成为大众和学者讨论的重要问题。让搜索引擎
排名真实可靠，已不再是纯粹的技术问题，也成为社会道德问题。
反Link Spam 的算法策略研究
2
影响搜索的结果的几个因素包括：
1.搜索匹配性。通过搜索条件的关键词划分，关键词匹配的返回的索引页面结
果就是搜索引擎查询的结果。可以这么说，页面文本中关键词的匹配对搜索引擎
结果的影响是最大的，如果搜索引擎提供的网页跟查询完全无关，那么将没有用
户再去使用。当然，这也是搜索引擎提供商能够提供保证的，在中文网页上面，
这个问题突出表现为中文分词问题。
2.权威性。在 google 的策略中，google 不会让赞助商影响搜索结果排序。在
这种情况下，通过权威度这个概念来对网页的质量进行评价，而权威度也在结果
排序中起到决定性作用。而在百度的策略中，影响结果排名的是赞助商的排序竞
价。基于学术上的研究目的，我们在稳重考虑的是用权威度来进行网页结果的排
序。
3.可信度。可行度的产生是因为网页垃圾的出现，垃圾网页的出现使得单纯使
用权威度来处理结果排序已经不能达到预想的如是反映网页质量的目的。可信度
是解决网页垃圾的一种解决方案。
§1.3 Web Spam
怎样提高在搜索引擎结果中的排序，成为一个热门的问题，也因此出现了一
个新的行业——搜索引擎优化，他们提供一系列的网站设计方案，使得搜索引擎
更容易发现信息，并且通过提高自己的网站质量来提高自己在行业内的权威，以
此来提高自己在搜索结果中的排序。但是也出现了一些投机者，他们根据搜索引
擎的运作机制，根据各个搜索引擎不同的结果排序算法，设计出一些作弊网页，
我们称之为 Web Spam 或者 Search Engine Spam，这种 Spam 网页的出现，会使得
用户对搜索引擎的满意度降低，长久会使搜索引擎丧失用户，并且对互联网的和
谐与稳定，提出了挑战。
Term Spam 是在 html 文件中增加大量的关键字或者重复多次关键字来提高网
页针对某个查询的相关度的 Spam 技术；而 Link Spam 是Web Spam 中靠网页之
间的连接来获取不应得的结果排序的一种作弊机制，二者是现在比较流行的 Spam
技术，除此以外还有很多种提高页面流行度或者权威度的作弊技术。那么如何识
别Web Spam；并且，标记为 Spam 的页面与站点信息怎么利用；如何对原有的排
序算法进行改进使其增强对 Web Spam 的免疫能力，是搜索引擎研究的一个重要
的方面。对于改进现在搜索引擎的性能，提高搜索引擎用户的满意度，有效的维
护互联网的公平公正，促进我国互联网健康稳定的发展，有重要的意义。
第一章 绪论
3
§1.4 Spam 学术研究现状
国外对 Web Spam 的研究开始的较早，早在 2002 年，Monika R,Henzinger 等
人在《Challenges in Web Search Engines》[2]一文中，便提到了 Web Spam 将成为
搜索引擎必须面对的挑战，著名的商用搜索引擎 Google 也随后在 2004 年更改了
自己原有的结果排序算法——PageRank，换之以对 Spam 有更强免疫力的算法。
Spam 技术和反 Spam 技术之间的对抗也从此开始，国外的一些学者将主要的 Web
Spam 技术进行了归类比较分析[3,4]，在这些学术论文中，最有代表性的要数《Web
Spam Taxonomy》[3]，文中根据 Spam 技术实施的目的性，将 Spam 技术主要分为
Boosting 技术与 Hiding 技术，前者根据各个搜索引擎的运行特点和相应的算法而
找出相应的投机策略，以此获取更容易被搜索引擎找到，在结果中排序更靠前的
效果；而后者，则是将这些经过精心设计的 Spam 网站或者页面隐藏得更不容易
被反 Spam 工作者发现，更像是正常的网站。对 Spam 技术的归类与分析更容易
反Spam 工作者采取相应的对策。
而针对众多 Spam 技术中的 Link Spam，国外的工作者取得的研究成果更是丰
富[5~9]。比如，Baoning Wu 等人在 2005 年的论文中提出了一种鉴别 Link Farm 算
法，可以实现鉴别 Link Farm 过程全自动化。
在处理包含 Spam 页面结果的排序问题上，国外学术工作者也是提出了各种
各样的算法和解决机制。这些算法大部分其实针对的还是 Link Spam 的。比如，
BadRank 算法通过利用一个 Spam 黑名单，通过网页之间的链接来繁殖页面是
Spam 可能性。而 TrustRank 算法在这个问题上引入信任度的概念，也是通过网页
之间链接来繁殖这种信任度。在这些算法与理论提出的基础上，一些学者也对其
进行了完善，该进了这些算法的性能。
Gary William Flake[10]等人提出了通过网站之间的链接关系来识别网络社区的
方法，Krishna Bharat[11]等人提出了扩大网络描述的粒度的方法，减少了分析网络
之间的链接的工作量，
Alexandros Ntoulas 研究了网页的生命周期[12]。这三方面工
作对于研究 Link Farm 有重要指导意义。
国内搜索引擎方面的研究已经取得一定的成果，国内也有百度这样的成功的
商业搜索引擎，北大天网搜索引擎也取得了大量的研究成果，这其中孟 涛等人研
究的增量搜索技术[13,14]。但 Web Spam 这方面的起步比较晚，虽然现在也有一些
文章介绍 Web Spam，但是对 Spam 的研究还是比较少。但是如何应对 Spam 技术
给搜索引擎带来的挑战，也是无论国内还是国外搜索引擎必须面临的问题，怎样
有效解决这个问题需要学术界与搜索引擎公司的共同努力。
摘要：

i摘要互联网自出现以来，经过短短几年已经发展成为一个巨大的全球化信息空间，网络用户的信息定位成本也急剧提高。搜索引擎出现并迅速发展成为互联网的入口，网络信息检索的重要工具。搜索结果的排序中蕴含的利润，使得SPAM（搜索引擎作弊行为）出现并成为了搜索引擎的巨大挑战，SPAM浪费了巨大的信息资源，更为严重的是影响了信息定位的效果。文章简述了搜索引擎常用的算法，指出了其中可能被作弊者利用的地方。在分类的基础上简单介绍了一些常用的作弊方式。对于这些问题网站的处理目前都是加以人工参与，这种方式准确率高，但是成本也很高，不能推广，无法批量处理。这在海里信息的今天己经成为成为了瓶颈，这使得研究高效的作弊行为...

展开>> 收起<<
反Link Spam的算法策略研究.pdf

共65页,预览7页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：牛悦 分类：高等教育资料 价格：15积分 属性：65 页 大小：2.44MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 65
评分 收藏
分享
立即下载 VIP免费下载
客服
关注