智能算法——PageRank

一、PageRank的基本概念

1、PageRank的概念

PageRank,即网页排名算法,又称为网页级别算法,是由佩奇和布林在1997年提出来的链接分析算法。PageRank是用来标识网页的等级、重要性的一种方法,是衡量一个网页的重要指标。PageRank算法在谷歌的搜索引擎中对网页质量的评价起到了重要的作用,在PageRank算法提出之前,已经有人提出使用网页的入链数量进行链接分析,但是PageRank算法除了考虑入链数量之外,还参考了网页质量因素,通过组合入链数量和网页质量因素两个指标,使得网页重要性的评价更加准确。

    在搜索中,有人为了使得自己的网页的排名能够靠前,想出了很多的方法来作弊,这样的作弊被称为链接作弊(Link Spam)。简单来讲,对于上述的仅考虑入链数量的网页级别算法,有人为了使自己的网页(称为网页A)的级别更高,便做了很多的网页以使得这些网页都指向网页A,这样网页A的入链数量就会变得很多,自然,网页A的网页级别就会变得很高,但是这样的网页A的高级别只是所有者作弊的结果,并不等价于网页的质量就很好。

    但是,PageRank算法可以避免这样的情况,因为PageRank值同时考虑入链数量和网页质量,入链数量之前已经说了,然而,对于自己作弊生成的指向网页A的网页的质量本身就很低,这样综合的结果是网页A的网页质量也不会变得很高,这样PageRank算法就对网页质量的评价起到了很好的效果。

    网页的链接分析可以抽象成图模型,如下图所示:

(图 1 有向图)

在上图中,链接关系分别为:1-->2,1-->3,1-->4,2-->1,2-->4,4-->2,4-->3。

2、PageRank的两个假设

    对于某个网页的PageRank的计算是基于以下两个假设:

  1. 数量假设。在Web图模型中,如果一个页面节点接收到的其他网页指向的链接数量越多,那么这个页面越重要。简单来讲是指链接到网页A的链接数越多,网页A越重要。
  2. 质量假设。指向页面A的入链的质量不同,质量高的页面会通过链接向其他的页面传递更多的权重,所以越是质量高的页面指向页面A,则页面A越重要。简单来讲是指链接到网页A的原网页越重要,则网页A也会越重要。

    数量假设,简单来讲就是在互联网中,如果一个网页接收到的其他的网页指向的入链数量越多,那么这个页面就越重要。质量假设,简单来讲就是在互联网中,对于一个页面,越是质量高的网页指向该页面,则该页面越重要。

       PageRank算法很好地组合了这两个假设,使得对网页的重要性评价变得更加准确。如早期只有数量假设,现实的情况是并不是指向该网页的链接越多该网页越重要,比如可以通过一些办法使得很多的网页指向该网页,在社交网络中,可以购买一些垃圾粉,但是这样并不会提升自己的重要性,反倒是有一些很重要的用户关注你,你的重要性较高。

二、PageRank的计算方法

1、有向图的表示

    如图1,对于图模型,通常可以使用矩阵来存储,成为邻接矩阵,则图1的邻接矩阵为:

其中,邻接矩阵的每一行代表的是每个节点的出链。

2、网页链接概率矩阵

    对上述的邻接矩阵的出链进行归一化,即:

这样,即表示有多少概率链接到其他的点,如从节点1分别以概率

链接到节点2,节点3,节点4。

3、概率转移矩阵

    对上述的网页链接概率矩阵求转置即可得到概率转移矩阵:

概率转移矩阵可以描述一个用户在网上的下一步的访问行为。若此时初始化用户对每一个网页节点的访问概率相等,即:

则当该用户下一次访问各节点的概率为:

但是,此时存在这样的一个问题,一个用户不可能一直按照链接进行操作,有时会重新进去新的页面,即以一定的概率按照转移概率浏览网页节点。

4、修改后的转移矩阵

在上述转移矩阵中加入跳出当前链接的概率:

此时转移矩阵变为:

在谷歌的计算中,通常取

5、迭代计算求解PageRank值

通过迭代公式:

求解PageRank值,当

的误差在一定的范围内,即为最终的PageRank值。

三、简单的原理实现

    对于是上述图1的问题,通过PageRank算法求出各节点的PageRank值为:

0.32456139 0.2251462 0.2251462 0.2251462

对应的程序代码为:

#coding:UTF-8

import numpy
from numpy import zeros
from numpy import ones
from numpy import mat
import string
import math

