搜索引擎主题模型优化(传统的WEB搜索引擎大多数算法２.１Google和PageRank算法)

　　搜索引擎主题模型优化(传统的WEB搜索引擎大多数算法２.１Google和PageRank算法)

　　一、介绍

　　万维网（World Wide Web）是一个巨大的、分布在全球的信息服务中心，并且正在迅速扩展。1998 年，WWW 上大约有 3.5 亿个文档 [14]，每天增加大约 100 万个文档 [6]，不到 9 个月，文档总数将翻一番 [14] ]。与传统文档相比，WEB上的文档具有许多新的特点。它们是分布式的、异构的、非结构化的或半结构化的，这给传统的信息检索技术带来了新的挑战。

　　传统的WEB搜索引擎大多基于关键字匹配，返回的结果是收录查询项的文档。还有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。一些网站故意增加关键词的频率，以增加其在搜索引擎中的重要性，破坏了搜索引擎结果的客观性和准确性。此外，一些重要的网页不收录查询词。搜索引擎的分类目录不可能全面考虑所有的分类，而且大部分目录都是手动维护的，主观性强、成本高、更新慢[2]。

　　近年来，许多研究人员发现，万维网上的超链接结构是一种非常丰富和重要的资源，如果能够充分利用，可以大大提高搜索结果的质量。基于这种超链接分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1]，同年J. Kleinberg提出了HITS算法[5]，其他学者相继提出了其他链接分析算法。如SALSA、PHITS、贝叶斯等算法。其中一些算法已经在实际系统中实现和使用，并取得了良好的效果。

　　文章 的第 2 部分按时间顺序详细剖析了各种链接分析算法，比较了不同的算法。第 3 节对这些算法进行评估和总结，并指出存在的问题和改进方向。

　　2. WEB超链接分析算法

　　２.1Google和PageRank算法

　　搜索引擎 Google 最初是由斯坦福大学博士生 Sergey Brin 和 Lawrence Page [2] 实现的原型系统，现在已经发展成为 WWW 上最好的搜索引擎之一。Google 的架构类似于传统的搜索引擎。它与传统搜索引擎最大的不同在于，它根据权威值对网页进行排序，使最重要的网页出现在结果的顶部。Google 通过 PageRank 元算法计算网页的 PageRank 值，从而确定网页在结果集中的位置。PageRank 值越高，在结果中的位置就越高。

　　２.１.1PageRank算法

　　PageRank算法基于以下两个前提：

　　前提1：一个网页如果被多次引用，它可能很重要；如果一个网页没有被多次引用但被重要网页引用，则它可能很重要；一个网页的重要性被平均传递给它所指的网页。这样重要的页面被称为权威页面。

　　前提2：假设用户首先随机访问网页集合中的一个网页，然后沿着该网页的出站链接向前浏览该网页而不返回，则浏览下一个网页的概率为浏览网页的PageRank值。

　　简单的PageRank算法描述如下：u是一个网页，是u指向的网页集合，是指向u的网页集合，是u指向的链接数，显然=| | , c 是一个用于归一化的因子（谷歌通常取0.85）,（这个符号也适用于后面介绍的算法），那么u的Rank值计算如下：

　　这是算法的正式描述。该算法也可以用矩阵来描述。设A为方阵，行列对应网页集合的网页。如果网页 i 有指向网页 j 的链接，否则 = 0。设V为网页集合对应的向量，有V=cAV，V为特征值为c的A的特征向量。其实只需要最大特征根的特征向量，就是网页集合对应的最终PageRank值，可以迭代计算。

　　如果有两个网页a和b相互指向，它们不指向任何其他网页，并且有一个网页c指向a和b中的一个，比如a，那么在迭代计算中，a和b的rank值是不连续分布和累积的。如下所示：

　　为了解决这个问题，Sergey Brin 和 Lawrence Page 对算法进行了改进，引入了一个衰减因子 E(u)，E(U) 是对应于网页集合的某个向量，对应于 rank 的初始值，而算法改进如下：

　　其中，=1，对应的矩阵形式为V'=c(AV'+E)。

　　此外，还有一些特殊的链接指向没有传出链接的网页。在计算PageRank时，这种链接先去掉，计算完成后再添加，对原计算网页的rank值影响不大。

　　除了对搜索结果进行排名之外，Pagerank 算法还可以应用于其他方面，例如估计网络流量、反向链接的预测器、为用户导航等 [2]。

