第18讲 Web搜索之链接分析在线视频

欢迎来到

互联网大规模数据分析技术

的课堂

我是今天的主讲教师李琳

来自武汉理工大学

今天我们开始第十八讲的学习

关于Web搜索之链接分析

今天我们的内容

将包含以下四个方面

图数据，爬虫

用入度来作为投票的结果

还有一些相关的问题

对于图大家已经很熟悉了

在社交网络上

人和人之间的关系

构成了社交网络图

那么在博客当中

人和人之间帖子的回复

构成了这样一个关系图

在我们的论文数据库当中

引用和被引用的关系

构成了论文的引用数据

在我们的计算机网络当中

网线将计算机

连成了这样一个网络拓扑图

在我们的路网当中

路、节点也构成了

我们之间的交通路网图

所以这样一些图的数据

在我们的Web上

也是非常应用的典型

比如说我们把Web网页

看成一个节点

那么Web网页和Web网页之间

的超链接就变成了

连接Web网页之间的线

那么这样的话呢

我们也会形成一个Web的网络

这样一个Web的网络当中

对我们的数据分析

有一些什么样的帮助呢

我们来看一下

大家知道

在信息检索系统当中

Web信息检索系统

有一个非常关键的部件

也就是要从网上将数据爬取下来

我们需要设计一个蜘蛛程序

对网络数据进行爬取

这个蜘蛛是怎么把网络的数据

全部爬取出来

从而存到我们的信息检索数据库

然后让用户产生查询需求

最后得到输出结果的呢

这个爬虫借助的一个

非常关键的信息就是超链接

也就是超链接所形成网络

我们基本的爬虫的操作有哪些呢

首先呢

它会有从一些

已知的种子URL开始

对这些URL

我们做一个什么操作呢

解析

这些URL上面的HTML语言当中

又蕴含了很多超链接

通过这些超连接的解析之后

我们又把这些URL放到网上去

将它的内容爬取下来

从而形成往复循环的

这样一种爬取

我们看一下这个图

我们有种子网页

有没有一个蜘蛛已经设计好了

然后呢

我们把网页上的这些URL

全部爬取下来

爬取下来后

我进行解析

解析之后我又得到新的URL

然后这些URL又向前

一步一步的去把我们未知的网络

一步一步的爬取下来

所以这样的

是一个基本的爬虫功能

当然这个爬虫

它会遇到一些问题

一些什么问题呢

比如说，spide trap

什么叫spide trap呢

我们刚才的网络所组成的一张图

这个图当中从a出发到b到c

有可能又回到a

如果没有一些机制的话

这些爬虫会在a b c d a里面

反复的去循环

从而无法获取整个WEB的文档

所以对于这样一些问题呢

我们需要一些技术来进行解决

在这样一些解决当中

我们同时还要意识到

如果你反复地去爬取一些网站

这些网站会不高兴的

因为你反复地来爬取我的内容

会影响到其它用户

对这个网站的连接

所以在一般开发网站的人员当中

都会有一个文件

这个文件很重要

叫做robots.txt

当你设计爬虫程序的时候

你首先要去读取东西那些网站的

robots.txt文档

要遵循robots.txt文档中的

一些规则

从而能够实现我们内容的爬取

另外一只蜘蛛能不能把所有的

网站都爬取下来呢

显然不行

所以这必然涉及到一个

分布式的问题

一定是多条蜘蛛

同时出发去进行爬取

所以这样的话它天生呢

也是一个分布式并行计算的问题

同时我们的爬虫呢

去爬去网页的时候要注意一下

网页的质量

也不说什么网页你都爬取出来

有些网页比如说可能是垃圾网页

我要尽量地把它屏蔽

不去爬它

大家在使用搜索引擎的时候

会发现

其实很少遇到一些垃圾的网页

大部分的网页提供给大家

都是有实际性的内容

是一个爬虫

所需要遵循的一些问题

通过这样一个改进之后

我们再来看一下这个爬虫程序

同样它还是从种子节点出发

我们有多个爬虫

多个爬虫

就会导致一个什么问题呢

你速度是快了

可能我爬了A

你也爬了A

他爬了B

你也爬了B

所以我们有一个URL frontier

它存取的你们所爬取的内容

在这样我们frontier里面我们

可以把一些重复的url去删除

达到有效地获取网页的目的

这就是URL frontier的一些功能

可以含有不同的网页

来自这样一个hoster

大家可以去统一地去爬取

但是要避免在一个网站上面

去读取这些文件

在同一个时间

因为你所有的爬虫

都集中到一个网站上去下载数据

这个网站的服务器

可能会遇到问题

所以这种情况下在设计的时候

需要去做一个区分的考虑

这就是我们利用爬虫

利用爬虫

在网上的超链接这样一种结构

来实现网络网页的爬取

从而使得互联网上的数据

能够存储到我们的服务器当中

当然在这里我们注意一下

当你设计爬虫程序的时候

一定要遵循一些原则

刚才我们讲到了robots.txt

一定要遵循我们的要求

另外一个

这个robots.txt的

这样一个文档

它会写上这样一些话

比如说

User-agent

用户

不能干什么写的很清楚

那么对于Search Engine来说

它也会写上一些

或者说没有写

你就可以读取所有的内容

也就是说对于这样一个

robots.txt的这样一个文档

作为一个爬虫程序

你首先要去读一读它

允不允许你

它不允许你爬你强行去爬

