Computer Science ›› 2020, Vol. 47 ›› Issue (8): 137-143.doi: 10.11896/jsjkx.190700188

Previous Articles     Next Articles

Incremental Attribute Reduction Algorithm in Dominance-based Rough Set

SANG Bin-bin, YANG Liu-zhong, CHEN Hong-mei , WANG Sheng-wu   

  1. Department of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China
    Key Laboratory of Cloud Computing and Intelligent Technology, Southwest Jiaotong University, Chengdu 611756, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:SANG Bin-bin, born in 1992, Ph.D, is a member of China Computer Federation.His main research interests include rough set and granular computing.
    CHEN Hong-mei, born in 1971, Ph.D, professor, Ph.D supervisor, is a member of China Computer Federation.Her main research interests include rough set and granular computing, and intelligent information processing.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61572406, 61976182) and Key Program for International S&T Cooperation of Sichuan Province (2019YFH0097).

Abstract: In real life, as the data increase continuously, the relation between the original criteria and the decision making changes dynamically.How to effectively calculate the attribute reduction becomes an urgent problem to be solved in the dynamic decision making.Incremental updating method can effectively complete the dynamic learning task, because it can acquire new knowledge based on previous knowledge.This paper exploited the dominance-based rough set approach to study the incremental attribute reduction method when adding a single object to the data with dominant relation.Firstly, the dominant set matrix is defined as the target of the update to calculate the new dominant conditional entropy.Then, an incremental learning mechanism of the dominant conditional entropy is proposed by analyzing the three different situations of the adding object.After that, an incremental attribute reduction algorithm is designed based on the dominant set matrix.Finally, experiments on six different UCI data set are conducted to compare the effectiveness and efficiency of the incremental and non-incremental algorithms.The experimental results show that the incremental attribute reduction algorithm proposed in this paper is not only consistent with the non-incremental attribute reduction algorithm in term of effectiveness, but also far superior to the non-incremental attribute reduction algorithm in term of efficiency.Therefore, the proposed incremental algorithm can effectively and efficiently accomplish the task of attribute reduction in dynamical data with dominant relation.

Key words: Attribute reduction, Dominance-based rough set approach, Dominant set matrix, Dynamic decision-making, Incremental learning

CLC Number: 

  • TP301.6
