Google搜索背后的PageRank算法

pagerank-feature

进入互联网时代以来,搜索引擎已经是人们离不开的东西,每当遇到问题,就要去请教搜索引擎,搜索引擎会根据你输入的关键字来返回成千上万的结果,但是,互联网上的资源是异常丰富的,搜索引擎是怎么样把用户真正想要的结果排在最前面呢?这个问题很大程度上决定了搜索引擎的质量,Google不会像百度那样把交了广告费八竿子达不到的东西排在最前面,给用户造成误解,这篇文章将会介绍Google的PageRank网页排名技术。

总体来说,对于一个搜索引擎,搜索结果的排名先后主要取决于两个信息他们分别是:网页的质量信息,以及查询关键字与网页的相关信息。其中,网页的质量信息就需要用到PageRank网页排名技术来实现,而关键字相关则需要用到TF-IDF算法,以后我将会专门写一篇博客。

PageRank算法的出现时革命性的,这个技术在1998年发明之后使得搜索技术有了质的飞跃,比较圆满的解决的了网页搜索结果中排序不理想的问题,这个技术也带来了Google的成功。

说了这么多,到底PageRank算法是什么原理呢,其实也没有什么神秘的地方,说的通俗一点就是民主表决,假如我在人群中说要寻找Steve Jobs,可能会有50个人举手。那么谁是真的呢?是会有好多人叫做Steve Jobs,可是哪一个是大家真正想要找的那个人呢,如果大家都说要找的是那个Apple公司的Steve Jobs,那么他就是大家真正要找的。

也就是说,在互联网中,如果一个网页被其他网页所连接,说明这个网页收到了普遍的承认和对待,那么他的排名就越高。即一个页面的得票数由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。这也就是为什么我们这些小型博客网站的博主或者其他一些网站总是有一些友情链接版块,就是为了形成一张网,让自己的网页收到普遍承认。这就是PageRank技术的核心思路,当然实际实现起来要比这个复杂得多。

但是对于不同的网页要区别对待,也就是说,一个网页的不同外链的权重是不一样的,因为如果外链本身排名就很高,更可靠,所以说要给这些链接较大的权重。就和股东大会表决一样,拥有20%股份的股东说话的分量肯定比拥有1%股东的人说的话更有分量。

所以说,在Google上搜索一个陌生的词,第一个跳出来的网页往往是Wikipedia,这就是因为维基百科被大部分用户看过,他的排名很高,PageRank认为Wiki的内容更加可靠,是用户想要找的。对于一个产品的名字,比如iPhone,出来的第一个应该是Apple的官网,之后可能是Wiki之类的,可以看出,这个算法的高明之处就是他把整个互联网当做一个整体来对待,很早以前,引擎会把每个网页当做独立个体来看,因为当时设计者们只是注重了网页内容,和查询相关性,并没有在意网页的质量,忽略了网页之间的关系。

现在来举一个例子,根据上面所描述的,网页A的排名应该取决于只想这个网页的其他网页的数量和他们各自的权重,比如网页A分别有B1,B2,B3,B4,B5指向他,那么A的排名就是这5个网页排名的权重之和。

Page-Rank

A的排名 = 0.01+0.05+0.37+0.12+0.14 = 0.69

那么问题来了,网页B1到B5的权重也应该是他们自身的权重,那么,对搜索结果的排名要用到结果自身的排名,这不就成了先有鸡还是先有蛋的问题了么。。。

要解决这个问题,需要将PageRank转换成一个二维矩阵项城的问题 (后面会介绍),并且使用迭代方法。假设所有的网页的排名都是相同的,都有一个初始值,第一次迭代,根据信这个初始值算出各个网页第一次的迭代排名,之后根据第一次的迭代排名,算出来第二次的,这个算法保证了网页排名的估计经过数次迭代后收敛成为网页排名的真实值,并且,这种做法并不需要任何人工干预。

现在来说下具体的计算方法,用到线性代数的知识:

假设矩阵A是网页之间链接的数目,A比如Amn代表第m个网页指向第n个网页的链接数,也就是说一个横排上的所有元素就是当前网页指向外链的排名。

matA

假设向量

B = (b1, b2, b3, b4 … bN)

代表第1,第2,到第N个网页的网页排名,就和A矩阵中的一横排一样。

在A和B中,A是一个已知的矩阵,B是未知的,使我们需要通过计算来得到的。

假设B(i)是第i次迭代的结果,那么:

B(i) = A * B(i-1)

在一开始,假设所有网页排名都是 1/n

B(0) = (1/n, 1/n ….. 1/n)

通过上面的迭代公式,就可以求出B1, B2 …. Bi, 最后Bi会手链,当Bi和B(i-1)之间的差异非常小的时候停止迭代运算,此时 B 差不多等于 B*A。

但是由于网页之间链接数量比互联网中的要稀疏得多,所以要对零概率或者小概率事件做一些平滑处理,要用到一个常数α。之后,迭代公式变为。

iteration-formula

其中n是互联网中网页的数量,α是一个较小的常数,I是单位矩阵。α一般都用0.85

以上就是PageRank的简介,具体实现的话还需要还需要用到其他一些技术,因为互联网中网页数量是巨大的,二次矩阵A的元素数量将是一个互联网网页总和数量平方数量元素的矩阵,一台服务器是无法完成这么庞大的计算的,需要用到Map Reduce 来使用多台服务器进行并行运算, Map Reduce技术同样也是现今众多大数据处理程序的核心思想、

现今,Google等搜索引擎比当初要复杂,要完善,但是PageRank在Google的众多算法中至关重要的,也被公认为文献检索中最大的贡献之一。

 

MikeTech现已登陆iPhone和Android

iPhone版下载
Android版下载

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *