《经典粗糙集理论.ppt》由会员分享，可在线阅读，更多相关《经典粗糙集理论.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法经典粗糙集理论 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.2 不可分辨关系不可分辨关系（Indiscribility relation 令令aA，xU，f(x,a)Va；对于任一子集；对于任一子集P A A，在，在U U上的不可分上的不可分辨关系辨关系I I定义为：定义为：I
2、=(x,y)I=(x,y)UU：f(x,q)=f(y,q)qP 若若(x,y)I I，则则称称x x和和y y是是不不可分辨的。可分辨的。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.2 不可分辨关系不可分辨关系Indiscernibility relation 显然，这样定义的不显然，这样定义的不可分辨关系是一个等价可分辨关系是一个等价关系关系(自反自反 的、对称的、的、对称的、传递的）。传递的）。包含对象包含对象x的等价类的等价类记为记为I(x)。等价类与知等价类与知识粒度的表达相对应，识粒度的表达相对应，它是粗糙集主要概念，它是粗糙集主要
3、概念，如近似、依赖及约简等，如近似、依赖及约简等，定义的基础定义的基础上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法 粗糙集的主要思想粗糙集的主要思想 粗糙集的主要思想是基于不可分辨关系，粗糙集的主要思想是基于不可分辨关系，每一个对象与一些信息相联系，且对象仅能每一个对象与一些信息相联系，且对象仅能用获得的信息表示。因此，具有相同或相似用获得的信息表示。因此，具有相同或相似信息的对象不能被识别。论域的不可分辨对信息的对象不能被识别。论域的不可分辨对象形成了不可分辨对象的聚类，即知识粒度。象形成了不可分辨对象的聚类，即知识粒度。用于近似的知识将用于近
4、似的知识将U划分为由条件属性集判划分为由条件属性集判断是不可分辨的对象元素集，元素集被视为断是不可分辨的对象元素集，元素集被视为用于近似的用于近似的“知识粒度知识粒度”；被近似的知识将；被近似的知识将U划分为由决策属性集生成的决策类，在此划分为由决策属性集生成的决策类，在此基础上，用一种知识近似另一种知识。基础上，用一种知识近似另一种知识。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.3 粗糙近似粗糙近似上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.3 粗糙近似粗糙近似定义定义 给定一个信息系统
5、（知识表示系统）给定一个信息系统（知识表示系统）S=(U,A,V,f)，A=CD上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.3 粗糙近似粗糙近似 集合集合X的下近似实际上是由那些根据已有知识判断的下近似实际上是由那些根据已有知识判断肯肯定属于定属于X的对象所组成的最大的集合，也称为的对象所组成的最大的集合，也称为X的正区的正区,记记作作pos(X)(X)；集合集合X X的负区的负区neg(X)neg(X)为为根据已有知识判断根据已有知识判断肯定不属于肯定不属于X的对象组成的集合的对象组成的集合;集合集合X的上近似的上近似由所有与由所有与X相交
6、非空的等价类的并集组相交非空的等价类的并集组成成，即那些可能属于，即那些可能属于X的对象组成的最小集合。的对象组成的最小集合。集合集合X的边界区的边界区bnd(X)bnd(X)为集合为集合X的上近似与下近似之差的上近似与下近似之差，如果如果bnd(X)bnd(X)是空集，则称是空集，则称X关于关于I是清晰的；反之如果是清晰的；反之如果bnd bnd(X)(X)不是空集，则称集合不是空集，则称集合X关于关于I是粗糙的。是粗糙的。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.4 粗糙隶属函数粗糙隶属函数上一页上一页下一页下一页返回本章首页返回本章首
7、页粗糙集的基础理论和方法粗糙集的基础理论和方法2.4 近似精度与近似质量近似精度与近似质量上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 算例算例表表1所示的关于全球变暖的一个信息系统所示的关于全球变暖的一个信息系统,a1太阳能太阳能(Solar energy)，a2火山活动火山活动(Volcanic activity),a3二氧化碳含量（二氧化碳含量（Residual CO2,），），d温度温度（Temperature）上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 算例算例 对论域进行划
8、分，可得如下等价类对论域进行划分，可得如下等价类 U/C=X1,X2,X3,X4,X5,X6其中：其中：X1=n1，X2=n2，X3=n3，X4=n4,n5,n6,n9，X5=n7，X6=n8YL=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=n8YL=n2,n3,n4,n5,n6,n8，YH=n1,n7,n9据此可求得粗糙近似如下据此可求得粗糙近似如下:YL的下近似：的下近似：aprapr(
9、Yn)=n2,n3,n8YL的上近似：的上近似：n2,n3,n4,n5,n6,n9YH的下近似：的下近似：aprapr(Yp)=)=n1,n7YH的上近似：的上近似：n1,n7,n4,n5,n6,n9 YL的分类精度的分类精度=3/6=0.5YH的分类精度的分类精度=2/6=0.33 分类质量分类质量=5/9=0.56上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.5 属性约简与核属性约简与核上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.6 决策规则决策规则上一页上一页下一页下一页返回本章首页返回
10、本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.7 约简算法约简算法上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.7 约简算法约简算法 约简对于在模型中分类对象最终构建约简对于在模型中分类对象最终构建一系列规则是重要的，有关的文献探讨一系列规则是重要的，有关的文献探讨了约简的两个主要方面，一方面是为给了约简的两个主要方面，一方面是为给定的系统寻找约简的问题，这个问题是定的系统寻找约简的问题，这个问题是一个一个NP完全问题，常见的约简算法有：完全问题，常见的约简算法有：快速约简、遗传算法、动态约简、相容快速约简、遗传算法、动态约简、相容性
11、约简等。性约简等。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法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=n
12、1,n4,n6，X2=n2，X3=n3，X4=n5，X5=n7U/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=n7YN=n1,n2,n3，YP=n4,n5,n6,n7Yn的下近似：的下近似：aprapr(Yn)=n2,n3 Yn的上近似：的上近似：apr(apr(Yn)=n2,n3,n4,n1,n6Yp的下近似：的下近似：aprapr(Yp)=)=n5,n7 Yp的上近似：的上近似：apr
13、(apr(Yp)=)=n5,n7,n4,n1,n6 Yn的分类精度的分类精度=2/5=0.4YP的分类精度的分类精度=2/5=0.4 分类质量分类质量=4/7=0.57上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 求约简算例求约简算例U/D=YN,YP以以a1对对论论域域进进行行划划分分，我我们们求求分分类类质量：质量：YN=n1,n2,n3，YP=n4,n5,n6,n7X1=n1,n2,n4,n6，X2=n3,n5,n7，因此分类质量为：因此分类质量为：分类质量分类质量=0/7=0 显然属性显然属性a1不是约简。不是约简。上一页上一页下一
14、页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 求约简算例求约简算例U/D=YN,YP以以属属性性集集a1,a2对对论论域域进进行行划划分分，我们求分类质量：我们求分类质量：YN=n1,n2,n3，YP=n4,n5,n6,n7X1=n1,n2,n4,n6，X2=n3,n5,n7，因此分类质量为：因此分类质量为：分类质量分类质量=0/7=0 显然显然属性集属性集a1,a2不是约简。不是约简。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 求约简算例求约简算例U/D=YN,YP以以属属性性集集a1,a3对对论论
15、域域进进行行划划分分，我们求分类质量：我们求分类质量：YN=n1,n2,n3，YP=n4,n5,n6,n7X1=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,
16、a3构构造造的的决决策策规则为规则为:If a11a3=2 then d=N 支持对象数支持对象数 1If a12a3=1 thend=N 支持对象数支持对象数 1a12a3=2 then d=P 支持对象数为支持对象数为2分类质量分类质量=4/7=0.57上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 算例算例表表1所示的关于全球变暖的一个信息系统所示的关于全球变暖的一个信息系统,a1太阳能太阳能(Solar energy)，a2火山活动火山活动(Volcanic activity),a3二氧化碳含量（二氧化碳含量（Residual CO2
17、,），），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=n7YL=n2,n3,n4,n5,n6,n8，YH=n1,n7,n9显然，属性显然，属性a1的的分类质量小于总的分类质量
18、，属性分类质量小于总的分类质量，属性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=n7YL=n2,n3,n4,n5,n6,n8，YH=n1,n7,n9分类质量分类质量=5/9=0.56，与整个属性集的分类质量相同，与整个属性集的分类质量相同因此，属性子集因此，属性子集a1,a2是约简。是约
19、简。上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法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=n8YL=n2,n3,n4,n5,n6,n8，YH=n1,n7,n9分类质量分类质量=5/9=0.56，与整个属性集的分类质量相同，与整个属性集的分类质量相同因此，属性子集因此，属性子集a1,a3也是约简。也是约简。上一页上一页下一页下一页返回本章首页返
20、回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法2.8 求约简算例求约简算例上一页上一页下一页下一页返回本章首页返回本章首页粗糙集的基础理论和方法粗糙集的基础理论和方法数据离散数据离散 粗糙集理论分析要求，数据必须以类别的形式出现。因粗糙集理论分析要求，数据必须以类别的形式出现。因此，连续数据必须首先进行离散化处理，离散的结果可能会此，连续数据必须首先进行离散化处理，离散的结果可能会减小原始数据的精度，但将会提高它的一般性。减小原始数据的精度，但将会提高它的一般性。数据离散问题是一个数据离散问题是一个NP完全问题，数据离散可分为专家完全问题，数据离散可分为专家离散与自动离散，专家离散指由
21、某一领域的专家根据他的判离散与自动离散，专家离散指由某一领域的专家根据他的判断或使用该领域确定的标准进行的离散；自动离散指按自动断或使用该领域确定的标准进行的离散；自动离散指按自动定义的方式进行的离散，定义的方式进行的离散，自动离散方法又可分为有监督离散法和无监督自动离散法，自动离散方法又可分为有监督离散法和无监督自动离散法，无监督离散法可视为一个简单的聚类过程，无监督离散法可视为一个简单的聚类过程，如等频率区间法、如等频率区间法、等大小宽度区间法。有监督的的离散化方法又可分为两类，等大小宽度区间法。有监督的的离散化方法又可分为两类，全局离散方法与局部离散方法。全局离散方法与局部离散方法。注注:将信息系统中的连续型数据离散为粗糙集模型可用的数将信息系统中的连续型数据离散为粗糙集模型可用的数据时，会产生潜在的信息损失，这个问题值得探讨。据时，会产生潜在的信息损失，这个问题值得探讨。