拟单层覆盖粗糙集中近似集的增量更新算法

doi:10.19678/j.issn.1000-3428.0062982

摘要/Abstract

摘要： 拟单层覆盖粗糙集与集值信息系统之间存在一一对应的映射关系，当集值信息系统中的对象集动态添加或移除时，对应拟单层覆盖粗糙集中的信息单元也会随之改变，导致拟单层覆盖粗糙集中的近似集发生变化。针对拟单层覆盖粗糙集中近似集的动态更新问题，将拟单层覆盖粗糙集与增量学习相结合，提出近似集的增量更新算法。设计拟单层覆盖集中信息单元的更新算法，以分析信息单元的变化情况，分别构建近似集中可靠单元和争议单元的相关可靠单元集的更新算法。在此基础上，设计与可靠单元和争议单元更新算法相对应的增量更新算法，并且分析其时间复杂度。在UCI数据集上的实验结果表明，与静态算法相比，该算法在对象集发生添加和移除情况下的近似集更新效率分别提高21.5和29倍，能够有效提高近似集的计算效率。

关键词: 粗糙集, 拟单层覆盖, 集值信息系统, 增量学习, 近似集

Abstract: A one-to-one mapping relationship exists between the semi-monolayer cover rough sets and the set-valued information system.When an object set in a set-valued information system is dynamically added or removed, the information unit that corresponds to the semi-monolayer cover rough sets also changes.This leads to the change in the approximation sets on the semi-monolayer cover rough sets.To address the dynamic updating problem of approximation sets on semi-monolayer cover rough sets, an incremental updating algorithm for approximation sets is proposed by combining semi-monolayer cover rough sets with incremental learning.The updating algorithom, comprising a centralized information unit with semi-monolayer coverage, is designed to analyze the changes in the information unit.The updating algorithms of relevant reliable unit sets of approximation centralized reliable and controversial units are constructed.An incremental updating algorithm that corresponds to the updating algorithms of reliable and controversial units is designed, and then its time complexity is analyzed.The experimental results on the UCI dataset indicate that compared with the static algorithm, the update efficiency of the approximation sets with the addition and removal of the object sets is improved by 21.5 and 29 times, respectively.Therefore, the incremental updating algorithm can effectively improve the computational efficiency of the approximation sets.

Key words: rough sets, semi-monolayer cover, set-valued information system, incremental learning, approximation sets

中图分类号:

TP18

吴正江, 张亚宁, 张真, 梅秋雨, 杨天. 拟单层覆盖粗糙集中近似集的增量更新算法[J]. 计算机工程, 2022, 48(6): 200-206,212.

WU Zhengjiang, ZHANG Yaning, ZHANG Zhen, MEI Qiuyu, YANG Tian. Incremental Updating Algorithm for Approximation Sets on Semi-Monolayer Cover Rough Sets[J]. Computer Engineering, 2022, 48(6): 200-206,212.

http://www.ecice06.com/CN/Y2022/V48/I6/200

图/表 6

20220625175806

20220625175810

20220625175814

20220625175817

20220625175821

20220625175824

参考文献

