1. 前言
这系列的文章主要讲述2006年评出的数据挖掘10大算法(见图1)。文章的重点将偏向于算法的来源以及算法的主要思想,不涉及具体的实现。如果发现文中有错,希望各位指出来,一起讨论。
图1 来自IDMer的文章
在这些算法中,最引人注目的自然是Google的核心技术之一——PageRank。因此本系列就先来探索PageRank的诞生过程。
2. 核心思想
常言道,看一个人怎样,看他有什么朋友就知道了。也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。将这个知识迁移到网页上就是“被越多优质的网页所指的网页,它是优质的概率就越大”。
PageRank的核心思想就是上述简单却有效的观点。由这个思想,可以得到一个直观的公式:
(1)
R(x)表示x的PageRank,B(x)表示所有指向x的网页。
公式(1)的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。粗看之下,公式(1)将核心思想准确地表达出来了。但仔细观察就会发现,公式(1)有一个缺陷:无论J有多少个超链接,只要J指向I,I都将得到与J一样的重要性。当J有多个超链接时,这个思想就会造成不合理的情况。例如:一个新开的网站N只有两个指向它的超链接,一个来自著名并且历史悠久的门户网站F,另一个来自不为人知的网站U。根据公式(1),就会得到N比F更优质的结论。这个结论显然不符合人们的常识。
弥补这个缺陷的一个简单方法是当J有多个超链接(假设个数为N),每个链接得到的重要性为R(j)/N。于是公式(1)就变成:
(2)
N(j)表示j页面的超链接数
图2 来自Lawrence Page的文章
从图2可以看出,如果要得到N比F更优质的结论,就要求N得到很多重要网站的超链接或者海量不知名网站的超链接。而这是可接受的。因此可以认为公式(2)将核心思想准确地表达出来了。为了得到标准化的计算结果,在公式(2)的基础上增加一个常数C,得到公式(3):
(3)
3. 计算
由公式(3)可知,PageRank是递归定义的。换句话就是要得到一个页面的PageRank,就要先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过,如果有办法得到合理的PageRank初始值,还需要这个算法吗?或者说,这个严重依赖于初始值的算法有什么意义吗?
依赖于合理初始值的PageRank算法是没意义的,那么不依赖于初始值的PageRank算法就是有意义的了。也就是说,如果存在一种计算方法,使得无论怎样设置初始值,最后都会收敛到同一个值就行了。要做到这样,就要换一个角度看问题,从线性代数的角度看问题。
将页面看作节点,超链接看作有向边,整个互联网就变成一个有向图了。此时,用邻接矩阵M表示整个互联网,若第I个页面有存在到第J个页面的超链接,那么矩阵元素m[i][j]=1,否则m[i][j]=0。对于图3有
矩形M={ 0, 1, 1, 0,
0, 0, 0, 1,
1, 0, 0, 0,
1, 1, 1, 0}
图3
观察矩阵M可发现,M的第I行表示第I个网页指向的网页,M的第J列表示指向J的网页。如果将M的每个元素都除于所在行的全部元素之和,然后再将M转置(交换行和列),得到MT。MT的每一行的全部元素之和不就正好是公式(3)中的 吗?例如图3可以得到这样的矩阵:
MT={ 0, 0, 1, 1/3,
1/2, 0, 0, 1/3,
1/2, 0, 0, 1/3,
0, 1, 0, 0 }
将R看作是一个N行1列的矩阵,公式(3)变为
R = C MT R (4)
在公式(4)中,R可以看作MT的特征向量,其对应的特征值为C(看不明白这句话,可以回忆下线性代数中对特征向量的定义——对于矩阵A,若存在着列向量X和一个数c,使得AX=cX,则X称为A的特征向量,c称为A的特征值)。幂法(power method)计算主特征向量与初始值无关,因此只要把R看作主特征向量计算,就可以解决初始值的合理设置问题。
幂法得到的结果与初始值无关,是因为最终都会收敛到某个值。因此使用幂法之前,要确保能够收敛。但是,在互联网的超链接结构中,一旦出现封闭的情况,就会使得幂法不能收敛。所谓的封闭是指若干个网页互相指向对方,但不指向别的网页,具体的例子如图4所示:
图4 来自Soumya Sanyal的PPT
上图4个绿色网页就是封闭情况。这种情况会使得这些网页的PageRank在计算的时候不断地累加,从而使得结果不能收敛。仔细研究就会发现红色网页的PageRank给了绿色网页后,绿色网页就将这些PageRank吞掉了。Larry Page将这种情况称为Rank Sink。
如果沿着网页的链接一直点下去,发现老是在同样的几个网页中徘徊,会怎么办?没错,把当前页面关掉,再开一个新的网页。上述情况正好与Rank Sink类似,也就意味着可以借鉴这个思想解决Rank Sink。因此,在公式(3)中的基础上加一个逃脱因子E,得到:
(5)
E(i)表示第i个网页的逃脱因子
将(5)变成矩阵形式,可得:
R = C MT R + CE = C( MT R + E )
其中列向量R的1范数(即R的全部矩阵元素相加)为1
将上式重写为
R = C( MT + E * 1 ) R (6)
1是指一行N列的行向量,且每个元素都是1
在公式(6)中,只要将R看作(MT + E * 1)的特征向量,就可以同时解决初始值设置问题和封闭的情况。
4. 资料共享
找资料是简单的事,但要找到好资料就不那么容易了。因此,这一小节是分享我找到的一些比较好的资料。
1. PageRank之父的文章: The PageRank Citation Ranking Bringing Order to the Web
http://ilpubs.stanford.edu:8090/422/
2. 一个对PageRank进行解释的PPT,讲解得很好: The PageRank Citation Ranking – Redone
http://wenku.baidu.com/view/30657568a98271fe910ef975.html?from=related
3. 不错的PageRank科普文: Google 的秘密- PageRank 彻底解说 中文版
http://www.kreny.com/pagerank_cn.htm
4. 本文所用到的线性代数相关知识
http://ceee.rice.edu/Books/LA/eigen/
分享到:
相关推荐
### Google的PageRank算法详解 #### 一、PageRank算法概念与起源 PageRank是Google搜索引擎的核心算法之一,由Google的创始人Larry Page和Sergey Brin在斯坦福大学研究期间提出。该算法的主要目的是通过对网页之间...
在"Google PageRank算法挖掘重要物理文献"这一主题中,我们可以深入探讨PageRank如何应用于物理学领域的文献检索和知识发现。 首先,理解PageRank的基本原理至关重要。PageRank算法将每个网页视为网络中的一个节点...
首先,PageRank算法是Google早期用来评定网页重要性的一种算法。它的基本思想是将互联网视为一个有向图,页面间通过超链接相互关联。在这种视角下,PageRank算法为每一个网页赋予一个反映其重要性的数值,即PageRank...
PageRank算法,作为谷歌的核心算法之一,自问世以来便在信息检索领域占据了举足轻重的地位。它通过深入挖掘网络中网页之间的链接关系,评估网页的重要性,从而为用户提供更高质量的搜索结果。本文将详细介绍PageRank...
总的来说,PageRank算法是理解和应用大数据分析的一个重要组成部分,尤其是在网络数据挖掘和搜索引擎优化中。通过Python实现PageRank,并在大数据环境下进行优化,不仅可以提高计算效率,还能为实际的网页排名问题...
PageRank算法是搜索引擎技术中的重要算法之一,由Google公司的联合创始人Sergey Brin和Lawrence Page于1998年提出。该算法基于一种重要的理念:一个网页的重要性可以通过其它网页对它的引用次数来评估。简单来说,...
在“PageRank分值计算 Python爬虫 数据挖掘实验”中,我们将深入探讨这三个关键概念,并结合华南理工大学的实践教学,了解如何运用Python爬虫获取网页数据,然后通过数据挖掘技术来实施PageRank算法。 首先,让我们...
PageRank算法是一种基于网页链接结构的重要性评估方法,最初由谷歌创始人拉里·佩奇(Larry Page)和谢尔盖·布林(Sergey Brin)在斯坦福大学期间开发。该算法利用网页间的链接关系来衡量网页的重要性,对于搜索...
Google的PageRank算法通过分析网页间的链接关系,为每个网页分配一个数值,以此来衡量其重要性。尽管PageRank算法在实际应用中取得了显著效果,但它也存在一些局限性,如主题漂移和对旧网页的过度偏重。 主题漂移是...
pagerank算法是Google创始人拉里·佩奇和谢尔盖·布林提出的一种评估网页重要性的数学模型,它在搜索引擎优化(SEO)和数据挖掘领域具有广泛应用。该算法基于网络的链接结构,认为一个被很多高质量网页链接的网页...
下面我们将深入探讨PageRank算法以及其在数据挖掘领域的应用。 PageRank算法的核心思想是:一个网页被其他高质量网页链接的次数越多,其PageRank值就越高。PageRank值的计算通常涉及以下步骤: 1. **初始化**:每...
pagerank算法是Google创始人拉里·佩奇和谢尔盖·布林提出的一种评估网页重要性的数学模型,它在搜索引擎优化(SEO)和网络分析中起着关键作用。本项目提供了一个基于Java实现的无向图和加权图的PageRank算法版本,...
在本实验中,我们将使用MATLAB这一强大的数学计算工具来实现Pagerank算法,这对于数据挖掘、网络分析等领域具有重要意义。 一、 Pagerank算法简介 Pagerank算法的核心思想是:一个被许多高质量网页链接的网页具有更...
此外,PageRank 算法也广泛应用于信息检索、数据挖掘、社交网络分析等领域。 结论 ---- PageRank 算法是一种评估网页重要性的算法,其思想是:被越多优质的网页所指的网页,它是优质的概率就越大。 PageRank 算法...