下载掌阅APP，畅读海量书库
立即打开
|
1.2 粗糙集理论 |
粗糙集（Rough Set）是一种从数据中提炼知识并揭示暗含其中规律的数学工具，它能对各种不完备信息进行有效处理，并分析出隐藏的规律。属性约简是指在不影响整体决策分类能力的前提下，通过筛选重要或相关属性，用较少的重要属性总结出问题的正确决策。
粗糙集理论 [2] 的最大特点在于，它不需要任何额外的相关数据信息，仅仅依赖已存于数据内部的知识，通过数据之间的近似来表达知识的不确定性，所以它对问题的不确定性的描述或处理是比较客观的。
一般地，知识被认为是比较抽象的、具有普遍意义的理论，区别于传统知识的概念，粗糙集理论中的知识被看作是一种分类能力 [3～6] 。
定义
1.1 由所研究对象组成的集合U称为论域，它是非空的、有限的。对于U上的一个非空子集{X
1
，X
2
，…，X
n
}，若X
i
∩X
j
=∅，i≠ j，并且
，那么这个非空子集{X
1
，X
2
，…，X
n
}就是U上的一个划分。
定义 1.2 若集合A上的二元关系R满足自反关系、对称关系、传递关系，则称R是一个等价关系。对于∀a∈A，a关于R的等价类[a] R ={x | xRa}，简称[a] R 。用U R表示，对于论域U，在等价关系R下的一个划分。
定义 1.3 知识系统S可以表示成有序的四元组S=＜U，A，V，f ＞。其中，属性集A是由条件属性C和决策属性D的并集组成；V=∪ r∈A V r 为属性值的集合，V r 表示第r个属性的取值，f：U×A→V是一个映射函数，确定U中任意一个对象x的值。
定义 1.4 任意属性集∀P⊆A，知识系统S上的不可分辨关系IND（P），可定义为：IND（P）={（x，y）∈U×U：∀b∈P，b（x）=b（y）}。
如果（x，y）∈IND（P），则称x和y对P是不可分辨的。显然，不可分辨关系IND（P）为一等价关系，且IND（P）=∩ b∈P IND（{b}）。U IND（P）是不可分辨关系IND（P）对论域的一个划分，记作U P。
定义 1.5 对于任意子集∀X ⊆U，R为不可分辨关系，给出X 在知识系统S中关于R的下近似集合和上近似集合的定义：
称
为正域，NEG（X）=U-X为负域，
为边界域。
由定义 1.5 可知，在关系R下，由那些肯定属于X 中的元素构成了下近似集合
，又或者说是正域POS
R
（X）；而由那些肯定不属于X 的元素构成了负域NEG
R
（X）；上近似集合R
（
x
）
是由那些肯定属于或可能属于X 的元素组成的集合；而边界域BN
R
（X）是那些不能确定的元素组成的集合。
在现实生活中，使用众多特征属性来尽可能细致地描述对象，这些属性的重要程度是不同的，甚至说某些属性是冗余的。删除这些冗余的属性和不必要的属性值，不但不会影响知识发现的结果，还能达到简化计算的作用，同时也能降低算法复杂度。
定义 1.6 设R是一等价关系集，且r∈R，若有IND（R）=IND（R-{r}）成立，那么r就是不必要的；否则r是必要的。若对于R中的任何一个关系∀r∈R都是必要的，那么称等价关系集R是独立的，否则称R是依赖的。
定义 1.7 设Q⊆R，若Q是独立的，且IND（Q）=IND（R），则称Q是等价关系族R的一个约简，记作Red（R）。
定义 1.8 在等价关系R中，由所有的必要关系构成的关系子集称为等价关系R的核，记作Core（P）。所有约简Red（R）的交集等于R的核，即Core（P）=∩Red（R）。
属性约简问题，作为粗糙集理论的核心，长久以来一直得到众多学者的关注，先后出现众多行之有效的约简算法。在实际应用中，没有必要获得属性的最佳约简，只要得到一个有效的相对约简就已经足够可以有效解决具体问题了。
下面详细介绍两种常用的属性约简算法 [7～9] 。
1 .基于属性重要度的属性约简
由核属性Core（P）的定义可知，各约简结果的交集一定属于核属性，所以先找到Core（P），有助于实现属性的快速约简。基于属性重要度的约简算法，就是在求得属性集的核属性的基础上，通过扩充得到属性子集的一种约简算法。
属性重要度计算公式为：
从非核属性集中找出部分属性，然后将其与核属性合并所得并集计算对决策属性的相对正域，当遍历完所有条件属性后，由相对正域相等的添加属性组成的集合就是一个约简结果。
具体实现步骤如下：
1） 首先求得属性集的核属性Core
输入：信息系统S=（U，A，V，f）。
输出：Core，表示核属性集。
（1）加载数据data，并令Core=∅；
（2）∀a∈A，如果IND（A-{a}）≠IND{A}，则Core⇐Core（Y{a}）；
（3）当遍历完A中元素时，算法终止。
2）属性约简
输入：信息系统S=（U，A，V，f）。
输出：Red，是一个属性约简的结果。
（1）输入数据data，求出S的核属性集Core；
（2）令Red=Core，若IND（Red）=IND（A），结束算法，输出Red；
（3）计算∀a∈A-Red的属性重要度并按降序排列，选取属性重要度最大的，当属性有多个时，则选取划分个数最少的，Red⇐Red（Y{a}）；
（4）如果IND（Red）≠IND（A），转到步骤（3），否则算法终止，此时的Red即为所有约简属性集。
2 .基于信息熵的属性约简
我们可以把等价关系认为，由论域U的任意子集构成的随机变量。
定义 1.9 等价关系R的信息熵H （R）可以按下式来计算：
当H （R）=0时，说明只有一种可能性存在，没有其他不确定情况发生；相对于有n种可能发生的情况，H （R）取得越大，则系统的不确定性越大。
具体实现步骤如下：
输入：信息系统S=（U，A，V，f）。
输出：Red，是一个属性约简后的结果。
（1）按公式（1.4）计算H （A）的值；
（2）计算S的核属性集Core，并在此基础上进行扩充，令Red=Core；
（3）当H （Red）≠H （A）时，顺序执行，否则跳转到步骤（5）；
（4）对于∀a∈A-Red，计算a的重要度：
其中，
，
分别是Red（Y{a}）和Red的概率分布，取差值最大的属性a，并令Red⇐Red（Y{a}），跳转到步骤（3）；
（5）算法结束，输出Red。