　　２.１.2 算法的一些问题

　　Google结合文本[2]实现PageRank算法，所以只返回收录查询项的网页，然后根据网页的rank值对搜索结果进行排序，排名最高的网页value 放在顶部，但如果最重要的网页不在结果网页集合中，PageRank 算法将无能为力。例如，在谷歌中查询搜索引擎非常重要，如谷歌、雅虎、Altivas 等，但这些页面不会出现在谷歌返回的结果中。同一个查询示例还可以说明另一个问题。Google 和 Yahoo 是 WWW 上最受欢迎的网页。如果它们出现在查询项car的结果集中，肯定有很多网页指向它们，会得到更高的rank值。

　　在PageRank算法的基础上，其他研究人员提出了改进的PageRank算法。华盛顿大学计算机科学与工程系的 Matthew Richardson 和 Pedro Dominggos 提出了一种结合链接和内容信息的 PageRank 算法。与内容相关的另一个网页的情况[3]。斯坦大学计算机科学系的 Taher Haveliwala 提出了一种主题敏感的 PageRank 算法 [4]。斯坦福大学计算机科学系的 Arvind Arasu 等人通过实验表明，PageRank 算法的计算效率也可以大大提高 [22]。

　　２.2HITS 算法及其变体

　　PageRank算法对出站链接的权重贡献是平均的，即不考虑不同链接的重要性。WEB链接具有以下特点：

　　1.有些链接是注释性的，有些是导航或广告的。带注释的链接供权威判断。

　　2.出于商业或竞争考虑，很少有 WEB 页面指向其竞争领域的权威页面。

　　3.权威网页很少有明确的描述。例如，谷歌主页没有明确给出WEB搜索引擎等描述。

　　可以看出，平均分配权重不符合链路的实际情况[17]。J. Kleinberg [5] 提出的 HITS 算法引入了另一种网页，称为 Hub 页面。中心页面是提供权威网页链接集合的网页。它本身可能并不重要，或者很少有网页指向它，但 Hub 页面确实提供了指向某个主题的最重要站点的链接集合，例如课程主页上的推荐参考列表。一般来说，一个好的hub页面指向很多好的权威页面；一个好的权威页面是很多好的hub页面指向的WEB页面。Hub和Authoritive网页之间的相互促进关系可以用于权威网页的发现和WEB结构和资源的自动发现。这就是 Hub/Authority 方法的基本思想。

　　２.２.1HITS算法

　　HITS（Hyperlink-Induced Topic Search）算法是一种使用Hub/Authority方法的搜索方法。算法如下： 将查询 q 提交给传统的基于关键字匹配的搜索引擎。搜索引擎返回很多网页，其中前n个网页作为根集，记为S。S满足以下三个条件：

　　1、S中的网页数量比较少

　　2. S中的大部分网页都与查询q有关

　　3. S中的网页收录更权威的网页。

　　通过将 S 引用的页面和引用 S 的页面添加到 S 中，将 S 扩展为更大的集合 T。

　　以T中的Hub网页为顶点集V1，以权威网页为顶点集V2，V1中的网页到V2中的网页的超链接为边集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) 收敛。（证明这个算法收敛可见）

　　I 操作：(1） O 操作：(2）

　　每次迭代后，需要对 a(u)、h(v) 进行归一化：

　　公式（1)反映的是，如果一个网页被很多好的Hub指向，它的权限值会相应增加（即权限值增加为所有的已有Hub值的总和）指向它的网页）。公式（2)反映了如果一个网页指向很多好的权威页面，那么Hub值也会相应增加（即Hub值随着权威的总和而增加）链接到该网页的所有网页的值）。

　　与PageRank算法一样，该算法可以用矩阵的形式来描述，这里不再赘述。

　　HITS算法输出一组Hub值较大的网页和权限值较大的网页。

　　２.２.2 个热门问题

　　HITS算法存在以下问题：

　　1、在实际应用中，从S生成T的时间开销是非常昂贵的，需要对S中每个网页所收录的所有链接进行下载和分析，并排除重复链接。通常，T 比 S 大得多，从 T 生成有向图也很耗时。需要单独计算网页的A/H值，计算量大于PageRank算法。

