经典粗糙集理论.ppt

2 粗糙集,2.1 信息系统 设S=(U,A,V,f)为一个信息系统，也称为知识表示系统。其中，U= U1,U2,U3,U|u|为有限非空集合，称为论域对象空间；A=a1,a2,a3,a|A|为属性的非空有限集合。若A中的属性又可分为两个不相交的子集，即条件属性集C和决策属性集D，A=CD,CD= ,则S也称为决策表。 V=Va 其中aA， Va为属性a的值域；f：UAV为信息函数，对于aA，xU，f(x,a)Va，它指定了U中每一对象的属性值。,2.2 不可分辨关系 （Indiscribility relation,令aA，xU，f(x,a)Va；对于任一子集P A，在U上的不可分辨关系I定义为：I=(x,y)UU：f(x,q)=f(y,q) qP 若(x,y)I，则称x和y是不可分辨的。,2.2 不可分辨关系 Indiscernibility relation,显然，这样定义的不可分辨关系是一个等价关系(自反 的、对称的、传递的）。 包含对象x的等价类记为I(x)。等价类与知识粒度的表达相对应，它是粗糙集主要概念，如近似、依赖及约简等，定义的基础,粗糙集的主要思想,粗糙集的主要思想是基于不可分辨关系，每一个对象与一些信息相联系，且对象仅能用获得的信息表示。因此，具有相同或相似信息的对象不能被识别。论域的不可分辨对象形成了不可分辨对象的聚类，即知识粒度。用于近似的知识将U划分为由条件属性集判断是不可分辨的对象元素集，元素集被视为用于近似的“知识粒度”；被近似的知识将U划分为由决策属性集生成的决策类，在此基础上，用一种知识近似另一种知识。,2.3 粗糙近似,2.3 粗糙近似,定义 给定一个信息系统（知识表示系统）S=(U,A,V,f)，A=CD,2.3 粗糙近似,集合X的下近似实际上是由那些根据已有知识判断肯定属于X的对象所组成的最大的集合，也称为X的正区,记作pos(X)； 集合X的负区neg(X)为根据已有知识判断肯定不属于X的对象组成的集合; 集合X的上近似由所有与X相交非空的等价类的并集组成，即那些可能属于X的对象组成的最小集合。 集合X的边界区bnd(X)为集合X的上近似与下近似之差，如果bnd(X)是空集，则称X关于I是清晰的；反之如果bnd (X)不是空集，则称集合X关于I是粗糙的。,2.4 粗糙隶属函数,2.4 近似精度与近似质量,2.8 算例,表1所示的关于全球变暖的一个信息系统, a1太阳能(Solar energy)，a2火山活动(Volcanic activity) , a3二氧化碳含量（Residual CO2,），d温度（Temperature）,2.8 算例,对论域进行划分，可得如下等价类 U/C=X1, X2, X3, X4, X5, X6 其中：X1=n1，X2=n2，X3=n3，X4=n4,n5,n6,n9，X5=n7，X6=n8 YL=n2,n3,n4,n5,n6, n8，YH=n1, n7, n9,2.8 算例,X1=n1，X2=n2，X3=n3，X4=n4,n5,n6,n9，X5=n7，X6=n8 YL=n2,n3,n4,n5,n6, n8，YH=n1, n7, n9 据此可求得粗糙近似如下: YL的下近似：apr(Yn)=n2 , n3 ,n8 YL的上近似： n2 ,n3 ,n4,n5,n6,n9 YH的下近似：apr(Yp)= n1, n7 YH的上近似： n1,n7,n4,n5,n6,n9 YL的分类精度=3/6=0.5 YH的分类精度=2/6=0.33 分类质量=5/9=0.56,2. 5 属性约简与核,2.6 决策规则,2.7 约简算法,2.7 约简算法,约简对于在模型中分类对象最终构建一系列规则是重要的，有关的文献探讨了约简的两个主要方面，一方面是为给定的系统寻找约简的问题，这个问题是一个NP完全问题，常见的约简算法有：快速约简、遗传算法、动态约简、相容性约简等。,2.8 算例,下面通过一个简单的例子说明，如表1所示，S=(U,A,V,f)，其中U= n1, n2, n3, n4, n5, n6, n7,条件属性集C=a1, a2, a3 , a4, a5, a6，决策属性集D=d。,2.8 算例,对论域进行划分，可得如下等价类 U/C=X1, X2, X3, X4, X5 其中：X1=n1,n4,n6，X2=n2，X3=n3，X4=n5，X5=n7 U/D=YN,YP 其中：YN=n1, n2,n3，YP=n4, n5,n6, n7,2.8 算例,X1=n1,n4,n6，X2=n2，X3=n3，X4=n5，X5=n7 YN=n1, n2,n3，YP=n4, n5,n6, n7 Yn的下近似：apr(Yn) =n2, n3 Yn的上近似：apr(Yn) =n2, n3 , n4, n1, n6 Yp的下近似：apr(Yp)= n5, n7 Yp的上近似：apr(Yp)= n5, n7 , n4, n1, n6 Yn的分类精度=2/5=0.4 YP的分类精度=2/5=0.4 分类质量=4/7=0.57,2.8 求约简算例,U/D=YN,YP 以a1对论域进行划分，我们求分类质量： YN=n1, n2,n3，YP=n4, n5,n6, n7 X1=n1, n2,n4,n6，X2=n3, n5 , n7， 因此分类质量为： 分类质量=0/7=0 显然属性a1不是约简。,2.8 求约简算例,U/D=YN,YP 以属性集a1,a2对论域进行划分，我们求分类质量： YN=n1, n2,n3，YP=n4, n5,n6, n7 X1=n1, n2,n4,n6，X2=n3, n5,n7， 因此分类质量为： 分类质量=0/7=0 显然属性集a1,a2不是约简。,2.8 求约简算例,U/D=YN,YP 以属性集a1,a3对论域进行划分，我们求分类质量： YN=n1, n2,n3，YP=n4, n5,n6, n7 X1=n1,n4,n6，X2=n2，X3=n3，X4=n5,n7 因此分类质量为： 分类质量=4/7=0.57 由于a1,a3与全部条件属性集具有相同的分类质量，且为最小的条件属性子集，因此为约简。,2.8 求约简算例,可求得约简为： a1,a3，a4,a5，a5,a6 由约简a1 ,a3构造的决策规则为: If a11a3=2 then d=N 支持对象数 1 If a12a3=1 then d=N 支持对象数 1 a12a3=2 then d=P 支持对象数为2 分类质量=4/7=0.57,2.8 算例,表1所示的关于全球变暖的一个信息系统, a1太阳能(Solar energy)，a2火山活动(Volcanic activity) , a3二氧化碳含量（Residual CO2,），d温度（Temperature）,2.8 求约简算例,(1) 求整个条件属性集的分类质量：分类质量=5/9=0.56 (2) 求约简 由属性a1对论域进行划分，可得如下等价类 U/a1=X1, X2, X3, X4, X5, X6 其中：X1=n1,n3,n8，X2=n2,n4,n5,n6,n9，X3=n7 YL=n2,n3,n4,n5,n6, n8，YH=n1, n7, n9 显然，属性a1的分类质量小于总的分类质量，属性a1不是约简,2.8 求约简算例,由属性a1 , a2对论域进行划分，可得如下等价类 U/C=X1, X2, X3, X4, X5, X6 其中：X1=n1，X2=n2，X3=n3, n8，X4=n4,n5,n6,n9，X5=n7 YL=n2,n3,n4,n5,n6, n8，YH=n1, n7, n9 分类质量=5/9=0.56，与整个属性集的分类质量相同 因此，属性子集a1,a2是约简。,2.8 求约简算例,由属性a1 , a3对论域进行划分，可得如下等价类 U/C=X1, X2, X3, X4, X5, X6 其中：X1=n1，X2=n2，X3=n3，X4=n4,n5,n6,n9，X5=n7，X6=n8 YL=n2,n3,n4,n5,n6, n8，YH=n1, n7, n9 分类质量=5/9=0.56，与整个属性集的分类质量相同 因此，属性子集a1,a3也是约简。,2.8 求约简算例,数据离散,粗糙集理论分析要求，数据必须以类别的形式出现。因此，连续数据必须首先进行离散化处理，离散的结果可能会减小原始数据的精度，但将会提高它的一般性。 数据离散问题是一个NP完全问题，数据离散可分为专家离散与自动离散，专家离散指由某一领域的专家