搜索引擎的算法研究与分析论文

2.1基于词频统计——词位置加权的搜索引擎 利用关键词在文档中出现的频率和位置排序是搜索引擎最早期排序的主要思想，其技术发展也最为成熟，是第一阶段搜索引擎的主要排序技术，应用非常广泛，至今仍是许多搜索引擎的核心排序技术。其基本原理是：关键词在文档中词频越高，出现的位置越重要，则被认为和检索词的相关性越好。 1）词频统计 文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高，其相关度越大。但当关键词为常用词时，使其对相关性判断的意义非常小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。TF（Term Frequency）：单文本词汇频率，用关键词的次数除以网页的总字数，其商称为“关键词的频率”。IDF（Inverse Document Frequency）：逆文本频率指数，其原理是，一个关键词在N个网页中出现过，那么N越大，此关键词的权重越小，反之亦然。当关键词为常用词时，其权重极小，从而解决词频统计的缺陷。 2）词位置加权 在搜索引擎中，主要针对网页进行词位置加权。所以，页面版式信息的分析至关重要。通过对检索关键词在Web页面中不同位置和版式，给予不同的权值，从而根据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有：是否是标题，是否为关键词，是否是正文，字体大小，是否加粗等等。同时，锚文本的信息也是非常重要的，它一般能精确的描述所指向的页面的内容。 2.2基于链接分析排序的第二代搜索引擎 链接分析排序的思想起源于文献引文索引机制，即论文被引用的次数越多或被越权威的论文引用，其论文就越有价值。链接分析排序的思路与其相似，网页被别的网页引用的次数越多或被越权威的网页引用，其价值就越大。被别的网页引用的次数越多，说明该网页越受欢迎，被越权威的网页引用，说明该网页质量越高。链接分析排序算法大体可以分为以下几类：基于随机漫游模型的，比如PageRank和Repution算法；基于概率模型的，如SALSA、PHITS；基于Hub和Authority相互加强模型的，如HITS及其变种；基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。本文主要介绍以下几种经典排序算法： 1）PageRank算法 PageRank算法由斯坦福大学博士研究生Sergey Brin和Lwraence Page等提出的。PageRank算法是Google搜索引擎的核心排序算法，是Google成为全球最成功的搜索引擎的重要因素之一，同时开启了链接分析研究的热潮。 PageRank算法的基本思想是：页面的重要程度用PageRank值来衡量，PageRank值主要体现在两个方面：引用该页面的页面个数和引用该页面的页面重要程度。一个页面P（A）被另一个页面P（B）引用，可看成P（B）推荐P（A），P（B）将其重要程度（PageRank值）平均的分配P（B）所引用的所有页面，所以越多页面引用P（A），则越多的页面分配PageRank值给P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的页面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。 其计算公式为： PR（A）：页面A的PageRank值； d：阻尼系数，由于某些页面没有入链接或者出链接，无法计算PageRank值，为避免这个问题（即LinkSink问题），而提出的。阻尼系数常指定为0.85。 R（Pi）：页面Pi的PageRank值； C（Pi）：页面链出的链接数量； PageRank值的计算初始值相同，为了不忽视被重要网页链接的网页也是重要的这一重要因素，需要反复迭代运算，据张映海撰文的计算结果，需要进行10次以上的迭代后链接评价值趋于稳定，如此经过多次迭代，系统的PR值达到收敛。 PageRank是一个与查询无关的静态算法，因此所有网页的PageRank值均可以通过离线计算获得。这样，减少了用户检索时需要的排序时间，极大地降低了查询响应时间。但是PageRank存在两个缺陷：首先PageRank算法严重歧视新加入的网页，因为新的网页的出链接和入链接通常都很少，PageRank值非常低。另外PageRank算法仅仅依靠外部链接数量和重要度来进行排名，而忽略了页面的主题相关性，以至于一些主题不相关的网页（如广告页面）获得较大的PageRank值，从而影响了搜索结果的准确性。为此，各种主题相关算法纷纷涌现，其中以以下几种算法最为典型。 2）Topic-Sensitive PageRank算法 由于最初PageRank算法中是没有考虑主题相关因素的，斯坦福大学计算机科学系Taher Haveli-wala提出了一种主题敏感（Topic-Sensitive）的PageRank算法解决了“主题漂流”问题。该算法考虑到有些页面在某些领域被认为是重要的，但并不表示它在其它领域也是重要的。 网页A链接网页B，可以看作网页A对网页B的评分，如果网页A与网页B属于相同主题，则可认为A对B的评分更可靠。因为A与B可形象的看作是同行，同行对同行的了解往往比不是同行的要多，所以同行的评分往往比不是同行的评分可靠。遗憾的是TSPR并没有利用主题的相关性来提高链接得分的准确性。 3）HillTop算法 HillTop是Google的一个工程师Bharat在2001年获得的专利。HillTop是一种查询相关性链接分析算法，克服了的PageRank的查询无关性的缺点。HillTop算法认为具有相同主题的相关文档链接对于搜索者会有更大的价值。在Hilltop中仅考虑那些用于引导人们浏览资源的专家页面（Export Sources）。Hilltop在收到一个查询请求时，首先根据查询的主题计算出一列相关性最强的专家页面，然后根据指向目标页面的非从属专家页面的数量和相关性来对目标页面进行排序。 HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过分依靠PageRank的值去寻找那些权威页面的方法，避免了许多想通过增加许多无效链接来提高网页PageRank值的作弊方法。HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性，通过不同位置的评分确保了主题（行业）的相关性，通过可区分短语数防止了关键词的堆砌。 但是，专家页面的搜索和确定对算法起关键作用，专家页面的质量对算法的准确性起着决定性作用，也就忽略了大多数非专家页面的影响。专家页面在互联网中占的比例非常低（1.79%），无法代表互联网全部网页，所以HillTop存在一定的局限性。同时，不同于PageRank算法，HillTop算法的运算是在线运行的，对系统的响应时间产生极大的压力。 4）HITS HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超链接分析排序算法中另一个最著名的算法之一。该算法按照超链接的方向，将网页分成两种类型的页面：Authority页面和Hub页面。Authority页面又称权威页面，是指与某个查询关键词和组合最相近的页面，Hub页面又称目录页，该页面的内容主要是大量指向Authority页面的链接，它的主要功能就是把这些Authority页面联合在一起。对于Authority页面P，当指向P的Hub页面越多，质量越高，P的Authority值就越大；而对于Hub页面H，当H指向的Authority的页面越多，Authority页面质量越高，H的Hub值就越大。对整个Web集合而言，Authority和Hub是相互依赖、相互促进，相互加强的关系。Authority和Hub之间相互优化的关系，即为HITS算法的基础。 HITS基本思想是：算法根据一个网页的入度（指向此网页的超链接）和出度（从此网页指向别的网页）来衡量网页的重要性。在限定范围之后根据网页的出度和入度建立一个矩阵，通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。 实验数据表明，HITS的排名准确性要比PageRank高，HITS算法的设计符合网络用户评价网络资源质量的普遍标准，因此能够为用户更好的利用网络信息检索工具访问互联网资源带来便利。 但却存在以下缺陷：首先，HITS算法只计算主特征向量，处理不好主题漂移问题；其次，进行窄主题查询时，可能产生主题泛化问题；第三，HITS算法可以说一种实验性质的尝试。它必须在网络信息检索系统进行面向内容的检索操作之后，基于内容检索的结果页面及其直接相连的页面之间的链接关系进行计算。尽管有人尝试通过算法改进和专门设立链接结构计算服务器（Connectivity Server）等操作，可以实现一定程度的在线实时计算，但其计算代价仍然是不可接受的。 2.3基于智能化排序的第三代搜索引擎 排序算法在搜索引擎中具有特别重要的地位，目前许多搜索引擎都在进一步研究新的排序方法，来提升用户的满意度。但目前第二代搜索引擎有着两个不足之处，在此背景下，基于智能化排序的第三代搜索引擎也就应运而生。 1）相关性问题 相关性是指检索词和页面的相关程度。由于语言复杂，仅仅通过链接分析及网页的表面特征来判断检索词与页面的相关性是片面的。例如：检索“稻瘟病”，有网页是介绍水稻病虫害信息的，但文中没有“稻瘟病”这个词，搜索引擎根本无法检索到。正是以上原因，造成大量的搜索引擎作弊现象无法解决。解决相关性的的方法应该是增加语意理解，分析检索关键词与网页的相关程度，相关性分析越精准，用户的搜索效果就会越好。同时，相关性低的网页可以剔除，有效地防止搜索引擎作弊现象。检索关键词和网页的相关性是在线运行的，会给系统相应时间很大的压力，可以采用分布式体系结构可以提高系统规模和性能。 2）搜索结果的单一化问题 在搜索引擎上，任何人搜索同一个词的结果都是一样。这并不能满足用户的需求。不同的用户对检索的结果要求是不一样的。例如：普通的农民检索“稻瘟病”，只是想得到稻瘟病的相关信息以及防治方法，但农业专家或科技工作者可能会想得到稻瘟病相关的论文。 解决搜索结果单一的方法是提供个性化服务，实现智能搜索。通过Web数据挖掘，建立用户模型（如用户背景、兴趣、行为、风格），提供个性化服务。