def loadData(filepath):
	f = open(filepath)
	#用于记录顶点
	dict_tmp = {}
	
	#获取到所有的顶点
	for lines in f.readlines():
		line = lines.strip().split("\t")
		if line[0] not in dict_tmp:
			dict_tmp[line[0]] = True
		if line[1] not in dict_tmp:
			dict_tmp[line[1]] = True
	
	#统计顶点的个数
	num = len(dict_tmp.keys())

	f.close()
	
	#构建矩阵
	M = zeros((num, num))
	f = open(filepath)
	for lines in f.readlines():
		line = lines.strip().split("\t")
		#为简单起见,顶点是从0开始编码
		M[string.atoi(line[0]), string.atoi(line[1])] = 1

	f.close()
	
	return M

def compareMatrix(q, p, n, e):
	#对比的是两个列向量
	for i in xrange(n):
		if (abs(p[i,0] - q[i,0]) > e):
			return False
	return True

def pagerank(M, alpha, e):
	#从M得到转移矩阵
	num = len(M[0,])
	for i in xrange(num):#行
		sumCol = sum(M[i,])
		for j in xrange(num):#列
			M[i, j] = M[i, j] / sumCol

	#转移矩阵
	M = M.T
	N = ones((num, num))
	G = alpha * M + (1-alpha)*(1.0/num)*N

	#初始化pagerank值
	q = (1.0/num) * ones((num, 1))		
	q_new = mat(G) * mat(q)

	#迭代计算
	i = 0
	while(not compareMatrix(q_new, q, num, e)):
		q = q_new
		q_new = mat(G) * mat(q)
		i += 1
		print i
		print q_new
	
	return q_new
		


if __name__ == "__main__":
	M = loadData("E:\python\data.txt")
	e = 0.0000001
	pr = pagerank(M, 0.85, e)
	
	print "the final pagerank:"
	print pr

参考文献

1、PageRank算法(点击打开链接)

2、谷歌背后的数学(点击打开链接)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏流柯技术学院

性能测试学习之二 ——性能测试模型(PV计算模型)

=( (总PV*80%)/(24*60*60*40%))/服务器数量              

26120
来自专栏算法channel

深入理解 TensorFlow :怎样的 AI 程序才是具备产品级的

目前市面上绝大多数的 TensorFlow 程序都基本可以称为玩具,那么,一个真正可以产品化的 TensorFlow 程序应该具有哪些的功能呢?

11300
来自专栏ATYUN订阅号

建立智能的解决方案:将TensorFlow用于声音分类

对于人类的语音识别,目前有很多不同的项目和服务,像Pocketsphinx,谷歌的语音API,以及其他等等。这样的应用程序和服务能够以一种很不错的质量识别语音然...

56470
来自专栏量子位

MobileNet教程(2):用TensorFlow搭建安卓手机上的图像分类App

王瀚宸 编译自 Hackernoon 量子位 报道 | 公众号 QbitAI 上周末,量子位翻译了一份MobileNet教程,其中讲述了怎样在一个新的数据集上重...

51960
来自专栏AI2ML人工智能to机器学习

All-in-one! 深度学习的Docker套装

跑深度学习Deep Learning已经快成为程序员必备技能了。 那么, 一个随手可得测试环境将是很必要的。 如果有时间有精力, 那么自己安装编译一个也不错。...

36020
来自专栏人工智能LeadAI

关于深度学习框架Hamaa与Python API文档生成工具Sophon

当时我学习Deep Learning已有两个月,看了很多论文、教程与博客,于是尝试着去阅读Keras的源代码来学习别人是怎么实现的,尤其是back propa...

13130
来自专栏null的专栏

MATLAB技巧——imshow多张图片

本专题整理一些工作学习中使用到的一些MATLAB的技巧。 1、单个图片的显示 在MATLAB中,可以使用函数imshow展示图片,如手写体库MNIST的图: ?...

39060
来自专栏机器之心

教程 | 如何用TensorFlow在安卓设备上实现深度学习推断

42150
来自专栏张红林的专栏

大规模机器学习框架的四重境界(下)

同步协议本节假设读者已经对随机梯度优化算法比较熟悉,如果不熟悉的同学请参考吴恩达经典课程机器学习中对SGD的介绍,或者我之前多次推荐过的书籍《最优化导论》。

1.2K00
来自专栏机器之心

教程 | 如何构建自定义人脸识别数据集

在接下来的几篇博文中,作者将带领大家训练一个「计算机视觉+深度学习」的模型来执行人脸识别任务。但是,要想训练出能够识别图像或视频流中人脸的模型,我们首先得收集人...

22920

扫码关注云+社区

领取腾讯云代金券