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

doi:10.11772/j.issn.1001-9081.2017.12.3391

计算机应用 ›› 2017, Vol. 37 ›› Issue (12): 3391-3396.DOI: 10.11772/j.issn.1001-9081.2017.12.3391

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

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

1. 安徽大学计算机科学与技术学院, 合肥 230601;
2. 计算智能与信号处理教育部重点实验室(安徽大学), 合肥 230039

收稿日期:2017-06-16 修回日期:2017-09-07 出版日期:2017-12-10 发布日期:2017-12-18
通讯作者: 徐怡
作者简介:胡善忠(1990-),男,安徽安庆人,硕士研究生,CCF会员,主要研究方向:粗糙集理论、粒计算、数据挖掘;徐怡(1981-),女,安徽滁州人,副教授,博士,主要研究方向:智能信息处理、粒计算、粗糙集理论;何明慧(1991-),男,山西晋中人,硕士研究生,主要研究方向:神经网络、粗糙集理论;王冉(1993-),男,安徽合肥人,硕士研究生,主要研究方向:推荐系统、粗糙集理论。
基金资助:
国家自然科学基金资助项目（61402005）；安徽省自然科学基金资助项目（1308085QF114）；安徽省高等学校省级自然科学基金资助项目（KJ2013A015）；安徽大学计算智能与信号处理教育部重点实验室课题项目。

Effective algorithm for granulation reduction of multi-granulation rough set

HU Shanzhong¹, XU Yi^1,2, HE Minghui¹, WANG Ran¹

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.

摘要/Abstract

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

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

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

中图分类号:

TP18

胡善忠, 徐怡, 何明慧, 王冉. 多粒度粗糙集粒度约简的高效算法[J]. 计算机应用, 2017, 37(12): 3391-3396.

HU Shanzhong, XU Yi, HE Minghui, WANG Ran. Effective algorithm for granulation reduction of multi-granulation rough set[J]. Journal of Computer Applications, 2017, 37(12): 3391-3396.

参考文献

