当前课程知识点:互联网大规模数据分析技术 > 第七章 Web链接分析 > 第19讲 Web搜索之PageRank > 第19讲 Web搜索之PageRank
欢迎来到
互联网大规模数据分析技术
的课堂
我是今天的主讲教师李琳
来至武汉理工大学
今天我们开始第19讲
关于Web搜索之PageRank
我们的内容主要包括
对PageRank的算法
做一个简要的描述
然后
我们了解一下PageRank的
数学表达式
接下来我们讨论一下PageRank
存在的一些问题
在上面的课程当中
我们看到了
我们把Web看成一个有向图
节点就是网页
点和点之间是
通过超链接连接起来的
点一下就可以进入另外一个网页
同时我们知道了
了解到了每一个网页
它的重要性不一样的
像斯坦福这样的学校
由于它的in-link数比较多
使得它的重要性远远大于
只有一个in-link的其他网页
我们看一下那么PageRank
怎么来描述这样一个问题呢
我们把link
作为投票的这样一个机制
我们in-link的数
作为一个打分的机制
同时我们要考虑来自重要的网页
它的link
要在我们整个打分机制中
占的权重更多
那么这就变成了一个循环
递归的问题怎么来解决它呢
我们来看一下
在上一节课中我们讲到了
你有7个in-link
你的重要性就为7
你有一个in-link
你的重要性就1
但是我讲到了
万一这个in-link能来源B
他是一个诺贝尔奖获得者
那你这个1
可能比所有的7都要重要
由于你来自于一个重要的人
你又来自于别的
所以这样就形成了循环
究竟我该怎么算呢
我算不清楚了
存在这样一个问题出来了
所以
这种情况下我们看一下
假设我把这个图转换一下
假设我知道这个网页
它的重要性是100分
它有两个out-link
每个out-link
由于它的in-link数比较多
所以我把它取为50
它少一点我给它3
那么,这一个网页
它有两个in-link
一个是50,一个是3
按照我们刚才的数数,它只有2
但是由于它来自于
一个重要的网页
所以它变成了50+3变成了53
同样
我们看到在这样一个网页当中
我只有一个in-link来自于50
我虽然只有一个
但是我的重要性是50
我就是50
也就是说我一个网页
它的重要性
不但取决于in-link的个数
还取决于in-link自身的重要性
我们对这样一个问题
做一个数学描述
大家看一下这个公式
rj在哪里呢
j是红色的点
rj的重要性取决于它的in-link
in-link有谁呢
有i和k
我不是i+k、1+1
因为我的重要性是取决于你的
是i的重要性
我表示成ri
是k的重要性我表示成rk
但也不是ri+rk
为什么呢
因为我ri有3个out-link
我的重要性是ri
我3个out-link平分我的重要性
所以是ri除以3
我的rk有4个out-link
借一个作为你的in-link
所以我是被我的4个out-link
去分了其中的一份
所以是ri除以3加上rk除以4
好的,这样我们知道了
rj重要性怎么打
分取决于in-link
这个点
它的重要性
被它的out-link去平分
这样的自然语言的表达
显得不是那么简洁和明了
我们怎么来表示一下呢
我们用这样一个公式
rj,就是某个节点的重要性
它是,所有in-link之和
指向我的,这些点
所有的指向向我的这些点
去求一个和
这些点我们用ri表示
那么是不是把ri去直接求和呢
是不是直接写r到j去
ri求和呢
我们刚才讲到了
ri这个点
它可能有若干个out-link
rj只是我其中的一个
你只能平分
所以这个di就是我的出度
也就是out-degree of the node
大家看看这个数学表达式
是不是非常简洁和明了
比刚才我们讲的
ri除以3加上rk除以4
这样的表达方式
就会显得比较简洁
按照我们这样一个表达
大家看一下
y,它有几个in-link呢
有两个
这个in-link来自于谁呢
a,a有几个out-link呢
两个
每一个分二分之a
那么y还有一个in-link
来自于自身
它自己有一个out-link到a
又一个out-link到自己
所以呢,y也被分了两个
大家再来看a
a有几个in-link呢
一个来自于y
一个来自于m
y被两个out-link平分
所以是二分之y
m被1个out-link
所以它就是m
rm只有一个in-link来自于谁呢
a,由于a被两个out-link平分
所以它就是ra/2
这样的话呢
我们按照解方程的思路
大家会发现
我有三个方程
我有三个未知数
但是我没有常量的约束
这种时候我们的解
没有唯一的解
因为我所有的解
都可以对它做一个加倍数的处理
我们来解决这个问题该怎么办呢
我们可以借助一些数学的方法
比如说高斯
但是这种高斯的估计
对于小量的数据是可以的
大量的数据完成起来
计算复杂度太高
所以我们需要一种
针对大规模的Web数据
提供一种更好的解决方案
怎么来解这三个方程
在解这三个方程当中
我们借助这样一个公式
那么大家看一下
我们把这样一个公式
通过一种矩阵来表示
这个矩阵的行就是网上所有的点
这个矩阵的列也是网上所有的点
那么这一个点代表什么意思呢
page i links to 3 pages
including j
也就是这个点代表i指向的j,指向了k,指向了m
j是我指向的其中的一个
也就是我们的j是i的out-link
i是j的in-link
我把这样一个数值
存成这样一个矩阵
怎么表示这个呢
大家看一下
ri等于它所有的in-link去除以
in-link的out-link度
大家看
求一个和
这也行去乘以这一列
这一行代表的什么呢
这一行代表的
j的所有的in-link
i指向j,k也指向j,m也指向j
那么就是我所有的in-link
i指向j,k指向j,m指向j
我所有的in-link
去乘以每一个
in-link它自身的重要性
这一行去乘以这一列
在做累乘之后做一个累加
我们就得到了rj
就正好解释了这个公式
所以当我们把网络的关系
变成这样一个矩阵之后呢
我们会得到这样一个数学表达式
m去乘以r要等于r
刚才的那样一个例子
我们来看一下
我们把它表示成
这样一个矩阵的形式就是
2/1,2/1,0,2/1,0和1
因为我这个代表m
a在这个位置2/1
而y也没有,m也没有
所以是0,0
这样的方式
我们就能够来进行一种运算
我们把这个运算叫做迭代
大家看一下这个图
我们首先
有ra, ry, ra, rm
但是
老师 ry, ra, rm是什么呢
不知道,我给它一个初始值
这个初始值我就假设总量为1
网上有三个点
每一点都要平分
那就是三分之一
我们两个都是三分之一之后
我是不是可以算呢
我知道你是三分之一,三分之一
三分之一,三分之一,三分之一
我就可以算一个新的ra, ry, rm
然后我又得到一个三分之一
三分之六,六分之一
那老师
到底是三分之一,三分之一
三分之一,还是三分之一
六分之三,六分之一呢
这个时候
我们就需要一个准则来判断
什么时候我不需要再这样算下去
你看,我还可以算
我还可以算
每一次算的结果,都不一样
我把三分之一,六分之三
六分之一带进来
我又算了一个新的值
我把十二分之五,三分之一
十二分之三算进来
我又得到一个值
那算到猴年马月结束呢
我们这里有一个准则
也就是前后两次的值变化不大
如果我前面一次算的
也是十五分之六
如果前后两次的值不再变化
那我们就到此为止
这是
解决这样一个
大规模数据计算的一个问题
通过不停的迭代
去达到逼近我们最终的结果
这是我们最终求出来的
我们看到了PageRank的
这样一个循环迭代运算
我们也了解了它能够解决
衡量一个网页重要性的问题
在这个里面
我们有一些问题
来跟大家探讨一下
解决PageRank计算的时候
我们还有一些模型叫
Topic-PageRank
可我们还有Hits
这样的运算
前面我们讲到了
当你用cosine
来计算相似度的时候
你输java
我为了让某个垃圾网页排在前面
那些垃圾网页的制造者
会在网页当中复制
成千上万个java
以获cosine排名的高
同样在这个里面
你用in-link来衡量我的重要性
你把重要的网页排到前面去
这些网络上的垃圾网站的制造者
又想出了一个新的垃圾制造方法
他们用link
你不说in-link越多越好吗
我就人造的去伪装
很多in-link
我们就形成一个联盟
我连你,你也连我,我连你十个
你再连我十个
这样的话
来增加自己的in-link数
从而来将我们PageRank的值
来获得提升
这样的情况
我们也需要一定的解决方案
我们用PageRank解决了
cosine这样一个基于内容的
垃圾网页的排序的问题
如果又有了
基于link的垃圾网页
我们又该怎么办呢
实际上在学术上我们有
TrustRank这样的算法
当然
这就不在我们这次课的讲解当中
大家感兴趣的话
可以去参考更多的资料
来完成这方面知识的学习
今天的课程就到这里
感谢同学们的观看
-第1讲 大数据与数据挖掘概述
-第2讲 频繁项集和关联规则的基本概念
-第3讲 Apriori算法
-第4讲 Apriori算法的改进与兴趣度度量
-第5讲 分类的基本概念
-第6讲 决策树
--第6讲 决策树
-第7讲 简单贝叶斯分类
-第8讲 聚类的基本概念
-第9讲 K-Means & K-Medoids Clustering
--第9讲 K-Means & K-Medoids Clustering
-第四章 聚类算法--习题
-第10讲 大数据处理平台Hadoop
-第11讲 MapReduce编程
-第12讲 大数据处理平台Spark
-第13讲 NoSQL数据库
-第14讲 Web信息检索简介
-第15讲 信息检索之倒排索引
-第16讲 信息检索之TFIDF
--Video
-第17讲 信息检索之相似度排序
-第18讲 Web搜索之链接分析
-第19讲 Web搜索之PageRank
-第20讲 Lucene信息检索平台
-第七章 Web链接分析--习题
-第21讲 推荐系统简介
-第22讲 推荐系统之协同过滤
-第23讲 Mahout数据挖掘平台
-第24讲 信息过滤评价体系
-第八章 推荐系统--习题一
-第八章 推荐系统--习题二
-综合编程题