（计算机系统结构专业论文）xml文档结构相似度研究及在文档聚类中应用.pdf

山东大学硕士学位论文 摘要 近几年来，随着社会信息化进程的不断深入发展，人类对信息的需求和依赖 程度越来越高，如何从海量的信息资源中快速有效的获取有用的信息，已经成为 研究的热点，这也给信息检索带来了极大的挑战。 相似度的计算是文档检索、挖掘和文本聚类的基础，因此对相似度算法进行 研究具有非常重要的意义，可以说文档相似度的计算直接影响了最后的检索结 果。x m l 语言具有“自描述”、“树形结构”、“结构嵌套”等特点受到了业 界的普遍欢迎和支持，越来越多的应用领域已经将其作为主要的存储格式和传输 媒体。因此如何计算x m l 文档的相似度特别是它的结构相似度是目前研究的主 要任务。 通过对x m l 文档的不断深入研究，发现传统的相似度的计算方法已不能满 足计算元素的嵌套结构的语义要求。用树的编辑距离来计算文档的相似度时，如 果树描述全部结构信息，这样树的结构会非常庞大，并且树编辑距离方法对文档 中元素重复和元素可选问题不能有效处理。另一方面，在因特网上通过搜索引擎 检索信息时，出来的信息成千上万，丽人们通常只关心检索的前2 0 名，如何提高 前2 0 项( 或前n 项) 与用户相关项的个数，即提高检索结果的准确性是研究的另 外一个难题。 为了解决上述问题，本论文，在文档对象树的基础上，提出了一种基于树路 径的x m l 文档描述模型，并给出了相应的相似度算法，将问题有效地简化，从 而降低了解决问题的复杂度。这种算法能快速、准确分辨出具有相同结构的x m l 文档。 首先，本文提出了一种基于树路径模型的相似度算法，来实现对x m l 文档之 间相似度的计算。该算法简化了x m l 文档描述，从而降低了解决问题的复杂度。 此算法在文档类别数较少，且不同类别的文档的结构相差较大时，有很好的聚类 效果。 其次，在此算法的基础上，针对它存在的一些问题如：路径只是包含父子 这种祖先与子孙的关系，忽略了兄弟结点之间关系；没有考虑各路径的权重：并 且在比较两路径的相似度时用的是路径的完全匹配等，本文对此一一进行了改 山东大学硕士学位论文 进，并提出了改进后的相似度的计算方法，改进后的算法计算出来的相似度更准 确，处理了文档中元素重复问题，使得计算结果也更符合人的直观理解。 最后本文进行了实验测试，并且在计算文档相似度的基础上对文档进行了聚 类，实验结果显示与其它算法相比，本文的方法更显著地提高了识别具有相同结 构的x m l 文档的能力，在此基础上，通过对文档进行聚类，使具有相同特征或 相似度值很大的文档归为一类，很好提高检索结果的准确性。 关键词：x 札；树路径；结构相似度；文档聚类 i i 山东大学硕士学位论文 a b s t r a c t i nr e c d l ty e a r s ，a l o n gw i t ht h ea c h i v e m e n to f i n f o r m a t i o n i z ew i t ls o c i e t yd e v e l o p s i nd e p t h ，t h ed e m a n d sa n dt h ed e g r e eo fr e l i a n c eo fh u m a nb e i n gt oi n f o r m a t i o na r e m o r ea n dm o r eh i g h ，h o wt og a i nu s e f u li n f o r m a t i o nr a p i d ya n de f f e c t i v e l yf r o ml i q u o r i n f o r m a n o nr e s o u r c e sw i 也t h eg r e a tc a p a c i t y , a l r e a d yb e c o m e st h ef o c a lp o i mt h a t p e o p l es t u d i e sa n da l s oi sag r e a tc h a l l e n g et ot h ei n f o r m a u o nr e t r i e v a l b e c a u s et h es i m i l 缸t ya m o n gd o c u m e n t si st h eb a s eo fi n f o r m a t i o nr e t r i e v a l ，d a t a m i n i n ga n dd e e p s e a t e di n t e l l i g e n t i z eh a n d l i n g , i ti sv e r yi m p o r t a n tt od ot h er e s e a r c ho n t h ed o c u m e n ts i m i l a r i t y t h ed o c u m e n ts i m i l a r i t yd e t e r m i n e st h ea c c u r a ( ：yo ft h er e s u l t s i ni n f o r m a t i o nr e t r i e a l x m ll a n g u a g eh a sa c c 印t e dm o r ea n dm o r e a p p l i c a t i o n ，b e c a u s e i th a s s e l f - d e s c r i b i n g 、”s h a p es t r u c t u r e “a n d s t r u c t u r en e s t e d e t c i th a se m e 唱e da sa s t a n d a r df o rr e p r e s e n t i n ga n de x c h a n g i n gd a t ao nt h ew b r l dw i d ew 曲x m li sa t y p i c a lh a l f - s m a c t u r a l d a t at h a tb ea b l et oe x p r e s sd a t as u c ha s 、衍mr e l a t i o n sa n d s t r u c t u r e ，b e i n ga p p l i e di nl a r g ea m o u n ti nt h ed a t ae x c h a n g ea n di n t e g r a t i o n s i m i l a r i t y d e g r e et h e r e f o r eh o w t oc a l c d a t et h ex m ld o c u m e n t se s p e c i a l l yi t ss t r u c t u r es i m i l a r i t y d e g r e ei st h em a j o rt a s k 吐l a tw es t u d ya tp r e s e n t a l o n gw i t l lt h ec o n t i n u o u sd e e p e n i n go f t h ex m ld o c u m e n t ，b e c a u s et h eu s eo f “s t r u c t u r en e s t e d ，t oe x p r e s st h es e m a n t i ci n f o r m a t i o no fe l e m e n t si nx m l d o c u m e n t s ，s ot h et r a d i t i o ns i m i l a r i t ym e t h o d sd o n tm e e tt h en e e d s t r a d i t i o n a l l y , t r e e m o d e l ( d o c u m e n to b j e c tt r e e s li su s e dt or e p r e s e n tx m e d o c u m e n t s a n dc a l c u l a t e st h e d o c u m e n ts i m i l a r i t yu s i n gt h et r e ee d i t - d i s t a n c eh o w e r v e , c o m p u t a t i o no fs t r u c t u r a l s i m i l a r i t yb e t w e e nd o c u m e n tb a s e do nt h et r e em o d e li sv e r ye x p e n s i v e ，e s p e c i a l l yw h e n t h es i z eo f d o c u m e n ti sl a r g ea n dc o m p l e x , a n di td o e s n td e e lw i t l lt h er e p e a t e de l e m e n t s e f f e c t i v e l y i nd o c u m e n t s o nt h eo t h e rh a n d , 也ei n f o r m a t i o ni s h u g e o u sw h e n r e t r i e v a l i n gi n f o r m a t i o nt h r o u g hs e a r c he n g i n ei ni n t e r n e t ，b u tp e o p l eu s u a l l yo n l yc a r e a b o u tt hf i r s t2 0 ，h o wt oi n c r e a s et h en u m b e ro ft h ef i r s t2 0 ( o rf i r s tni t e m s ) c o n n e c t w i t l lt h eu s e r s ，n a m e l yt h ee n h a n c er e t r i e v a la c c l l r a c yi sa n o t h e rd i f f i c u l tp r o b l e mi n r e s e a r c h i nt h i st h e s i s ，t os o l v et h e s eq u e s t i o n s ，w ep r o p o s ea na l t e r n a t i v em o d e lt op r e s e n t t h es t r u c t u r a li n f o r m a t i o no fd o c u m e n tb a s e do nt h et r e em o d e l ，c a l l e dt h ep a t h so ft r e e m o d e l ，a n dd e f i n et h ec o r r e s p o n d i n gs i m i l a r i t ym e a s u l e ，t h em o d e lp r e d i g e s t st h e i l i 山东大学硕士学位论文 q u e s t i o na n dr e d u c e st h ec o m p l e x i t yt h em o d e li sp o w e r f u le n o u g ht od i s t i n g u i s ht h e s i m i f a rs t r u c t u r a ld o c u m e n t s a tf i r s t ，w ep r o p o s eas i m i l a r i t ym e a s u r eb a s e do nt h et r e ep a t ht oc a l c u l a t et h e s i m i l a r i t yb e t w e e nx m ld o c u m e n t st h i sm e a s u r es i m p l i f i e st h ed e s c r i p t i o no fx m l d o c u m e n t ，a n da c c o r d i n g l yr e d u c e st h ec o m p l e x i t yi nc o m p u t a t i o n i ti sp o w e r f u l e n o u g ht od i s t i n g u i s ht h es i m i l a rs t r u c t u a ld o c u m e n t sw h e nt h ed i f f e r e n tc l u s t e r i n gh a s v e r yu n l i k es t r u c t u r e ，a n da l s op e r f o r m sw e l lo nd o c u m e n tc l u s t e r i n g s e c o n d l y ，t h et r e em o d e lr e t a i n si n f o r m a n o no na l lp a r e n t - c h i l dr e l a t i o n s h i p s ，b u t i g n o r e ss i b l i n gr e l a t i o n s h i p s ；i g n o r e s t h ew e i g h to ft r e e p a t h ；o n l yu s e st h ec o m p l e t e m a t c h i n gw h e nc o m p u t et h es i m i l a r i t yb e t w e e nt r e ep a t h sa n de t c ，w ea l s op r o p o s ea s t r o n g e rm o d e lt or e s l o v et h eq u e s t i o n s t h ei n p r o v e dm e a s u r ed e a l sw i t ht h er e p e a t e d e m e n t ( i nt h i st h e s i sa r er e p e a t e dt r e ep a t h s ) ，a n dl e a d i n gt os i m i l a r i t ys c o r e st h a ta r e m o r ei n t u i t i v et h a nt h eo n e sg e n e r a t e d b yt r a d i t i o n a ls i m i l a r i t ym e a s u r e s a tl a s t ，t h et h e s i sc o n d u c t e dv a r i o u se x p e r i m e n t st o w a r d st h ea p p r o a c ha n dt h e e x p e r i m e n t a lr e s u l t sa r em o r ea b l et oi d e n t i f yt h ex m ld o c u m e n t st h a th a v et h es a m e s n u c u t r ea n dp u tt h e mi n t ot h es a m ec l u s t e r i n gi nt e x tc l u s t e r i n g ，c o m p a r e dt ot h e t r a d i t i o n a lm e t h o d , t h et e x tc l u s t e r i n gb a s e do nt h et r e ep a t hm o d e lw o k sf a i r l yw e l la n d i m p r o v e st h ep r e c i s i o no f i n f o r m a l a o nr e t r i e v a l k e y w o r d s ：x m l ；t h et r e ep a t h ：s t r u c r a s i m i l a r i t y ：t e x tc l u s t e r i n g 山东大学硕士学位论文 第1 章前言 1 1 背景介绍 我们正处在一个信息爆炸的时代，全世界每年出版大约1 5 6 0 0 0 种期刊，而且 这一数字以每年1 2 0 0 0 种的速度递增。而另一个增长更为惊人的信息渠道为 i n t e m e t ，统计结果表明，i n t e m e t 上约有35 亿个静态h t m l 页面，每天增加将近 一百万。面对如此庞大而且集聚膨胀的信息海洋，如何高速组织和管理这些信息， 并快速、准确、全面的从中搜索到用户所需要的信息是当前信息检索领域所面临 的挑战。社会的进步和科技的发展使得信息技术叠出，新的检索内容和检索手段 不断产生，传统的媒体和检索工具、检索方式也在不断发生变化。海量的网上信 息资源并发增长，既为信息的开发与利用提供了便利条件，也为信息的发布与分 享提供了外部环境。然而信息产生和流动的随机性、信息时空关系和系统状态的 不确定性导致查找和使用上的困难，数字化、网络化信息分散、无序、动态变化 等以及信息的庞杂同特定需求之间的矛盾，也给人们搜集与利用信息的运作增加 了困难和不便。 搜索引擎是在浩瀚的w e b 中搜索各种有用信息最主要的一种检索工具，但往 往忽略了信息的内容，且比较少的对信息资源作预处理，使得搜索引擎仍然存在 不少的局限性，比如信息丢失、返回信息太多、信息无关等，这些问题有待于我 们进一步研究解决。 从信息来源看，主要包括搜索引擎与结构化和半结构化数据库的整合，以及 对异构、跨语言和多媒体数据库等方面的研究；从信息获取看，主要包括检索语 言、智能代理、检索模型和算法、域本体和语义、并行和分布式信息检索及信息 可视化等方面的研究。以往的研究虽然对检索模型有着某些改进，但事实上仍然 没有实质性的突破。这主要是由于以用户需求为中心的问题尚未作深入的研究， 而这正是提高信息检索效率及准确度的关键。 相似度的计算是文档检索、挖掘和深层次智能处理的基础，因此对相似度计 算机进行研究具有非常重要的意义，可以说对文档相似度的计算直接影响了最后 的检索结果。如果文档相似度的计算结构高效准确，那么检索结果就能达到用户 的期望值。反之，如果文档相似度的计算结果不准确，查询过程的查全率和查准 山东大学硕士学位论文 率就会受到很大的影响，最后用户检索不好自己想要的结果。 随着w e b 网上信息的爆炸增长，从半结构化文档( 特别是h t m l 和x m l 文档) 中提取信息变得越来越重要。如何识别出具有相同结构的文档是我们研究的主要 任务，认为在任意给定的站点，如果文档中某个节点下结构很相似，则认为这个 节点下包含的信息也相似。如果我们能很容易识别出具有相同结构的文档，就可 以根据文档结构对文档进行聚类，这样就更好地组织和管理信息，并快速，准确， 全面的从中搜索到用户所需要的信息，而最基本的是需要有一个模型能很好地描 述x m l 文档的结构信息。 x m l 文档可以用一棵有序的带标记的树来表示。树中的每个结点对应文档 中的一个元素，用元素的标签来表示结点名。树中的每条边对应x m l 文件中两 个元素的嵌套关系( 孩子结点对应的元素包含于父结点对应的元素，在父结点下 面) 。x m l 文档中有很多超链接，连接到其他文档。这样的链接会形成一个图 而不是树，它对文档数据的应用很重要，但是在计算文档结构相似度是用处不大， 在这篇论文中我们将不讨论。 作为x m l 文档的近似搜索的基础，首先要能够准确地度量查询与文档、文 档与文档间的相似度。传统的信息检索技术利用向量空间模型来表示一个文档， 并利用代表文档的空间向量间的距离来度量两个文档间的相关程度，但向量空间 模型无法反映儿文档中的元素嵌套结构的语义。一般地，一个x m l 文档可 以模型化为一棵树或一个图，两个x m l 文档间的相似度可以用这两棵树( 图) 间 的距离来度量。在x m l 出现之前，已有许多工作1 研究了两棵树( 图) 间的相似 测度的问题，其中最自然和应用最广的测度是树的编辑距离。t a i f l i 最早提出了利 用编辑距离来度量两棵树( 图) 间的差异。在t a i 的工作的基础上，z h a n g 和 s h a s h a i 2 4 1 等提出了计算两棵树间的各种编辑距离的算法。 1 2 本文的工作 通过研究发现，树的编辑距离方法和传统的相似度计算方法相比，在计算 x m l 文档的相似度时，考虑到了x 亿文档的结构特征，但是当树要描述全部结 构信息时，树的结构将会很复杂庞大，这样很难处理，更重要的是它的时间复杂 度很大，还有，对于文档中存在的元素重复和元素可选问题树模型不能很好处理。 2 山东大学硕士学位论文 例如：如果两个文档仅仅是其中某个子元素的个数不同，我们希望计算出的相似 度很大。基于树模型的一些方法却得不到这样结果。 本文对儿文档进行了研究，在文档对象模型的基础上提出了一种基于路 径的模型，称为树路径模型，来描述x m l 文档的结构，并根据这种模型给出了 相应的相似度的计算方法。这种模型比树模型要简单，并且包含了所有 p a r e n t c h i l d 关系，该模型简化了x m l 文档描述，从而降低了解决问题的复杂度。 此算法在文档类别数较少，且不同类别的文档的结构相差较大时，有很好的聚类 效果。但是它忽略了同父兄弟结点之间的关系，而且在比较两路径的相似度时用 的是路径的完全匹配，在此基础上对它进行改进，称为改进后的树路径模型，改 进后的模型解决了树路径所出现的一些问题，并且考虑到了兄弟结点之间关系， 和树路径相似度计算时的重复匹配问题。 实验结果显示与其它算法相比，本文的方法更显著地提高了识别具有相同结 构的x m l 文档的能力，并且对文档有很好的聚类效果。 1 3 本文的组织 全文共分为六章，安排如下： 第1 章介绍了本课题的背景，阐述了本课题的研究目的以及意义，最后介绍 了本文各章节的组织结构。 第2 章介绍了文本聚类基本知识以及在信息检索中的作用， 第3 章介绍了) 国噩结构化文档及其对象模型树，它们是以下讨论的基础。 第4 章对几种常用的计算相似度的方法进行了概括和分析。 第5 章主要介绍利用树路径模型对x m l 文档进行相似度计算的研究，并通 过实验讨论它在文本聚类中的应用。 第6 章对本文在课题中所做的工作进行一个全面的总结，并指明了下一步需 要进行的工作。 山东大学硕七学位论文 第2 章文档聚类基本知识及在信息检索中应用 2 1 引言 信息的查找萌芽于图书馆的参考工作。“信息检索”一词出现于2 0 世纪5 0 年 代。信息检索是指信息用户为处理解决各种问题而查找、识别、获取相关的事实、 数据、文献的活动及过程。信息检索1 6 】研究则是伴随着科学技术的发展和信息数 量的剧增而兴起来的研究领域。英国科学家詹姆斯马丁认为：人类的科学知识 在1 9 世纪是每5 0 年增加一倍，2 0 世纪中叶是每l o 年增加一倍，在2 0 世纪7 0 年代就 已经缩短到每5 年增加一倍；同时，信息分散，交叉应用频繁，人类信息的生产 能力超过了人类对信息的处理、组织和吸收能力，从而产生了信息爆炸的危机。 人们越来越关注如何从浩如烟海的信息源中迅速而准确的查找到学习和研究所 需要的材料，因而，信息检索的战略地位也就显得日益重要。 信息检索按对象分为文献检索、数据检索和事实检索；按设备分为手工检索、 机械检索和计算机检索。由一定的设备和信息集合构成的服务设施称为信息检索 系统，如穿孔卡片系统、联机检索系统、光盘检索系统、多媒体检索系统等。信 息检索最初应用于图书馆和科技信息机构，后来逐渐扩大到其他领域，并与各种 管理信息系统结合在一起。与信息检索有关的理论、技术和服务构成了一个相对 独立的知识领域，是信息学的一个重要分支，并与计算机应用技术相互交叉。 2 2 信息检索基本原理 2 2 1 信息检索过程 按照一定方式组织存贮信息，并根据用户需求查找出有关信息的过程，又称 信息存贮与检索、情报检索。信息检索包括3 个主要环节：( 1 ) 信息内容分析与 编码，产生信息记录及检索标识。( 2 ) 组织存贮，将全部记录按文件、数据库 等形式组成有序的信息集合。 ( 3 ) 用户提问处理和检索输出。关键部分是信息 提问与信息集合的匹配和选择，即对给定提问与集合中的记录进行相似性比较， 根据一定的匹配标准选出有关信息。信息捡索过程如图2 1 所示。 山东大学硕士学位论文 2 2 2 信息检索技术 图2 - 1 信息检索过程 1 布尔检索( b o o l e a ns e a r c h ) 利用逻辑算符进行检索词或代码的逻辑组配，是现代信息检索中最常用的一 种方法。其中， 1 ) 逻辑与：如a b ，表明篇文献中a 或b 必须同时存在； 2 1 逻辑或：如a + b ，表明一篇文献中a 或b 必须存在，也包含同时存在： 3 1 逻辑非：如a - b ，表明一篇文献中包含a 但不包含b 。 2 截词检索( t r u n c a t i o ns e a r c h ) 截词检索也是一种常用的检索技术，在西文检索中使用更广泛。它可以一次 性地解决词干相同的词，英美不同拼法的词的检索。借此检索按截断的位置来分， 有后截断、前截断、中截断三种；按截断的字符数量来分，有有限截断和无限截 断两种。 后截断：将截词符号放在字符串右方，保持词的前方一致。如：c o m p u t e r * ， 可检索出：e o m p u t e r a c y 、c o m p u t e r i z e 、c o m p u t e r s 前截断：将截词符号放在字符串左方，保持词的后方一致。如：+ c o m p u t e r ， 可检索出：m i c c o m p u t e r 、m i n i c o m p u t e r 中截断：又称通用字符法，将截词符放在检索词的中间，主要解决一个词的 英美不同拼法及有些词的单复数问题。如：o r g a n i ? a f i o n ，可检索出：o r g a n i s a t i o n 、 山东大学硕七学位论文 o r g a n i z a t i o n 。 有限截断和无限截断的区别在于对被截断部分的字符数是否限制。上述例子 中均未限制，因此，也为无限截断。 3 限制检索( l i m i t a t i o ns e a r c h ) 在信息检索系统中，为缩小命中文献的数量，常将检索范围限定在某个字段 或某个范围中。如将检索词限制在标题字段，这样，检索面要比在全文字段的范 围小很多，而且命中的文献可能会与提问更贴切。还可以将提问缩小到某个时间 范围进行检索。 4 位置检索( p o s i t i o ns e a r c h ) 位置检索可以反映出两个检索词在文献中的临近关系。常用的表示有：中间 可查入几个字、两次可否颠倒位置、紧密相连、在同一句话中等，这种检索技术 常用在全文检索中，可以弥补布尔检索的不足。 5 加权检索( w e i 【g h ts e a r c h ) 加权检索中，检索者根据检索词在需求中的重要程度给定个权值。在检索 中，由系统先查找存在这些检索词的文献，并计算它们的权值总和。然后，检索 者再给定一个阈值。只有当存在这些检索词的文献的权值之和大于或等于该阈值 时，才算命中。 6 超文本检索( h y p e r t e x ts e a r c h ) 超文本是一种信息的组织方法。它把不定长的基本信息单元存放在结点上， 这些基本信息单元可以是单个字、句子、章节、文献，甚至是图像、音乐或录像。 结点以链路方式链接。链路可以分为层次链、交叉引用链、索引链等，构成网状 层次结构。超文本检索时，其内容排列是非线性的，按照知识( 信息) 单元及其 关系建立起知识结构网络，操作时根据相关的知识单元，检索便可追踪下去，进 入下面各层单元。 2 2 3 信息检索模型 a ) 相关概念 停用词( s t o pw o r d ) ：指文档中出现的连词，介词，冠词等并无太大意 义的词。例如在英文中常用的停用词有t h e ，a ，i t 等：在中文中常见的 山东大学硕士学位论文 有“是”，“的”，“地”等。 索引词( 标引词，关键词) ：可以用于现代文档内容的预选词语，一般 为名词或名词词组。 词干提取：例如：c o u n t r i e s = c o u n t r y ，i n t e r e s t i n g = i n t e r e s t 中文切词( w o r ds e g m e n t a t i o n ) ：或称分词，主要在中文信息处理中使 用，即把一句话分成一个词的序列。如，“网络与分布式系统试验时”， 分词为“网络与分布式系统试验室”。 b 1 取模型的形式化特征 1 文档逻辑视图：用一组索引词或关键词来表示一篇文档。索引词既可以 自动提取，也可以是由人主观指定。 2 信息组织是实现信息检索的基础，原始的文档中包括文本、图像、视频、 音频等数据，不能直接进行检索，需要从这些原始数据中抽取逻辑视图，支持信 息检索。用户用查询来表示他们的信息需求。检索系统根据查询的表示，搜索文 档集，获取与用户查询相关的文档。信息检索的匹配是相似性匹配，查询的结果 按序返回。信息检索的过程主要涉及到三个重要的处理：文档集的逻辑表示、查 询的表示、相似匹配( 也就是后面要介绍的相似度的计算) 及其排序。 依照用户查询，对文档集合进行有关排序的一组前提假设和算法，信息检索 可以表示为一个三元组( 如下) ：f 【d ，e ，尺( g ，d ，) j ，其中，d 是文档集中的 一组文档逻辑视图( 或称为文档的表示) ；q 是一组用户信息需求的逻辑视图( 表 示) ，这种视图( 表示) 被称为查询；f 是一个框架，用以构建文档；查询以及 它们之间关系的模型。r k ，d ，) 是一个排序函数，该函数输出一个与查询q ，q 和文档表示d ，d 有关的实数。这样就在文档之间根据查询吼定义了一个顺序。 常用的信息检索模型有：集合论模型、代数模型、概率模型等。 l l f 东大学硕士学位论文 $ 。i 。t l i i g 0 。一i 上土；出0 图2 2 文档逻辑视图( 即文档表示) 信息检索模型分为三类：基于内容的信息检索模型，结构化模型和浏览型 检索模型。 其中基于内容的信息检索模型有： 1 ) 集合论模型：布尔模型、模糊集合模型、扩展布尔模型； 2 ) 代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经 网络模型； 3 ) 概率模型：经典概率论模型、推理网络模型、置信( 信念) 网络模型。 c ) “共有词汇”假设( s h a r e db a go f w o r d s ) 1 用词汇来表示一篇文档，并用它作为相关性评价的基本依据。 文档与查询中所有出现的词汇构成了一个词典= 伍” ”，则一个查询q 可以表示一个向量 ”1 旷。w 目，一个文档d 2 ”1 ，”r 。此时，所表示的文 档和语法无关( 词的次序) 、和文档结构无关( 标题，段落) 、和元信息无关( 作 者，来源，类别等) 。 2 依据共有词汇假设的信息检索 存在共有：如果t 有q 含有的某些，则r e l e v a n t ( q ，d ，) = l ： 全部共有：如果t 有q 含有的所有七，则r e l e v a n t ( q ，d ，) = l ； 比例共有：如果d ，有q 共有多于m 的k ，则r e l e v a n t ( q ，d ，) = 1 。 d ) 布尔检索模型 这是一种简单的检索模型，建立在经典的集合论和布尔代数的基础上。 遵循两条基本规则：1 ) 每个索引词在一篇文档中只有两种状态：出现或不 山东大学硕士学位论文 出现，对应的权值为0 或1 。2 ) 查询时有三种布尔逻辑运算霁 i a n d ，o r ，? 1 0 琏接 索引词组成的布尔表达式； 用d 1 和d ：分别表示两个有限集合，给出布尔逻辑运算“与( a n d ) ”、“或 ( d r ) ”、“非( 打”运算的定义，如图2 1 所示。其中“n ”，“u ”和“一”分 别为a n d 、o r 和n o t 运算符表示。 可以将查询转化为一个主析取范式肼。 例如：查询为q = k 。i 阮y k 。) ，进一步表达为：g 耐= ( 1 ，u ) v ( 1 ，l ，o ) y o ，0 ，0 ) 即：每一个分量都是三元组纯，k b ，k 。) 的二值分量。 定义：用g 村表示查询q 的析取范式，表示g 村的任意合取分量a 文档t 与查询q 的相似度为： r ，1 i f3 q 。i ( q 。q 村) i ( v k i ，g ，乜) = 晶0 。) ) s i m ( d i ，g ) = ( 2 i ) lo 。旃。，括p 如果曲”乜，g ) = l ，则表示文档乃与g 相关，否则为不相关。曲”，g ) 为该 模型的匹配函数。 1 简单实例： 口：病毒a n d ( 计算机0 l 电脑) a n d 肋r 医，则搜索出来的文档列表如 下： 吐：据报道，计算机病毒近日猖獗 d ，：小王虽然是学医的，但对研究电脑病毒也很感兴趣，最近发明 了一种 d ，：计算机程序发现了艾滋病病毒的传播途径 2 布尔模型的优缺点：布尔模型简单且容易理解，可以处理结构化提问。 然而由于它所采用的准确匹配策略过于僵硬，构造一个好的布尔表达式并不容 易。另外，由于索引词的状态只有存在和不存在两种情况，无法反映索引词在每 篇文章中的数量，不能实现区分对待每一篇文档，因而无法反映不同文档的重要 程度。再者，检索输出完全依赖于布尔表达式与文档的匹配情况，输出量较难控 制，容易造成零输出或输出过量。为了克服上述缺陷，人们对传统的布尔模型进 行改进和扩展，建立了一些新的模型。 f ) 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 山东大学硕士学位论文 向量检索是以向量的方式确定检索内容的方法，系统中的每一篇文档和每一 个提问均用等长的向量表示。 例如，文档集合中的第z 篇文档用p = ( ，。，：，卅) 表示，其中，i ，i 2 ， ，m 为系统中所有索引词集合；提问集合中的第j 个提问用o ，= ( 1 1 , i ：，i 。) 表 示；，。表示文档向量或提问向量中的第后个分量，即文档表示或提问式中所含的 第k 个索引词或检索词。传统的向量空间模型将标引词，。的取值定为o 或1 ， 现在则大多在 o ，1 】区间取值。 这样形成一个向量空间，信息检索中文档与提问的匹配处理过程就转化为向 量空间中文档向量与提问向量的相似度计算问题。某一文档与某一提问的相关程 度可以通过计算该向量对之间的相似度来测定。当全部文档向量与某个提问向量 的相似度都计算完毕后，系统就把相似度超过某一规定阈值的文档( 或者根据预 定要检出的文档数量) 按相似度大小降序排列输出。因此，排在最前面的文档从 理论上讲是和提问最相关的文档。 与布尔模型相比，向量模型有以下几个特色： 1 ) 改变了布尔模型中匹配策略过于僵硬的缺点，索引词和文档的相关程度 可在【o ，1 】闭区间中取值； 2 ) 把用户提问与文档的相似程度作为检索标准，可以从量的角度判断文档 命中与否，从而使检索结果更趋于合理： 3 ) 检索结果可按与提问的相关度排序输出，便于用户通过相关反馈技术修 正提问，控制检索量。 g ) 概率模型 概率模型试图在概率的框架下解决信息检索的问题，即根据文献与提问的相 关概率来排序输出。对于某个特定的检索提问，文献集合中的某一文献是否符合 用户的信息需求可以看成是一个随机事件，每篇文献是否是相关文献的概率各不 相同，综合信息需求的概率和文献与标引的相关概率，才能更为合理地划分检索 结果。 对于概率模型而言，标引词的权值都是二值的，即w f 0 , 1 。目前提出和建 立的概率检索模型大多数建立在贝叶斯( b a y e s ) 概率与统计决策理论基础上， 假设丁表示相关文献集合，r 是r 的补集，表示不相关文献集合。条件概率 山东大学硕士学位论文 e ( r l p ) 表示文献d j 与用户提问q 相关的概率，e ( rd j ) 表示文献b 与用户提 问q 不相关的概率。根据贝叶斯定理可得 咖( 删) 2 黼 ( 2 - 2 ) 概率模型主要关心的是对应一个提问q ，一篇文献d ，出现时它为相关( 或不 相关) 的概率。概率模型正确处理了文献相关的随机性，因而体现了更为先进的 检索思想，并且向用户提供文献的分等级输出，因此，从客观上讲，概率模型使 检索更为合理。 2 2 4 信息检索评估指标 信息检索的评价标准有两个：1 ) 用户是否得到了所需要的信息；2 ) 得到的 信息是否全面而准确。对于第一个问题的评判方法简单而明确。而第二个问题在 实际评判中往往显得比较困难，因为它是反映成功程度的等级尺度。 一般情况下，“查全”和“查准”是用于判定检索效果的两个常用标准。假 设a 为检出的相关信息数：6 为检出的非相关信息数，为误检出的信息；c 为未检 出的相关信息数，为遗漏的信息；d 为未检出的非相关信息数，为系统根据检索 提问正当拒绝的信息，如表2 1 所示。 表2 1 评价指标 、用户判定 相关非相关合计 系统疟卜 己检出 口6口+ 占 未检出 dc + d 总计口一c6 + d口+ 6 c + d 1 查全率( f e c a l lr a t i o ) 当用户要全面检索某一信息库时，检出的成功度可用检出的所有相关信息在 信息库所有相关信息中所占的比例来表示。这种对信息库检索全面性的测量指标 即为查全率，可定义为： 查全率= 蒜嚣豁圳。s ， 也可以表示为： 山东大学硕士学位论文 查全率：生1 0 0 ( 2 4 ) 2 查准率( p r e c i s i o nr a t i o ) 当用户要对检索到的结果进行分析时，检出的相关信息数在所有检出信息中 所占的比例往往成了较重要的评判指标。这种对检索结果中的相关信息的测量指 标即为查准率。也可称为信号噪声比( s i g n a l t o n o i s er a t i o ) 。查准率与检索出 的相关信息数有关，可定义为： 查准率= 筠器m 。 沼s ， 也可以表示为： 查准率= ；1 0 0 ( 2 6 ) 查准率和查全率必须结合使用，单独使用两者中的任何一个都不能全面说明 检索效果的好坏。若检出1 篇相关信息，必能达到1 0 0 的查准率，但是查全率却 会非常低：同样，若检出的信息数等于库中信息的总量口_ - 6 + c t d ，则必能获得 1 0 0 的查全率，但是很显然查准率必定少的可怜。 尽管查全率和查准率在信息检索效果评价中是非常通用的，但是他们都有一 定的局限性。对查全率和查准率而言，它将所有的相关信息都一视同仁，假设他 们具有同等的价值。有这样一种情况，检出的信息对用户来说是以前未曾知道的、 价值非常高的信息，而未检出的信息对用户来说并不十分需要。因此尽管这些都 是相关信息，但是信息的价值却不相同。如果仅用查全率和查准率来评价的话， 是不能很好地反映这个现象的。 3 误检率( n o i s er a t i o ) 误检率为鉴出的结果中，不相关信息占检出信息的比例，可定义为： 误检率= 鼍舞慧笋枷。 池， 也可以表示为： 误检率= ；x 1 0 0 ( 2 - 8 ) 4 漏检率( o m i s s i o nr a t i o ) 漏检率为系统未检索出的相关信息占库中相关信息总数的比例，可定义为： 山东大学硕士学位论文 漏检率= 意嚣黼x 1 0 0 协， 也可以表示为： 漏检率= = 一1 0 0 ( 2 1 0 ) 其实，查全率和漏检率是互补的：而查准率和误检率也是互补的。即：查全 率+ 漏检率= l ；查准率+ 误检率= l 。 2 3 信息过载 因特网大大方便了信息的传播，对我们的工作、生活和学习产生了深刻的影 响。但是，如果要对某一个问题进行研究，人们就会试图在因特网上检索信息。 但通过雅虎等搜索引擎检索出的信息成千上万，有时几乎没有研究价值，这就是 一种信息的冗余。从用户的角度来说就是：怎样找到我想要的信息? 而从研究角 度，即从信息检索的结果来看，怎样高效、准确地从w e b 数据库中查找用户需要 的信息，并以有效的形式呈现给用户。如果对检索结果进行聚类研究，把相似度 很高的信息归为一类，用户可以在有限时间内判断是不是他需要的信息，如果是， 则不用再往下看，只用仔细看这一类；如果不是，再迅速转到下一个聚类，这样 可以节省用户的查询时间，也提高了检索的准确度。 下面一节主要介绍有关文档聚类的知识。 2 4 文档聚类 随着互联网上x m l 文档的日益增多，如何对其内容进行有效的检索查询已 经成为亟待解决的问题。x m l 查询缓存被认为是现阶段能改进x m l 查询引擎 的最直接的办法。在对当前x m l 文档查询系统研究和分析的基础上，本章首先 设计了一个引入语义缓存机制的x m l 查询系统，给出了系统总体架构图，对框 架内各主体模块功能依次进行了介绍和分析，并对x m l 查询缓存模块及其中的 替换策略进行了重点阐述。 山东大学硕士学位论