1. 引言
粗糙集理论 [1] 作为一种数据分析方法,在定性和定量分析的基础上用来描述决策系统中的不确定性。属性约简 [2] [3] [4] [5],也称特征选择,是粗糙集理论的重要核心应用。它是从信息系统的所有属性中选择部分重要度较高的属性,同时不减少数据分类的准确性。属性约简已被广泛应用于许多研究领域,如模式识别、数据挖掘与机器学习等。在数据挖掘 [6] 领域中,属性约简是一种常用的数据处理工具,主要对数据中的冗余属性进行删除操作,使其达到更高的分类性能且不损失数据表的任何信息。
前期学者们提出了许多属性约简准则和约简算法,几乎所有的约简准则都宣称保持分类不变、信息无损失。然而,本文从信息熵角度 [6] 分析,定量分析删除的冗余属性可能含有一定的信息量,可以得出属性约简可能会导致信息的损失。为了探究不同约简准则信息损失量的差异,提出联合粒度属性约简算法,同时对比了正区域约简、知识粒度约简和该算法的约简准则对数据分类、信息损失量的影响,从而验证此算法的有效性。
2. 基础知识
给定一个信息系统 [1]
中,U是论域,A是论域U上的条件属性集。在条件属性集中任取条件属性
都存在一个函数
,与其相对应,
为属性m的值域。U中每个元素称为个体、对象或行。
定义2.1 [5] 对于任意的属性子集
和任何个体
都对应着如下的信息函数:
B-不分明关系(或称为不可区分关系)定义为:
任何满足
的2个元素
都不能由B的任何子集区分,
表示由x引导的
等价类。
2.1. 属性约简
定义2.2 [6] 在决策系统
中,
是DS的基于正区域的相对约简当且仅当
满足以下两个条件:
(1)
;
(2) 对于任意的
,都有
.
定义2.3 [6] 给定一个决策系统
,
称为该决策系统DS的一个基于条件熵的相对约简当且仅当
满足如下两个条件:
(1)
;
(2) 对任意的
,均都有
。
2.2. 知识粒度的基本概念
定义2.4 [7] 给定一个信息系统
,对于任意属性子集
导出的划分
,则该信息系统对于属性子集M的知识粒度的定义为
定义2.5 [7] 设给定一个信息系统
,如果存在属性子集
,则有属性子集
相对于子集
的知识粒度的定义为
定义2.6 [7] 对于给定决策系统
,若属性子集
是当且仅当满足以下两个条件:
(1)
;
(2) 对于任意的
,
。
称
为该决策系统的一个知识属性约简。
定义2.7 [8] 在给定的信息系统
中,若存在属性子集
,则属性
与决策属性D的相似度定义为:
2.3. 知识粒度的启发式属性约简算法 [8]
根据知识属性约简的定义可得出一个属性约简算法,算法具体步骤如表1。
目前很多约简算法均要先求核属性,但该算法不需要。此算法在一定程度上减少了求核属性的工作量,同时时间复杂度相对缩减。
3. 联合粒度属性约简算法
受表1算法的启发,以知识粒度 [7] 作为启发式函数进行遍历搜索,选取知识粒度值的大小进行比较,得出一个新算法—基于联合粒度属性约简算法。算法的具体描述如表2所示。
![](Images/Table_Tmp.jpg)
Table 1. Heuristic attribute reduction algorithm based on knowledge granularity [8]
表1. 基于知识粒度的启发式属性约简算法 [8]
![](Images/Table_Tmp.jpg)
Table 2. Attribute Reduction Algorithm Based on Joint Granularity
表2. 基于联合粒度属性约简算法
基于联合粒度属性约简算法不同于上述表1,它主要从知识属性、粒计算 [9] 角度进行约简,可以直接对不同知识属性进行粒度和重要度的比较,同时使得约简过程更加精细,约简结果更加精确。
属性约简信息损失 [9]
定义3.1 [9] [10] [11] 在一个给定的决策系统
中,设A和
在论域U上导出的划分分别为X和Y,其中
,
,
,
,
,
,
,
. A和
的信息熵 [12] 分别可
定义为:
与A的联合熵 [13] 即可定义为:
定义3.2 [9] [10] [11] 给定
是一个决策系统,
是该决策系统的一个约简,则
属性约简的信息损失定义如下:
属性约简的信息损失率可定义如下:
命题1 给定一个决策系统
,若
是基于正区域的相对约简,
是基于知识粒度的属性约简,
是基于联合粒度的属性约简,则有
.
证明:根据知识粒度约简、联合粒度约简及正区域相对约简可证。
例1下表所示
是一个决策表,如表3所示。U为论域,其中
,
是条件属性,
是决策属性集。
![](Images/Table_Tmp.jpg)
Table 3. Decision System D S 1 = ( U , A , d )
表3. 决策系统
由正区域的定义可得:
。
根据条件属性依赖度的计算公式可得:
,所以该决策表是不相容决策表。
(1) 根据知识粒度的属性约简算法可得约简后为:
.
根据属性约简的信息损失的计算方法可得:
故
的信息损失量为:
。
(2) 由正区域约简算法可得:
,
故
的信息损失量为0。
的信息损失量为
。
(3) 根据联合粒度属性约简算法可得:
故
的信息损失量为0。
例2下表所示为一个决策表,
是一个决策系统,如表4所示。U为论域,
是条件属性,
是决策属性集。
![](Images/Table_Tmp.jpg)
Table 4. Decision system D S 2 = ( U , A , d )
表4. 决策系统
,
,
由正区域的定义可得:
。
根据条件属性依赖度计算公式得:
,所以该决策表是相容决策表。
(1) 基于正区域的相对约简:
故
的信息损失量为:
。
(2) 基于知识粒度的属性约简:
故
的信息损失量为:
。
(3)基于联合粒度的属性约简:
故
的信息损失量为:
。
4. 仿真实验分析
本节将采用一系列数据集进行验证本文所提出的算法的高效性和准确性。首先将本文提出的联合粒度属性约简算法与知识粒度属性约简算法、正区域相对约简算法 [14] 对同一组UCI数据集进行离散化处理,然后比较三种算法属性约简后的信息损失量从而验证本文算法的有效性。其实验平台的硬件环境为CPU Intel core i5和4 GB内存,操作系统为Windows 10专业版,实验所运用的编程工具为VC++6.0。
本次实验数据取自UCI数据集中的四组典型数据如表5所示。首先将每组数据集分成10等份,选择1份作为测试集,其他9份作为训练集,对这9份训练集进行联合粒度、知识粒度和正区域约简,然后比较它们约简后的信息损失量。
文中采用重庆邮电大学开发的RIDAS系统进行属性约简。使用正区域约简算法、知识粒度约简算法和联合粒度约简算法求取不同属性约简集合。根据信息熵的计算公式,根据已有计算信息熵的程序代码 [9],计算给定信息系统的条件属性集合的信息熵及每个约简后的信息熵,可得出不同约简准则的信息损失量的大小以及信息熵与信息损失率之间的关系。
图1~4分别表示四组数据集的约简准则与信息损失量仿真实验结果图,其中横坐标表示属性约简结果,纵坐标表示信息损失量大小。图5~8分别表示四组数据集约简后集合的信息熵与信息损失率仿真实验图,其中横坐标表示约简后信息熵,纵坐标表示信息损失率大小。
根据上述8张图示可以清楚地看出,本文提出的基于联合粒度属性约简的信息损失远小于基于正区域、基于知识粒度属性约简信息损失,从而说明本文提出的基于联合粒度属性约简算法的有效性,可以有效地解决大数据时代下海量数据的约简,减少约简导致的分类准确率较低、信息损失量较大的问题。
![](//html.hanspub.org/file/4-1541899x162_hanspub.png)
Figure 1. Comparison of dermatology
图1. Dermatology比较
![](//html.hanspub.org/file/4-1541899x163_hanspub.png)
Figure 2. Comparison of conceptual method choices
图2. Contraceptive Method Choice比较
![](//html.hanspub.org/file/4-1541899x165_hanspub.png)
Figure 4. Comparison of letter recognition
图4. Letter Recognition比较
![](//html.hanspub.org/file/4-1541899x166_hanspub.png)
Figure 5. Analysis of dermatology
图5. Dermatology分析
![](//html.hanspub.org/file/4-1541899x167_hanspub.png)
Figure 6. Analysis of conceptual method choice
图6. Contraceptive Method Choice分析
![](//html.hanspub.org/file/4-1541899x169_hanspub.png)
Figure 8. Analysis of letter recognition
图8. Letter Recognition分析
5. 结论
本文通过引入联合粒度的概念,并将其运用到粗糙集理论的属性约简 [15] 中,提出了基于联合粒度属性约简算法,然后分析比较不同的属性约简产生的信息损失,最终得到本文的基于联合粒度的属性约简不仅能保持数据分类的准确性,同时也能维持约简后的信息损失较低的结论。后续我们将继续研究该算法对带权决策表的约简信息损失的影响及进一步的优化。