信息内容安全技术 网络数据主动获取技术 1

通用网络信息主动获取系统 工作流程 主要技术 聚焦爬虫

工作流程 搜集 预处理 服务 搜集 整理 服务 批量搜集，增量式搜集；搜集目标，搜集策略 关键词提取；重复网页消除；链接分析；索引 查询方式和匹配；结果排序；文档摘要 现代大规模高质量搜索引擎一般采用三段式的工作流程，即： 网页搜集，预处理，和查询服务 1) 定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。 开始时搜集一批，往后只是（1）搜集新出现的网页，（2）搜集那些在上次搜集后有过改变的网页，（3）发现自从上次搜集后已经不再存在了的网页，并从库中删除。我们称之为“增量搜集”。 “目标网页”指的是搜索引擎设计覆盖的网页范围。例如Google是全球，天网是全中国。 2) 对于中文来说，就是要根据一个词典Σ，用一个所谓“切词软件”，从网页文字中切出Σ所含的词语来。在那之后，一篇网页主要就由一组词来近似代表了 . 天网在2003年的一次大规模统计分析表明，网页的重复率平均大约为4。 大量的HTML标记既给网页的预处理造成了一些麻烦，也带来了一些新的机遇。从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我们能依据的就是“共有词汇假设”（shared bag of words），即内容所包含的关键词集合，最多加上词频（term frequency 或tf、TF）和词在文档集合中出现的文档频率（document frequency 或df、DF）之类的统计量。而TF和DF这样的频率信息能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性，这是有意义的。 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的顺序是很重要的一个问题。 3) 搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标题，网址和摘要。 3

系统流程

系统结构

主要技术 网络信息搜索系统由搜索器、索引器、检索器和用户接口等四个部分组成。 搜索器 搜索器的功能是在互联网中漫游，发现和搜集信息。它要尽可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死连接和无效连接。 挑战性问题：搜索效率、命中率、按兴趣搜索、网络信息形式多种多样

① 单机抓取算法 DS： Url_QUEUE uqueue; History_LIST hlist; PROCEDURE: Crawler（seed_url） // seed_url是起始URL队列集合 { in_queue (uqueue , seed_url); while （u=out_queue(uqueue) ） //从uqueue队列中移除url地址 { wpage=http_get(u); // 下载网页 save wpage; // 保存网页 for each url in wpage // 解析网页中的URL，看是否被访问过 { if url not in hlist then in_queue (uqueue , url); } // 未被访问加入到uqueue队列中 }

协调 进程 （节点） 抓取 调度模块 ……

索引器 2.索引器 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。 索引项有客观索引项和内容索引项两种： 客观项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度（Link Popularity）等等； 内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。 内容索引项可以分为单索引项和多索引项（或称短语索引项）两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空格）；对于中文等连续书写的语言，必须进行词语的切分 挑战性问题：分类准确性、热点评价、权重评价

以下介绍几种著名的算法： ① PageRank (Google创始人之一拉里·佩奇（Larry Page )算法： PageRank是Google算法的重要内容。2001年9月被授予美国专利. PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是 Page Rank 的核心思想。 　　算法基本思想概括为，如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为： PR（T）/C(T) 　　其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。 　　该算法的优点是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得，有效减少了在线查询时的计算量，极大降低了查询响应时间。 该算法的不足是，人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低。另外，PageRank有很严重的对新网页的歧视。

② Topic-Sensitive PageRank（主题敏感的PageRank）算法： 基本思想：该算法是针对PageRank对主题的忽略而提出。算法通过离线计算出一个PageRank向量集合，该集合中的每一个向量与某一主题相关，即计算某个页面关于不同主题的得分。主要分为两个阶段，主题相关的PageRank向量集合的计算和在线查询时主题的确定。 该算法的优点是，根据用户的查询请求和相关上下文判断用户查询相关的主题（用户的兴趣）返回查询结果准确性高。 该算法的不足是，没有利用主题的相关性来提高链接得分的准确性。

检索器和用户接口 3.检索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。 4.用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。 　　

通用网络信息主动获取系统 聚焦爬虫 基本概念 主要技术

特定内容的网页爬虫（聚焦爬虫） 根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的URL队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。 另外，所有被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以便之后的查询和检索；对于聚焦爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。 通用爬虫 专用爬虫：垂直搜索； 14

相对于通用网络爬虫，聚焦爬虫需要解决3个主要问题： 1 对抓取目标的描述或定义 2 对URL的搜索策略 3 网页分析与过滤

1 抓取目标描述 分为基于目标网页特征、基于目标数据模式和基于领域概念3种。 1 抓取目标描述 分为基于目标网页特征、基于目标数据模式和基于领域概念3种。 基于目标网页特征（内容或结构特征）的爬虫所抓取、存储并索引的对象一般为网站或网页。 根据种子样本获取方式可分为： 1） 预先给定的初始抓取种子样本； 2） 预先给定的网页分类目录和与分类目录对应的种子 样本，如Yahoo!分类结构等； 3） 通过用户行为确定的抓取目标样例 a 用户浏览过程中显示标注的抓取样本； b 通过用户日志挖掘得到访问模式及相关样本。

基于目标数据模式爬虫：针对的是网页上的数据，所抓取的数据一般要符合一定的模式，或者可以转化或映射为目标数据模式。 基于目标领域爬虫：建立领域的本体或词典，用于从语义角度分析不同特征在某一主题中的重要程度。

2 网页搜索策略 网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。 深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。

2.1 广度优先搜索策略 广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。 该算法的设计和实现相对简单。 在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。 缺点在于，随着抓取网页的增多，大量的无关网页将被下载并过滤，算法的效率将变低。

2.2 最佳优先搜索策略 按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。 它只访问经过网页分析算法预测为“有用”的网页。 存在的一个问题是，在爬虫抓取路径上的很多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。 研究表明，这样的闭环调整可以将无关网页数量降低30%~90%。

3 网页分析算法 分为基于网络拓扑、基于网页内容和基于用户访问行为三种 基于网络拓扑的分析算法 基于网页之间的链接，通过已知的网页或数据，来对与其有直接或间接链接关系的对象（可以是网页或网站等）作出评价的算法。又分为网页粒度、网站粒度和网页块粒度这三种。

基于网页内容的网页分析算法 利用网页内容（文本、数据等资源）特征进行的网页评价。 多媒体数据、Web Service等各种网络资源形式也日益丰富，基于网页内容的分析算法也从原来的较为单纯的文本检索方法，发展为涵盖网页数据抽取、机器学习、数据挖掘、语义理解等多种方法的综合应用。

挑战问题 网络信息发布技术多种多样,Webpage、bbs、blog、论坛、BT、PPLive、PPStream、迅雷、Java script等等 音视频信息越来越多 规避爬虫的机制 海量信息处理 关键指标：效率、成功率、穿透、热点的发现能力 网络的开放性：受欢迎的用户越多越好，越多越赚钱----眼球效应；限制不受欢迎的用户，如爬虫； 23

课堂讨论 tcpdump剖析 爬虫（Nutch）剖析 如何实现虚拟世界到物理世界主体、客体的映射？保证物理世界的秩序性？