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

山西大学论文 编号： 论文题目 不完备信息系统中基于不可区分度的 知识约简算法的程序设计与实现 姓 名 院 系 计算机与信息技术学院 专 业 计算机科学与技术 学习年限 2005 年 9 月至 2009 年 7 月 指导教师 学位级别 学 士 2009年5月23日 不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现 学生姓名： 指导教师： 内容提要 由于不完备信息系统（含有缺省数据或不精确数据）普遍存在，近年来，对不完备信息系统的研究已经引起了人们的广泛注意。但到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究还集中在理论方面，缺乏实际成型、有效的应用程序或软件。本课题完成了不完备信息表中基于不可区分度的知识约简算法和不完备决策表中基于不可区分度的相对约简算法的程序设计与实现。本程序设计可作为该算法的辅助工具，具有实际意义。 关键词 不完备信息系统，不可区分度，重要性，（相对）核，（相对）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 基于条件不可区分度的不完备决策表属性约简算法 对于决策表,可以利用每个条件属性对决策属性的相对重要性大小来判断添加它之后引起的条件不可区分度的变化大小，可以通过不断增加相对重要性最大的属性寻找相对约简。由性质可方便地求出不完备决策表的相对核，由于相对核的唯一性，因此可以将它作为求相对约简的起点，令，并由相对重要性定义逐次选择相对重要性最大的属性添加到相对约简中，直到系统关于相对于的条件不可区分度与系统关于相对于的条件不可区分度相等时