Dynamic updating method of approximations in multigranulation rough sets based on tolerance relation

doi:10.11772/j.issn.1001-9081.2018102086

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (5): 1247-1251.DOI: 10.11772/j.issn.1001-9081.2018102086

• Artificial intelligence • Next Articles

Dynamic updating method of approximations in multigranulation rough sets based on tolerance relation

XU Yi¹, XIAO Peng^1,2

1. Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education(Anhui University), Hefei Anhui 230039, China;
2. School of Computer Science and Technology, Anhui University, Hefei Anhui 230601, China

Received:2018-10-15 Revised:2018-12-10 Online:2019-05-10 Published:2019-05-14
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,2

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

通讯作者: 肖鹏
作者简介:徐怡(1981-),女,安徽滁州人,副教授,博士,主要研究方向:智能信息处理、粒计算、粗糙集理论;肖鹏(1992-),男,河北石家庄人,硕士研究生,主要研究方向:粗糙集理论、粒计算。
基金资助:
国家自然科学基金资助项目（61402005）；安徽省自然科学基金资助项目（1308085QF114）；安徽省高等学校省级自然科学基金资助项目（KJ2013A015）；安徽大学计算智能与信号处理教育部重点实验室课题项目。

Abstract

Abstract: Focused on the issue that missing attribute values are obtained when an incomplete information system changes, in order to solve the problem of low time efficiency of updating the approximations in a multigranulation rough sets, a dynamic update algorithm based on tolerance relationship was proposed. Firstly, the properties of the approximations change based on tolerance relationship were discussed, and the change trends of the approximations of optimistic and pessimistic multigranulation rough sets were obtained according to the relevant properties. Then, a theorem of dynamic update tolerance class was proposed for the problem of low efficiency of updating tolerance class. Based on this, a dynamic update algorithm based on tolerance relationship was proposed. The simulation experiments were carried out using four data sets in UCI database. When the data set becomes larger, the calculation time of the proposed update algorithm is much smaller than that of the static update algorithm. The experimental results show that the time efficiency of the proposed dynamic update algorithm is higher than that of the static algorithm, which verifies the correctness and efficiency of the proposed algorithm.

Key words: incomplete information system, multigranulation, dynamic update, tolerance relationship multigranulation rough sets, approximations

摘要： 针对不完备信息系统变化时缺失值获取具体属性值的特性，为解决多粒度粗糙集中更新近似集时间效率低的问题，提出了一种基于容差关系的近似集动态更新算法。首先，讨论了基于容差关系的近似集变化的性质，并根据相关性质得出乐观、悲观多粒度粗糙集的近似集的变化趋势；然后，针对更新容差类效率低的问题，提出了动态更新容差类的定理；最后，在此基础上，设计出基于容差关系的近似集动态更新算法。采用UCI数据库中4个数据集进行仿真实验，当数据集变大时，所提更新算法的计算时间远小于静态更新算法的计算时间，即所提动态更新算法的时间效率高于静态算法，验证了所提算法的正确性和高效性。

关键词: 不完备信息系统, 多粒度, 动态更新, 容差关系多粒度粗糙集, 近似集

CLC Number:

TP18

XU Yi, XIAO Peng. Dynamic updating method of approximations in multigranulation rough sets based on tolerance relation[J]. Journal of Computer Applications, 2019, 39(5): 1247-1251.

徐怡, 肖鹏. 基于容差关系的多粒度粗糙集中近似集动态更新方法[J]. 计算机应用, 2019, 39(5): 1247-1251.

References

