Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (12): 3391-3396.DOI: 10.11772/j.issn.1001-9081.2017.12.3391

Previous Articles     Next Articles

Effective algorithm for granulation reduction of multi-granulation rough set

HU Shanzhong1, XU Yi1,2, HE Minghui1, WANG Ran1   

  1. 1. College of Computer Science and Technology, Anhui University, Hefei Anhui 230601, China;
    2. Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education(Anhui University), Hefei Anhui 230039, China
  • Received:2017-06-16 Revised:2017-09-07 Online:2017-12-10 Published:2017-12-18
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61402005), the Natural Science Foundation of Anhui Province (1308085QF114), the Higher Education Natural Science Foundation of Anhui Province (KJ2013A015), the Open Foundation of Key Laboratory of Intelligent Computing and Signal Processing at Anhui University of Ministry of Education of China.

多粒度粗糙集粒度约简的高效算法

胡善忠1, 徐怡1,2, 何明慧1, 王冉1   

  1. 1. 安徽大学 计算机科学与技术学院, 合肥 230601;
    2. 计算智能与信号处理教育部重点实验室(安徽大学), 合肥 230039
  • 通讯作者: 徐怡
  • 作者简介:胡善忠(1990-),男,安徽安庆人,硕士研究生,CCF会员,主要研究方向:粗糙集理论、粒计算、数据挖掘;徐怡(1981-),女,安徽滁州人,副教授,博士,主要研究方向:智能信息处理、粒计算、粗糙集理论;何明慧(1991-),男,山西晋中人,硕士研究生,主要研究方向:神经网络、粗糙集理论;王冉(1993-),男,安徽合肥人,硕士研究生,主要研究方向:推荐系统、粗糙集理论。
  • 基金资助:
    国家自然科学基金资助项目(61402005);安徽省自然科学基金资助项目(1308085QF114);安徽省高等学校省级自然科学基金资助项目(KJ2013A015);安徽大学计算智能与信号处理教育部重点实验室课题项目。

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|2+|A|2·|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|2+|A|2·|U|),其中|A|表示粒度集合大小,|U|表示决策信息系统中实例数。在UCI数据集上的实验结果验证了所提算法的有效性和高效性,并且随着数据集的增大,EAGRMRS相较于多粒度粗糙集粒度约简的启发式算法(HAGSS)效率优势更加明显。

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

CLC Number: