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

发布时间：2018-04-18 20:37

  本文选题：多粒度粗糙集 + 布尔矩阵　； 参考：《计算机应用》2017年12期

【摘要】：针对已有多粒度粗糙集粒度约简算法效率较低的问题,提出一种多粒度粗糙集粒度约简的高效算法(EAGRMRS)。首先,以决策信息系统为对象,定义决策类下近似布尔矩阵,该矩阵能够将粒度约简过程中过多且有重复的集合运算转换为布尔运算,基于该矩阵给出计算决策类下近似算法和计算粒度重要度算法。然后,针对计算粒度重要度时存在冗余计算的问题,提出粒度动态增加时快速计算粒度重要度的算法,并在此基础上,提出EAGRMRS,该算法的时间复杂度为O(|A|·|U|~2+|A|~2·|U|),其中|A|表示粒度集合大小,|U|表示决策信息系统中实例数。在UCI数据集上的实验结果验证了所提算法的有效性和高效性,并且随着数据集的增大,EAGRMRS相较于多粒度粗糙集粒度约简的启发式算法(HAGSS)效率优势更加明显。
[Abstract]:Aiming at the low efficiency of existing multi-granularity rough set granularity reduction algorithms, an efficient algorithm of multi-granularity rough set granularity reduction is proposed.Firstly, taking decision information system as an object, the approximate Boolean matrix under decision class is defined. The matrix can transform too many and repeated set operations into Boolean operations in the process of granularity reduction.Based on the matrix, the approximate algorithm of computing decision class and the algorithm of calculating granularity importance are given.Then, aiming at the problem of redundant calculation in computing granularity importance, a fast algorithm for calculating granularity importance is proposed when granularity increases dynamically, and on this basis,EAGRMRS is proposed. The time complexity of the algorithm is O (A U ~ (2) A ~ (2) A ~ (2) U), where A denotes the size of granularity set and U represents the number of instances in a decision information system.The experimental results on UCI datasets verify the effectiveness and efficiency of the proposed algorithm, and with the increase of the data set, the efficiency of the proposed algorithm is more obvious than that of the heuristic algorithm of multi-granularity rough set granularity reduction (HAGSS).
【作者单位】： 安徽大学计算机科学与技术学院;计算智能与信号处理教育部重点实验室(安徽大学);
【基金】：国家自然科学基金资助项目(61402005) 安徽省自然科学基金资助项目(1308085QF114) 安徽省高等学校省级自然科学基金资助项目(KJ2013A015) 安徽大学计算智能与信号处理教育部重点实验室课题项目~~
【分类号】：TP18
，

本文编号：1769985