Abstract: Aiming at the low efficiency problem of the existing granulation reduction algorithms for multi-granulation rough set, an Effective Algorithm for Granulation Reduction of Multi-granulation Rough Set (EAGRMRS) was proposed. Firstly, the lower approximation Boolean matrix of decision classes was defined by using the decision information system as the object. The defined matrix could be used for converting redundant and repeated set operations into Boolean operations in the process of granular reduction. Based on this matrix, the algorithm for computing lower approximation of decision classes and the algorithm for computing the important measure of granularity were presented. Then, focusing on the problem of redundancy calculation when computing the important measure of granularity, a fast algorithm for computing the important measure of granularity with dynamic increasing of granularity was presented. On the basis, the EAGRMRS was proposed. The time complexity of the proposed algorithm is O(|A|·|U|²+|A|²·|U|), in which|A|is the size of granulation set,|U|is the number of instances in decision information system. The experimental results on UCI datasets show that, the proposed algorithm is effective and efficient, the efficiency advantage of EAGRMRS is more obvious over Heuristic Approach to Granular Structure Selection (HAGSS) for multi-granulation rough set when the dataset increases.

Key words: multi-granulation rough set, boolean matrix, information system, important measure, granulation reduction

摘要： 针对已有多粒度粗糙集粒度约简算法效率较低的问题，提出一种多粒度粗糙集粒度约简的高效算法（EAGRMRS）。首先，以决策信息系统为对象，定义决策类下近似布尔矩阵，该矩阵能够将粒度约简过程中过多且有重复的集合运算转换为布尔运算，基于该矩阵给出计算决策类下近似算法和计算粒度重要度算法。然后，针对计算粒度重要度时存在冗余计算的问题，提出粒度动态增加时快速计算粒度重要度的算法，并在此基础上，提出EAGRMRS，该算法的时间复杂度为O（|A|·|U|²+|A|²·|U|），其中|A|表示粒度集合大小，|U|表示决策信息系统中实例数。在UCI数据集上的实验结果验证了所提算法的有效性和高效性，并且随着数据集的增大，EAGRMRS相较于多粒度粗糙集粒度约简的启发式算法（HAGSS）效率优势更加明显。

关键词: 多粒度粗糙集, 布尔矩阵, 信息系统, 重要度, 粒度约简