模式识别与智能计算-MATLAB技术实现（第5版）-课件 第八章+粗糙集分类器设计

模式识别与智能计算杨淑莹天津理工大学计算机科学与工程学院第八章粗糙集分类器设计8.1粗糙集理论的基本概念8.2粗糙集在模式识别中的应用8.3粗糙集理论的分类方法

8.1粗糙集理论的基本概念知识表达系统：

知识表达系统可用一个四元组S表示：式中,为一个非空有限对象的集合，称为论域＝｛X1，X2，…，XN｝,其中Xi为对象；R为对象的属性集合；V为属性值的集合，Va是属性a∈R的值域；f为R—>V的一个信息函数，它为每个对象X的每个属性a赋予一个属性值,即

a∈R，X∈,fa(X)∈Va。8.1粗糙集理论的基本概念决策表：设

是一个信息系统（知识表达系统），R＝C∪D，C称为条件属性集合，D称为决策属性集。具有条件属性和决策属性的信息系统称为决策表。

8.1粗糙集理论的基本概念等价关系：

设A代表某种属性集合。a代表属性中的某一种取值。如果有两个样品Xi，Xj满足如下关系：对于

，它们的属性值相同，即fa（Xi）＝fa（Xj）成立，称对象Xi和Xj是对属性A的等价关系，表示为可见属性值相同的两个样品之间的关系为等价关系。8.1粗糙集理论的基本概念等价集：

在中，对属性集A中具有相同等价关系的元素集合成为等价关系IND（A）

的等价集，［X］A表示在属性A下与X具有等价关系的元素集合。

8.1粗糙集理论的基本概念等价划分：

从所采集的训练集中把属性值相同的样品聚类，形成若干个等价集，构成A集合。在中对属性A的所有等价集形成的划分表示为具有特性：①Ei≠Ø；

②当i≠j时，Ei∩Ej＝Ø；

③

＝∪Ei。8.1粗糙集理论的基本概念

［例1］设

＝｛a（血压正常），b（血压正常），c（血压正常），d（血压高），e（血压高），f（血压很高）｝，

对于属性A（血压）的等价关系有

IND（A）＝｛（a，b），（a，c），（b，c），（d，e），（a，a），（b，b），（c，c），（d，d），（e，e），（f，f）｝

属性A的等价集有E1＝［a］A＝［b］A＝［c］A＝｛a，b，c｝

E2＝［d］A＝［e］A＝｛d，e｝

E3＝［f］A＝｛f｝

中对属性A的划分为A＝｛E1，E2，E3｝

＝｛｛a，b，c｝，｛d，e｝，｛f｝｝8.1粗糙集理论的基本概念上近似集和下近似集：

下近似集定义：对任意一个决策属性的等价集

，属性A的等价集

，有或表示等价集Ei＝［X］A中的元素X都属于Y，即

，则X一定属于Y。A_（Y）表示下近似集。8.1粗糙集理论的基本概念上近似集定义：对任意一个决策属性的等价集

，属性A的等价集Ei=[X]A，有或表示等价集Ei＝［X］A中的元素X可能属于Y，即

，则X可能属于Y，也可能不属于Y。A—（Y）表示上近似。8.1粗糙集理论的基本概念正域、负域和边界的定义：全集可以划分为3个不相交的区域，即正域（POSA）、负域（NEGA）和边界（BNDA）：正域：POSA（Y）＝A_(Y)负域：边界：由此可见：8.1粗糙集理论的基本概念从图8-1中可以看出：任意一个元素X∈POS（Y），一定属于Y；任意一个元素X∈NEG（Y），一定不属于Y；集合Y的上近似是其正域和边界的并集，即对于元素X∈BND（Y），无法确定其是否属于Y，因此对于任意元素X∈A—（Y），只知道X可能属于Y。

图8-1Y关于属性A的正域、负域和边界8.1粗糙集理论的基本概念粗糙集：若A—（Y）＝A_（Y），即BNDA（Y）＝Ø，即边界为空，称Y为A的可定义集；否则Y为A的不可定义集，即A—（Y）≠A_（Y），称Y为A的粗糙集（Roughset）。8.1粗糙集理论的基本概念确信度：确信度αA（Y）表示为其中||和｜A—（Y）-A_（Y）｜分别表示集合

、A—（Y）-A_（Y）中的元素个数。确信度性质：0≤αA（Y）≤18.1粗糙集理论的基本概念相对正域：设决策属性D的划分Y＝（Y1，Y2，…YM），条件属性C相对于决策属性D的正域定义为POS（C，D）＝∪C_（Yi）8.1粗糙集理论的基本概念决策表的一致性：

决策表中的对象X按条件属性与决策属性关系看做一条决策规则，写成

∧fCi（X）＝fD（X）式中，Ci表示多个条件属性；D表示决策属性；fCi（X）表示对象X在Ci的取值；∧表示逻辑“与”关系。（1）一致性决策规则定义如果对任一个对象Xi≠Xj，若条件属性有fCi（Xi）＝fCi（Xj），则决策属性必须有fD（Xi）＝fD（Xj），即一致性决策规则说明条件属性取值相同时，决策属性取值必须相同。该定义允许：若条件属性有fCi（Xi）≠fCi（Xj），则决策属

性可以是fD（Xi）＝fD（Xj）或fD（Xi）≠fD（Xj）。

（2）决策表一致的定义在决策表中如果所有对象的决策规则都是一致的，则该信息表示一致的，否则信息表示不一致的。在进行属性约简时，每约简掉一个属性时要检查决策表，若保持一致性，则可以删除，否则不可以删除。8.1粗糙集理论的基本概念8.1粗糙集理论的基本概念属性约简：

（1）属性依赖度：决策表中决策属性D依赖条件属性C的依赖度定义为

γ（C，D）＝｜POS（C，D）｜/｜｜式中，｜POS（C，D）｜为正域POS（C，D）元素的个数，｜｜

为整个对象集合的个数。γ（C，D）的性质如下：①若γ＝1，表示在已知条件C下，可以将

上全部个体分类到决策属性D的类别中去。②γ＝0，即利用条件C不能分类到决策属性D的类别中去。③0＜γ＜1，即在已知条件C下，只能将

上那些属于正域的个体分类到决策属性D的类别中去。8.1粗糙集理论的基本概念属性约简：

（2）属性重要度：C，D⊂A，C为条件属性集，D为决策属性集，a∈C，属性a关于D的重要度定义为SGF（a，C，D）＝γ（C，D）-γ（C-｛a｝，D）式中，γ（C-｛a｝，D）表示在C中缺少属性a后，条件属性与决策属性的依赖程度；SGF（a，C，D）表示C中缺少属性a后，导致不能被准确分类的对象在系统中所占的比例。SGF（a，C，D）的性质：①SGF（a，C，D）∈［0，1］。②SGF（a，C，D）＝0，表示属性a关于D是可约简的。③SGF（a，C，D）≠0，表示属性a关于D是不可约简的。8.1粗糙集理论的基本概念属性约简：

（3）最小属性集概念：设C，D分别是信息系统S的条件属性集和决策属性集，若属性集P（P⊆C）是C的一个最小属性集，当且仅当γ（P，D）＝γ（C，D）并且

时，则P具有与C同样的区分决策类的能力。8.1粗糙集理论的基本概念规则获取：

通过分析中的两个划分C＝｛Ei｝和D＝｛Yj｝之间的关系，把C视为分类条件，D视为分类结论，可以得到下面的分类规则：①当Ei∩Yj≠Ø时，则有：rij：Des（Ei）→Des（Yj）

