基于信息粒度与交互信息的属性约简改进算法

张清华,李新太,2,赵 凡,2,高 满,2

（1.计算智能重庆市重点实验室（重庆邮电大学），重庆400065；2.重庆邮电大学计算机科学与技术学院，重庆400065）

1982年,波兰学者Pawlak提出粗糙集理论[1]，该理论用于处理不精确、不一致、不完备信息和知识的有效数学工具，目前已经在故障诊断、图像处理、海量数据处理、智能控制等研究领域得到广泛应用[2].

属性约简作为粗糙集理论的一个重要研究课题，其主要思想是在满足一定约束的前提下，通过删除不重要或冗余的属性，找到与原始信息系统具有相同分类能力的属性子集，从而提高数据处理与挖掘的效率[3-4].目前，经典的属性约简算法主要有:基于差别矩阵的属性约简算法[5-6]、基于正域的属性约简算法[7-8]和基于信息熵的属性约简算法[9-10].基于差别矩阵的属性约简算法，主要利用差别矩阵导出区分函数，并求解区分函数的析取范式，所有析取项均是约简结果，该方法可以找到所有约简结果，但计算复杂度较高.基于正域的属性约简算法，利用分类质量衡量属性重要度，主要保持约简结果划分到正域集合中的对象个数与全集一致，该方法时空复杂度较低.基于信息熵的属性约简算法，主要从信息观的角度计算属性重要度，利用启发式搜索策略迭代选择重要度大的属性，直到得到的属性集合与原信息系统的分类能力相同.

进一步地，随着基于粗糙集理论的属性约简研究不断深入，众多学者也从多个不同的角度对此研究进行了探索.Chen 等[11]为减少待选择属性的迭代次数从而提升约简算法的效率，提出一种基于属性组的加速策略；……