决策信息系统分解约简研究论文.doc

摘 要
粗糙集是一种处理不精确、不一致和不完备信息的数学工具，但在实际应用中，数据规模庞大、结构复杂，限制了其应用，在数据分析之前对决策信息系统进行分解是一种有效的数据转换方法。本文主要研究决策信息系统分解约简方法。首先介绍粗糙集理论的基础知识，包括等价关系、信息系统和决策系统、上下近似、约简与核等概念。然后详细论述比较了两种决策信息系统分解方法，即基于粗糙集属性度量的决策信息系统分解方法和属性层次分解约简方法，通过分析，说明了两种方法具有信息量无损，时间复杂度低，实用性强，动态特性好等优点，文中对两种方法均给出了实例说明。根据基于粗糙集属性度量的分解方法，设计并实现了一个分解约简实验系统，详细论述了系统的目标及功能，主要模块的算法思想，介绍系统的实现过程，包括开发平台、编程工具、数据源、数据库等的选取。通过对实验数据的测试验证了该分解约简方法的可行性。最后，对全文进行了概括性总结，并提出了有待进一步研究和完善的问题。

关键词 粗糙集，决策信息系统，分解，约简

ABSTRACT
Rough set theory is a new mathematical tool for processing imprecise, inconsistent and incomplete information, but the traditional rough set method becomes inefficient while dealing with large data sets. Decomposition of the large decision information system is an effective approach to solve the problem. The thesis focuses on decomposition and reduction approaches of decision information system. Firstly, the basic knowledge of rough set theory is introduced in detail, including equivalent relations, information and decision system, upper/lower approximation, core, reduction, etc. Secondly, two different decomposition and reduction approaches of decision information system are analyzed and compared in the thesis. The introductory examples to the approaches are given. It is proved that the two approaches will not cause the loss of information, while computing complexity decreases at the same time. Subsequently, according to the decomposition approach based on rough set attribute measurement, an experimented system is designed and implemented. The aim of the system is presented and the main functional modules as well as algorithms are described in detail. The testing result on the experimented data set shows the applicability of the approach to practice. Finally, a recapitulative conclusion is given, and the problems for further research are pointed out.

KEY WORDS rough set, decision information system, decomposition, reduction

目 录

摘 要 I
ABSTRACT II
第一章 绪 论 1
1.1 研究背景 1
1.2 国内外研究现状 2
1.2.1 粗糙集理论研究现状 2
1.2.2 决策信息系统分解约简研究现状 3
1.3 论文研究内容与结构 3
1.3.1 论文研究内容 3
1.3.2 论文结构 4
第二章 粗糙集理论基础 5
2.1 知识表达 5
2.2 粗糙集合 7
2.3 知识约简与知识的依赖性 8
2.4 本章小结 13
第三章 决策信息系统分解约简研究 14
3.1 基于粗糙集属性度量的决策信息系统分解方法 14
3.1.1 基于粗糙集属性度量的决策信息系统分解思想 14
3.1.2 基于粗糙集属性度量分解方法的性质 17
3.1.3 实例 18
3.2 属性层次分解约简方法 20
3.2.1 属性层次分解约简过程 21
3.2.2 属性层次分解约简的性质 21
3.2.3 实例 22
3.3 本章小结 26
第四章 系统设计与实现 27
4.1 系统设计目标及任务 27
4.2 功能模块设计 28
4.2.1 划分求取 28
4.2.2 相对正域求取 28
4.2.3 核求取 29
4.2.4 属性约简 30
4.2.5 决策信息系统分解 32
4.3 系统实现 33
4.3.1 开发工具及平台 33
4.3.2 数据源 33
4.3.3 数据库 34
4.3.4 系统运行结果 35
4.4 本章小结 36
第五章 工作总结与展望 37
5.1 工作总结 37
5.2 工作展望 38
参考文献 39
致 谢 41

40

