基于改进的差别矩阵的快速属性约简算法

摘要

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|).其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O(|C|2∑0≤i＜j≤k|Di||Dj|),O(|C||U|))和max(O(|C|∑0≤i＜j≤k|Di||Dj|),O(|U|)).最后,实例分析与实验结果表明了新算法具有高效性.