那么你就不礼貌了

没有遵循我们网络的

这样一些规则

我们把整个爬虫的这样一个步骤

跟大家列一下

首先我们到frontier里面

去找一个URL

然后把这个URL下载下来之后

我要进行解析

解析的目的是什么呢

因为这个URL上还有很多link

我要把这些link

一个一个都找到

如果这个找到的URL的这个内容

已经存在于我的数据中心了

我就不需要添加进去了

如果没有我就加进去

对于每一个已经解析过的URL

我们要把它check一下

它是不是已经在我们的这个

frontier里面

也就跟刚才是一样的

如果有重复的话

要去掉

每一步都要去做这样一个检查

这是整个爬虫的架构

大家可以结合那个书本上的内容

作进一步的学习

在这个过程当中

主要有解析

重复地这样一个删除工作

我们已经看到了

我们已经把网页爬下来了

根据超链接

根据这样一些link的信息

那么我们怎么来组织网页呢

是一个一个给大家吗

还是以列表的形式

还是以目录的形式呢

大家可以看到

在这个图当中

雅虎它是以目录的形式来给出的

但是这种目录的方式

并不能在大规模的数据当中

得到很好的应用

我们目前在传统的信息检索当中

包括我们这个搜索引擎当中

还是以列表的形式推荐给用户

所以这就是我们讲的爬虫将根据

超链接的信息将内容爬下来

接下来我们要解决的一个问题

就是

我们有很多的网页信息

我们刚才又用了TF-IDF

对它进行了排序

用了cosine

但是那个是内容相关的排序

比如说你输一个java

你说java出现的次数越多

就越排在前面

垃圾网页的制造者就可以把

java这个词在某一个网页当中

去重复1000次

复制粘贴就可以了

在打分当中

它显然

当你输入java的时候

它会被排在前面

但是这样的网页对你有价值吗

没有价值

所以我们需要解释一个问题

可信

不是简单地这样一个垃圾网页

的这样一种重复

所以

如何来解决这个问题

不仅仅是从内容上的匹配

你有java我有java

你有一个java我有1000个java

我就把1000个java排在前面吗

所以在这一节课当中

我们对这样一个问题

做一个初步的探讨

怎么来衡量一个网页的重要性

在前面我们看到了

它不像人

我们有奖励来评价

有考核机制

一个网页

谁来给出网页的重要性呢

这个时候我们就要动动脑筋

看能不能利用某些信息

在这个里面谷歌它非常聪明

用到了link的信息

大家在这样一个图上

可以看到我有两个点

一个是蓝色的点

一个是红色的点

如果这两个点和查询词的

Cosine相似度都是一样的

我想问大家

你们直观上觉得

是红色的点重要性更高

还是蓝色的点重要性更高

大家会看到这个蓝色的点

有很多网页围绕着它

指向着它

连接着它

说明大家喜欢连它

愿意连它

相信它

所以从这样一个角度我们看到

link这样一种超链接的结构

能够帮助我们对一个网页的

重要性进行分析

我们就考虑利用link信息

来解决网页的重要性排序

在这一节课当中我们只是对

PageRank这样的一个排序算法

做一个前面的铺垫

后面的一节课当中的我们会重点

讲PageRank

我们看一下我们的基本思想

大家已经知道了

我们用link来作为投票来打分

那到底是In-coming link重要

还是Out-going link重要呢

大家想一想

in-link是别人连我

out-link是我连别人

如果我被别人连接的越多

说明别人认可我

那么我的重要性就体现出来了

这就相当于论文当中的引用一样

我的论文被别人引用了

说明我的论文的重要性和质量

比较好

同样大家看一下这样一个例子

斯坦福学校的主页

有23400个被别人链接的记录

但是这样一个网址

它只有一个连接记录

显然我们认为

斯坦福的可信度要高

所以我们把in-link

作为一个打分的标准

这个例子当中

大家看一下A这个节点有一个

入度为1

有一个in-link

所以它的打分为1

B这个节点它有1个，2个，3个

4个，5个，6个，7个

它有7个in-link

所以B它的重要性打分为7

如果一个查询词的

cosine相似度

和A，和B相等的话

那么在排序的时候谁排前面呢

我们倾向于把B排到前面去

这是一个最简单的

基于in-link对于重要性的打分

看上去我们似乎解决了一个问题

我们基于内容的cosine打分

基于in-link的重要性的打分

但是是不是就完美地解决

所有的问题呢

不是的

我们会看到有一个问题出现了

什么问题呢

是不是所有的in-link都同样呢

Are all in-links are equal

我们举一个例子

比如我发表了一篇论文

我这篇论文被A引用了

被B也引用了

我的引用次数是两次

那么我的另外一位同学

发表了一篇论文

他只被C引用了

只用了一次

按照in-link个数的多少来排序

由于我发表的论文

被别人引用了两次

我显然排在前面

但是现在的问题是

我的同学发表的论文

虽然只引用了一次

但是引用它的人

是诺贝尔奖的获得者

大家是不是思想上

已经偏向了我同学的论文

因为引用它的人非常权威

所以在这个问题当中

就出现了这样一句话

A “vote” from an important

page is worth more

也就是说不仅仅是数量

还要考虑质量

一个网页它是否重要取决于

它是否被其它重要的网页链接

那么这个问题该怎么解决呢

我们留到下节课来给大家做讲解

今天的课就到这里

谢谢观看