完不备信息系统中基于不可区分度的知识约简算法的程序设计与实现大学论文.doc

山西大学论文编号：论文题目不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现姓名院系计算机与信息技术学院专业计算机科学与技术学习年限2005年9月至2009年7月指导教师学位级别学士2009年5月23日不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现学生姓名：指导教师：内容提要由于不完备信息系统（含有缺省数据或不精确数据）普遍存在，近年来，对不完备信息系统的研究已经引起了人们的广泛注意。但到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究还集中在理论方面，缺乏实际成型、有效的应用程序或软件。本课题完成了不完备信息表中基于不可区分度的知识约简算法和不完备决策表中基于不可区分度的相对约简算法的程序设计与实现。本程序设计可作为该算法的辅助工具，具有实际意义。关键词不完备信息系统，不可区分度，重要性，（相对）核，（相对）约简1引言粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法，该理论已被广泛应用于知识获取、专家系统、决策分析和决策支持等各种应用领域。知识约简是粗糙集理论处理信息系统的重要手段。现实生活中存在着大量的不完备信息系统（含有缺省值或不精确数据），因此不完备信息系统中的知识约简算法就具有重要的实际意义。文[13]基于不完备信息系统提出了信息系统的可区分度和不可区分度的概念，给出了它们的重要性质，并建立了二者之间的关系，并且证实了不完备信息系统的不可区分度和可区分度可退化为完备信息系统的知识粒度与信息熵。文[9]在文[13]研究的基础上提出了一种基于不完备信息系统的知识获取方法，该算法将含有缺省值的不完备信息系统的知识约简方法与多值信息系统的知识约简统一起来，最终能得到不完备信息表的约简和不完备决策表的相对约简。到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究已经有了大量的理论研究，但是还缺少实现它的软件工具，这是这方面的研究方向。2基本原理2.1基本概念2.1.1不完备信息系统一个信息系统是一个二元组,其中（1）是对象的非空有限集合；（2）是属性的非空有限集合；（3）对，有一个映射，，其中是的幂集，表示空集，每一个属性集决定一个二元不可区分关系，即易证,是集合上的一个等价关系。关系，，构成了的一个划分，用表示[13]。2.1.2相容类令，定义相容关系（满足自反性和对称性）如下：用表示分类，即为由相容关系决定的最大相容类集合。2.1.3不可区分度文[13]基于不完备信息系统（含有缺省数据或不精确数据）提出了信息系统的不可区分度和可区分度的概念，给出了它们的重要性质，并建立了二者之间的关系。设是一个不完备信息系统，。则信息系统关于的不可区分度定义为：若，则可取得最小值。若，且对有，则可取得最大值。不可区分度和可区分度的关系为+=1。其中定义为：表示决策属性集的条件可分度，定义为：。表示决策属性集的条件不可分度，且与关系为+=1。2.1.4属性重要性度量设是一个不完备信息表，，任意属性关于属性集的重要性定义为：该定义表明，对一个属性集合，添加一个属性引起的不可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简[9]。设是一个不完备决策表，属性相对于决策属性集的重要性定义为：该定义表明，属性在属性集中的相对重要性由去掉它所引起的条件不可区分度的大小来度量[9]。2.1.5（相对）约简，（相对）核令为一族等价关系,r，如果(-{r}),则称r为中必要的,否则称r为中不必要的。如果每一个r都为中必要的，则称为独立的，否则称为依赖的。如果是独立的，，则也是独立的。设，如果是独立的，且，则称为的一个约简。中所有必要关系组成的集合称为的核，记作。，其中表示的所有约简。令和为等价关系族，，如果,则称为中不必要的，否则为中必要的。如果中的每一个都为必要的，则称为独立的。设，为的约简当且仅当是的独立子族且。的约简简称为相对约简。中所有必要的原始关系构成的集合称为的核，简称为相对核。记为：。2.2算法原理2.2.1基于不可区分度的不完备信息表属性约简算法由重要性的定义表明，对一个属性集合，添加一个属性引起的可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简。由性质可方便地求出不完备信息表的核，由于核的唯一性，因此可以将它作为求约简的起点，令，并由重要性定义逐次选择重要性最大的属性添加到约简中，直到系统关于的不可区分度与系统关于整个属性集合的不可区分度相等时算法结束。2.2.2基于条件不可区分度的不完备决策表属性约简算法对于决策表,可以利用每个条件属性对决策属性的相对重要性大小来判断添加它之后引起的条件不可区分度的变化大小，可以通过不断增加相对重要性最大的属性寻找相对约简。由性