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

山 西 大 学 论 文 编号：论文题目 不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现姓 名 院 系 计算机与信息技术学院 专 业 计算机科学与技术 学 习 年 限 2005 年 9 月至 2009 年 7 月指 导 教 师 学 位 级 别 学 士 2009 年 5 月 23 日1不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现学生姓名： 指导教师：内容提要 由于不完备信息系统（含有缺省数据或不精确数据）普遍存在，近年来，对不完备信息系统的研究已经引起了人们的广泛注意。但到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究还集中在理论方面，缺乏实际成型、有效的应用程序或软件。本课题完成了不完备信息表中基于不可区分度的知识约简算法和不完备决策表中基于不可区分度的相对约简算法的程序设计与实现。本程序设计可作为该算法的辅助工具，具有实际意义。关键词 不完备信息系统，不可区分度，重要性， （相对）核， （相对）约简 1 引言粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法，该理论已被广泛应用于知识获取、专家系统、决策分析和决策支持等各种应用领域。知识约简是粗糙集理论处理信息系统的重要手段。现实生活中存在着大量的不完备信息系统（含有缺省值或不精确数据） ，因此不完备信息系统中的知识约简算法就具有重要的实际意义。文13基于不完备信息系统提出了信息系统的可区分度和不可区分度的概念，给出了它们的重要性质，并建立了二者之间的关系，并且证实了不完备信息系统的不可区分度和可区分度可退化为完备信息系统的知识粒度与信息熵。文9在文13研究的基础上提出了一种基于不完备信息系统的知识获取方法，该算法将含有缺省值的不完备信息系统的知识约简方法与多值信息系统的知识约简统一起来，最终能得到不完备信息表的约简和不完备决策表的相对约简。到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究已经有了大量的理论研究，但是还缺少实现它的软件工具，这是这方面的研究方向。2 基本原理2.1 基本概念2.1.1 不完备信息系统一个信息系统是一个二元组 ,其中)(AUS（1） 是对象的非空有限集合；U2（2） 是属性的非空有限集合；A（3）对 ，有一个映射 ， ，其中 是 的幂集， 表示空集，每aaf)2(:aVUaV2一个属性集 决定一个二元不可区分关系 ，即PPIND(),)|,()aaINDPxyfxfy易证, 是集合 上的一个等价关系。关系 ， ，构成了 的一个划分，用)(IUIAU表示 13。PNDU2.1.2 相容类令 ，定义相容关系（满足自反性和对称性）如下：A(),)|,()aaSIMPxyUPfxfy用 表示分类，即为由相容关系 决定的最大相容类集合。/()UI ()SIM2.1.3 不可区分度文13基于不完备信息系统（含有缺省数据或不精确数据）提出了信息系统的不可区分度 和)(AI可区分度 的概念，给出了它们的重要性质，并建立了二者之间的关系。)(AD设 是一个不完备信息系统， 。则信息系统 关于 的不可区分度,US ,.|21UxS定义为：|21()()|iixiIASA若 ，则 可取得最小值 。/()USIMA()I 2|U若 ，且对 有 ，则 可取得最大值 。,xy(,)1Axy()I2|1U不可区分度 和可区分度 的关系为 + =1。其中 定义为：)(I)(DID)(A|21|(| iiUxiS表示决策属性集的条件可分度，定义为： 。)|(/CD |)()(CDC表示决策属性集的条件不可分度，且与 关系为 + =1。|/I |(/D|/)|/I2.1.4 属性重要性度量3设 是一个不完备信息表， ，任意属性 关于属性集 的重要性定义(,)SUCC Cc为： ()()(CcsigiD该定义表明，对一个属性集合，添加一个属性引起的不可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简 9。设 是一个不完备决策表，属性 相对于决策属性集 的重要性定义为：),(DCUSc)|()|()( / CDCsigsiDC该定义表明，属性在属性集中的相对重要性由去掉它所引起的条件不可区分度的大小来度量 9。2.1.5（相对）约简， （相对）核令 为一族等价关系,r ，如果 ( -r),则称 r 为 中必要的,否则称 r 为RRindi)(RR中不必要的。如果每一个 r 都为 中必要的，则称 为独立的，否则称 为依赖的。如果是独立的， ，则 也是独立的。设 ，如果 是独立的，且 ，则称PPQ)()(QindPi为 的一个约简。 中所有必要关系组成的集合称为 的核，记作 。Q core，其中 表示 的所有约简。)()(redco)(Pred令 和 为等价关系族， ，如果 ,则称 为R)()()()( ipsindposRPindPi R中 不必要的，否则 为 中 必要的。如果 中的每一个 都为 必要的，则称 为 独立的。PQQQ设 ， 为 的 约简当且仅当 是 的 独立子族且 。 的 约简简SS )()(possPS称为相对约简。 中所有 必要的原始关系构成的集合称为 的 核，简称为相对核。记为：。)(PcoreQ2.2 算法原理2.2.1 基于不可区分度的不完备信息表属性约简算法由重要性的定义表明，对一个属性集合，添加一个属性引起的可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简。由性质可方便地求出不完备信息表的核，由于核的唯一性，因此可以将()|()0Cccoresig它作为求约简的起点，令 ，并由重要性定义逐次选择重要性最大的属性添加到约red)(Core简 中，直到系统关于 的不可区分度与系统关于整个属性集合 的不可区分度相等时算)(red C法结束。2.2.2 基于条件不可区分度的不完备决策表属性约简算法4对于决策表,可以利用每个条件属性对决策属性的相对重要性大小来判断添加它之后引起的条件不可区分度的变化大小，可以通过不断增加相对重要性最大的属性寻找相对约简。由性质可方便地求出不完备决策表的相对核，由于相对核的唯一性，因()|()0CcDDcorecsig此可以将它作为求相对约简的起点，令 ，并由相对重要性定义逐次选择相对重)(CredD()Dcore要性最大的属性添加到相对约简 中，直到系统关于 相对于 的条件不可区分度与CdD系统关于 相对于 的条件不可区分度相等时算法结束。C2.3 相关技术（1）C#程序设计语言C#是一种面向对象的编程语言，它不但有着 C+的强大功能，语法也和 C+基本相同，并且还包含了大量的高效代码和面向对象的特性，而且，C#语言将在保持 C/C+灵活性的特点上，为程序员带来更高效的开发方式，它不仅能用于 WEB 网站服务程序，而且还能开发强大的系统工具，总体来说，它具有以下特性：1：C#代码在.net 框架提供的受控环境下运行，不允许直接操作内存，增强了程序的安全性。2：C/C+中的指针已经不在 C#中出现了。3：C#具有面向对象语言编程的一切特性，如封装，继承，多态等。在 C#的类型系统中，每种类型都可以看做是一个对象，但 C#只允许单继承，这样避免了类型定义的混乱。（2）SQL Server 2000 数据库SQL 是英文 Structured Query Language 的缩写。SQL 语言的主要功能就是同各种数据库建立联系，进行沟通。SQL 语句可以用来执行各种各样的操作，例如更新数据库中的数据，从数据库中提取数据等。目前，绝大多数流行的关系型数据库管理系统，如 Oracle, Sybase, Microsoft SQL Server, Access 等都采用了 SQL 语言标准。虽然很多数据库都对 SQL 语句进行了再开发和扩展，但是包括 Select, Insert, Update, Delete, Create 以及 Drop 在内的标准的 SQL 命令仍然可以被用来完成几乎所有的数据库操作。 2.4 开发环境及工具软件环境：Microsoft Windows XP、SQL Server 2000 数据库、Microsoft Visual Studio 2005。硬件环境：AMD Sempron(tm) Processor 3000+处理器、1M 内存、4G 硬盘。3 系统分析3.1 需求分析本算法是不完备信息系统基于不可区分度的知识约简算法的程序设计与实现，按照具体环境设定对其提出如下具体要求：（1）程序有登录界面，并有能连接、断开数据库和选择并打开库中表的功能；（2）程序能创建表，只要对表名，字段名及其类型和长度进行正确填写即可创建新表，并链接到数据库，操作简单；（3）程序能对信息表及决策表进行相容类分类，计算不可区分度、属性重要性和相对重要性、核5和相对核，最后得出约简及相对约简结果；（4）程序具有可移植性，即不改源代码在别的计算机上也能连接数据库使用；（5）约简后的表数据不能覆盖原数据，另存也没意义，故不提供保存功能；（6）保证程序的稳定性。3.2 系统总体设计本系统主要完成了连接、断开数据库，创建表，打开表，对表进行相容类分类，约简（信息表约简和决策表相对约简）等功能。系统功能模块图如 3-2-1 所示，系统流程图如图 3-2-2 所示。图 3-2-1 系统功能模块图6图 3-2-2 系统流程图3.3 后台数据库设计图 创建不完备决策表，表格式如表 3-1 所示，表内容如表 3-2 所示。表的创建：只要对表名，字段名及其类型和长度进行正确填写即可创建新表。表 3-1 不完备决策表格式7表 3-2 不完备决策表内容注意：表内容“*”表示信息缺失或空值。3.4 用户界面设计（1）登录界面该界面用于连接数据库，只要创建数据库成功并设置用户名、密码，连接数据源便可使用。如图3-4-1 所示。图 3-4-1 登录界面（2）选择表界面该界面用于选择表，创建表，打开表，断开数据库，退出程序。此界面主要用于显示数据库中的表，它只搜索 SQL Server 2000 数据库中的用户表，能保证库中系统表的安全性，并在界面中显示出来。如图 3-4-2 所示。图 3-4-2 选择表界面8（3）约简界面该界面主要用于对表进行约简，可以显示相容类分类，不可区分度，属性（相对）重要性， （相对