[1] PAWLAK Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1995, 38(11):88-95.
[2] 梁吉业.信息系统中的不确定性与知识获取[M].北京:科学出版社,2005:13-113.(LIANG J Y.Uncertainty and Knowledge Acquisition in Information Systems[M]. Beijing: Science Press,2005: 13-113.)
[3] 王国胤. Rough集理论与知识获取[M].西安:西安交通大学出版社, 2001:99-134.(WANG G Y.Rough Set Theory and Knowledge Acquisition[M].Xi'an:Xi'an Jiaotong University Press,2001:99-134.)
[4] 张文修. 信息系统与知识发现[M].北京:科学出版社, 2003:15-25.(ZHANG W X.Information System and Knowledge Discovery[M].Beijing: Science Press, 2003:15-25.)
[5] 李元诚, 方廷健. 基于粗糙集理论的支撑向量机预测方法研究[J]. 数据采集与处理, 2003, 18(2):199-203.(LI Y C, FANG T J. Study of forecasting algorithm for support vector machines based on rough sets[J]. Journal of Data Acquisition & Processing,2003,18(2)199-203.)
[6] FAKIH S J, DAS T K. LEAD: a methodology for learning efficient approaches to medical diagnosis[J]. IEEE Transactions on Information Technology in Biomedicine, 2006, 10(2): 220-228.
[7] LUO C, LI T, CHEN H, et al. Incremental approaches for updating approximations in set-valued ordered information systems[J]. Knowledge-Based Systems, 2013, 50: 218-233.
[8] ZHANG J, LI T, DA R, et al. Neighborhood rough sets for dynamic data mining[J]. Information Sciences, 2014, 257(4):81-100.
[9] LIU D, LI T, DA R, et al. An incremental approach for inducing knowledge from dynamic information systems[J]. Fundamenta Informaticae, 2009, 94(2): 245-260.
[10] ZHANG J, LI T, DA R, et al. Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J]. International Journal of Approximate Reasoning, 2012, 53(4):620-635.
[11] CHEN H, LI T, QIAO S, et al. A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values[J]. International Journal of Intelligent Systems, 2010, 25(10):1005-1026.
[12] CHEN H, LI T, DA R. Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining[J]. Knowledge-Based Systems, 2012, 31(7):140-161.
[13] CHEN H, LI T, RUAN D. Dynamic maintenance of approximations under a rough-set based variable precision limited tolerance relation[J]. Journal of Multiple-Valued Logic and Soft Computing, 2012, 18(5): 577-598.
[14] QIAN Y, LIANG J, YAO Y, et al. MGRS: a multi-granulation rough set[J]. Information Sciences, 2010, 180(6): 949-970.
[15] YANG X, QI Y, YU H, et al. Updating multigranulation rough approximations with increasing of granular structures[J]. Knowledge-Based Systems, 2014, 64(1):59-69.
[16] HU C, LIU S, LIU G. Matrix-based approaches for dynamic updating approximations in multigranulation rough sets[J]. Knowledge-Based Systems, 2017, 122: 51-63.
[17] 胡成祥, 赵国柱. 优势关系多粒度粗糙集中近似集动态更新方法[J]. 中国科学技术大学学报, 2017(1):40-47.(HU C X, ZHAO G Z. Multi-granularity rough set approximation set dynamic update method[J]. Journal of University of Science and Technology of China, 2017(1): 40-47.)
[18] JU H, YANG X, SONG X, et al. Dynamic updating multigranulation fuzzy rough set: approximations and reducts[J]. International Journal of Machine Learning & Cybernetics, 2014, 5(6):981-990.
[19] HU C, LIU S, HUANG X. Dynamic updating approximations in multigranulation rough sets while refining or coarsening attribute values[J]. Knowledge-Based Systems, 2017, 130(15): 62-73.
[20] QIAN Y, LIANG J, DANG C. Incomplete multigranulation rough set[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2010, 40(2):420-431.
[21] 许韦, 吴陈, 杨习贝. 基于容差关系的不完备可变精度多粒度粗糙集[J]. 计算机应用研究, 2013, 30(6):1712-1715. (XU W,WU C,YANG X B. Incomplete variable precision multi-granulation rough sets based on tolerance relation[J]. Application Research of Computers,2013,30(6):1712-1715.)
[22] YANG H L, GUO Z L. Multigranulation decision-theoretic rough sets in incomplete information systems[J]. International Journal of Machine Learning & Cybernetics, 2015, 6(6):1005-1018.

Dynamic updating method of approximations in multigranulation rough sets based on tolerance relation

基于容差关系的多粒度粗糙集中近似集动态更新方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

[1]	Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index [J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.
[2]	PANG Xiaoqiong, YAN Xiaolong, CHEN Wenjun, YU Benguo, NIE Mengfei. Dynamic multi-keyword ranked search over encrypted data supporting semantic extension [J]. Journal of Computer Applications, 2019, 39(4): 1059-1065.
[3]	YU Dunhui, WANG Yi, ZHANG Wanshan. Ability dynamic measurement algorithm for software crowdsourcing workers [J]. Journal of Computer Applications, 2018, 38(12): 3612-3617.
[4]	WANG Chao LUO Ke. Attributes reduction method based on limited tolerance relation in incomplete information system [J]. Journal of Computer Applications, 2011, 31(12): 3236-3239.
[5]	. ITBI: Labeling scheme for XML data update [J]. Journal of Computer Applications, 2010, 30(9): 2324-2328.
[6]	. Extended rough set model based on improved complete tolerance relation [J]. Journal of Computer Applications, 2010, 30(07): 1873-1877.
[7]	TAO Zhi . Rough set model based on set pair analysis in incomplete information system [J]. Journal of Computer Applications, 2008, 28(7): 1684-1685.
[8]	. Component-based dynamic updating software system [J]. Journal of Computer Applications, 2006, 26(8): 1909-1911.
[9]	ZHAO Xiang,LIU Tong-ming,XIANG Yi-dan. Extension of rough set model based on weighted connection degree in incomplete information systems [J]. Journal of Computer Applications, 2005, 25(04): 824-826.
[10]	HU Peng, HONG Pei-lin, LI Jin-sheng, YANG Hai-song. Research on request-routing system in CDN [J]. Journal of Computer Applications, 2005, 25(02): 245-247.