决策信息系统分解约简研究 第一章 绪论
第一章 绪 论
1.1 研究背景
随着数据库技术的迅速发展和Internet的迅速普及，人们所面对的数据量急剧增长，无论商业、企业、科研机构或者政府部门都积累了海量的，以不同形式存储的数据资料。依靠传统的数据库技术对数据进行查询、检索等操作不能有效地帮助用户从数据中提取带有结论性的有用信息，远远不能满足数据分析和处理的要求。在拥有大量数据的同时人们对数据中所蕴涵的信息和知识缺乏充分发掘和利用，从而造成了信息的浪费，由此也会产生大量的数据垃圾。因此，人们迫切需要新的强有力的数据分析方法和技术以解决“数据丰富，但信息贫乏”这一现象，帮助人们从繁杂的数据中挖掘出有用的信息，发现其中存在的关系和规则，根据现有的数据来预测未来的发展趋势以辅助决策的智能化自动化，从而带来商业上巨大的信息价值。在这种情况下，数据库知识发现(KDD，Knowledge Discovery in Database)或称为数据挖掘(DM,Data Mining)技术应运而生并显示出强大的生命力。
从20世纪80年代末至今，KDD和数据挖掘技术得到了很大的发展。KDD这一术语首先出现在1989年在美国底特律召开的第11届国际人工智能联合会议的专题讨论会上，1991、1993和1994年又接着继续举行KDD专题讨论会。1995年在加拿大召开了第一届知识发现和数据挖掘国际学术会议，从1997年开始，KDD已经拥有了专门的杂志《Knowledge Discovery and Data Mining》，国外在这方面发表了众多的研究成果和论文，并且开发了一大批数据挖掘软件，建立了大量的相关网站，对KDD和数据挖掘的研究已成为计算机领域的一个热门课题。我国近几年也逐渐跟上国际步伐，许多计算机、数据库、人工智能、机器学习领域的专家学者投入到KDD和数据挖掘的研究中，并已取得了一定的成果。
本世纪七十年代初，波兰学者Z.Pawlak领导的波兰科学院和华沙大学的研究小组，开始对信息系统逻辑特性进行长期基础性研究。他们针对从实验中得到的以数据形式表述的不精确、不相容和不完备等问题，进行分类分析。这项研究是粗糙集理论(Rough Set Theory)产生的基础。
1982年Z.Pawlak发表经典论文 Rough Sets，宣告粗糙集理论的诞生[[] Pawlak Z. Roughsets[J].Int J Comput Inf Set,1982,11(5)：341～336
]。
1991年Z.Pawlak出版专著[[2] Pawlak Z. Roughsets-theoretical aspects of reasoning about data[M].Dordrent：Kluwer Academic Publisheres, 1991
]，系统全面地阐述粗糙集理论，奠定粗糙集理论严密的数学基础，成为粗糙集理论研究的第一个里程牌。
1992年在波兰Kiekrz召开第一届国际粗糙集理论研讨会。同年，粗糙集理论应用专集的出版，极好地总结了这一时期粗糙集理论与实践的研究成果，也进一步促进粗糙集理论的发展。
1996年在日本东京召开第五届国际粗糙集理论研讨会，推动了亚洲地区对粗糙集理论与应用的研究。
2001年5月第一届中国粗糙集理论与软计算学术研讨会在重庆举行。
粗糙集理论不仅为信息科学和认知科学提供了新的科学逻辑和研究方法，而且为智能信息处理和数据挖掘提供了有效的技术。作为一种新型的处理不确定性知识的工具，它能有效地处理下列问题：
1. 不确定或不精确知识的表达；
2. 从实例中获取知识；
3. 不一致信息的分析；
4. 根据不确定和不完整的知识进行推理；
5. 在保留信息的前提下进行数据约简；
6. 近似模式分类；
7. 识别并评估数据之间的依赖关系。
现今如GB数量级的大型数据表已不鲜见，海量数据表中存有百万个对象，上百个属性，当使用原有粗糙集约简方法直接对它们进行分析，以生成规则时，存在如下弊端和不足：
1. 一个含有许多属性的大型决策表能被约简成为一个含有较少相关属性的小型决策表，这一论断并非总能成立；在某些情况下，决策属性实际上受大多数条件属性的影响，因此移除部分属性将有可能引起重要信息的丢失；
2. 许多现有约简算法的结果极大依赖于训练集的大小，也就是说，当训练集规模很大时，约简所得的子集也将很大；
3. 在某些情况下，即使移去了冗余属性，仍然要面对是一个具有大量属性的大型数据集；
4. 在处理含有百万个对象，上百个属性的大型数据库时，使用原有的约简方法，效率将变得很低。
因此有必要对大型数据表进行分解，将多属性多对象组成的大型决策信息系统分解成若干个属性子集，少量对象组成的较小的决策信息系统。分解的目的是使分解所得的决策子系统能方便地利用原有的粗糙集方法进行处理，并且对所用子系统处理的总的时间低于对原系统直接处理的时间，同时尽量保证信息量无损失。
1.2 国内外研究现状
1.2.1 粗糙集理论研究现状
近年来，粗糙集理论及其应用得到了广泛的认可，许多国际会议、学术期刊都将它列为重要内容之一，对粗糙集理论及应用的研究已经成为国际学术界的一个热点，而国内也正处在一个迅猛发展的时期。
粗糙集理论除了朝着逻辑及其近似推理方向发展以外，近些年来出现了大量的Rough函数的研究，发表了一系列关于Rough函数方面的论文，如Rough函数的各种近似运算，Rough函数的基本性质，关于它的Rough连续、Rough极限、Rough可导、Rough积分和Rough稳定性、Rough函数控制及建立由Rough实函数控制的离散动态系统都是典型的问题，这些问题都要求在Rough函数理论的模型下给予公式化。其研究将有贡献于定性推理方法的研究。这种研究实质上是使连续数学离散化，从而使连续数学也能被现代计算机所接受。
目前，对粗糙集理论研究集中在其数学性质，粗糙集拓广，与其它不确定方法的关系和互补，及有效算法等方面。
1. 粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构、拓扑结构，以及粗糙集的收敛性问题。
2. 粗糙集拓广方面的研究主要涉及广义粗糙集模型(或称变精确性粗糙集模型)与对连续属性的离散化等。
3．粗糙集理论与其他不确定性方法之间的关系的研究中，目前主要讨论它与模糊集理论和D-S证据理论的关系和互补。
4. 基于粗糙集的逻辑是关于粗糙集的不确定推理的基础，发展这类逻辑的理论基础也是目前粗糙集理论研究的重要课题。
1.2.2 决策信息系统分解约简研究现状
决策信息分解约简可以说是粗糙集理论中一个较新的研究领域，当前正处于发展阶段。目前的分解方法根据角度不同，主要分为面向对象的分解方法和面向属性的分解方法两种。
现已提出的方法包括：Blaz Zupan等提出的基于函数分解的方法[[] Blaz Zupan, Marko Bohanec, Ivan Bratko, et al. Machine Learning by Function Decomposition. In：Proceedings of the Fourteenth International Conference on Machine Learning, 1997
]，马昕等人提出的基于粗糙集属性度量的分解方法[[] 王庆东，马昕，孙优贤. 基于粗糙集属性量度的数据库分解方法[J]. 浙江大学学报，2004，38(9)：1196～1200
]，樊群等人提出的基于核的分解约简方法[[] 樊群，赵卫东，达庆利. 一种基于粗集的实例分解归纳学习方法[J]. 管理工程学报，2001，15(2)：79～81
]，杨善林提出的属性聚类分解方法[[] 杨善林，刘业政，李亚飞. 基于Rough Sets理论的证据获取与合成方法[J].管理科学学报，2005，8(5)：69～75
]等。
经分析验证，这些方法对某些大型决策信息系统处理时，在计算时间复杂度上优于直接使用粗糙集方法，有较大的应用价值。但这些方法在信息量损失、终止度量选择、动态性等方面均存在不同程度的问题，且只能针对某些特定问题有效，不具备很强的通用性。因此，仍然有待进一步研究发展。
1.3 论文研究内容与结构
1.3.1 论文研究内容
本论文研究的内容为决策信息系统的分解约简，重点研究决策表的分解方法及其性质，同时分析基于分解的约简理论与方法。分析已有的各种方法，进行总结，加以改进。在论文中详细研究一到两种分解约简方法，分析方法其性质，包括其计算时间复杂度、信息量是否损失、动态性、实用性等。综合运用所学的基础理论知识和基本技能，制定合理可行的实验方案，设计并实现一个分解约简系统。
1.3.2 论文结构
论文共分五章，结构安排如下：
第一章，绪论，简要介绍研究背景和意义，粗糙集理论和决策信息系统分解约简的研究现状，以及论文的研究内容。
第二章，粗糙集理论基础，介绍粗糙集理论的基础内容，包括知识表达、信息系统和决策系统、粗糙集合、知识的约简、知识的依赖性等粗糙集理论的基本概念，以及信息熵在粗糙集中的应用等。
第三章，决策信息系统分解约简研究，论述了基于属性度量的分解约简方法和属性层次分解约简方法，详细说明它们的基本思想，并分别对两种方法进行性质分析，实例研究，最后是两种方法的比较。
第四章，系统设计与实现，提出分解约简系统的设计目标及任务，系统功能模块的划分。详细描述主要模块的功能及所使用的算法思想。介绍系统的实现过程，包括开发平台、编程工具、数据源、数据库的选取等。通过测试结果证明该系统的可行性。
第五章，工作总结与展望，对本文的工作进行总结，并进行工作展望，提出继续进行研究的方向。

