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

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

　　一、介绍

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

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

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

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

　　2.WEB超链接分析算法

　　２.１Google 和 PageRank 算法

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

　　２.１.１PageRank算法

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

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

　　前提2：假设用户一开始随机访问了网页集合中的一个网页，然后不回退，而是按照该网页的传出链接向前浏览该网页，则浏览下一个网页的概率为该网页的PageRank值。正在浏览的网页。

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

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

　　如果有两个网页a和b相互指向，它们不指向任何其他网页，而有一个网页c指向a和b之一，例如a，那么在迭代计算中，a和b的秩值不分配出去而是继续累加。如下所示：

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

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

　　另外还有一些特殊的链接，它们指向的网页没有外链。计算PageRank的时候，先去掉这种链接，计算完成后再添加。这对网页最初计算的排名值影响不大。

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

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

　　谷歌通过结合text方法实现PageRank算法[2]，所以它只返回收录查询项的网页，然后根据网页的排名值对搜索结果进行排序，并将排名值最高的网页放到顶，但是如果最重要的网页不在结果页面集中，PageRank算法就无能为力了。例如，在谷歌中搜索搜索引擎，如谷歌、雅虎、Altivisa 等非常重要，但这些页面不会出现在谷歌返回的结果中。同样的查询示例还可以说明另一个问题。Google 和 Yahoo 是 WWW 上最受欢迎的网页。如果它们出现在查询项car的结果集中，就会有很多网页指向它们，你会得到更高的排名值。事实上，它们与汽车并没有太大关系。

　　在 PageRank 算法的基础上，其他研究人员提出了改进的 PageRank 算法。华盛顿大学计算机科学与工程系的 Matthew Richardson 和 Pedro Dominggos 提出了结合链接和内容信息的 PageRank 算法，去掉了 PageRank 算法的先决条件 2，并考虑了用户直接从网页到一个间接相邻但与内容相关的另一个网页的情况[3]。斯坦大学计算机科学系的Taher Haveliwala提出了Topic-sensitive PageRank算法[4]。斯坦福大学计算机科学系的Arvind Arasu等人已经证明PageRank算法的计算效率可以得到很大的提高[22]。

　　２. 2HITS 算法及其变体

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

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

　　2.基于商业或竞争的考虑，很少有网页指向竞争领域的权威网页。

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

　　可以看出，平均分配权重不符合链路的实际情况[17]。J. Kleinberg [5] 提出的 HITS 算法引入了另一种类型的网页，称为 Hub 网页。Hub 网页是提供权威网页链接集合的网页。它，但 Hub 页面确实提供了指向某个主题的最重要站点的链接集合，而不是课程主页上的推荐参考列表。一般来说，一个好的Hub网页指向很多好的权威网页；一个好的权威网页是一个有很多好的Hub网页指向的WEB页面。Hub和Authoritive网页之间的这种相辅相成的关系可以用于权威网页的发现和WEB结构和资源的自动发现。

　　２.２.１HITS算法

　　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指向，它的权限值会相应增加（即权限值增加到所有web的现有Hub值之和）指向它的页面。公式（2)反映了如果一个网页指向很多好的权威页面，Hub值会相应增加（即Hub值增加到权威值的总和链接到该网页的所有网页）。

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

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

　　２.２.2HITS问题

　　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-linked TKC（Tightly-Knit Community Effect）的现象[8]。如果集合T中有几个网页与查询主题无关，但联系紧密，那么HITS算法的结果可能就是这些网页，因为HITS只能找到主社区，偏离了原创查询主题。TKC 问题在下面讨论的 SALSA 算法中解决。

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

　　２.２. 3 个 HITS 变体

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

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

　　对于上面提到的 HITS 遇到的第二个问题，Monika R. Henzinger 和 Krishna Bharat 在 [7] 中做了改进。假设主机 A 上有 k 个网页指向主机 B 上的某个文档 d，则 A 上的 k 个文档对 B 的权限的贡献值为 1，每个文档贡献 1/k 而不是每个文档贡献 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的相似度计算公式如下：

　　,, = 词条 i 在查询 Q 中出现的次数，

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

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

　　在这种改进的算法中，计算文档相似度的时间成本会非常大。

　　２.２.３. 2ARC 算法

　　IBM阿尔马登研究中心的Clever工程组提出了ARC（Automatic Resource Compilation）算法，对原有的HITS进行了改进。页面集对应的链接矩阵的初始值与链接的锚文本相结合，以适应不同链接权重不同的情况。

　　ARC算法和HITS的区别主要有以下3点：

　　1、从根集S扩展到T时，HITS只扩展根集网页链接路径长度为1的网页，即只扩展与S直接相邻的网页，增加扩展链接长度在 ARC 中为 2。页面集称为Augment Set（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的转置矩阵，迭代执行以下3个操作：

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

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

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

　　艾伦鲍罗丁等。[11]中指出了一个现象。有M+1 Hub网页和M+1权威网页。前M个Hub指向第一个权威网页，第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（Hub-Averaging-Kleinberg）算法。

　　２.２.３.4 阈值（Threshhold—Kleinberg）算法

　　艾伦鲍罗丁等。在[11]中同时提出了三种阈值控制算法，分别是Hub阈值算法、权限阈值算法和两者结合的全阈值算法。

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

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

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

　　２.３SALSA算法

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

　　具体算法如下：

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

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

　　Vh = {sh | s∈C and out-degree(s)> 0} (G'的Hub侧)。

　　VA = {sa | s∈C and in-degree(s)> 0} (G'的权威侧)。

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

　　这定义了 2 个链，Authority 链和 Hub 链。

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

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

　　5、A中值最高的对应网页就是您要查找的重要网页。

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

　　在实际应用中，SALSA 在扩展根集时忽略了很多不相关的环节，例如

　　1. 同一站点内的链接，因为这些链接大部分只是为了导航。

　　2. CGI 脚本链接。