Abstract: 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.

Key words: rough set, attribute reduction, discernibility matrices, core attribute

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

关键词: 粗糙集, 属性约简, 差别矩阵, 核属性