论文部分内容阅读
摘要：决策表的属性约简，又称知识约简，是粗糙集理论最核心内容之一，最优属性约简是NP难问题。根据粗糙集理论，本文定义了特征集以及属性分辨力概念，提出了基于特征集和属性分辨的启发式搜索算法，在一定程度上提高了搜索效率。
关键词：属性简约；差别矩阵；特征集；属性分辨力
中图分类号：TP18
1 引言
1982年波兰数学家Pawlak教授提出粗糙集理论⑴，是数据约简的有效工具，并从海量数据中发现隐含的知识。属性约简，又称知识约简，是粗糙集理论最核心内容之一。对于大型决策表，属性的约简一般有多种，求所有约简已被证明是NP困难问题，最小属性约简也是NP难题⑵针对这种状况，许多学者已对属性约简的算法进行了大量的研究，常见的属性约简方法有：基于信息熵的方法⑶，基于正区域的方法⑷，和基于差别矩阵的方法
由于基于差别矩阵的属性约简方法简洁，易于理解，得到许多学者的关注。本文基于由差别矩阵简化而来的特征矩阵，提出了基于属性分辨力的最小属性约简的启发式算法，它避免差别矩阵过大造成算法的低效。
2 相关定义及性质
定义1：决策表S=（U，C∪D）的差别矩阵定义为：
利用柴恩矩阵，我们可以比较容易分析属性的重要程度，决策表的核集可由特征集中考的基数为1的元素确定【参考文献：帕瓦克】，但同时其中的空集元素对分析属性重要程度作用不大。
定义2：决策表 的条件属性集C的特征集定义为： .
显然，决策表S关于条件属性集合C的特征集是由可辨识矩阵中非空元素所组成。但是由于集合的性质，其中不含有相同的元素，从而特征集的元素多数情况下少于差别矩阵中元素个数，对于一些大容量的决策表，特征集能显著减少数据量，使占用的存储空间较小。
定义3：设条件属性集 ，则P关于决策属性集D的分辨力集定义为：
定义3：设条件属性集 ，则P关于决策属性集D的分辨力定义为：
其中， 表示集合 的基数.
定义4：设 是S基于 属性集分辨力的约简集， ，满足以下两个条件：
（1）E（R）=1；
（2）
定义5：设Red是S基于正域的约简集， 满足以下两个条件：
（1）
（2）
属性的分辨力有如下性质：
性质1：
性质2：若
证明：因， 故E（R）=1.由定义 ，从而 总存在 ，使得 .即 覆盖了M，从而 .
又 ，所以 ，从而
类似的有：
性质3：若 ，则有 .
性质4：基于正域的约简集和基于属性集分辨力的约简集等价.
证明：由性质2和3显然.
3 基于属性分辨力的属性约简
算法1：
输入： ；
输出：属性约简Red.
Step1：置 ；
Step2：球决策表 的可辨识矩阵A以及M；
Step3：有性质1求核 ；
Step4：計算 ，检验E（R）=1，是，则转Step7，否则 转Step5；
Step5：任取 并计算 ；
Step6：求出最大相对分辨力属性 ，若 ，则转Step7，否则，转Step4；
Step7： ，输出Red.
4 应用实例
以天气状态决策为例，见下表
U Outlook
Temperature
humidity
Wingdy
Class（D）
1 sunny hot high f N
2 sunny hot high t N
3 overcast hot high f P
4 rain mid high f P
5 Irain cool normal f P
6 rain cool normal t N
7 overcast cool normal t N
8 sunny mid high f P
9 sunny cool normal f P
10 rain mid normal t P
11 sunny mid normal t P
12 overcast mid high t P
13 overcast hot normal f P
14 rain mid high t N
先求差別矩阵，为书写便利，以数字1，2，3，4分别代替属性 . 如下：
（1）
实验结果表明 ，属性约简自寻优算法能够以较大的概率和较高的效率获得较优的属性约简 ，对于某些具体问题来说甚至能够获得最佳的属性约简 ；这也同时表明相对差异比较表的提出对于进一步构造效率更高的属性约简算法具有较大的实际意义。
参考文献
（1）葛浩，李龙澍，杨传健. 可信度差别矩阵机器属性约简[J].四川大学学报：工程科学版，2011.435：146-152.
（2）刘文军，谷云东，冯艳宾，等.基于可辨别矩阵和逻辑运算的属性约简算法的改进[J].模式识别与人工智能，2004，171：119-123.
（3）张文修，吴伟志，梁吉业，等. 粗糙集理论与方法[M]，北京：科学出版社，2001.Rough set attribute reduction algorithm based on discrimination of attribute
关键词：属性简约；差别矩阵；特征集；属性分辨力
中图分类号：TP18
1 引言
1982年波兰数学家Pawlak教授提出粗糙集理论⑴，是数据约简的有效工具，并从海量数据中发现隐含的知识。属性约简，又称知识约简，是粗糙集理论最核心内容之一。对于大型决策表，属性的约简一般有多种，求所有约简已被证明是NP困难问题，最小属性约简也是NP难题⑵针对这种状况，许多学者已对属性约简的算法进行了大量的研究，常见的属性约简方法有：基于信息熵的方法⑶，基于正区域的方法⑷，和基于差别矩阵的方法
由于基于差别矩阵的属性约简方法简洁，易于理解，得到许多学者的关注。本文基于由差别矩阵简化而来的特征矩阵，提出了基于属性分辨力的最小属性约简的启发式算法，它避免差别矩阵过大造成算法的低效。
2 相关定义及性质
定义1：决策表S=（U，C∪D）的差别矩阵定义为：
利用柴恩矩阵，我们可以比较容易分析属性的重要程度，决策表的核集可由特征集中考的基数为1的元素确定【参考文献：帕瓦克】，但同时其中的空集元素对分析属性重要程度作用不大。
定义2：决策表 的条件属性集C的特征集定义为： .
显然，决策表S关于条件属性集合C的特征集是由可辨识矩阵中非空元素所组成。但是由于集合的性质，其中不含有相同的元素，从而特征集的元素多数情况下少于差别矩阵中元素个数，对于一些大容量的决策表，特征集能显著减少数据量，使占用的存储空间较小。
定义3：设条件属性集 ，则P关于决策属性集D的分辨力集定义为：
定义3：设条件属性集 ，则P关于决策属性集D的分辨力定义为：
其中， 表示集合 的基数.
定义4：设 是S基于 属性集分辨力的约简集， ，满足以下两个条件：
（1）E（R）=1；
（2）
定义5：设Red是S基于正域的约简集， 满足以下两个条件：
（1）
（2）
属性的分辨力有如下性质：
性质1：
性质2：若
证明：因， 故E（R）=1.由定义 ，从而 总存在 ，使得 .即 覆盖了M，从而 .
又 ，所以 ，从而
类似的有：
性质3：若 ，则有 .
性质4：基于正域的约简集和基于属性集分辨力的约简集等价.
证明：由性质2和3显然.
3 基于属性分辨力的属性约简
算法1：
输入： ；
输出：属性约简Red.
Step1：置 ；
Step2：球决策表 的可辨识矩阵A以及M；
Step3：有性质1求核 ；
Step4：計算 ，检验E（R）=1，是，则转Step7，否则 转Step5；
Step5：任取 并计算 ；
Step6：求出最大相对分辨力属性 ，若 ，则转Step7，否则，转Step4；
Step7： ，输出Red.
4 应用实例
以天气状态决策为例，见下表
U Outlook
Temperature
humidity
Wingdy
Class（D）
1 sunny hot high f N
2 sunny hot high t N
3 overcast hot high f P
4 rain mid high f P
5 Irain cool normal f P
6 rain cool normal t N
7 overcast cool normal t N
8 sunny mid high f P
9 sunny cool normal f P
10 rain mid normal t P
11 sunny mid normal t P
12 overcast mid high t P
13 overcast hot normal f P
14 rain mid high t N
先求差別矩阵，为书写便利，以数字1，2，3，4分别代替属性 . 如下：
（1）
实验结果表明 ，属性约简自寻优算法能够以较大的概率和较高的效率获得较优的属性约简 ，对于某些具体问题来说甚至能够获得最佳的属性约简 ；这也同时表明相对差异比较表的提出对于进一步构造效率更高的属性约简算法具有较大的实际意义。
参考文献
（1）葛浩，李龙澍，杨传健. 可信度差别矩阵机器属性约简[J].四川大学学报：工程科学版，2011.435：146-152.
（2）刘文军，谷云东，冯艳宾，等.基于可辨别矩阵和逻辑运算的属性约简算法的改进[J].模式识别与人工智能，2004，171：119-123.
（3）张文修，吴伟志，梁吉业，等. 粗糙集理论与方法[M]，北京：科学出版社，2001.Rough set attribute reduction algorithm based on discrimination of attribute