（计算机软件与理论专业论文）基于信息熵的属性约简方法研究.pdf

摘要 摘要 粗集理论的出现，为我们处理不完整、不精确的数据提供了一种很好 的方法。成为知识发现和数据挖掘领域中的有力工具。它不需要专家的知 识和专门机构为原有的数据提供更多的解释，只依赖现有的知识划分等价 类、约简、获取规则。 约简是粗集知识发现的关键，而最小约简的求解是个n p 难度问题。 许多学者提出了一些求解的方法，如基于属性重要性的方法、基于辨识矩 阵的方法、基于信息熵的方法等。 通常属性约简是定义在代数论下的，主要针对协调的信息系统，而对 于实际中大量存在的不协调信息则不完全适用。粗集的信息论描述建立在 信息熵的基础之上，由此定义的理论、定理能很好的解决这个问题。 本文首先阐述了粗集理论的发展及现状，分析了r o u g h 下代数论与信 息论的区别，讨论了基于信息熵的属性约简相关概念、定义，并通过条件 信息熵作为启发知识设计了决策表的启发式知识约简算法，并给出相应描 述。接着结合传统辨识矩阵的特点，在信息论下重新定义了一种新的辨识 矩阵，弥补了对不协调信息处理的不足，并提出了在新的辨识矩阵下计算 核属性以及约简的方法，进一步完善了粗集的信息论理论体系。r r d b 理 论上属于不完备信息系统里的多值系统，在已有概念定义的基础上，针对 精确约简和完全约简提出了r r d b 中上下近似集定义，以及属性约简辨识 矩阵的模型。 最后，给出了实验系统的初步设计，阐述了系统目标和功能模块描述， 并进行系统分析及总体设计，为下一步的研究做出了初步的规划。 关键词粗集；知识发现：信息熵：约简；辨识矩阵 燕山大学工学硕士学位论文 a b s t r a c t t h ea p p e a r a n c eo ft h et h e o r y ( r s t ) ，h a so f f e r e dak i n do fv e r yg o o d m e t h o df o rt h et h i n gt h a tw ed e a lw i t ht h ei n c o m p l e t e ，n o ta c c u r a t ed a t aa n d b e c o m e sa ne f f e c t i v et o o lo f k n o w l e d g ed i s c o v e r ya n d d a t a m i n i n g i td o e s n o t n e e dt h ee x p e r t sk n o w l e d g ea n ds p e c i a l i z e da g e n c yt oo f f e rm o r e e x p l a n a t i o n s f o ra l r e a d ye x i s t i n gd a t a ，o n l yr e l y so ne x i s t i n gk n o w l e d g et od i v i d e ，r e d u c t ， o b t a i nt h er u l e r e d u c t i o ni st h ek e yo fr s ti nk d d ，a n di ti sad i 拄已u l t q u e s t i o no f n p d e g r e et oo b t a i nt h em i n i u mr e d u c t i o n al o to fs c h o l a r sh a v eg i v e ns o m e m e t h o dt os o l v et h ep r o b l e m ，s u c ha sm e t h o df o ri n s t a n c eb a s e do na t t r i b u t e i m p o r t a n c e ，m e t h o do nt h eb a s i so fd i s t i n g u i s h i n gm a t r i x ，m e t h o db a s e do n i n f o r m a t i o ne n t r o p y , e t c u s u a l l ya t t r i b u t er e d u c t i o ni sd e f i n e du n d e rt h ea l g e b r a t h e o r y , d i r e c ta g a i n s t st h ec o n s i s t e n ti n f o r m a t i o ns y s t e mm a i n l y b e c a u s eo fa l a r g e a n l o u n to f i n c o n g r u i t yi n f o r m a t i o n ，i t i sn o t t o t a l l y s u i t a b l e t h e i n f o r m a t i o nt h e o r yo fr s ti ss e tu po ni n f o r m a t i o nf o u n d a t i o no f e n t r o p y , s oi t i su s e f u lt os o l v et h e p r o b l e m t h i sp a p e re x p l a i n st h ed e v e l o p m e n ta n dc u r r e n ts i t u a t i o no fr s ta tf i r s t ， a n a l y s e st h ed i f f e r e n c eb e t w e e na l g e b r at h e o r ya n di n f o r m a t i o nt h e o r yu n d e rt h e r o u g h ，d i s c u s s e ss o m er e l e v a n td e f i n a t i o na n dt h e o r yb a s e do nt h ei n f o r m a t i o n e n t r o p ya n d u s e sc o n d i t i o ni n f o r m a t i o na si n s p i r ek n o w l e d g et od e s i g nd e c i s i o n h e u r i s t i c k n o w l e d g e o fr e d u c t i o na n dd e s c r i b e s c o r r e s p o n d i n g l y t h e n i t c o m b i n e st h ec h a r a c t e r i s t i co ft h et r a d i t i o n a ld i s t i n g u i s h i n gm a t r i x ，r e d e f i n e sa k i n do fn e wm a t r i xu n d e rt h ei n f o r m a t i o n t h e o r y , h a sr e m e d i e d i tt ot h e d e f i c i e n c yo fi n c o n s i s t e n ti n f o r m a t i o np r o c e s s i n g t h em e t h o do fc a l c u l a t e d c o r ea t t r i b u t ea n dr e d u c t i o nu n d e rt h en e wm a t r i xo f d i s t i n g u i s h m e n th a sg i v e n ， s oi th a sp e r f e c t e dt h et h e o r e t i c a ls y s t e mo fr s tf u r t h e r r r d b b e l o n g st ot h e n - v a l u es y s t e mi nt h ei n c o m p l e t e di n f o r m a t i o ns y s t e mi nt h e o r y o nt h e e x i s t i n g 摘要 b a s i s ，ac o n c e p ti sd e f i n e df o rr o u g hc o m p l e t er e d u c t i o na n dr o u g hc r i s p r e d u c t i o na n dd e f i n e st h ed i s t i n g u i s h i n gm o d e lo f m a t r i xi na t t r i b u t er e d u c t i o n f i n a l l y , p r o v i d e s t h e p r e l i m i n a r yd e s i g n o ft h e e x p e r i m e n t a ls y s t e m ， e x p l a i n s a n dd e s c r i b e st h e s y s t e m a t i cg o a l a n df u n c t i o n m o d u l e ，m a k e s p r e l i m i n a r yp l a n n i n gf o rn e x tr e s e a r c h k e y w o r d sr o u g hs e t ；k n o w l e d g ed i s c o v e r y ；i n f o r m a t i o ne n t r o p y ；r e d u c t i o n ； d i s t i n g u i s hm a t r i x 1 1 1 第l 章绪论 1 1引言 第1 章绪论 在现代社会，随着计算机应用的越来越广泛，每年都要积累大量的信 息，即数据。这些信息、数据来自各种领域，如医疗机构、科学观察、公 共服务等等。这些数据中隐含着大量有价值的信息，对这些信息智能的处 理是当前信息科学理论和应用研究的一个热点领域，人们已经在专家系统、 知识工程、人工神经网络、模糊集合等许多领域取得了很多成果。 同时随着信息量的不多增长，人们对信息分析工具的要求也越来越高。 希望自动地从数据中获取其潜在的依赖模型。因此能够从大量信息中形成 实际概括的系统就显得特别重要。虽然已经有了对数据简单统计技术，但 高级的智能分析技术还没有成熟。数据本身所蕴涵的信息往往和得出的结 论相差甚远或不精确，而这些情况的出现也都是因为缺乏一种方便、快捷、 有效的分析工具。 r o u g h 集理论( r o u g h s e tt h e o r y ，简称r s t ) 是波兰数学家z p a w l a k 于 1 9 8 2 年提出的一种数据分析理论。它是一种新的处理模糊和不确定性知识 的数据工具。其主要思想就是在保持分类能力不便的前提下，对决策表进 行约简，导出问题的决策或分类规则。在很多领域内都已被成功地应用或 已取得了丰硕地成果。因此选择r s t 作为研究的理论依据有着坚实的理论 基础和广泛的应用前景。 粗集方法是知识获取和知识发现的主要方法之一。一般来讲，大多数 机构建立数据库的目的是为了有效的管理信息资源，但很少是专门为了挖 掘发现知识。因此，数据库会有许多不完善之处，常常包含许多对发现规 则来讲是冗余的和不必要的属性、不确定值。如果这些冗余属性不能全部 去掉，不仅发现规则的时间复杂性增长，而且发现规则的质量也会相应下 降。粗集方法可以用来处理这些类型的问题，它可以通过对数据进行预处 理，通过属性约简，去掉冗余属性，从而可提高发现效率，降低错误率。 1 燕山大学工学硕士学位论文 随着数据挖掘和知识发现研究的兴起，粗集理论越来越受到重视。知 识获取的对象多为关系型数据库，而关系表可被看作为粗集理论中的决策 表，这给粗集方法的应用带来了极大的方便，而且从数据库中发现不确定 知识也是粗集应用的特长。运用粗集方法得到的知识发现算法有利于并行 执行，可以极大的提高发现效率。对于大型数据库中的知识发现来说，这 是非常关键的。 本文研究的出发点有以下几点： ( 1 ) r s t 以集合论和关系代数为理论基础，是一种刻画不完整性和不确 定性的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的 信息，在数据约简、规则推理方面是一种有力的工具，并在机器学习、模 式识别以及人工智能等领域取得了很多成功的应用； ( 2 ) 信息熵是是立足于概率、抽样、通信这些非确定性概念引出来的概 念，是不确定性信息的重要量度： ( 3 ) 知识发现和知识获取是人工智能领域一个重要的研究问题，而将 r s t 应用到数据信息处理中也是一个主要研究方向，是r s t 理论的核心问 题，也是r s t 从理论到应用的一个关键过程； ( 4 ) 属性约简是知识约简与知识获取中一个重要步骤，针对传统r o u g h 理论的最小属性约简是n p 问题，最优算法的求解是目前一个重要的研究方 向； ( 5 ) 基于信息熵的属性约简则能解决大量不协调信息中属性约简这个 问题，而且还适用于协调系统； ( 6 ) r r d b ( r o u g h r e l m i o nd a t a b a s e ) 也是一种特殊的信息系统，从理论 上说属于一种不完备信息系统。以往的文献中给出了r r d b 中的一些概念 和定义，而针对这种不完备信息系统的属性约简也可以进一步概括研究。 1 2 课题的研究现状及发展趋势 目前，粗糙集理论在科学与工程领域中得到了广泛的应用。已经在人 工智能、知识与数据发现、工业控制、信息检索、模式识别与分类、故障 检测、机器学习、近似推理、决策分析、数据库中的知识发现、专家系统、 2 第1 章绪论 决策支持系统、关联规则挖掘、特征属性选择、决策树生成等方面得到了 较为成功的应用。 1 2 1 课题研究的现状 r o u 【g h 集理论自1 9 8 2 年由p a w l a k 提出以来，不仅在数学理论上不断 完善，而且在其他领域也取得了长足发展和广泛应用，同时也增加了学习 和研究粗糙集理论人员的信心【1 4 】。 针对于粗集研究呈现一种多样化的趋势，张文修等人提出了粗糙集理 论的若干进展与展望，文中对分析了粗集理论的主要研究的8 个方向，并 详细分析论述了己取得的一些成果，最后对以后的研究提出了展望【”。 基于粗糙集的知识约简和知识发现是r s t 研究的一个重要方向。对于 一个信息系统，人们总是期望找出所有约简或最小约简。然而寻求所有约 简或最小约简均为n p 完全问题。同时大部分的约筒算法也都是基于理想 情况下的信息系统，而实际的很多系统中，信息经常出现不协调( 一致) 或 不完备的情况，这就使普通的约简算法不适用。在知识约简这一研究方向 上，主要可以分为针对不协调信息系统与不完备信息系统的知识约简与知 识获取问题。 在课题的调研过程中得到的很多关于知识约简的有价值的文献和资 料，为更好地解决理论和实际的问题，它们将r s t 与其它理论或技术相融 合，为本课题提供了很好的典范，启发了作者的研究思路。 张文修等1 7 j 针对不协调决策表，提出了最大分布约简的概念，它弱于 分布约简，克服了对信息系统过于苛刻的要求：同时，又克服了分配约简 可能产生与原系统不相容的命题规则的缺陷。进一步讨论了分布约简、分 配约简、最大分布约简和近似约简之间的关系，并给出了求这些约简的辨 识矩阵构造方法，对于协调的决策表也适用。 苗守谦等 8 - 9 1 从信息角度，对决策表中属性的重要度给出度量，区另u 于 经典r s t 中属性重要度的定义，提出了一种基于互信息的知识相对约简启 发式算法，该算法的复杂度是多项式级的，并证明了能够通过该算法得到 决策表的最小约简，但不能保证该算法的完备性。 燕山大学工学硕士学位论文 王国胤对r s t 的信息论观点进行了分析，对知识约简在信息论下和代 数观点进行了研究【” ，取得了一些理论成果。用条件信息熵为启发知识设 计了决策表的启发式知识约简算法，通过仿真实验验证了该算法的有效性 和约简效果l ，同时也论述了基于熵的核属性构造方法，为上述算法提供 了必要的依据【l 舶。马垣、王旭等对于信息熵函数的构造详细的进行了详细 分析，提出了一种新的类似熵构造函数l l ”。r s t 信息论的观点拓宽了作者 的思路，成为本课题选择的重要依据，奠定了牢固的理论基础。 信息论观点有着坚实的数学理论基础，将它有效地与r s t 结合在一起 是对传统r s t 的扩充和完善，是本课题的立足点。 在前人深入研究的基础上，周献中等人进行更进一步的探索和研究并 将等价关系进行了扩充，放宽为相容关系。基于相容关系将分布约简、最 大分布约简、分配约简引入不完备信息系统，提出了一种新的约简一分配 序约简，并讨论了几种约简之间的关系，给出了分配约简的一种启发式算 法：条件信息量算法，并验证是有效的【l 。 b t h e r e s a 等人提出了粗糙关系数据库模型( r r d m ) ，并对它进行了定 义，对粗糙关系操作，包括并、差、选择、投影、连接，及相关性质进行 了研究【2 】。y yy a o 、安秋生等分别对r r d m 的基本定义进行了扩充，得 出了一些重要的结论【” 17 1 。郭景峰等关于r s t 理论事务处理方法的研究， 对r r d m 领域进行深入的探讨，如解决r r d m 中属性值的语义等价问题 18 1 9 等，并将这一研究成果应用到课题其它的部分中。 r r d b 是一种多值系统，从理论上说属于一种不完备信息系统。在以 上文章中给出了r r d m 和r r d b 中的一些概念和定义。文献 1 9 】中提出等 价和类和共同类定义和算法描述，分别对应查询处理的精确查询和完全查 询，参照这种定义，对应r r d b 这种特殊的不完备信息系统，其属性约简 也可以相应的分为精确约简和完全约简。对不完备信息系统属性约简的研 究已经有了一些成形的理论和算法，在这些参考文献的基础上，郭景峰等 从r r d b 的角度去讨论多值系统属性约简，提出了新的约简定义和解决方 法及有效的数学模型。完善了粗糙数据库理论体系，为r r d b 应用研究呈 现出一个广阔的应用前景。 4 第1 章绪论 1 2 2 课题研究的发展趋势 随着信息管理系统应用的深入发展，人们对产品系统的要求会越来越 高，既要求具有更好智能性、使用灵活，能够自动的从已有的大量不规则 信息中获取潜在的规律。因此这种知识约简和知识获取的方法就显得尤其 重要。 r o u g h 集理论是一种数据分析理论。它是一种新的处理模糊和不确定 性知识的数据工具。其主要思想就是在保持分类能力不便的前提下，对决 策表进行约简，导出问题的决策或分类规则。因此高效的约简方法是r s t 数据分析的基础，目前并还不存在一种非常有效的普遍算法，所以寻求一 种快速有效的约简方法是r s t 的一个主要研究方向。 目前许多学者对知识约简做了深入的研究，并提出了很多可行的算法 和成果。但是这些研究中大多是在协调( 一致) 的信息系统中进行的。实际 上由于种种原因，大量的信息系统是不协调的，要想从大量的不协调信息 系统中提取规则，就必须对系统进行约简。而基于信息熵的属性约简则能 有效的解决这个问题。 基于信息熵的属性约简是将信息的概率分布理论和粗集理论结合在一 起，定义了信息论下的属性约筒和属性重要性，针对决策系统中大量的不 协调信息更具实际价值。而且在协调信息系统中，信息论和代数论是等价 的。 随着粗集理论的曰臻完善以及新兴领域和新技术的不断涌现，与课题 相关的下一步研究目标如下： ( 1 ) 应用信息熵的理论解决实际中大量存在的不协调信息系统中提取 规则问题，对r s t 下信息论进行研究和扩充； ( 2 ) 讨论分析熵约简函数，及基于熵的辨识矩阵的构造，参照以往辨识 矩阵在约简中的应用，考虑基于熵的辨识矩阵解决不协调信息系统中属性 约简这一问题； ( 3 ) 在不完备信息系统知识约简讨论的基础上，对r r d b 进行讨论分 析，尝试提出r r d b 这一多值系统属性约简定义及理论框架。 s 燕山大学工学硕士学位论文 1 3 课题研究的目标及方法 1 3 1 课题研究的目标 课题研究的目标和设想如下： ( 1 ) 深入研究信息论下属性约简，争取有所创新和突破； ( 2 ) 根据传统辨识矩阵定义结合信息熵提出新的构造方法； ( 3 ) 研究可行的基于熵的属性约简算法，给出具体的实例验证； ( 4 ) 建立r r d b 这一不完备信息系统属性约简理论框架模型。 本文的研究不仅要完善相关文献所提出的方法和理论【1 0 q3 1 ，而且提出 一些新的理论和方法应用到基于r s t 的知识获取领域。 预期的研究结果是在实现所提出方法的理论模型和实现算法的基础 上，通过编程实验来验证方法的有效性和可行性，从而进一步进行实际的 应用。 1 3 2 课题研究的方法 本课题的研究方法是建立在r o u g h 集理论基础上的，r o u g h 集理论是 处理不确定信息的优秀的数学工具。知识约简是r s t 的一个重要研究方 向，具有广泛的应用领域。由于实际系统中大量不协调信息的存在，将 r o u g h 集理论与概率分布结合在一起提出的信息论观点对于解决不协调信 息表知识约简更具有重要意义。在r s t 代数论下辨识矩阵是属性约简的一 种有效手段，结合信息熵共同构成信息论下辨识矩阵构造的理论基础，有 着广泛的应用前景和现实可行性。 课题的实验数据都是实际的决策信息系统实例，本课题的研究成果都 将用这些实验数据进行仿真试验。本课题在研究过程中通过应用现有理论 和模型，将进一步定义验证基于辨识矩阵的属性约简。本课题从实际的实 例出发探讨解决存在不一致信息的决策系统属性约简新的可行性方法。 文中所采用的研究方法是在已有的文献或理论方法的基础上，发现某 项研究领域内的空白、已有文献中出现的问题或解决方法的不足之处，应 6 第1 章绪论 用r s t 理论及其它相关技术提出自己的看法和见解，务求新提出的方法具 有一定的创新性，并要保证所提出方案的系统化和给出其对应简洁清晰的 模型。在提出解决方法之后给出必要的仿真算例和方法分析，其中仿真算 例( 实例) 的作用包括： ( 1 ) 能够进一步解释所提出解决方法的思想； ( 2 ) 能够通过计算来验证所提出方法的有效性和正确性。 另外，仿真算例的设计要本着简单、清晰易懂的原则，并能很好地体 现算法或解决问题的方法思想。而在每次提出某一个问题的解决方法之后， 也要给出该方法的分析，方法分析必须在肯定了方法的优点的同时，还要 指出其不足之处，分析其原因。 1 4 本文主要研究内容 课题研究的主要内容是基于信息熵的属性约简研究及其在实际中的应 用。主要包括以下几个方面： ( 1 ) 基于信息熵的约简算法实例验证及其应用； ( 2 ) 结合信息熵的辨识矩阵构造； ( 3 ) r r d b 属性约简定义。 1 5 本文的结构 本论文主要框架和结构如下。 第一章给出了课题研究的出发点以及研究的主要问题及范围，分析了 r s t 和信息论以及属性约简的发展现状，介绍课题研究的目标及研究方法 的同时，也给出了本文研究背景和未来发展趋势。 第二章是全文基础，首先阐述了与课题研究内容相关的知识和基础理 论，然后根据理论的层次性，从底层到上层依次简要介绍了经典集合理论、 r s t 、属性约简，最后给出了熵理论的简要概述。 第三章是信息论中属性约简，指出现实中存在大量的不协调性( 不一致 性) 。不协调性的存在，缘于多种因素，在约简中，考虑不协调信息是很有 7 燕山大学工学硕士学位论文 必要的，而粗集中的信息论则可以很好的解决这个问题。可以通过条件信 息熵作为启发知识设计了决策表的启发式知识约简算法，并给出相应描述。 第四章是阐明了对于不协调信息系统的约筒应用s k o w r o n 定义的辨识 矩阵也是不完全适用的。结合传统辨识矩阵的特点，在信息论下重新定义 了一种新的辨识矩阵，弥补了对不协调信息处理的不足，并提出了在新的 辨识矩阵下计算核属性以及约简的方法，进一步完善了粗集的信息论理论 体系。 第五章r r d b 理论上属于不完备信息系统里的多值系统，因此属性约 简和规则提取可以参考一些不完备信息系统文献，可以直接处理也可以转 化成完备信息系统处理，但对r r d b 来说第二种方式无疑会增大系统的开 销和信息的冗余，在合适一定条件下，直接用共同关系方式处理也不失为 一种可行办法。本章在已有概念定义的基础上，针对精确约简和完全约简 提出了r r d b 中上下近似集定义，以及属性约简辨识矩阵的模型。 第六章先介绍国外的一个成型的实验系统软件r o s e t t a 的主要功能和 应用实例，再对自己的实验验证方法给出功能分析以及部分模块实现的代 码。 最后总结全文，从r s t 和信息熵理论应用的角度，阐述了课题研究的 结论，并给出了今后本课题主要研究的内容和方向。 第2 章粗集理论及相关知识 2 1引言 第2 章粗集理论及相关知识 本章简要介绍了课题所涉及的基础理论及相关知识，以使论文更易于 阅读和理解，主要包括数据挖掘和知识获取技术、集合论、粗集理论、信 息熵等。 知识发现、数据挖掘是智能信息处理的热点领域，其中一个重要的分 支就是决策信息表的属性约简，粗集理论是知识发现的一个有力研究分析 工具。 集合理论为我们描述离散世界中各种事件提供了一个十分有用的基 础，我们周围千姿百态的世界和千差万别的事物，都可以用集合论的方法 加以描述和阐释。 粗集理论是在集合论基础上发展起来的在智能信息处理中使用的又 一有力工具。它是基于一个机构关于一些现实的大量数据信息，对观察和 测量所得数据进行分类的能力为基础，从中发现、推理知识和分辨系统的 某些特点、过程、对象等。 传统的粗集理论( 代数论) 可以有效的从大量协调、完备信息中获取知 识、提取规则，但对于实际中普遍存在的不协调信息的处理则显得力不从 心。基于信息熵的粗集理论( 信息论) ，能够定义、描述、处理知识中的不 确定信息，从而进一步完成知识发现与知识获取。 2 2 知识发现与数据挖掘 数据库中的知识发现是一个从大量数据中提取出可信的、新颖的、有 效的并能被人理解的模式的多阶段的高级处理过程。 随着数据库技术的不断发展和数据库管理系统的广泛应用，存储的信 息量急剧增大，但数据库只能对数据进行存取，而那些隐藏在大量数据后 的更重要信息则不能获得。而另一方面，人工智能领域的一个重要分支机 燕山大学工学硕士学位论文 器学习的研究也取得了很大进展。关于机器学习的许多方法，如：实例学 习、神经网络和遗传算法等也已经被人们运用于实际系统及智能系统的设 计和实现中。 正是由于数据库技术和机器学习技术的发展，同时为了满足人们实际 工作中的需要，数据库中的知识发现技术才逐渐发展起来【2 0 啦l 。 2 2 1知识发现 数据库中的知识发现是一个多阶段的处理过程，在整个知识发现的过 程中包括很多处理阶段。分别是数据准备、数据选择、数据预处理、数据 缩减、目标确定、挖掘算法确定、数据挖掘、模式解释及知识评价【2 3 】。 知识发现就是利用机器学习的方法从数据库中获得有价值知识的过 程，它是数据库技术和机器学习两个学科的交叉学科。数据库技术侧重于 对数据存储处理的高效率方法的研究，而机器学习则侧重于设法从数据中 提取知识。知识发现利用数据库技术对数据进行前端处理，而利用机器学 习方法从处理后的数据中提取有用的知识。 知识发现使用的数据来自于实际的数据库，所要处理的数据量可能很 大，因此学习算法的效率和扩充性就显得尤其重要，同时数据的完整性和 一致性也很难保证。基于这一点，有效、完善的数学工具对知识发现就尤 其重要。 2 2 2 数据挖掘 数据挖掘( d a t am i n i n g ) 是从大量数据中挖掘出隐含的、未知的、对决 策有潜在价值的知识和规则。它是知识发现的一个重要步骤 2 4 l 。 根据所挖掘的数据库类型、发现的知识类型、采用的技术类型，数据 挖掘有不同的分类方法。 ( 1 ) 按数据库类型分类如果从关系数据库中发现知识，成为关系数据 挖掘：如果从面向对象数据库中发现知识，称为面向对象数据挖掘；还有 事务数据库、演绎数据库、时态数据库、多媒体数据库、主动数据库、空 间数据库、i n t e r n e t 信息库等数据挖掘。 1 0 第2 章粗集理论及相关知识 ( 2 ) 按挖掘的知识类型分类按挖掘的知识类型可分为关联规则、特征 规则、分类规则、偏差规则、聚集规则、判别式规则及时序规则等。另外， 按知识的抽象层次可分为归纳知识、原始级知识、多层次知识。一个灵活 的规则挖掘系统能在多个层次上发现知识。 ( 3 ) 按挖掘的深度分类在较浅的层次上，利用现有数据库管理系统的 查询及报表功能，与多维分析、统计分析方法相结合，进行联机分析处理， 从而得出可供决策参考的统计分析数据。在深层次上，从数据库中发现前 所未知的、隐含的知识。 ( 4 ) 按挖掘的技术工具分类在数据挖掘过程中，往往含有大量不精 确、不确定的信息，如f u z z y 信息、v a g u e 信息等，而经典数学理论对于 这些不确定信息的处理有其局限性，所以自上个世纪六十年代以来，先后 产生了模糊数学、粗集理论、v a g u e 集理论等新兴科学。由此形成了两大 类数据挖掘的数学理论及其挖掘算法集。一类是依据经典理论发展起来的 方法，如基于概率的方法、基于证据理论的方法等；另一类是依据新兴数 学理论发展起来的方法，如粗集方法、v a g u e 集方法、变权分析等。 粗糙集与其它软计算方法的集成是数据挖掘的一种趋势。目前关粗糙 集需进一步研究的问题主要有：粗糙集和其它软计算方法的结合，以提高 分类的能力；粗糙集分类规则的递增算法；高效的启发式约简算法等。 2 3 经典集合理论 2 3 1 集合论的基本概念及运算 集合【25 】是现代数学和逻辑学的基本概念之一。本世纪以来，关于集合 的理论一集合论，对现代数学和逻辑学的发展产生了巨大影响，今天它已 成为数学和逻辑学的一种基础理论。r o u g h 集理论所研究的对象也是集合， 因此现对集合论进行简单介绍。 2 3 1 1 集合论的基本概念用集合论的创始人康托尔增经解释过的话来 说：所谓集合，可以理解为由人的知觉或思维确定的、能明确区分开的对 1 1 燕山大学工学硕士学位论文 象m ，聚集成的一个整体m ，这些对象m 。叫做m 的“元素”。 一般地说，集合是一个不加精确定义的基本概念。把具有某种属性地 一些对象汇集成一个整体，就形成了一个集合，包含在该集合中地对象称 作该集合中的元素【2 6 1 。 2 3 1 2 集合代数运算正如数学中两数之间可以进行加、减、乘、除等 运算一样，两集合之间也有类似的运算。 定义2 1 ：a 和b 是集合，则： ( 1 ) a 和曰的并( 逻辑和) 是集合，记为a u b ，且a u b = x l x a v x b ； ( 2 ) a 和b 的交( 逻辑积) 是集合，记为a n b ，且4 n b = 缸i x a a x b ； ( 3 ) a 和b 的差( 逻辑差) 是集合，记为4 ，且a b = x | x a x b ) 。 定义2 2 ：设a 和b 是集合，如果4 n b = o ，那么则称集合a 和b 是不相交的。 集合的代数运算有如下性质： ( 1 ) a = b 寸b = a ； ( 2 ) a u b o 寸a a v b a ； ( 3 ) a n b a a a b a ； ( 4 ) a a u b ，b 互a u b ； ( 5 ) a n b a ，a n b 互b ； ( 6 ) a = q ，q = a 。 集合的代数运算还满足如下定律： ( 1 ) 幂等律：a u a = a ，a n a = a ； ( 2 ) 交换律：爿u b = b u a ，a n b = b n a ： ( 3 ) 结合律：( a u b ) u c = a u ( b u c ) ，( a n b ) n c = a n ( b n c ) ； ( 4 ) 分配律a u ( b n c ) = ( a u b ) n ( a u c ) ； ( 5 ) 恒等律：一u a = a ，a n q = a ，4 u q = q ，a n a = a ； ( 6 ) 互补律：a u a = q ，a n a = a ； ( 7 ) 德么根律：爿u b = a n b ，a n b = a u b ； ( 8 ) 吸收律：4 u ( a n b ) = a ，a n ( a u b ) = a ； ( 9 ) 双否律：a = a 。 1 2 第2 章粗集理论及相关知识 2 3 2 等价关系及等价类 在集合理论和关系概念的基础上，才能给出了等价关系的定义。等价 关系是所有被讨论的关系中( 如相容关系、序关系等) 最重要的一种。由等 价关系所确定的等价类，是对论域的精确划分，被认为是人工智能的基础。 2 3 2 1关系这里简要给出以下相关定义【2 7 】。 定义2 3 ：a b 的子集叫做4 到曰的一个二元关系：a t a ，x 4 的子 集叫做4 4 4 上的一个三元关系；4 4 一。的子集叫做 a 4x 爿。上的一个竹元关系；a ”的子集叫做4 上的n 元关系。 因为关系是由胛元序偶( 一般为2 元序偶) 构成的，序偶不仅能够表达 集合a 中客体( 元素) 之间的任意关系，还可以被看作单个的元素进行处理， 因此，从本质上讲，关系也是一个集合。 定义2 4 ：设r 是a i 的一个子集，如果r o ，则称r 是空关系；如 果r = 爿，则称r 为全关系。 2 _ 3 2 2 等价关系及等价类这里简要给出以下相关定义f 2 7 】。 定义2 5 ：设尺是集合爿到4 的二元关系，如果对v a a 有( 吼口) r ， 则称胄是a 上的自反关系。 定义2 6 ：设r 是集合爿上的二元关系，如果对v a ，b a ，有( 口，b ) r ， 也必有( 6 ，口) r ，则称r 是彳上的对称关系。 定义2 7 ：设胄是集合4 上的二元关系，对v a ，b ，c a ，如果无论什么 时候有( 口，6 ) r 和( 6 ，c ) r ，必有( 口，c ) r ，则称r 是a 上的传递关系。 定义2 8 ：设r 是集合上的二元关系，如果它是自反、对称和传递的， 则它是a 上的等价关系。 定义2 9 ：设r 为集合一上等价关系a a ，集合陋k = 缸ix a ，a r x ) 称为元素口形成的r 等价类。 定理2 1 ：设r 是集合一上的等价关系，m 、峨是a 中所有等价类， 于是a = m 1 u m ：u ，并且m ，n m ，= a ，i ，。亦即，集合4 上的等价 关系把a 分成了互不相交的等价类。 定理2 2 ：设r 是集合s 的一个等价关系，那么r 的等价类形成s 的 燕山大学工学硕士学位论文 一个划分。因此，给定集合s 的一个划分 4 i i i ) ，存在个等价关系尺 使得每个4 ，i i 作为它的等价类。 2 4 知识库和信息系统 知识表达是智能信息系统的关键。所谓知识获取，就是要从大量的原 始数据信息中分析发现有用的规律信息，既是将知识从一种原始的表达形 式转换为便于理解处理的形式。基于r o u g h 集理论的知识发现，主要是借 助于信息表这样一种有效的数据表知识表达形式，通过现有的方法和工具， 如粗集，对信息表进行分析、约简，最后得到符合用户需要的有价值的规 则。 2 4 1 知识与分类 一般认为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特 性，是属于认识论范畴的概念。知识是客观的并且不以人的意志为转移的， 因此对知识的研究和学习，也存在着客观性和真理性。任何知识都是对其 事物运动状态及变化规律的概括性描述。这个定义不能算是一个完全、精 确的表达，因为知识具有多种意义，特别是在不同领域中进行讨论更加如 此。 知识是人类通过实践认识到的客观世界的规律性的东西，是人类实践 经验的总结和提炼，具有抽象和普遍的特性。知识是对信息进行加工处理、 解释、挑选和改造而形成的。知识是命题、规则等的集合。知识一般可以 分为说明性知识、过程性知识和控制性知识。 有些人认为，知识源于人类以及其它物种的分类能力。关于环境的知 识，从生存的观点来看，就是感觉信号的复杂分类，它是从每个动物的基 本机能对不同情况分类的能力而来的。更抽象层次上的分类是推理、学习、 决策的关键，是一种基础知识。任何事物都是由一些知识来描述的，根据 这些知识可以把它们分类，利用事物不同的属性知识描述，对它们可以产 生不同的分类【2 6 】。 1 4 第2 章粗集理论及相关知识 假定如果两个元素具有相同的信息，则它们是不可区分的，即根据已 有的信息不能够将其划分开，这显然是一种等价关系。 在这个方法中，假设知识是基于对对象分类的能力。对象可以是任何 想象得到的东西，例如实际物体、状态、抽象概念、过程、时刻等。由此 得到以下定义。 定义2 ，l o ：设u o 是研究者感兴趣的对象组成的有限集合，可称为 论域【2 7 】。 定义2 1 1 ：任何子集x u ，称为u 中的一个概念或范畴。 为规范化起见，空集也被认为是一个概念。 定义2 1 2 ；u 中的任何概念族称为己厂的抽象知识，简称知识贮引。 这样，知识就可以定义为：给定一组数据【，和等价关系集合月，在等 价关系集合r 下对u 的划分，成为知识，记为u r 。知识是由人们感兴趣 的邻域的分类模式组成的，它提供关于现实的明显实事，同时也具有由明 显实事推导出模糊实事的推理能力。 知识库( k n o w l e d g eb a s e ) 是以人的分类能力构建人工智能的观点的最 重要的基础概念，信息系统( i n f o r m a t i o ns y s t e m ) 贝1 是粗集方法所要处理的 对象，包括在一个信息系统上进行数据约简、属性约简和规则推理等。 如果论域中的两个对象具有相同的信息，则它们是不可区分的，即根 据已有的知识不能够将其划分开，显然这是一种等价关系。任意的知识都 对应相应的等价关系。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类f 或者u 上的 分类) 构成的集合，【z 。表示包含元素x u 的r 等价类。一个知识库就是 一个关系系统k = ( u ，r ) ，其中u 为非空有限集( 即论域) ，r 是u 上的一族 等价关系f 2 7 j 。 通常我们用等价关系代替分类，在这里，因为这两个概念是完全可以 互相替代的，并且关系更容易处理。 定义2 。1 3 ：若p r ，且p g ，则n p c p 中所有等价关系的交集) 也 是一个等价关系，称为p 上的不可分辨( i n d i s c e m i b i l i t y ) 关系，记为i n d ( p ) ， 且有： 1 5 燕山大学工学硕士学位论文 x 】p 1 = n 【x 】月( 2 - 1 ) 这样，u i n d ( p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相 关的知识，称为足中关于u 的户基本知识。为简单起见，用u p 代替 u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念和基本范畴。特别地， ( 户u i n d ( p ) 还可以被称作初等概念或初等范畴。 实际上p 基本范畴是论域的基本特性，该论域可成为拥有知识p ，换 句话说就是：它们是知识的基本模块，或者说是拥有知识p 的论域的基本 特性。 同样，也可以定义：当k = ( u ，r ) 为一个知识库，i n d ( k ) 定义为丘中所 有等价关系的族，记做i n d ( k ) = i n d ( p ) l o p r ， 2 8 1 。 设k = ( u ，p ) 和墨= ( u ，o ) 是两个知识库。如果i n d ( p ) = i n d ( q ) ，则称k 和k l 是等价的，k 和k l 是等价也就意味着k 和瓦- 具有相同的基础类，即 具有相同的表达能力。利用这个性质可以做为判断知识库约简是否成立的 条件。 2 4 2 信息系统 一个信息系统被描述为s = ( 埘) ，其中u 是一个非空、有穷、被称为 全域的个体的集合，4 是非空、有穷的属性集合，即对于属性a a ，有 a ：u 斗k ，其中圪被称做属性a 的值集；集合矿( 是所有属性a 的值集的 并集) 被说成是属性集a 的值区域，一般情况下，可以将一个信息系统理解 成常用的一张二维关系表。 一般说来，在一个给定的系统中，不能利用系统的属性区别全体单个 个体，也就是说，不同的个体关于考虑的属性可以有相同的值，因此，任 意属性值可以将u 分成类，这些类建立了全体个体集【，上的划分。给定一 个信息系统s = ( u c t ) ，任一子集b a ，加上被称为不可分辨关系的二元 关系i n d ( b ) ：i n d ( b ) = ( ”，u 3 i u x u ：v a b ，口( “) = 口( ” 2 9 。 设论域u = “，心，“，蝴，“，) ，并设属性a = 口，6 ，c ，d ，e ，置圪= ( o ，1 ，2 ) ， 圪= 0 ，1 ) ，= 1 ，2 ，= 1 ，2 ) ，k = o ，1 ，2 ) ，则s = ( c 叫) 是信息系统的 一个实例，如表2 - 1 。 1 6 第2 章粗集理论及相关知识 表2 - 1 一个信息系统的例子 t a b l e2 - 1o n ei n s t a n c eo f i n