决策信息系统分解约简研究 第二章 粗糙集理论基础
第二章 粗糙集理论基础
粗糙集理论是面向人类认识知识的数学学科，认为知识是人类对对象进行分类的能力，不可分辨关系是粗糙集理论中的最基本概念。在此基础上，粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性；引入约简和求核进行知识的约简等计算。
2.1 知识表达
1. 知识与分类
分类是推理、学习与决策中的关键问题。因此，粗糙集假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称为所讨论的全域或论域。对于全域及知识的特征并没有任何特别假设。知识构成某一感兴趣领域中各种分类模式的一个族集，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。
给定一个感兴趣的对象论域U，对于任何子集XU可称之为一个U中的概念或范畴，它们构成了特定论域U的分类。
其中，XiU,Xi；XiXj=,当ij,i,j=1,2,…,n；且Xi=U。
知识系统通常处理的是U上的分类族。一个U上的分类族，定义为一个U上的知识库；这样，知识库就是表达一个智能系统的各种基本分类方式的集合。常用等价关系代替分类，因为这两个概念完全可以互相代替。
若R是U上的划分R={X1,X2,…,Xn}表达的等价关系，(U,R)称为近似空间，U/R是R(或U的分类)的所有等价类族。用[x]R表示子集X属于R的一个范畴，且R包含元素xU。
当等价关系所进行的分类将论域细化到某种程度时，就出现了对象间的不可分辨关系。不可分辨关系是粗糙集理论的起点，它意味着由于缺乏信息，不可能通过已有信息分辨对象，换言之，不能将元素作为单一对象来处理，而只能将不可分辨对象族作为知识的一部分来处理。
一个知识库可以表达为K=(U,R)，U/R中的集合称为基本概念、初等范畴或者知识模块。

