pagerank:数据挖掘领域十大经典算法:PageRank算法

 2021-06-29 23:36    77  

佩奇排名(PageRank)pagerank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

pagerank:数据挖掘领域十大经典算法:PageRank算法

pagerank:数据挖掘领域十大经典算法:PageRank算法

简介

pagerank:数据挖掘领域十大经典算法:PageRank算法

佩奇排名(PageRank),又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名pagerank。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。

pagerank:数据挖掘领域十大经典算法:PageRank算法

PageRank通过网络浩瀚的超链接关系来确定一个页面的等级pagerank。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

pagerank:数据挖掘领域十大经典算法:PageRank算法

基本思想

pagerank:数据挖掘领域十大经典算法:PageRank算法

假设网页T存在一个指向网页A的连接,则表明T的全部者觉得A比較重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/L(T)

pagerank:数据挖掘领域十大经典算法:PageRank算法

当中PR(T)为T的PageRank值,L(T)为T的出链数

pagerank:数据挖掘领域十大经典算法:PageRank算法

则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

pagerank:数据挖掘领域十大经典算法:PageRank算法

即一个页面的得票数由全部链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由全部链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反假设一个页面没有不论什么链入页面,那么它没有等级。

pagerank:数据挖掘领域十大经典算法:PageRank算法

算法原理

1 )普遍情况

首先,PageRank算法预先给每个网页一个PR值(PR值指代PageRank值),PR值在物理意义上为一个网页被访问的概率,所以一般是1/N,其中N为网页总数。

另外,所有网页的PR值的和一般为1。(如果实在不为1也不是不行,最后算出来的不同网页之间PR值的大小关系仍然是正确的,只是这个数值不能直接地反映概率罢了。)

接着,运用下面的算法不断迭代计算,直至达到平稳分布为止。

迭代算法到底是如何进行的呢?下面我们给出一个具体的例子:

互联网中的众多网页可以看成一个有向图,箭头的指向即为链接的链入,如下图所示有4个网页:

根据上图,我们可以得到A的PR值为:

但是从图中可以看出,除了C只有A这一个出口外,B和D都不止一个出口,所以上面的那个公式并不是非常正确。举个实际的例子,一个用户正在浏览网页B,那么接下来他去往网页A和网页D的概率在统计学上应该是一样的,所以A的PR值应该表示为:

2) 特殊情况(没有出链)

网络中不乏一些没有出链的网页,如下图:

其中,网页C没有出链,也就是说网页C对其他网页没有PR值的贡献,我们不喜欢这种“自私”的网页(其实是为了满足 Markov 链的收敛性),于是设定其对所有网页(包括它自己)都有出链,则此图中A的PR值表示为:

3) 特殊情况(出链循环圈)

网络中还存在这样的网页:只对自己有出链,或者几个网页的出链形成一个循环圈。那么在不断迭代的过程中,这一个或几个网页的PR值将只增不减,这显然是不合理的。

如下图中的C就只对自己有出链:

那么如何解决这个问题呢?我们假设某人正在浏览网页C,显然他不会一直停留在网页C,他可能会随机地输入一个网址从而去往另一个网页,并且其跳转到每个网页的概率是一样的。

于是此图中A的PR值表示为:

综上,一般情况下,一个网页的PR值计算公式如下:

其中,Mpi是所有对pi网页有出链的网页集合,L(pj)是网页pj的出链数目,N是网页总数,α一般取0.85。

根据上面的公式,我们就可以计算出每个网页的PR值,在不断迭代并趋于平稳的时候,即为最终结果。

PageRank算法优缺点

长处:

是一个与查询无关的静态算法,全部网页的PageRank值通过离线计算获得;有效降低在线查询时的计算量,极大降低了查询响应时间。

缺点:

1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性减少

2)旧的页面等级会比新页面高。由于即使是非常好的新页面也不会有非常多上游链接,除非它是某个网站的子网站。

成都加米谷教育,专注于大数据人才培养,9月下旬数据分析与挖掘培训班新课正在火热咨询报名中,大数据开发新课咨询中,中秋国庆特惠学员活动,详情见微头条!

本文标签:算法数据挖掘

原文链接:https://www.xgfox.com/alpx/76.html

本文版权:如无特别标注,本站文章均为原创。