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

1、 山西大学论文 编号：论文题目 不完备信息系统中基于不可区分度的 知识约简算法的程序设计与实现姓 名 院 系 计算机与信息技术学院 专 业 计算机科学与技术 学习年限 2005 年 9 月至 2009 年 7 月指导教师 学位级别 学 士 2009年5月23日不完备信息系统中基于不可区分度的知识约简算法的程序设计与实现学生姓名： 指导教师：内容提要 由于不完备信息系统（含有缺省数据或不精确数据）普遍存在，近年来，对不完备信息系统的研究已经引起了人们的广泛注意。但到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究还集中在理论方面，缺乏实际成型、有效的应用程序或软件。本课题完成了不完备

2、信息表中基于不可区分度的知识约简算法和不完备决策表中基于不可区分度的相对约简算法的程序设计与实现。本程序设计可作为该算法的辅助工具，具有实际意义。关键词 不完备信息系统，不可区分度，重要性，（相对）核，（相对）约简 1 引言粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法，该理论已被广泛应用于知识获取、专家系统、决策分析和决策支持等各种应用领域。知识约简是粗糙集理论处理信息系统的重要手段。现实生活中存在着大量的不完备信息系统（含有缺省值或不精确数据），因此不完备信息系统中的知识约简算法就具有重要的实际意义。文13基于不完备信息系统提出了信息系统的可区分度和不可区分度的概念，给出了它

3、们的重要性质，并建立了二者之间的关系，并且证实了不完备信息系统的不可区分度和可区分度可退化为完备信息系统的知识粒度与信息熵。文9在文13研究的基础上提出了一种基于不完备信息系统的知识获取方法，该算法将含有缺省值的不完备信息系统的知识约简方法与多值信息系统的知识约简统一起来，最终能得到不完备信息表的约简和不完备决策表的相对约简。到目前为止，对基于不可区分度的不完备信息系统知识约简算法的研究已经有了大量的理论研究，但是还缺少实现它的软件工具，这是这方面的研究方向。2 基本原理2.1 基本概念2.1.1 不完备信息系统一个信息系统是一个二元组,其中（1）是对象的非空有限集合；（2）是属性的非空有限集

4、合；（3）对，有一个映射，其中是的幂集，表示空集，每一个属性集决定一个二元不可区分关系，即 易证,是集合上的一个等价关系。关系，构成了的一个划分，用表示13。2.1.2 相容类令，定义相容关系（满足自反性和对称性）如下： 用表示分类，即为由相容关系决定的最大相容类集合。2.1.3 不可区分度文13基于不完备信息系统（含有缺省数据或不精确数据）提出了信息系统的不可区分度和可区分度的概念，给出了它们的重要性质，并建立了二者之间的关系。设是一个不完备信息系统，。则信息系统关于的不可区分度定义为： 若，则可取得最小值。若，且对有，则可取得最大值。不可区分度和可区分度的关系为+=1。其中定义为： 表示决

5、策属性集的条件可分度，定义为：。表示决策属性集的条件不可分度，且与关系为+=1。2.1.4 属性重要性度量设是一个不完备信息表，任意属性关于属性集的重要性定义为： 该定义表明，对一个属性集合，添加一个属性引起的不可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简9。设是一个不完备决策表，属性相对于决策属性集的重要性定义为： 该定义表明，属性在属性集中的相对重要性由去掉它所引起的条件不可区分度的大小来度量9。2.1.5（相对）约简，（相对）核令为一族等价关系,r，如果(-r),则称r为中必要的,否则称r为中不必要的。如果每一个r都为中必要的，则称为独立

6、的，否则称为依赖的。如果是独立的，则也是独立的。设，如果是独立的，且，则称为的一个约简。中所有必要关系组成的集合称为的核，记作。，其中表示的所有约简。令和为等价关系族，如果,则称为中不必要的，否则为中必要的。如果中的每一个都为必要的，则称为独立的。设，为的约简当且仅当是的独立子族且。的约简简称为相对约简。中所有必要的原始关系构成的集合称为的核，简称为相对核。记为：。2.2 算法原理2.2.1 基于不可区分度的不完备信息表属性约简算法由重要性的定义表明，对一个属性集合，添加一个属性引起的可区分度变化量越大，则该属性对此属性集就越重要。因此可用它作为启发知识以减少搜索空间来寻找约简。由性质可方便地

7、求出不完备信息表的核，由于核的唯一性，因此可以将它作为求约简的起点，令，并由重要性定义逐次选择重要性最大的属性添加到约简中，直到系统关于的不可区分度与系统关于整个属性集合的不可区分度相等时算法结束。2.2.2 基于条件不可区分度的不完备决策表属性约简算法对于决策表,可以利用每个条件属性对决策属性的相对重要性大小来判断添加它之后引起的条件不可区分度的变化大小，可以通过不断增加相对重要性最大的属性寻找相对约简。由性质可方便地求出不完备决策表的相对核，由于相对核的唯一性，因此可以将它作为求相对约简的起点，令，并由相对重要性定义逐次选择相对重要性最大的属性添加到相对约简中，直到系统关于相对于的条件不可

8、区分度与系统关于相对于的条件不可区分度相等时算法结束。2.3 相关技术（1）C#程序设计语言C#是一种面向对象的编程语言，它不但有着C+的强大功能，语法也和C+基本相同，并且还包含了大量的高效代码和面向对象的特性，而且，C#语言将在保持C/C+灵活性的特点上，为程序员带来更高效的开发方式，它不仅能用于WEB网站服务程序，而且还能开发强大的系统工具，总体来说，它具有以下特性：1：C#代码在.net框架提供的受控环境下运行，不允许直接操作内存，增强了程序的安全性。2：C/C+中的指针已经不在C#中出现了。3：C#具有面向对象语言编程的一切特性，如封装，继承，多态等。在C#的类型系统中，每种类型都可

9、以看做是一个对象，但C#只允许单继承，这样避免了类型定义的混乱。（2）SQL Server 2000数据库SQL是英文Structured Query Language的缩写。SQL语言的主要功能就是同各种数据库建立联系，进行沟通。SQL语句可以用来执行各种各样的操作，例如更新数据库中的数据，从数据库中提取数据等。目前，绝大多数流行的关系型数据库管理系统，如Oracle, Sybase, Microsoft SQL Server, Access等都采用了SQL语言标准。虽然很多数据库都对SQL语句进行了再开发和扩展，但是包括Select, Insert, Update, Delete, Cre

10、ate以及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）程序能创建表，只要对表名，字段名及其类

11、型和长度进行正确填写即可创建新表，并链接到数据库，操作简单；（3）程序能对信息表及决策表进行相容类分类，计算不可区分度、属性重要性和相对重要性、核和相对核，最后得出约简及相对约简结果；（4）程序具有可移植性，即不改源代码在别的计算机上也能连接数据库使用；（5）约简后的表数据不能覆盖原数据，另存也没意义，故不提供保存功能；（6）保证程序的稳定性。3.2 系统总体设计本系统主要完成了连接、断开数据库，创建表，打开表，对表进行相容类分类，约简（信息表约简和决策表相对约简）等功能。系统功能模块图如3-2-1所示，系统流程图如图3-2-2所示。图3-2-1 系统功能模块图图3-2-2 系统流程图3.3

12、后台数据库设计图 创建不完备决策表，表格式如表3-1所示，表内容如表3-2所示。表的创建：只要对表名，字段名及其类型和长度进行正确填写即可创建新表。表3-1 不完备决策表格式表3-2 不完备决策表内容 注意：表内容“*”表示信息缺失或空值。3.4 用户界面设计（1）登录界面该界面用于连接数据库，只要创建数据库成功并设置用户名、密码，连接数据源便可使用。如图3-4-1所示。图3-4-1 登录界面（2）选择表界面该界面用于选择表，创建表，打开表，断开数据库，退出程序。此界面主要用于显示数据库中的表，它只搜索SQL Server 2000数据库中的用户表，能保证库中系统表的安全性，并在界面中显示出来

13、。如图3-4-2所示。 图3-4-2选择表界面（3）约简界面该界面主要用于对表进行约简，可以显示相容类分类，不可区分度，属性（相对）重要性，（相对）约简、核的计算结果。图3-4-3为信息表约简界面，图3-4-4为决策表相对约简界面。图3-4-3 信息表约简界面图3-4-4 决策表相对约简界面4 系统约简关键算法及其流程图4.1 基于不可区分度的不完备信息表属性约简算法该算法流程图如图3-5-1所示。图3-5-1 信息表的约简算法流程图算法过程为：输入：一个不完备信息表；输出：的一个属性约简。步骤1：计算系统关于属性集的不可区分度；步骤2：令，计算每个属性对于的重要性。若，则令。最后得到的即为的

14、核，令；步骤3：若，则转至步骤5；否则转至步骤4；步骤4：对，计算，令，则，转至步骤3；步骤5：最后得到的即为的一个属性约简。算法结束。4.2 基于条件不可区分度的不完备决策表属性约简算法该算法流程图如图3-5-2所示。计算不可区分度令，计算每个相对于决策属性的令， 则, 否是令 得到的即为的一个相对约简对，计算结 束开 始图3-5-2 决策表相对约简算法流程图算法过程为：输入：一个不完备决策表；输出：的一个相对约简。步骤1：计算；步骤2：令，计算每个相对于决策属性的重要性。若>0，则令。最后得到的即为相对核，令；步骤3：若，则转至步骤5；否则转至步骤4； 步骤4：对，计算，令， 则，转