2. 信息系统和决策系统
为了进行数据分析与处理，需要知识的符号表达，知识表达系统的基本成分是研究对象的集合，关于这些对象的知识是通过指定对象的基本特征(属性)和特征值(属性值)来描述的。
一个知识表达系统S可以表达为四元组
S=<U,A,V,f>
其中，U是对象的非空有限集合，A是属性的非空有限集合，V=∪a∈AVa，Va是属性的值域，f：U×A→V是一个信息函数，它指定U中每一对象x的属性值。
在粗糙集理论中，知识表达系统又称为信息系统，可以表示成信息表的形式。信息表的列表示属性，行表示对象，每个单元格表示对象的属性值。容易得知，一个属性对应一个等价关系，一个信息表可以看作是对一族等价关系的定义，即知识库。
信息系统如果表示为S=<U,CD,V,f>，其中U、V和f的意义不变，CD是属性的非空有限集，C表示条件属性集合，D表示决策属性集合，则这种信息系统被称为决策信息系统或决策表。
决策表可以理解为这样一种描述，即当一些条件被满足时，就可以采取一些决策，大部分决策问题都可以通过决策表形式化，它在许多应用中起了很重要的作用。这里要强调的是，决策表的形式跟关系数据库的关系模式非常相似，而关系数据库已经取得了巨大的发展，所以有关关系数据库的许多新技术可以应用在决策表的操作上，从而使决策表知识表示的应用在新技术的基础上变得更容易实现[[] 肖文洁，王建东，朱朝晖. 决策表的逻辑表达式分析[J]. 南京航空航天大学学报，2006，38(1)：106～110
]。

3. 知识的概率分布
将信息理论的内容引入粗糙集理论中，知识的粗糙性有了信息论的解释，能够帮助更容易地理解粗糙集本质并帮助粗糙运算。
在粗糙集中，知识被理解成关于论域的各种划分模式。对论域进行一种划分就得到关于论域的一组基础概念。如果在论域中任意选取一个对象，那么该对象就随机地满足某个基础概念(即它随机地属于这种划分得到的子集)。所以，粗糙集中的知识可以被看作为随机变量。
设U为一个论域，P和Q为U上的两个等价关系。可以把P和Q定义为U的子集组成的-代数上的两个随机变量。
定义 2.1 设P和Q在U上导出的划分分别为X和Y：
X=U/P={X1,X2,…,Xn}，Y=U/Q={Y1,Y2,…,Ym}，则P和Q在U的子集组成-代数上定义的概率分布分别为：
， (2-1)
其中，Card(X)表示集合X中元素的个数。
，，i=1,2,…,n； (2-2)
，，j=1,2,…,m； (2-3)
定义 2.2 P和Q的联合概率分布定义为：
(2-4)
其中，，，i=1,2,…,n，j=1,2,…,m。
有了概率分布和联合概率分布的定义后，就可以定义知识的条件概率。
定义 2.3 已知知识P的条件下，知识Q的条件概率定义为：
，i=1,2,…,n，j=1,2,…,m (2-5)
2.2 粗糙集合
1. 从精确集合到粗糙集合
集合是由Georg Cantor于1883年提出的，他是整个近代数学的基础性概念。集合是由其中的元素来定义的，一旦集合中的全部元素都唯一确定，则集合本身也就确定了。集合在数学中的定义是明确的，否则就不可能证明任何数学定理
粗糙集理论延拓了经典集合论，把用于分类的知识引入集合内，作为集合组成的一部分。一个对象a是否属于集合X，需要根据拥有的关于论域的知识来做出判断，可分为三种情况：
(1) 对象a肯定属于集合X；
(2) 对象a肯定不属于集合X；
(3) 对象a可能属于集合X，也可能不属于集合X。
因此，集合划分依赖于所掌握的关于论域的知识，是相对的而不是绝对的。给定论域U，等价关系R将U划分为互不相交的基本等价类U/R。设X是论域U上的一个集合，如果X能表示成等价类组成的并集时，则称X在U上是R可定义的，否则X为R不可定义的。R可定义是指可以在知识库K=(U,R)中被精确定义的；R不可定义则不可能在这个知识库中被精确定义，只能通过近似的方法来刻化。R可定义集也称作R精确集(R-exact sets)；对应地，R不可定义集也可称为R非精确集(R-inexact sets)或者粗糙集(Rough sets)。
粗糙集可以近似地定义，在粗糙集理论中采用两个精确集(粗糙集的上近似集和下近似集)逼近的方法来达到这个目的。
定义 2.4 给定知识库K=(U,R)和U的分类U/R，对每个子集XU，X的R下近似和R上近似的定义如下：
集合X关于R的下近似：
={xU：R(x)X} (2-6)
即当且仅当R(x)X时，有x。也就是说，代表那些根据现有知识能够判断出肯定属于X的元素所组成的最大集合。
集合X关于R的上近似：
={xU：R(x)X} (2-7)
即当且仅当R(x)X时，有x。则代表与X相交非空的所有等价族的并集，是可能属于X的对象所组成的最小集合。