[1] PAWLAK Z.Rough sets[J].International Journal of Computer & Information Sciences, 1982, 11(5):341-356.
[2] 李抒音, 刘洋.权重模糊粗糙集的分类规则挖掘算法[J].计算机工程, 2019, 45(9):211-215. LI S Y, LIU Y.Classification rule mining algorithm for weighted fuzzy rough sets[J].Computer Engineering, 2019, 45(9):211-215.(in Chinese)
[3] 姜宇, 张大方, 刁祖龙.基于点击流的用户矩阵模型相似度个性化推荐[J].计算机工程, 2018, 44(1):219-225. JIANG Y, ZHANG D F, DIAO Z L.Similarity personalized recommendation of user matrix model based on click stream[J].Computer Engineering, 2018, 44(1):219-225.(in Chinese)
[4] 王建华, 陈永乐, 张壮壮, 等.基于工控系统功能码特征的同源攻击分析[J].计算机工程, 2020, 46(7):36-42. WANG J H, CHEN Y L, ZHANG Z Z, et al.Same origin attack analysis based on features of industrial control system function code[J].Computer Engineering, 2020, 46(7):36-42.(in Chinese)
[5] 王运明, 陈波, 周敏, 等.基于主客观权重判决的异构无线网络接入选择算法[J].计算机工程, 2019, 45(11):107-111, 120. WANG Y M, CHEN B, ZHOU M, et al.Heterogeneous wireless network access selection algorithm based on subjective and objective weight judgment[J].Computer Engineering, 2019, 45(11):107-111, 120.(in Chinese)
[6] KRYSZKIEWICZ M.Rough set approach to incomplete information systems[J].Information Sciences, 1998, 112(1):39-49.
[7] STEFANOWSKI J, TSOUKIAS A.Incomplete infor-mation tables and rough classification[J].Computational Intelligence, 2001, 17(3):545-566.
[8] WANG G Y.Extension of rough set under incomplete information systems[C]//Proceedings of IEEE International Conference on Fuzzy Systems.Washington D.C., USA:IEEE Press, 2002:1098-1103.
[9] GUAN Y Y, WANG H K.Set-valued information systems[J].Information Sciences, 2006, 176(17):2507-2525.
[10] WU Z J, CHEN N, GAO Y.Semi-monolayer cover rough set:concept, property and g-ranular algorithm[J].Information Sciences, 2018, 456:97-112.
[11] 吴正江, 刘永利, 高岩.拟单层覆盖上的覆盖粗糙集族[J].山东大学学报(理学版), 2014, 49(8):6-14. WU Z J, LIU Y L, GAO Y.Cover rough sets on a semi-monolayer cover[J].Journal of Shandong University (Natural Science), 2014, 49(8):6-14.(in Chinese)
[12] WU Z J, WANG H, CHEN N, et al.Semi-monolayer covering rough set on set-valued information systems and its efficient computation[J].International Journal of Approximate Reasoning, 2021, 130:83-106.
[13] HUANG Q Q, LI T R, HUANG Y Y, et al.Dynamic dominance rough set approach for processing composite ordered data[J].Knowledge-Based Systems, 2020, 187:1-17.
[14] 吴杰, 梁妍, 马垣.基于下确界不可约的概念格属性约简方法[J].计算机工程, 2016, 42(11):213-218. WU J, LIANG Y, MA Y.Attribute reduction method of concept lattice based on infimum irreducibleness[J].Computer Engineering, 2016, 42(11):213-218.(in Chinese)
[15] YANG X, LIU D, Yang X B, et al.Incremental fuzzy probability decision-theoretic approaches to dynamic three-way approximations[J].Information Sciences, 2021, 550:71-90.
[16] 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.
[17] 刘凤玲, 林国平.动态更新属性值变化时的最优粒度[J].小型微型计算机系统, 2020, 41(10):2063-2067. LIU F L, LIN G P.Updating optimal scale in multi-scale decision systems under environment of attribute value[J].Journal of Chinese Computer Systems, 2020, 41(10):2063-2067.(in Chinese)
[18] SANG B B, CHEN H M, YANG L, et al.Feature selection for dynamic interval-valued ordered data based on fuzzy dominance neighborhood rough set[J].Knowledge-Based Systems, 2021, 227:1-10.
[19] 张钧波, 李天瑞, 潘毅, 等.云平台下基于粗糙集的并行增量知识更新算法[J].软件学报, 2015, 26(5):1064-1078. ZHANG J B, LI T R, PAN Y, et al.Parallel and incremental algorithm for knowledge update based on rough sets in cloud platform[J].Journal of Software, 2015, 26(5):1064-1078.(in Chinese)
[20] 孙海霞.基于对象变化的邻域决策粗糙集动态更新算法[J].智能系统学报, 2021, 16(4):746-756. SUN H X.Dynamic updating algorithm of neighborhood decision-theoretic rough set model based on object change[J].CAAI Transactions on Intelligent Systems, 2021, 16(4):746-756.(in Chinese)
[21] 苑红星, 卓雪雪, 竺德, 等.基于矩阵的混合型邻域决策粗糙集增量式更新算法[J].控制与决策, 2022, 37(6):1621-1631. YUAN H X, ZHUO X X, ZHU D, et al.Incremental updating algorithms of neighborhood decision-theoretic rough set model for hybrid data based on matrix[J].Control and Decision, 2022, 37(6):1621-1631.(in Chinese)
[22] 徐怡, 孙伟康, 王泉.邻域多粒度粗糙集知识更新增量算法[J].小型微型计算机系统, 2020, 41(5):908-918. XU Y, SUN W K, WANG Q.Incremental algorithm for knowledge updating of neighborhood multigranulation rough set[J].Journal of Chinese Computer Systems, 2020, 41(5):908-918.
[23] SANG B B, CHEN H M, YANG L, et al.Incremental attribute reduction approaches for ordered data with time-evolving objects[J].Knowledge-Based Systems, 2021, 212:1-13.

选择文件类型/文献管理软件名称

选择包含的内容