解密搜索引擎技术之排序算法

一、PageRank

算法PageRank是***的搜索引擎Google采用的一种算法策略，是根据每个网页的超级链接信息计算网页的一个权值，用于优化搜索引擎的结果。由拉里-佩奇提出。

简单说，PageRank算法是计算每个网页的综合得分数，即假如网页A链向网页B，则网页B加一分，当然。不同链接网页对于指向网页的加分也是不同的，一个页面的得分情况是由所有链向它的页面的重要性经过递归算法得到的。

PageRank算法的基本原理推导如下：

PR(A) = (1-d) + d*(PR(T₁ )/C(T₁ ) + … + PR(T_n )/C(T_n ))

其中，PR(A)是指网页A的PR值。

T_1， T_2， …，T_n 是指网页A的链入网页。

PR(T_i )是指网页T_i 的PR值（i=1，2，…，n）。

C(T_i )是指网页T_i 的链出数量（i=1，2，…，n）。

D是一个衰减因子，0<d<1，通常取值为0.85。

从以上公式可以看出，影响一个网页PR值的主要因素如下：

• （1）该网页的链入数量。
• （2）该网页的链入网页本身的PR值。
• （3）该网页的链入网页本身的链出数量。

根据上面分析可以判断：一个网页的链入数量越多，这些链入网页的PR值越高，这些网页本身的链出数量越少，则该网页的PR值越高。

Google给每一个网页都赋予一个初始PR值（1-d），然后利用PageRank算法收敛计算其PR值。

网页的链入链出关系，时刻都在变化，那么PR值也需要更新，可以用定时任务重复计算后更新，使得网页的最终PR值达到一个均衡稳定的状态。

Google的查询过程是这样的：首先根据用户输入的查询关键词对于网页数据库中的网页尽情匹配，然后对于匹配到的网页按照其本身的PR排序呈献给用户。

此外，一个网页在检索结果列表中的位置还与其它很多因素相关，比如检索词在网页中的位置等。

PageRank的缺陷在于不考虑链接的价值，这对通用搜索引擎比较合适，但对主题相关的垂直搜索引擎而言并不是很好的策略。

二、HITS

PageRank算法对于向外链接的权值贡献是平均的，即不考虑不同链接的重要性，但是页面链接中可能某些是广告、导航或者注释链接，平均权值显然不太符合实际情况。

HITS（Hyperlink Induced Topic Search）算法则是一种经典的专题信息提取策略，能够提高垂直查准率。

1、原理

HITS算法由Jon Kleinberg提出，其对每个网页都要计算两个值：权威值（authority）和中心值（hub）。

（1）权威网页

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

（2）Hub网页

提供指向权威网页的链接集合的Web网页，它本身可能并不重要，或者说没几个网页指向它，但是它提供了指向就某个主题而言最为重要的站点的链接集合，这种网页叫做Hub网页。

（3）算法思想

首先利用通用搜索引擎得到一个网页的初始子集I，当然I内的页面都是和用户查询条件有很大相关性。然后把I指向的网页和指向I的网页都包含进来，形成基础集合E，E中的每个页面都具有一个authority权值和hub权值，分别记作a和h，a值表示网页与查询条件相关度的高低，h反应的是该页面链出相关度页面的多少情况。a=(a₁ , a₂ , …, a_n )和h=(h₁ , h₂ , …, h_n )代表E中所有网页的authority和hub向量，初始时把所有的a_i 和h_i 都设置为1，然后利用下面的公式进行计算：

其中，B(i)和F(i)分别表示指向该网页的网页链接集合和该网页指向的网页链接集合。用n*n的矩阵A表示集合E的网页节点间的连接，如果节点i和节点j之间有连接，则A[i,j]=1，则A[i,j]=0，因此，上面公式可以表示为：

迭代计算a和h，直至收敛。这样我们集中求A^T A和AA^T 。***按照authority和hub值排序，将a和h值大于阈值M的网页挑出来。

若一个网页由很多好的hub指向，则其权威值会相应增加；若一个网页指向很多好的权威页，则hub值也会相应增加。HITS算法***输出的一组具有较大hub值的网页和具有较大权威值的网页。

2、缺陷

HITS算法在提高一定的垂直查准率的同时，也存在如下缺陷：

（1）HITS算法忽略了网页内容的差异，对于每个链接网页赋予相同的加权常数，因为每个网页中都会有一些广告链接等非相关的链接网页，这些非相关网页和相关网页同等对待，会容易产生主题漂移现象。

（2）在开始形成url集合E中，对于初始集合I中网页的一些非相关链接也加入到E中，增加了无谓的下载量，也致使后边更多的无关网页参与到了计算，对准确率存在一定的影响。

3、改进

改进方向如下：

（1）主题漂移

（2）下载过滤