2. 正域、负域和边界域
有了R下近似和R上近似的定义，下面介绍正域、负域和边界域的定义。
定义 2.5 边界域BN(X)= -
边界域所包含的是那些不能确定是否属于X的元素。边界域是判断精确与不精确、清晰与不清晰的根据。当BN(X)=时，则称X关于R是可定义的；当BN(X)时，则称X是关于R的粗糙集。
当以论域U中集合X为核心时，能够给出相应的X关于R的下近似，X关于R的上近似和边界域BN(X)。而从整个论域U的角度考虑，又能给出相应的刻画。相对于X而言，U可以用正域和负域来描绘。
正域定义为POSR(X)=，即肯定属于X的元素集合。从形式上看，上近似就是正域和边界域的并集。
负域定义为NEGR(X)=U-，即肯定不属于X的元素集合。
可以看到，模糊性和不确定性在此有了联系，即模糊性是由不确定来表示的。一般地，在给定的近似空间中，并非所有的对象子集都可用给定的知识来表示成概念，这样的子集就认为是粗糙概念。但是，粗糙概念可以通过两个精确概念来粗糙地定义，这就使人们可精确地描述不精确的概念。
2.3 知识约简与知识的依赖性
知识约简与知识的依赖性是粗糙集理论的两个最基本问题。知识约简是研究近似空间中每个等价关系是否都是必要的，以及如何删去不必要的知识，知识约简在信息系统分析与数据挖掘等领域都具有重要的应用意义。知识之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往往是知识约简的重要启发式信息。下面给出有关知识的约简、相对约简以及知识的依赖性的相关定义。
1．知识的约简与核
约简与核是两个最重要的基本概念。直观地，所谓知识的约简是指知识的本质部分，它足以定义所考虑的知识中遇到的所有基本概念，而核是其最重要的部分。
定义 2.6 给定知识库K=(U,R)和U的分类U/R, rR，如果
U/R=U/(R-{r}) (2-8)
则称r为R中冗余的，否则r为R中非冗余的。
这个概念与分类相联系，可以这样理解，R是论域中对象的属性集合，去除冗余属性r后，剩下的属性集R-{r}仍然保持原来的等价关系。
若任意rR，r非冗余，则称族R为独立(independent)。如果R是独立的，PR，则P也是独立的。在用属性集R来表达论域知识时，R独立意味着属性集里的每一个属性都是必不可少的，它可以独立地表达一组知识分类。
定义 2.7 当Q独立，QP且U/Q=U/P，则Q为P的约简(Reduction)，用RED(P)表示。
约简Q是能够与P表达同样知识的最小等价关系集合，是P中的重要部分。虽然Q去除了部分多余的知识，但仍然可以取得与原有的完整知识库一样的分类结果。
定义 2.8 一族等价关系P可能有多个约简，全部约简的交集定义为P的核(Core)，记作CORE(P)。
CORE(P)=RED(P) (2-9)
CORE(P)含有P的全部约简中共同的等价关系，是知识库P中必不可少的重要部分。核的概念有两方面的作用：首先核可以作为所有约简的计算基础，因其包含在全部的约简中，并且其计算是直接的；其次，核可以解释为知识最重要的部分的集合，进行知识的约简时不能够删除它。计算所有约简与计算一个最佳约简都是NP难题[[] 胡可云，陆玉昌，石纯一. 粗糙集理论及其应用进展[J]. 清华大学学报，2001，41(1)：64～68
]。

