第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这样的算法

当然

这就不在我们这次课的讲解当中

大家感兴趣的话

可以去参考更多的资料

来完成这方面知识的学习

今天的课程就到这里

感谢同学们的观看