搜索引擎的算法

《搜索引擎的算法》由会员分享，可在线阅读，更多相关《搜索引擎的算法（10页珍藏版）》请在金锄头文库上搜索。

1、搜索引擎算法研究1弓|言万维网WWW （World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞 快的速度扩展。1998年WWW上拥有约3.5亿个文档14，每天增加约1百万的文档，不到9 个月的时间文档总数就会翻一番Ml。WEB上的文档和传统的文档比较，有很多新的特点， 它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档， 也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键 字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性

2、和准确性。另 外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面， 并且目录大多靠人工维护，主观性强，费用高，更新速度慢。最近几年，许多研究者发现，WWW上超链结构是个非常丰富和重要的资源，如果能够 充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的思想，Sergey Brin 和 Lawrence Page 在 1998年提出 了 PageRank 算法1，同年 J. Kleinberg 提出 了 HITS 算法5， 其它一些学者也相继提出了另外的链接分析算法，如SALSA，PHITS，Bayesian等算法。 这些算法有的已经在实际的系统中实现和使

3、用，并且取得了良好的效果。文章的第2部分按照时间顺序详细剖析了各种链接分析算法，对不同的算法进行了比较。 第3部分对这些算法做了评价和总结，指出了存在的问题和改进方向。2. WEB超链分析算法2.1 Google 和 PageRank 算法搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page实现的一 个原型系统，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似 于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序 处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网

4、页的 PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出 现的位置越前。2.1.1 PageRank 算法PageRank算法基于下面2个前提：前提1： 一个网页被多次引用，则它可能是很重要的；一个网页虽然没有被多次引用，但 是被重要的网页引用，则它也可能是很重要的；一个网页的重要性被平均的传递到它所引用 的网页。这种重要的网页称为权威（Authoritive）网页。前提2：假定用户一开始随机的访问网页集合中的一个网页，以后跟随网页的向外链接向 前浏览网页，不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。简单PageRank算法描

5、述如下：u是一个网页，*）是u指向的网页集合，缶）是指向 u的网页集合，是u指向外的链接数，显然g） = 脚）|，c是一个用于规范化的因子（Google通常取0.85），（这种表示法也适用于以后介绍的算法）则u的Rank值计算如下：R) = c 云/Mv)汀旦;)这就是算法的形式化描述，也可以用矩阵来描述此算法，设A为一个方阵，行和列对应一，一一 , 一一 一 ，一一，, 一 ,4，- =1/24网页集的网页。如果网页i有指向网页j的一个链接，则勺盘，否则耳温=0。设V是对应网页集的一个向量，有V=cAV，V为A的特征根为c的特征向量。实际上，只需要求出最大特征根的特征向量，就是网页集对应的最

6、终PageRank值，这可以用迭代方法计算。如果有2个相互指向的网页a，b,他们不指向其它任何网页，另外有某个网页c，指向a， b中的某一个，比如a，那么在迭代计算中，a，b的rank值不分布出去而不断的累计。如下 图：为了解决这个问题，Sergey Brin和Lawrence Page改进了算法，引入了衰退因子E(u)， E(U)是对应网页集的某一向量，对应rank的初始值，算法改进如下： R(u) =c R(v)/N(v) +cE(u)|TU其中，II反111=1，对应的矩阵形式为V=c(AV+E)。另外还有一些特殊的链接，指向的网页没有向外的链接。PageRank计算时，把这种链接 首先

7、除去，等计算完以后再加入，这对原来计算出的网页的rank值影响是很小的。Pagerank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量， 向后链接的预测器，为用户导航等。2.1.2算法的一些问题Google是结合文本的方法来实现PageRank算法的，所以只返回包含查询项的网页，然 后根据网页的rank值对搜索到的结果进行排序，把rank值最高的网页放置到最前面，但是 如果最重要的网页不在结果网页集中，PageRank算法就无能为力了，比如在Google中查询 search engines，像Google， Yahoo， Altivisa等都是很重要的，但是Google返回

8、的结果中这 些网页并没有出现。同样的查询例子也可以说明另外一个问题，Google，Yahoo是WWW 上最受欢迎的网页，如果出现在查询项car的结果集中，一定会有很多网页指向它们，就会 得到较高的rank值，事实上他们与car不太相关。在PageRank算法的基础上，其它的研究者提出了改进的PageRank算法。华盛顿大学计 算机科学与工程系的Matthew Richardson和Pedro Dominggos提出了结合链接和内容信息的 PageRank算法，去除了 PageRank算法需要的前提2,增加考虑了用户从一个网页直接跳转 到非直接相邻的但是内容相关的另外一个网页的情况3。斯坦大学计