2．知识的相对约简与相对核
在粗糙集理论的应用中，一个分类相对另一个分类的关系十分重要[[] 石红，沈毅. 关于粗糙集理论及其应用问题的研究[J]. 计算机工程，2003，29(3)：1～4
]，因此需要讨论知识的相对约简和相对核的概念。首先定义相对正域的概念。
定义 2.9 设P和Q是论域U上的等价关系的族集，族集Q的P正域记为POSP(Q)，定义为
(2-10)
族集Q的P正域是论域U的所有那些使用分类U/P所表达的知识中能够正确地分类到U/Q的等价类之中的对象的集合。一个集合X相对于一个等价关系P的正域就是这个集合的下近似；而一个等价关系Q相对于另一个等价关系P的正域的概念是表示分类Q的等价类(一般视为决策类)之中的哪些对象可由分类P的等价类(一般视为条件类)来分类的问题。
定义 2.10 P和Q为U中的等价关系族，当POSp(Q)=POS(P-{r})(Q)时，称rP为P中相对Q冗余的(Q-dispensable)，否则，r为P中相对Q非冗余(Q-indispensable)。
定义 2.11 当P中每个r都为相对Q非冗余时，称P为Q独立(Q-independent)。当S为P的Q独立子族，且POSS(Q)= POSP(Q)时，则族SP称为P的Q约简(Q-Reduct)。
当必须利用整个知识P来划分对象到Q的初等范畴时，知识P为Q独立的。
定义 2.12 P中所有相对Q非冗余的关系族称为P的Q核(Q-Core)，记为COREQ(P)。
COREQ(P)=REDQ(P) (2-11)
其中REDQ(P)为P中所有Q约简的集合。
P的Q核是知识P中最基础的部分，消去它就会减少把对象划入初等范畴Q的能力。知识P的Q约简是P的最小子集，它为知识Q的初等范畴提供了与全部知识P相同的对象分类，往往P有不止一个相对约简。
只有一个Q约简的知识P，从某种意义上说是一种确定性知识，即当使用P的初等范畴划分对象到Q的初等范畴时，只能有一种途径；而在知识P不确定的情况下，一般有多种Q约简，因此知识的不确定性和多种约简是同义语。

3. 知识的依赖性
要进行知识的约简，并从一个给定知识中导出另一知识，必须研究信息系统中知识之间的依赖性关系。
当Q的所有初等范畴可以用P中的某些初等范畴定义时，则知识Q是从知识P中可导的。当Q从知识P中可导时，称Q依赖于P，记为PQ。依赖性可形式化地定义如下：
定义 2.13 令K=(U,R)为一知识库，且P，QR。
(1) 知识Q依赖于知识P，当U/PU/Q，记为PQ；
(2) 知识P和Q是等价的,当且仅当PQ且QP，记为P＝Q，明显地，P＝Q当且仅当U/P=U/Q；当不存在PQ，且不存在QP，P和Q是独立的。
知识的部分依赖性表明知识推导也可以是部分的，即有部分知识Q是可以由P推导的，部分可导性可用知识的正域来定义，为了度量知识的依赖性我们形式化地定义部分可导性。
定义 2.14 令K=(U,R)为一知识库，P，QR，称知识Q以依赖度k(0k1)依赖于知识P，记为PkQ，当且仅当
(2-12)
(1) 若k＝1，称知识Q完全依赖于知识P；
(2) 若0<k<1，称知识Q部分依赖于知识P；
(3) 若k＝0，则称知识Q完全独立于知识P。
上述思想可以通过对象的分类能力解释。准确地说，若k=1，则论域的所有对象都可以通过知识P来分类于U/Q的范畴之中；若0<k<1，则仅仅是论域之中属于正域的对象可通过知识P来分类于知识Q的范畴之中；若k=0，论域中没有对象可以通过知识P来分类于知识Q的范畴。