　　2. 有时，一台主机A上的多个文档可能指向另一台主机B上的一个文档，这增加了A上文档的Hub值和B上文档的权限，反之亦然。HITS假设一个文档的权限值是由不同的个体组织或个人决定的，上述情况影响了A和B上文档的Hub和Authority值[7]。

　　3、网页中一些不相关的链接会影响A、H值的计算。在创建网页时，一些开发工具会自动在网页中添加一些链接，其中大部分与查询主题无关。同一站点内的链接的目的是为用户提供导航帮助，与查询主题关系不大。还有一些商业广告、赞助和友情交流的链接，也会降低HITS算法的准确性[8]。

　　4. HITS算法只计算主要特征向量，即只能在T集合中找到主要社区（Community），而忽略其他重要社区[12]。事实上，其他社区也可能非常重要。

　　5. HITS算法最大的弱点是无法处理话题漂移问题[7, 8]，即Tightly-Knit Community Effect (TKC)现象[8]。如果集合 T 中有少数网页与查询主题无关，但联系紧密，那么 HITS 算法的结果可能就是这些网页，因为 HITS 只能找到主要社区，这与原创查询主题。TKC 问题在下面讨论的 SALSA 算法中得到解决。

　　6. 使用HITS进行狭义主题查询时，可能会出现主题泛化问题[5, 9]，即扩展后引入比原主题更重要的新主题，新主题可能与原主题无关询问。概括的原因是因为网页收录指向不同主题的传出链接，而指向新主题的链接更为重要。

　　２.２.3 HITS 变体

　　HITS算法遇到的大部分问题都是因为HITS是纯基于链接分析的算法，没有考虑文本内容。在 J. Kleinberg 提出 HITS 算法之后，许多研究人员对 HITS 进行了改进，并提出了许多 HITS 变体算法。，有：

　　２.２.３.1 Monika R. Henzinger 和 Krishna Bharat 对 HITS 的改进

　　对于上面提到的 HITS 遇到的第二个问题，Monika R. Henzinger 和 Krishna Bharat 在 [7] 中对其进行了改进。假设主机 A 上有 k 个网页指向主机 B 上的一个文档 d，那么这 k 个文档对 B 的总贡献值为 1，每个文档贡献 1/k 而不是每个文档在 HITS 中的贡献。文档贡献1，总贡献k。同理，对于 Hub 值，假设主机 A 上的一个文档 t 指向主机 B 上的 m 个文档，则 B 上的 m 个文档对 t 的 Hub 值贡献 1，每个文档贡献 1/m。I、O操作改为如下

　　我操作：

　　Ø 操作：

　　调整后的算法有效地解决了问题 2，称为 imp 算法。

　　在此基础上，Monika R. Henzinger 和 Krishna Bharat 还引入了传统信息检索的内容分析技术来解决问题 4 和问题 5，实际上同时解决了问题 3。具体方法如下，提取根集S中每篇文档的前1000个词，拼接为查询主题Q，文档Dj与主题Q的相似度按照如下公式计算：

　　, , = 查询 Q 中项目 i 的出现次数，

　　= 项目 i 在文档 Dj 中出现的次数，IDFi 是对 WWW 上收录项目 i 的文档数量的估计。

　　将S扩展到T后，计算每个文档的主题相似度，根据不同的阈值（threshold）进行选择，可以选择所有文档相似度的中值，根集文档相似度的中值，最大文档相似度的一小部分，例如1/10，作为阈值。根据不同的阈值处理，删除不满足条件的文档，然后运行imp算法计算文档的A/H值。这些算法分别称为 med、startmed 和 maxby10。

　　在这种改进的算法中，计算文档的相似度将花费大量时间。

　　２.２.３.2ARC算法

　　IBM Almaden 研究中心的 Clever 工程组提出了 ARC（Automatic Resource Compilation）算法，对原有的 HITS 进行了改进，结合链接的锚文本给出了网页集对应的连接矩阵的初始值，适应对不同的链接有不同的权重。

　　ARC算法与HITS的区别主要在于以下三点：

　　1.当根集S展开为T时，HITS只将链接路径长度为1的网页展开到根集，即只展开与S直接相邻的网页，而在ARC中，展开后的链接长度增加到2，扩展后的网页集合称为Augment Set。

