基于属性分辨力的决策表属性约简

摘 要 ：决策表的属性约简,又称知识约简,是粗糙集理论最核心内容之一,最优属性约简是NP难问题.根据粗糙集理论,本文定义了特征集以及属性分辨力概念,提出了基于特征集和属性分辨的启发式搜索算法,在一定程度上提高了搜索效率.

关 键 词 ：属性简约；差别矩阵；特征集；属性分辨力

中图分类号：TP18

1.引言

1982年波兰数学家Pawlak教授提出粗糙集理论⑴,是数据约简的有效工具,并从海量数据中发现隐含的知识.属性约简,又称知识约简,是粗糙集理论最核心内容之一.对于大型决策表,属性的约简一般有多种,求所有约简已被证明是NP困难问题,最小属性约简也是NP难题⑵针对这种状况,许多学者已对属性约简的算法进行了大量的研究,常见的属性约简方法有：基于信息熵的方法⑶,基于正区域的方法⑷,和基于差别矩阵的方法

由于基于差别矩阵的属性约简方法简洁,易于理解,得到许多学者的关注.本文基于由差别矩阵简化而来的特征矩阵,提出了基于属性分辨力的最小属性约简的启发式算法,它避免差别矩阵过大造成算法的低效.

2.相关定义及性质

实验结果表明 ,属性约简自寻优算法能够以较大的概率和较高的效率获得较优的属性约简 ,对于某些具体问题来说甚至能够获得最佳的属性约简 ；这也同时表明相对差异比较表的提出对于进一步构造效率更高的属性约简算法具有较大的实际意义.