（计算机应用技术专业论文）基于粗糙集的信息检索研究.pdf

摘要 粗糙集理论是一种处理含糊和不确定性问题的新型数据分析方 法，以其为理论基础的数据处理技术得到深刻关注和不断发展。信息 检索致力于寻求准确、高效、智能的信息组织与存取方法，成为当今 智能信息处理领域的重要研究内容。本文基于粗糙集理论，针对信息 检索模型和信息处理技术涉及的几个关键问题进行了较为深入的研 究和探索。 比较分析传统信息检索模型与标准粗糙集信息检索模型，将条件 概率相似关系结合粗糙集理论引入信息检索，构造概率粗糙集信息检 索模型，有效地解决了标准粗糙集信息检索模型中如何设计分类方 法，以及体现类间关系的难题。在标引词空间定义条件概率关系，反 映了标引空间的模糊相似性，不仅能充分挖掘和利用标引词间相似关 系，而且可调节支持度阈值获得理想检索效果。 深入研究规则获取过程的本质，分析已有规则获取方法存在的问 题，将分布约简应用于规则归纳系统，定义规则的分布核与分布约简 概念，提出一种基于分布约简构造规则知识库的增量式学习方法。采 用启发式算法获取决策信息系统规则集，当新对象加入时在原有规则 知识库基础上进行增量式更新，避免了为更新规则而重新运行规则获 取算法。该方法能适应决策信息系统的不一致情形，且运用此方法所 得规则集能够保持与原信息系统一致。 关键词粗糙集，信息检索，检索模型，规则获取，增量式更新 a b s t r a c t r o u g hs e tt h e o r yi sa k i n do fn e wd a t aa n a l y s i sm e t h o dt od e a lw i t h v a g u e n e s sa n du n c e r t a i n t y ar a p i dg r o w t ho f i n t e r e s tc a nb el a t e l ys e e ni n r o u g hs e tt h e o r ya n di t sa p p l i c a t i o n s t a k i n gu pw i t ho r g a n i z i n ga n d a c c e s s i n gi n f o r m a t i o nr e s o u r c e sp r e c i s e l y , e f f e c t i v e l ya n di n t e l l i g e n t l y , i n f o r m a t i o nr e t r i e v a lh a sb e e nb e c o m i n gc u r r e n tr e s e a r c hh o t s p o to f i n t e l l i g e n ti n f o r m a t i o np r o c e s s i n g t h i st h e s i sm a i n l ya i m st os t u d yo n t h ep r o b l e m so fr o u l g hs e tt h e o r yi nr e t r i e v a lm o d e la n di n f o r m a t i o n p r o c e s s i n gt e c h n o l o g y t h et h e s i sp r o p o s e san o v e li n f o r m a t i o nr e t r i e v a lm o d e lb a s e do n c o n d i t i o n a lp r o b a b i l i t yr e l a t i o na n dr o u g hs e t ，i ta l s op r o v i d e sas o l u t i o n t od e s i g nc l a s s i f i c a t i o nm e t h o da n dr e p r e s e n tr e l a t i o n s h i pb e t w e e nc l a s s e s d e f i n i n gc o n d i t i o n a lp r o b a b i l i t yr e l a t i o n i ni n d e xw o r d ss p a c eo f f e r s c o n v e n i e n c e st om i n ea n du t i l i z es i m i l a r yr e l a t i o n s h i pb e t w e e ni n d e x w o r d s ，a n dg e t sa b i l i t yo fo b t a i n i n gs a t i s f a c t o r yr e t r i e v a lr e s u l t sb y a d j u s t i n gt h es u p p o r td e g r e e 1 1 1 es t u d yo fr u l ea c q u i s i t i o na p p l i e sd i s t r i b u t i o nr e d u c t i o ni nr u l e s i n d u c t i o ns y s t e m d e f i n e sd i s t r i b u t i o nc o r ea n dd i s t r i b u t i o nr e d u c t i o no fa r u l e ，a n dp r o p o s e sak i n do fi n c r e m e n t a ll e a r n i n gm e t h o db a s e do n d i s t r i b u t i o nr e d u c t i o nt oa c q u i r er u l ek n o w l e d g ed a t a b a s e i td e a l sw i t h i n c o n s i s t e n t s a m p l e s ，u s e sh e u r i s t i ca l g o r i t h mt og a i nc o n c i s e r u l e k n o w l e d g ew h i c ha c c o r d sw i t hd e c i s i o nt a b l e ，a n du p d a t e st h ee x i s t i n g r u l ek n o w l e d g ed a t a b a s ew i t hi n e r e m e n t a lw a yw h e nan e ws a m p l ei s a d d e di nd e c i s i o ni n f o r m a t i o ns y s t e m t h i sm e t h o dw o u l db ea p p l i c a b l e t oi n c o n s i s t e n td e c i s i o nt a b l e s ，a n dt h er u l es e tw o u l db ec o n s i s t e n tw i t h t h eo r i g i n a li n f o r m a t i o ns y s t e m k e yw o r d sr o u g hs e t ，i n f o r m a t i o nr e t r i e v a l ，r e t r i e v a lm o d e l ，r u l e a c q u i s i t i o n ，i n c r e m e n t a lu p d a t i n g 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在在论文中作了明确的说明。 作者签名：垄= 塑! 垫日期：么壁z - 年丛月j 细 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：趁幽导师签名：丑7 珥日期珥年上月血 硕士学位论文第一章绪论 第一章绪论 粗糙集理论是一种处理含糊和不确定性问题的新型数据分析方法，以其为理 论基础的数据处理技术得到越来越广泛的应用。信息检索致力于寻求准确、高效、 智能的信息组织与存取方法，成为目前智能信息处理领域的一个研究热点。因此， 基于粗糙集的信息检索理论与应用研究已成为智能信息处理领域的一个前沿问 题，具有重要的理论价值和现实意义。 1 1 引言 大规模数据库的广泛使用和网络的高速发展，导致信息资源数量的急剧增 长，人们正生活在一个巨大的信息海洋之中。然而丰富信息的巨大价值并没有得 到充分体现，人们面对的是一个无序的信息世界，有价值和无价值的信息相互混 杂，如何从这些信息中发掘出真正需要的信息成为当今世界人们面临的一个普遍 难题，这就需要研究新的技术手段组织、整理和存取海量信息。致力于寻求准确、 高效、智能的信息组织与存取方法，信息检索由此成为当前计算机科学与技术学 科的一个研究热点。 、 经典逻辑中只有真假二值，但在现实生活中，实际上有大量含糊现象存在于 真假二值之间。早在1 9 0 4 年，著名哲学家g f r e g e 提出含糊概念，并把其归结 到边界线区域，即在全域上存在一些个体既不能在某个子集上被分类，也不能在 该子集的补集上被分类。1 9 6 5 年，l a z a d e h 提出模糊集理论【l 】【2 】，不少学者试 图通过这一理论解决g f r e g e 的含糊概念，但模糊集没有给出数学公式描述这一 含糊概念，故无法计算出边界线上含糊元素的具体数目。1 9 8 2 年，波兰数学家 z p a w l a k 提出粗糙集理论【3 1 ，把这些无法确认的个体都归属于边界线区域，将这 种边界线区域定义为上近似集和下近似集之差集。由于上近似集和下近似集都可 通过等价关系给出确定的数学公式描述，因此含糊元素数目可以被计算出，从而 实现了g f r e g e 的边界线思想。与其它处理不确定信息的方法比较，如模糊集、 概率统计等，粗糙集具有如下基本特点： ( 1 ) 建立在分类机制基础上，认为知识是将对象进行分类的能力，将分类 理解为在特定空间上的不可分辨关系。不可分辨关系导致对论域的划分，每一被 划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，来近似刻画 不精确或不确定的知识。 ( 2 ) 无需提供所处理数据集合之外的任何先验信息，如统计学中的概率分 硕士学位论文第一章绪论 布、模糊集理论中的隶属度等，而是直接从给定的信息出发，通过不可分辨关系 确定问题的近似域，挖掘隐含在数据中的潜在有用模式，因此对问题不确定性的 描述或处理体现了客观性。 ( 3 ) 将知识的粒度性视为已有知识不能确定表示某些概念的原因，可以表 达和处理不确定信息，并对数据进行简化，在保留关键信息的前提下对数据进行 化简并求得知识的最小表达；能识别并评估数据之间的依赖关联；能从经验数据 中获取易于证实的规则知识。 ( 4 ) 粗糙集理论未能包含处理不精确或不确定原始数据的机制，所以它与 概率论、模糊集理论等其它处理不确定或不精确问题的理论有很强的互补性。粗 糙集与模糊集分别刻画了不完备信息的两个方面：粗糙集以不可分辨关系为基 础，侧重分类，模糊集基于元素关于集合隶属程度的不同，强调集合本身的含混 性。从粗糙集观点看，粗糙集合以不可分辨关系为基础，由一对精确集合所界定， 信息不确定性产生的原因是缺乏足够的论域知识。 作为一种能有效处理不完备、不确定知识的新型数据分析方法【4 】【5 】嘲，粗糙 集理论已在机器学习、决策分析、专家系统、模式识别与数据挖掘等领域【7 l 【8 】【9 1 【1 0 】【l i 】得到了较为广泛的应用，同时也仍然存在许多关键技术与应用均亟待我们 去研究和发展。基于粗糙集的信息检索理论与应用研究已成为智能信息处理领域 的一个前沿研究课题。 1 2 国内外相关研究现状 1 9 8 2 年波兰数学家z p a w l a k 提出粗糙集理论，为数据分析与处理提供了一 种新的数学方法。但是当时该项研究并未引起国际计算机学术界的重视，研究仅 限于一些东欧国家。 1 9 9 1 年z p a w l a k 出版了第一本关于粗糙集的专著( r o u g hs e t - t h e o r e t i c a l a s p c c t so f r e a s o n i n ga b o u td a t a 【1 2 l ，成为粗糙集理论研究的第一个里程碑。1 9 9 2 年r s l o w i n s k i 主编了粗糙集理论应用专著( i n t e l l i g e n td e c i s i o ns u p p o r t ：h a n d b o o k o f a p p l i c a t i o n sa n da d v a n c e so f t h er o u g hs e t st h e o r y ) ) 1 1 3 1 ，此专著对这一时期的工 作成果作了极好的总结，同时也进一步促进了粗糙集理论向应用领域渗透扩展。 1 9 9 2 年开始，国际粗糙集研讨会几乎每年举行一次，会议分别在波兰、加 拿大、美国、日本等地举行。2 0 0 3 年5 月，我国在重庆成功举办了第九届国际 粗糙集、模糊集、数据挖掘与软计算研讨会。此外，分别在1 9 9 8 年、2 0 0 0 年、 2 0 0 2 年、2 0 0 4 年和2 0 0 5 年举行了五届粗糙集与计算趋势国际会议。在这些会议 上，发表了大量具有较高学术价值和应用价值的论文，极大地推动了国内外粗糙 2 硕士学位论文第一章绪论 集理论和应用的广泛深入发展。 信息检索则是伴随着网络技术的发展和信息资源数量的剧增而兴起的研究 领域。当前信息检索技术的研究主要集中在检索模型研纠1 4 】【1 5 】【16 】【1 7 1 、信息处理 技术研列1 8 】【1 9 2 0 l p l l 以及技术应用研究【2 2 】【2 3 1 1 2 4 1 等一些方面。致力于提高信息综合 处理技术的自动化与智能化，缓解丰富信息资源与贫穷知识发现之间的矛盾，基 于粗糙集的信息检索理论与应用研究已成为智能信息处理领域的一个前沿问题， 具有重要的理论价值和现实意义。本文基于粗糙集理论，着重对检索模型和信息 处理技术方面进行深入研究。 检索模型研究的重要作用主要体现在以下几个方面【2 5 】：更精确地描述出文 档与文档、文档与查询问的相关关系，使之能比较和计算；安排更合理、更便于 检索的文献存储形式；在此基础上设计出合理的检索方式；除信息检索外，还进 行一些信息辅助分析工作。传统的信息检索模型有布尔模型、向量空间模型、概 率模型等。文献【2 6 】提出检索系统的布尔模型，其优点在于运算简单易行，且其 结构化提问方式符合用户思维习惯，但是布尔检索本身所赖以建立的二值逻辑和 集合理论缺乏必要的灵活性，不能给出部分满足用户要求的结果。文献【2 7 】提出 检索系统的向量空间模型，其优点在于允许对标引项进行加权，易于实现检索结 果的排序，但是存在提问式缺乏结构性、存储和计算量大、难以反映标引项问关 系等一些缺陷。文献 2 8 】阐述了概率检索模型，概率模型考虑到文档与查询式间 相关性，体现了更为先进的检索思想，从客观上使检索更趋合理，然而一篇文档 是否相关的可能性大小是一个随机事件，其随机性难以确定，因此在可靠的参数 估计方法问题得到解决之前，概率检索模型较难应用于实际。 粗糙集理论在信息检索模型研究中有着自身独特优势。文献【2 9 】首次提出 信息检索的粗糙集模型，认为粗糙集检索模型以标引词空间的不可分辨关系为 基础形成概念类，从而考虑了标引词间的语义关系，实际上是隐含并扩展了布 尔模型；允许对标引项进行加权，并且为检索设置不同的匹配等级，同等级内 又定义了检索结果与查询问的贴近度，因而可方便有效地实现检索结果与查询 式间相似度排序。同时也指出如何设计分类方法，以及如何体现类间关联是有 待进一步研究的难题。经典粗糙集理论通过不可分辨关系划分论域，以集合整 体逼近的方式发现信息系统中的隐含知识【3 0 】。但是经典粗糙集中对象间满足等 价关系的要求过于严格，对于模糊概念的边界区域刻画过于简单，缺乏对复杂 数据的处理机制，特别是对噪声数据的干扰十分敏感，使其应用受到极大限制。 为此有些研究者提出一些泛化的粗糙集模型，如粗糙模糊集模型与模糊粗糙集 模型【3 1 1 ，基于相似关系的粗糙集模型1 3 2 】，基于覆盖的粗糙集模型p 3 1 ，广义模糊 粗糙集模型【3 4 】等，这些模型的提出丰富了粗糙集理论，拓宽了粗糙集理论的应 硕士学位论文 第一章绪论 用研究。因此，扩展标准粗糙集检索模型，设计一种自动的、合理体现类间关 联的分类方法应用于信息检索，是当前基于粗糙集的信息检索模型研究应予以 紧密关注的问题。 自动分类是信息处理技术领域的一个核心部分，文献【3 5 】在此领域进行了开 创性的研究，是关于自动分类的第一篇论文，随后许多著名的情报学家都在自动 分类领域进行了卓有成效的研究。目前，已有大量的统计分类与机器学习技术应 用于自动分类中，包括最近邻算法、决策树、朴素贝叶斯、相关反馈等。自动分 类包括自动聚类、自动归类和类号的自动转换。自动聚类是从待分类对象中提取 特征，然后对其特征进行比较，再根据某种原则将相同或相近特征的对象定义为 一类，并设法使各类所包含的对象数目大致相等。自动归类是分析待识样本的特 征，将其与各类中对象的共同特征进行比较，然后将样本归为特征最接近的一类 并赋予相应的分类号。类号的自动转换则是针对多部分类法并存的现状提出，以 利于分类的标准化。 规则提取属于自动归类的基础性研究工作，也是粗糙集理论的重要研究内 容。针对一致性决策信息系统，已经提出很多基于粗糙集获取规则的有效方法， 取得了一些相关成剿3 6 】【3 _ 7 1 。但是由于描述属性选择不充分、测量误差、以及数 据具非确定性等一些因素，现实应用中数据往往大量地呈现出非一致性。因此， 在基于粗糙集的规则知识获取研究中，必须充分合理地考虑决策信息系统的非一 致性，增强所获取规则集的一般性、和提高其泛化能力，以适应复杂决策信息系 统的分析与处理。关于从非一致决策信息系统中获取规则知识的研究也取得了一 些成果【3 8 1 1 3 9 1 ，其目的在于增强所获取规则知识的适应能力，提高待识对象的匹 配能力。研究规则获取的有效方法，使其对决策信息系统的一致和非一致情形均 适用，并有效服务于后续的决策分析；增量式更新规则集的有效方法，能降低规 则集更新的开销；设计待识对象的决策匹配和冲突处理策略，取得决策分析与自 动分类等关键技术的理论与方法突破，这些关键技术和方法均有待进一步深化提 高。文献【4 0 】将r o u g h 集理论应用于规则归纳系统，提出一种基于粗糙集获取规 则知识库的增量式学习方法，能够有效处理决策表中不一致情形，采用启发式算 法获取决策表的最简规则，当新对象加入时在原有规则集基础上进行规则知识库 的增量式更新，避免了为更新规则而重新运行规获取算法。文献 4 h 基于决策表 分布约简定义规则的分布核与分布约简概念，提出一种基于分布约简的规则获取 方法，首先确定条件类的分布核，进而采用启发式算法计算其分布约简，挖掘出 最简产生式规则，该方法能适应决策表的不一致情形，且运用此方法所提取的规 则集能够保持与原信息系统一致。 综上所述，基于粗糙集的信息检索研究已取得了一些成果，也仍然存在诸多 4 硕士学位论文 第一章绪论 问题有待进一步研究、发展和完善，这正是开展本文研究工作的基点和出发点。 1 3 本文主要工作及创新点 随着大规模数据库的广泛使用和网络的高速发展，信息资源得到极大的丰 富，人们越来越关注如何开发和利用这些资源，高效地定位目标信息变得越来越 重要，信息检索由此成为智能信息处理领域的研究热点。粗糙集理论是一种研究 不完备、不确定知识和数据的表达、学习、归纳的理论方法，以其为基础的数据 分析与处理技术得到越来越广泛的应用。因此，研究基于粗糙集的信息检索具有 极其重要的理论意义和现实意义。本文基于粗糙集理论，针对信息检索模型和信 息处理技术涉及的几个关键问题进行研究，主要工作与创新点包括： ( 1 ) 在分析现有的文本信息检索理论与方法的基础上，将条件概率关系结 合粗糙集理论引入信息检索，给出一种基于概率粗糙集模型的信息检索优化方 法。有效地解决了将粗糙集应用于信息检索时设计分类关系、体现类间关联的难 题。在标引词空间定义条件概率关系，不仅能充分挖掘和利用标引词间相似关系， 而且可据相关反馈调整标引项的支持度阂值，获得理想的检索效果。 ( 2 ) 分析规则获取的过程及本质，在此基础上给出一种基于粗糙集理论的 启发式规则获取方法。其特点在于：采用分类正确度有效处理信息系统中的不一 致情形，从而有效地处理信息系统中不一致情形，极大限度地浓缩数据；求取规 则的核作为获取规则约简的基础；采用启发式算法，根据属性重要度值求得规则 的近似最小约简，从而避免了n p 完全问题。该算法简便、直观，易于从本质上 体现规则获取的过程及实质。 ( 3 ) 基于决策表分布约简定义规则的分布核与分布约简概念，给出一种基 于分布约简的规则获取方法，首先确定条件类的分布核，进而采用启发式算法计 算其分布约简，挖掘出最简产生式规则。该方法能适应决策表的不一致情形，且 运用此方法所提取的规则集能够保持与原信息系统一致。 ( 4 ) 当新对象加入时需更新规则集，为避免重新运行规则获取算法，本文 所设计的增量式算法将浓缩后数据存放于另一专用决策表中，在原有规则集基础 上进行规则知识库的增量式更新，减少了规则产生过程中的搜索空间范围，算法 简洁且易于实现。 1 4 本文结构组织 论文共分七章，总体结构组织如下： 5 硕士学位论文 第一章绪论 第一章主要介绍粗糙集理论提出的背景，评述国内外相关研究现状，简述本 文主要研究内容，并给出论文各章结构安排。 第二章简要介绍粗糙集有关的基本概念，包括信息系统、近似空间及约简等。 第三章着重阐述信息检索领域的研究与发展现状，探讨几种传统的信息检索 模型，并对其性能与优缺点进行分析评价。 第四章针对粗糙集信息检索模型进行研究：首先将其与几种传统的信息检索 模型相比较，论述粗糙集信息检索模型的优势所在；然后详细介绍如何将粗糙集 理论应用于信息检索，并阐述有待进一步解决的问题；最后将条件概率相似关系 与粗糙集理论相结合引入信息检索，构造概率粗糙集信息检索模型，有效地解决 了标准粗糙集信息检索模型中如何设计分类方法，以及体现类问关系的难题。 第五章主要基于粗糙集理论对规则获取进行研究：将粗糙集理论应用于规则 归纳系统，研究基于粗糙集的规则知识库获取方法，当新对象加入时在原有规则 集基础上进行规则知识库的增量式更新，避免为更新规则而重新运行规获取算 法，并在此基础上研究如何应用规则知识库对任意待识样本进行归类。 第六章利用信息检索语料库和u c i 数据集，对第四章的粗糙集信息检索改 进模型和第五章的规则获取方法进行实验分析。 第七章归纳总结本文的研究工作，并展望今后进一步的研究工作。 1 5 本章小结 本章主要简介粗糙集理论的诞生背景、发展历程、以及一些基本特点；结合 信息检索领域综述国内外相关研究现状；简述本文的研究内容与创新点；最后给 出论文的总体结构组织。 6 硕士学位论文 第二章粗糙集理论与方法 第二章粗糙集理论与方法 粗糙集理论是一种处理含糊和不确定性问题的新型数据分析方法。它自问世 以来得到了广泛应用和深入发展，为机器学习、知识发现、决策分析、专家系统、 模式识别、模糊控制等领域提供了一种新的数据分析方法。基于粗糙集理论的数 据分析方法与应用研究，成为当今国际学术研究领域的热点和亮点。 2 1 粗糙集基本概念 经典集合论是粗糙集理论的基础，集合论的等价关系主要用来划分等价类。 全集中的任意子集按等价关系被分类，在给定的全域u 的子集有时能全被分成 类，有时不能被分成类，称能全被分成类的子集x u 是可定义的；而不能全被 分成类的子集是不可定义的。若子集在某一等价关系下不能全被分成类，那么此 时可通过r o u 曲集方法将它近似地分类。 定义2 1 设x u ，r 是u 上的等价关系，a = ( u ，r ) 是一个近似空间，若 u 的子集x 是一些r - 基本类的并集，则称x 是r 可定义的；否则称x 是r _ 不 可定义的。r 可定义集是全集【，上的子集，此子集在全集u 上恰好可被定义， 而r 不可定义集则是在全集u 上不可恰好被定义的子集。r 可定义集被称之为 r - 一致集，而且不可定义集被称之为五不一致集或r - r o u g h 集，简称不一致集 或r o u g h 集。 ， 定义2 2 在近似地定义r o u g h 集时，要借用上近似集和下近似集两个概念： 星( ) = u r u i n d ( r ) y x ) ( 2 - 1 ) 且( x ) = u z u 1 n d ( r ) y n x g ) ( 2 - 2 ) 其中基( x ) 和r ( x ) 分别为肖的胄下近似和r 上近似，y 是( ，上按等价关系 r 生成的等价类。下近似为所有被包含在x 中的等价类的并集，上近似为所有与 x 交集不为空的等价类的并集。 定义2 3 关于r ，可分为以下几种情形： ( 1 ) 墨( x ) = 置( x ) ，x 称为可定义的； ( 2 ) 星( x ) aa n dr ( x ) u ，x 称为粗糙可定义的； ( 3 ) 星( z ) ga n d 月( x ) = u ，x 称为外部不可定义的； ( 4 ) 星( x ) = a a n dr ( x ) u ，x 称为内部不可定义的； ( 5 ) 星( x ) = aa n dr ( x ) = u ，x 称为完全不可定义的。 定义2 4 上近似与下近似之间的差称为j 的r 边界( 域) ，表示为： 7 硕士学位论文第二章粗糙集理论与方法 曰虮( x ) = g ( x ) - g ( x ) ( 2 3 ) 边界是那些既不能在x 上被分成等价类，也不能在1 r 上被分成等价类的元 素的集合。边界域为空，则可通过等价关系恰当地观察凰否则只能r o u g h 地观 察瓜 工的r 正区域记为p o s r ( x ) = 星( x ) ，它是完全属于x 的等价类的元素的集 合；x 的r 负区域记为n e g r ( x ) = u r ( 工) ，它是完全属于x 的补集的等价类 的元素的集合。 近似精度a 。( x ) = c a r d ( r ( x ) ) c a r d ( r ( x ) ) ，表示获得关于x 的知识是否完 全的程度。其中e a r d q ：n 表示集合y 的基数。 因为星( x ) r ( x ) jc a r d ( r ( x ) ) c a r d ( r ( x ) ) ，所以0 钆( x ) 1 。当 靠( x ) = l 时，b k ( x ) = r ( ) 一星( x ) = ，此时x 是可精确定义的；当靠( x ) 0 则s ( y ，功 0 ； ( 3 ) 传递性：若联而力刮力 0 且s ( y ，力s ( z ，y ) 0 则s ( x ，z ) s 也力。 定义4 3u 为一非空有限论域，一个条件概率相似关系是一个映射 r ：u u - - - o ，1 1 ，r 对v x ，y u 满足： i x n v l r ( x ，y ) = p ( x l 力= p ( y 力= 早 卫 ( 4 4 ) j y l 此处，r ( x ，力表示y 支持x 的程度，或者说y 与x 相似的程度。 由定义4 3 可知，模糊相似关系 4 9 1 是弱模糊相似关系的特例，条件概率关系 是弱模糊相似关系的一个具体实例。条件概率关系可作为论域u 中对象相似度 表示的基础，运用概率认识论通过对象间语义关系估计概率值。二维信息表中， 对象由一组属性表示，定义定义4 3 给出了估算条件概率值的算法过程。 考虑如表4 - 4 的二维信息表，对象集u = d t ，0 2 ，0 5 。，通过8 个属性构成 的属性集4 r = ，a 2 ，a 8 ) 描述。表4 - 4 中，西= 口3 ，吩) ，畋= 如，a s ，a 4 ，a 7 ) ， 以= a 3 ，吼，a 7 ，a 8 ) 。因此有：r ( 西，喀) = o ，r ( 吐，以) = l 4 , e ( d 2 ，吗) = 2 4 。 当单元格中值域为【o ，1 】时，二维信息表就泛化为模糊的信息表。相应地，此 时就需要定义模糊条件概率相似关系。 定义4 4 对于z ，y u ，以，以为x , y 关于属性集a t 的模糊集，一个模糊条 件概率相似关系一个映射r ：u x u 一【o ，l 】，胄对v x ，y u 满足： 硕士学位论文第四章基于粗糙集的信息检索模型研究 关于温度 2 4 2 6 ，3 6 的两个模糊集对象实例w a r m ( 聊和r a t h e r - h o t ( r h ) 见 表4 5 。矽和r h 间的相似度计算如下： r(wrh)一min(1,05)+min(05,1)+min(02,1)丝 0 5 + l + l + 0 53 r(rh，1一min(1,o5)+min(05,1)+min(02,1)丝 表4 - 5 关于温度的模糊信息表 条件概率关系与模糊条件概率关系均用来表示对象间相似关系。且模糊条件 概率关系代表了更一般化情形。很容易就能验证，模糊条件概率关系r 也满足 硕士学位论文第四章基于粗糙集的信息检索模型研究 弱模糊相似关系。并且对x ，y ，z u 另外有如下特性： ( 1 ) r ( x ，j ，) = r o ，x ) = 1 营x = y ； ( 2 ) r ( y ，x ) = l r ( x ，y ) 0 铮h = 1 ) ，i ； ( 4 ) r ( x ，力 0 ； ( 6 ) 俾( x ，y ) r ( y ，x ) 0 ) 僻( j ，z ) r ( z ，j ，) o ) e ( x ，力r ( z ，x ) 。 4 3 条件概率粗糙近似 粗糙集理论是一种处理含糊和不精确问题的新型数据分析方法。这一理论引 入代数学中的等价关系讨论知识，把知识看作是关于论域的划分。虽然粗糙集理 论易于分析数据，但是不一定能反映实际应用中元素间关系的现实视图。与基于 划分的标准粗糙集理论相比，基于论域覆盖的模型更具现实意义，因为实际应用 中数据对象间关系不一定严格满足对称性与传递性。本节将条件概率关系与粗糙 集理论相结合，以表示对象间关联，并给出概率粗糙集模型描述。 定义4 5u 为一非空有限论域，r 为u 上一条件概率关系。对坛u 其盯- 被支持集与口- 支持集分别定义为： ( 功= y i y u r ( x ，力口 鲜( 功= y i y u a r ( y ，x ) 口， ( 4 6 ) ( 4 7 ) 其中，口 o ，l 】，蟛( x ) 为支持工的对象集，鲜( 力为被x 支持的对象集。条 件概率关系满足自反性，因此 霹( x ) k u ) 与 鲜( x ) 卜u ) 均构成论域u 上的一 个覆盖。以下仅讨论( ，关于睇( 力通过类似方法推导可得 以表4 - 6 为例，令a = o 7 5 ，可计算出各对象的支持集如下： 碟”( 4 ) = 碣 r o ”( d o = 如，砖，吨，西，碣。) r o ”( 以) = 以，以，匾，碣，每。 r o ”( 以) = 吐，匾， r 0 7 5 ( 以) = 畋，吐，以，4 ，) 硭7 5 ( 吃) = 吐，吨，4 ，4 ，) 碟”瞄) = 西) 霹7 5 ( 喀) = 吐，吨) r 0 7 5 ( 面) = d 2 ，西，4 。，4 ，) 霹7 5 ( 九) = 吐。) 群”( 碣。) = 吃，哝，西，4 ，a l ，) 雕” ：) = 嘎：) 碟”( a l ，) = 碣，以，或，吐：，碣，码， 碟7 5 ( 4 。) = 碱。 7 5 ( 4 ，) = 碣，呜，吃，4 。，4 ，正，a l ，) 碟7 5 ( 码。) = 吃，4 。，4 。) 硭7 5 ( 4 ，) = 吐，西，匾。，碣，) 碟”( a l 。) = 融，吃，a l 。 磷”( e l ，) = 4 ，4 ，4 ， 碟7 5 ( 如) = 如) 硕士学位论文第四章基于粗糙集的信息检索模型研究 定义4 6u 为一非空有限论域，r 为u 上一条件概率关系。对于论域u 的 任意子集x u ，其下近似集与上近似集分别定义为： 壁( x ) = u 彤( x ) 卜u 蟛( x ) x ( 4 8 ) 霹( x ) = u 孵( x ) k u r s ( x ) n x o 下近似集壁( x ) 由所有为x 子集的r ；( x ) 构成， x 相交不为空的群( 工) 构成。 ( 4 9 ) 上近似集( x ) 由所有与 令a = 0 7 5 ，给定u 的一子集x = 破，以，西，吨，4 ，吐。，吐，) ，可计算其条件概 率粗糙下、上近似集如下： 碟7 5 ( x ) = 吃，以，d 7 ，嚷，吐，) 硭7 5 ( x ) = 吐，以，喀，一，以，吃，西，以，西，4 。，西：，吐，4 ，吐，嘎。，碣，4 。，碣，) 4 4 概率粗糙集信息检索模型 文献【2 9 指出：如何设计分类方法是将粗糙集模型应用于信息检索的关键难 题之一，具体表现在如何确定相似关系以及如何控制由此关系导致的粒度大小。 此后较多学者对此进行了一定的研究【5 0 】【5 1 1 ，但均没有很好地解决这些问题。本 节讨论在将文档自动标引后，如何应用概率租糙集模型进行信息检索。 传统的计算机信息检索中，对每篇文档抽取若干标引词，用这些词条的集合 来代表原文，近似表示原文的语义，从而实现按原文语义进行检索。假设m 个文 档构成文档集d = 碣，吐，吒) ，其标引词空间r = ，2 ，) ，文档 d ，( 1 ，m ) 形式化表示为d ，= f i ，2 ，乞 。啾t o ( 1 f m ，1 ，玎) 为布尔 取值，此时d ，为文档的精确标引词空间表示；其取值定义为区间【0 ，l 】更符合当 前信息检索的一般方法，此时d ，即为文档的模糊标引词空间表示。针对文档的 精确表示和模糊表示进行信息检索，为自动挖掘相似概念类，须分别构造标引词 空间的条件概率关系和模糊条件概率关系。 定义4 7 标引词空问t = t i 如，厶) 上的条件概率关系是一个映射 r ：t x t 斗【0 ，1 】，使得对v t ，t 有： 盹舶= 帮 ( 4 1 0 ) 其中s ( ) 为含有标引词的文档集，s ( 0 ) 为同时含有标引词与的文 档集。 定义4 8 标引词空间r = t 。, t 2 ，厶) 上的模糊条件概率关系是一个映射 r ：t x t - o ，1 】使得对v ，0 r 有： 硕士学位论文第四章基于粗糙集的信息检索模型研究 m i n p a ( t , ) ，心( 0 ) ) 她 伊业1 矿 q 。1 d 其中儿( ) 为标引词关于d 的隶属度。 条件概率关系实质上是模糊条件概率关系的特例，对应于标引词隶属度为逻 辑取值情形。以下仅讨论一般化情形一模糊条件概率关系即可。条件概率关系与 模糊条件概率关系体现了这样一个事实：若两标引词趋向同时出现在文档对象 中，则认为此两个标引词相互依赖，属于同一相似概念。既然模糊概率关系对应 在区间【o ，1 】内取值，那么当然就可以在此关系基础上，通过设置一阈值口以自动 挖掘各标引词的相似概念类。 定义4 9 设且是标引词空间t = t , , t 2 ，厶) 上的模糊条件概率关系，对 v t , t 分别定义其盯一被支持集和口一支持集如下： ( ) = ，f r ，r r ( ，) 口) ( 4 1 2 ) 娣( ) = ，i t j r r o ，) 甜 ( 4 1 3 ) 定义4 1 0 假设有m 个文档构成文档集d = 吐，吐，吒) ，r 是标引词空间 t = r 1 ，t 2 ，乙) 上的模糊条件概率关系，对v d d 分别定义其关于r 的甜下近 似集与口上近似集如下： 蜷( d ) = t j r g ( t , ) j t , d 能) d ) ( 4 - 1 4 ) 蟛( 力= u 霹( ) k d a 心) n d a ) ( 4 1 5 ) 霹( ) 与群弛) 用于在标引词空间挖掘概念类形成类空间，口越大则分类所 导致粒度越小，相反口越小则分类所导致粒度越大，因此需据分类结果选择一合 适的盯值。然后在此基础上根据定义9 可求取文档集中任意对象的口下近似集 与上近似集，以便于下一步的贴近度计算。同时，针对文档的模糊表示，为进一 步得到其下、上近似模糊集，还须定义标引词关于文档m 下、上近似集隶属度 计算方法。 定义4 1 l 设r 是标引词空间r = t , , t 2 ，) 上的模糊条件概率关系，文档d 的模糊表示对应文档论域上的一个模糊集，标引词t j ( t j n 关于模糊集d 的下、 上近似集隶属度分别定义为： 镌( 由( ) = 1 ： y a t , ) l t je t a t j 鲜( ) ) ( 4 - 1 6 ) 惕( 们纯) = s u p , u d ( t j ) t j t a t j 蟛( ) ) ( 4 1 7 ) 此处删表示取下确界，s u p 表示取上确界。这样就可首先以文档论域为基 硕士学位论文 第四章基于粗糙集的信息检索模型研究 础据蜷“) 形成标引词概念空间，然后计算文档对象的近似集，再依据近似集隶 属度定义计算每一标引词关于文档对象近似集的隶属度，从而得到文档近似集的 模糊表示。查询式下、上近似集及隶属度计算方法同文档对象计算方法。 定义4 1 2 文档与查询问语义贴近度定义如下： s 1 m ( q ，d ，) = ! 世( q ，d ，) + s i m ( q , ，d ，) ( 4 1 8 ) 删( 刚弘垮塑全些划 ( 4 1 9 ) 墅丝( q ，d ，) = 芒 = = _ ( 4 1 9 ) 。 l 彤( q ) v 聪( d ，) i ，= 躺 ( 4 2 0 ) 得到查询或文档下、上近似集模糊表示后，即可应用贴近度公式计算文档与 查询间、以及文档与文档间语义贴近度，最终根据贴近度值实现检索匹配结果的 排序输出。 4 5 本章小结 本章针对粗糙集信息检索模型进行研究，首先将其与几种传统的信息检索模 型相比较，论述粗糙集信息检索模型的优势所在；然后详细介绍如何将粗糙集理 论应用于信息检索，并阐述需要进一步解决的问题；最后在分析现有的文本信息 检索理论与方法的基础上，将条件概率关系结合粗糙集理论引入信息检索，给出 一种基于概率粗糙集模型的信息检索优化方法。有效地解决了将粗糙集应用于信 息检索时设计分类关系、体现类间关联的难题。在标引词空间定义条件概率关系， 不仅能充分挖掘和利用标引词间相似关系，而且可据相关反馈调整标引项的支持 度阂值，获得理想的检索效果。 硕士学位论文 第五章基于粗糙集的规则获取研究 第五章基于粗糙集的规则获取研究 规则获取是信息处理技术的重点研究内容。本章主要基于粗糙集理论对规则 获取进行研究：将粗糙集理论应用于规则归纳系统，研究基于粗糙集获取规则知 识库的有效方法，当新对象加入时在原有规则集基础上进行规则知识库的增量式 更新，避免为更新规则而重新运行规获取算法，并在此基础上研究如何应用规则 知识库进行决策分析。 5 1 规则获取的r o u g h 集原理 一个决策信息系统( 简称决策表或信息系统) 定义为四元组 俗u ，a ，v ，f 。其中，u = “，x 2 ，屯，矗) 为论域；a = c u d 为有限属性集， c 和d 分别为条件属性集和决策属性集；v = u 。圪，圪为属性a 的值域； f ：u x a v 为一信息函数使得厂( ，口) 圪瓴u ，a 4 ) 。 属性集r 似4 ) 上的不可分辨关系定义为：i n d ( r ) = ( t ，x ，) u 2 l v 口r ， 厂( t ，口) = f ( x ，口) ) 。x u 基于不可分辨关系i n d ( r ) 的下近似定义为 堡( x ) = u 置r ( c ) l z c _ x ，星( 幻是那些可根据知识r 判断肯定属于x 的u 中元素组成的集合；x 基于不可分辨关系i n d ( r ) 的上近似定义为 r ( x ) = u 置r ( c ) l 置n x g ，r ( x ) 是那些可根据知识r 判断可能属于x 的 u 中元素组成的集合。 给定信息系统i s = ，c 和