9、算机科学系Taher Haveliwala提出了主题敏感(Topic-sensitive) PageRank算法4。斯坦福大学计算机科学系 Arvind Arasu等经过试验表明，PageRank算法计算效率还可以得到很大的提高22。2.2 HITS算法及其变种PageRank算法中对于向外链接的权值贡献是平均的，也就是不考虑不同链接的重要性。 而WEB的链接具有以下特征：1. 有些链接具有注释性，也有些链接是起导航或广告作用。有注释性的链接才用于权威 判断。2. 基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页。3. 权威网页很少具有显式的描述，比如Google主页不会明确给

10、出WEB搜索引擎之类的描述信息。可见平均的分布权值不符合链接的实际情况14J. Kleinberg5提出的HITS算法中引入了 另外一种网页，称为Hub网页，Hub网页是提供指向权威网页链接集合的WEB网页，它本 身可能并不重要，或者说没有几个网页指向它，但是Hub网页确提供了指向就某个主题而 言最为重要的站点的链接集合，比一个课程主页上的推荐参考文献列表。一般来说，好的 Hub网页指向许多好的权威网页；好的权威网页是有许多好的Hub网页指向的WEB网页。 这种Hub与Authoritive网页之间的相互加强关系，可用于权威网页的发现和WEB结构和 资源的自动发现，这就是Hub/Authori

11、ty方法的基本思想。2.2.1 HITS 算法HITS (HyperlinkInduced Topic Search)算法是利用 Hub/Authority 方法的搜索方法，算 法如下：将查询q提交给传统的基于关键字匹配的搜索引擎.搜索引擎返回很多网页，从中 取前n个网页作为根集(root set)，用S表示。S满足如下3个条件：1. S中网页数量相对较小2. S中网页大多数是与查询q相关的网页3. S中网页包含较多的权威网页。通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T.以T中的Hub网页为顶点集Vl，以权威网页为顶点集V2，Vl中的网页到V2中的网页 的超链接为边集

12、E，形成一个二分有向图SG=(V1，V2, E)。对V1中的任一个顶点v，用 h(v)表示网页v的Hub值，对V2中的顶点u，用a(u)表示网页的Authority值。开始时h(v) = a(u)=1，对u执行I操作修改它的a(u)，对v执行O操作修改它的h(v)，然后规范化a(u)， h (v)，如此不断的重复计算下面的操作I，O，直到a (u)，h (v)收敛。(证明此算法收敛 可见四)h(y)= ),板)I操作：中心f(1) o操作:(2)每次迭代后需要对a(u),h(v)进行规范化处理：=泌)=的)/ 区冲)式(1)反映了若一个网页由很多好的Hub指向，则其权威值会相应增加(即权威值增

13、加为 所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页，则 Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。和PageRank算法一样，可以用矩阵形式来描述算法，这里省略不写。HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。2.2.2 HITS的问题HITS算法有以下几个问题：1. 实际应用中，由S生成T的时间开销是很昂贵的，需要下载和分析S中每个网页包 含的所有链接，并且排除重复的链接。一般T比S大很多，由T生成有向图也很耗时。需 要分别计算网页的A/H值，计算量比PageRank算法大。2. 有些时候，一主机A上的

14、很多文档可能指向另外一台主机B上的某个文档，这就增 加了 A上文档的Hub值和B上文档的Authority，相反的情况也如此。HITS是假定某一文 档的权威值是由不同的单个组织或者个人决定的，上述情况影响了人和B上文档的Hub和 Authority 值7。3. 网页中一些无关的链接影响A，H值的计算。在制作网页的时候，有些开发工具会自动的在网页上加入一些链接，这些链接大多是与查询主题无关的。同一个站点内的链接目的 是为用户提供导航帮助，也与查询主题不甚无关，还有一些商业广告，赞助商和用于友情交 换的链接，也会降低HITS算法的精度凶。4. HITS算法只计算主特征向量，也就是只能发现T集合中的

15、主社区(Community)，忽 略了其它重要的社区12。事实上，其它社区可能也非常重要。5. HITS算法最大的弱点是处理不好主题漂移问题(topic drift) f，也就是紧密链接 TKC (Tightly-Knit Community Effect)现象8。如果在集合T中有少数与查询主题无关的网 页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页，因为HITS只能发现主 社区，从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了 TKC问题。6. 用HITS进行窄主题查询时，可能产生主题泛化问题59,即扩展以后引入了比原来主 题更重要的新的主题，新的主题可能与原始查询无

16、关。泛化的原因是因为网页中包含不同主 题的向外链接，而且新主题的链接具有更加的重要性。2.2.3 HITS的变种HITS算法遇到的问题，大多是因为HITS是纯粹的基于链接分析的算法，没有考虑文本 内容，继J. Kleinberg提出HITS算法以后，很多研究者对HITS进行了改进，提出了许多 HITS的变种算法，主要有：2.2.3.1 Monika R. Henzinger 和 Krishna Bharat 对 HITS 的改进对于上述提到的HITS遇到的第2个问题，Monika R. Henzinger和Krishna Bharat在7中进 行了改进。假定主机A上有k个网页指向主机B上的某个文档