（信号与信息处理专业论文）基于internet的文本口语检索的研究.pdf

北京交通大学博士学位论文 摘要 摘要 随着i n t e r n e t 的迅猛发展，i n t e r n e t 承载了无比浩瀚的海量信息，如何从这 些海量信息中方便高效地获取信息和知识，是当今一个非常重要的研究课题。文本 检索是信息获取、知识获取的一个重要途径，从基于关键字的全文检索到基于自然 语言处理的知识检索，文本检索的研究正在一步步走向深入。文本分类作为文本检 索的重要手段，在文本检索中起着重要的作用。本文的研究重点是文本分类算法特 别是支持向量机的研究，提出了改进支持向量机性能的一些方法，同时在实现口语 检索的语音识别技术方面做了一些尝试，提出了一种促进语音识别技术应用的方法。 具体研究内容与创新如下 ( i ) 对统计学习理论的新进展支持向量机( s u p p o r t v e c t o rm a c h i n e s ，s v m ) 进 行了较深入的研究，提出了一种改进的支持向量机一n n - s v m ：它先对训练集进行 修剪，根据每个样本与其最近邻( n e a r e s tn e i g h b o r ) 类标的异同决定其取舍，然后 再用s v m 训练得到分类器。此方法的提出源于这样一种考虑，在要划分的两类的 交界区域，两类的样本点往往是混杂在一起的，如果不进行适当的处理，可能会造 成两种后果。一是造成分类边界过于复杂反而降低分类器的泛化能力，二是造成分 类器的学习过程较复杂。n n s v m 的做法就是首先尽量减轻混杂的程度，将混在另 一类的“异类”除去，等边界变得清晰后再做划分。实验表明，相比s v m ，n n s v m 可以达到更高的分类精度，同时大幅缩短了分类时间。这说明n n - s v m 所确定的边 界更合理更简洁。 ( 2 ) 提出了一种针对大规模样本集的支持向量机的学习策略l s v m ，首先用一 个小规模的样本集训练得到一个初始的分类器，然后用这个分类器对大规模训练集 进行修剪，保留下与初始分类边界距离较近的样本点，去掉其它样本点，修剪后得 到一个规模很小的约减集，再用这个约减集进行训练得到最终的分类器。l s v m 是 基于这样一种考虑：为了避免直接用大规模训练集训练，首先用一个小样本集训练， 小样本集训练出的分类边界可能不是很精确，但也粗略反映了精确边界，然后保留 下大规模样本集中与初始边界距离较近的样本点，这是因为靠近分类边界的点往往 是比较重要的点( 可能是支持向量) ，这样在使用约减集训练时既减小了训练规模， 又保留了重要的样本点。实验表明，采用这种学习策略不仅大幅降低了学习的代价， 而且这样获得的分类器的分类精度完全可以与直接通过大规模样本集训l 练得到的分 类器的分类精度相媲美，甚至更优，同时分类速度也得到大幅提高。 北京交通大学博士学位论文 摘要 ( 3 ) 将n n s v m 和l s v m 用于文本分类。理论和实践都证明了支持向量机是 非常适宜于文本分类的，本文进一步将n n s v m 和l s v m 用于文本分类，实验表 明，相比标准的s v m ，n n s v m 可以达到更高的分类精度，而l s v m 在不降低分 类精度的前提下可以大幅降低训练的代价，同时后两者都可以提高分类的速度。 ( 4 ) 提出了种度量语音识别结果与原始1 2 1 语输入本意之间相似程度的文本发 音相似度的概念，给出了计算该相似度的数量化描述。该相似度的引出基于这样的 发现：语音识别的结果与原始语音输入的文本在发音上总是相似的，利用这种相似 性，当已知语音输入为某个有限集的元素之一时，可以高成功率的找出原始语音输 入。该相似度的提出，为语音识别技术的某些条件下( 特别是当已知语音输入为某 个有限集的元素之一时) 的实际应用提供了一种行之有效的方法。 ( 5 ) 利用以上的支持向量机的改进方法及相似度概念，开发了一个奥运会比赛 项目的口语检索演示系统。该系统利用支持向量机( 结合文中的改进方法) 作为文 本分类器，将搜集的文本按奥运会的比赛项目分类后放到类别知识库中，用户可通 过语音输入奥运会比赛项目来查询与该项目相关的文本。一方面，由于使用了支持 向量机的改进方法，文本分类有较高的精度；另方面，系统可以对语音输入实现 鲁棒性识别，使用通用的识别引擎，用户无需适应性语音训练，无论男女老幼，只 要是较为标准的普通话，都可以达到很高( 接近百分之百) 的成功率。同时开发了 一个个性化智能语音浏览器，用户可通过语音访问自己喜欢的数十个网站，其特点 也是具有高成功率。 关键词口语识别与理解文本检索文本分类支持向量机文本发音相似度( 文 音相似度) n n s v m l s v m 北京交通大学博士学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i d l yd e v e l o p m e n to f i n t e r a c t ，i th a sb e e nl o a d e di m m e n s ei n f o r m a t i o n h o wt og e to n e sf a v o r i t ei n f o r m a t i o n c o n v e n i e n t l ya n de f f e c t i v e l yf r o m s om u c h i n f o r m a t i o nh a sb e c o m eam o s ti m p o r t a n ti s s u e t e x tr e t r i e v a li sa ni m p o r t a n t a p p r o a c h t o p e r f o r mi n f o r m a t i o ni n q u i s i t i o na n dk n o w l e d g ei n q u i s i t i o n ，a n dt e x tc a t e g o r i z a t i o n ( t c ) i sa ni m p o r t a n tm e a n st oa c h i e v et e x tr e t r i e v a l t h i sd i s s e r t a t i o nf o c u s e so nt h e a l g o r i t h m o f t c ，e s p e c i a l l ys u p p o r t v e c t o rm a c h i n e s ( s v m ) w e p r o v i d es e v e r a li m p r o v e d a p p r o a c h e so f s v m i nt h em e a n t i m ed e f i n eak i n do f s i m i l a r i t ym e a s u r e t om a k e s p e e c h r e c o g n i t i o n ( s r ) t e c h n i q u ea p p l i c a b l e t h em a i nw o r k sa n di n n o v a t i o n sa r ea sf o l l o w s r 1 、i no r d e rt oi m p r o v et h eg e n e r a l i z a t i o na b i l i t yo fs v m w ep r e s e n ta ni m p r o v e d s v m ：n n s v m i tf i r s tp r u n e st h et r a i n i n gs e t r e s e r v e so rd e l e t e sas a m p l ea c c o r d i n gt o w h e t h e ri t sn e a r e s tn e i g h b o rh a ss a m ec l a s s1 a b e lw i t l li t s e l fo rn o t t h e nt r a i n st h en e ws e t w i t hs v mt oo b t a i nac l a s s i f i e r t h em e t h o d sb a s e do ns u c hac o n s i d e r a t i o n ：i nt h ec r o s s a r e ao ft w oc a t e g o r i e s t h es a m p l e sa r eu s u a l l ym i x e dt o g e t h e r i fw ed o n td e c r e a s e 血e m i x e dd e g r e e t h e r ew i l ll c a dt ot w or e s u l t s t h ef i r s ti st h eb o u n d so ft h ec l a s s i f i c a t i o ni s t o oc o m p l e xt or e d u c et h eg e n e r a l i z a t i o no ft h ec l a s s i f i e r t h es e c o n di st h ep r o c e d u r eo f m a c h i n el e a r n i n gi sm a d et o ot i m ec o n s u m i n g n n s v mf i r s tr e d u c e st h em i x e dd e g r e e t h e nt r a i r l st h er e d u c e ds a m p l es e t e x p e r i m e n t r e s u l t ss h o wt h a tn n - s v mi sb e t t e rt h a n s v mi na c c u r a c ya n ds p e e do fc l a s s i f i c a t i o n ( 2 ) p r e s e n t e d a l e a r n i n gs t r a t e g yo f s v mf o rl a r g et r a i n i n gs e t ：l s v m w ef i r s tt r a i na n i n i t i a lc l a s s i f i e rw i t has m a l lt r a i n i n gs e t ，t h e np r u n e st h el a r g et r a i n i n gs e tw i t ht h ei n i t i a l c l a s s i f i e rt oo b t a i nas m a l lr e d u c t i o ns e t t r a i n i n gw i t l lt i l er e d u c t i o ns e tw eo b t a i nf i n a l c l a s s i f i e r e x p e r i m e n t ss h o w t h a tu s i n gt h i sl e a r n i n gs t r a t e g y , w en o to n l yr e d u c et h ec o s t g r e a t l yb u ta l s og e tac l a s s i f i e rt h a t h a st h es a m ea c c u r a c ya s ( e v e nb e r e rt h a n ) t h e c l a s s i f i e ro b t a i n e db yt r a i n i n gl a r g es e td i r e c t l y ，i na d d i t i o n ，s p e e do fc l a s s i f i c a t i o ni s g r e a t l yi m p r o v e d ( 3 ) a p p l y n n s v ma n dl s v mt ot c e x p e r i m e n t ss h o wt h a tc o m p a r e d 、v i ms t a n d a r d s v m ，n n s v mc a nr e a c hh i g h e ra c c u r a c y , l s v mc a r lr e d u c et h et r a i n i n gc o s t ，a n db o t h o f t h e mc a l li m p r o v et h es p e e do f c l a s s i f i c a t i o n ， l u - 型生星! i 坠兰竖主兰堡丝：三 垒坐! 竺! ( 4 ) d e f i n eak i n do fs i m i l a r i t ym e a s u r e ( t e x t p r o n u n c i a t i o ns i m i l a r i t y , t p s i m i l a r i t y ) t o m e a s u r et h e s i m i l a r i t yb e t w e e nt h eo r i g i n a li n p u ta n dt h es r sr e s u l t ，t h ec o n c e p ti sb a s e d o ns u c ha l lo b s e r v a t i o n ：t h ep r o n u n c i a t i o n so f t h eo r i g i n a li n p u ta n dt h es r sr e s u l ta r e s i m i l a r t h i sc o n c e p tm a k e st h es r t e c h n i q u ea p p l i c a b l ee s p e c i a l l yw h e nw ek n o wt h a t t h ei n p u ti sa l le l e m e n to f ak n o w n s e t ( 5 ) u t i l i z i n g t h ea b o v e i m p r o v e ds v ma n dc o n c e p to fs i m i l a r i t y d e v e l o p e d a l l i n t e m e t - b a s e dt e x tr e t r i e v a ls y s t e mb ys p o k e nl a n g u a g e t h es y s t e mu s en n s v m a si t s t e x tc l a s s i f i e r , r i s e rc a n i n q u i r ed o c u m e n t sa b o u to l y m p i cg a m e sb ys p o k e nl a n g u a g e o n o n eh a n d ，i th a sh i g hc l a s s i f i c a t i o nr a t e ；o nt h eo t h e rh a n d ，i th a s v e r yh i g hs ra c c u r a c y w ea l s od e s i g n e da ni n d i v i d u a li n t e l l i g e n ts p e e c hb r o w s e r o n ec a nb r o w s e h i s ( h e r ) t e n s o f f a v o r i t ew e b s i t e sb ys p o k e n l a n g u a g e k e y w o r d ss p o k e nl a n g u a g er e c o g n i t i o n a n d u n d e r s t a n d i n g ，t e x tr e t r i e v a l ，t e x t c m e g o n z a t i o n ，s u p p o r t v e c t o rm a c h i n e s ，t e x t - p r o n u n c i m i o ns i m i l a r i t y ( t p s i m i l a r i t y ) ， n n s v ml s v m 北京交通大学博卜学位论文第一章绪言 第一章绪言 文本检索在网络迅猛发展的今天显得尤为重要，从基于关键字的全文检索到基 于自然语言处理的知识检索，文本检索的研究正在一步步走向深入。文本分类作为 文本检索的重要手段，在文本检索中起着重要的作用。本文的研究重点是文本分类 算法特别是支持向量机的研究，提出了改进支持向量机性能的一些方法，同时在实 现口语检索的语音识别技术方面做了一些尝试，提出了一种促进语音识别技术应用 的方法。本章主要介绍文本检索的研究概况、文本分类与支持向量机、口语检索的 有关技术、试图解决的问题，以及本文的研究重点和论文的组织安排。 i n t e r n e t 的迅猛发展，将我们抛进了信息爆炸的惊涛骇浪中。远在1 9 9 7 年，w o r l d w i d ew e b ( w w w ) 就已经拥有了几千万用户和约4 0 0 万站点、3 亿页面，而且这 个数字仍以每4 至6 个月翻一倍的速度增加 2 8 】。美国一家名为“赛维伦斯”的因 特网搜寻公司在2 0 0 0 年发表研究报告说( 新华网洛杉矶7 月1 7 曰专电) ：据不完 全统计，因特网上向公众开放的网页已经达到2 1 亿页，正以每天7 3 0 万页的速度继 续增加，到2 0 0 0 年1 0 月可望达到3 0 亿页，2 0 0 1 年2 月达到4 0 亿页( 此次只统计 了使用超级文本传输协定的h t t pu r l s ，并不包括f t p 网页和保安网站等其它类 型的网页) 。按这样一个速度估计w w w 上的网页数量已达百亿之巨( 如今的搜索 引擎g o o g l e 已经索引了近3 1 亿张网页) 。毋庸嚣疑，我们已经置身在信息的汪洋 大海之中。 随着网络上信息资源的迅速膨胀，w w w 的开放性、异构性和动态性导致了网 络信息资源定位问题的出现，这主要表现在如下几方面： ( t ) w w w 的异构性，决定了其上的信息资源是多种多样的，没有统一的或者 结构化的组织形式和存储结构，也没有统一的访问界面，使得用户无法像检索关系 型数据库那样进行信息资源的有效检索 2 8 】。 ( 2 ) w w w 的开放形式使得难以对其进行有效地管理与组织，也就难以生成和 维护一个统一、全面的w w w 信息资源描述表。 北京交通大学博上学位论文 第一章绪言 ( 3 ) w w w 的开放性允许网络用户可以任意地在w ，上发表自己的信息， 这就导致了w w w 上的信息质量的复杂性，使得w w w 既包含大量的有用信息， 也包含了大量无用的甚至有害的垃圾信息 6 8 。 ( 4 ) w w w 上的信息资源每- - n 都在增加和更新，在一定的时间内，这种变化 对绝大多数用户来说都是隐匿的，谁都无法精确回答诸如“w w w 上有多少服务器 和信息资源? ”、“w w w 上有哪些资源? ”、“w w w 上的资源是如何分布的? ”等 问题 4 】。 上述问题导致了用户无法精确的对w w w 上的信息资源进行定位，w w w 用户 只能使用浏览器逐个页面浏览，以“漫游”的方式寻找自己需求的信息。随着w w w 的急速膨胀，以这种方式进行信息获取的有效性变得越来越低下，并且成为了阻碍 w w w 继续高速发展的瓶颈之一。一方面，w w w 上的信息资源在不断增多，内容 越来越丰富：但另一方面，w w w 用户面对w w w 这个纷繁复杂、信息质量良莠不 齐的庞大信息海洋，因缺乏有效的信息资源定位手段而显得力不从心，无法迅速有 效地从网络上获取所需信息，这就是所谓的“r i c h d a t a p o o r i n f o r m a t i o n ”问题。因 此，随着w w w 资源的迅速膨胀，如何迅速有效地从w w w 上获取用户所需信息， 就成为了w e b 技术领域中的一项重要研究课题。 文本检索技术为人们查找信息、获取知识提供了便利，因此该项技术的研究得 到了广泛的重视并一步步走向深入。目前w e b 上用于检索信息的主要工具是搜索引 擎，其核心技术已相当成熟，并已被广泛应用。但搜索引擎也有明显的弊端，例如 搜索结果往往非常庞大，内容重复，等等。于是更高层次的检索，如文本挖掘成为 当今的研究热点。 1 2 文本检索的研究概况 国际上文本信息检索的发展始于二十世纪五十年代1 3 1 ，中文文本信息检索最早 见于7 4 8 工程中的汉字情报检索1 1 0 3 1 。8 0 年代中期后，由于计算机处理能力的大 大提高和应用的普及化，中文文本信息检索的研究开始进入黄金期，各种汉字文本 索引方法、检索算法以及实用化系统开始出现，各种全文检索商用系统的出现就是 这个阶段的成果。经过1 0 多年的发展，中文文本( 基于关键字的) 全文检索技术已 经完全成熟。 在检索系统性能的评价方面，美国技术和标准研究所主办了t r e c ( t e x t r e t r i e v a lc o n f e r e n c e ) 文本检索会议，旨在建立一套评价文本检索技术和系统的标 北京交通火学博上学位论文 第一章绪言 准。它的最大特点是通过提供大规模训练语料和统一评测方法来支持i r 技术的研 发。研究团队必须首先通过大会的统一评测，而后只有那些名列前茅的项目，才能 获准到会上来做报告。1 9 9 2 年起t r e c 每年举办一届大会，并得到美国国防部 ( d a r p a ) 和国家标准技术局( n i s t ) 的资助。会议对包括中文、日文在内的多 文种文档库开展了i r 评测。t r e c 为文本检索的发展起到了巨大的推动作用。 文本检索从狭义上来讲，就是从大量的文本中找到用户需要的文本。实际上， 随着研究的不断深入，文本检索的研究内容已远远超出了其字面上的含义。它涉及 的范畴也日益广泛，例如信息检索、文本挖掘、文本分类( 聚类) 、文本摘要、搜索 引擎技术都与它有着密不可分的关系。从历史发展的角度来看，文本检索经历了一 个从全文检索到知识检索的过程。全文检索是基于关键词的检索，其思想简单，尽 管目前已发展得相当成熟，并己得到广泛应用，例如搜索引擎，但它仍存在很多不 足。知识检索是基于自然语言处理的检索，涉及了很多复杂的理论，如自然语言知 识、统计学理论等，目前还处于初级阶段，其代表是文本挖掘。 从原理上，检索可以采取两种方案：其一是将文档归入一个有序的结构，再按 结构规则提取文档( 检索) ，这种方法也被称为“文本挖掘( t e x tm i n i n g ) ”；另 一种方案是不建立结构，在检索时，用户自由地输入检索词或短语，由系统进行匹 配，并将匹配到的文档按检索词出现频率的统计规则提供给用户，这就是全文检索。 结构化方案本身又可分为两种：其一是由机器根据文档特征，按一定算法自动 建立有序的结构，并将文档归入该结构；其二是人工建立结构，再人工将文档归入 结构。第一种方法的代表产品是i b m 的t e x tm i n e r 和a u t o n o m y 公司的c o n c e p t a g e n t 。在第二种方法中，最常采用的结构是树状分类表，该分类表由本领域的专家 编制，再由“知识工程师”按文档内容将它归入某一个最终子类，检索时可按树状 结构一层一层地找到文档。这种方法的问题是分类规则有很强的主观性，与编制者 对该领域的理解有很大关系。也就是说，客体并不能被表达成唯一的分类表，这就 给文档的归类和检索造成了困难：另一方面，分类表灵活性差也是存在的问题之一。 除分类表外，还有另一种方法，这就是结构化的概念集合主题词表。它将 本领域的主要概念( 主题词) 收集在一起，给出概念间的相互关系：并列、同意、 上下位等；然后再将文档按其内容所涉及的主题，从主题词表中选出若干个概念， 作为该文档的标识，并存入数据库。以后，只要从主题词表中选出合适的主题词， 就可以提取文档。主题法适用于计算机检索，灵活性较分类法好，但主题词表的编 制很困难，给文档赋予主题词( 标引) 也较分类法困难，这些都是“主题法”的不 足。 北京交通大学博士学位论文 第一章绪言 全文检索的好处是技术上容易实现，但它的查准率和查全率都不算好。常常可 能遇到这样的情景：搜索引擎自动检索出的绝大多数文献都不是您想要的。出现这 种情况的原因有两点：一是检索者用的检索词其实并不是该专业的通用术语；另一 个原因是文档的主题与检索词出现的频率相关度不高。尽管如此，全文检索在目前 仍然是知识管理系统的标准文档检索方案，因为除此之外，再没有性价比更好的实 用技术了。 1 2 1 w e b 全文信息检索技术 i w e b 全文信息检索技术的基本过程 w e b 全文信息检索是根据i n t e m e t 信息的特点而发展起来的一种检索方式。它 主要指研究对整个文档信息的表示，存储、组织和访问，即根据用户的查询要求， 从信息数据库中检索出相关信息资料。 全文检索的中心环节是文件内容表达、信息查询的获得以及相关信息的匹配。 一个好的全文信息检索系统不仅要求将输出信息进行相关性排列，还应该能够根据 用户的意图、兴趣和特点自适应和智能化地调整匹配机制，获得用户满意的检索输 出。 全文检索包括w e b 信息预处理和检索两大部分。信息预处理的主要功能是过滤 文件系统信息，为文件系统的表达提供一种满意的索引输出。其基本目的是为了获 取最优的索引记录，使用户能很容易地检索到所需信息。信息预处理具体包括格式 过滤、语词切分、词法分析、词性标注和短语识别、自动标引、自动分类等步骤， 这是全文检索的准备阶段。检索包括文件信息表达和查询信息表达以及相关信息预 测过程。 2 搜索引擎 w e b 全文检索的一个代表是网络搜索引擎，它在网络信息资源查找中起到了重 要的作用，可以帮助人们从浩如烟海的网络信息中找出自己想要的信息。 传统搜索引擎站点的结构与工作原理一般都很相似，都是由网上r o b o t s 、索日 工具、文档索引库和查询服务等四大模块组成，如图1 1 所示 1 2 6 。 ( 1 ) r o b o t ：r o b o t 用于w w w 的漫游与网页的下载。 北京交通大学博士学位论文第一章绪言 ( 2 ) 索引工具：索引工具是搜寻站点的核心，它协调各r o b o t 的工作，并对下 载的网页进行分类、索引与组织。 ( 3 ) 索引数据库：r o b o t 采集到的网页索引和相关描述信息全部存储在索引数 据库中。不同的检索站点记录的内容是不同的，有些记录了网页的全部内容，有的 只记录网页的地址、标题、关键词、摘要等信息。不同的检索站点数据库的规模也 不同，数据库的规模直接影响了系统查询的查全率。 ( 4 ) 查询服务：查询服务子系统负责接收用户的查询请求和根据用户查询进行 数据库检索，并将结果集按相关度反馈给用户。 按照工作方式，可将现有的检索站点分为两大类：检索工具站点和检索服务站 点 1 2 6 。 ( 1 ) 检索工具站点：拥有自己的r o b o t 、索引数据库，按照自己的目的和遍历 策略与索引算法建立w w w 信息索引库，向用户提供基于自身索引库的查询服务。 根据浏览方式、索引技术、查询语言、查询匹配算法等又可将搜索引擎进一步分类。 按是否隐藏索引结构，搜索引擎可分为可分类浏览型和不可分类浏览型，y a h o o 、 e x c i t e 、l y c o s 等属于分类浏览型，y a h o o 将索引信息分为a r t 、b u s i n e s s 、c o m p u t e r 、 e d u c a t i o n 等1 4 大类；e x c i t e 将索引组织成为w e bg u i d e 、e x c i t i n gs t u f f 等1 4 个频 道( c h a n n e l ) ；l v c o s 则分为1 8 个主题，用户可以按类别浏览索引信息和进行分类 内的查询。g o o g l e 属于不可分类浏览型，用户看不到其内部的索引结构。 图1 ，i 检索站点结构 按索引技术，搜索引擎可分为全文索引型和非全文索引型。a l t a v i s t a 、e x c i t e 、 o p e n t e x t 、w e b c r a w l e r 以全文索引方式索引了网页的标题和内容，属于全文索引类 型：l y c o s 、w w ww o r m 、y a h o o 属于非全文检索型。 北京交通大学博士学位论文 第一章绪言 按查询语言，搜索引擎可分为自然语言型和非自然语言型，w e b c r a w l e r 、 i n f o s e e k 属于自然语言型，能够理解像“w h a ti si n t e m e t ”之类的简单语言查询。 按查询匹配算法，搜索引擎则可分为布尔型、向量型、概率型等，搜寻引擎一 般同时使用几种匹配算法。 ( 2 ) 检索服务站点：自己不进行w w w 的遍历和索引，也没有自己的索引库， 它只是向用户提供一个查询界面，将用户提交的查询传送给其它多个搜索引擎来完 成，对各搜索引擎反馈回的结果经过筛选、组织后，再送交给用户。利用检索服务 站点进行查询，查询的范围可涉及多个搜索引擎的索引数据库，可以起到取长补短 的作用。例如i b m 的i n f o m a r k e t 要访问y a h o o 、o p e nt e x t 、m a g e l l a n ；m e t a c r a w l e r 则要访问o p e nt e x t 、l y c o s 、w e b c r a w l e r 、i n f o s e e k 、e x c i t e 、a l t av i s t a 、y a h o o 和 g a l a x y 等8 个站点。 3 g o o g l e 简介 下面我们以国外著名的搜索引擎g o o g l e m t t p ：w w w g o o g l e c o m ) 为例，进一步加 深对搜索引擎的认识。 g o o g l e 的搜索机制是：几个分布的c r a w l e r ( 自动搜索软件) 同时工作在网上 “爬行”，u r l 服务器则负责向这些c r a w l e r 提供u r l 的列表。c r a w l e r 所找到的网 页被送到存储服务器( s t o r es e r v e r ) 中。存储服务器于是就把这些网页压缩后存入一 个知识库( r e p o s i t o r y ) 。每个网页都有一个关联i d d o ci d ，当一个新的u r l 从 一个网页中解析出来时，就被分配一个d o ci d 。索引库( i n d e x e r ) 和排序n ( s o r t e r ) 负 责建立索引，索引库从知识库中读取记录，将文档解压并进行解析。每个文档就转 换成一组词的出现状况( w o r d o c c m - r e n c e s ) ，称为h i t s 。h i t s 记录了词、词在文档中的 位置、字体大小、大小写等。索引库把这些1 1 i t 又分成一组“b a r r e l s ”，产生经过部分 排序后的索引。索引库同时分析网页中所有的链接并将重要信息存在a n c h o r s 文档 中。这个文档包含了足够信息，可以用来判断一个链接被链入或链出的结点信息。 u r l 分解器( u r lr e s o l v e r ) 阅读a n c h o r s 文档，并把相对的u r l 转换成绝对的 u r l s ，并生成d o ci d ，它进一步为a n c h o r 文本编制索引，并与a n c h o r 所指向的 d o ci d 建立关联。同时，它还产生由d o ci d 对( p a i r so f d o ci d ) 所形成的数据库。这 个链接数据库( l i n k s ) 用于计算所有文档的页面等级( p a g e r a n k ) 。 排序器会读取b a r r e l s ，并根据词的j d 号( w o r di d ) 列表来生成倒排挡。一个名 为d u m p l e x i c o n 的程序则把上面的列表和由索引库产生的一个新的词表结合起来产 生另一个新的词表供搜索器( s e a r c h e r ) 使用。这个搜索器就是利用一个w e b 服务器， 并使用由d u m p l e x i c o n 所生成的词表，并利用上述倒排挡以及页面等级来回答用户 的提问。 从g o g l g l e 的搜索原理中可以看到，其关键而具有特色的一步是：利用u r l 分 北京交通大学博士学位论文第一章绪言 解器获得l i n k s 信息，并且运用一定的算法得出页面等级的信息，这采用的技术是 网络结构挖掘技术。由此可见，作为新兴的搜索引擎，g o o g l e 已并不单单停留在原 有全文检索技术的水平上，而且融入了对w w w 的连接进行分析和大规模的数据挖 掘的技术，使其搜索技术远胜一筹。这也是当今信息检索技术的一个发展趋势。 4 搜索引擎存在的问题 搜索引擎技术虽然已被广泛应用，并建立了多个成功的商业性系统，在一定程 度的满足了用户信息查找的要求，但这些系统还存在一些不足： ( 1 ) 为了提高系统的应答速度和减小索引数据库的规模，系统往往只采用较为 简单的索引与检索策略，并且只对部分信息( 如页面的t i t l e 、页面的起始段落) 进 行索引 1 1 8 】，这就导致了查询结果的不准确问题。系统所返回的结果集中经常会有 大量非相关的、过时的或已经不存在的地址，需要用户耗费很多时间去一一验证地 址的有效性： ( 2 ) 现有的搜索引擎一般只能提供基于关键词的查询，用户无法准确描述复杂 的信息资源需求： ( 3 ) 因w w w 信息空间极为庞大，且动态性强，任何一个搜索引擎都无法对 其进行全面、及时的遍历和索引，这就使得每一个系统都有一定的索引盲区，据文 献 8 5 的统计，l y c o s 、w e b c r a w l e r 、i n f o s e e k 、g a l a x y 、o p e n t e x t 、y a h o o 等6 个系 统两两之间相同查询结果的交叉率仅有3 0 左右； ( 4 ) 各个系统没有统一的查询界面和查询语法，不便于用户使用。 虽然有x m l 等能够提高w w w 资源可检索性的w e b 应用规范出台，但是规范 普及应用还需要很长一段时间，并且由于w w w 所固有的分布性、动态性、开放性、 异构性，w w w 上的信息资源准确定位与获取问题还将依然存在，因此w w w 上的 信息检索技术仍然是一项有待于进一步探索的研究领域。 1 2 2 文本挖掘 1 文本挖掘的基本概念、基本方法 文本挖掘可以看成是文本检索的升华，是文本检索的高级形式。文本挖掘可简 单定义为：从大量的非结构化的文本文档集中提取感兴趣的、非平凡( n o n t r i v i a l ) 7 北京交通大学博士学位论文第一章绪言 的模式或知识 9 4 1 。文本挖掘的主要任务是分析文档集的内容，发现文档集中概念、 文档之间的相互关系和相互作用，为用户提供相关知识和信息。文本挖掘中对信息 表示更加准确，通常使用词和短语表示文本的概念内容。文本挖掘不仅能够区分不 同的概念，还能够分析不同概念结点之间的相互关联关系。文本挖掘处理的基础是 文本的概念集合，概念通常由重要语词和短语表示。文本中短语获取的基础是词法、 句法及语义分析，因此自然语言处理成为文本挖掘处理的基础。 w e b 文本挖掘实际就是针对w e b 上的大量的文档，结合自然语言理解技术，应 用数据挖掘方法，对文档进行总结( 摘要提取) 、分类、聚类、关联分析，发现有用 的知识以及利用w e b 文档进行趋势预测等。 文本总结是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要或解 释。文本总结有助于用户迅速的了解文本的主要内容，以便在大量的文本中快速找 到自己关心的文本。目前的搜索引擎出于效率的考虑通常简单地把文本的前几行作 为文章的摘要。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个类 别。用户可以通过限制搜索范围来使文本的查找更容易。比如我们想获取如何做“鱼 香肉丝”的知识，就可以直接到“烹饪”类文章中去找，不必在所有的文章中翻找。 利用文本分类技术可以对大量文档进行快速有效的自动分类。目前，常用的文本分 类算法有t f i d f 和n a v eb a y e s 等方法 3 8 】。 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别，它的目标 是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能的大，而不同 簇间的相似度尽可能的小。用户可以通过只考虑相关的簇而大大减少浏览量。目前， 文本聚类算法主要有两类：以g h a c 等算法为代表的层次凝聚法和以k - m e a n s 等 算法为代表的平面划分法。 关联分析是指从文档集合中找出不同词语之间的关系。b r i n 提出了一种从大量 文档中发现一对词语出现模式的算法，并用来在w e b 上寻找作者和书名的出现模 式，从而发现了数千本在a n l a z o n 网站上找不到的新书籍 6 。w a n g 等人以w e b 的 电影介绍作为测试文档，通过使用o e m 模型从这些半结构化的页面中抽取词语项， 进而得到一些关于电影名称、导演、演员、编剧的出现模式 1 0 4 。 分布分析与趋势预测是指通过对w e b 文档的分析，得到特定数据在某个历史时 刻的情况或将来的取值趋势。f e l d m a n 等人使用多种分布模型对路透社的两万多篇 新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相对分布，揭示了 北京交通大学博士学位论文 第一章绪言 一些有趣的趋势 2 0 。w u t h r i c h 等人通过分析w e b 上出版的权威性经济文章，对每 天的股票市场指数进行预测，取得了良好的效果 1 1 4 1 。 2 文本挖掘的处理过程 文本挖掘可以分为两个大的阶段：文本精炼( t e x tr e f i n i n g ) 阶段和知识提取 ( k n o w l e 起ed i s t i l l a t i o n ) 阶段 9 4 】。文本的精炼包括文本的特征表示、特征提取等， 知识提取包括文本分类、聚类、可视化、模型预测、关联发现等。文本挖掘处理为 我们更好的从大批量的文本数据中获取有用的信息和知识提供了强有力的帮助。在 1 3 中将详细介绍文本分类的处理过程。 3 文本挖掘的国内外研究概况 国际上，文本挖掘( 信息提取) 是一个非常活跃的研究领域。近年来随着i n t e r n e t 的大规模普及和企业信息化程度的提高，有越来越多的信息积累，而需要信息的人 还没有特别方便的工具去从来自异构数据源的大规模的文本信息资源中提取符合需 要的简洁、精炼、可理解的知识，文本挖掘和知识检索是解决这个问题的方向。在 美国，以文本挖掘为主题的m u c 会议连续开了6 届，对于英语语料的处理有比较 大的进展并已经形成一套评测的规范，一些情报部门已经在利用文本挖掘系统来搜 集特定方面的情报，一些公司已在吸收文本挖掘的技术成果，以此为基础来构造提 供知识检索服务的系统。但是，由于汉语自然语言理解的困难和以往这方面科技投 入的不足，面向中文语料的文本挖掘目前还没有象样的系统。国内在中文文本挖掘 与知识检索方面有一定研究基础的有国家智能中心、复旦大学、微电子发展中心等。 国外有代表性的产品是i b m 的文本智能挖掘机及a u t o n o m y 公司的c o n c e p t a g e n t s 。 i b m 的文本智能挖掘机有三部分组成：高级搜索引擎( a d v a n c e ds e a r c h e n g i n e _ 卜t e x t m i n e r 、w e b 访问工具( w e ba c c e s st o o l s 卜包括w e b 搜索引擎 n e t q u e s t i o n 和w e bc r a w l e r 、文本分析工具( t e x ta n a l y s i st o o l s ) 。i b m 的t e x t m i n e r 的主要功能是特征抽取、文档聚集、文档分类和检索，它支持1 6 种语言的多种格式 文本的数据检索，采用深层次的文本分析与索引方法，支持全文搜索及索引搜索， 搜索的条件可以是自然语言和布尔逻辑条件：它是c l i e n t s e r v e r 结构的工具，支持 大量的并发用户做检索任务：它鹾机更新索引，同时又能完成其它的搜索任务。 a u t o n o m y 公司最核心的产品是c o n c e p t a g e n t s ，在经过训练以后，它能自动地从文 本中抽取概念。另外还有t e l t e c h 公司提供专家服务、专业文献检索服务、产品与 厂商检索服务。t e l t e c h 成功的关键是建立了高性能的知识结构，它采用主题法，其 主题词表分为不同专业，共有3 万多个，由数位知识工程师维护，每周更新5 0 0 1 2 0 0 个词。 北京交通大学博士学位论文 第一章绪言 i 3 文本分类 文本分类与聚类是文本挖掘