基于加权粒度和优势关系的程度多粒度粗糙集近似集的动态并行更新算法

doi:10.11896／j.issn.1002-137X.2018.10.003

摘要/Abstract

摘要： 随着大数据集的不断更新,经典的多粒度粗糙集理论不再适用。为此,提出加权粒度优势关系程度悲观多粒度粗糙集与加权粒度优势关系程度乐观多粒度粗糙集的相关理论。在此基础上,给出了一种基于加权粒度和优势关系的程度多粒度粗糙集近似集的动态并行更新算法。最后,通过实验验证了所提算法的有效性,其能够应对海量动态更新的数据变化并提升运行效率。

关键词: 并行更新算法, 多粒度粗糙集, 加权, 优势关系

Abstract: With the continuous updating of large data sets,the classical multi-granulation rough set theory is no longer practical.Therefore,this paper put forward the related theory of graded pessimistic multi-granulation rough set with weighting granulations and dominance relation,graded optimistic multi-granulation rough set with weighting granulations and dominance relation.On the basis of this improved theory,this paper proposed a dynamic parallel updating algorithm forapproximate sets of graded multi-granulation rough set based on weighting granulations and dominance relation.Finally,the experiment verifies the effectiveness of the proposed algorithm,which is able to handle data with massive dynamic updates and improve running efficiency.

Key words: Dominance relation, Multi-granulation rough set, Parallel updating algorithm, Weighting

中图分类号:

TP182

赵艺琳, 姜麟, 米允龙, 李金海. 基于加权粒度和优势关系的程度多粒度粗糙集近似集的动态并行更新算法[J]. 计算机科学, 2018, 45(10): 11-20. https://doi.org/10.11896／j.issn.1002-137X.2018.10.003

ZHAO Yi-lin, JIANG Lin, MI Yun-long, LI Jin-hai. Dynamic Parallel Updating Algorithm for Approximate Sets of Graded Multi-granulation Rough Set Based on Weighting Granulations and Dominance Relation[J]. Computer Science, 2018, 45(10): 11-20. https://doi.org/10.11896／j.issn.1002-137X.2018.10.003

参考文献