15、至步骤3；步骤5：最后得到的即为的一个相对约简。算法结束。5 系统的优缺点分析优点：（1）本系统具有可移植性，只要创建数据源并设定数据名和密码，即可连接本地SQL Server 200数据库。（2）本系统界面友好，用户操作简单，使用方便。（3）本系统不修改后台数据库内容，安全性高。（4）本系统可呈现十分详细的计算过程，容易理解。缺点：本系统完成了用户登录，连接、断开数据库，新建表，打开表，对表进行相容类分类、(相对)约简及（相对）核计算等功能。因为对C#语言不是很熟练，实现算法的代码量稍大，运行时间稍长，没有达到理想效果，加大了工作量，而且由于技术及时间原因扩展功能也不是很多，这是本系统的不足

16、之处。6 结束语经过了一个学期的学习，我终于完成了该系统的算法设计及实现。从开始接到论文题目到系统的实现，再到论文的完成，每走一步对我来说都是新的尝试与挑战，这也是我在大学期间独立完成的最大的项目。在这段时间里，我学到了很多知识也有很多感受，从对数据挖掘知识的一无所知，对C#语言等相关技术很不了解的状态，我开始了独立的学习和试验，查看相关的资料和书籍，让自己头脑中模糊的概念逐渐清晰，使自己作品一步步完善起来，每一次改进都有进步，都是我学习的收获。本次设计是在指导老师庞继芳老师的指导下完成的。在实验研究的过程中，庞老师给予了指导，并提供了很多与该研究相关的重要信息，给我以思路上的引导和拓宽，培养

17、了我对科学研究的严谨态度。这将非常有利于我们今后的学习和工作。我对庞继芳老师表示深深的敬意和由衷的感谢！参考文献：1Z.Pawlak.Rough Sets J.International Journal of Computer and Information Sciences.1982,11:341-356. 2Z. Pawlak. Rough sets:Theoretical Aspects of Reasoning about Data M.Kluwer Academic Publishers, Boston,1991.3王亚英,邵惠鹤.基于粗糙集理论的规则知识获取技术J.上海交通大学学报

18、,2000,24(5):638-640.4A. Skowron, J.F. Peteres.Rough sets:Trends and Challenges C.In:G.Y.Wang, Q.Liu, Y.Y.Yao, A.Skow- ron (eds.). Proceedings of 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and GraGranular Computing, Chongqing, China: Springer-Verlag Heidelberg,2003,25-34.5D.

19、Y.Li, B.Zhang, Y.Leung. On knowledge reduction in inconsistent decision information systems J. International Journal of Uncertainty,Fuzziness and Knowledge Based Systems,2004,12(5):651-672.6王国胤. Rough集理论与知识获取M.西安:西安交通大学出版社,2001,11(6):197-203.7梁吉业,曲开社,徐宗本.信息系统的属性约简J.系统工程理论与实践,2001,21(12):76-80.8梁吉业,徐

20、宗本,李月香.含度与粗糙集数据分析中的度量J.计算机学报,2001,24(5):544-547.9Yi Zhang,Jifang Pang,Jiahua Liang,Yiye Liang.A Method of Knowledge Acquisition Based on the Discernibility Imperfect Information SystemJ.November 18-20,Nanjing,China.Proceeding of 2007 IEEE International Conference on Grey Systems and Intelligent Serv

21、ices,2007,1602-1606.10何伟,刘春亚,赵军,李华.不完备信息系统下的属性约简算法J.计算机科学,2004,31(2):117-119.11张伟,廖晓峰,吴中福.一种基于Rough集理论的不完备数据分析方法J.模式识别与人工智能，2003,16(2):158-162.12黄兵,周献中.不完备信息系统中基于联系度的粗集模型拓展J.系统工程理论与实践,2004,11(1)： 88-92.13J.Y.Liang,J.F.Pang,A Measure method for Indiscernibility in Imperfect Information SystemJ,9th Jo

22、int Conference on Information Science,The Splender Kaohsiung,Taiwan,ROC,October8-11,2006, 896-899.14赵卫东,曹文彬,戴伟辉.不完全信息下的粗集拓展J.系统工程学报,2002,17(6):481-485.Design and Implementation of Knowledge Reduction Algorithm Based on the Discernibility in Imperfect Information SystemStudent Name：Jin Yuan Tutor：Pang JifangAbstract Due to imperfect information systems (with missing data or imprecise data) widespread,the research of imperfect