信息系统的表示及属性约简

1、武汉科技大学 硕士学位论文信息系统的表示及属性约简姓名：曹梦菲中请学位级别：硕士专业：应用数学_指导教师：陈少白2010-11-01信息系统是一个有对象和属性关系的数据库.一个数据库的木质是一堆数据和这一堆 数据之间的各种关系，因此数据库可以抽象的描述为对象集和对象集上的一些二元关系， 根据这种思想，本文将信息系统表示为一个二元组，而不是通常的三元组或者四元组，然 后在新的表示方式下讨论信息系统的属性约简问题，主要包括以下几方面的内容：1. 信息系统的表示.首先给出了信息系统新的定义，证明了该表达方式与以信息函 数表达的信息系统是等价的，然后给出了在新的表达方式下，等价类、上近似、下近似等 基

2、本概念及相关性质和定理.2. 简单信息系统的属性约简.首先给dr了分离属性集的定义，然后提出了分明多项 式的概念，它是由等价关系的补经过有限次并运算和交运算组成的表达式，证明了分明多 项式由分明析取范式转变成分明合取范式可以确定全部的约简，最后提出了极小元法，该 算法在一定程度上减少了计算量.3. 口标信息系统的属性约简.给出了口标信息系统的定义及相关基木概念和定理， 讨论了协调和不协调的目标信息系统在新的表达方式下的属性约简问题.4 粗糙集方法在数据挖掘中的应用.简单说明了数据挖掘的三个主要步骤，并通过 分析实例来说明粗糙集方法在数据挖掘中的作用.关键词：信息系统；属性约简；分离属性集；极小

3、元法abstractinformation 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 binary relations on the set of objects. according to this ide

4、a, 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 content.1. expression of information system. firstly, a new defin

5、ition 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 definition of separation attribute sets is given. then the notion of s

6、eparation 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 disjunctive normal form to separation conjunctive normal form of the

7、separation polynomial can determines all the reductions. finally, minimal element method is putting forward which has reduced the amount of calculation to a certain degree3. attribute reduction of objective information system a new definition of objective information system and relevant theorems are

8、 given, it also discusses attribute reductions of coordinate objective information system and non-coordinate objective information system under the new expression4. application of rough set approach in data mining. simply introduces three main steps of data mining, and explains the effect of rough s

9、et approach in data mining through analyzing an example.key words: information system; attribute reduction; separation attribute sets； minimal element method武汉科技大学利京 圧荷论 万右ii端桂 吉阳本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研究 所取得的成果。除了文中己经注明引用的内容或属合作研究共同完成的工作 外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文

10、中以明确方式标明。申请学位论文与资料若有不实之处，本人承担一切相关责任。论文作者签名:研究生学位论文版权使用授权声明本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位的 名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定，同 意学校保留并向有关部门（按照武汉科技大学关于研究生学位论文收录工作 的规定执行）送交论文的复印件和电子版本，允许论文被查阅和借阅，同意 学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行检索和 对外服务。第一章绪论1. 1引言知识是人类认识客观世界的结果，也是人类社会发展的动力.随着时代和环境的变化, 人们必须不断地获取新的知识来满足社会发

11、展的需要e但在计算机技术高速发展的今天, 各领域、各行业、各部门在短时间内就会积累并存储各种大量的数据资料，大规模数据给 人们正确运用信息带来了困难，如何从海量的数据屮捉取冇用的信息成为了人们急需解决 的问题，此后数据库的知识发现(knowledge discovery in data base,简称kdd)技术便应 运而生数据库的知识发现是指从人量数据中提取有效的、新颖的、潜在有用的，最终可被理 解的模式非平凡过程.基于数据库的知识发现的方法很多，如基丁网络结构的神经网络 算法，基于统计理论的数据挖掘与支持向量机方法、基于归纳学习的机器学习方法等等木 文的研究对象是信息系统.信息系统是一个具

12、有对象和属性关系的数据库.经典的信息系 统一般表示为一个三元组(u,a,f),五元组(u,a,f,d,g)用来表示目标信息系统.实际生 活中数据的多样性，使得信息系统也具有多样性.不同的信息系统川，一是依赖于属性取 值域，如格值信息系统；二是依赖于在信息系统上建立的不同的关系，如关系信息系统、 邻域信息系统等.由于数拯表的规模性和多样性，对象集和属性之间的不确定关系必须依 赖一定的数学方法和计算工具才能转变为有用的知识，而在1 982年，由波兰数学家 乙pawlak提出的粗糙集方法网正是一种不需要数据集额外先验信息的、能处理不确定信 息的数据分析工具.在乙pawlak教授提出粗糙集起初，并没有

13、受到广泛的关注，直到 上世纪八十年代末，才引起各国学者的注意1992年在波兰召开的第一届关于粗糙集方法 的国际学术会议，推动了国际上对粗糙集理论与应用的研究.此后每年一届的冇关粗糙集 理论应用的国际学术会议进-步推动了粗糙集的发展，越来越多的科技人员开始了解并准 备从事该领域的研究.目前，粗糙集已成为人工智能领域中的一个学术热点，在机器学 习、知识获取、决策分析、过程控制等领域得到了广泛的应用，并取得了重大突破.粗糙集理论的主要思想z在于它恰好反映了人们用粗糙集方法处理不分明问题的常 规性，即以不完全信息或知识去处理一些不分明现象的能力或依据观察度量到的某些不精 确的结果而进行分类数据的能力.

14、粗糙集理论能在较短的时间内得到广泛的应用是由于它 在处理不确定性问题上有以下特点，(1)粗糙集理论不需要任何预备的或额外的数据信 息，即先验信息，可以直接处理数据；(2)粗糙集理论能处理不确定性和模凌两可，包括 确定性和非确定性的情况；(3)粗糙集理论能在保留关键信息的前提下，求得知识的最小 表达和知识的各种不同的颗粒层次；(4)粗糙集理论能识别并评估数据之间的依赖关系， 从数据中揭示出概念简单且易于操作的模式.鉴于以上粗糙集理论的特点，粗糙集理论便开始被用于数据挖掘过程.数据挖掘是数 据库知识发现的一个重要步骤，它是从犬量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其屮

15、的、人们事先不知道的、但又是潜在有用的信息和知识的 过程.当前数据挖掘应用主要集中在石油勘探、金融市场、商业销售、产品制造、医 疗保险、化工生产等领域，各个企业和机构可以根据数据挖掘分析出的结果，做出 对自己有利的决策，可以提高企业的竞争力.12国内外研究现状目前，国内外学者用粗糙集作为数据分析工具来研究信息系统，主要解决信息系统的 知识约简问题.知识约简包括属性约简和值约简.属性约简是指在不影响原來信息系统 的分类的情况下，删除不相关或者不重耍的属性很多吋候，信息系统中的属性集较人， 但并不是所有属性都是必要的，有些属性去掉后并不会影响分类的知识发现，有些属性去 掉后必然会影响分类的知识发现