[1]PAWLAK Z.Rough set [J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
[2]BAZAN J,PETERS J F,SKOWRON A,et al.Rough set approach to pattern extraction from classifiers[J].Electronic Notes in Theoretical Computer Science,2003,82(4):20-29.
[3]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001.
[4]PAL S K,MITRA P.Multispectral image segmentation using the rough-set-initialized EM algorithm [J].IEEE Transactions on Geoscience and Remote Sensing,2002,40(11):2495-2501.
[5]张文修,仇国芳.基于粗糙集的不确定性决策[M].北京:清华大学出版社,2005.
[6]MIAO D Q,ZHANG Q H,QIAN Y H,et al.From human intelligence to machine implementation model:theories and applications based on granular computing [J].CAAI Transactions on Intelligent Systems,2016,11(6):743-757.(in Chinese)
苗夺谦,张清华,钱宇华,等.从人类智能到机器实现模型——粒计算理论与方法[J].智能系统学报,2016,11(6):743-757.
[7]WANG G Y,ZHANG Q H,MA X A,et al.Granular computing models for knowledge uncertainty[J].Journal of Software,2011,24(4):676-694.(in Chinese)
王国胤,张清华,马希骜,等.知识不确定性问题的粒计算模型[J].软件学报,2011,24(4):676-694.
[8]ZHANG Y P,ZHANG L,WU T.The representation of diffe- rent granular worlds:A quotient space [J].Chinese Journal of Computers,2004,27(3):238-333.(in Chinese)
张燕平,张铃,吴涛.不同粒度世界的描述法——商空间法[J].计算机学报,2004,27(3):238-333.
[9]LIANG J Y,QIAN Y H,LI D Y,et al.Theory and method of granular computing for big data mining [J].Science China:Information Sciences,2015,45(11):1355-1369.(in Chinese)
梁吉业,钱宇华,李德玉,等.大数据挖掘的粒计算理论与方法[J].中国科学:信息科学,2015,45(11):1355-1369.
[10]YAO Y Y,LIN T Y.Generalization of rough sets using modal logics [J].Intelligent Automation and Soft Computing,1996,2(2):103-120.
[11]GRECO S,MATARAZZO B,SLOWINSKI R.Rough approxi- mation by dominance relations[J].International Journal of Intelligent Systems,2002,17(2):153-171.
[12]QIAN Y H,LIANG J Y,YAO Y Y,et al.MGRS:a multi-gra- nulation rough set[J].Information Sciences,2010,180(6):949-970.
[13]QIAN Y H,LIANG J Y,WANG F.A positive approximation based accelerated algorithm to feature selection from incomplete decision tables [J].Chinese Journal of Computers,2011,34(3):435-442.(in Chinese)
钱宇华,梁吉业,王锋.面向非完备决策表的正向近似特征选择加速算法[J].计算机学报,2011,34(3):435-442.
[14]XU W H,WANG Q R,LUO S Q.Multi-granulation fuzzy rough sets [J].Journal of Intelligent and Fuzzy Systems,2014,26(3):1323-1340.
[15]WU Z Y,ZHONG P H,HU J G.Graded multi-granulation rough sets [J].Fuzzy Systems and Mathematics,2014,28(3):165-172.(in Chinese)
吴志远,钟培华,胡建根.程度多粒度粗糙集[J].模糊系统与数学,2014,28(3):165-172.
[16]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.(in Chinese)
张明,唐振民,徐维艳,等.可变多粒度粗糙集模型[J].模式识别与人工智能,2012,25(4):709-720.
[17]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.(in Chinese)
张明,程科,杨习贝,等.基于加权粒度的多粒度粗糙集[J].控制与决策,2015,30(2):222-228.
[18]WANG X Y,SHEN J L,SHEN Y X.Graded multi-granulation rough set based on weighting granulations and dominance relation[J].Journal of Shandong University(Natural Science),2017,52(3):97-104.(in Chinese)
汪小燕,沈家兰,申元霞.基于加权粒度和优势关系的程度多粒度粗糙集[J].山东大学学报(理学版),2017,52(3):97-104.
[19]LI J H,REN Y,MEI C L,et al.A comparative study of multigranulation rough sets and concept lattices via rule acquisition [J].Knowledge-Based Systems,2016,91:152-164.
[20]LIN G P,LIANG J Y,QIAN Y H.An information fusion approach by combining multigranulation rough sets and evidence theory [J].Information Sciences,2015,314:184-199.
[21]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:184-199.
[22]LI T R,RUAN D,GEERT W,et al.A rough sets based characteristic relation approach for dynamic attribute generalization in data mining [J].Knowledge-Based Systems,2007,20(5):485-494.
[23]LI S Y,LI T R,LIU D.Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set [J].Knowledge-Based Systems,2013,40(1):17-26.
[24]CHEN H M,LI T R,RUAN D,et al.A rough-set-based incremental approach for updating approximations under dynamic maintenance environments[J].IEEE Transactions on Know-ledge and Data Engineering,2012,25(2):274-284.
[25]LIU W B,LI T R,ZOU W L,et al.Approaches for Incrementally Updating Approximations under Characteristic Relation-based Rough Sets While Attribute Values Coarsening and Refining[J].Computer Science,2010,37(6):248-251.(in Chinese)
刘伟斌,李天瑞,邹维丽,等.特性关系粗糙集下属性值粗化细化时近似集增量更新方法研究[J].计算机科学,2010,37(6):248-251.
[26]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.
[27]JU H R,YANG X B,SONG X N,et al.Dynamic updating multigranulation fuzzy rough set:approximations and reducts [J].International Journal of Machine Learning and Cybernetics,2014,5(6):981-990.
[28]HU C X,LIU S X,HUANG X L.Dynamic updating approximations in multigranulation rough sets while refining or coarsening attribute values [J].Knowledge-Based Systems,2017,130:62-73.
[29]HU C X,LIU S X,LIU G X.Matrix-based approaches for dynamic updating approximations in multigranulation rough sets [J].Knowledge-Based Systems,2017,122:51-63.
[30]HU C X,ZHAO G Z.A dominance-based multigranulation rough sets approach for dynamic updating approximations [J].Journal of University of Science and Technology of China,2017(1):40-47.(in Chinese)
胡成祥,赵国柱.优势关系多粒度粗糙集中近似集动态更新方法[J].中国科学技术大学学报,2017(1):40-47.
[31]SUN A W.Experience in the diagnosis and treatment of acute pyelonephritis [J].Chinese Journal of Medicine,1966,15(1):32-33.(in Chinese)
孙爱文.诊治急性肾盂肾炎的体会[J].中国医刊,1966,15(1):32-33.
[32]刘维.实战MATLAB之并行程序设计[M].北京:北京航空航天大学出版社,2012.
[33]HAO C,LI J H,FAN M,et al.Optimal scale selection in dynamic multi-scale decision tables based on sequential three-way decisions [J].Information Sciences,2017,415:213-232.

相关文章 15

[1]	杨文坤, 原晓佩, 陈小锋, 郭睿. 三维激光雷达点云空间多特征分割 Spatial Multi-feature Segmentation of 3D Lidar Point Cloud 计算机科学, 2022, 49(8): 143-149. https://doi.org/10.11896/jsjkx.210300275
[2]	石先让, 宋廷伦, 唐得志, 戴振泳. 一种新颖的单目视觉深度学习算法:H_SFPN Novel Deep Learning Algorithm for Monocular Vision:H_SFPN 计算机科学, 2021, 48(4): 130-137. https://doi.org/10.11896/jsjkx.200400090
[3]	储杰, 张正军, 汤鑫瑶, 黄振生. 基于加权样本和共识率的标记传播算法 Label Propagation Algorithm Based on Weighted Samples and Consensus-rate 计算机科学, 2021, 48(3): 214-219. https://doi.org/10.11896/jsjkx.191200103
[4]	张天瑞, 魏铭琦, 高秀秀. 基于IPSO-WRF的选择性激光烧结件气泡溶解时间预测模型 Prediction Model of Bubble Dissolution Time in Selective Laser Sintering Based on IPSO-WRF 计算机科学, 2021, 48(11A): 638-643. https://doi.org/10.11896/jsjkx.210300080
[5]	薛占熬, 张敏, 赵丽平, 李永祥. 集对优势关系下多粒度决策粗糙集的可变三支决策模型 Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation 计算机科学, 2021, 48(1): 157-166. https://doi.org/10.11896/jsjkx.191200175
[6]	朱珍, 黄锐, 臧铁钢, 卢世军. 基于加权近红外图像融合的单幅图像除雾方法 Single Image Defogging Method Based on Weighted Near-InFrared Image Fusion 计算机科学, 2020, 47(8): 241-244. https://doi.org/10.11896/jsjkx.200300068
[7]	宋传鸣, 洪旭, 王相海. 空-频域联合投票的交通视频阴影去除方法 Shadow Removal of Traffic Surveillance Video by Joint Voting in Spatial-Frequency Domain 计算机科学, 2020, 47(5): 129-136. https://doi.org/10.11896/jsjkx.190400040
[8]	朱莹,夏亦犁,裴文江. 基于改进的BEMD的红外与可见光图像融合方法 Fusion of Infrared and Color Visible Images Based on Improved BEMD 计算机科学, 2020, 47(3): 124-129. https://doi.org/10.11896/jsjkx.190100038
[9]	吴甜甜,王洁. 基于可能回答集程序的多Agent信念协调 Belief Coordination for Multi-agent System Based on Possibilistic Answer Set Programming 计算机科学, 2020, 47(2): 201-205. https://doi.org/10.11896/jsjkx.190100101
[10]	古雪梅,刘嘉勇,程芃森,何祥. 基于增强BiLSTM-CRF模型的推文恶意软件名称识别 Malware Name Recognition in Tweets Based on Enhanced BiLSTM-CRF Model 计算机科学, 2020, 47(2): 245-250. https://doi.org/10.11896/jsjkx.190500063
[11]	刘志, 曹诗鹏, 沈阳, 杨曦. 基于改进深度强化学习方法的单交叉口信号控制 Signal Control of Single Intersection Based on Improved Deep Reinforcement Learning Method 计算机科学, 2020, 47(12): 226-232. https://doi.org/10.11896/jsjkx.200300021
[12]	董本清, 李凤坤. 基于加权划分非平衡决策树的诗歌朗读情感度分析 Analysis of Emotional Degree of Poetry Reading Based on WDOUDT 计算机科学, 2020, 47(11A): 46-51. https://doi.org/10.11896/jsjkx.200600055
[13]	易玉根, 李世成, 裴洋, 陈磊, 代江艳. 联合多流形结构和自表示的特征选择方法 Feature Selection Method Combined with Multi-manifold Structures and Self-representation 计算机科学, 2020, 47(11A): 474-478. https://doi.org/10.11896/jsjkx.200100037
[14]	张文华, 刘晓鸽, 王沛沛, 刘静静, 程敬亮. 肝脏多b值扩散加权图像的三维配准 3D Registration for Multi-b-value Diffusion Weighted Images of Liver 计算机科学, 2020, 47(11A): 241-243. https://doi.org/10.11896/jsjkx.200400060
[15]	张良成, 王运锋. 动态自适应的多雷达信息加权融合方法 Dynamic Adaptive Multi-radar Tracks Weighted Fusion Method 计算机科学, 2020, 47(11A): 321-326. https://doi.org/10.11896/jsjkx.2004000145

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed