Video在线视频

各位同学 大家好

欢迎来到网络 群体与市场的

在线课堂

我是这门课的主讲老师——石兵

来自武汉理工大学

在这一讲我们将介绍

网络信息的链接分析

这个是现代搜索引擎的

核心技术之一

我们可以看一下

当你上网的时候

你很多时候会要通过网络来

搜索一些信息

你可能选择百度

也可能选择谷歌

当你们在搜索的时候

搜索引擎公司（和你）关心

这样一些基本的问题

计算机的显示屏非常小

一次一般来说只能显示

5-6个结果

但是典型的搜索引擎掌握的

网页超过10亿个

所以对于用户提交的一个查询

这样一个搜索引擎必须要从

海量的网页集合中将最可能

满足用户需求的那几个结果

找出来 把它放在前面

这个时候我们要注意一下

这个 最可能满足 其实是

有一些多义性要处理

比如说对于同一个查询

可能有不同的需求

当你查询苹果

可能指的是苹果的电脑

或者说软件

还可能就是指的吃的苹果

另外还可能不同的查询词

可能表达的是同一个意思

比如说电脑和计算机

那么搜索引擎怎么来从

海量的信息中找到最合适用户

需求的信息呢

这里面大家考虑的就是有效地

利用链接关系蕴含的信息

推荐来找到合适的信息

我们可以看一个日常生活的例子

其实搜索引擎采用的信息链接

分析技术也是源于此

现在假设有5个餐馆

新辣道 海底捞 麦当劳

五方院 俏江南

有四个人 甲 乙 丙 丁

他们要对这样五个餐馆进行

推荐打分 我们可以看到

对于新辣道

甲 丙 丁觉得不错

对于海底捞

甲 乙 丙觉得不错

据此我们可以得到一些打分

比如说我们可以看到因为有

三个人推荐了新辣道

所以它的得分是3

对于海底捞也是三个人

所以得分也是3

其他的分别是1 2 2

这个时候有这样一个问题出现

我们发现新辣道和海底捞的得分

是一样的 都是3分

五方院和俏江南得分也一样

是2分

这个时候我们不能完全区分它们

哪个好哪个坏

这个时候我们会考虑到我们

现在认为甲 乙 丙 丁

每个人的推荐水平都是一样的

也就说他们的票数只有一

但实际上甲是一个非常

喜欢吃的人

他可能对这些美食的了解程度

非常高

因此我们要考虑到这个因素

我们怎么来考虑到这个因素呢

我们要把他们首次打分推荐的

结果考虑进去

把它作为推荐人水平的一个指标

对于甲 他推荐了新辣道

海底捞以及五方院

这三个餐馆的打分分别是

3 3 2

所以我们觉得推荐人甲的水平

就应该是3+3+2=8

这个8就可以在一定程度上反映

甲对这些餐馆的熟悉程度

同样的对于乙我们也可以算出

他的（推荐）水平等于6

我们也可以得到丙和丁的

在得到这些之后

我们就可以用他们的推荐水平

作为衡量的一个因素

来进一步考虑这些餐馆的

打分是多少

比如我们现在看新辣道

甲 丙 丁都对它投票了

那他应该得8+6+7=21分

据此我们还可以算出

其他餐馆的得分

在这个时候我们可以发现

我们可以把这些餐馆区分开来

显然我们可以看到

新辣道的得分最高

其次是海底捞

然后五方院和俏江南

虽然在这里面没有区分

现在我们可以区分了

五方院好于俏江南

这样一个餐馆推荐问题

隐藏的算法

我们就可以把它用在互联网

搜索引擎里面网页的推荐

这其实就是一个反复改进原理

这个原理什么意思呢

比如说左边表达的是

与 newspaper 这个字面

相关的一些网页

右边是这些网页所指向的

那些网页

也就是说所指向的这些网页可能

跟 newspaper 相关

我们据此可以得到一个

票数 表示他们的认可度

我们直接数它们的链入的这些

链接就行了

比如说我们看对于纽约时报

有这样四个网页指向它

所以它的得票就是4

对于这样一个今日美国

USA Today 的得票是3

当然我们这里面还发现

Facebook Yahoo!

他们分别也有投票

而且 Yahoo! 的投票

还不低也是3

但实际上我们知道

Yahoo! 跟 newspaper

没什么相关

这很可能是由于这几个网页

含有 newspaper

这个页面

但是它们不够权威

所以我们要反过来评估这个

推荐者的水平

我们按照刚才这样一个

餐馆推荐问题

我们可以反过来衡量

对于这个网页

它的推荐者的水平是多少呢

就应该是它所指向的这些

网页的得票数之和

就是2+2+4=8

据此我们也可以算出其他的

这些网页它们现在的

分量是多少

然后在这个基础上我们就可以

在考虑推荐者的分量情况下

重新来评估这些网站相对于

newspaper 的重要性

也就相当于是一个加权平分

比如说我们可以看到现在

我们重新对这些它链向的

这些网页来打分

比如说我们看纽约时报

他的打分就变成

8+11+7+5=31

我们现在看这个时候

Yahoo! 的得分是15

也就是说因为它现在所指向的

是6+3+6

我们通过这样这一轮的改进

我们现在发现差不多就可以把

真的跟 newspaper

相关的网页给选出来了

比如说 华尔街时报

USA Today

然后其他这些不相关的

它们的得分相对会比较低一点

而且这个过程我们可以

反复地进行下去

在刚才这个过程里面

我们就涉及到网页的两个性质

一个叫做中枢性

还一个叫做权威性

也就是说

如果这个网页被很多其他的

网页所指向

说明很多网页认可它

也就是说它的权威性很高

另外一方面如果这个网页

它指向了很多其他的网页

类似于那些导航的网站

说明它作为一个枢纽

中枢性就很强

我们可以通过HITS算法

来计算网页的权威值和中枢值

我们接下来看怎么来计算

首先

这个算法的输入是一个有向图

我们首先要初始化

对于每一个网页

也就是说对于每一个节点

它初始的权威值是1

中枢值也是1

我们接下来利用中枢值来

更新权威值

怎么更新呢 对于节点p

节点p的权威值等于指向

节点p的所有其他节点q

的中枢值之和

然后我们可以利用权威值

进一步来更新中枢值

怎么来更新呢 对于节点p

我们让p的中枢值等于p的

所指向的所有节点q的

权威值之和

这样的一个过程我们可以

重复地进行若干次

直到收敛

我们接下来看搜索引擎里面

是怎么收敛的

其实我们在搜索引擎领域有很多

网页不单权威值比较高

中枢值也比较高

很多网页也可能二者皆有

我们刚才提到的这样一个

收敛的问题

我们其实可以看到

在随着算法不停地迭代

这个数值是随着迭代次数（增加）

在不停地递增的

但其实我们在考虑

网页推荐的时候

我们其实是考虑它们的相对大小

我们不需要考虑它们的绝对大小

所以我们可以在每一轮结束之后

做这样一个归一化处理

我们把每个网页的中枢值

或者它的权威值除以所有

网页的中枢值（权威值）之和

然后随着迭代次数的不断增加

这个结果可能会趋向于一个极限

也就说再也不会变化了

我们可以看到最终稳定之后

这些点的权威值分别是这样子

我们可以看到与

newspaper

相关的这些网页

它们的权威值都比较高

而我们刚才所说的比如说

Yahoo

Facebook

它们的值就相对比较低

说明它们跟 newspaper

不是特别相关

在这一讲我们就介绍了这样一个

信息链接的算法——HITS算法

当然还有其他算法

比如说PageRank算法

感兴趣的同学可以

翻阅资料或者教材

我们可以总结一下

当我们把信息刻画成网络的时候

信息之间会互相隐含一种

推荐关系

网页A指向B就表达了

一个A对B的推荐

我们可以利用这样一个推荐

来进行评估

而且我们还要注意一下

这样一个评估方法

不仅要考虑局部的结构

而且要考虑全局结构带来的影响

反复改进原理是一个基本的手段

我们还介绍了这样一个

中枢值和权威值的计算

这一讲的内容就到这里

谢谢大家