4. 属性的重要性
在作为粗糙集研究对象的信息系统中，知识具体表现为对象的各个属性，属性的重要性即体现了分类的重要性。在其它理论中，这种重要性可在辅助知识的基础上事先假设，并用“权重”表达。而在粗糙集中，无需使用任何先验信息，即能用数据本身的客观信息来度量属性重要性。
为了找出某属性的重要性，需要从属性集合中去掉该属性，再来考察删除该属性后分类会发生什么变化。若去掉该属性后分类情况改变较大，说明该属性重要性高，反之重要性低。可见，属性的重要性可以用正域来衡量。
定义 2.15 设决策表为S=<U,CD,V,f>，属性子集BC，则相对于决策属性D属性子集B的重要性用以下依赖程度的差值来表示：
(2-13)
上式表示当从条件属性集合C中去掉某些属性子集B后对对象分类时，分类U/D的正域受到怎样的影响。属性重要性还可以用POSC-B(D)和POSC(D)之比的形式来表示。
属性重要性是知识约简研究中的一个关键概念，王国胤已证明约简的信息论描述形式包含了上面所介绍的代数形式，而属性重要性的信息定义也包含了其代数定义[[] 吴明芬. 粗糙集理论的研究现状与前景[J]. 五邑大学学报，2002，16(2)：16～21
]，在定义知识的概率分布之后，从信息熵角度研究属性的重要性，可以在粗糙集框架下定义知识的信息熵、条件熵、互信息熵等概念。将其用于机器学习中度量属性的重要性，属性相对于目标概念信息熵的下降也就是信息不确定性的下降。下面给出用粗糙集描述的信息熵、条件熵、互信息熵的定义。
定义 2.16 设具有决策D的论域U被等价类Ci，i=1,…,Card(VD)划分为，目标概念的个数为Card(VD)，其中VD是决策D的值域。假设U中对象在的各个等效类中随机分布，则包含的信息量为
(2-14)
p(Ci)是U中对象被正确分类到Ci的概率，-logp(Ci)是Ci包含的信息量，对各个类别的信息量加权求和，得到的熵值即为所包含的信息量。
信息熵的物理意义有以下三个方面：一是信息熵表示知识的每一个变量所提供的平均信息量；二是表示知识的平均不确定性；三是表示知识的随机性。
定义 2.17 称属性—值序偶对(a,v)，aA，vVa为一个原子特征。任何原子特征或原子特征的合取被称为一个描述子，全部属性的原子特征的合取被称为一个充分描述子。对于属性BA，不取空值的描述子被称为B-完全描述子。
={xU|fa(x)=v}代表具有原子特征(a,v)的对象的集合。
在原子特征(a,v)条件下量度包含的信息，其条件熵为：
(2-15)
上式中，p(Ci|v)是对象集合属于类Ci的条件概率。则相对于属性a的
条件熵定义如下：
定义 2.18 相对于属性a的条件熵
(2-16)
其中，p(vj)是属性a具有属性值v的概率，Va是a的值域。
条件熵表示在属性a已知情况下，知识仍然存在的平均不确定度。属性相对于目标概念的条件熵的下降也就是信息不确定性的下降。
定义 2.19 若以描述子(a1,)…(am,)来度量包含的信息，则属性集合{a1,…,am}的条件熵可表示为：
(2-17)
其中：
(2-18)
是属于类的联合条件概率。反映了以属性集合{a1,…,am}划分论域U得到的所包含的信息量。较大，说明属性集合{a1,…,am}反映的信息不确定性较高，属性集合包含的重要信息较少；较小则说明属性集合{a1,…,am}反映的信息不确定性较低，属性集合包含重要信息。
定义 2.20 属性集合{a1,…,am}与划分之间的互信息量为：
(2-19)
反映了在属性集合{a1,…,am}划分情况下，对的不确定性的消除程度。若值较大，说明属性集合{a1,…,am}比较重要；反之，若值较小，则属性集合{a1,…,am}相对不太重要。
定义2.20与定义2.15均描述了从决策表中去掉某一属性或属性集合后对决策信息系统不可分辨性的影响，因此可用它们衡量属性的重要性，进而进行属性选择。
2.4 本章小结
在粗糙集理论中，知识被理解成关于论域的各种划分模式。同时把知识看作是具有粒度的，知识的粒度性是造成用已有知识不能精确表示某些概念和对象之间不可分辨的原因。为刻画这种模糊性，粗糙集理论采用两个精确集合——上近似和下近似来逼近待描述的集合。
知识约简和知识的依赖性是粗糙集理论的两个最基本的问题。知识约简研究近似空间中每个等价关系是否都是必要的，以及如何删去不必要的知识。知识之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的属性重要性往往是知识约简的重要启发式信息。

决策信息系统分解约简研究 第三章 决策信息系统分解约简研究
第三章 决策信息系统分解约简研究
从海量数据中挖掘出有用的知识来辅助决策是数据挖掘研究领域的重要课题，由于