（光学专业论文）基于模糊区分矩阵的区间信息系统属性约简.pdf

中文摘要 i 中 文 摘 要 中 文 摘 要 信息系统中的每个属性代表对论域中对象的区分或分类的能力，在属性集中往 往存在冗余的信息，如何找到一个不冗余且保留原属性集的全部区分信息的极小或 最小属性集是信息处理的重要课题。z.pawlak 的粗糙集理论可以完美的处理基于完 备信息系统上的不可分辨关系，对于其他类型的信息系统，粗糙集理论无法直接处 理，人们提出很多方法扩展粗糙集理论到其他类型的信息系统上。 区间信息系统的存在是由于在实际的问题中，信息系统的属性值往往无法精确 测定，而是落在某个区间上。对于区间信息系统，已经有包括基于区间包含的偏序 关系，区间相似度关系引入阈值参数转化为相容关系等处理方法。前者的适用范围 较小，因为区间值往往不是互相包含的。后者的区间量之间的相似性是基于区间的 重叠区域大小定义的。 本文首先分析区间量的测量过程， 根据误差理论定义了一种能够合理反映两个区间 量相似程度的相似关系。定义区间量的相似性度量，将属性集映射到论域笛卡尔积 上的一个模糊集簇，建立了基于区分度矩阵的属性约简理论，讨论了其特点，提出 了将区分度离散化的观点，探讨了它对于系统鲁棒性的意义。最后设计了基于属性 重要度的约简算法并通过实例验证了其有效性。 关键词：区间值信息系统；相似性度量；区分度；相似度；模糊区分矩阵；属性约 简；区分度离散化；约简鲁棒性；值约简； abstract ii abstract in an information system, every attribute represent certain ability to distinguish or classify the objects of universe. the attribute set often include some redundant information, so it has become an important topic to find out a minimal attribute set that can keep the complete sorting information. z. pawlak proposed rough sets theory which can perfectly deal with the complete information system based on equivalence relation. other information systems cant be solved directly with rough sets, so a lot of extent rough set theories are proposed to solve these incomplete information systems. in practical situations, we can hardly measure the value of object properties precisely. instead, we can tell the precise values are most probably in an interval, so it is necessary to do some research on interval information systems. existing methods include partial order relation rough set model, compatibility relation rough sets model and so on. the former cant be used widely because intervals seldom include each other. in the latter model, the similarity measurement is defined based on the overlapping of intervals. in this paper, we proposes a new method to measure the similarity of two interval values, this measurement is based on physical measuring and error processing theory, so it is more reasonable than original methods. based on this, we introduce a new method of attributes reduction with fuzzy discernibility matrix. we also discuss a discretization argument of the similarity measurement function, which helps to improve the system robustness. key words: interval-valued information; similarity measurement; fuzzy discernibility matrix; discretization argument; attribute reduction; reduction robustness; attribute value reduction; 承诺书 45 承承 诺诺 书书 本人郑重声明：所呈交的学位论文，是在导师指导下独立完成的， 学位论文的知识产权属于山西大学。如果今后以其他单位名义发表与在 读期间学位论文相关的内容，将承担法律责任。除文中已经注明引用的 文献资料外，本学位论文不包括任何其他个人或集体已经发表或撰写过 的成果。 作者签名： 20 年 月 日 学位论文使用授权声明 46 学位论文使用授权声明学位论文使用授权声明 本人完全了解山西大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文 被查阅和借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。 同意山西大学可以用不同方式在不同媒体上发表、传播论文的全部或部分 内容。 保密的学位论文在解密后遵守此协议。 作者签名： 导师签名： 20 年 月 日 引言 1 第一章 引言 第一章 引言 1.1 课题研究的背景、现状和目标 1.1 课题研究的背景、现状和目标 随着网络和数据库等信息技术的发展，信息的采集、存储和管理水平有了非常大 的提高，由此而产生的数据呈现指数式的增长。以往传统的人手工处理的方式已经 不可能满足需求，因此人们开始研究从海量的数据中提取对人们有用的知识和信息， 由此产生了一门新的科学智能信息处理1,2,3。 它是一门要从数据集中识别出有效 的、新颖的、潜在有用的以及最终可理解的模式的非平凡过程的科学 4。 随着人们对智能信息处理技术的不断研究，它取得了长足的发展。对于各种不同 类型的信息系统，各自发展了很多适合于处理的理论方法。这些方法包括粗糙集理 论5,6,7,8、模糊集合论9,10,11、证据理论12,13和概率理论14,15,16、相互补充，没有哪一 种方法可以取代别的方法。粗糙集理论的特点是无须提供处理数据以外的任何先验 信息，是一种有效的处理模糊和不确定系统的数学工具17,18,19 。 本文要研究的区间信息系统20,21的一种，它的特点是各属性下的值取区间值。对 于区间信息系统，现有的处理方法都是将区间信息系统进行处理，将其转化为确定 值信息进行处理。已有的处理方法包括基于区间包含的偏序关系，区间相似度关系 引入阈值参数转化为相容关系22法。前者的适用范围较小，因为区间值往往不是互 相包含的。后者的区间量之间的相似性是基于区间的重叠区域大小定义的。这些研 究方法，都是加入许多假设，引入相关的近似机制，对区间信息系统进行简化为粗 糙集理论可以处理的问题。 首先， 本文认为区间信息系统并非一种能够完全表达所表示的系统所有信息的信 息系统。智能信息处理本来就是一个从实践需求中发展而来的科学，所以对于实际 的区间信息系统的获取和分析是十分必要的，脱离了实际信息系统测量的数据分析 意义不大。信息系统自所以出现区间性，现在认为是有两种情况。一种观点认为， 有些属性值本身就是区间值，这种情况在现实中是广泛存在的，对它的研究有很重 要的意义，但是不在本文的研究范围。本文主要研究另外一种传统的观点，它认为 信息系统的属性值自所以出现区间值是因为实际测量的时候，属性值往往无法精确 基于模糊区分矩阵的区间信息系统属性约简 2 测定，而出现只能去确定其值为某个区间内，但是实际的准确值是存在的，我们只 能以我们的测量精度确定在一个概率下该真实值在这个区间以内23。这个真实值我 们是无法根据给定的区间信息系统确定的，否则区间信息系统就变成确定值的信息 系统了。尽管如此，我们任然可以根据实际的系统，得到一些关于真实值的信息， 这些信息能够帮助我们进行信息处理。 其次，作为信息系统的一种形式，区间信息系统的处理，现有的方法是将其经过 近似机制，转化为已经有比较成熟理论的完备信息系统，然后利用粗糙集理论进行 处理24。如假设区间信息系统的属性值满足包含关系而建立起来的偏序关系处理方 法25，这种方法在理论上没有什么缺陷，但是和实际相差甚远，因为满足区间包含 的实际系统是非常少的。再如基于变精度相容关系的区间信息系统粗糙集处理方法， 首先定义了区间量的相似性，得到一个论域笛卡尔积上的模糊关系，然后用一个统 一的阈值将模糊关系截为一个相容关系，然后利用粗糙集下的区分矩阵方法处理。 这种方法有一定的合理性，但是本文这里考虑两点。第一，对于两个区间相似性的 定义，因为对于两个区间量，不可能像确定值那样进行直接的等价分类，所以这个 相似性定义似乎是要处理区间信息系统的必然选择。正因为如此，它的定义的合理 性才更加的突出，本文分析了现有的相似性定义的特点和不足，试图从区间信息系 统属性值的区间性和测量机制角度，定义一种更加合理的区间相似性度量。该定义 在弥补了现有的相似性定义的不足之外，还将其与信息系统的获得过程联系起来， 使得后续的信息处理结果更加有实际意义，即使在不能提供先验的信息系统活的过 程的知识，采取合理的默认值，这种方法也完全能够进行合理的数据分析。 再次，在对于完备信息系统的处理上，经典粗糙集已经非常成熟，并且在完成属 性的约简之后，经典粗糙集理论还对完备信息系统进行有效的属性值约简26,27,28,29。 变精度相容关系模型无法完成对区间信息系统的有效的属性值约简，原因在于基于 经典粗糙集理论的区分矩阵方法的属性约简，相容关系完全可以适用，然而经典粗 糙集的值约简算法，是严格基于等价关系分类的，相容关系和相容类不能使用其方 法。本文认为，在定义了区间量相似性度量之后，区间信息系统就被有效的转化为 一个基于论域笛卡尔积上的模糊关系，我们在分析了这个度量的特性和信息系统属 性约简的目标和本质之后，提出了一种基于模糊集理论的处理方法。在此基础上， 本文的方法中属性值的约简方法自然的呈现。 另外，本文在分析相似性度量定义模型的时候，借鉴了证据理论的相关思想，利 引言 3 用了一些概率论的知识，在属性约简和属性值约简的方法上，借鉴了一些经典粗糙 集的思想；具体的处理方法，则主要使用了模糊集理论。因而本文试图结合概率论、 证据理论、 粗糙集和模糊集合论30,31,32， 对于区间信息系统建立一种特别的处理方法。 对于文中提到的各个方面，都有未考虑完全之处，需要进一步深入的研究。 1.2 本文工作及结构安排 1.2 本文工作及结构安排 本文的后续分为五个章节。第二章介绍了需要用到的预备知识，包括区间信息系 统的定义、粗糙集与知识约简、模糊集合论和误差理论。第三章分别具体分析了现 有的主要的区间信息系统处理方法，基于变精度极大相容类的区间信息系统属性约 简。第四章阐述了本文要建立的基于模糊区分矩阵的信息系统属性约简方法，首先 建立了新的区间量相似性度量方法；引入模糊区分矩阵的概念；在模糊区分矩阵的 基础上建立了属性约简的理论；最后讨论了相似性度量函数的离散化和其对于系统 约简鲁棒性的作用。第五章说明了区间信息系统在基于模糊区分矩阵属性约简之后， 对约简结果进行属性值约简的方法和步骤。第六章通过一些区间信息系统实例验证 了该方法的有效性。第七章是对全文的总结和展望。 基于模糊区分矩阵的区间信息系统属性约简 4 第二章 预备知识 第二章 预备知识 2.1 区间信息系统区间信息系统 定义 2.1定义 2.133,34,35（信息系统）称有序四元组( , , ,)iu a v f=为一个信息系统，其中： 12 ,., n ux xx=是一个由所研究对象组成的非空有限集合，也称为论域。 12 ,., n aa aa=是所有属性的集合，称为属性集。 12 ,., n vv vv=为所有属性取值的值域的并集。 :f uav为一个映射函数，为每个属性对象对赋予一个函数值。 信息系统是用来一种知识表达系统，类似的知识表达系统还有决策表，本文只 研究信息系统。 定义 2.2定义 2.2 （区间信息系统）36设信息系统( , , ,)iu a v f=满足条件： 12 ,., n vv vv=，属性值域中元素均为区间量，即( )a x表示对象x在属性a下的 取值，若( )a x为一闭定义定义区间，即( ),( ) lr a x ax，则( , , ,)iu a v f=为一个间值信息系 统。 2.2 粗糙集与知识约简粗糙集与知识约简 定义 2.3 定义 2.3 （序偶）序偶就是由两个元素 12 ,a a 构成的二元有序组 12 (,)a a。其中 1 a 为序 偶的第一分量， 2 a 为序偶的第二分量。 定义 2.4定义 2.4 （集合的笛卡尔积）设集合a和b，称( , )|,a ba baa bb=为集合a 和b的笛卡尔积。 定 义 2.5定 义 2.5 （ 二 元 关 系 ） 设 集 合a和b， 称a和b的 笛 卡 尔 积 ( , )|,a ba baa bb=的任何一个子集为从集合a到b的一个二元关系r，记为 arb。 我们称从集合a到a的关系为集合a上的关系。 定义 2.6定义 2.6 （等价关系）如果集合a上的关系r满足条件： 预备知识 5 （1）自反性,xa xrx （2）对称性,x ya xryyrx （3）传递性, ,x y za xryyrzxrz 且 则称r为集合a上的等价关系 定义 2.7定义 2.7 （等价类）设r是论域u上的等价关系，xu ，定义： | r xy yrx= 为对象x关于关系r的等价类。 显然，若干等价类把论域划分成几个部分，称为论域的一个划分。 定义 2.8定义 2.8 （知识库）称由一个论域u和u上的一簇等价关系s组成的二元组 ( , )ku s=是u上的一个知识库 论域上的一个等价关系就对应着一个对论域的划分，知识库就是在论域上的一 系列的等价关系构成的整体。在前一节定义的信息系统中，对于完备信息系统，每 个属性对象对都取确定的值，因而可以根据这些取值确定一个对应的等价关系 和划分。粗糙集认为，知识就是对论域中对象的分类能力，本文后面针对区间信息 系统的特殊情况，对这一概念进行了扩展，我们认为在定义了相似性度量的情况下， 区间信息系统的知识是对论域中对象的区分能力。之所以由分类能力变为区分能力， 是由于在区间信息系统中，属性值对应的是区间值，区间值之间不存在先验的等价 关系，因此没有直接的分类能力，当然经过适当的处理，是可以实现近似分类的。 定义 2.9定义 2.9 （不可分辨关系）一个论域u和u上的一簇等价关系s，ps是所有等 价关系集合的一个子集，则称p中所有等价关系的交集为p上的不可分辨关系，记 为( )ind p 容易证明： () , ind pr r p xuxx = （2.1） 不难理解，一个等价关系簇子集的不可分辨关系表达了该子集中所有等价关系 对论域分类能力的总和。对于本文后续讨论的区间信息系统，在定义了相似性度量 而引入模糊区分矩阵以后，信息系统的每个属性不再对应于一个论域上的等价关系， 而是对应一个论域上的模糊关系，即论域笛卡尔积上的一个模糊集合。在此基础上， 本文也对等价关系的不可分辨关系进行了概念扩展，使其适用与模糊关系的情况， 基于模糊区分矩阵的区间信息系统属性约简 6 它对应模糊区分矩阵中属性区分模糊集合的并集。 定义 2.10定义 2.10 （集合的下近似和上近似）给定一个知识库( , )ku s=，论域u中的子集 xu和u上的一个关系r。定义x关于知识r的： 上近似为： () |()( ) r r xxxuxx = （2.2） 下近似为： () |()( ) r r xxxuxx = （2.3） 称()()r xr x 为x的r边界域， 表示的是在知识r所能确定的分类下， 不能确 定是否属于集合x的元素的集合，记为() r bnx；()r x 称为x的r正域，表示在关 系r所 能 确 定 的 分 类 下 ， 确 定 必 然 属 于 集 合x的 元 素 的 集 合 ， 记 为 () r posx;()ur x 为x的r负域，表示在关系r所能确定的分类下，确定必然不属 于集合x的元素的集合，记为() r negx。 定义 2.11定义 2.11 （r-粗糙集和精确集） 给定一个知识库( , )ku s=， 论域u中的子集xu 和u上的一个关系r。若()()r xr x =，则称集合x为 r-精确集，否则称集合x为 r-粗糙集。 定义 2.12定义 2.12 （知识独立性）给定一个知识库( , )ku s=， ,psrp 若： ( )( )ind pind pr= （2.4） 则称知识r为p中不必要的，否则称知识r为( )core p中必要的。如果p中的每一 个知识元素都是必要的，则称它是独立的，否则称它是依赖的或者不独立的。p中 所有必要的知识的集合称为知识库p的核，记为( )core p。 定义 2.13定义 2.13 （知识的约简）给定一个知识库( , )ku s=， ,psgp若满足： （1）g是独立的 （2）( )( )ind gind p= 则称 23 1 , /() r rrr uind srx = 是p的一个约简，记为( )gred p，其中( )red p 为p的所有约简组成的集合。不难经过分析知道，每个知识库的约简对论域中对象 预备知识 7 的分类能力是相同的。一个知识库的约简一般不是唯一的，可能有许多不同的知识 约简。 为了更形象的理解上述概念， 我们给出一个简单的知识库， 分析对应的等价关系、 等价类、不可分辨关系及知识库的核和所有约简。我们给出的是一个完备信息系统， 如下： 表 2.1 一个完备信息系统实例 /r u 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 1 r 1 2 3 1 1 4 4 2 2 r 1 3 1 3 1 2 3 3 3 r 1 3 4 4 1 2 3 3 信息系统的每一个属性， 按照论域对象的取值将论域进行划分， 对应一个等价关 系。在该信息系统中论域 128 ,.,ux xx=，知识库 123 ,sr r r=，他们对应的等价 类为： 114528367 / , ,urx xxxxxx x=（2.5） 315627834 / , , ,urx xxxxxx x= 15283467 /( ) , , , , uind sx xxxxxxx= 因为： 23 1 , 15362784 /() , , /( ) r rr r uind srx x xxxx x xx uind s = = 所以知识 1 r在知识库s中是必要的。 因为： 213562478 / , ,urx x xxxxxx= 基于模糊区分矩阵的区间信息系统属性约简 8 13 2 , 15362847 /() , , , /( ) r rr r uind srx x xxxxxx x uind s = = = （2.6） 所以知识 2 r在知识库s中是不必要的。 因为： 12 3 , 15362847 /() , , , /( ) r rr r uind srx x xxxxxx x uind s = = = （2.7） 所以知识 32 r在知识库s中是不必要的。 因此，知识库s的核为: 1 ( )core sr= 又因为： 12 12 , 15362847 /(,) , , , /( ) r rr r uindr rx x xxxxxx x uind s = = = （2.8） 所以 12 ,r r是知识库 123 ,sr r r=的一个约简。 13 13 , 15362847 /(,) , , , /( ) r rr r uindr rx x xxxxxx x uind s = = = （2.9） 所以 13 ,r r是知识库 123 ,sr r r=的一个约简。 从上述讨论不难理解， 知识库 123 ,sr r r=和他的两个约简 12 ,r r， 13 ,r r具有对 论域的完全的相同的分类能力，即他们对知识的表达能力是相同的。而知识库中存 在冗余的信息，它的约简结果更加简明，实用性更强，所以知识约简是智能信息处 理的非常重要的课题。 2.3 模糊集模糊集 在经典的集合中，论域上的元素是否属于某个集合是“非此即彼”的关系。若 用元素属于集合的隶属度函数来说明，一般刻画经典集合的隶属度函数取值只有 0 预备知识 9 或者 1，0 代表元素不属于该集合，1 代表元素属于该集合。然而在现实生活中，人 们发现很多时候有些概念不是非此即彼的关系。比如要判断一个人是否属于高个子 人的集合，就没有一个统一而确定的标准，这时候有一个连续的隶属度函数显得更 加合理。1965 年，美国计算机与控制论专家 l.a.zadeh 提出了模糊集理论37，迄今 为止，模糊集已经成为人工智能技术的一个重要工具，在各个领域取得了很大的成 功。但是模糊集有着它固有的缺陷，隶属度的确定往往较强的依赖于人们的主观认 识，没有发现也不可能存在一种通用的确定模糊程度的方法。 定 义 2.14 定 义 2.14 38,39,40 （ 模 糊 集 的 概 念 ） 给 定 论 域,uuu ， 以 映 射 函 数 :0,1,( ) aa uuu?为隶属度函数确定的一个集合， 称为论域u上的一个模糊子 集 a。 模糊集合的隶属度函数值域为0,1，如果取为0,1，即论域中元素隶属于集合 的隶属度为非 0 即 1 的时候，模糊集合退化为经典集合。可以认为，经典集合是隶 属度只取值域中两个特定值的特殊情况，即模糊集是经典集合的泛化，经典集合是 模糊集的特例，所以模糊集合的计算和性质可以用于经典集合。 定义 2.15定义 2.15 （模糊集并和交运算）设 a和 b分别为论域u上的模糊子集， uu 若 有 ( )( ) ab uu成立，则称 a包含 b，或者 b包含于 a，记为 ab。 定义 2.16定义 2.16 （模糊集并和交运算） 设 a和 b分别为论域u上的模糊子集， 定义 a和 b 的并 ab和交 ab分别为： ( )max( ),( ) abab uuu= ( )min( ),( ) a bab uuu= （2.10） 本文的后续章节中， 通过定义相似性度量引入了模糊集， 制定了相应的模糊程度 的标准。在如何定义这个模糊标准的时候，本文希望尽可能的减小人的主观认识， 所以是在参考了物理测量过程中固有存在的测量规律和误差处理理论来定义的，在 一定程度是比较客观的。 2.4 误差理论误差理论 现实世界中，所有的有意义的数据，都不可能凭空得到，都是物理测量直接或者 间接测量得到的。测量分为直接测量和间接测量，直接测量是把一个量与同类量直 接进行比较以确定待测量的量值。一般基本量的测量都属于此类，如用米尺测量物 基于模糊区分矩阵的区间信息系统属性约简 10 体的长度，用天平称铜块的质量，用秒表测量单摆的周期等。但是在实际生活中， 能够直接测量的量是比较少的，绝大多数物理量要经过测量基本量，然后经过计算 得到。 测量都是在一定的温度， 湿度的环境下， 用一定精度的测量仪器进行测量得到的， 测量的到的值分为离散化的值和连续分布的值。在任何的测量中，测量观察得到的 结果n和它客观存在的待测量的真实值 n之间会有差异，称测量的结果与真实值之 间的差异 nnn=为误差41。产生测量误差的原因有：环境误差、人为误差、方 法误差、仪器误差等。误差是不可避免的，真实值是个理想的概念，任何测量都不 可能完全取得真实值，但是误差也是可以分析的。通过分析误差，我们可以将误差 控制可以接受的范围内。 根据误差的性质，在分析误差时，我们可以把误差分为系统误差和随机误差。系 统误差是由于固定不变或者按照规律变化的因素而造成的误差，这些误差一般是可 以掌握的，引起系统误差的因素包括： （1）测量装置和仪器的因素，如由于仪器本身问题（如尺的刻度偏大，表盘不均匀 等）而产生的系统误差，或者由于仪器安装和调整不当导致测量值固定的偏大 或者偏小。 （2）测量方法的因素产生的误差，如由于间接测量所采用的测量计算公式本身在做 近似的时候就存在偏大或者偏小的问题，又如测量过程中忽略了一些应该考虑 的因素而造成结果与真实值之间的偏差。 （3）环境方面因素产生的误差，如由于测量环境的温度、湿度和气压等环境因素和 标准测量要求的环境条件有差异而造成的误差。 （4）人为因素，由于测量者的操作不规范或者测量习惯如读表盘的刻度习惯性的偏 大或者偏小而造成的误差。 由于系统误差的上述特点， 系统误差的发现是重点。 常见的可以利用理论分析法、 数据分析法、实验验对比法等方法发现系统误差，然后针对产生系统误差的原因进 行处理，采用引入修正项，改变实验方法，多人合作重复实验，更换实验仪器等方 法，减小系统误差到能够接受的范围内。 随机误差是由于感官灵敏度、 仪器精确度限制和在测量时候无法控制的随机因素 导致的测量误差，因而这样产生的误差是大小无定值的，它符合一下规律： 预备知识 11 （1）单峰性，测量值与真实值相差越小，其出现的可能性越大，与真实值相差很大 的，出现的可能性很小。 （2）对称性，测量值与真实值相比，偏大和偏小的可能性是相等的。 （3）有界性，在一定的测量条件下，误差不会超过某一绝对值。 （4）补偿性，随机误差算数平均值随着测量次数的增加越来越小。 随机误差用误差范围来表示，它可由误差理论估算出来，其表示方法有标准误 差、平均误差和极限误差等，它们的区别仅在于概率大小的不同。人们生活的长期 实践中发现，在许多多次的无差别测量中，随机误差是呈现正态分布的，这也是本 文后续分析和处理区间量数据的基础。 基于模糊区分矩阵的区间信息系统属性约简 12 第三章 区间信息系统属性约简算法分析 第三章 区间信息系统属性约简算法分析 本文主要介绍对于区间信息系统的属性约简现行的算法中比较常见的一种， 基于 极大相容类的区间信息系统属性约简算法。我们在阐述其算法理论和方法的同时， 分析了其特点，针对这些特点提出了一些改进，在这些改进的基础上构成了本文将 阐述的基于模糊区分矩阵的区间信息系统的属性约简算法。关于该算法的主要内容， 将在下一章中阐述。 3.1 基于极大相容类的区间信息系统属性约简算法 定义 3.1 【31】 3.1 基于极大相容类的区间信息系统属性约简算法 定义 3.1 【31】 （区间相交相似性度量） 设(,)u a是一个区间信息系统， 011 ,. n ux xx = 为对象的非空有限集， 0,11 ,. m aa aa =为属性的非空有限集，对,aaxu ， ( )a x表示对象x在属性a下的取值， 若( )a x为一闭区间， 即( ),( ) lr a x ax， 则称(,)u a 为 区 间 值 信 息 系 统 。 设(,)u a为 区 间 值 信 息 系 统 ， ,( )( ),( ) lr x yu aa a xa x ax = ，( )( ),( ) lr a yay ay= , ( ),( )( ),( ) ( ),( )( ),( ) lrlr a x y lrlr a x axa y ay s a x axa y ay = （3.1） 称为( )a x ， ( )a y的相交相似度量，其中|.|表示闭区间的长度大小。 由相交相似性的定义式不难证明，相似性度量满足: （1）对称性： , , aa x yy x x yu aass= （2）归一性： , ,0,1 a x y x yu aas （3）自反性： , ,0,1 a x x xu aas 该式是两个区间的相交部分与它们并集区间大小的比值， 可以一定程度上反映两 个区间的相似程度， 比值越大， 说明他们相似性越高。 然而如果仅考虑( )( )a xa y的 情况，当( )a x与( )a y的区间中心值越接近，两者的相似程度应该越大，然而在上面 的定义中没能反映出来。如下表格中的( )0,10a x = ， ( )a y长度为 1，后者区间长度 大小小于前者，当( )a y的区间中心值移动时，它们的相似度应该在它们的中心值重 合的时候达到峰值，往两边相似度会逐渐变小。所以在移动过程中相似度本应该有 所变化反映，但是这个定义中，它们的相似度始终保持不变。 区间信息系统属性约简算法分析 13 设( )0,10a x = 表 3.1 区间值与相似度关系 ( )a y 0,1 1,2 2,3 3,4 4,55,66,77,8 8,9 9,10 , a x y s 0.10 0.10 0.10 0.10 0.10 0.10 0.10 0.10 0.10 0.10 定 义 3.2定 义 3.2 （ 变 精 度 相 容 关 系 ） 设(,)u a是 一 个 信 息 系 统 ， 对 于 ,(0,1x yu ba，定义变精度相容关系： , ( ,)|, k bijijki j rx xxu xuab s = （3.2） 即论域中相对知识库b中所有属性相似性都大于给定阈值的对象序偶组成的集 合。变精度相容关系，满足： （1）自反性：,(0,1,( , ) b xubax xr （2）对称性：,(0,1,( , )( , ) bb x yuba x yry xr 定义 3.3定义 3.3（变精度相容类）设(,)u a是一个信息系统，对于,(0,1 i xu ba， 定义变精度相容类： ( )|,( ,) bijjijb rxxxux xr = (3.3) 为 i x在相似度阈值下关于知识库b的变精度相容类。当ba=时，称为 i x在阈值 下的极大相容类。 定 义 3.3定 义 3.3 （ 区 分 矩 阵 和 区 分 函 数 ） 设(,)u a是 一 个 信 息 系 统 ， 对 于 ,(0,1 ij x xu ba，记 , | i jki j daa s =， (4.21) 即区间信息系统的核等于该区间信息系统的区分矩阵的所有行中，存在唯一的 最小值对应的列属性的集合。 证明：当某个属性对应区分矩阵某一行的唯一的最小值时，去掉该属性，则该 行对应的两个对象的区分能力就会减小，因而这个属性是必要的。对于所有行都必 要的属性集合就组成了属性集的核。 定义 4.10定义 4.10（属性重要度） 设(,)u a为区间值信息系统，aa ，定义： , ( , ) ( ) | a x y x yu u d sig a uu = (4.22) 为a的属性重要度。( )sig a反映了属性a对论域中对象的区分能力， ( )0,1sig a ，( )sig a越大，属性a对论域中对象的区分能力越强，反之越弱。 基于区分矩阵的区间信息系统属性重要度启发约简算法： 输入：区间信息系统(,)u a 输出：区间信息系统的一个近似约简 step 1 建立相似性矩阵 k m m step 2 求属性集a的核c step 3 求所有属性的重要度 step 4 求属性约简 （1）bc= （2）若( )( )up bup a=则算法结束，输出b，即为所求约简，否则转向（3） 基于模糊区分矩阵的区间信息系统属性约简 27 （3）求出属性集ab中属性重要度最大的属性，添加到b中，转向（2） 基于属性重要度的启发式算法， 得到的是区间信息系统的一个近似约简， 得到的 约简结果是概然的取极小数目属性的集合，它是在充分的降低约简的算法复杂度的 情况下的一个折衷算法。另外，该方法得到的仅仅是一个近似约简，不能得到信息 系统的全部约简。理想的属性约简算法，应该是在较小的算法复杂度情况下，直接 得到系统的最小约简属性集合。然而相关研究已经证明，求信息系统的最小属性约 简是一个 np 问题， 求信息系统的最小属性约简的复杂度和求信息系统的全部属性约 简的复杂度是相同的。在对约简结果要求较高的场合，上面的基于属性重要度的启 发式算法不能适用，需要研究新的约简算法。 4.3.2 基于模糊区分矩阵的求区间信息系统极小属性约简算法基于模糊区分矩阵的求区间信息系统极小属性约简算法 基于模糊区分矩阵的区间信息系统极小属性约简算法： 输入：区间信息系统(,)u a 输出：区间信息系统的一个约简 step 1 建立区间信息系统的区分矩阵 k m m step 2 求系统属性集a的核属性集c step 3 求所有属性的重要度 step 4 求属性约简 （1）ba= ，e ac=，置e中所有属性为未标记状态。 （2）循环： 1.若e中还存在未标记的属性，则从e中取一个属性重要度最小的属性， 转向，否则转向（3） 2.若( )( )up ceup a+，标记，返回，否则转向。 3. ee=，取消b中所有属性的标记，返回 （3）bce=+即为区间信息系统的一个极小属性约简。 算法的思想是讲属性分为核属性和非核属性两部分，然后从非核属性中剔除一 个属性，看看剩下的核属性与非核属性的并是否保留全部的区分信息；如果仍然能 保留全部的区分信息，则可以讲该属性从非核属性中剔除；这个过程是按照属性重 要度从小到大的顺序选取属性的，因为属性重要度大的属性，冗余的可能性较小， 反之，属性重要度小的属性，冗余的可能性更大，所有首先考虑剔除。每次剔除一 个属性之后，这个过程必须重新开始，再选取那些属性重要度最小的属性考虑剔除。 基于模糊区分矩阵的区间信息系统属性约简 28 不难证明，该算法法得到的结果，可以确定是信息系统的一个极小属性约简，不存 在冗余的属性；又因为是按照属性重要度的顺序选取属性进行剔除的，所有得到的 约简结果是概然下数目较小的，所以它是一个极小的近似最小的属性约简。该方法 得到的约简结果更加精确，但是同时算法复杂度提高了很多，约简结果精度和约简 算法的复杂度是此消彼长的关系。 基于模糊区分矩阵的区间信息系统处理方法， 对于求信息系统的最小约简， 本文 没有给出有效的算法。求出所有可能的属性组合，结合属性重要度来求解最小约简 集会遇到组合爆炸的问题，在对实际的系统的分析时意义不打，我们相信在可以接 受复杂度范围内的最小约简算法是存在的，这有待进一步的研究。 4.4 区分度离散化 4.4 区分度离散化 基于区分矩阵的属性约简方法， 依赖于集对的区分度最大项， 因为区分度量函数 是一个复杂的实数定义式，度量值几乎不可能相等。即使对于差距非常小的两个度 量，也有大小之分，所以这种约简方法会对数据项非常敏感，数据项非常小的改动 都可能导致约简结果的改变。本文的解决方法是在构造区分矩阵的时候，对区分度 量函数做一定处理。考虑我们自然语言中，也会用“完全不同” ， “很不相同” ， “有 点类似” ， “很相似” ， “几乎一样” ， “完全一样”等词汇来形容两个事物的相似程度。 我们可以用阶梯性函数将区分度离散化，具体的阶梯性函数可以根据实际的数据选 择。这样处理过程更直观接近人的直觉，还得到了一个可以控制约简精度的方法， 同时使得该方法具有鲁棒性。称将区分度离散化的参数为区分函数离散化参数，记 为。在此离散化参数下，定义一个离散化函数： ( )( / 1)f xx=+ (4.23) 其中是离散化参数，一般取(0,1， x为取整函数，为不大于x的最大整 数值。离散化参数是一个有阶梯性质的函数，它将相似性度量化为一些分立的值。 离散化参数的选取要根据实际的区间信息系统实际情况而定，如果取的过小，则会 将区分度离散化的过细，而导致离散化函数不起作用而失去意义；如果取的过大， 则会使得在离散化的过程中伴随着信息的严重丢失，从而使离散后的信息系统与原 来的信息系统相比失真严重，会使得约简的结果没有实际意义。实际的约简过程中， 我们可以取几个离散化参数分别进行处理，然后比较约简结果。在刚好使得约简结 果发生变化的离散化参数处取值是比较合适的。 基于模糊区分矩阵的区间信息系统属性约简 29 当然，本文采用引入离散化参数和离散化函数对相似性在 0 至 1 范围内做 处理， 但是对于一些具有独特特征的信息系统，十分有必要建立其特殊的离散化 函数形式。这样的离散化函数应该是对相似度分布密集的区间点附近，做分度值较 小的离散化；而对于相似性分布比较稀疏的区间点附近，做分度值较大的离散化。 对于更合理的离散化函数很离散化参数的选取，需要进一步的研究14。 基于模糊区分矩阵的区间信息系统属性约简 30 第五章 基于模糊区分矩阵的区间信息系统属性值约简 第五章 基于模糊区分矩阵的区间信息系统属性值约简 信息系统中知识的简化通常包括属性约简和属性值约简， 在上一章介绍的基于模 糊区分矩阵的区间信息系统属性约简基础上，可以进行有效的属性值约简。信息系 统的值约简就是保持信息系统对论域中对象的分类或者区分能力不变的一个极小知 识范畴集的值域42,43,44。 具体结合到基于模糊区分矩阵的区间信息系统约简方法， 得到的约简是使得论域 中任何两个对象的区分度取得最大值的极小属性集合。 定义 5.1 定义 5.1 （区间信息系统的信息粒）给定一个区间信息系统( , ,)isu c v f=，其中 论域 12 ( ,.,) n ux xx=，属性集 12 (,.,) m ca aa=，称一个对象、一个属性和对应的对 象的属性值组成的一个三元组( ,( ) ijji x afx为区间信息系统的一个信息粒， 一个区间 信息系统是由很多的信息粒构成的。 有了信息粒的概念， 我们可以分析信息粒的对论域中对象区分能力的共享和信息 粒的冗余性。对于一个区间信息系统，我们首先用前一章的基于模糊区分矩阵方法， 得到区间信息系统的一个属性约简。由上一章分析可知，得到的约简是使得论域中 任何两个对象的区分度取得最大值的极小属性集合。所以在约简的属性集中每个属 性都至少提供论域中某一对对象的最大区分度，而这个最大区分度是约简集中其他 的属性不能提供的。考虑一个约简属性集对应的约简后的区间信息系统，如果信息 系统的某一个信息粒在其所在属性下，与论域中每个对象的区分度都不是约简信息 系统的最大区分值，则这个信息粒实际上对论域中所有的对象的区分能力都是没有 贡献的，换句话说，它是冗余的。由此我们得到一个该区间信息系统的值约简。 定义