（计算机应用技术专业论文）关联规则挖掘及其在概念检索中的应用研究.pdf

关联规则挖掘及j 在概念榆索中的应用研究 摘要 随着因特网技术的迅速发展，因特网上信息成几何级数增长，传统的信息检 索服务己不能满足用户的检索需求，因此智能信息检索成为重要的研究课题。概 念检索是实现智能信息检索的重要方式之一。本文针对目前概念检索系统中存在 的问题，利用关联规则挖掘技术，挖掘概念之间的关联和层次关系，自动构建概 念树，实现概念检索。 本文首先介绍了概念检索和关联规则挖掘的发展概况和基本概念，在此基础 上，分析了概念检索中存在的问题。针对自动从文档中导出关键词词条之间的 关联性问题，本文在深入研究加权挖掘算法和向量空间模型中权值特点的基础 上，提出一种矩阵加权关联规则挖掘算法。该算法首先根据k 权值估计思想找出 频繁项集，然后根据矩阵加权置信度找出关联规则。实验结果表明，该算法能有 效地解决上述问题。针对交互式挖掘关联规则的问题，本文将查询表达式作为约 束条件来挖掘相关的关联规则，在分析现有约束关联规则挖掘算法的基础上，提 出一种基于两阶段的约束关联规则挖掘算法。该算法利用已挖掘的关联规则，实 现约束关联规则的挖掘过程。由于在约束条件挖掘的过程中不需要再对数据库进 行挖掘处理，算法可以节省大量时间，提高了查询效率。实验结果验证了这一结 论。本文还针对查询扩展的问题，提出了一种基于规则的概念关联扩展检索技术 以及概念层次的生成方法，该方法根据关键词词条之间的关联规则，将查洵表 达式扩展为相关的表达式，提交给系统执行检索，提高了查全率和查准率。本文 在已有关联规则挖掘算法的基础上，结合所提出的改进算法及技术，最后实现了 一个基于关联规则挖掘的中文概念检索系统原型。 关键词：概念检索，关联规则挖掘，概念关联扩展，加权关联规则，约束关联规 则 天联埘则挖抓 乏je 神概念检索中的心究 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e tt e c h n o l o g ya n dt h e nt h e s u r p a s s i n g i n c r e a s e o fa l lk i n d so fi n f o r m a t i o nc h a r a c t e r i z e db yg e o m e t r i cp r o g r e s s i o n t h e i n t e l l e c t u a l i z e di n f o r m a t i o nr e t r i e v a lh a sb e c o m eam a j o rr e s e a r c ht o p i c f o rt h e t r a d i t i o n a li n f o r m a t i o nr e t r i e v a lc a n tm e e tt h er e q u i r e m e n t so fu s e r s s i n c et h e c o n c e p t - b a s e dr e t r i e v a l i so n eo ft h em o s ti m p o r t a n tw a y so fi n t e l l e c t u a l i z e d j n f o r m a t i o nr e t r i e v a l i no r d e rt os o l v et h ee x i s t i n gp r o b l e ma b o u tc o n c e p t b a s e d r e t r i e v a l ，t h i sp a p e re x p o u n d sa n dp r o v e sh o wt og e n e r a t et h ea s s o c i a t i o nb e t w e e n c o n c e p t sa n dt h ec o n c e p t sl a y e r s ，b u i l dc o n c e p t b a s e dt r e e sa u t o m a t i c a l l ya n da c h i e v e t h ec o n c e p t b a s e dr e t r i e v a lt h r o u g ht h et e c h n o l o g yo fm i n i n ga s s o c i a t i o nr u l e s f i r s t l y ，t h i sp a p e rb r i e f l y i n t r o d u c e st h e d e v e l o p m e n tr e g a r d i n g t h e c o n c e p t b a s e dr e t r i e v a la n dt h et e c h n o l o g yo fm i n i n ga s s o c i a t i o nr u l e s b a s e do nt h i s i n t r o d u c t i o n ，t h i sp a p e ra n a l y s e st h ee x i s t i n gp r o b l e m sa b o u tt h ec o n c e p t b a s e d r e t r i e v a l s e c o n d l y ，i no r d e rt of i n dt h es o l u t i o nt oh o wt od e r i v ek e yw o r d s e n t r i e s f r o md o c u m e n t s ，t h i sp a p e rp u t sf o r w a r dam a t r i x w e i g h t e dm i n i n ga s s o c i a t i o nr u l e a l g o r i t h mb a s e do nt h ew e i g h t e dm i n i n ga l g o r i t h ma n dt h ew e i g h t e dv a l u eo fv e c t o r s p a c em o d e l ，v s m a c c o r d i n gt ot h i sn o v e la l g o r i t h m ，t h es e to ff r e q u e n ti t e m sc a nb e d e r i v e df r o mt h ei d e ao fk - w e i g h t e s t i m a t e ，a n dn e x t ，a s s o c i a t i o nr u l e sc a nb e d i s c o v e r ya c c o r d i n gt ot h em a t r i x w e i g h t e dc o n f i d e n c e e x p e r i m e n t sh a v ep r o v e dt h a t t h i sn o v e la l g o r i t h mi sr e a l l yw o r k s a n dt h i r d l y , t oc o p yw i t ht h ei n t e r a c t i v em i n i n g a s s o c i a t i o nr u l e sw h i l er e t r i e v i n g ，t h i sp a p e rf u r t h e rp u t sf o r w a r dam i n i n gc o n s t r a i n e d a s s o c i a t i o nr u l ea l g o r i t h m ，w h i c ha c h i e v e si t sg o a lt h r o u g ht h em i n e da s s o c i a t i o n r u l e s t h i sm i n i n gc o n s t r a i n e da s s o c i a t i o nr u l ea l g o r i t h mw o r k sj u s tb e c a m ei ts a v e sa g r e a td e a lo ft i m ew i t h o u tr e m i n i n gt h ed a t a b a s e w h a t sm o r e t h i sc o n c l u s i o ni s b a s e do ne x p e r i m e n t s a n dt h e n ，t os o l v et h er e t r i e v a le x p a n s i o n ，t h i sp a p e rf u r t h e r p u t sf c r w a r dat e c h n o l o g yo fc o n c e p t b a s e da s s o c i a t i o ne x p a n s i o nr e t r i e v a l ，a n da m e t h o do fg e n e r a t i n gc o n c e p tl a y e r s ，w h i c hi sa b l et os u b m i tt h er e l e v a n tf o r m s e x p a n d e d f r o mt h er e t r i e v a lo n e si nl i n ew i t ht h ea s s o c i a t i o nr u l e so fk e y w o r d s e n t r i e st ot h er e t r i e v a ls y s t e m f i n a l l y , o nt h eb a s i so ft h em i n i n ga s s o c i a t i o n r u l ea l g o r i t h m ，c o u p l e dw i t ht h en e w l y r a i s e da l g o r i t h ma n dt e c h n o l o g y ，ap r o t o t y p e i sd e s i g n e d w h i c hi sac h i n e s ec o n c e p t b a s e di n f o r m a t i o nr e t r i e v a lb a s e dm i n i n g a s s o c i a t i o nr u l e s k e y w o r d s ：c o n c e p t b a s e dr e t r i e v a l ，m i n i n g a s s o c i a t i o n r u l e s ，c o n c e p t b a s e d a s s o c i a t i o ne x p a n s i o n ，w e l g h t e da s s o c i a t i o nr u l e s ，c o n s t r a i n e da s s o c i a t i o n r u l e s 1 i 关联规则挖掘及：巾概念 ；：索中的胞用训究 1 1 智能信息检索概述 1 1 1 研究背景 第一章绪论 信息检索( i n f o r m a t i o nr e t r i e v a l ，l r ) 的发展经历了稚尔检索、向量空问检索、 模糊集合检索、概率检索、全文检索等过程，目前已发展到超文本检索，不仅检 索过程更加灵活、方便、友好，而且检索结果图、文、声并茂，更加生动形象， 将信息检索提高到一个更高的阶段。但是，单纯运用超文本技术，或者简坼地将 超文本技术与传统地检索方法或系统相结合，并不能得到令人满意地效果和效 率，因为，传统的信息检索服务系统仍然采用关键词或改进的关键词匹配。事实 上，导致检索性能低下的主要原因是孤立词或词组作为查询描述输入。在检索过 程中，检索机制利用输入的关键词信息搜索被检索的文档集合中确切包含相应信 息的文档信息，但由于语法表达中，对同一个信息的描述存在有多种方式，如用 户要求查找搜索引擎的网络蜘蛛实现技术，可能输入时只提供了“网络蜘蛛”这 一知识，但山于描述“网络蜘蛛”还存在有其他的名词：如“机器人”、“爬行器” 等，但在用户提交“网络蜘蛛”的概念后，可能只能查找到包含“网络蜘蛛”概 念信息的文档信息，而对于“机器人”、“爬行器”的信息却检索1 i 出来。吲此利 用传统的检索技术奄找出的文件内容相似性较差。为了能迅速、准确地榆索出用 户所需的信息，人们开始研究智能信息检索。 1 1 2 研究进展 智能信息检索是人_ t 智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 和信息检索相结合 地一个交叉学科，是一种智能化的计算机信息检索系统，它模拟人类关于信息处 理的思维过程和智能活动，实现信息知识的存储、检索和推理，并向用户提供智 能辅助。日| j 人工智能和信息检索的结合主要包括三方面：( 1 ) 信息检索和号家 系统：主要研究方向是丌发一个专家中介系统来协助查询形成、搜索策略选择以 及预测检索文件；r 2 1 信息检索和自然语言处理：它实际e 是以字或词为符号的 一种符号系统。目前自然语言处理对信息检索的应用仍停留在简单语言处理上， 关联胤则挖掘段j 神：概念犄索中的脚川田f 究 例如确认同根和词组等；f 3 ) 信息检索和知i 表达：此领域的研究主要是通过应 用领域知识来理解文件和查询的信息内容。 概念检索【2 j ( c o n c e p t b a s e dr e t r i e v a l ) 是人t 智能和信息检索相结合的一一个 方面，通过”发个专家中介系统( 知识库) 束协助查询，它是实现智能信息检 索的重要方式之 。概念柃索通过构建概念之l i ，j 的相关性( 知识库) ，将用户的查 询请求以概念的形式进行扩展，然后提交到检索系统，输出查询结果，并按知识 库中概念之蒯的相天性对奄询文档进行排序。由于概念检索突破了关键词匹配局 限于表面形式的缺陷，从词条所表达的概念意义层次上来认识和处理检索用户的 请求，所以能较好地消除用户所表达的杏询需求与系统所执行的查询结果之问的 差异，提高系统的查准率和查全率。概念检索首先由m c c u n e l 5 】提出，目前已有 许多智能信息检索系统是基于概念榆索 2 - 6 ，其中比较成功的外文系统有 r u b r i c i “，c s3 1 6 i 等。r u b r i c ( r u l eb a s e di n f o r m a t i o nr e t r i e v a lb yc o m p u t e r ) 是 将信息检索与人： + 智能技术向结合，由专家定义规m 0 树( r u l e b a s e dt r e e s ) ( a n d o r 树) 来表示概念之阳j 的关联以及概念之间的权值。后来有学者【7 。8 1 对 系统作了进一步的改进。c s 3 ( c o n c e p t s e ts t r u c t u r i n gs y s t e m ) 系统可通过用户 界面来定义和调整概念及概念之间的关联，将概念的层次关系以规则树的形式存 储；比较成功的中文系统有“首都电子商城”系统h ，系统采用人工智能中专家 系统的构造技术，通过创建专家知口 库( 语义网络) 初步实现了计算机领域的中 文概念检索。第二章将详细分析这些检索系统。 这些系统主要是通过领域专家定义概念及概念之川的关联，然后对查咖表达 式进行扩展，实现概念检索。这种方式固然有效，但其最大的缺点是建立相关词 典、语义知识库和规则树必须要大量人：i ：参与，工程量大，同时一旦建立好就很 难动态的改变。因此自动构建概念及概念之问的关联成为重要的研究课题。 信息检索中存在着大量的关联规则1 1 0 l ，如：信息资源关联、用户问题表达的 关联、时问关联、组件关联、词条之间的关联等。如何充分利用这些关联，尤其 是文档中关键词和词条之间的关联性，来提高信息检索的智能化，是值得探讨的。 目前已有学者利用关键词词条之l n j 的关联性，有效地解决了文档分类和聚类问 题f l l _ 1 2 】，并提高了系统的查准率和查全率。 1 2 数据挖掘 数据挖掘( d a t am i n i n g ) 【”i 指的是从大型数据库或数据仓库中提取人们感 关联规则挖掘擞儿订：概念榆索中的心j r j 研究 兴趣的知识，这些知识是隐含的、事先未知的潜在的和有用的信息。近几年来， 该技术受到国际人工智能和数据库界的广泛重视，足数据库和信息决策领域前沿 的研究方向之一。研究的主要目标是发展有关的方法论、理论和工具，以支持从 大量数据中提取有用的和计人感兴趣的知u 和模式。 数据挖掘研究涉及到数据库、机器学习、统计学习等众多学科，现已经逐步 扩展到不确定性推理技术、人工智能、高性能计算以及基于神经网络、模糊集理 论、粗集理论、进化计算的软计算等研究领域【1 3 _ “l 。目前各种方向与技术之间相 e 融合，研究内容也纷繁复杂。数据挖掘功能主要包括关联规则、数据分类陋2 捌、 聚类分析【2 3 2 6 l 等。作为本文的研究重点，关联规则挖掘将在下一节详细讨论。 1 3 关联规则 关联规则挖掘较早应用在超市购物篮的分析1 2 7 , 2 8 1 ，是数据挖掘领域早最为活 跃的研究方向之- - 1 i 。它主要片j 来分析数据库中不同属性问有价值的相互依存关 系，目前的研究主要集中在以下几个方珀i ： 1 3 1 基本关联规则挖掘算法 在基本的关联规则挖掘算法研究中，最著名的是a p r i o r i 算法1 2 8 l ，它依赖于 有效的频繁数据项集的产生，开辟了关联规则数掘挖掘的先河。在a p r i o r i 算法 分层搜索的基础上，提出了一些改进的挖掘算法，如d h p ( d i r e c th a s h i n ga n d p r u n e l 算法，p a r t i t i o n 算法【= l l 】等。 l 述算法都没有脱离分层搜索的基本框架，分层搜索最大缺陷是需要多次扫 描数据库，形成多个候选数据项集，算法的执行效率较低，因此不少学者提出了 一些新的频繁数据项产牛方法，如格子图遍历法( l a t t i c eg r a p h ) 3 2 1 、频繁模式 增长算法( f r e q u e n t p a t t e r ng r o w t ha l g o r i t h m ，f p g r o w t h ) 1 33 1 、i s s d m 算法 3 4 1 等。 第三章将详细探讨a p r i o r i 算法、d h p 算法和f p g r o w t h 算法。 1 3 2 关联规则评价 如何构造感兴趣的舰则指标是关联规则挖掘研究的一个重要研究内容陋3 9 j 。 很多算法【2 7 - 3 2 j 都使用“支持度( s u p p o r t ) 置信度( c o n f i d e n c e ) ”的框架。这样 的结构一般挖掘不邢砦支持度很低但置信度较高的关联规则，也无法发现基丁- 负项集( n e g a t i v el t e m s e t ) 的关联舰则，甚至有时会产生一些错误的结果。 ：是 关联规则挖掘披j c 在概念椅索中的、v 用研究 人们引入各利新的阀值以加强对关联舰则的评判。这当中，兴趣度陋3 9 1 的提出是 一个比较瞩目的观点。这些兴趣度的定义各有特色，文献【3 5 1 给出了感兴趣的规则 的定义( r i n t e r e s t i n g ) ，文献【3 6 j 对此作了改进，把事件依赖性的统计定义扩展到 兴趣度定义卜米，文献【3 7 _ 3 8 1 定义了负关联规则的兴趣度，文献1 3 9 l 定义了收集强度 ( c o l l e c t i v es t r e n g t h ) ，使厅j “大于期望值”束发现有意义的关联姚则。 1 3 3 加权挖掘算法 基本关联规则挖掘算法是将数扒库中各个项目以平等一致的方式处理，但事 实上，不同的项目往往有着不i 司的重要性，如超市的管理中，经理可能更关心利 润高或f 在促销的商品的关联规则。为了解决项目、属性在数据库中的重要性不 一致的问题，或特意挖捌某些规则的问题，对项目、记录和属性等赋予一定的权 值。目前针对不同的加权方式，提出了相应的加权挖掘算法。如：m i n w a l 算 法解决了项目加权和记录加权的问题；w a r 算法用来挖掘规则中带参数的 关联规则；m w q a r 算法【4 2 1 是对祸性及量化项进行加权处理，挖掘属性加权关 联规则。第四章将洋细分析这些算法。 1 3 4 增量挖掘算法 增量挖掘算法的研究有事务增量和参数增量两个方面。在许多实际应用中数 据库中的事务记录往往是不断刷新的，新的数据不断被写入，旧的数据可能会被 删除，在这种数据环境下我们称为事务增量。在另方面，数据挖掘过程是一个 人机爿i 断交互的过程，往往需要不断凋整支持度、置信度、约束条件等参数获取 满意的挖掘结果，这种情况我们称之为参数增量。两种挖掘算法的研究都比较多， 如事务增量挖掘算法有f u p 算法i4 ”，基于负边界集( n e g a t i v eb o r d e rs e t s ) 算法 等；参数增量挖掘算法有r e o r d e r ”1 ，d i r e c t l 4 5 1 ，p a t t e r n g r o w n l 4 “，s e p a r a t e l 4 7 l 和s e p a r a t em 1 48 】算法等。第五章将详细分析这些参数增量算法。 1 1 4 本文研究内容 概念检索的关键技术主要集中在如何构建知识库( 规则树) ，如何利用知识 库来进行概念联想扩展。这些问题的解决将对实现概念检索，有着重要的实际意 义。为了解决概念检索中自动构建规则树的问题，本文将关联规则挖掘技术与信 息检索紧密结合，挖掘关键词几司条之问的关联性，提出了两种新的关联规则挖 关联州则挖掘发je 在概念检索中的腑j f j 研究 掘算法及概念联想扩展技术，并应用于概念检索系统中。论文主要工作如f ： 一、对智能信息检索、数据挖掘、概念检索、关联规则挖掘进行了比较深入 研究。描述了概念检索的相关概念以及模型结构，详细介绍了几种概念检索系统； 概述了数据挖掘和关联规则挖掘的研究进展，分析探讨了关联规则定义、挖掘算 法框架及典型算法。 二、针对自动从文档中导出关键问词条之叫的关联性问题，在深入研究加权 挖掘算法和向量空间模型中权值特点的基础上，提出一种矩阵加权关联姚则挖掘 算法。该算法首先根据k 权值估计思想找出频繁项集，然后根据矩阵加权置信度 找出关联规则。实验结果表明，浚算法能有效地从向量空闻模型中挖掘关键词 词条之间的关联规则。 三、为了解决用户在查询过程中，能交互式挖掘关联规则的问题，本文将查 询表达式作为约束条件来挖掘相关的关联规则。在分析现有约束关联规则挖掘算 法的基础上，提出一种基于两阶段的约束关联规则挖掘算法。该算法的基本思想 是以花费长时问来挖掘( 初始化) 无约束关联舰则为代价，换取更短的晌应时间， 算法中优化了关联规则集的存储结构，扩展了类s q l 查询语句。由于在约束条 件挖掘的过程中不需要再对数据库进行挖掘处理，算法可以节省大量时洲，因而 算法是有效的。实验结果验证了这一结论。 四、针对查询扩展的问题，提出了一种有效的基于关联规则的概念关联扩展 检索技术以及j | 念层次的，l 成方法，该方法根据关键嗣阋条之j n j 的关联姗则， 将查询表达式扩展为相关的表达式，提交给系统执行检索，提高查全率和查准率。 血、在已有关联规则挖掘算法的基础上，结合所提出的改进算法及技术，实 现了一个基于关联规则挖掘的中文概念检索系统原型。 全文分为七章，主要内容如f ： 第一章概述了智能信息检索、数据挖掘和关联规则挖掘的研究进展，介绍本 文研究内容。第二章介绍了概念检索的模型结构、概念检索的形式，分析了几种 概念检索系统的基本原理及优缺点。第三章介绍了关联规则的基本问题及定义， 重点探讨了关联规则的算法框架及典型的挖掘算法。第四章分析了加权关联规则 的基本定义和研究现状，提出种适合从向量空间模型中挖掘加权关联规则的算 法。第五章在研究约束必联规则挖捌算法的基础上，提出了一种快速挖掘约束关 联规则的算法。第六章实现一个基于关联规则的智能信息检索原型系统。对系统 的设讣，关键技术的处理，主要功能的实现作了全面的拙述。重点分析了关联库 的构建、概念联想打展、关联库的维护等关键技术的处理过程。第七章总结全文， 给出了本文的i i 要结论和进一步的研究方向。 关联规则挖掘成e n 概念榆索中的心用研究 2 1 基本术语 第二章概念检索 ( j ) 概念：概念是在客观事物的基础上概括而成的，是客观事物在头脑中的 反映。在讨沦信息检索这一课题时，我们认为概念是一些相近实例的聚集，它必 须能够表达这些实例的公共特征。一般来讲，概念包括以下3 种信息：上层概 念( 概括性) ：下层概念( 专门性) ：所有实例的公共特征和限制。 ( 2 ) 概念检索：通过知识库，将用户的查询请求转换为概念形式然后提交 到检索系统，输出查询结果，并按概念中的权值对奄询文档进行排序。 ( 3 ) 概念词典：包含了语法和词汇信息，通过它能使词汇迅速被抽象为概念。 ( 4 ) 概念树：是个别领域知识的层次或分类结构，它的作用主要有两个， 一是表明了概念之间的关系，二是建立了从概念节点到基于概念数据库的关联。 ( 5 ) 文档的分类及索引：搜集到的文档，首先通过预处理抽出文档中的词汇 和短语，然后埘文档进行分类，并抽象文档所包含的概念，同时存入数据库。 2 2 概念检索的模型结构 2 2 1 模型结构 基于概念检索模型如图2 1 所示。 图2 1 概念检索的模型结构 关联圳则挖掘驶j e 在概念检索中的应用研究 图巾概念检索的模型结构分为两大部分：前端盘询部分和后台处理部分。 前端查询部分：用户通过用户界面输入查询条件，系统对用户输入的查洵进 行分析，从概念词典和概念树中得出相应的概念组合，再利用搜索程序从文档数 槲库中，查询符合条什的文档，并将查询结果返回给用户。 后台处理部分：系统利用网络蜘蛛、r o b o t 等搜索工具，搜集w e b 页面及 文档，存储到数据库中。首先通过预处理抽出文档。卜的词汇和短语，对文档进行 分类和索引，并抽象出文档所包含的概念，同时存入文档数据库。 2 2 1 2 概念词典 概念词典将建立从训条到概念的相互映射，即给定个词条就能知道它表 达哪些概念，而给定一个概念，义可得到描述概念的所有词条，这是一个多对多 的映射。词典的构造原则是： ( 1 ) 它是针对领域的，因为很多词条在不同的领域有不同的含义，概念词 典中必须包含领域信息； ( 2 ) 在概念词典中，主要考虑以下词性的词扩：名词、动词、形容词、副 词及其短语( 即所谓的实词) 。 2 2 3 概念树 仪有孤立的概念是不够的，还必须掌握概念之问的关系。在这里根据领域 知识的层次结构特点以及概念之州的浯义关系，构造能反j 吠概念之| u j 关系的结构 概念树。 由于概念树采用的结构依据领域知识的层次分类，所以从外形看，概念树 像是一棵n 叉树，在这棵树上，越往上越抽象，越往下越具体。上层概念是下层 概念的概括，而下层概念是上层概念的细化。概念树的构造将遵循以下规则： ( 1 ) 概念树的结构是层次型的，是由领域专家来定义； ( 2 ) 父概念比子概念更一般，即父节点包含子节点概念： ( 3 )子节点的概念必须覆盖父节点概念的某一领域。 由这种方式构成的层次结构，并不严格要求子女仅有一个父母，因此它实 际上是一个有向无环图。 关联j _ ! i ! 则挖掘戌订! 概念榆索中的腑用蚵f 究 2 3 概念检索的方式 概念足个抽象的东西，它通过“表意符号”( 即概念描述元素) 4 能表达 出来。同一概念可以由多个元素来表达，这些拙述元素在概念的约束下就形成同 义关系。同义扩展检索是概念检索的一个基础功能。设想个用厂- 想要查询有关 计算机的信息，他输入关键词“计算机”，但表达相同概念的“电脑”、“微机” 却由于词形上的差异不能满足关键刊匹酉已的要求；另一方面，同概念人们先前 对其称呼和现在的称呼可能有所不同；随着地域的改变同一概念的表达也会不 同；在科技领域中，不同领域出有着自己的术语命名舰范。因此，概念描述具有 很大的 i 确定性。所有这些都使得检索结果受限，而同义扩展检索可以成功地解 决上述问题。 但概念检索不限于此，因为概念并不是孤立存在的。一个概念总是与其概 念之间存在各种各样的联系。例如，一个化学家会将“酒精”这个概念与一个产 品、一种反应物、一种溶剂、一种用途及一种属性等联系起来。他希望从索引中 得到的不仅是文档，还希望索引能帮他产生新想法，建议新的组合，或发现就在 他嘴边却被忘记了名字的事物，这些都是智能检索所必须满足的条件。因此，真 正的概念检索必须实现语义蕴涵扩展( 血查嘲“动物”时，也能奁询其他属于此 类的词如“猫”、“狗”) 、语义外延扩展( 如查询“操作系统”时，也能查询“计 算机软件”) 、语义相关扩展( 如查询“因特尔”时，也能查询“奔腾处理器”) 。 目前国内外的信息检索系统基本没达到这样的要求。 简而言之，概念检索的主要形，包括两个方面，即同义扩展检索和概念联 想扩展检索，前者能够提高检索的杏全率，而后者能够加强系统与人的交，使 其具有一定程度的智能。 2 4 概念检索系统 2 4 _ 1 同义扩展检索 i d g s 系统阻5 0 i ( i n f o r m a t i o nd i s c o v e r i n ga n dg a t h e r i n gs y s t e m ) 通过设置同义 词典和蕴含词典、近义词词典和关联词词典，实现同义扩展检索。系统采剧了向 量空阳j 模型( v e c t o rs p a c em o d e l ，v s m ) 和基于诃频统计的权值评价技术，山特 征提取、源站点查询、文档采集、模式匹配等4 部分组成。其中，为了解决v s m 关联规则挖掘发e 在概念榆索中的应j f j 研究 一蛆一谪 爱k ：舔商 关联脚则挖掘及j d ：概念榆索中的成用研究 图中的每个节点代表一个概念c ，旁边的汉字是对该概念的一种描述。每个 概念c 都带有一个由表达概念的所有同义词所构成的集合巾( c ) 。如：中( “计 算机软件”) = f 计算机软件，软件，程序， ，这相当于知识库中建立了一个 同义词典，可以方便地支持同义扩展检索。图中节点之间地连线代表概念之间的 关系。其中，实线所表示的是概念之间往内涌和外延上的竖向层次关系，虚线所 表示的是相关概念之间的横向关联。 ( 2 ) 概念检索的实现 同义词扩展检索的实现 将所有概念描述元素都统进行概念意义分类标注，使得每个概念的同义词 集合巾中的所有元素都赋予了同样的标识。再对标识进行索引，生成倒排索引文 件，其结构与词索引完全相同。当用户键入一个查询请求时，也同样对其进行分 类标注，并将其作为检索入口，查找标识符索引文件，实现同义扩展检索。 语义蕴涵和外延扩展检索的实现 语义蕴涵和外延扩展检索的主要依据是分类树。通过分类标识符，可以方便 地找到当前概念的父概念、兄弟概念和子概念。读取其父概念、兄弟概念实现了 外延扩展榆索读取其子概念实现了蕴涵扩展检索。 语义相关扩展检索的实现 在概念节点定义中，定义了指m 与当f j i 概念语义棚关的所有概念集合的指 针。只要将其读取出来并输出，便可完成语义相关扩展检索。相关概念集合是以 当前概念的标 符为入口，通过对关系表巾所有参数项的查询而得到的。 2 4 2 2r u b r i c 系统 ( 1 ) 规则树( r u l e b a s e dt r e e ) 的结构 r u b r i c 系统中的规则树是 士| 领域专家直接构建，其结构如图2 3 所示 图2 3 “h u m a n 。h e a l t h s c i e n c e ”概念的规则树结构 1 0 关联规则挖掘及其才概念检索中的应用研究 图中最上一层为抽象概念，然后对其进行细分，下一层可以是索引词( 加双 引号) ，也可以是概念( 应包含在上层抽象概念之中) 。如果是概念，则又对其进 行细分，这样循环执行细分，直到所有节点为叶子节点( 索引词) 。概念与概念 之间以及概念与索引词之间的关联程度用权值来表示，权值的取值为【o ，1 】，权值 越大，表示关联程度越高。抽象概念细分成具体概念或索引词时，用“a n d ”， “o r ”表示之间的关系，确定是整体与部分的关系，还是包含与被包含的关系， 或者是其他关系。 ( 2 ) 概念检索的实现 系统接受用户提交查询条件后，首先，从与查询条件最相近的概念出发，沿 着规则树从上到下，搜索所有与之相关的索引词集。然后，搜索数据库中所有文 档，如果文档中包含某个索引词，则将该索引词的权值赋为1 ，否则为0 。这样， 对于每篇文档都有一组索引词的权值。用这些权值来计算此概念的权值，就可判 定文档是否与此概念具有相关性，即文档是否满足用户的需求。如用户提交的查 询为“h e a l t hs c i e n c e ( h u m a n ) ”，而一文档中包含索引词：“h u m a n ”，“g e n e s ”， “d n a ”，“r i s k a s s e s s m e n t ”，则这些索引词的权值为1 ，其它索引词的权值为o 。 通过自下而上，逐层计算，得出概念“h e a l t hs c i e n c e ( h u m a n ) ”的权值为o 6 4 ， 意味着这篇文档与此概念有较强的相关性，可能是用户感兴趣的。 2 4 2 3c s 。系统 ( 1 ) 规则树的构建 c s 3 系统的规则树结构基本同r u b r i c 系统，只是提供图形界面，能方便地 构建和维护概念。这些功能主要包括创建新的概念和维护已有的概念。图2 4 是 系统的一个用户界面。 图2 4 创建和维护概念的界面 关联规则挖掘及j e t ic 概念检索中的戊用研究 用户町通过界面中的按钮和输入框直接处理创建丰维护概念的操作。例如： 要构建一个新的概念，首先在“n e wt o p i cn a m e ”输入框中输入概念的名称，概 念的组件就可以加入到概念层次中，然后输入组件的名称和权值。如果选择 “t e r m ”选项，则将插入索引词条( 如叶肖点) 。组件和相关概念的关系用“o r ” 或“a n d ”束表示。一个构建好的规则树可永久保存供以后使用通过给定的 规则树名称来读取。 ( 2 ) 概念检索的实现 c s 3 系统的概念检索是通过将概念转换为一系列最d , i 1 条集( m i n i m a lt e r m s e tm t s ) ，然后找出满足最小词条集中索引词的文档，并根据权值进行排序。首 先，构造m t s ，类似r u b r i c 系统实时计算各个索引词的权值的方法，m t s 的 构造也是自下往上进行。所不同的是，c s 3 中m t s 的构造是事先完成的，即将 概念展开，直接根据规则树中概念关联及相应权值，一次性转换为一系列m t s ， 而不是对数掘库中每篇文档计算一次。从规则树的叶节点( 索引词) 开始，向上 逐层替换概念，直到树的根节点。在替换过程中，如果部分之间是“a n d ”关 系，则概念只有一个表达式，如果是“o r ”关系，则概念可由多个表达式表示。 对于图2 3 所示的规则树，可以生成以fm t s 。 概念h u m a n m t s ：“m a l l ”( 0 5 ) ) ， ( w o m a n ”( o 5 ) 1 ， “h u m a n ”( 1 0 ) 概念h e a l t h m t s ： h e a l t hh a z a r d s ”( 0 7 ) ， 概念h e a l t hs c i e n c e ( h u m a n ) m t s ：“m a l l ”，“h e a l t hh a z a r d s ”( 0 5 ) ， w o m a n ”，“h e a l t hh a z a r d s ”( 0 5 ) ) ， h u m a n ”，“h e a l t hh a z a r d s ”( 0 6 3 ) ) ， m a n ”，“b i o l o g i c a le f f e c t s ”( 0 3 2 ) ， “w o m a n ”，“b i o l o g i c a le f f e c t s ”( o 3 2 ) 1 ， ( h u m a n ”，“b i o l o g i c a le f f e c t s ”( o 3 a ) ) ， “m a n ”，“g e n e s ”( o 4 ) ) ) 括号中的数字是权值，即表示该词条集对概念的重要程度。 当用户输入查嘲条件后，系统将列出所有与该概念相关的m t s ，供用户选 择。然后将用户所选定的m t s 提交到已有的检索系统中，将返回的结果经排序 后，提交给用户。 】2 关联规则挖掘及j 在概念检索中的脚用研究 2 5 小结 概念检索是智能信息检索的重要研究内容。本章在给出了概念检索的基本术 语、模型结构、检索方式之后，重点对巾、外文概念检索系统的天键技术：规则 树、语义网络的构建和概念联想扩展检索等技术，进行了详细的分析和探i 、r 。 关联则挖掘及j e 亿概念榆索中的) , t is l l 圳究 第三章关联规则挖掘算法研究 3 1 基本问题描述 3 1 1 频繁数据项集 在交易数据库中d 中，假设含囱n 次交易( 即n 个记录) ，且每一个交易 都有一个唯一的交易i d 号，称为t i d ( 即主键) 。每次交易记为t ，均为一些 商品的集合，每个商品称为一个数拥项( i t e m ) 。设i = i 1 ，i 2 ，i m 是所有数据 项的集合，定义数据项集( i t e m s e t ) 是数据项的非空集合，数据项集中数据项的 数目称为该数据项集的长度。如果数据项集x 中含有m 个数据项，则称x 为m 数据项集或称m 长度数据项集。显然d 中的每一次交易t 都对应一个数据项集， 为讨论问题方便我们这里假设t 中的数据项0 i 重复且为有序排列。 数据项x 的支持度和频繁数掘项集定义如下： 定义3 1 在数据库d 中，如果交易t 包含数据项集x 的所有子集，称t 支 持x ，所有支持x 的交易集合被描述为t ( x ) 。数据项集x 的支持度( s u p p o r t ) 简写为s u p p ( x ) ，是指d 中支持x 的交易( 记录) 和所有交易数量的比值。即 s u p p ( x ) = i t ：x t ，t d i i d l( 3 1 ) 定义3 2 对于一个给定的最小支持度m i n s u p ，如果数据项集x 的支持度 s u p p ( x ) m i n s u p 我们就说x 是频繁的，并称其为频繁数据项集( f r e q u e n ti t e m s e t ) 或大数据项集( 1 a r g ei t e m s e t ) 。 基本的关联挖掘只对在数据库汜录中频繁出现的数据项集感兴趣。数据项 集有以下儿个非常有用的性质，是关联规则挖掘算法的设计基础。 性质3 1 对于数据项集a 、b ，如果a b ，则s u p p ( a ) 一 s u p p ( b ) 。 性质3 2 非频繁数据项集的超集仍然非频繁数据项集。 性质3 3 频繁数据项集的子集定是频繁数据项集，但所有子集均频繁的数 据项集不一定是频繁数据项集。 天肤心则挖掘及j n ： | 念榆索中的腑川州l 宄 3 1 2 关联规则 关联规则的定义源丁二“购物篮分析”，其挖掘目的足在海量数据集中发现数 据项集之矧的有趣联系。典型的应用是发现交易数据库中不同商品( 项) 之间的 联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影 响。发现这样的规则可以应用于商品货架设计、货存安排以及根掘购买模式对用 户进行分类。基本关联规则定义如f ： 定义3 3 设x ，y 为数据库dr t 的不相交的数据项集，x ，y c i ，x n y = 巾， 则关联规则是如下形式的一个蕴涵式 r ：x y ( 3 2 ) 在上述定义中，x ny = 中的条件虽然彳：是绝对必需的，但缺少这个条件会产 生出一些冗余规则。例如，规则x y 是显而易见的，规则x x u y 与x y 在数据挖掘的过程中的意义是致的。 前面讨论了关联规则必须具有一定的支持的和置信度才有意义，f 面给出这 两个兴趣指标和强规则的具体定义。 定义3 4 规则r 的嚣信度( c o n f i d e n c e ) 简写称c o n f ( r ) 为c ，是指在数 据库d 中支持x 的事务中有c 事务也支持y ，基于条件概率的定义为： c 。矿( r ) = p ( y i x ) =p ( y t n x t ) s u p p ( x u y ) p ( x 丁)s u p p ( x ) ( 3 3 ) 定义3 5 规则r 的支持度为s 是指