（计算机软件与理论专业论文）文本挖掘及其在文本检索中的应用.pdf

摘性 摘要 ，。 f 、当前，凼特川发展十分迅猛，凶特网已经成j , j 人们fi 常7 l 活中的。个蔓要 的f 占息源。但是由于网络信息本身所具有的分散性、动态性、多样性使得网络 信息的获取十分困难。如何在网络上查找用户所需要的、所关心的信息是信息 科学工作者所面临的一个挑战。为了解决网络上文本检索的问题，j 本文进行了 以下方面的研究： 作为整个文本检索系统的基础，本文首先讨论了为文本检索系统建立索引。 本文讨论了在关系数据库下倒排索引的建立、编码、压缩、存储、获取以及并 行化等问题。 分类是有效组织网上信息的一个有效的途径。本文在向量空问模型的基础 上讨论了文本的自动分类的方法。并且讨论了基于群体智能的文本自动聚类的 算法。 为了能够帮助用户更加准确的表达自己的查询意图，我们必须解决词汇不 匹配的问题。本文讨论了利用共现分析和h o p f i e l d 网络的方法自动发掘概念之 间的关联，生成概念空间，完成查询扩展的方法。 最后，本文讨论了如何利用上述技术实现一个有效的查询接口。可以看到， 利用这些技术我们可以帮助用户实现有效的查询。 关键词：文本检索，数据挖掘，文本分类，糕概念空f 日j 坐竺l 一 a b s t r a c t i n t e r n e ti s g r o w i n ge x p l o s i v e l y a n di th a se v o l v e di n t o a m a j o r s o u r c eo l i n f o r m a t i o ni np e o p l e so r d i n a r yl i v e s b u ti n f o r m a t i o no nt h ei n t e r n e ti sd i s t r i b u t e d ， d y n a m i c a n dd i v e r s ew h i c hm a k ei td i f f i c u l tt or e t r i e v ei n f o r m a t i o no nt h ei n t e r n e t h o wt of i n dt h ei n f o r m a t i o nu s e r sn e e d e di sac h a l l e n g et oc o m p u t e rs c i e n t i s t s t o a l l e v i a t et h i sp r o b l e m ，m yt h e s i sh a sf o c u s e dr e s e a r c h e si nt h ef o l l o w i n g a r e a s ： f i r s t l v w ed i s c u s s e dh o wt ob u i l dt h ei n d i c e so ft e x tr e t r i e v a ls y s t e m s w e f o c u s e do u rd i s c u s i o no nt h eb u i l d i n g ，e n c o d i n g ，c o m p r e s s i n g ，s t o r i n g ，r e t r i e v i n g a n dp a r a l l e l i z a t i o no fi n v e r t e di n d e x c l a s s f i c a t i o ni sa ne f f e c t i v em e a n so fo r g a n i z i n gt h ei n f o r m a t i o no nt h ei n t e r n e t b a s e do nt h ev e c t o rs p a c em o d e l ，w ed i s c u s s e dt h ea u t o m a t i cc l a s s i f i c a t i o no f d o c u m e n t s a n dw eu s es w a r n li n t e l l i g e n c ea l g o r i t h mt oa u t o m a t i c a l l yc l a s s f y i n g d o c u m e n t s t oh e l pt h eu s e r st oe x p r e s st h e i rq u e r ym o r ep r e c i s e l y , w em u s to v e r c o m et h e v o c a b u l a r yp r o b l e ma n d o f f e rv o c a b u l a r y b a s e ds e a r c ha i d i nt h i st h e s i s ，w ed i s c u s s h o wt ou s ec o o c c u r r e n c ea n a l y s i so fw o r d sa n dh o p f i e l dn e u r a ln e t w o r kt of i n dt h e r e l a t i o n s h i p b e t w e e n c o n c e p t sa u t o m a t i c a l l y , g e n e r a t i n gc o n c e p ts p a c e u s i n g c o n c e p ts p a c e ，s y s t e mc a ne x p a n du s e r s q u e r i e s f i n a l l y , w ed i s c u s sh o w t oi m p l e m e n ta ne f f e c t i v eq u e r yi n t e r f a c eb y i n t e g r a t i n g t h et e c h n i q u e sm e n t i o n e da b o v e k e yw o r d s ：t e x tr e t r i e v a l ，t e x tm i n i n g ，t e x tc l a s s f i c a t i o n ，c l u s t e r i n g ，c o n c e p ts p a c e 长人声明所呈交的沦文是我个人在导| j | f j 指导l 、进行的研究】作及呶他 的研究成果。就我所知，除了义。 特别加以标注和致谢的地乃外，沦艾叶， 1 i 包禽其他人已经发表或撰。与过的研究成果。与我刚【作的同志刈小删 究所做的任何贞献均已在沦义中作j ，明确l 均况l ! j 并农小j 7 谢意。 作者签移 关于沦文使用授权的说明 t f 国科学院计算技术研究所何权处础、保留送交论丈的复【= | j 什，允i 7 l 沦丈被食阅和借阅：j ：可以公佰沦义的个部或部分l 为容，n j 。以采川t 影d i j 、 缩印或其它复制于段俅仔i 亥沦迁。， 作者签钇：三f 役导帅铃私：义必笮豇j ：l 叫3 ，工 本文受 国家自然科学基金项日“多策略数据库知识发现研究”( 6 9 8 0 3 0 1 0 ) 国家自然科学基金项目“概念语义空间及其应用”( 6 0 1 7 3 0 1 7 ) 北京市自然科学基金霞点项目“源于信息获取知识的知识挖掘理论与 技术研究” ( 4 0 1 1 0 0 3 ) 中科院计算所青年基金项目“基于智能主体技术的宏观经济模型仿真 中若干问题的研究”( 2 0 0 1 6 2 8 0 1 1 ) 中科院数学院青年创新研究基金 资助 1 1 本文研究背景 第一章绪论 文本检索技术直是信息科学工作者和图书馆的管理员关注的焦点。文本 检索的目的是要对于用户的请求给日j 相关的资料。在计算机得到普及之前，我 们经常依靠人工来完成这个任务。图书馆的管理员需要知道自己所管理的资料 并且知道它们的内容，然后借助人工的索引、摘要或者图书馆目录等工具来找 到相关的信息。然而，随着计算机的普及以及互联网的发展，使得这些方法变 得越来越不可行。这主要是由当前因特网上信息的特性所决定的： 首先，互联网上的信息是没有组织的。在图书馆罩存放的是关于某个特定 领域的特殊文档，而互联网上的信息并非如此。不像在图书馆罩面的信息，在 因特网上的信息是更为混乱、没有组织的，并且所包含的信息的质量经常并彳i 是很高。“因特网是分散的、动态的、多样的：要在网上找到信息是一个挑战。” f p i n k e r t o n ，19 9 4 j 其次，因特网上信息的形式是多种多样的。虽然文本信息占了主要部分， 然而图形、音频、视频信息也占了相当大的部分。 第三，因特网上的信息容量是十分巨大的并且发展十分迅猛。不仅仪是因 为因特网信息的没有组织，因特网的大信息量以及迅猛发展给信息检索带柬了 更大的挑战。根据c y v e i l l a n c e 公司到2 0 0 0 年7 月1 0 同的统计表明当时因特网 共有2 1 亿个网页，平均每天增长7 3 0 万个网页。 项目数量统计闩期 网页数量 2l b i l l i o n 2 0 0 0 年7 月 每同增加网页数目 7 3 m i l l i o n2 0 0 0 年7 月 网站数 8 4 m i l l i o n 2 0 0 1 年1 0 月 平均每个网页大小 1 0 ，0 6 0 t l y t e s2 0 0 0 年7 月 文本信息量 10 2 0 t e r ab v t e2 0 0 0 白i 衷l “1 前川特旧的容量 皇尘丝塑丝! ! 尘墨垒丝墨! 塑生旦l 一 i n t e r n e t 的增长 幽1 ll n l e r n e i 臼勺增k 所以，我们必须找到一些方法能够在海量的信息量罩面找到我们所需要的 有用的信息而不至于被大量的信息所淹没。 1 2 文本检索技术的发展 g e m l ds a l t o n 从7 0 年代就开始从事文本检索的研究。他所提出的向量空间 模型( v e c t o r s p a c e m o d e l ) 已经成为现在的文本检索系统以及网络搜索引擎的 基础。下面我们简要的回顾一下文本检索技术发展的历史： 在7 0 年代，文本检索引入了倒排索引( i n v e r t e di n d e x ) 以及向量空i 日j ( v e c t o r s p a c e ) 模型。另外，创立了基于贝叶斯统计( b a y e s i a ns t a t i s t i c s ) 的靠尔方法 ( b o o l e a nr e t r i e v a lm e t h o d ) 和简单概率获取模型( s i m p l e p r o b a b i l i s t i cr e t r i e v a l m o d e & ) 。虽然已经经过了近3 0 年的历史，这些技术至今仍然构成当今文本检 索技术的基础。 在8 0 年代，与新的人工智能技术的发展同时，产生了一些以模拟专业文献 搜集者和领域专家的专家系统。使用了对用户建模以及自然语言处理( n a t u r a l l a n g u a g ep r o c e s s i n g ，n l p ) 等技术来辅助对于用户和文档的表示。并且产m 了一些研究用的原型系统来产生。 存9 0 年代，当研究者们认识到了创建领域知议库的困难之后，研究者们试 图采用新的机器学习技术用于信息分析。这些技术包括神经网络、遗传算法、 符号学习等。 9 0 年代中期之后，随着搜索引擎的普及以及网络s p i d e r ，索引，超链分析 等技术的发展，文本检索系统已经成为更新的并且更强大的用于网络内容的锼 索1 具。 ：v j n 0 0 0 n 0 j o o 0 0 o o 0 0o_o。io：，v 0 o 0 “0 o 0 0 0 “ l | ，= v 0 o o：=_旧旧 o p 5 0 6 0 5 4 4：2 2 ，1 h，te_ne网页数量 一笙二至堡堡 _-一 1 3 文本检索系统的性能评价 评价义本检索系统性能的一个关键概念是“l h 关性”( r e l e v a n c e ) 。它是h 3 柬判断获取的文档集合对r 用户需求的满足的程度。相关性是个主观冉勺概念， 相关性的度量不仅仅依赖于用户的查询和所搜索的文档的集合，它也与用。的 个人需求、偏好、知以、语言等有关系。【h e r s h ，1 9 9 5 通常将“查准率”和“查全率”这两个指标共同用来衡量检索系统的性能。 查准率表明系统的精确性。查全率反映了系统的覆盖性。这两个量不是独立的， 其中一个指标的提高往往以另一个指标的降低为代价。 查准率( p r e c i s i o n ) ：是信息检索的性能指标，定义为被检索到的相关文档数 除以所有要检索的文档数。 p r e c l s l o n = r e l e v a n t c - 、 r e t r i e ! ! 空丑 r e t r i e v e d 查全率( r e c a l l ) ：是信息检索的另一个性能指标。定义为查找到的相关文档 数除以集合中全部相关文档数的值。即 wcall一relevantnretrievedi ( 1 - 2 ) r e l e v a n t 、 7 图12 奄全率与奄准率 在实际应用中，有些用户更加注重查准率，而另外一些用户更加注重查全 率。 r i j s b e r g e n1 9 7 9 禾- r j 用一个综合了查全率与查准率的指标e 来衡量系统的性 能。 ez1 口f g + ( 1 一口) 土 l pj 、 7 r ( 1 3 ) 其中p 是查准率，r 为查全率，a 是一个0 到l 的参数。a 为0 的时候， 只考虑查全率，a 为l 的时候只考虑查准率。 查准率比较易于度量，剥于所获取的文档集合，只要判断每篇文档足a 和给定查询相关就可以了，所以查准率的计算是比较直接的。而对j 二杏全：冢的 计算就相对困难一蝗，因为这意味着对于给定杏询，必须计算整个文档集合1 ， 十父文档的数h 。! j 文档集合过大时，这是不可行的。 。 ! 垒幽型坠些型型坚生一一 1 。4 文本检索模型 史本稳索当中经常使”j 的模雀主要存：j 个：确i 尔授登、檄j 簪摸毪殷翘鞋l 。 闻模型。 匆尔摸型跫基于特诬项的严辏匹配模型。酋先建立： 个二值变量的集合。 如架文本中出现了对应的特征项，则变量取“d u e ”，甭! i l | j 取“f a l s e ”。套嘲m 特征项和逻辑运算符( “a n d ”、“o r ”、“n o t ”) 组成。文本查询的匹配舰则 遵循布尔运算的法则。在六、七十年代的许多商用检索系统d i a l o g 、s t a i r s 、 m e d l a r s 就蓬基于括尔模型。帝尔检索模型的差要的优点为：是速度抉， 二蹙易于表示嗣义关系( 电脑o r 诱冀枧) 和涸绢( 数据a n d 挖掘a n d 系 统) 。缺点是不能表示特征颇列文本的遵要性，缺乏定鞋分机和灵活性，以及4 ： 能表述模糊匹配。 概率模型主要针对信息检索中相关性判断的不确定性以及查询信息衷示的 模糊性。它主爱是基于概率排序原则：对予给定的箱产查询q ，对所有的文本 d 汁算概率覆r i d 并献大到，j 、送行排序。其中霞表示文本d 与查溜9 的稠 关性。文本d 可以表示为。一汹。如幽) ，为特征个数，磊= l 表示特缝项i 在文本中出现；霸一o 表示特征项i 在文本中不出现( 文本的由尔表示) 。 p ( r i d 固) 擎4 l o g 箫焉 ( 1 4 ) 这攀参数p l ，q ，主要通过稽关反馈避章亍估计。一种麓单稳方法是： r疗一f p t 2 j ，q t 一孑( 1 s ) 其中，”为反馈文本集所含的文本总数，r 为与用o 禽询相关的文本数，”。为特 征i 出现的文本数，n 为特征f 出现且弓用户森询稿关的史奉个数。概率模墅的 歌点燕对文本集的依赖性过强丽虽处理问题过于简t 孽。 囱量空闽模型把文本表示戏向量空划中数点( 向量) ，蠲它 f 】之| 拜兴熊豹余 弦作为相似性度量。在向篷空间模型中，首先要建立文本枣u 用户奄询的向量， 然后进行查询向量和文本向量的榈似性计算。并可以在匹l ! | i 己结果的摹础 ：进行 相关反馈，优化用j _ 、的查洵。关于向髓的表示和柏似一h - 计算r 叮以参阅第，章。 f 旬餐空问模型的优点扫二于将文本和商询简化为特征项及权值集合的向鞋表 示，觚丽匏检索操作变成网景窄闯生| 勺向蓬运斧。向箍的权。麓可以通过简荦的 统计来完成，郯避过定量的分柝对查溺霹l 文奉进舒匹隧。它豹皴点隆j ：特翟：琰 之| 舅j 的无关假设， ：! = ( 很明疆在自然语南+ 巾，列或 i l l ? _ 州办戎嚣十分鬻 j j o , j 联 系，所以对计算结果的”r 辖t 造成一定的影i 忆， 銎! 堑堡 一 一 1 5 文本检索技术的应用 现在已经有许多成熟的商用的文本检索系统。- ，j _ 以将它们分为：种类氆。 筇种是通用的文本检索系统，这种系统维护自已的知谚 库米对用户提供服务； 第一种是基于网络的文本检索系统，也就是搜索引擎：第一二种是知识管理系统， 这些系统收集、处理、组织企业的知识，以便为企业的决策提供支持。实际上 种划分并不是绝对的，经常可以通过对于一种产品的改造束实现别的类型产品 所能提供的服务。 1 5 1 通用文本检索系统 通用文本检索系统利用自己维护的信息库通过网络或者其他的形式向用户 提供服务。现在比较成熟的有如下这些通用文本检索系统。有关它们的具体比 较可以参看附录l 。 l 巳x i s n e x i s l e x i s n e x i s 是个用来获取法律( l e x i s ：) 或者新闻( n e x l s ) 文档的 商用系统。l e x i s n e x i s 支持传统的“严格”布尔查询，即严格匹配的布尔查 询。它还特别支持以御尔算子形式提交的查询，这些算子在l e x i s n e x i s 中 被称作联接子( c o n n e c t o r ) ，包括o r 、a n d 和w n 。最后一个算子是用来表示 接近查询的。并且它还支持通配符( w i l d c a r d ) 查询。最近，l e x i s n e x i s 还 提供了自然语言查询的功能，被称作f r e e s t y l e 搜索。这种查询方式4 i 需 要佰尔联接子。l e x i s n e x i s 提供了一些对于自然语言特有的结果显示选项。 例如，用户可以显示“文本中权重最大的块一一也即最与查询相符的部分”。 “w h y ”这个选项用来表示“解释你的搜索结果”。 d i a l o g d i a l o g 是一个用来搜索下列主题领域数据库的文档的商用系统。这些主 题包括：商业，知识产权法律政府，医药，新闻，人文，科学，社会科学以 及技术等。用户选择一个主题。然后选择该丰题下的+ 个( 或者一组) 数掘库。 对于不同的数据库有不同的搜索选项。例如对于新闻数据库包括：e 题( 关键 字) ，标题，作者，期刊等等 d o wj o n e sn e w s r e t r i e v a l d o wj o n e sn e w sr e t r i e v a l 足个町以搜索多达1 9 0 0 个新闻来源的商t 叶】系 统。例如，报纸，杂志等等。和卜向介绍的系统相类似，它也支持严格自，尔查 询以及一组算子，例如a n d ，o r ，n o t ，s a m e ，n e a r 等。并且可以根捌 n j 、领域、相：文档中的化胃、i ：题、特定新闻源等进步限制搜索。 t o p i c j 匕面：个胁i k 文小检索系统小同，t o p i c 并，f i 是一个利用臼止j l t l 有的文本 集合提供信息服务i m 足个甲独的义本检索j j t 。用户购j ( t o p i c ，然后装找 兰坐丝塑些! ! 生生竺竺垒! 塑坐型一 ( 己的信息，利用t o p i c 提供自己的信息服务。 s m a r t s m a r t 是由c o m e l lu n i v e r s i t y 的g e r a r ds a l t o n 丌发的，是最一的文本检索 系统之一。它具有以卜特点：( 1 ) 自动建立索引；( 2 ) 自动生成聚类层次计算 聚类中心：( 3 ) 进行台询文档相似度计算并闩根据史档与查询的相似程度对文 档排序；( 4 ) 将文档以缺r 词汇的向量空j 、日j 表示：( 5 ) 根据用户反馈自动提高 对奁询的处理。 i n q u e r y 这个系统是u n i v e r s i t yo fm a s s a c h u s e t t s 智能信息检索中心的产品。它是一 个基于贝叶斯网络结构的概率模型，包括两个部分：文本网络与查询网络。给 定一定的集合，文本网络是静态的，节点表示文本，与表示单词的节点相连。 所以给定一个文本，i n q u e r y 能计算一个特定单词的概率。而查询式中的单 词与那些应该与之有联系的节点有一连线。( 比如，某个a n d 节点满足一组单 词的要求，那么它的概率是每个单词的概率的乘积。) 这些连接的单词就是用户 的信息需求。运行检索时，系统将两个网络连在一起，然后计算信息需求满足 每一个给定文本的状态概率。系统就以该概率排序文本。 1 5 2 搜索引擎 现在共有两种类型的搜索引擎( s e a r c he n g i n e ) 。一种是基于s p i d e r 的搜索 引擎，另外一种是人工目录。 基于s p i d e r 的搜索引擎( s p i d e r - b a s e d s e a r c he n g i n e s ) 。这种搜索引擎利用 s p i d e r 技术搜集当前网络上面的网页信息，自动创建索引。所以如果列某个网 页进行了更新，那么这种搜索引擎能够自动发现这些改变，并且进行自动更新。 另外一种搜索引擎是像y a h o o ! 这些人一1 j 目录( h u m a n - p o w e r e dd i r e c t o r y ) 需要人力来维护它们的索引。对于一个网站，必须由网站的管理肯提交关于该 网站的简短说明或者由列表的编辑者写一个关于他们所见查的网站的简短综 述。系统寻找那些与查询相符合的描述作为返回。如果阐页内容发乍更改系统 不能自动发现。 在早期，一个搜索引擎或者是基于s p i d e r 的搜索引擎或者是人厂维护的【j 录。在今天更多的是两种形式混合的搜索引擎( 坳b r i ds e a r c he n g i n e l 。然而， 通常一个搜索引擎可能更加倾向于其中的一种形式，例如y a h o o ! 虽然能够提供 基于s p i d e r 的结果( 由g o o g l e 提供的) ，然而它更加倾向 二1 1 录的力提供结 果。 基于s p i d e r 的搜索引擎通常足山三部分组成的。第部分是s p i d e r 。s p i d e r 访问一个网页，读取它，然后根掘陔网页的联接访问纠站内鄢其他i - j 贝。s p i d c r 能够定期( 例如每两个j j ) 叵新访问这个州站束跟踪刚站的变化。之j _ ，s p i d c r 所获得的内容进入了搜索引擎的第：部分，索引部分。索0 像小人l 诈9 k 十t 包含s p i d e r 所找到的所仃网页的个钎份。如粜址个州页发化变化，那么禚个 笙：旦生生一 , 索r j l f q 容也将发生变化。搜索，j | 擎软件是搜索引擎的绝二部分，刈于给定搜 索，搜索引擎软件能够找剑j 搜索相关的刚灭并把它们按照定顺序提交给 用，“。f 面我们对这些主要的搜索引擎做一个简单的介绍。 1 5 2 1 基于s p i d e r 的搜索引擎 f 面我们给出一些常用的基丁s p i d e r 的搜索引擎的简介。有关它们与其他 些基于s p i d e r 的搜索引擎的比较可以参看附录2 。 ( 1 ) g o o g l eh t t p ：w w w , g o o g l e c o m 作为当前最为优秀的网上搜索引擎，g o o g l e 于1 9 9 9 年9 月2 1f 1 萨式发伽。 它拥有自己的网页数据库。2 0 0 1 年1 2 月g o o g l e 宣称它已经对1 5 亿个网页进 行索引，是目前最大的搜索引擎。它不仅对普通网页进行索引，也对p d f ，p s ， d o c ，x l s ，t x t ，p p t ，r t f ，a s p ，w p d 等类型文件进行索引。并且也包 含了图形数据库。 g o o g l e 使用p a g e r a n k 的方法对网页进行联结分析，对网页的重要性进行排 序。并且对于同一网站的网页进行归并，最多显示每一个网站的两个网页。 g o o g l e 对大小写不敏感。并且可以根据用户需求，限定语言( 共2 7 种语言) 、 日期( 三月内、六月内、十二个月内) 、关键词位置( 标题，f 文等) 等对网页 进行搜索。 ( 2 ) a l t a v i s t a h t t p ：w w w a l t a v i s t a c o m 多年来，a l t a v i s t a 曾经一直是三个最大的搜索引擎之一。它有简单查询 ( s i m p l es e a r c h ) 与高级查询( a d v a n c e d s e a r c h ) 两种方式。a l t a v i s t a 维护自己 的网页数据库。简单查询和高级查询两种方式分别有着自己不同的特色。简单 查询：通过输入一个或几个关键词后提交查询任务即可与传统的检索方法相 似。高级查询：过滤文章、设置时间段、关于字串的说明、大小写说明、通配 符说明等。 ( 3 ) l y c o sn ! ! 卫；! 型旦3 1 ：盥! q 墨q ! 旦 l y c o s 提供了w e b 搜索引擎、主题目录以及一些其它的服务。1 9 9 9 年4 月， 它使用o p e n d i r e c t o r y 提供目录服务。对丁二普通的搜索，l y c o s l 9 9 7 年夏天做出 了重大的改变，抛弃了原来的系统，引入了新的系统。2 0 0 0 年一月，它的高级 搜索丌始转向使用f a s t 数据库。 在查询时，只提供+ 作为a n d 运算，作为n o t 运算，不提供其它的前】尔 算于。并且它能够限制位置、限制语南进行搜索。 ( 4 ) h o t b o t h ! ! p ：w w w h o t b o t c o m h o t b o t 足t e r r a l y c o s 的产晶。它是最火的网络搜索引擎之，它使用 l n k t o m i 的数据库并且也使用d i r e c th i t 和o p e n d i r e c t o r y 的数据库。它也捉供 基本查询和高级查询两种方式。 ( 5 )m s n h t ! t p ：s c a r c h m s n c o m m s n 健川1 o o k s m a r t 作为它的i 求，使川l n k t o m i 作为它的搜索。j 警数 l l ； ! 尘丝堡丝! ! ! ：! 尘羔蟹芏! 塑生坐! 一 库。并且它也利 干j 了d i r e c ti i t 的结果。 ( 6 ) t e o m ah t ! 坦；t c o m a c o m t e o m a 在2 0 0 1 年春天菏次出现，它拥有自已的数据库，并e l 能够提供一些有f j 己特色的服务。例如，在其中存在一个联结指向“r e l a t e dt o p i c & e x p e f l l i n k s ”， 这些联结所指向的网站擎面收集了一些指向其他相关资源的嘲站。它们被称作 元网站m e t a s i t e 。 1 5 2 2 网络目录 下面我们给出y a h o o ! 与o p e nd i r e c t o r y 两种网络目录的简介。有关它们与 其他一些网络目录的比较可以参看附录3 。 ( 1 ) y a h o o ! h t t p ：w w w y a h o o c o m y a h o o ! 是最著名的网络目录。可以直接通过对目录的搜索与浏览进行搜 索。在搜索的时候，如果在y a h o o ! 中没有找到满足条件的项，那么y a h o o ! 将自 动转向g o o g l e 的数据库进行搜索。到2 0 0 0 年1 0 月，y a h o o ! 目录中有一百七十 仃条目录的纪录。这些目录是通过用户的提交或者y a h o o ! 的网站编辑获得的。 ( 2 ) o p e nd i r e c t o r yh t t p ：& n o z o r g o p e nd i r e c t o r y 是归n e t s c a p e 所有的，但是它的运行需要靠数万个自愿的 网站编辑来完成。o p e nd i r e c t o r y 一个比较大的目录数据库，有许多其它搜索引 擎使用了o p e nd i r e c t o r y 例如：a l t a v i s t a ，n e t s c a p e l y c o s ，h o t b o t 。 1 5 3 知识管理系统 知识管理是为了企业的运行与决策的目的来收集、处理以及组织企业知识 的系统与管理方法。知识的获取是当前知识管理系统所要面临的一个核心问题 和新的挑战。一些生产传统的文本检索系统的厂商例如v e r i t y ，e x c a l i b u r 和 d a t a w a r e 等公司就将它们的文本获取的技术加以改造用于知识管理。 现在生产知识管理系统的厂商主要有k c c 、a u t o n o m y 、h u m m i n g b i r d 、o p e n t e x t 、v e r i t y 、e x c a l i b u r 、d o c u r n e n t u m 、s e m i o 、i n x i g h t 、e g a i n 等等。对于它 们的比较可以参看附录4 。 我们从下面三个方面对它们进行比较：文本处理与分析技术、文档收集t j 处理技术、显示以及提交技术等。其中文本分析主要包括自然语。；处理：实体 名称抽取；概念关联，自动同义词典生成；领域相关知讧5 的过滤；自动分类生 成；多种文档格式支持；多种语言支持。文档收集与处理技术差要包括以p 儿 个方面：s p i d e r 技术，用于h t t p 文档的收集；数据仓库技术：内容归类；超 链生成；自动文章摘要。获取、显示以及提交技术主要包括以v ) l 个方面：搜 索引擎、可视化、安个j 认证、无线访问、数据x m i 。标汴、个，p ：化提交等。 塑二里堕丝 一一 1 6 数据挖掘简介 数据挖掘( d 。ma 卉”i 馏) 是从大量的、不完全的、订噪卢的、模糊的、随 机的数据集中识别有效的、新颖的、潜在有用的，以及最终可理解的模式的非 平儿过程。它是一门涉及面很广的交叉学科，包括机器学爿、数理统计、神经 网络、数据库、模式识别、粗糙集、模糊数学等相关技术。 1 6 1 数据挖掘过程 幽1 3 数据挖掘过程示意图 数据挖掘挖掘可粗略地理解为三部曲：数据准备( d a t a p r e p a r a t i o n ) 、数掘 挖掘，以及结果的解释评估( i n t e r p r e t a t i o na n d e v a l u a t i o n ) 。 数据准备又可分为三个子步骤：数据选取( s e l e c t i o n ) 、数掘预处删 ( p r e p r o c e s s i n g ) 和数据变换( t r a n s f o r m a t i o n ) 。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ， 它是根据用户的需要从原始数据库中抽取的。组相关数据。数据预处理一般可 能包括消除噪声、推导计算缺值数据、消除重复记录以及完成数据类型转换。 数据变换的主要目的是消减数据维数或降维，即从初始特征! 中找出真正订j l j 的 特征以减少数据挖掘时要考虑的特征或变量个数。 数据挖掘阶段首先要确定挖掘的任务或目的足什么，如数掘总结、分类、 聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使j m f t 么样的挖掘算法。同样的任务可以用不同的算法来实现选择实现算法订眄个 考虑因素：一是不同的数 l 有不同的特点，i 太i 此需要用与之相父的钟诎术挖捌： 墨垒丝塑些! ! 生! j ! ；尘堡垒主塑! ! ! ! 一一 一赴h j ，二，或实际运彳j 系统f 一赞水，f j 嗍j h ，1u j 能捕型拙：帜描述型的、容易雕斛 的知以( 采用规则表不的挖掘方法黟然要好j 神经i * * j - 8 z 类的方法) t m j 仃的用 户或系统的目的是获取预测准确度尽口j 能高的预测掣知以。 完成了上述准备工作后，就可以实施数据挖掘操作了。数据挖掘算法足 k d d 的核心，也是目前研究人员t 要的努力方向，要获徊好的挖掘效果，必须 对各种挖掘算法的要求或前提假设有充分的理解。 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余或 无关的模式，这时需要将其剔除：包有可能模式不满足用户要求，这时则需要 整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、 设定新的数据挖掘参数值，甚至换一种挖掘算法( 如当发现任务是分类时，有 多种分类方法，不同的方法对不同的数据有不同的效果) 。另外，挖掘结果由于 最终是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结果转 换为用户易懂的另种表示，如把分类决策树转换为“i f t h e n ”规则等。 然而根据估计在知识发现过程中2 2 的精力花费在确定挖掘目标上面，这 需要i t 工作者和企业管理者的通力合作。因为需要很多数据库相关的工作，多 于5 5 的知识发现的工作集中在数据准备、预处理与转换上。而数据挖掘实际 只花费1 2 的精力。剩下1 0 的精力主要花费在结果能分析、解释和评价上面 c h e n2 0 0 1 】。 1 6 2 数据挖掘的分类 数据挖掘作为k d d 的核心部分，它被研究得最多。目自h 存在很多数据挖掘 方法或算法，有必要对这些方法进行分门别类。我们知道，描述或说明一个算 法涉及三个部分：输入、输出和处理过程。数据挖掘算法的输入可以是多种形 式的数据，算法的输出是要发现的知识或模式，算法的处理过程则涉及具体的 搜索方法。从算法的输入、输出和处理过程三个角度分，我们可以确定这样儿 种分类标准：挖掘对象、挖掘任务、挖掘方法。 根据挖掘任务分，有如下几种知识发现任务：分类或预测模型知识发现、 数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发 现、异常和趋势发现等等。 根据挖掘对象分，有如下若干种数据库或数据源：关系数据库、面向对象 数据库、空问数据库、时态数据库、文本数据源、多媒体数据库、异质数掘库、 遗产( 1 e g a c y ) 数据库，以及万维网( w e b ) 。 根据挖掘方法分，可粗分为：统计方法、机器学习方法、神经网络方法和 数据库方法。统计方法中，可细分为：回归分析( 多元叫归、自回归等) 、判别 分折( 贝叶斯判别、费歇尔判别、j f 参数判别等) 、聚类分析( 系统聚类、动态 聚类等) 、探索性分析( 卡元分析法、相关分析法等) 等。机器学习l f l ，可细分 为：归纳学习乃法( 决策树、舰则归纳等) 、璀丁范例学刊、遗传算法等。神纤 m 络方法小，州绑分为：前向神经网络( b p 臂浚：等) 、f i 组织神经川络( f i 圳 一垫里堕堕 一 一 彩：特千【f ：映刺、竞争，、产习等) 等。数折：4 二疗法主要是多维数捌分析或o l a p 方浊 外上奎有面向属性的9i 纳力法。 1 6 3 文本挖掘 文本挖掘( t e x t m i n i n g ) 也称为文档挖掘( d o c u m e n t m i n i n g ) ，文本数捌挖 掘( t e x td a t am i n i n g ) 以及文本( 数据库) 中的知识发现( k n o w l e d g ed i s c o v e r y i nt e x t u a ld a t a b a s e ) 。 一般认为文本挖掘是指在大量文本集合或语料库上，发现其中隐合的、令 人感兴趣的、有用的模式和知识。r o n e nf e l d m a n 在k d d 9 9 的给出文本挖掘下 了定义。他认为文本挖掘是一门新的研究领域，通过采用数扼挖掘、机器学习、 自然语言处理、信息检索和知识管理的技术以解决信息过载的问题。它涉及文 档集合的预处理、中问形式的处理( 分类、聚类、趋势预测、关联规则等) 以 及结果的可视化。 在文本挖掘的框架中，文本挖掘可以分为两个阶段：文本精炼和知识提取。 文本精炼将自由形式的文档转变为中间形式；知识提取从中问形式中推理出模 式和知识。 中间形式可以是半结构化的形式，如概念图或者结构化的关系表。在基于 文档的中间形式中每一个实体表示一个文档：在基于概念的中间形式中每个实 体表示特定领域中一个感兴趣的对象和概念。一般而言+ ，基于概念的中间形式 总是依赖于领域的，而基于文档的中问形式可以与领域无关。基于文档的中| 日j 形式可以通过在特定领域中抽取感兴趣的相关对象转变为基于概念的中间形 式。 对基于文档的中间形式进行挖掘可以获得文档问的模式和关系，因而文档 的分类、聚类以及可视化均属此类。对基于概念的中叫形式进行挖掘可以获取 对象、概念间的模式和关系。因而预测模型和关联属于此类。 兰坐丝堡丝! ! ! 兰垒丝墨! 堡坐竺生一 图14 文本分析与文本挖掘的四个层次 由文本挖掘的定义我们可以看出，文本挖掘与分析的技术可以被分为四个 层次：语义学分析自然语言处理，统计共现分析，聚类分类，可视化人机交 互。： 最底层是语言学分析和自然语言处理。这一层次主要目的是从文本中识别 出关键词、关键概念。在这一层次需要建立词的倒排索引。根据所建立的索引 可以进行布尔查询、接近搜索以及模糊搜索等。这一层次分析的单位是词、词 组、句子，也可以是语义分析。如果分析单位是词，那么分析的主要目的是从 中抽取有意义的词尤其是名词。句子层次的分析包括对那些语法萨确的句子进 行上下文无关语法( c o y l t c x t - f t e eg r a m m a r ) 分析等。语义分析包括对句子的语 义分析和故事理解。语义分析经常是领域相关的并 j 缺少可扩展性。基于句于 的分析结构化过于强而不实用。语义分析经常需要领域的知识库不适合于应用 于多个领域的通用的文本挖掘。所以还是基于词和词组的分析最为合适。本文 中将介绍如何建立倒排索引，并且介绍如何使用这个倒排索引进行布尔查询。 基于统计和共现分析技术，通过关联分析我们可以自动生成同义词典或者 抽取出概念之问的概念关联。可以利用一些相似性函数，例如j a c c a r d 函数或者 c o s i n e 函数来计算一对概念之问的距离。有的系统利用一元语法、三元语法、 n 元语法或者有限状态自动机束进一步发现概念之l 、h j 的关联模式。并目现有的 手工义类词典可以与这“冀机器j “q i 的义类浏典相结合束方便用户的查询。本文 将讨论如何利用共现关系分析发现概念之i n j 关联权重，并儿如何利用这个关联 权重使用h o p f i e l d 网络的技术自动生成概念空间。 堆于统计和神经例络拽术的聚类和分类技术可以把相似的文档、请求进行 p 类。之后町以， ：成棚膨的层次结构，用户n r 以利刚这个层次结构对1 ：史档集 合f j 。定的人致了解。这 ! 使川这就需要借豁许多j ： j i i 抛剑的数拱i 挖拥“内算法。 水史将介绍种l h l f i l 刈彩j ，次的l l 采结构逊行文档的r j 动分类的疗法。”外木 墨：垦塑堕 j-一 文将讨论如何利j j 种箍r 群体智能的方法刈文档进仃聚类。 可视化技术以及人机交，f - 技术可以帮助搦小概念之例的关联以及丈档的层 次。不m 的表示结构( 例绷1 树、网络等结卡 = i ) ，显示维度( 1 维、2 维、3 维) 以及不同的交! i 技术u j 以帮助用户一更好的理解结果。本文将i j 论如何将前i 平叶1 技术产生的结果进行融合提交给n j 户，以帮助用户找到自己所想要的信息。 1 7 本文研究内容及组织结构 为了能够提高文本检索系统的效