[1] PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1982, 11(5):341-356.
[2] HU Q H, CHE X J, ZHANG L, et al. Rank entropy based decision trees for monotonic classification[J]. IEEE Transactions on Knowledge & Data Engineering, 2012, 24(11):2052-2064.
[3] SRINIVASA K G, VENUGOPAL K R, PATNAIK L M. A soft computing approach for data mining based query processing using rough sets and genetic algorithms[J]. International Journal of Hybrid Intelligent Systems, 2008, 5(1):1-17.
[4] 白鹤翔,王健,李德玉,等.基于粗糙集的非监督快速属性选择算法[J].计算机应用,2015,35(8):2355-2359.(BAI H X, WANG J, LI D Y, et al. Fast unsupervised feature selection algorithm based on rough set theory[J]. Journal of Computer Applications, 2015, 35(8):2355-2359.)
[5] QIAN Y H, LIANG J Y, YAO Y Y, et al. MGRS:a multi-granulation rough set[J]. Information Sciences, 2010, 180(6):949-970.
[6] XU W H, SUN W X, ZHANG X Y, et al. Multiple granulation rough set approach to ordered information systems[J]. International Journal of General Systems, 2012, 41(5):475-501.
[7] YANG X B, SONG X N, DOU H L, et al. Multi-granulation rough set:from crisp to fuzzy case[J]. Annals of Fuzzy Mathematics and Informatics, 2011, 1(1):55-70.
[8] LIN G P, QIAN Y H, LI J J. NMGRS:Neighborhood-based multigranulation rough sets[J]. International Journal of Approximate Reasoning, 2012, 53(7):1080-1093.
[9] QIAN Y H, ZHANG H, SANG Y L, et al. Multigranulation decision-theoretic rough sets[J]. International Journal of Approximate Reasoning, 2014, 55(1):225-237.
[10] 张明,唐振民,徐维艳,等.可变多粒度粗糙集模型[J].模式识别与人工智能,2012,25(4):709-720.(ZHANG M, TANG Z M, XU W Y, et al. Variable multigranulation rough set model[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(4):709-720.)
[11] 桑妍丽,钱宇华.一种悲观多粒度粗糙集中的粒度约简算法[J].模式识别与人工智能,2012,25(3):361-366.(SANG Y L, QIAN Y H. A granular space reduction approach to pessimistic multi-granulation rough sets[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(3):361-366.)
[12] YANG X B, QI Y S, SONG X N, et al. Test cost sensitive multigranulation rough set:model and minimal cost selection[J]. Information Sciences, 2013, 250(11):184-199.
[13] 张明,程科,杨习贝,等.基于加权粒度的多粒度粗糙集[J].控制与决策,2015,30(2):222-228.(ZHANG M, CHENG K, YANG X B, et al. Multigranulation rough set based on weighted granulations[J]. Control and Decision, 2015, 30(2):222-228.)
[14] DAI J H, WANG W T, TIAN H W, et al. Attribute selection based on a new conditional entropy for incomplete decision systems[J]. Knowledge-Based Systems, 2013, 39(2):207-213.
[15] MIAO D Q, GAO C, ZHANG N, et al. Diverse reduct subspaces based co-training for partially labeled data[J]. International Journal of Approximate Reasoning, 2011, 52(8):1103-1117.
[16] QIAN J, MIAO D Q, ZHANG Z H, et al. Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation[J]. International Journal of Approximate Reasoning, 2011, 52(2):212-230.
[17] 鞠恒荣,周献中,杨佩,等.测试代价敏感的粗糙集方法[J].系统工程理论与实践,2017,37(1):228-240.(JU H R, ZHOU X Z, YANG P, et al. Test-cost-sensitive based rough set approach[J]. System Engineering-Theory and Practice, 2017, 37(1):228-240.)
[18] YANG X B, QI Y, YU H L, et al. Updating multigranulation rough approximations with increasing of granular structures[J]. Knowledge-Based Systems, 2014, 64(1):59-69.

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

Effective algorithm for granulation reduction of multi-granulation rough set

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	彭莉, 张海清, 李代伟, 唐聃, 于曦, 何磊. 基于粗糙集理论的不完备数据分析方法的混合信息系统填补算法[J]. 计算机应用, 2021, 41(3): 677-685.
[2]	李从东, 章志伟, 曹策俊, 张帆顺. 基于多重网络的复杂产品工程变更传播影响评估[J]. 计算机应用, 2020, 40(4): 1215-1222.
[3]	徐怡, 肖鹏. 基于容差关系的多粒度粗糙集中近似集动态更新方法[J]. 计算机应用, 2019, 39(5): 1247-1251.
[4]	郑文彬, 李进金, 于佩秋, 林艺东. 变精度多粒度粗糙集近似集更新的矩阵算法[J]. 计算机应用, 2019, 39(11): 3140-3145.
[5]	谢静, 邹滨, 李沈鑫, 赵秀阁, 邱永红. 大气污染暴露风险防控可视化决策支持平台[J]. 计算机应用, 2019, 39(11): 3391-3397.
[6]	万志超, 宋杰, 沈永良. 可变直觉模糊多粒度粗糙集模型及其近似分布约简算法[J]. 计算机应用, 2018, 38(2): 390-398.
[7]	姚晟, 汪杰, 徐风, 陈菊. 不完备邻域粗糙集的不确定性度量和属性约简[J]. 计算机应用, 2018, 38(1): 97-103.
[8]	王扬, 吴凡, 姚宗强, 刘杰, 李栋. 基于正则化矩阵分解的用户用电行为分析[J]. 计算机应用, 2017, 37(8): 2405-2409.
[9]	任冬梅, 张宇洋, 董新玲. 应用于石油钻井安全评价的改进主成分分析贝叶斯判别方法[J]. 计算机应用, 2017, 37(6): 1820-1824.
[10]	赵冬梅, 李红. 基于并行约简的网络安全态势要素提取方法[J]. 计算机应用, 2017, 37(4): 1008-1013.
[11]	徐涛, 孟野. 踪迹聚类下组织实体的重要度排序方法[J]. 计算机应用, 2016, 36(5): 1284-1289.
[12]	余顺坤, 闫泓序. 基于双阈值约束容差优势关系的评价模型[J]. 计算机应用, 2016, 36(11): 3131-3135.
[13]	梁海龙, 谢珺, 续欣莹, 任密蜂. 新的基于区分对象集的邻域粗糙集属性约简算法[J]. 计算机应用, 2015, 35(8): 2366-2370.
[14]	郝彦彬, 郭晓, 杨乃定. 基于增量计算的信息系统属性粒结构计算方法[J]. 计算机应用, 2015, 35(7): 1915-1920.
[15]	郝彦彬, 郭晓, 杨乃定. 信息系统的属性信息粒计算方法[J]. 计算机应用, 2015, 35(4): 1030-1034.