[1]PAWLAK Z.Rough sets [J].International Journal of Computer &Information Sciences, 1982, 11(5):341-356.
[2]GRECO S, MATARAZZO B, SLOWINSKI R.Roughapproxi-mation of a preference relation by dominance relations [J].European Journal of Operational Research, 1999, 117(1):63-83.
[3]DU W S, HU B Q.Dominance-based rough set approach to incomplete ordered information systems[J].InformationSciences, 2016, 346-347(C):106-129.
[4]SUN B Z, MA W X.Rough approximation of a preference relation by multi-decision dominance for a multi-agent conflict ana-lysis problem [J].Information Sciences, 2015, 315(10):39-53.
[5]HUANG B.Graded dominance interval-based fuzzy objective information systems [J].Knowledge-Based Systems, 2011, 24(7):1004-1012.
[6]SONG P, LIANG J Y, QIAN Y H.A two-grade approach to ranking interval data [J].Knowledge-Based Systems, 2012, 27(3):234-244.
[7]ZHANG H Y, YANG S Y.Feature selection and approximate reasoning of large-scale set-valued decision tables based on α -dominance-based quantitative rough sets[J].Information Scien-ces, 2017, 378 (1):328-347.
[8]WANG F, LIANG J Y, DANG C Y.Attribute reduction for dynamic data sets [J].Applied Soft Computing, 2013, 13(1), 676-689.
[9]LIANG J, WANG F, DANG C, et al.A Group Incremental Approach to Feature Selection Applying Rough Set Technique [J].IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2):294-308.
[10]JING Y G, LI T R, FUJITA H, et al.An incremental attribute reduction approach based on knowledge granularity with a multi-granulation view [J].Information Sciences, 2017, 411(10):23-38.
[11]XIE X J, QIN X L.A novel incremental attribute reduction approach for dynamic incomplete decision systems [J].International Journal of Approximate Reasoning, 2018, 93:443-462.
[12]HU Q H, GUO M Z, YU D R, et al.Information entropy for ordinal classification [J].Information Sciences, 2010, 53(6):1188-1200.
[13]HU Q H, CHE X J, ZHANG L, et al.Rank entropy-based decision trees for monotonic classification [J].IEEE Transactions on Knowledge and Data Engineering, 2012, 24(11):2052-2064.
[14]PAWLAK Z.Rough sets:Theoretical Aspects of Reasoningabout Data [M]∥Norwell, USA:Kluwer Academic Publishers, Boston, 1991.
[1] LIU Dong-mei, XU Yang, WU Ze-bin, LIU Qian, SONG Bin, WEI Zhi-hui. Incremental Object Detection Method Based on Border Distance Measurement [J]. Computer Science, 2022, 49(8): 136-142.
[2] SHEN Shao-peng, MA Hong-jiang, ZHANG Zhi-heng, ZHOU Xiang-bing, ZHU Chun-man, WEN Zuo-cheng. Three-way Drift Detection for State Transition Pattern on Multivariate Time Series [J]. Computer Science, 2022, 49(4): 144-151.
[3] WANG Zi-yin, LI Lei-jun, MI Ju-sheng, LI Mei-zheng, XIE Bin. Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost [J]. Computer Science, 2022, 49(4): 161-167.
[4] LI Yan, FAN Bin, GUO Jie, LIN Zi-yuan, ZHAO Zhao. Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets [J]. Computer Science, 2021, 48(6A): 342-348.
[5] ZENG Hui-kun, MI Ju-sheng, LI Zhong-ling. Dynamic Updating Method of Concepts and Reduction in Formal Context [J]. Computer Science, 2021, 48(1): 131-135.
[6] LIU Ling-yun, QIAN Hui, XING Hong-jie, DONG Chun-ru, ZHANG Feng. Incremental Classification Model Based on Q-learning Algorithm [J]. Computer Science, 2020, 47(8): 171-177.
[7] YUE Xiao-wei, PENG Sha and QIN Ke-yun. Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice [J]. Computer Science, 2020, 47(6A): 436-439.
[8] CHEN Yi-ning,CHEN Hong-mei. Attribute Reduction of Fuzzy Rough Set Based on Distance Ratio Scale [J]. Computer Science, 2020, 47(3): 67-72.
[9] XU Yi,TANG Jing-xin. Attribute Reduction Algorithm Based on Optimized Discernibility Matrix and Improving Discernibility Information Tree [J]. Computer Science, 2020, 47(3): 73-78.
[10] HOU Cheng-jun,MI Ju-sheng,LIANG Mei-she. Attribute Reduction Based on Local Adjustable Multi-granulation Rough Set [J]. Computer Science, 2020, 47(3): 87-91.
[11] YANG Wen-jing,ZHANG Nan,TONG Xiang-rong,DU Zhen-bin. Class-specific Distribution Preservation Reduction in Interval-valued Decision Systems [J]. Computer Science, 2020, 47(3): 92-97.
[12] GUO Qing-chun,MA Jian-min. Judgment Methods of Interval-set Consistent Sets of Dual Interval-set Concept Lattices [J]. Computer Science, 2020, 47(3): 98-102.
[13] LONG Bing-han, XU Wei-hua, ZHANG Xiao-yan. Distribution Attribute Reduction Based on Improved Discernibility Information Tree in Inconsistent System [J]. Computer Science, 2019, 46(6A): 115-119.
[14] LI Yan, ZHANG Li, CHEN Jun-fen. Attribute Reduction Method Based on Sequential Three-way Decisions in Dynamic Information Systems [J]. Computer Science, 2019, 46(6A): 120-123.
[15] LI Yu, CHAI Guo-zhong, LU Chun-fu, TANG Zhi-chuan. On-line sEMG Hand Gesture Recognition Based on Incremental Adaptive Learning [J]. Computer Science, 2019, 46(4): 274-279.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!