万维网中的搜索.pptx

万维网上有很多公共搜索引擎依靠在万维网上搜集到的静态文字索引进行搜索,这个索引通常是由一种称作搜索机器人或者蜘蛛的程序自动搜集的。
1. PageRank算法
2. HITS算法
PageRank算法
PageRank算法由斯坦福大学Brin 和Page1998年提出
应用:Google搜索引擎中。
PageRank使用索引中网页入度分布的图论分析法,再与以文字排列为基础的启发式方法结合起来。因此,索引中不但要存储搜集到的网页的文字信息,还要存储网页间的链接结构,也就是网页的图形结构。
该算法的主要思想是根据每个网页的链入链接数对它们进行相关性或普及性层次分配:当当网页vj有一个链接指向网页vi时,就认为网页vi获得了一定的分数,该分值的多少取决于网页vj的重要程度,即网页vj的重要性越大,网页vi获得的分数就越高。
PageRank算法
对于某个互联网网页A来说,该网页PageRank的计算基于以下两个基本假设:      数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要。     质量假设:指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A,则页面A越重要。
PageRank算法
简单算法是,将某个页面的 PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的 PageRank 相加,即得到了被链接的页面的 PageRank。
PageRank算法
计算过程
PageRank算法
A = [ 0, 1, 1, 1, 1, 0, 1;
1, 0, 0, 0, 0, 0, 0;
1, 1, 0, 0, 0, 0, 0;
0, 1, 1, 0, 1, 0, 0;
1, 0, 1, 1, 0, 1, 0;
1, 0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 1, 0, 0; ]
PageRank 式的推移概率行列 M ,是将 A 倒置后将各个数值除以各自的非零要素之和后得到的。
M = [ 0, 1, 1/2, 0, 1/4, 1/2, 0 ;
1/5, 0, 1/2, 1/3, 0, 0, 0;
1/5, 0, 0, 1/3, 1/4, 0, 0;
1/5, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 1/3, 0, 1/2, 1;
0, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 0, 0, 0, 0; ]
PageRank算法
表示 PageRank 的矢量 R (各个的页面的等级数的队列),存在着 R = cMR 的关系(c 为定量)。在这种情况下,R 相当于线形代数中的特征向量,c 相当于对应特性值的倒数。为了求得 R ,只要对这个正方行列 M 作特性值分解就可以了。
EigenVector = [





]
PageRank =






PageRank算法
PageRank算法
修正PageRank计算公式
 由于存在一些出链为0,也就是那些不链接任何其他网页的网, 也称为孤立网页,使得很多网页能被访问到。因此需要对 PageRank公式进行修正,即在简单公式的基础上增加了阻尼系数(damping factor)q, q一般取值q=。
是pj 链出页面的数量,而N是所有页面的数量。
PageRank值是一个特殊矩阵中的特征向量。这个特征向量为:
PageRank算法
R是如下等式的一个解: