粗糙集的数学结构

第1章 一般关系下的粗糙集 本章给出无限论域中基于一般二元关系的粗糙近似算子的构造性定义和公理化刻画. 1.1 Pawlak粗糙集的基本概念 本节介绍Pawlak粗糙近似的概念及基本性质，详细内容见文献[86]. 设U是非空集合，U中的子集全体(即U的幂集)记为P(U).对于X，记，称为集合X与Y的差，特别地，记，称.X为X在U中的补集.若X是有限集，则记为集合X的基数，即X中的元素个数. 定义1.1 设U和W是两个非空论域，称是从U到W的一个二元关系.若，则记，称y为x关于关系R的后继，简称为后继，x为y的前继，记 Rs(x)称为x关于关系R的后继邻域.若，则称R是串行的(serial)(有的文献称双论上的这种关系为区间关系(interval relation)，而单论域上的这种关系为串行关系[156]).若U=W，则称为U上的一个二元关系.对于U上的二元关系R，称关系R是逆串行的，若，存在使，即;称关系R是自反的，若，有，即;称关系R是对称的，若，蕴涵;称关系R是传递的，若，与蕴涵;称关系R是欧几里得的，若，和蕴涵;称关系R是相容的，若R是自反和对称的;称关系R是预序关系(preorder)，若R是自反和传递的;称关系R是等价的，若R是自反、对称和传递的二元关系. 若R是U上的等价关系，对于，记称为x的等价类.U=R是U上由R生成的等价类全体，也称商集，它构成了U上一个分划.可以证明，U上的分划可以与U上的二元等价关系之间建立一一对应. 定义1.2 设U是非空有限论域，是U上的二元等价关系，R称为不可分辨关系，序对(U，R)称为Pawlak近似空间，若，则称对象x与y在近似空间(U，R)中是不可分辨的.U=R中的集合与空集称为基本集或原子集.若将U中的集合称为概念或表示知识，则(U，R)称为知识库，原子集表示基本概念或知识模块.对于U上任意一个集合X，若它能表示为基本集的并，则称X为可定义集，否则称X为不可定义的.可定义集也称为精确集，它可以在知识库中被精确地定义或描述，可表示已知的知识.对于论域U上任意一个子集X，X不一定能用知识库中的知识来精确地描述，即X可能为不可定义集，这时就用X关于近似空间(U，R)的一对下近似R(X)和上近似R(X)来近似地描述: (1.1) 分别称为下近似算子和上近似算子，简称Pawlak近似算子，也称为由近似空间(U，R)导出的近似算子;R(X)又称为X关于近似空间(U，R)的正域，记作POSR(X)，它解释为由那些根据现有知识判断出肯定属于X的对象所组成的集合，R(X)解释为由那些根据现有知识判断出可能属于X的对象所组成的集合;.R(X)称为X关于(U，R)的负域，记作，它解释为由那些根据现有知识判断出肯定不属于X的对象所组成的集合;称为X关于(U，R)的边界域，记作，它解释为由那些根据现有知识判断出可能属于X但不能完全肯定是否一定属于X的对象所组成的集合.由于R是等价关系，可以证明，X关于近似空间(U，R)的近似集可以等价地定义为如下形式: (1.2) 从(1.2)式可以看出，下近似R(X)是(U，R)中含在X中的*大可定义集，而上近似R(X)是(U，R)中包含X的*小可定义集，因此，X是可定义的当且仅当，而X是不可定义的当且仅当R(X)6=R(X)，这时称X关于(U，R)是粗糙的，称序对是一个Pawlak粗糙集.称系统为一个Pawlak粗糙集代数系统，简称为Pawlak粗糙集代数. 定理1.1[86，179] 设(U，R)为一个Pawlak近似空间，R与R是由它导出的Pawlak近似算子，则以下性质成立: 性质(L1)与(U1)表明近似算子是一对对偶算子，常称为对偶性质，具有相同数字标号的性质也可以看成对偶性质. X关于(U，R)的近似质量定义为 近似质量反映了知识X中肯定在知识库中的部分在现有知识中的百分比.X关于(U，R)的粗糙性测度定义为 显然， X是可定义的当且仅当粗糙性测度反映了知识的不完全程度. X关于(U，R)的近似精，度定义为 它反映了根据现有知识对X的了解程度. 粗糙集理论还对于集合类关于近似空间定义了下近似和上近似，从而该理论可应用于分类问题.设;是由U的子集所构成的集类，则F关于近似空间(U，R)的下近似R(F)和上近似R(F)分别定义为 这时，F关于(U，R)的近似精度.R(F)和近似质量分别定义为 特别地，当F也是U的分划时，F关于(U，R)的近似质量在判断一个决策表是否协调以及在规则提取中有重要的应用. 粗糙集理论中的知识表达方式一般采用信息表或称为信息系统的形式，它可以表示为四元有序组， (有时简记为二元组(U，A))，其中U是有限非空对象全体，即论域;A是有限非空属性全体;是属性a的值域，是信息函数 ，反映了对象x在S中的完全信息. 对于这样的信息系统，每个属性子集定义了论域U上的一个二元等价关系，即，定义RB如下: 由此可见，信息系统类似于关系数据库模型的表达方式.有时属性集A还可分为条件属性集C和决策属性d，这时的信息系统称为决策表或决策系统，记为，其中. 无决策的数据分析和有决策的数据分析是粗糙集理论在数据分析中的两个主要应用.粗糙集理论给出了对知识(或数据)的约简和求核的方法，从而提供了从信息系统中分析多余属性的能力.设，是一个信息系统，记由属性集所导出的等价关系为，若，则称属性a是多余的;若在系统中没有多余属性，则称A是独立的;属性子集称为A的约简，若RB=RA且B中没有多余属性，约简的全体记为red(A);A的所有约简的交集称为A的核，记作core(A).一般属性的约简不唯一而核是唯一的. 粗糙集数据分析方法除了给出对知识(或数据)的约简和求核的方法外，还提供从决策表中抽取规则的能力，该方法可以做到在保持决策一致的条件下将多余属性删除. 在一个决策表中，记 若，即有，则称决策是协调的，否则称为不协调的. 从协调的决策表中可以提取确定性规则;而从不协调的决策表中只能抽出不确定性规则或广义决策规则，这是因为在不协调的系统中存在着矛盾的事例. 决策表中的决策规则一般可以表示为 其中称为规则的条件部分，而(d，w)称为规则的决策部分.决策规则即使是*优的也不一定唯一. 在决策表中抽取规则的一般方法为 (1)在决策表中将信息相同(即具有相同描述)的对象及其信息删除只留其中一个得到压缩后的信息表，即删除多余的重复事例; (2)删除多余的属性; (3)在每一个对象及其信息中将多余的属性值删除; (4)求出属性约简; (5)根据*小约简，求出逻辑规则. 1.2 二元关系导出的邻域算子系统 本节从一个一般二元关系出发构造由它生成的邻域算子系统与粗糙近似算子系统，并讨论这些算子系统的性质. 定义1.3 设U是非空论域，R是U上任意二元关系，关系Rk称为由关系R导出的第步关系，定义如下 其中N表示正整数集. 显然， 很明显，当U是有限论域时，若，则对于k>n有.事实上，Rn就是R的传递闭包，当然Rn是传递的. 由U上任意一个二元关系R，可导出三个关系 显然，关系和都是对称的，并且 定理1.2 设R是U上的任意一个二元关系，则 (1)若R是传递的，则Rk也是传递的，并且Rk=R. (2)若R是对称的，则Rk也是对称的. (3)若R是自反的，则Rk也是自反的. (4)若R是串行的，则Rk也是串行的. (5)若R是逆串行的，则Rk也是逆串行的. (6)若R是欧几里得的，则Rk也是欧几里得的. 证明(1)-(5)的成立显然，我们只需证明(6)成立.设R是欧几里得关系，我们先证R2也是欧几里得关系. 设任意的满足和，则由定义知，存在使或 (a)假如xRy且xRz，由R的欧几里得性知yRz，从而由定义得yR2z. (b)假如xRy且xRz;z'Rz.结合xRy和xRz'，我们有z'Ry.从而结合z'Ry和z'Rz得yRz，于是yR2z成立. (c)假如xRy';y'Ry且xRz.类似于(b)可证yR2z成立. (d)假如xRy';y'Ry且xRz';z'Rz.结合xRy'和xRz'得y'Rz'，从而再结合y'Rz'和y'Ry可得z'Ry，这样由z'Ry和z'Rz可得yRz，于是yR2z成立. 由上述(a)-(d)知yR2z成立，即证R2是欧几里得的. 对于一般情形，注意到若且，则由R的欧几里得性可得yRz，从而由定义知yRkz对任意k2N成立，这样利用数学归纳法可证Rk是欧几里得关系. 定理1.3 设U是有限集，且，若R是U上串行和对称关系，则Rn是等价关系. 证明 由于R是串行的，于是由定理1.2知Rn也是串行的.则对任意x2U，存在y2U使xRny，又由R的对称性可知Rn也是对称的，从而yRnx.再由Rn的传递性知xRnx，即证Rn是自反的.这样证明了Rn是自反、对称和传递的二元关系，即Rn是等价关系. 引理1.1 若R和S是U上二元关系，则 (1) (2) 证明 (1)显然.