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

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

Fast attribute reduction algorithm based on improved discernibilty matrices

In order to solve the efficiency problem of calculating the attribute reduction based on discernibility matrices，a new algorithm based on counting sorting for computing U/C is provided，and its complexity is cut down to O（|C||U|）.Then，the shortcomings of attribution reduction algorithm are analyzed based on discernibility matrices，and the definition of the improved discernibility matrices is presented.Furthermore，core attribute computed by a fast computing core algorithm and an attribute with more frequencies can be used to generate smaller class feature matrices.So a new algorithm based on the improved class feature matrices is proposed，whose worst time complexity and space complexity are cut down to max（O（|C|²∑_0≤i<j≤k|D_i||D_j|），O（|C||U|））and max（O（|C|∑_0≤i<j≤k |D_i||D_j|），O（|U|）） respectively.An example is used to illustrate the efficiency of the new algorithm.Experiments show that the new algorithm is efficient for various kinds of data sets.