1 page ranking 使用的是图的随机游走算法,
这是Google的创始人Page的方法,中间的转化步骤是用一步马尔科夫状态转移方程
进行的,马尔科夫状态转移方程有遍历态,有两种情况,一种情况是稳定态,一种是奇异态,
区别是转移节点的分类,当节点集合中有子集是闭集,转到这些节点中后,就不能在出来了
【0,0.5,0.5,0
0, 0, 0, 1
0, 0, 0, 1
1, 0, 0, 0】
然后一步右乘一次上面的方程,可以达到稳定的状态,就是任意两个节点,
当达到了稳定状态,两个节点之间的转移概率就稳定了,这样就可以使用在半监督分类
和聚类方法。
This is PageRank:external image 0ef2112463f96b0dc89559b9.jpg

下面是PageRank方法的初衷:

pagerank原理  

通过对由超过 50,000 万个变量和 20 亿个词汇组成的方程进行计算,PageRank 能够对网页的重要性做出客观的评价。PageRank 并不计算直接链接的数量,而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样,PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。

此外,PageRank 还会评估每个投票网页的重要性,因为某些网页的投票被认为具有较高的价值,这样,它所链接的网页就能获得较高的价值。重要网页获得的 PageRank(网页排名)较高,从而显示在搜索结果的顶部。Google 技术使用网上反馈的综合信息来确定某个网页的重要性。搜索结果没有人工干预或操纵,这也是为什么 Google 会成为一个广受用户信赖、不受付费排名影响且公正客观的信息来源。

其实简单说就是民主表决。打个比方,假如我们要找李开复博士,有一百个人举手说自己是李开复。那么谁是真的呢?也许有好几个真的,但即使如此谁又是大家真正想找的呢?:-) 如果大家都说刚从 Google 离职的那个是真的,那么他就是真的。

在互联网上,如果一个网页被很多其它网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。这就是 Page Rank 的核心思想。 当然 Google 的 Page Rank 算法实际上要复杂得多。比如说,对来自不同网页的链接对待不同,本身网页排名高的链接更可靠,于是给这些链接予较大的权重。Page Rank 考虑了这个因素,可是现在问题又来了,计算搜索结果的网页排名过程中需要用到网页本身的排名,这不成了先有鸡还是先有蛋的问题了吗?

Google 的两个创始人拉里·佩奇 (Larry Page )和谢尔盖·布林 (Sergey Brin) 把这个问题变成了一个二维矩阵相乘的问题,并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的,并且根据这个初始值,算出各个网页的第一次迭代排名,然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。值得一提的事,这种算法是完全没有任何人工干预的。

理论问题解决了,又遇到实际问题。因为互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页,那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘,计算量是非常大的。拉里和谢尔盖两人利用稀疏矩阵计算的技巧,大大的简化了计算量,并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中,进一步缩短了计算时间,使网页更新的周期比以前短了许多。

网页排名的高明之处在于它把整个互联网当作了一个整体对待。它无意识中符合了系统论的观点。相比之下,以前的信息检索大多把每一个网页当作独立的个体对待,很多人当初只注意了网页内容和查询语句的相关性,忽略了网页之间的关系。

今天,Google 搜索引擎比最初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界, 这个算法被公认为是文献检索中最大的贡献之一,并且被很多大学引入了信息检索课程 (Information Retrieval) 的教程。

Page rank算法

基本思想:如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/C(T)其中PR(T)为T的PageRank值,C(T)为T的出链数,则A的PageRank值为一系列类似于T的页面重要性得分值的累加。优点:是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。

不足:人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低;另外,PageRank有很严重的对新网页的歧视。

Topic-Sensitive PageRank

(主题敏感的PageRank)

基本思想:针对PageRank对主题的忽略而提出。核心思想:通过离线计算出一个PageRank向量集合,该集合中的每一个向量与某一主题相关,即计算某个页面关于不同主题的得分。主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定。

优点:根据用户的查询请求和相关上下文判断用户查询相关的主题(用户的兴趣)返回查询结果准确性高。

不足:没有利用主题的相关性来提高链接得分的准确性。

Hilltop

基本思想:与PageRank的不同之处:仅考虑专家页面的链接。主要包括两个步骤:专家页面搜索和目标页面排序。

优点:相关性强,结果准确。

不足:专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性,而专家页面的质量和公平性难以保证;忽略了大量非专家页面的影响,不能反应整个Internet的民意;当没有足够的专家页面存在时,返回空,所以Hilltop适合对于查询排序进行求精。