（计算机应用技术专业论文）综合风险垂直搜索引擎的研究与实现.pdf

摘要 摘要 随着i n t e r n e t 信息的爆炸性增长以及信息多元化的发展，通用搜索引擎已经 无法提供令专业人员满足的行业知识搜索，而提供专业信息搜索服务的垂直搜 索引擎正逐渐成为当前搜索引擎研究的热点。文章分析当前w e b 信息检索的模 型及算法，并针对基于文本分类器的综合风险行业信息垂直搜索中的一些关键 问题展开研究，主要包括三个核心模块：综合风险的信息分类、信息爬取和信 息索引。研究内容包括： 1 提出了一种遗传算法与支持向量机相结合的w e b 文本分类器模型。结合 h t m l 标记权重信息建立向量空间模型，弥补了特征项在文本集合中分 布的差异。向量空间的特征选择上采用改进了交叉算子的遗传算法，降 低了向量维数。分类算法分析了支持向量机在w e b 文本分类中的优势， 采用支持向量机算法，通过对比实验证明了该分类器模型的有效性。 2 改进了爬行器中动态搜索的f i s h 算法。去掉了f i s h 算法中对风险信息爬 取意义不大的中间部分，改进了f i s h 算法中的u r l 排序算法。爬虫设 计上提出了基于s t r a t e g y 模式的搜索策略模块设计，提高了系统的可扩 展性。 3 建立了一个单汉字索引数据库分析了基于分词的索引模型和基于单汉 字的索引模型，针对综合风险词汇更新较快的特点和分词索引的不足， 利用倒排索引技术建立了单汉字索引数据库。用户查询使用“首字定位， 全词匹配”的查询算法，提高了查询效率 4 设计实现了一个综合风险垂直搜索引擎，提供风险行业的信息搜索专业 性服务，具有良好的可扩展性 本课题得到了“十一五”国家科技支撑计划重点项目“综合风险防范 ( 承g ) 关键技术研究与示范”( 2 0 0 6 b a d 2 0 8 0 2 ) 支持。 关键词：垂直搜索，综合风险，遗传算法，支持向量机 a b s t r a c t a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ha n dd i v e r s i f i c a t i o no fi n t e m e ti n f o r m a t i o n ，g e n e r a l s e a r c he n g i n e sh a v eb e e nu n a b l et op r o v i d ep r o f e s s i o n a ls e r v i c e s v e r t i c a ls e a r c h e n g i n e sa r eg r 删l ya sh o t 鹊c u r r e n tg e n e r a ls e a r c he n g i n e s t h ec u r r e n tm o d e la n d a l g o r i t h mo fw e bi n f o r m a t i o nr e t r i e v a la f ea n a l y z e da n da n u m b e ro fk e yi s s u e sa r e d i s c u s s e di nt h et e x tc l a s s i f i e rb a s e dv e r t i c a ls e a r c he n g i n eo fi n t e g r a t e dr i s k i n f o r m a t i o n t h e r ea r et h r e ec o r em o d u l e s ：i n t e g r a t e dr i s ki n f o r m a t i o nc l a s s i f i c a t i o n , i n f o r m a t i o nc r a w l i n ga n di n f o r m a t i o ni n d e x i n g t h er e s e a r c hi n c l u d e s ： 1 aw e bt e x tc l a s s i f i e rm o d e lc o m b i n e dg e n e t i ca l g o r i t h ma n ds u p p o r tv e c t o r m a c h i n ei sp r o p o s e d v e c t o rs p a c em o d e li sc o n s t r u c t e d 、i n lh t m l t a gw e i g h t s ， w h i c ho f f s e tt h ed i s t r i b u t i o nd i f f e r e n c e so ft e x tt e r m s g e n e t i ca l g o r i t h mw i t h i m p r o v e dc r o s s o v e ro p e r a t o ri su s e df o rf e a t u r es e l e c t i o nw h i c hl o w e r sv e c t o r d i m e n s i o n s s u p p o r tv e c t o rm a c h i n e sa d v a n t a g e sa a n a l y z e d a n ds v m i su s e d f o rw e bt e x tc l a s s i f i c a t i o n t h ee x p e r i m e n t sr e s u l t ss h o wt h ee f f e c t i v e n e s so f t h i s m o d e l 2 m a k ei m p r o v e m e n t si nf i s ha l g o r i t h m , t h ed y n a m i cs e a r c ha l g o r i t h mo f i n t e g r a t e dr i s kc r a w l e r t h em i d d l ep a r to ff i s ha l g o r i t h mi se l i m i n a t e da n dt h e u r l s o r t i n g , a l g o r i t h mi su p d a t e d c r a w l e rd e s i g ni sb a s e do ns t r a t e g yp a t t e r n a n di t se x p a n s i b i l i t yi si m p r o v e d 3 e s t a b l i s has i n g l ec h i n e s ec h a r a c t e ri n d e x i n gd a t a b a s e i n d e x i n gm o d e l sb a s e o nw o r d ss p l i t t i n ga n ds i n g l ec h a r a c t e ri sa n a l y z e d s i n c et h ew o r d so fi n t e g r a t e d r i s ki su p d a t e dr a p i d l ya n dd r a w b a c k se x i s t si nw o r d ss p l i t t i n gi n d e x i n gm o d e l ， t h ei n d e x i n gd a t a b a s ei sc o n s t r u c t e db a s e do ns i n g l ec h i n e s ec h a r a c t e ri n d e x i n g m o d e la n di n v e r t e dl i s tt e c h n o l o g y c l i e n t s 峨t h em e t h o do f “f i r s tc h a r a c t e r d e t e r m i n et h ep o s i t i o n ，t h e nf i n dt h ew h o l ew o r d ”t oq u e r yi n f o r m a t i o n , a n dt h e q u e r ye f f i c i e n c yi si m p r o v e d 4 d e s i g na n di m p l e m e n ta ni n t e g r a t e dr i s kv e r t i c a ls e a r c he n g i n e ，p r o v i d i n g n a b s t r a c t p r o f e s s i o n a lr i s ki n f o r m a t i o nq u e r ys e r v i c e sw i t he x c e l l e n te x p a n s i b i l i t y t h er e s e a r c hw o r ki ss u p p o r t e db yk ：yn a t i o n a ls c i e n c ea n dt e c h n o l o g yp r o j e c to f t h e l l t hf i v e - y e a r ”p l a n ，”k e yt e c h n o l o g yr e s e a r c ha n dd e m o n s t r a t i o no f i n t e g r a t e d r i s kg u a r d i a n s ”( n o 2 0 0 6 b a d 2 0 8 0 2 ) k e y w o r d s ：v e r t i c a ls e a r c h ，i n t e g r a t e dr i s k , g e n e t i ca l g o r i t h m ，s u p p o r tv e c t o r m a c h i n e i l l 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适 学位论文作者签名： 砷 指导教师 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：撇 砰年多月陟日 第一章绪论 第一章绪论 本章主要介绍了关于搜索引擎的基本概念，搜索引擎的发展历史，通用搜 索引擎以及垂直搜索的研究现状，分析了综合风险的垂直搜索研究背景，给出 了文章的主要研究内容及全文组织结构等内容 1 1 引言 现代科学技术的发展将人类带入了一个名符其实的“信息爆炸”时代。美国 加利福尼亚大学伯克利分校研究人员发现，仅用3 年时间，全球新生产出的信 息量就翻了一番。据这所大学发布的新闻公报介绍，该校信息管理及系统学院 莱曼教授领导的小组在研究中对多种信息源进行了采样分析。结果发现，2 0 0 2 年中全球由纸张、胶片以及磁、光存储介质所记录的信息生产总量达到5 万亿 兆字节，约等于1 9 9 9 年全球信息产量的两倍换句话说，在1 9 9 9 年到2 0 0 2 年 这3 年间，世界范围内信息生产量以平均每年3 0 左右的速度递增。美国著名 的未来学家奈斯比特n i s b i t t j 在 大趋势一书中说到：“我们淹没在信息中但 是却渴求知识”为何当信息潮水般向我们涌来，我们却缺乏所需要的信息呢? 这主要是因为我们缺乏有效的信息搜索手段。 据中国互联网中心报道l l l ，截至到2 0 0 7 年1 月，中国网站总数达到了 8 4 3 ，0 0 0 个，网贞总数达到“7 亿个，网页字节总数为1 2 2 ，3 0 6 g b 。由于i n t e r a c t 上的信息呈几何级数增长，而这些信息又是极其无序的，因此想要在这个浩瀚 无垠、瞬息多变的信息海洋中迅速、准确地找到自己所需要的信息无异于“大 海捞针”搜索引擎正是为了解决这个“迷航”问题而出现的技术。搜索引擎以 一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理， 并为用户提供检索服务，从而起到信息导航的目的搜索引擎提供的导航服务 已经成为互联网上非常重要的网络服务，搜索引擎站点也被美誉为“网络门户” 自1 9 9 4 年基于w e b 的搜索引擎出现以来，搜索引擎便得到了极大的发展根 据统计，大约8 5 的用户使用搜索引擎去定位他们需要的信息。因此，搜索引 擎研究对于网络信息资源的有效开发和利用具有重要的意义。 第一章绪论 1 2 搜索引擎的发展状况 1 2 1 搜索引擎发展简史 早在w e b 出现之前，互联网上就已经存在许多旨在让人们共享的信息资源 了。那些资源当时主要存在于各种允许匿名访问的f t p 站点( a n o n y m o u sf 砸) ， 由于当时还没有h t m l ，内容以学术技术报告、研究性软件居多，它们以计算 机文件的形式存在，文字材料的编码通常是p o s t s c r i p t 或者纯文本 2 1 。 1 9 9 0 年，加拿大麦吉尔大学( u n i v e r s i t yo f m c g i l l ) 计算机学院的师生开发 出a r c h i e ，人们通过f t p 来共享交流资源。虽然a r c h i e 搜集的信息资源不是网 页( h r m i ，文件) ，但和搜索引擎的基本工作方式是一样的；自动搜集信息资源、 建立索引、提供检索服务所以，a r c h i e 被公认为现代搜索引擎的鼻祖 1 9 9 3 年m a t t h e wg r a y 开发了w o r l dw i d ew e bw a n d e r e r ，这是第一个利用 h t m l 网页之间的链接关系来检测万维网规模的“机器人( r o b o t ) ”程序。开 始，它仅仅用来统计互联网上的服务器数量，后来也能够捕获网址( u r l ) 1 9 9 4 年4 月，斯坦福大学( s t a n f o r du n i v e r s i t y ) 的两名博士生，美籍华人 j e r r yy a n g ( 杨致远) 和d a v i df i l o 共同创办了y a h o o 。随着访问量和收录链接 数的增长，y a h o o 目录开始支持简单的数据库搜索。因为y a h o o ! 的数据是手工 输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。 1 9 9 4 年7 月，卡内基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的m i c h a e l m a u l d i n 将j o h nl e a v i t t 的s p i d e r 程序接入到其索引程序中，创建了l y c o s 除 了相关性排序外，l y c o s 还提供了前缀匹配和字符相近限制，l y c o s 第一个在搜 索结果中使用了网页自动摘要，而最大的优势还是它远胜过其它搜索引擎的数 据量。 1 9 9 5 年1 2 月，d e c 的正式发布a l t a v i s t a 。a l t a v i s t a 是第一个支持自然语 言搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎( 如a n d ，o r , n o t 等) 用户可以用a l t a v i s t a 搜索新闻组( n e w s g r o u p s ) 的内容并从互联网上获 得文章，还可以搜索图片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s 、搜索 a c t i v e x o b j e c t s 。a l t a v i s t a 也声称是第一个支持用户自己向网页索引库提交或删 2 第一章绪论 除u r l 的搜索引擎，并能在2 4 小时内上线。 ， 1 9 9 5 年9 月2 6 日，加州伯克利分校助教e r i cb r e w e r 、博士生p a u lg a u t h i e r 创立了i n k t o m i 1 9 9 6 年5 月2 0 日，i n k t o m i 公司成立，强大的h o t b o t 出现在 世人面前。声称每天能抓取索引1 千万页以上，所以有远超过其它搜索引擎的 新内容h o t b o t 也大量运用c o o k i e 储存用户的个人搜索喜好设置。 1 9 9 8 年l o 月之前，g o o g l e 只是斯坦福大学( s t a n f o r du n i v e r s i t y ) 的一个 小项目b a c k r u b 。1 9 9 5 年博士生l a r r yp a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册了g o o g l e c o m 的域名，1 9 9 7 年底，在s e r g e ) , b r i n 和s c o t t h a s s a n 、 a l a ns t e r e m b e r g 的共同参与下，b a c h _ r u b 开始提供d e m o 。1 9 9 9 年2 月，g o o g l e 完成了从a l p h a 版到b e t a 版的蜕变。g o o g l e 以网页级别( p a g e r a n k ) 为基础， 判断网页的重要性，使得搜索结果的相关性大大增强。 f a s t ( a l l t h e w e b ) 公司创立于1 9 9 7 年，是挪威科技大学0 q t n l d 学术研究的 副产品。1 9 9 9 年5 月，发布了自己的搜索引擎a l l t h e w e b 。f a s t ( a l l t h e w e b ) 的网页搜索可利用o d p 自动分类，支持f l a s h 和p d f 搜索，支持多语言搜索， 还提供新闻搜索、图像搜索、视频、m p 3 、和f t p 搜索，拥有极其强大的高级 搜索功能( 2 0 0 3 年2 月2 5 日，f a s t 的互联网搜索部门被o v e r t u r e 收购) 中文搜索相对起步比较晚。1 9 9 6 年8 月，s o h u 公司成立，制作中文网站分 类目录随着互联网网站的急剧增加，这种人工编辑的分类目录已经不适应 s o h u 于2 0 0 4 年8 月独立域名的搜索网站“搜狗”，自称“第三代搜索引擎”。 o p e n f m d 创立于1 9 9 8 年1 月，其技术源白台湾中正大学吴升教授所领导的 o a i s 实验室。o p e n f m d 起先只做中文搜索引擎，鼎盛时期同时为三大著名门户 新浪、奇摩、雅虎提供中文搜索引擎，但2 0 0 0 年后市场逐渐被b a i d u 和g o o g l e 瓜分。2 0 0 2 年6 月，o p e n f i n d 重新发布基于g a i s 3 0p r o j e c t 的o p e n a n d 搜索引 擎b e t a 版，推出多元排序( p o l y r 锄k t m ) ，宣布累计抓取网页3 5 亿，开始进入 英文搜索领域。 2 0 0 0 年1 月，两位北大校友，超链分析专利发明人、前i n f o s e e k 资深工程 师李彦宏与好友徐勇( 加州伯克利分校博士后) 在北京中关村创立了百度 ( b a i d u ) 公司。2 0 0 1 年8 月发布b a i d u t o m 搜索引擎b e t a 版，2 0 0 1 年l o 月 2 2 日正式发布b a i d u 搜索引擎，专注于中文搜索。 第一章绪论 2 0 0 3 年1 2 月2 3 日，原慧聪搜索正式独立运做，成立了中国搜索2 0 0 4 年 2 月，中国搜索发布桌面搜索引擎网络猪1 0 ，2 0 0 6 年3 月中搜将网络猪更名为 i g ( i n t e m e tg m e w a y ) 2 0 0 5 年6 月，新浪正式推出自主研发的搜索引擎“爱问” 搜索引擎出现虽然只有1 0 年左右的历史，但在w e b 上已经有了确定不移 的地位。据c n n i c 统计，它已经成为继电子邮件之后的第二大w e b 应用。虽 然它的基本工作原理已经相当稳定，但在其质量、性能和服务方式等方面的提 高空间依然很大，研究成果层出不穷，是每年w w w 学术年会的重要论题之一 1 2 2 通用搜索引擎 上一节讲到的搜索引擎关注广大用户的搜索需求，因而也被称为通用搜索 引擎它们通常使用一个或多个的w e b 信息提取器( 网络蜘蛛) 从i n t e m e t 上 收集各种数据( 如w w w ) n e w s , e - m a i l ，f t p ) ，然后在自身服务器上为这些数 据创建索引，当用户搜索时根据用户提交的查询条件从索引库中迅速查找出所 需的信息返回给用户。 一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成【3 川。 搜索器 搜索器的功能是在互联网中漫游，发现和搜集信息。它常常是一个计算机 程序，日夜不停地运行它要尽可能多、尽可能快地搜集各种类型的新信息， 同时因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息， 以避免死连接和无效连接。目前有两种搜集信息的策略： 1 ) 从一个起始u r l 集合开始，顺着这些u r l 中的超链( h y p e r l i n k ) ，以 宽度优先、深度优先或启发式方式循环地在互联网中发现信息。这些 起始u r l 可以是任意的讲也，但常常是一些非常流行、包含很多链接 的站点( 如y a h 0 0 1 ) 2 ) 将w e b 空间按照域名、i p 地址或国家域名划分，每个搜索器负责一卜 子空间的穷尽搜索搜索器搜集的信息类型多种多样，包括h t m l 、 x m l 、n e w s g r o u p 文章、f t p 文件、字处理文档、多媒体信息。搜索 4 第一章绪论 器的实现常常用分布式、并行计算技术，以提高信息发现和更新的速 度。商业搜索引擎的信息发现可以达到每天几百万网页。 索引器 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示 文档以及生成文档库的索引表。 索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关， 如作者名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等等： 内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内 容索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索引项对 于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ； 对于中文等连续书写的语言，必须进行词语的切分。 在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引项对文档 的区分度，同时用来计算查询结果的相关度使用的方法一般有统计法、信息 论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 索引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ，即由索引项查找相应 的文档索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索 引项之间的相邻或接近关系( p r o x i m i t y ) 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必 须实现即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速度。 索引算法对索弓f 器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。 一个搜索引擎的有效性在很大程度上取决于索引的质量。 检索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查 询的相关度评价，对将要输出的结果进行捧序，并实现某种用户相关性反馈机 制 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合 模型四种 用户接口 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机 5 第一章绪论 制。主要的目的是方便用户使用搜索引擎，高效率、，多方式地从搜索引擎中得 到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以 充分适应人类的思维习惯。 用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输 入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算( 与、 或、非) 、相近关系( 相邻、n e a r ) 、域名范围( 如e d u 、c o r n ) 、出现位置( 如 标题、内容) 、信息时间、长度等等目前一些公司和机构正在考虑制定查询选 项的标准。 通用搜索的引擎框架图如图1 1 所示。 1 2 3 垂直搜索引擎 图1 1 搜索引擎框原理图 在过去的十几年中，搜索引擎技术也跟随w e b 信息的急速增长而快速发展， 当前的大规模搜索引擎如1 3 0 0 9 l e 可以处理数十亿网页嗍由于当前网站的迅速 增多，w e b 信息存储量增长越来越快，网站更新越来越频繁。集中式的通用搜 。一，索引擎因无法保持相应的增长速度而搜索覆盖的信息里下降趋势，其巨大的索 引数据和广泛搜索主题也带来了较低的搜索效率，为了获取数条相关信息，用 6 第一章绪论 户不得不在大量的失效信息甚至垃圾信息中费力寻找。目前人们对搜索引擎的 首要关注点已经从如何找到更多的信息转向如何快速找到准确、有用的信息。 因此近年来专为查询某一主题或学科信息的主题搜索引擎应运而生，也称之为 垂直搜索引擎或者主题搜索引擎，本文统称为垂直搜索引擎。与通用搜索引擎 相反，垂直搜索引擎使用有限的计算资源和存储空间，专门采集某一学科、某 一主题、某一行业范围的信息资源，并用更为详细和专业的方法对信息资源进 行标引和描述，且往往在信息组织设计上利用与该专业密切相关的方法技术。 垂直搜索引擎概念的提出，就是针对性的为某一特定领域、某一特定人群 或某一特定需求提供的有一定价值的信息和相关服务可以简单的说成是搜索 引擎领域的行业化分工。众多专业性网站、行业网站独立服务于互联网的成功， 恰恰证明了互联网的格局应该是多方面的。通用搜索引擎的性质，决定了其不 能满足特殊领域、特殊人群的精准化信息需求服务。市场需求多元化决定了搜 索引擎的服务模式必将出现细分，针对不同行业提供更加精确的行业服务模式。 可以说通用搜索引擎的发展为垂直搜索引擎的出现提供了良好的市场空间，势 必将出现垂直搜索引擎在互联网中占据部分市场的趋势，也是搜索引擎行业细 分化的必然趋势。 1 2 4 垂直搜索研究现状 目前，有关主题搜索引擎的研究正在成为一个热点研究领域，下面介绍一 些较具有代表型的主题搜索引擎系统。 1 ) e l s e v i e r 公司的s c i r u s 系统 s e i r u s 科学搜索引擎是一个专门为搜索高度相关的科学信息而设计的主题 搜索引擎s e i r u s 是目前互联网上最全面、综合性最强的科技文献门户网站之 一它的搜索领域只面向包含有科学内容的网站，如大学和作者个人主页以及 e l s e v i e r 公司自己的数据库。 2 ) b e r k e l e y 的f o c u s e dp r o j e c t 这个系统由一个印度裔的科学家s c h a r k r a b a r t i 带头从事开发。该系统通过 两个程序来指导主题网络蜘蛛，一个是主题分类器c l a s s i f i e r ，用来计算下载的 7 第一章绪论 文档与预定主题的相关程度。另一个则是净化器d i s t i l l c f ，用来确定那些链接指 向很多相关资源的页面。 3 ) 美国的国家科学数字图书馆的c o l l e c t i o n b u i l d i n g p r o g r a m ( c b p ) 该项目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试 图研究在某一主题资源中自动建设数字图书馆的可能性。c b p 具有三个突出的 特点：第一，由于c b p 项目面向教育、教学，主题精确度( p r e c i s i o n ) 比覆盖度 ( r e c a l l ) 更为重要；第二，c b p 并不存储资源原文，只是提供资源的u r l ；第三， c b p 只需要用户输入少量信息，如关键词，系统就可以自动的将有关该主题的 最相关的u r l 返回给用户。 1 3 选题背景及研究意义 目前，我国是世界上自然灾害最严重的少数国家之一。据统计嘲，2 0 0 6 年 全国因自然灾害死亡3 1 8 6 人，紧急转移安置1 3 8 4 5 万人( 次) ；农作物受灾面积 4 1 0 9 1 3 千公顷，其中绝收面积5 4 0 8 9 千公顷：倒塌房屋1 9 3 - 3 万间；因灾直接 经济损失2 5 2 8 1 亿元。而且，随着社会经济的发展和人类活动的增强，自然灾 害的损失还在以更快的速度增长，给人民生命财产带来了巨大损失，严重影响 了我国的可持续发展。为了推进我们自然灾害综合风险防范的数字化、信息化 建设，国内许多风险防范方丽的研究所、高校、政府部门等纷纷建立起自己的 综合风险信息网站。但是由于综合搜索引擎自身的局限，综合风险主题信息的 获取仍然十分困难 为贯彻国家中长期科学和技术发展规划纲要( 2 0 0 6 - - 2 0 2 0 ) ) 精神，落 实“农业领域”中保障农业生态安全，以及“公共安全领域”提高国家综合减 灾能力的目标，科技部决定启动综合风险防范关键技术研究与示范重点项 目，该项目已经通过专家论证。通过该项目的实施，将形成我国综合风险防范 的关键技术体系，开发若干项具有自主知识产权的技术、专利和软件，形成综 合风险防范的技术集成平台，制定完善我国综合风险分类体系、评价标准，以 及综合风险防范的制度体系，实现我国综合风险防范能力提升与改善关键技术 的跨越式发展，为我国综合减灾能力的提高及风险防范体系的建立提供先进技 8 第一章绪论 术支撑。建立综合风险行业信息垂直搜索引擎能为广大的综合风险防范工作者、 科研人员、民政部门以及林农提供快速准确的自然灾害风险信息，必将大大推 动我国自然灾害风险防范信息化工程的建设。 1 4 本文的研究内容和论文结构 针对行业信息的垂直搜索引擎是当前搜索引擎研究的热点，本文针对国家 在综合风险防范方面提出的相关要求，实现了基于文本分类器的综合风险垂直 搜索引擎。重点研究了基于遗传算法和支持向量机的文本分类器，基于改进的 f i s h 算法的爬行器和基于单汉字索引的索引数据库等方面的内容。 论文结构安排如下： 第一章简单介绍了搜索引擎的发展过程和理论基础，展现了当前通用搜索 引擎的不足及垂直搜索的特点。根据当前国家在综合风险防范方面的相关政策， 阐述了构建综合风险搜索引擎的必要性 第二章介绍了当前的网页信息检索模型。详细介绍了布尔模型、向量空间 模型，检索算法详细介绍了基于内容的检索和基于超链接的检索。 第三章重点叙述了垂直搜索引擎不同于通用搜索引擎的重要部分一网页 信息分类器的设计，针对h t m l 文本的半结构化特征使用h t m l 标记权重的 方法提高w e b 文本分类的准确率，利用标记权重的h t m l 文本特征建立向量 空间模型，提出了基于遗传算法和支持向量机的w e b 文本分类方法，并做了相 关的实现工作 第四章主要介绍了综合风险垂直搜索引擎的信息采集部分爬行器的设 计。介绍了不同的爬虫搜索策略和遍历策略，针对f i s h 算法的不足，提出了改 进的f i s h 算法 第五章介绍了综合风险垂直搜索引擎部分的网页信息索引模块的实现。根 据风险词汇的特征提出使用单汉字索引模型建立索引数据库。文件存储使用倒 排文件的格式，提高了检索效率，缩短了检索时间 第六章给出了基于上述理论的系统实现框架和系统运行界面。 第七章总结了本文的工作，并提出了综合风险垂直搜索的未来和发展趋势。 9 第二章w e b 信息检索理论基础 第二章w e b 信息检索理论基础 要准确快捷地获取到所需要的信息，就要有合适的信息检索模型和检索算 法。本章就常见的信息检索模型以及主要的信息检索算法作了介绍，首先详细 介绍了信息模型中的布尔逻辑模型、模糊逻辑模型、向量空间模型和概率模型， 其次介绍了基于内容的检索方法和基于超链接分析的检索方法，并对两种超链 接分析算法- p a g e r a n k 和h i t s 傲了比较分析 2 1 信息检索模型 布尔逻辑模型是最简单的检索模型，也是其他检索模型的基础。标准布尔 逻辑模型为二元逻辑，即一系列对应于文件特征的二元变量。这些变量包括从 文件中提取的文本检索词，有时也包括一些更为复杂的特征，如数据、短语、 私人签名和手工加入的描述子在布尔模型中有确切的文件特征表达集合。用 户可以根据检索项在文档中的布尔逻辑关系递交查询。匹配函数由布尔逻辑的 基本法则确定。所检索出的文档或者与查询相关，或者与查询无关。查询结果 一般不进行相关性排序。 模糊逻辑模型为了处理精度和复杂性之间的矛盾而引入的，它以逻辑真值 为【o ，l 】的模糊逻辑为基础的，以隶属函数概念来描述现象差异的中间过渡。 在查询结果处理过程中引入模糊逻辑运算，将所检索的文件信息和用户的查询 要求进行模糊逻辑比较，按照相关性的优先次序排出查询结果，在布尔检索中 借助模糊逻辑模型能够克服布尔逻辑查询结果的无序性 向量空间模型和布尔逻辑模型不同，向量空间模型中查询和文件都映射为 同一n 维空间向量。利用奇异值分解( s v d ) ，查询词和文件的内部结构联系， 通过欧几里德距离和余弦法则作相似性比较，根据向量空间的相似性，排列查 询结果。向量空间模型不仅可以方便地产生有效的查询结果，而且能够提供查 询结果分类，为用户提供准确定位所需的信息 概率模型的引入是由于在信息检索中存在不确定性问题，对查询本身来说， 它不能唯一地表示信息需求，对于结果来说，定查询结果的正确与否。对于布 1 0 第二章w e b 信息检索理论基础 尔检索也是如此，因为查询的提交本身就是一种不确切方式。因此为了解决在 布尔检索模型中的不确定性问题而引入概率模型。该模型基于概率排队理论： 当文件按相关概率递减原则排列时可以获得最大的检索性能。 2 2 信息检索算法 确定了信息模型后，下步的重要工作就是对信息进行加工处理，并选择 适当的算法进行检索。 2 2 1 基于内容的检索 基于内容的检索方法是传统的检索方法，主要是考虑用户提交的查询串在 文档集中的出现情况，包括特征项频率、特征项位置信息等等。代表性的方法 有：基于特征项频率的检索方法、基于特征项位置信息检索方法【8 1 1 ) 特征项频率的检索方法 向量空间模型是根据特征项频率进行检索的典型算法 9 1 ，最初由s a l t o n 等 人提出并发展起来的该模型主要是将给定的文本( 文章、查询串或文章的一 段等) 看作由相互独立的词条组( t i ，t ：，厶) 构成，对于每一个词都根据其在 文档中的重要程度赋以一定的权值嵋，将( t l , t 2 ，厶) 看成一个，l 维坐标系中 的坐标轴，( w i ，) 为对应的坐标值，从而转化为一个向量空间。词条“ 在文档西中的权值通常由两部分计算获得：一部分是词条k 在文档吐中出现 的次数，即以另一部分是整个文档集合中包含词条k 的文档个数，即i 矾 这样有： = 以+ 磁= 以+ ( 1 0 9 2 ( ，仇) + 1 ) ( 2 1 ) 其中，代表文档集合中的文档数量，仇代表在文档集合中出现特征项 的文档数耳从公式( 2 1 ) 中可知，吮越大，值越大；同样以值越小，w 业 ；一，j 。 值就越大说明该特征项r i 更能代表文档哦的内容。 第二章w e b 信息检索理论基础 进行文档向量与查询向量的相似度s i r e ( d , ，q ) 比较，通常采用余弦法： 吼 s i r e ( d , ，q ) = c o s o = 产= 型= = = = 一 1 f ( w 止2 ) ( 吼2 ) ( 2 2 ) 再进行查询匹配，查询条件q 的向量化过程可采用布尔模型进行： q ：妻，呈(23)j1 1 , 一2l ”，若；，芒q 屹。j 特征向量0 出现在查询条件q 中，n q ，为l ，否则为0 相似度值越高说明两者之间越相关，越能反映用户的查询要求。因此，向 量空间模型算法计算简单并且有效，得到广泛的应用 9 1 。但是它也存在以下的 缺点： 各个特征项不论处于文档中何种位置，表达文档内容的能力是相同的。 而实际上出现在文档不同位置的特征项对文档内容的贡献程度是不一 样的，比如出项在标题的特征项应该比出现在摘要中的特征项作用显得 更为重要。 w e b 文档信息之间的变迁是通过链接完成的，因此，链接的文本信息从 某个角度上来说代表了被链接w e b 文档的重要信息，而利用向量空间 模型进行w e b 信息查询忽视了这些信息。 2 ) 特征项位置的检索方法 m i c h a lc u r e r 1 0 l 算法根据特征项位置信息，利用h t m l 文档结构和链接信 息进行检索的方法该方法首先将h t m l 标记分为六类：p l a i nt e x t ( i e 文) ， t i t l e ( 标题) 、h l h 2 、h 3 h 6 ，s t r o n g ( 包括强调、粗体，斜体、下划线) 、a n c h o r ( 链 接标记文本) ，并根据重要程度对每类赋以不同的重要度因子c v 。特征项权值 的计算公式为： w = ( z f 矿+ c v ) + 豇扩 ( 2 4 ) 其中，巧y 代表特征项频率向量，t f v = ( 咖。，咖：，f l y 。) ，分别表示特征 项t 在正文、s t r o n g 、h 3 一h 6 、h l - h 2 、标记及标题中出现的次数。当 1 2 第二章w e b 信息检索理论基础 c v = ( 1 1 1 l ，0 ，1 ) 时，特征项t 的权值计算转变为向量空间模型的权值计算公式： w = ( z ：f y + c g o + i d f = ( h + 咖2 + + 吒) + l a y = t f i a f ( 2 5 ) 不同类别赋以不同重要度因子是因为查询匹配过程中，出现在w 曲中不同 位置的同一关键词表达文档内容的能力是有差别的。比如，出现在标题中的特 征项应该比出现在链接中的特征项更能确切代表文档的内容，同样出现在链接 中的特征项也要比出现在正文中的特征项更能代表文档的内容，因此该方法有 效地提高了检索质量。但同时该方法也存在不足：特征项权值的计算使用了反 比文献频率i d l ，每当文档集合增加一篇文档，文档总数就会发生改变，包含 该特征项的文档数目也随之发生变化，因此必须重新计算每一特征项的权值， 计算量太大，不适用于文档的动态更新根据特征项出现在不同部分将一篇文 档从逻辑上划分为个相对独立的文本段【l ，出现在不同独立段的特征项具有 不同的权值，权值的计算公式为； ： ( 2 6 ) ，i 其中，吮表示第k 个特征项在第i 个文本段中出现的频率，表示第i 个文 本段的长度，这样既避免了使用反比频率i a f , ，有利于实现文档的动态更新， 又体现了不同位置信息的特征项表达文档内容的不同能力。文献 1 2 1 认为m i e h a l 算法将h t m l 标签分为6 类仅仅基于作者对文章标题等的一般性看法，并不能 证实这样的分类是合理的。因此，它提出了利用聚类将h t m l 标记进行划分的 思想。分类在一组相似性很高的h n 压l 文档中进行，根据标签类别合并文档， 然后将这些标签文档相互比较，如果文档两两相近，则合并两个标签，有效地 改善了检索质量。 2 2 1 基于超链接的检索 在网页中创建了一条指向其它网页的超链接，特别是指向另一网站的超链 接，包含了一种有价值的人为判断，它表明了两个网页之间内容的相关性和延、一 续性如果把网页和网页上的超链接看作是一个有向图的点和边，则互联网就 是一个巨大的有向图，在这个有向图上，同一主题的网页之间的链接密度远远 第二章w e b 信息检索理论基础 大于不同主题网页之间的链接密度于是，依据主题的不同，互联网形成了一 个个内部耦合紧密，外部疏松的网络社区。同样地，在网络社区中，与主题相 关的权威页面的链接密度大于一般的页面。如果能够通过分析有向图的链接情 况得到这些权威页面以及它们的排名。不就可以提高搜索引擎的检索质量吗? 基于结构分析的基本思想就是充分利用超链接结构所包含的这种信息。 网页的创建和浏览是互联网的两种基本的行为，如果从用户浏览的角度来 看，结构分析的思想经常对应着用户浏览网页的行为模式。因为用户的浏览过 程，实际是对有向图的一种遍历，而网页节点在某一步被用户遍历到的概率就 是结构分析算法所要追求的权值。不同的用户浏览模式对应的概率不同，也就 对应着不同的结构分析算法。 目前，有关这方面的研究提出了如下方法。 p a g e r a n k 技术 p a g e r