《信息系统的表示及属性约简》由会员分享，可在线阅读，更多相关《信息系统的表示及属性约简（39页珍藏版）》请在金锄头文库上搜索。
1、武汉科技大学 硕士学位论文 信息系统的表示及属性约简 姓名：曹梦菲 申请学位级别：硕士 专业：应用数学 指导教师：陈少白 2010-11-01 武汉科技大学武汉科技大学 硕士学位论文 第 I 页 摘摘 要要 信息系统是一个有对象和属性关系的数据库一个数据库的本质是一堆数据和这一堆 数据之间的各种关系，因此数据库可以抽象的描述为对象集和对象集上的一些二元关系， 根据这种思想，本文将信息系统表示为一个二元组，而不是通常的三元组或者四元组，然 后在新的表示方式下讨论信息系统的属性约简问题，主要包括以下几方面的内容： 1信息系统的表示首先给出了信息系统新的定义，证明了该表达方式与以信息函 数表达的信息
2、系统是等价的，然后给出了在新的表达方式下，等价类、上近似、下近似等 基本概念及相关性质和定理 2简单信息系统的属性约简首先给出了分离属性集的定义，然后提出了分明多项 式的概念，它是由等价关系的补经过有限次并运算和交运算组成的表达式，证明了分明多 项式由分明析取范式转变成分明合取范式可以确定全部的约简，最后提出了极小元法，该 算法在一定程度上减少了计算量 3目标信息系统的属性约简给出了目标信息系统的定义及相关基本概念和定理， 讨论了协调和不协调的目标信息系统在新的表达方式下的属性约简问题 4粗糙集方法在数据挖掘中的应用简单说明了数据挖掘的三个主要步骤，并通过 分析实例来说明粗糙集方法在数据挖掘中
3、的作用 关键词：关键词：信息系统；属性约简；分离属性集；极小元法 武汉科技大学武汉科技大学 硕士学位论文 第 II 页 Abstract Information system is a database with object set and attribute relations. The essence of a database is the data and various relations among them, therefore the abstract description of a database can be set of objects and several bi
4、nary relations on the set of objects. According to this idea, this article expresses the information systems as binary combinations instead of general triple or four combinations. Then we discuss information system attribute reductions under the new expression, it mainly contain the following conten
5、t. 1. Expression of information system. Firstly, a new definition of information system is given. Then it gives some basic definitions, relevant properties and theorems with respect to equivalent class, upper and lower approximation. 2. Attribute reduction of simple information system, The definitio
6、n of separation attribute sets is given. Then the notion of separation polynomial is brought forward, which is a representation composed of the separators (complement of the equivalence relations) via finite union operations and intersection operations. It proves that convert the separation disjunct
7、ive normal form to separation conjunctive normal form of the separation polynomial can determines all the reductions. Finally, minimal element method is putting forward which has reduced the amount of calculation to a certain degree. 3. Attribute reduction of objective information system. A new defi
8、nition of objective information system and relevant theorems are given, it also discusses attribute reductions of coordinate objective information system and non- coordinate objective information system under the new expression. 4. Application of rough set approach in data mining. Simply introduces
9、three main steps of data mining, and explains the effect of rough set approach in data mining through analyzing an example. Key Words: Information system; attribute reduction; separation attribute sets；minimal element method 武汉科技大学武汉科技大学 硕士学位论文 第 1 页 第一章第一章 绪论绪论 1.1 引言引言 知识是人类认识客观世界的结果， 也是人类社会发展的动力
10、随着时代和环境的变化， 人们必须不断地获取新的知识来满足社会发展的需要 1 但在计算机技术高速发展的今天， 各领域、各行业、各部门在短时间内就会积累并存储各种大量的数据资料，大规模数据给 人们正确运用信息带来了困难，如何从海量的数据中提取有用的信息成为了人们急需解决 的问题，此后数据库的知识发现(Knowledge Discovery in Data Base，简称 KDD)技术便应 运而生 2,3 数据库的知识发现是指从大量数据中提取有效的、新颖的、潜在有用的，最终可被理 解的模式非平凡过程 4基于数据库的知识发现的方法很多，如基于网络结构的神经网络 算法， 基于统计理论的数据挖掘与支持向量
11、机方法、 基于归纳学习的机器学习方法等等 本 文的研究对象是信息系统信息系统是一个具有对象和属性关系的数据库经典的信息系 统一般表示为一个三元组( , ,)U A F ，五元组( , ,)U A F D G 用来表示目标信息系统实际生 活中数据的多样性，使得信息系统也具有多样性不同的信息系统 1，一是依赖于属性取 值域，如格值信息系统；二是依赖于在信息系统上建立的不同的关系，如关系信息系统、 邻域信息系统等由于数据表的规模性和多样性，对象集和属性之间的不确定关系必须依 赖一定的数学方法和计算工具才能转变为有用的知识，而在 1982 年，由波兰数学家 ZPawlak 提出的粗糙集方法 36正是一
12、种不需要数据集额外先验信息的、能处理不确定信 息的数据分析工具 5在 ZPawlak 教授提出粗糙集起初，并没有受到广泛的关注，直到 上世纪八十年代末，才引起各国学者的注意1992 年在波兰召开的第一届关于粗糙集方法 的国际学术会议，推动了国际上对粗糙集理论与应用的研究此后每年一届的有关粗糙集 理论应用的国际学术会议进一步推动了粗糙集的发展，越来越多的科技人员开始了解并准 备从事该领域的研究 6目前，粗糙集已成为人工智能领域中的一个学术热点，在机器学 习、知识获取、决策分析、过程控制等领域 7-10,38,39得到了广泛的应用，并取得了重大突破 粗糙集理论的主要思想 43在于它恰好反映了人们用
13、粗糙集方法处理不分明问题的常 规性，即以不完全信息或知识去处理一些不分明现象的能力或依据观察度量到的某些不精 确的结果而进行分类数据的能力粗糙集理论能在较短的时间内得到广泛的应用是由于它 在处理不确定性问题上有以下特点 11，(1)粗糙集理论不需要任何预备的或额外的数据信 息，即先验信息，可以直接处理数据；(2)粗糙集理论能处理不确定性和模凌两可，包括 确定性和非确定性的情况；(3)粗糙集理论能在保留关键信息的前提下，求得知识的最小 表达和知识的各种不同的颗粒层次；(4)粗糙集理论能识别并评估数据之间的依赖关系， 从数据中揭示出概念简单且易于操作的模式 鉴于以上粗糙集理论的特点，粗糙集理论便开
14、始被用于数据挖掘过程数据挖掘是数 据库知识发现的一个重要步骤，它是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程当前数据挖掘应用主要集中在石油勘探、金融市场、商业销售、产品制造、医 武汉科技大学武汉科技大学 硕士学位论文 第 2 页 疗保险、化工生产等领域 4，各个企业和机构可以根据数据挖掘分析出的结果，做出 对自己有利的决策，可以提高企业的竞争力 1.2 国内外研究现状国内外研究现状 目前，国内外学者用粗糙集作为数据分析工具来研究信息系统，主要解决信息系统的 知识约简问题知识约简包括属性约简和值约简属性约简
15、 1是指在不影响原来信息系统 的分类的情况下，删除不相关或者不重要的属性很多时候，信息系统中的属性集较大， 但并不是所有属性都是必要的，有些属性去掉后并不会影响分类的知识发现，有些属性去 掉后必然会影响分类的知识发现，还有些属性是和其它属性一起来确定分类的知识发现， 因此我们需要一些方法来区分这些属性，删除冗余的属性，达到简化原有信息系统的目 的对于目标信息系统而言，仅仅进行属性约简不能完全实现简化原有决策表的，需要进 一步简化决策规则， 从决策表中删除多余的条件属性， 获取简洁的决策规则， 即值约简 5,12 对信息系统属性约简的研究主要集中于三个方面：信息系统的属性约简，协调目标信 息系统的属性约简和不协调目标信息系统的属性约简 5 (1)信息系统的属性约简 1：一般的文献都将信息系统表示为一个三元组( , , )U A F 或四 元 组 ( , , ,)U A V F ，其中 12 , n Ux xx=L是一个 非空有限集合， 称之 为对象集 ； 12 , m Aa aa=L也为非空有限集合，称之为属性集； i i a aA VV = U表示属性值域，其中 i a V 表 示属性 i a 的值域；, j Ffjm=为U 和 A的关系集，其中: i ja fUV一个信息系统对应 了一个数据表，数据表的行表示对象集中的对象，列表示属性，行与列的交点为对象关于 属性的取值在对象集
