（计算机应用技术专业论文）互联网信息定向采集研究.pdf

摘要 摘要 本文提出了一种互联网信息定向采集方法。通过对互联网的定向搜索、反 馈和预测排队机制，对网页内容的进行分析处理( 分词、建立v s m 向量、计算 网页内容相关度) ，对页面上的超链接指向的页面内容进行预测和先下载和主题 相关性高的页面，实现在互联网上有选择的采集和主题相关性高的用户需求的 内容并进行存储。它与广度优先搜索和深度优先搜索相比，有更高的效率和更 小的代价。 传统的搜索引擎是基于整个网络进行采集，需要大量的硬件和网络资源的 支持，而且搜索引擎服务器存储只是网页的某一历史时刻的记录( 这一时刻与 现在时刻的距离取决于搜索引擎的更新时间) ，而定向采集可以只采集某些方面 的文档，所以与传统的搜索引擎相比系统资源和网络资源消耗很小，更新快， 比较接近当前的w e b ，用户个性化满足好。此系统可进行专题研究，可形成立体 的专题库( 时间和空间) ，进行历史资料的积累和查阅。 关键词：定向采集；向量空间模型；搜索引擎；网络挖掘 a b s t r a c t a b s t r a c t t h i sp a p e ri m p l e m e n t saf o c u s e dc r a w l e rf o ri n t e m e ti n f o r m a t i o nc o l l e c t i o n t r a d l t i o n a ls e a r c he n g i n e sa r eb a s e do nt h ew h o l ew e ba n dt h e i rc r a w l e r sa l w a y st r yt o c o l l e c ta l lt h ew e bp a g e st h a te x i s t , a n dt h e yn e e dh u g eh a r d w a r ea n ds o f t w a r e 嘲o u r c e t os u p p o r tt h es t o r a g ea n dr e t r i e v a lf o rt h ec o l l e c t e dw e bp a g e s t h ef o c u s e dc r a w l e r , o nt h ec o n t r a r y , o n l yt r i e st oc o l l e c tt h ew e bp a g e st h a tm e e tt h eu s e r sr e q u i r e m e n t s t o d ot h s ，w ed e s i g n e da na l g o r i t h mt h a tc a np r e d i c tau r l sr e l e v a n c ev a l u ea c c o r d i n g t oi t sa d d i t i o n a la t t r i b u t e ss u c ha sw e bs i t e s u b j e c t , l o c a t i o na n da n c h o rt e x t , e t c c o l l e c t e dw e bp a g e sa r ea l s ou s e dt oc a l c u l a t et h er e l e v a n c eb e t w e e nt h es i t e , s u b j e c t ， l o c a t i o na n dt h eu s e r sr c q u k e m c n t s e x p e r i m e n t ss h o wt h ef o c u s e dc r a w l e ri sm o r e e f f i c i e n ta n dl e s sc o s tt h a nt h eb r e a d t h - f i r s ts e a r c ha n dd e p t h - f i r s ts e a r c h k e yw o r d s ：f o c u s e dc r a w l e r , v s m ；s e a r c he n g i n e ；w e bm i n i n g i i 学位论文版权使用授权书 y 85 6 3 8 7 本人完全了解北京机械工业学院关于收集、保存、使用学位论文 的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和 电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以 及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向 国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名：言f 金刚 年工月) 矿日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 酬金刚 别年 月潞日 第1 章概述 1 1 引言 第1 章概述 无论想要收集任何信息，毫无疑问互联网是最好的信息源，因此，不管是 出于工作需要还是处于个人兴趣爱好，越来越多的人通过互联网来收集信息。 通常我们都是使用搜索引擎来进行信息收集，但随着互联网爆炸性的增长，对 于用户来说收集和分析互联网上特定主题的网页变得越来越困难。一方面搜索 引擎返回了大量的搜索结果，在众多的搜索结果中查找相关信息是十分乏味的， 另一方面互联网上每天都增加几百万的网页，如此快速的增长使得搜索引擎不 能和互联网保持同步。因此一个分类细致精确、对硬件要求低，数据全面深入、 更新及时的面向主题的搜索引擎，实现在互联网上有选择的采集用户需求的内 容并进行存储，这正是我们需要的。为此下面我们首先了解一下互联网的发展 史和搜索引擎的相关知识。 1 2 互联网发展史 i n t e r n e t 的最早起源于美国国防部高级研究计划署d a r p a ( d e f e n c e a d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 的前身a r p a n e t ，该网于1 9 6 9 年投入使 用。由此，a r p a n e t 成为现代计算机网络诞生的标志。 从六十年代起，由a r p a 提供经费，联合计算机公司和大学共同研制而发展 起来的a r p a n e t 网络。a r p a n e t 在技术上的另一个重大贡献是t c p i p 协议簇的 开发和利用。作为i n t e r n e t 的早期骨干网，a r p a n e t 的试验并奠定了i n t e r n e t 存在和发展的基础，较好地解决了异种机网络互联的一系列理论和技术问题。 1 9 8 3 年，a r p a n e t 分裂为两部分，a r p a n e t 和纯军事用的m i l n e t 。同时， 局域网和广域网的产生和逢勃发展对i n t e r n e t 的进一步发展起了重要的作用。 其中最引人注目的是美国国家科学基金会a s f ( n a t i o n a ls c i e n c ef o u n d a t i o n ) 建立的n s f n e t 。n s f 在全美国建立了按地区划分的计算机广域网并将这些地区 网络和超级计算机中心互联起来。n s f n e t 于1 9 9 0 年6 月彻底取代了a r p a n e t 而 第1 章概述 成为i n t e r n e t 的主干网。n s f n e t 对i n t e r n e t 的最大贡献是使i n t e r n e t 向全社 会开放，而不象以前的那样仅供计算机研究人员和政府机构使用。 i n t e r n e t 的第二次飞跃归功于i n t e r n e t 的商业化，商业机构一踏入 i n t e r n e t 这一陌生世界，很快发现了它在通信、资料检索、客户服务等方面的 巨大潜力。于是世界各地的无数企业纷纷涌入i n t e r n e t ，带来了i n t e r n e t 发展 史上的一个新的飞跃。 i n t e r n e t 的增长速度是相当惊人的，网络用户大约每年增长百分之一百， 而网上的业务流量，据预计将增长的更快，可能年增长率接近百分之五百。 同时i n t e r n e t 在我国也获得了高速的发展。根据c n n i c ( 中国互联网络信息 中心) 2 0 0 5 年7 月发布的最新的中国互联网络发展状况统计报告，我国上网 用户总人数1 0 3 0 0 万人( 2 0 0 0 年时是2 2 5 0 万人) ，上网计算机4 5 6 0 万台( 2 0 0 0 年时是8 9 2 万台) ，c n 下注册的域名总数为6 2 2 5 3 4 个( 2 0 0 0 年时是1 2 2 0 9 9 个) ， 我国网站总数( 包括c n 、c o m 、n e t 、o r g 下的网站) 约为6 7 7 5 0 0 个( 2 0 0 0 年时是2 6 5 4 0 5 个) ，国际出口带宽为8 2 6 1 7 m ( 2 0 0 0 年时是2 7 9 9 m ) 。互联网的蓬 勃发展为搜索引擎的出现奠定了基础。 1 3 搜索引擎的起源 在互联网发展初期，网站相对较少，信息查找比较容易。随着互联网的迅 猛发展、w e b 信息的增加，用户要在信息晦洋里查找信息，就像大每捞针一样， 搜索引擎技术应运而生( 它可以为用户提供信息检索服务) 。搜索引擎正是为了 解决这个“迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、 发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从 而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联网上非常重要 的网络服务，搜索引擎站点也被美誉为“网络门户”。搜索引擎技术因而成为 计算机工业界和学术界争相研究、开发的对象。 1 3 1 搜索引擎分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索 第1 章概述 引擎( m e t as e a r c he n g i n e ) 。 1 ) 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、 f a s t a 1 1 t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百 度( b a i d u ) 。它们都是通过从互联网上提取的各个网站的信息( 以网页文字为 主) 而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的 排列顺序将结果返回给用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己 的检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程 序，并自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的7 家引擎；另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果， 如l y c o s 引擎。 2 ) 目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅 仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词 ( k e y v o r d s ) 查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表 性的莫过于大名鼎鼎的y a h o o 雅虎。其他著名的还有o p e nd i r e c t o r yp r o j e c t ( d m o z ) 、l o o k s m a r t 、a b o u t 等。国内的搜狐、新浪、网易搜索也都属于这一类。 3 ) 元搜索引擎( m e t as e a r c he n g i n e ) 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并 将结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p l l e 、v i v i s m o 等( 元 搜索引擎列表) ，中文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排 列方面，有的直接按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则 将结果重新排列组合，如v i v i s i m o 。 除上述三大类引擎外，还有以下几种非主流形式： 1 、集合式搜索引擎：如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似m e t a 搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的4 个引擎当中选择，因此叫它“集合式”搜索引擎更确切些。 2 、门户搜索引擎：如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但 3 第1 章概述 自身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 3 、免费链接列表( f r e ef o ra l ll i n k s ，简称f f a ) ：这类网站一般只简单 地滚动排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目录 索引来要小得多。 1 3 2 搜索引擎工作原理 1 全文搜索引擎 在搜索引擎分类部分我们提到过全文搜索引擎从网站提取信息建立网页数 据库的概念。搜索引擎的自动信息搜集功能分两种。一种是定期搜索，即每隔 一段时间( 比如g o o g l e 一般是2 8 天) ，搜索引擎主动派出“蜘蛛”程序，对一 定i p 地址范围内的互联网站进行检索，一旦发现新的网站，它会自动提取网站 的信息和网址加入自己的数据库。 另一种是提交网站搜索，即网站拥有者主动向搜索引擎提交网址，它在一 定时间内( 2 天到数月不等) 定向向你的网站派出“蜘蛛”程序，扫描你的网站 并将有关信息存入数据库，以备用户查询。由于近年来搜索引擎索引规则发生 了很大变化，主动提交网址并不保证你的网站能进入搜索引擎数据库，因此目 前最好的办法是多获得一些外部链接，让搜索引擎有更多机会找到你并自动将 你的网站收录。 当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到 与用户要求内容相符的网站，便采用特殊的算法通常根据网页中关键词的 匹配程度，出现的位置频次，链接质量等计算出各网页的相关度及排名等 级，然后根据关联度高低，按顺序将这些网页链接返回给用户 2 目录索引 与全文搜索引擎相比，目录索引有许多不同之处。 首先，搜索引擎属于自动网站检索，而目录索引则完全依赖手工操作。用 户提交网站后，目录编辑人员会亲自浏览你的网站，然后根据一套自定的评判 标准甚至编辑人员的主观印象，决定是否接纳你的网站。 其次，搜索引擎收录网站时，只要网站本身没有违反有关的规则，一般都 能登录成功。而目录索引对网站的要求则高得多，有时即使登录多次也不一定 成功。尤其y a h o o ! 这样的超级索引，登录更是困难。此外，在登录搜索引擎时， 4 第1 章概述 我们一般不用考虑网站的分类问题，而登录目录索引时则必须将网站放在一个 最合适的目录( d i r e c t o r y ) 。 最后，搜索引擎中各网站的有关信息都是从用户网页中自动提取的，所以 用户的角度看，我们拥有更多的自主权；而目录索引则要求必须手工另外填写 网站信息，而且还有各种各样的限制。更有甚者，如果工作人员认为你提交网 站的目录、网站信息不合适，他可以随时对其进行调整，当然事先是不会和你 商量的。 目录索引，顾名思义就是将网站分门别类地存放在相应的目录中，因此用 户在查询信息时，可选择关键词搜索，也可按分类目录逐层查找。如以关键词 搜索，返回的结果跟搜索引擎一样，也是根据信息关联程度排列网站，只不过 其中人为因素要多一些。如果按分层目录查找，某一目录中网站的排名则是由 标题字母的先后顺序决定( 也有例外) 。 目前，搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文 搜索引擎现在也提供目录搜索，如g o o g l e 就借用o p e nd i r e c t o r y 目录提供分 类查询。而像y a h o o ! 这些老牌目录索引则通过与g o o g l e 等搜索引擎合作扩大 搜索范围。在默认搜索模式下，一些目录类搜索引擎首先返回的是自己目录中 匹配的网站，如国内搜狐、新浪、网易等；而另外一些则默认的是网页搜索， 如y a h o o 。 1 4 搜索引擎现状 随着i n t e r n e t 的迅速发展，网络正深刻地改变着我们的生活。然而，w e b 信息的急速膨胀，在给人们提供丰富信息的同时，又使人们在对它们的有效使 用方面面临一个巨大的挑战。因此，基于w e b 的信息采集、发布和相关的信息 处理日益成为人们关注的焦点。 传统的w e b 信息采集的目标就是尽可能多地采集信息页面，甚至是整个w e b 上的资源，而在这一过程中它并不太在意页面采集的顺序和被采集页面的相关 主题。这样做的一个极大好处是能够集中精力在采集的速度和数量上，并且实 现起来也相对简单，例如g o o g l e 采集系统在并行4 个采集器时的采集速度可以 达到每秒1 0 0 页。但是，这种传统的采集方法也存在着很多缺陷。 随着w w w 信息的爆炸性增长，通用的搜索引擎越的以下缺点越来越明显： 第1 章概述 i ) 使用的设备越来越多。在j o h nh e n n e s s y 和d a v i da p a t t e r s o n 所著 的计算机建筑：走迸大数中，推测g o o g l e 的服务器场中群集计算 机群形成的“搜寻场”在2 0 0 0 年大约应该有6 0 0 0 个处理器，1 2 0 0 0 个 普通i d e 硬盘( 即每个机器2 个硬盘1 个处理器) ，他们位于四个地方： 二个在矽谷和二个在维吉尼亚。每个都以o c4 8 的线路( 2 4 8 8m b i t s ， 参见宽带) 连接着因特网并且有一个0 c1 2 ( 6 2 2m b l t s ) 线路连接着 其他3 个g o o g l e 分站点。这些连接使用思科1 2 0 0 0 网关，用二个f o u n d r y n e t w o r k sb i g i r o n8 0 0 0 的以太网交换器分流成4x1g b i t s 的线路 连接到6 4 个服务器夹，里面前后各是4 0 台电脑和l 台惠普以太网交换 机，所以一个架子共有8 0 个机器和2 个惠普交换机。g o o g l e 在2 0 0 4 年4 月发布的i p os - i 表单后，大财政公司的英特网开发单位副总裁 t r i s t a nl o u i s 估计了现在的服务器场包含下列各项：7 1 9 个服务器架， 6 3 ，2 7 2 台机器，1 2 6 。5 4 4 个处理器，2 5 3 ，0 8 8g h z 的处理能力，1 2 6 ，5 4 4 g b 内存，5 ，0 6 2t b 的硬盘空间。 2 ) 采集周期过长。对于通用的搜索引擎来说，待刷新页面数量的巨大使得 很多采集系统刷新一遍需要数周到一个月的时问，这使得页面的失效率 非常地巨大。s e l b e r g 和e t z i o n i 在1 9 9 5 年的调查发现，通过i n t e r n e t 中最常用的一些搜索引擎查询到的结果u r l 中，1 4 9 的目标页面已经 失效了。一个好的缓解办法就是采用主题采集，通过减小采集页面的数 量，从而减小刷新一遍的时间，进而减小已采集页面的失效率。 3 ) 查询返回结果的效果不够好。主要体现在查询结果的采集时间、相关性、 和结果聚类三个方面。查询结果的采集时间和当前时间差距较大，主要 是因为采集周期过长造成的。查询结果的相关性差，主要是因为查询的 接口简单，只是输入几个关键词罢了，而且也没有提供结果聚类。 4 ) 查询结果页面存在垃圾信息。垃圾信息主要是一些出于商业目的的广告 等，这些垃圾信息对于用户来说是无用的。 1 5 需求的提出 在我们的现实生活中，在互联网上广泛的存在着这样一种需求：用户总到 某些特定的信息源去获取特定的信息，并且想跟踪新加入的信息。比如，了解 6 第1 章概述 特定领域的新闻，他们总是到权威的新闻网站收集最新的新闻信息。又比如， 研究证券市场，他们总是到他们常去的证卷网站查看证券信息。搞学术研究的， 总是跟踪某个领域的学术动态，等等。如果让用户一个一个的去各个网站手工 收集和加工，很显然效率相当的低，费时费力的。 现今通用的搜索引擎为不同类型的用户都提供统一的接口，不能对不同的 用户提供个性化的服务，显然不能满足用户的需求，即根据用户提出的明确要 求提供信息服务。 互联网信息保存项目和专题研究的需要。如敦煌艺术研究，当前的做法是 利用g o o g l e 等其他搜索引擎进行搜索，然后在浏览搜索结果。这样势必费时费 力，而且如果我们要查询以前的信息搜索引擎上是没有的，由于搜索引擎是每 过一段时间才更新一次服务器数据库，它所返回的查询结果是以前的一个历史 照相。而我们研究的是在互联网上有选择的采集用户需求的内容并进行存储， 它形成立体专题库( 时间和空间) ，很好的满足了专题研究的需要。 针对这种情况，我们需要一个分类细致精确、对硬件要求低，数据全面深 入、更新及时的面向主题的搜索引擎。 “互联网信息定向采集系统”的设计目标就是要充分利用计算机信息处理 技术，及时采集互联网上的海量信息，自动分析、过滤无关信息，把用户关心 的信息从互联网上有选择的采集下来，并保存在数据库中，以便查阅和研究。 基于上面的分析，“互联网信息定向采集系统”的设计目标具体的表现为具 有下列功能： 高效地采集互联网上的信息，并自动更新互联网上相关信息； 对采集到的信息自动整理，作为原始资料入库； 对采集到的信息提供的查阅服务，以便进行相关研究； 系统提供编辑工具使编辑人员方便地对原始资料进行编辑、整理。 i 6 发展现状 在主题搜索研究领域上，国内和国外都取得了一定的研究成果。下面分别 介绍了国内和国外比较好的研究成果。 第1 章概述 1 6 1 国内现状 现在国内的系统：中国科学院软件技术研究所在国内外已有主题采集系统 的基础上，开发了“天达”主题w e b 信息采集系统。为实现对基于主题的信息 自动采集，将整个处理过程分成七大模块：主题选择、初始u r l 选择、s p i d e r 采集、页面分析、u r l 与主题的相关陛判定( 链接过滤链接预测) 、页面与主题 的相关性判定( 页面过滤) 、数据存储。 为了有效地提高主题w e b 信息采集的可靠性( 查全率和查准串的综合) 和效 率，系统需要在采集过程中增加过滤机制，以使得采集的页面能够向主题靠拢。 过滤方法主要有四种：根据元数据的过滤、根据扩展元数据的过滤、根据 链接分析的过滤、根据页面内容语义的过滤。元数据方法需要人们在设计页面 时增加许多原来不需要的m e t a 信息，而这一点对设计者要求过高，因此目前此 方法并不实用。根据页面语义的过滤，需要对整个文本进行相关度计算，速度 较慢，不能符合人们实时性的要求，扩展元数据方法主要是利用链接周围的m e t a 信息来预测所链到的页面主题，尽管可靠性不如根据页面语义方法高，但有较 好的实时性。 因此，系统采用了综合扩展元数据方法和链接分析方法的i p a g e r a n k 方法。 他们的方法是进行u r l 与主题的相关性判定。按照高预测值优先采集、低预测 值( 小于设定阂值) 被抛弃的原则进行剪枝处理。这样可以大大减少采集页面的 数量，有效地提高主题信息搜索的速度和效率。 采用综合扩展元数据和链接分析的i p a g e r a n k 方法。对p a g e r a n k 方法进行 了改进：在链接关系的基础上，加入一定的语义信息权重，以使得所产生的重 要页面是针对某一个主题的，这就形成了i p a g e r a n k 算法。i p a g e r a n k 算法既利 用了p a g e r a n k 发现重要页面的优势，又利用r w 算法提高链接的相关性。 优点：采用综合扩展元数据大大降低了漏判相关页面的可能性，改进 p a g e r a n k 方法为i p a g e r a n k 使得原来针对广泛主题变为针对某一主题。为了进 一步提高采集页面的准确率，对采集的页面进行后期过滤。 缺点：采用综合扩展元数据增加了错判相关页面( 不相关的页面判断为相关 页面) 的可能性。综合扩展元数据方法主要是利用链接周围的m e t a 信息来预测 所链到的页面主题，可靠性与页面语义方法相比有一定差距。 8 第1 章概述 1 6 2 国外现状 国外的系统有：c cr e s e a r c hl a b o r a t o r i e s 开发的w t m s ( 基于主题的网 络信息采集分析系统) 。 w t m s 提供了几种不同层次的可视化的信息提取，用户能够在搜索的同时进 行浏览，除了传统的基于关键字的搜索，结构化分析技巧使得用户能够对于收 集结果获得几种有用的知识。它整合了查询和浏览，超越了基于关键词的查询， 用户能够成批的收集相关信息，过滤不重要的信息。用户很容易的共享收集到 的信息。 优点：引入了最佳中心页面和权威页面作为过滤信息的技巧。它通过减少 超过2 0 的下载页面改进了性能，同时只丢失了很少无关紧要的页面。 缺点：结构化分析不容易使用传统的搜索引擎或以前的主题管理系统，由 于是外国人开发的所以还不支持中文处理。 1 6 3 概述 上面列举一些国内和国外的此类系统，它们使用了不同的过滤方法，在一 定程度上减少了和主题无关的页面的下载，但是同时丢失了部分相关的页面， 使用的页面主题的预测技术准确度还可以进一步提高，国外的系统不支持中文。 总的来说它们都能较好的实现对主题定向采集，但是它们在主题搜索性能 上还有一定的不足。 9 第2 章研究的目标和方法 第2 章研究的目标和方法 我们现在已经进入信息时代，一切社会活动都是和信息密切相关的。信息 社会最突出的特点是：经济全球化、社会知识化、信息网络化、教育终身化。 没有信息，一切工作就无从谈起，因此我们首要的工作就是获取信息。 由于信息传播方式的多种多样，我们获取信息的方式也就多种多样。以前， 你可以通过社交活动、会议交流或信息发布这些常见的非正式信息传播方式获 取信息，可以通过报纸、广播、电视、广告这些大众传播媒介获取信息，也可 以通过图书、期刊、特种文献等印刷型信息传播媒介获取信息，还可以通过专 门的信息机构获取信息，比如你可以到专门的信息机构阅读、外借、复制信息， 可以参考专门信息机构提供的信息报道，可以接受专门信息机构提供的定题信 息服务，等等。 随着计算机的应用和现代通讯技术特别是数字通讯技术的发展以及大容量 信息载体的出现，信息传播有了一个划时代的飞跃。现代信息传播方式也越来 越先进，越来越丰富。在数字网络的世界里，你可以通过传真、电子邮件、电 子数据交换、图文电视、电子出版物、多媒体、电子公告板与电子论坛、网络 广播等等获取信息。 现在信息最丰富的地方就是互联网，掘发表在科学杂志1 9 9 9 年7 月的 文章w e b 信息的可访问性估计，全球目前的网页超过8 亿，有效数据超过 9 t ，并且仍以每4 个月翻一番的速度增长。其它的信息来源就是电子邮件、b b s 、 电子论坛、新闻组等。 通常，我们利用一些客户端软件手工链接到信息源去获取信息。比如，在 w i n d o w s 平台下，我们可以通过i e 浏览w e b 页面，通过o u t l o o k 收发电子邮件， 通过c u t e f t p 去f t p 服务器上下载软件，通过n e t t e r m 登陆到b b s 上，通过 n e t s c a p e 可以阅读新闻组等等。 这些常见的客户端软件有一个共同点：用户手工键入一个u r l 或电子邮件 地址，这些客户端软件就链接到信息源，用户从而可以从信息源上获取所需信 息。 1 0 第2 章研究的目标和方法 2 1 研究的目标 然而随着互联网的迅速发展，在网上传递的信息不仅容量巨大，时效性也 更强。仅仅依靠人工搜集、整理来跟踪国内外动态已愈来愈不能满足实际需要。 于是人们开始探索新的信息获取方式。采集技术就是应这种需求而产生的。由 于互联网是最主要的信息源，所以我们将使用采集技术在互联网上获取信息。 因此我们的目标是：一个分类细致精确、对硬件要求低，数据全面深入、 更新及时的面向主题的搜索引擎，实现在互联网上有选择的采集用户需求的内 容并进行存储，它是基于主题的w e b 信息采集( f o c u s e dc r a w l i n g ) ，也称为 t o p l c s p e c i f i cc r a w l i n g ，主要是指选择性地搜寻那些与预先定义好的主题集 相关的页面进行采集的行为。 由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比通用 搜索引擎将更加有效和准确，具有以下优势： 首先，能更好的满足以下的信息获取的原则： 1 ) 主动、及时原则：信息获取工作要主动，要及时发现、及时捕捉和获取 各类信息。 2 ) 真实、可靠原则：获取的信息要符合客观事实，正确无误。 3 ) 针对需求原则：信息获取要根据用户的需求，有针对性、有重点、有选 择地获取利用价值大的，符合需求的信息。 4 ) 全面、系统原则：有针对性、有重点的获取是在全面、系统的进行信息 获取的基础上进行的。 其次，它还有传统搜索引擎所没有的优点： 1 ) 用户自己可以设置信息源和所需信息类型； 2 ) 具有信息自动化、本地化、集成化，最新化的特点。 2 2 研究方法 现在的互联网规模十分庞大，据权威的统计数据，2 0 0 2 年末，全球网站数 量已超过5 0 0 0 万个，如此多的站点之间并不是毫无联系的，介绍相同主题的站 点之间常常存在超链接相互指向，一个站点内部，相近主题的页面之间通常会 有超链接相互指向，使得我们能够从一个页面跳转另一个相关页面上，浏览整 第2 章研究的目标和方法 个互联网上的相关页面。 首先，我们仔细研究了互联网上的网站和网页的组成和各个页面之间的关 系；其次，是互联网页面的主题分布规律。 2 2 1 网页的组成 一个页面主要由页面正文( 有些时候可能没有) ，超链接等组成。 温家宝会见法国工商界人士并发表演讲 h t t p r m 蕾锄磷l z 月b m 坨人目e 碍 民研巴黎1 2 胄6 日电_ l 己者是缔敏、张况基、廖先旺报道。正在珐酏行正式访问的国 务院总理沮裹宝5 日在巴辑靓了法国工爵再 士。沮裹宝舟绍了中国圭阳平发展退路。建 设和罾社台的方针御拙，糖中国。十一五规划的实施。法国锻嶂，华合阼台有更加广 嗣的前景希望法国企业家抓佳机d 积撅参与中国的经8 f 建设，为中t 击全萄战略伙停黄蔡 帕发展敞出贡献 会见后t 掘寰宝酊往i 圭国胜协会总瞢向 圭官工商霁 士发衰了渍讲( 壁克异发 法 国肚协台主釉里佐靶中小企业龉长瞳恃恸耶在讲话中表示中国充蔫活力的发屣给捆 提供了t 要机矗法国企业一i 关注井伴随着中国的发羼期待两国经跻亩作聊j 露茁法 国酊总筑患所坦，外鲤# 长及洼国工商界人士近o o 出雨了最1 j 卜台 局日，温燕i 赶台见了；圭国前息统觎昕坦，对抽嫩期i ：l 来觏褫瞎萄中法* 系发隈衰示臀 苗希望他为魅袭为| i 匕作出贡献 羹蕾虞佳竹您盯万t 黼羹窖佩乐帮盅鬻毽 s 嗍孵钱的糟晶瑗目 中艮0 0 r 冁镘并迥目 特色镕燕最抑张神痹 蟾轼男人，迁体健量t 肾爝、犀褒症愿4 办 好男 蔓强，更自信 矗血压珀疗上的飞跃， 图( 1 )互联网上的页面 在页面上我们还定义了区域的概念，区域指的是在页面上位置相邻，内 容相关性很高的一个区域，是由人们的排版习惯而产生的。 第2 章研究的目标和方法 下图是区域的示例 图( 2 )区域的示例 区域中一般是和正文并且相互之间有很高相关性的超链接，通常一个页面 上会存在几个不同的区域 我们人为的上网浏览相关文档过程就是从一个站点( 我们还发现有的站点对 某些主题具有很好的相关性，可以在该站点中找到大量的相关性高的文档) 的 页面开始浏览，再浏览页面上的相关的超链接( 通常区域内的超链接有很高的 相关性，我们可以利用区域内的超链接快速找到相关文档) 指向的页面，不断 的重复这个过程从而实现浏览整个互联网上相关文档( 我们研究的是在不使用 搜索引擎的情况下的过程) 。 2 2 2 互联网页面主题分布规律 其次，整个w e b 上的页面主题分布是混杂的，但同一个主题在w e b 上分布却 有一些规律。我们将这些分布规律总结为以下四个特性：h u b 特性、 s 1 b l i n g l i n k a g el o c a h t y 特性、站点主题特性、t u n n e l 特性。 2 2 2 1h u b 特性 美国康奈尔大学的教授j o nm k l e i n b e r g 发现w e b 上存在大量的h u b 页面， 这种页面不但含有许多o u t l i n k 链接( 指出链接) ，并且这些链接趋向于相关同 一个主题。也就是说，h u b 页面是指向相关主题页面的一个中心。另外，他还定 义了权威页面( a u t h o r l t y ) 的概念，即其它许多页面都认为相关于这一主题有价 值的好页面。好的h u b 页面一般指向多个a u t h o r i t y 的页面，并且所指向的 a u t h o r i t y 页面越权威h u b 页面的质量也越好；反过来，h u b 页面的质量越好， 它所指向的每个页面也趋向于越权威。我们把主题在w e b 上的这一特性称为h u b 第2 章研究的目标和方法 特性。 这一特性很好的反映出了相关主题页面的区域特点。h u b 页面上的多个相关 的o u t l i n k 链接形成了区域。 2 2 2 2s i b i ；n g ，l i n k a g el o c a l i t y 特性 在h u b 特性的基础上，人们又提出了s 1 b l i n g l l n k a g el o c a l i t y 特性。 1 ) l i n k a g el o c a l i t y ，即页面趋向于拥有链接到它的页面的页面主题；即页面 a 上面存在链接到页面b 的链接，页面b 的主题和页面a 的主题趋向于一致。 2 ) s i b l i n gl o c a l i t y ，对于链接到某主题页面的页面，它所链接到的其它页面 也趋向于拥有这个主题。即页面a 上面存在链接到页面b 的链接，页面b 为主 题页面，页面a 上的其它链接指向的页面主题也趋向于页面b 的主题。 这实际上是h u b 特性的变形，主要是从页面的设计者设计的角度考虑的。 一个页面的设计者趋向于把本页面指向于与本页面相关的其他页面。我们把主 题在w e b 上的这一特性称为s 1 b l i n g l i n k a g el o c a l i t y 特性。 其中的s i b l i n gl o c a l i t y 的页面a 上的其它链接也组成了和主题相关的区 域。 2 。2 2 3 站点主题特性 我们发现，一个站点趋向于说明一个或几个主题，并且那些说明每个主题 的页面较紧密地在此站点内部链接成团，而各个主题团之间却链接较少。我们 认为，这主要与网站的设计者的设计思路有关。每个网站在设计时都有目标， 而这种目标往往就集中在一个或几个主题中。而网站的浏览者往往也有一定的 目的性，这个目的性一般体现在用户趋向于浏览同一主题的页面。为了满足浏 览者的这一需求，网站设计者需要将相关内容紧密地链接在一起。 这一特性反映出了相关主题页面的站点特点，一个站点上有和主题相关度 高的页面，那么该站点上的其它相关页面的相关度也较高。 1 4 第2 章研究的目标和方法 2 2 2 4t u n n e l 特性 在w e b 中还有一类现象，就是主题页面团之间往往需要经过较多的无关链 接才能相互到达。这些无关链接就像一个长长的隧道，连接着两个主题团，因 此我们把这种现象称为“隧道现象”( t u n n e l ) 。在基于主题的页面采集过程中， t u n n e l 的存在极大地影响着采集的质量。为了提高采集页面的准确率，我们需 要提高过滤相关性判定阈值，而阈值的提高将过滤掉大量的t u n n e l ，使得采集 系统很可能丢失t u n n e l 另一端的主题团，进而影响了查全率( 或者说资源发现 率) 。反过来，为了提高查全率，就得大量发现t u n n e l ，降低过滤相关性判定阈 值，但是阈值的降低使得混进了大量的无关页面，从而大大降低了页面的准确 率。这是一个两难问题，但关键还是不能有效地区别t u n n e l 和其它大量无关页 面。事实上，两个主题团之间的隧道数也较少。 为了更好的区分t u n n e l 和其它无关页面，我们引入了预测排队机制，把无 关的链接排在后面，当采集到它上面的链接时，发现有相关高的链接迅速的把 它上面的其它链接向队列的前面移动，从而穿越了隧道。 2 2 2 5 四个特性的关系 w e b 中的页面对于主题来说是杂乱的，但也存在一些规律。h u b 特性说明了 主题容易成团出现的现象，l 1 n k a g e s 1 b l l n gl o c a l i t y 特性进一步对成团的特 性有所扩展，站点主题特性说明了主题团所在的位置( 即大部分分布于站点的内 部) ，而t u n n e l 特征说明了主题团在w e b 上的分布并不稠密。 研究四个特性后我们提出了页面相关性预测排队反馈算法。在一个页面采 集前，我们已知的属性： 1 站点。页面所在站点，根据站点主题特性，一个站点和主题有相关性。 2 栏目。页面所在站点内的栏目和主题的相关性。 3 区域。指向本页面的超链接的所在的区域，根据h u b 特性和s i b l i n g l o c a l i t y 特性，区域和主题有相关性。 4 超链接文本。超链接的文本反映了页面的主题。 通过对以上四个属性赋予不同的权重，分别把各个相关性和各自权重相乘 最后相加到一起表示页面和主题的相关性的预测值，使得我们可以在一个页面 第2 章研究的目标和方法 采集前预测出页面和主题的相关性，把预测的相关性按照高低进行排队，先采 集高相关性的，后采集低相关性的，提高了采集的准确率和效率。 在一个页面采集后，我们还可以对页面的正文内容和主题进行相关性计算， 从而得出页面和主题的相关性的准确值，通过这个值得高低，对上面提到的站 点、栏目、区域属性的相关性进行调整，这个值高则把站点、栏目、区域属性 的相关性增大，反之则减小，并把预测队列中的相关性预测值进行更新，得出 一个更准确地预测值。从而实现了反馈机制，有了反馈机制更新站点、栏目、 区域属性的相关性，我们能够在采集的同时不断提高预测的准确性。 使用预测排队和反馈机制来穿越隧道( t u n n e l ) ，当一个页面和主题相关性 较低时，会排在队列的后面，最后采集完该页面后提取该页面上的超链接和超 链接文本，一旦发现有和主题相关性高的超链接，就利用反馈机制调整这个相 关性高的超链接的站点、栏目和区域属性的相关性，从而也会使得队列中该页 面上的其它的相关的超链接的预测值增大，向采集队列的队头移动，实现穿越 隧道。 第3 章系统模型、相关问题和算法 第3 章系统模型、相关问题和算法 根据我们上一章提出的预测排队和反馈算法，我们研究了s p l d e r 的模拟过 程之后，设计出了定向采集系统的模型，阐述了系统的相关问题和它们的解决 方法，以及系统的实现算法。 3 1 s p i d e r 模拟过程 s p i d e r ，又称r o b o t 或c r a w l e r ，是专门用来搜集互联网上各种文档信息( 网 页) 的一种智能主体，具有独立的工作和决策能力，能自动地在互联网上搜索 爬行，并将搜集的信息返回给服务器。一般地，s p i d e r 从一定的初始u r l 地址 出发，根据u r l 中指向其它u r l 地址的超链接而跳到其它的u r l ，进而不断地深 入和扩展，基本上遍历整个网络。 搜索主要步骤可以如下： 1 ) s p i d e r 从初始u r l 列表中取出u r l 并从网上获取其h t m l 文档内容； 2 ) 从每个h t m l 文档中提取信息并放入网页数据库中； 3 ) 从h t m l 文档中提取指向其它页面文档的u r l ，并加入到u r l 列表中； 4 ) 重复以上三个步骤，直到再没有新的u r l 发现或超出了一定限制条件 ( 如时间或磁盘空间的限制) ； 搜索算法有深度优先和广度优先两种基本的搜索策略。s p i d e r 依据u r l 列 表的存取方式决定搜索策略： 1 ) 先进先出的队列方式，则形成广度优先搜索。当起始u r l 列表包含有大 量的网站服务器地址时，广度优先搜索将产生一个很好的初始结果，但 很难深入到服务器中去。 2 ) 先进后出的堆栈方式，则形成深度优先搜索。这样能产生较好的文档分 布，更容易发现文档的结构，即找到最大数目的交叉引用。 我们所使用的搜索算法称之为预测排队优先，根据u r l 的相关性进行排队， 相关性高的先下载，相关性低的后下载。 第3 章系统模型、相关问题和算法 下图是用s p i d e r 浏览相关文档的过程： 图( 3 )网络拓扑图 上图展示了s