网页抓取解密(GooglePageRank算法的基本原理推导和基本原理算法策略)

　　网页抓取解密(GooglePageRank算法的基本原理推导和基本原理算法策略)

　　一、PageRank

　　PageRank算法是最著名的搜索引擎谷歌采用的一种算法策略。它根据每个网页的超链接信息计算一个网页的权重，以优化搜索引擎的结果。，由拉里佩奇提出。

　　简单的说，PageRank算法计算每个网页的综合得分，即如果网页A链接到网页B，网页B当然会加一分。不同的链接网页有不同的指向网页的点。一个页面的分数是通过递归算法得到所有链接到它的页面的重要性的。

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

　　PR(A) = (1-d) + d*(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

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

　　T1、T2、...、Tn 指的是页面 A 的链接页面。

　　PR(Ti)是指网页Ti(i=1, 2, ..., n)的PR值。

　　C(Ti)指的是网页Ti(i=1, 2,..., n)之外的链接数。

　　D为衰减因子，0 由上式可知，影响网页PR值的主要因素如下：

　　（1）此页面的链接数。

　　（2） 链接到网页本身的网页的 PR 值。

　　（3）网页本身的链接数。

　　根据以上分析可以判断：一个网页的链接数越多，这些链接网页的PR值就越高，而来自这些网页的链接数越少，该网页的PR值就越高.

　　谷歌为每个网页分配一个初始PR值（1-d），然后使用PageRank算法收敛计算其PR值。

　　网页的link-in和link-out关系一直在变化，所以PR值也需要更新，可以用定时任务反复计算后更新，使网页最终PR值达到平衡和稳定的状态。

　　Google的查询过程如下：首先根据用户输入的查询，关键词尽可能匹配网页数据库中的网页，然后根据用户自己的PR排名将匹配的网页呈现给用户.

　　此外，网页在搜索结果列表中的位置还与很多其他因素有关，例如搜索词在网页中的位置。

　　PageRank的缺陷是没有考虑链接的价值，更适合一般搜索引擎，但对于主题相关的垂直搜索引擎来说不是一个好的策略。

　　二、命中

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

　　HITS（Hyperlink Induced Topic Search）算法是经典的主题信息提取策略，可以提高垂直精度。

　　1、原理

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

　　(1）权威页面

　　一个网页被多次引用，可能很重要；一个网页虽然没有被多次引用，但是被重要的网页引用，也可能很重要；网页的重要性均匀地转移到它指的是网页。此类页面称为权威页面。

　　(2）中心网页

　　提供权威页面链接集合的网页本身可能并不重要，或者指向它的页面很少，但它提供了到某个主题的最重要站点的链接集合。这种类型的页面称为 Hub 网页。

　　(3）算法思想

　　首先，使用通用搜索引擎获取网页的初始子集I。当然，I中的页面与用户的查询条件非常相关。然后将I所指向的网页和I所指向的网页收录起来构成一个基本集合E。E中的每个页面都有一个权限权重和一个枢纽权重，分别用a和h表示。a 值代表网页和查询条件相关的程度，h 反映了页面链接到相关页面的程度。a=(a1, a2, ..., an) 和 h=(h1, h2, ..., hn) 分别表示 E 中所有网页的权威和中心向量。 初始设置所有 ai 和 hi 为 1 ，并且然后使用以下公式计算：

　　

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

　　

　　迭代计算 a 和 h 直到收敛。这样，我们专注于ATA和AAT。最后，按照authority和hub值排序，选择a和h的值大于阈值M的网页。

　　如果一个网页被很多好的hub指向，它的权威值会相应增加；如果一个网页指向很多好的权威页面，那么hub值也会相应增加。HITS 算法的最终输出是一组具有较大中心值的网页和具有较大权限值的网页。

　　2、缺陷

　　HITS算法在提高一定垂直精度的同时，也存在以下不足：

　　（1）HITS 算法忽略了网页内容的差异，给每个链接的网页分配了相同的权重常数，因为每个网页都会有一些不相关的链接网页，比如广告链接，而这些不相关的网页和相关网页平等对待它们很容易导致主题漂移。

　　（1）在url集合E的开头，也把I初始集合中网页的一些不相关的链接加到了E中，增加了不必要的下载量，导致更多不相关的网页参与计算. 对精度有一定影响。

　　3、改进

　　改进方向如下：

　　(1）主题漂移

　　(2）下载过滤器