　　2.在HITS算法中，每个环节对应的矩阵值都设置为1，其实每个环节的重要性是不一样的。ARC 算法考虑链接周围的文本来确定链接的重要性。考虑链接p->q，在p中有几个链接标签，文本1，锚文本，文本2，假设查询项t在文本1，锚文本，文本2中，出现次数为n(t )，则 w(p,q)=1+n(t)。文本 1 和文本 2 的长度实验性地设置为 50 个字节 [10]。构造矩阵W，如果有网页i->j，Wi,j=w(i,j)，否则Wi,j=0，H值置1，Z为W的转置矩阵，迭代执行以下三个操作：

　　(1）A=WH (2）H=ZA (3）归一化 A, H

　　3. ARC算法的目标是找出最重要的前15个网页。它只需要保持A/H的前15个值的相对大小稳定，不需要A/H的整个收敛。这样，2中的迭代次数就足够少了。在[10]中指出5次迭代就足够了，因此ARC算法计算效率高，开销主要在扩展根集上。

　　２.２.３.3Hub平均（Hub-Averaging-Kleinberg）算法

　　艾伦鲍罗丁等人。[11]指出了一个现象，即有M+1个Hub页面，M+1个权威页面，前M个Hubs指向第一个权威页面，第M+1个Hub页面指向所有M+1个权威页面。显然根据HITS算法，第一个权威页面是最重要的，拥有最高的Authority值，这就是我们想要的。但是，根据 HITS，第 M+1 个 Hub 页面的 Hub 值最高。实际上，第 M+1 个 Hub 页面不仅指向第一个权威值高的权威页面，还指向其他低权威值的页面。其 Hub 值不应高于前 M 页的 Hub 值。因此，Allan Borodin 修改了 HITS 的 O 操作：

　　O 运算： , n 是 (v, u) 的个数

　　调整后，只指向高权限值页面的Hub值高于同时指向高权限值和低权限值页面的Hub值。该算法称为 Hub-Averaging-Kleinberg 算法。

　　２.２.３.4 阈值-克莱因伯格算法

　　艾伦鲍罗丁等人。[11]同时提出了三种阈值控制算法，即Hub阈值算法、Authority阈值算法和两者结合的全阈值算法。

　　在计算网页p的权限时，不考虑所有指向它的网页的贡献，而只考虑Hub值超过平均值的网页的贡献。这是 Hub 阈值方法。

　　权威阈值算法类似于 Hub 阈值方法。它不考虑p指向的所有页面的Authority对p的Hub值的贡献，只计算前K个权威页面对其Hub值的贡献。这是基于算法的。目标是找到最重要的K个权威网页的前提。

　　同时使用Authority阈值算法和Hub阈值方法的算法是全阈值算法

　　２.3SALSA算法

　　PageRank算法是基于用户对网页随机前向浏览的直观认识，HITS算法考虑了Authoritive网页与Hub网页之间的强化关系。在实际应用中，用户在大多数情况下是向前浏览网页，但也有很多情况是向后浏览网页。基于上述直观知识，R. Lempel 和 S. Moran 提出了 SALSA（Stochastic Approach for Link-Structure Analysis）算法[8]，该算法考虑了用户恢复浏览网页的情况，并保留了 PageRank 的随机漫游和命中。分为Authoritive和Hub的思路，取消了Authoritive和Hub的相辅相成关系。

　　具体算法如下：

　　1.和HITS算法的第一步一样，得到根集，扩展为一组网页T，去除孤立节点。

　　2.从集合T构造无向图G'=(Vh, Va, E)

　　Vh = { sh | s∈C 和 out-degree(s) > 0 }（G' 的中心边缘）。

　　VA = { 萨 | s∈C 和 in-degree(s) > 0 }（G' 的权威边）。

　　E= { (sh , ra) |s－>r in T}

　　这定义了 2 条链，权威链和 Hub 链。

　　3.定义两条马尔可夫链的变化矩阵，也是随机矩阵，即Hub矩阵H和Authority矩阵A。

　　4、得到矩阵H和A的主特征向量，即对应马尔可夫链的静态分布。

　　5.中值A大的对应网页就是你要找的重要网页。

　　SALSA算法在HITS中没有相辅相成的迭代过程，计算量也比HITS小很多。SALSA算法只考虑直接相邻网页对自身A/H的影响，而HITS计算整个网页集T对自身AH的影响。

　　在实践中，SALSA 在扩展根集时会忽略许多不相关的链接，例如

　　1. 同一站点内的链接，因为大多数这些链接仅用于导航。

　　2. CGI 脚本链接。