Des（Ei）和Des（Yj）分别是等价集Ei和等价集Yj中的特征描述：当Ei∩Yj＝Ei时，即下近似，建立的规则rij是确定的，规则的可信度cf＝1。当Ei∩Yj≠Ei时，即上近似，建立的规则rij是不确定的，规则的可信度为②当Ei∩Yj＝Ø时，Ei和Yj不能建立规则。8.2粗糙集在模式识别中的应用表8-1决策表样例8.2粗糙集在模式识别中的应用等价集、下近似集和依赖度的计算：（1）条件属性C（a，b，c）的等价集E1｛e1｝，E2｛e2｝，E3｛e3｝，E4｛e4｝，E5｛e5｝，E6｛e6｝，E7｛e7｝，E8｛e8｝（2）决策属性D（d）的等价集Y1：｛e1，e4，e5，e8｝，Y2：｛e2，e3，e6，e7｝8.2粗糙集在模式识别中的应用等价集、下近似集和依赖度的计算：（3）决策属性的各等价集的下近似集C—Y1＝｛e1，e4，e5，e8｝C—Y2＝｛e2，e3，e6，e7｝8.2粗糙集在模式识别中的应用等价集、下近似集和依赖度的计算：（4）计算POS（C，D）和γ（C，D）POS（C，D）＝C—Y1∪C—Y2＝｛e1，e2，e3，e4，e5，e6，e7，e8｝｜POS（C，D）｜＝8，｜｜＝8，γ（C，D）＝1，表明在已知条件C（a，b，c）下，可将

上全部个体分类到决策属性D的类别中。8.2粗糙集在模式识别中的应用属性约简：a的重要度计算条件属性C（b，c）的等价集：E1｛e1，e4｝，E2｛e2｝，E3｛e3，e6｝，E4｛e5，e7｝，E5｛e8｝决策属性D（d）的等价集仍为Y1和Y2。决策属性的各等价集的下近似集：C—Y1＝｛e1，e4，e8｝C—Y2＝｛e2，e3，e6｝计算POS（C-｛a｝，D）和γ（C-｛a｝，D）：POS（C-｛a｝，D）＝C—Y1∪C—Y2＝｛e1，e2，e3，e4，e6，e8｝｜POS（C-｛a｝，D）｜＝6γ（C-｛a｝，D）＝6/8属性a的重要程度：SGF（C-｛a｝，D）＝γ（C，D）-γ（C-｛a｝，D）＝1/4≠0结论：属性a是不可省略的。8.2粗糙集在模式识别中的应用8.2粗糙集在模式识别中的应用表8-2简化决策表8.2粗糙集在模式识别中的应用等价集、上下近似集的计算：①条件属性的等价集：②决策属性D（d）的等价集：8.2粗糙集在模式识别中的应用获取规则：8.2粗糙集在模式识别中的应用规则化简：①对r11和r41进行合并，有（a＝0∨a＝1）∧c＝0→d＝0其中a的取值包括了全部取值，故属性a可以删除，即c＝0→d＝0②对r32和r62进行合并，有（a＝0∨a＝1）∧c＝2→d＝1同样，可以删除属性a，得到c＝2→d＝18.2粗糙集在模式识别中的应用最后的规则：①发烧＝正常→感冒＝否，即c＝0→d＝0②咳嗽＝否∧发烧＝低烧→感冒＝否，即a＝0∧c＝1→d＝0③发烧＝高烧→感冒＝是，即c＝2→d＝1④咳嗽＝是∧发烧＝低烧→感冒＝是，即a＝1∧c＝1→d＝1对于一个条件属性已知，决策属性未知的新对象，利用最后获取的规则，可以得到该对象的决策属性，实现模式分类。8.3粗糙集理论的分类方法决策表构造：8.3粗糙集理论的分类方法规则训练：规则训练是指利用粗糙集理论，通过对决策表进行条件属性约简、决策规则约简，获取最小决策规则，作为最终分类规则。（1）等价集、下近似集和依赖度的计算（2）属性约简（3）等价集计算（4）获取规则（5）规则化简

8.3粗糙集理论的分类方法分类判别：利用训练好的规则，对待测样品X，已知其条件属性（即特征），在训练规则中检索，找到符合规则，其决策属性即为其类别。8.3粗糙集