16、，还有些属性是和其它属性一起來确定分类的知识发现， 因此我们需要一些方法来区分这些属性，删除冗余的属性，达到简化原有信息系统的目 的.对丁目标信息系统而言，仅仅进行屈性约简不能完全实现简化原冇决策表的，需耍进 一步简化决策规则，从决策表屮删除多余的条件属性，获取简洁的决策规则，即值约简卩阳.对信息系统属性约简的研究主耍集中于三个方面：信息系统的屈性约简，协调目标信 息系统的属性约简和不协调目标信息系统的属性约简山(1) 信息系统的属性约简一般的文献都将信息系统表示为一个三元组或四 元组(t/,a,v,f),其中(7=xpx2,l 是一个非空有限集合，称z为对象集； a = al9a2,l 9a

17、ffl也为非空有限集合，称之为属性集；u v,表示属性值域，其屮匕表 aa f1示属性q的值域；f = fjj<m为“和a的关系集，其中、fj：u 1人.一个信息系统对应 了一个数据表，数据表的行表示对象集中的对象，列表示属性，行与列的交点为对象关于 属性的取值.在对象集”上定义一个等价关系，即满足自反性、对称性和传递性的二元关 系：rb = (x,.,x7)g uxu :/；(%,.) = (vaz e b),其'pfic a ,对象兀关于心的等价类 记为比心=y ：(x,y)e /?定义1.1称ba是©,a,f)的协调集，若满足rb=r若对任意bwb ,还满足 rb

18、_b ra，则称3是(t/,a,f)的约简求信息系统的属性约简可以直接根据定义11來求，此外最常用、学者们研究最多的 方法是基于skowron的分明矩阵法，该方法是在1 992年由a. skowron教授提出的.设 r, = (x, y): fa(x) = £(y) (vae a),若(x,y)住ra,贝！j称对象兀和y关于属性。是不分明 的.分明矩阵的定义如下：定义1.2i13j设信息系统s = (t/",f)，其中t/=xpx2,l，兀为对象集，a = 04,l “” 为属性集合，信息系统s的分明矩阵为m(s) = ©h”，其中矩阵项定义如下： =ae a :

19、 a(xj 工 a(xjxi e u,xj e u,i.j = 1，2,l ,n.基于skowron的分明矩阵法的步骤如下":1 计算出信息系统的分明矩阵m(s) ； 2 计 算与分明矩阵相关的分明函数几小3计算分明函数九的最小析取范式，它将给出所 有的约简，即其中每个析取项是对应于该信息系统的一个约简.由于基于skowron的分明 矩阵法在计算可辨识矩阵时，产生许多重复的项，在时间和空间上都有一定的消耗，使得 算法的效率不高，为了提高算法的效率，裴小兵等人提出了扩展分明矩阵法，该算法在计 算绝对属性约简吋，算法效率有所提高.(2) 协调冃标新系统的属性约简目标信息系统也称为决策表，

20、一般表示为一个五元组其中(t/,af)是信息系统，a称为条件属性集，d称为目标属性集，即 d = £,d2，l ,d，g 为“和 d 的关系集，即 g =其中和山 tv； (j 5 p), v；为目标属性d/的值域.定义1.3设©,a,fq,g)为廿标信息系统，若raurb，则称目标信息系统是协调的, 否则称目标信息系统是不协调的.对于协调的目标信息系统，若存在bca使得rbrd， h对于任意的bwb, rb钿工陷，则称b是目标信息系统的一个约简.在协调目标信息系统的属性约简研究方面，全部相对属性约简算法和最优相对属性约 简算法是研究的两个方向.全部相对属性约简算法的常用方

21、法有数据分析法和基于分明矩 阵法；而最优和对属性约简一般采用启发式算法，有基于属性频率的约简算法和基于属性 重要性的约简算法.(3) 不协调目标信息系统的属性约简"j由于实际问题中数据的复杂性，使得大多数目 标信息系统是不协调的.典型的屈性约简方法冇分布约简、最大分布约简、分配约简和近 似约简.目而所提出的约简方法中，大多都会用到分明矩阵，但在遇到较大的数据集时， 如何降低算法的时间和空间的复杂度是个值得继续研究的问题目前属性约简的算法还冇很多，以下将列举其他几种常用的属性约简算法：1 启发式算法：此算法的种类有很多，如基于属性重要度的启发式算法!，5'161,信息爛 法l，

22、71，8i,属性频度的约简算法"，属性序法等.改算法的基木思想是先计算出核属性, 然后根据属性的重要度依次加入核属性集中或者根据决策属性对条件属性的依赖程度依 次删除对分类不产生影响的属性，直到得到一个约简为止该算法的优点是时间性能好.2. 遗传算法：遗传算法是由美国mi chi gan大学的hol i and教授及其学生在20世纪60年 代末提出的.该算法是通过不同的编码来实现约简的，如二进制编码、格雷码编码、实数 编码和符号编码等.不同的编码各有优缺点.3. 其它属性约简算法：如针对约简稳定性不足、规范化程度不高提出的动态约简法、 基于包含度的约简、基于粒度嫡约简、覆盖约简、基于

23、矩阵算法的约简等.在数据挖掘方而，数据挖掘技术是在1 989年8月美国举行的第十一届国际人工智能 联合学术会议上首次被提出的.到现在为止，kdd研讨会已召开了 7次，会议规模逐渐扩 大，研究的重点也从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及 多种学科之间的相互渗透.上世纪九十年代初，有部分学者较全面的论述了 kdd系统方法 论、发现结果的评价、kdd系统设计的逻辑方法，集屮讨论了鉴于数据库的动态性冗余、 高噪芦、不确定性和空值等问题，kdd系统与其他传统的机器学习、专家系统、人工神经 网络、数理统计分析系统的联系和区别.随后数拯挖掘及其核心技术也慢慢得到了广泛的 发展和应用

24、.近年来，基于粗糙集理论的数据挖掘的应用也冇了较大进展，并逐渐成为研 究的主流方法之一.为了降低算法的复杂度，许多学者研究了将粗糙集方法与模糊集、神 经网络、遗传算法或者面向属性的归纳方法相结合的方法，新方法在很人程度上提高了数 据挖掘的能力与效率.1.3本论文所做的工作本文所做的工作主要涉及如下几个方面：1 信息系统的表示.首先将信息系统的表示方法进行简化，将其表示为一个二元组， 并将这些二元关系定义为具有自反性、传递性的二元关系族，证明了以信息函数表达的信 息系统与该表达方式是等价的.然后证明这种表达方式适合所有的信息系统，最后给出这 种表达方式下，信息系统的基本概念、性质及相关定理.2简

25、单信息系统的屈性约简.首先给出了二元关系族“型”的定义，其实质是对信息 系统的对象集的一个最细的划分，接着给出了简单信息系统的分离属性集的定义，提出了 分离多项式概念，它是由等价关系的补经过有限次并运算和交运算组成的表达式，证明了 分离多项式由分离析取范式转变成分离合取范式可以确定全部的约简，并提出了极小元 法，在一定程度上减小了吋间和空间复杂度，提高了算法的效率.研究了信息函数之间的 复合运算及相关性质，得到信息函数的最大公因式计算方法.3.目标信息系统的属性约简.首先给出了目标信息系统的表达方式，简单说明了目标 信息系统在新的表达方式下的相关概念及性质等.然后定义了强弱覆盖来区分协调的目标

26、 信息系统和不协调的目标新系统，重点讨论了两种信息系统的属性约简，给出了求属性约 简分离属性集及相关的定理，并用实例进行了说明.4粗糙集在数据挖掘中的应用.简单说明了数据挖掘的作用，叙述了数据挖掘的三个 主要步骤，即数据预处理，属性约简和值约简.最后用粗糙集方法讨论了一个旅游公司的 实例，给出了相关的结论.1.4本文的创新之处1 将信息系统表示为一个二元组的形式，证明以信息函数表达的信息系统与该表达方 式是等价的.2.给出了极小元的算法，减少了在计算分离析取范式时的中间项，一定程度上减小了 算法的空间和时间复杂度，提高了计算机运行的效率.15本论文的内容安排全文共分为五章，其主要内容和章节安排

27、如下：第一章为绪论.第二章主要为信息系统的表示方式及基本概念.第三章主耍涉及简单信息系统的属性约简问题.第四章主要涉及冃标信息系统的属性约简.第五章为粗糙集理论在数据挖掘中的应用第六章对全文进行总结，并作出展望.第二章信息系统的表示信息系统是一个冇对彖和屈性关系的数据库.一个数据库的本质是一堆数据和这一堆 数据z间的齐种关系，因此数据库可以抽象的描述为对象集和对象集上的一些二元关系， 根据这种思想，本章将信息系统表示为一个二元组的形式，而非通常的三元组或四元组 i绚.讨论了这种表达方式的合理性，然后给岀了新的信息系统的相关基本定义和定理.本章的安排如下：2.1节提出了信息系统新的表达方式并说明

28、了新的表达方式的合理 性；2.2节说明了信息系统新的表达方式的一般性；2.3节给出了在新的表达方式下，信 息系统的相关基本概念及定理；2. 4节对本章进行小结.2. 1信息系统的表示定义1如果j为集合x上二元关系族，称(xjj )为广义信息系统，如果j为集合x 上具有口反性、传递性的二元关系族，称(xu )为信息系统，如果j为集合x上二元等 价关系族，称(xu )为简单信息系统.广义信息系统的二元关系族j中每一个二元关系替换成其口反、传递闭包，则广义信 息系统可生成一个对应的信息系统.设(xjj )为信息系统，/?eu则rcr"为x上等价关系，含xex的等价类表示为 xr=ye x

29、:xry,yrx,划分表示为 tir = x / r = xr x.对于 rwu ,映射 9r：x t%<pr(兀)= wr，xw x 称为信息系统(xjj )的7?属性，臥=小为元素兀的r属性值.自反性、传递性的二元关系rwu确定了集合nr=xr-.xex±一个二元关系xk <k yk 当且仅当 xry .该关系具有确定意义.事实上，如果仪y,贝ij对于任意xxr, y'eyr有水心i易知: 二元关系$是划分兀尺=兀尺：兀w x上偏序关系.于是，一个信息系统(xu)确定了一个 映射族f，其中每一个映射臥的定义域为x、值域为偏序集心的映射.集合x到一偏序集的映射称

30、为x的赋偏序映射，x的赋偏序映射全体记为d(x)对 于给定一个从集合x到偏序集(y,w)的映射a ,可以诱导集合x上一个二元关系/?：兀/?)，当 且仅当a(兀)< a(y)，该二元关系7?具自反性、传递性事实上，对于任意xw x ,因a(x) < a(x) 有xrx ；如果x/?y, yrz，ft a(x)<a(y)<a(z)有成立.丁是，一个从集合x到偏序集 的赋偏序映射族f确定了一个信息系统(xjj ).因此，信息系统可以表示成(x,f ),其 中f cp(x).映射6/gf称为信息系统(x,f )的。属性，a(x)为元素兀的a属性值. 2.2表示方式的一般性设f

31、 =勺,勺丄卫”是从集合x到偏序集(y,s)的映射族.对于某些信息系统，对象与属性z间存在不确定性关系，即一个对象有多种取值的可能性1371 .用p(li (x, alk (x)表示对象兀以p(li (x, alk (%)的程度取属性值alk (x)且 £ p(l!(x,alk(x) = i.对于映射用冋|表示对象x在属性®的作用下所有口j 如(x) 能取值的属性值的个数，在不致混淆的情况下用i引表示记如(兀) = £“(兀，创(%), al2(x) = pai(x,al2(x), l, q闯(兀)=眾(兀,勺屈(兀) 即妝表示对象兀在属性的作用下取第r个属性值的

32、概率，其中k<a取 4/(兀)=maxcso),d/2(x)，l，勺同(兀)，令 m(ii (x) = i: a (x) = au(x),于是对于 vx, y e x , 映射族f可以诱导一个二元关系0：兀心当且仅当mai(x) <r mai(y).该二元关系具有自 反性和传递性.事实上，vxg x ,由于mai(x)<m(ii(x),因此冇刃“；若色,”zwx,冇 xry , yrz ,则由 m仰(力5陆“(刃，得到 m©(x)wm©(z),即.因此从集 合x到偏序集(r,<)±的映射族f可以确定一个概率信息系统.下面说明从集合x到偏序集

33、(r,<)±的映射族f可以确定一个格值信息系统创.记 yn =yxyxl xy ,令ad) = (q(%!),a2(兀i),l ,an(xj)g yn,a(x2) = (al(x2),a2(x2),l ,an(x2)e yn,l。(兀”)=(q(xm),a2(xw),l ,an(xw)e y且规定vi <i,j<m, ax<ax.)当且仅当/k<n ,有(兀)5,于是易知映射族f 可以诱导一个具有自反性和传递性的二元关系心兀心当且仅当awg在(y"，s) 上定义二元运算v, a：。(耳)7 a(x.)=(舛(兀)7 坷(xy), a2 (兀)v

34、 a2 (y ),l ,an (xz) v an (x.), aiz(xy) = (a】(兀)aax(x.),勺(兀)aa2(© ),l ,a”(x,.) aan(x.) 则(f,<)是一个格,其中1 =(1,1,l j), 0=(0,0,l ,0)为最大元和最小元.于是，集合x到 偏序集(/,<)±的映射族f可以确定一个格值信息系统.由于格值信息系统是最广泛的信息系统，对其的研究结果适合于任何信息系统，因此 可以用上述二元组来表示所有的信息系统.2.3信息系统的基本概念及定理设(xjj )为信息系统,x=xpx2,l xm , j =/?,/?2,l，/?j

35、,对于 xex ,记 x = yex:xry,reu ，设1/为二元关系族j子集族，即1/ cu，则有以下性质成 立：性质2.1当j ev 2 cu吋，兀n珂2=珂(2) j=x :xe x是 x 的一个覆盖.(3)当)©打吋，c|xf 定义2.2设(xjj )是信息系统，对于任意kcx , 7 cu , ill& (y) = xey:xx c/,rv (y) = xey:xx i yh0称& (y)和瓦(y)分别为对彖集y关于信息系统(xu )的下近似和上近似.由定义2.2矢口，血(丫)中的元素必屈于丫，因此也称& (丫)为丫的v正域；x-rv (丫) 中的

36、元索必不属于y,因此也称x-rv (y)为y的v 负域；而瓦(y)-& (y)中既有属于 y的元素，也有不属于y的元素，因此称z为边界域.设(xjj)是一个信息系统，若y cu，则对于任意r,zcx，则有以下性质成立： 性质 2.2(1)垃(y)yrv (7)；(2) & (丫)=瓦(y), rv &)=& (y);(3) 血(0) = 0= (0) , & (x) = x=rv (x)；(4) & (yi z) = &(r)i ry (z), rv (kuz) = (y)u瓦(z)；(5) &(ruz)o (y)u©

37、(z), rv (yi z)u 瓦(7)1 rv (z)；(6) (r)o (z),瓦(丫)匸瓦(z)；(7) & (y) = & (& (y), rv (k) = (rv (/).定义2.3 "设(x,s)是偏序集，若对于任意的兀,x ,都有一个实数d(y/x)满足:(1) ()<d(7x)<l；(2) x < y => d(y /%) = 1 ；(3) x<y<z=> d(x/z)< d(x/y)；则称d是x上的包含度.例2.1设j=xx :xex是集合x上的一个覆盖，p(x)表示集合x的全体子集， “匸”表

38、示集合的包含关系，则(p(x)£)为偏序集，若记 d(yx /可)=|可i 疝|/|町则d是丿上的包含度.证明：显然|町i )亦|/|h |>o,又叮i 为c%k ,因此|可i 班|/|kv |<i, 所以有0<d(yx /xx )0;若可 口刑，则阿i 珂=可，因此»(切/可) = 1; 若可cy；旳，那么同i yx =可=kv i 叮且|凤|如|，因此有 d(可/zx )<d(xx /yx )故q是丿上的包含度.定理2.1设(xjj )为信息系统，其中x=w，a：2，l心,定义x上具有自反性、传递 性的二元关系a，®)wxxx:兀则对于

39、xox, v cu ,以下条件等价：(1) 对于任意xx , £>(%,.v /x,.j； ) = 1,其中d为包含度；(2) uk =xj ;(3) (绷=1.a s证明：d为包含度,d(x, v ix ) = 1当且仅当mi匸比1；，又对于y cu ,有 x(x m ,因此(1)0;对于任意的yenr9 &(r)cy,从而(r)|<|x|,yr所以(2)0(3).2. 4本章小结本章提出了信息系统的一个新的表示方式，即将信息系统定义为对彖集和对彖集上具 有门反性、传递性的二元关系族组成的二元组，证明了以信息函数表达的信息系统于该表 达方式是等价的0®

40、.然后采用自反、传递的二元关系族诱导的函数表示信息系统的属性, 说明了该表达方式的一般性，最后给出了在新的表达方式下的上近似、下近似、包含度等 基木概念和相关性质、定理.第三章简单信息系统的属性约简对信息系统的分析关键在于屈性约简，即从大量的、杂乱无章的数据屮捉取出冇利用 价值的信息，因此屈性约简方法的好坏，决定了能否得到可用的信息.本章提出了分离多 项式概念，它是由分离子（等价关系的补）经过有限次交运算、并运算的表达式，然后采 用极小元法，简化了由分离析取范式到分离合取范式的转换，减少了信息系统属性约简算 法的时间和空间开销，捉高了计算机运行的效率，并用一个实例进行了分析.最后研究了 信息函

41、数z间的复合运算及相关性质，得到信息函数的最大公因式计算方法阿.本章的具体安排如卜3.1节首先给出了型的定义，然后提出了分离多项式的概念， 并定义了分离属性集族，之后给出了基于分离属性集族的约简法的理论基础门3.2节给出 了极小元属性约简法的步骤，并进行了举例分析；3.3节介绍了属性的运算；3.4节对本 章进行了小结.3.1信息系统的分离属性集定义3.1设（xjj ）是简单信息系统，对象兀wx的等价类表示为刘尺二ywx,刃, 其对应的划分为 = i映射q : x t% =沖,5称为二元关系族的j的型，记作丁，如杲j =/?则简记作也 对于定义域为x的映射族 a,其在x上等值关（x, y）: a

42、（x） = a（y）, ae a所确定的型称为映射族a的型,记作直 如果a = a则简记作弘定义3.2设（x,f ）为信息系统，其中f =a9a2,l ,an称集合 e = （坷（兀）卫2（兀）丄，色（兀）1兀w x为 信 息 系 统（x,f ）的模式 空间，向量 （°1（兀）,°2（兀）丄an （x）为兀w x的模式,映射q:x a（x） = （t/j（x）,a2（x）,l ,an（x） xe x .为映射族f的合成映射.定理31设a = a19a2,l ,aj, a为映射族a的合成映射,则屣弘设人二阿宀丄卫”是定义域为x的映射族，其中x=xpx2,l ,x,j为对象集.

43、对于定 义域为x的映射空确定了 x上一个等值等价关系，在不引起混淆的情况卜“仍用a表示, 即a = （兀，刃w x xx : a（x） = a（y）.记万=x xx-a , 丁“是= x xx , al ci =.由人确定的等价关系= a2ili色称为合成等价关系（以下总假定等价关系是 非平凡等价关系）.映射族a的合成映射为。（兀）=（坷（兀）,色,l ,色（兀），xe x ，用 aa2 al心“表示映射族b的合成映射，它与勺1 a2i l i a“具有相同的型.定义3.3如果(x,y)ea 9称x与y关于等价关系a或映射a是可分的，否则称x与y关 于。是不可分的.如果(x,y)g a. i

44、z721 l i an，则表明兀与y关于映射族a中每一个映射是可分的， (兀,y)w%u込ul un”，则表明兀与y关于映射族a中至少一个映射是可分的.定义3.4曲等价关系的补经过右限次并运算和交运算组成的表达式称为分离多项式； 称m = bxlb2lbk为分离小项，m =£呱ul u瓦为分离大项，其屮勺wa, i = l,2,l,£.由若干分离小项的并组成的表达式称为分离析取范式，由若干分离大项的交 组成的表达式称为分离合取范式.显然，分离大项m=bluh2ul u瓦是等价关系勺i $il i q的补.定义35设a = ava2,l ,an为对象集x=xpx2,l ,xm

45、上的等价关系族如果bu a , 屣夙 则称3是a的协调集；如果b是人的协调集且对于b的任何真子集c,都有鈴厲 则称是a的约简.定义3.6对于xj,xjg x，记ai =ae a:(xj9xj)e a为a中口j分兀与厂的全部属性集， 简称分离属性集.称a. :1</</"为信息系统(x,a)的分离属性集族.定理3.2设州为信息系统(x,a)的分离属性集，则有以下性质：(1) a,=0, (i<n).(2) atj:<i< j<n是对称的.(3) 码匸九 u比，(v/j<n).证明:和(2)显然成立.要证(3),只需证x/au码,有a岸抵.若a浮

46、九u州, 则at e aik 且qg %,于是al(xi) = al(xk)且at(xk) = at(xj)，则有al(xj) = al(xj),所以at atj, 即证.定义3.7设a = a,a2,l 为对象集x二西,七丄，兀” 一上的等价关系族，若 屣a-临，贝u称属性©是核心元素或绝对必要属性.定理3.3设a = ara2,l ,an使是定义在x上的映射族，分离屈性集族 a.：l</< j<n有以下性质：(1) ba，使b 4严0, &j当ii仅当 4 奚.(2) 记4)= 州：心丿醛弘当且仅当对任意cua, bi c = 0 ,必有cea。(3)

47、必为核心元素当且仅当存在兀，xj(i$ j),使aij = al.证明：(1)设a.h分别为映射族4 , b的合成映射，若s工八每工0 ,则存在气e b 使气.w a.,即气(旳)工气(®),则有刚傍i 讣=0又be a ,有x,.cx.,勺匹x», 由i,丿的任意性，有i兀»=切朋，%7v=|x-k，所以醛系.反之，若篦乂，则vx,. g x , 冇兀尿=兀切 当兀汗兀佻时，冇兀沱比炉从而兀从w傀=0，所以存在听b,使得 alt< g a.,即 bi 每工0, &j.(2) 由(1)可得.(3) 设吗为核心元索，若任意包含q的分离属性集au&

48、;j中至少有两个元索，令 b=u(a u),则bi州工0(心力，由(1)知，有胆系，则存在cyb使c是约简，那 么qwc就与a,是核心元素孑盾了.反z,若存在舌，x j (i工j),使4/=。/，则 /ak a-af,有 ak(xi) = ak(xj),即屣 a-©,因此 q 必为核心元素.定理33说明了信息系统的展性约简可以利用分离属性矩阵来计算，即寻找满足条件 bi a.工0 (i h ;)的最小映射族b例3.1考虑表3. 1所示的信息系统(x,a),表3. 2为信息系统(x,a)的非空可分离集 族每：lgv j<5.表3.1ahcde00000x201101兀310110

49、1111010111表3.21234512bee3ci c dabed4abeda d eb5acea bc db d eb = h,c,cl,由定理 3.3 知，b 是协调集，且 b,=/2,c, b2=b,d, $=c,d均不满足定理3.3,因此b信息系统(x,小的一个属性约简.设b, :/</为信息系统(x,a)属性约简的全体，则id为核心属性集，即集合ib,中/=1 /=1的元素都是绝对必要属性；u.-i bi为相对必要属性集；a-ub,为绝对不必要属性集./=! /=! /=!3.2极小元属性约简法b是a的约简，当且仅当b是集合族c:cua,脸留关于集合包含关系的极小元.若 a

50、i =ae a:(xi9x.)e a是分离属性集,则州工0当且仅当(x,xy)g ax i a21 l i aw定义3.8对于属性集族a : a. 0,0 < i< j <n,称分离多项式f= u伽为信息系 统(x,a)的分离析取范式，其中a. 为分离小项；在非空属性集族 a.：a. 0,o<z<j<n中，关于集合包含关系的极小元设为人,短丄，4，称分离多项式 f= u %为信息系统(x,a)的简单分离析取范式，其屮=1©：*4为分离小项.isi “定理3.4设尸=u叫为信息系统(x,a)的简单分离析取范式，则f = al alll atl l&l

51、t;i<k证明 由 “ =i a:ae at u 哥 ua2 ul ian =al a2l l i an ,有f u % i a? i l i % ； 对于任意勺1 l i %=n|un2ul u瓦，可知每h0,设4(= a.为关于集合包 含关系的极小元，注意到m. u mt ,则(兀，兀jw c u m. - f .这就证明了f = aj a2i l i an .定理3.5设a = a,al ,am为对象集x上等价关系族，如果i m产吗i勺i l i a”， 其中m,为分离大项，则m,=ax a2lli an, z = l,2,l，/证明 设分离大项m严bj l i俵由定理条件知勺i勺

52、i l i a” u / ；由 q i勺i l i色uq i $ i l i bk及德摩根律有=勺1筠1 l i q uqll i色，所以 m. =aa 禺 i l i an /ixfl设非空分离属性集族州：每工0,ogv j<n屮有r个极小元人人丄，比，b = bpfi2,l ,坊为每一个非空分离属性集£,厂=1,2丄，/:中选取一个元素的组合全体. 对于b,wb, j = l,2,l/,记m严u:awd.根据集合交运算和并运算的分配律， 则u叫二1 mj,其屮777. =1 ataea为分离小项.由定理3.5冇<i<k1</</推论对于任意vbgb，

53、总有m = ua : ae b = ax a21 l i am .定理3.6如果cua,匪#,则存在beb使得buc证明 设(7 = cpc2,l u a ,#对于(xz,)g q i 色 i l i am = q i c? i l i q ,总存在cwc使得(%;.,x.)ec ,这表明每一个非空集合每小均有c的元素，因而极小元 £d，l人中每一个均有c的元素，即3beb*使得buc定理3.7 a的约简全体为bl证明 设50eb*,由定理7有确二弘设c是a的一个约简且cub°，因c u 4 ,匪甲, 由定理9, hbwb*使得buc,而为b中关于包含关系的极小元，得b =

54、 c = b°,证 明了 b屮极小元是a的约简.设c是4的一个约简，由定理8,存在beb*,使得buc, 由免系及约简定义得b = c,即人的约简是b小关于包含关系的极小元.设b*=bpb2,l 则定理 3.8 uar = usr r=lr=l证明显然u ar z) u b,若有el,2,l j使得ar -ubr0,则存在c r e a -ubrr=lr=l° r=l0° r=l及1g° < j0<n使得盅=九j°,曲于比是极小元，它不包含其它非空分离属性集族人，在盅 以外的非空分离属性集族中各取一个元素cr e - a.，得到在非

55、空分离属性集 4.，厂= 1,2,l ,k中选取一个元素的组合c,c2,l ,qg b ,于是mbwb*使得 b cz cpc2,l ,cj .由于b , b可分离于七故有不同于仏的可分离于牡，这 与 w ar - af.矛盾.rrml推论 a-jar=a-jbr.r=lr=l推论表明：通过对非空分离属性集族求极小元，可以确定全部的绝对不必要属性.例32考虑表3.3所示的信息系统(x, 4)；表34是非空可分离集族每:1</< j<5； 表3. 5是关于包含关系的极小元集族，为£=a,d, %=d,w,因此，绝对不要属性为a-vsar=b,c. r=l表3.3ahc

56、de112111221121321232431242531253表3.41234512ab d3a b c cl ec d e4a b c d ea c d eci d5a b c d ea c d ea d ed e表3.5123451234a d5d e下面给出属性约简的计算步骤及例子.设x=xpx2,l ,xj , "也宀丄,am为x上等价关系族.非空属性集族 每：每式0,09 v j<n中关于集合包含关系的极小元为£4，l，人,b = bpb2,l 为 每一个非空属性集a中选取一个元素的组合全体.算法计算aij=aea:(xj,xj)ea0,比较该集族中集合，将具冇包含关系的子集留 下，得到关于集合包含关系的极小元为am2,l ,4第一步，如果,4均为单元索集合，则得到惟一的约简b=jai1 口空第二步，如果a，a2,l ,4中冇多于一个元索的集合，选非单元索集合中的一个元索g， 将a,a,l ,£分成含a的一组:aucpa)uc2,l，uc，和不含a的一组 cr+i,cr+2,l ,