Incremental attribute reduction algorithm of positive region in interval-valued decision tables
BAO Di1,2, ZHANG Nan1,2, TONG Xiangrong1,2, YUE Xiaodong3
1. Key Lab for Data Science and Intelligence Technology of Shandong Higher Education Institutes(Yantai University), Yantai Shandong 264005, China; 2. School of Computer and Control Engineering, Yantai University, Yantai Shandong 264005, China; 3. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China
Abstract：There are a large number of dynamically-increasing interval data in practical applications. If the classic non-incremental attribute reduction of positive region is used for reduction, it is necessary to recalculate the positive region reduction of the updated interval-valued datasets, which greatly reduces the computational efficiency of attribute reduction. In order to solve the problem, incremental attribute reduction methods of positive region in interval-valued decision tables were proposed. Firstly, the related concepts of positive region reduction in interval-valued decision tables were defined. Then, the single and group incremental mechanisms of positive region were discussed and proved, and the single and group incremental attribute reduction algorithms of positive region in interval-valued decision tables were proposed. Finally, 8 UCI datasets were used to carry out experiments. When the incremental size of 8 datasets increases from 60% to 100%, the reduction time of classic non-incremental attribute reduction algorithm in the 8 datasets is 36.59 s, 72.35 s, 69.83 s, 154.29 s, 80.66 s, 1498.11 s, 4124.14 s and 809.65 s, the reduction time of single incremental attribute reduction algorithm is 19.05 s, 46.54 s, 26.98 s, 26.12 s, 34.02 s, 1270.87 s, 1598.78 s and 408.65 s, the reduction time of group incremental attribute reduction algorithm is 6.39 s, 15.66 s, 3.44 s, 15.06 s, 8.02 s, 167.12 s, 180.88 s and 61.04 s. Experimental results show that the proposed incremental attribute reduction algorithm of positive region in interval-valued decision tables is efficient.
[1] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11(5):341-356. [2] 王国胤,姚一豫,于洪.粗糙集理论与应用研究综述[J].计算机学报,2009,32(7):1229-1246. (WANG G Y, YAO Y Y, YU H. A survey on rough set theory and applications[J]. Chinese Journal of Computers, 2009, 32(7):1229-1246.) [3] LI D, ZHANG B, LEUNG Y. On knowledge reduction in inconsistent decision information systems[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2004, 12(5):651-672. [4] QIAN Y, LIANG J, PEDRYCZ W, et al. Positive approximation:an accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(9/10):597-618. [5] 苗夺谦,胡桂荣.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684. (MIAO D Q, HU G R. A heuristic algorithm for reduction of knowledge[J]. Journal of Computer Research and Development, 1999, 36(6):681-684.) [6] XU W, LI Y, LIAO X. Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J]. Knowledge-Based Systems, 2012, 27:78-91. [7] MIN F, HE H, QIAN Y, et al. Test-cost-sensitive attribute reduction[J]. Information Sciences, 2011, 181(22):4928-4942. [8] HU X, CERCONE N. Learning in relational databases:a rough set approach[J]. International Journal of Computational Intelligence, 1995, 11(2):323-338. [9] QIAN Y, LIANG X, WANG Q, et al. Local rough set:a solution to rough data analysis in big data[J]. International Journal of Approximate Reasoning, 2018, 97:38-63. [10] JIA X, LIAO W, TANG Z, et al. Minimum cost attribute reduction in decision-theoretic rough set models[J]. Information Sciences, 2013, 219:151-167. [11] LEUNG Y, FISCHER M M, WU W-Z, et al. A rough set approach for the discovery of classification rules in interval-valued information systems[J]. International Journal of Approximate Reasoning, 2008, 47(2):233-246. [12] 张楠,苗夺谦,岳晓冬.区间值信息系统的知识约简[J].计算机研究与发展,2010,47(8):1362-1371. (ZHANG N, MIAO D Q, YUE X D. Approaches to knowledge reduction in interval-valued information systems[J]. Journal of Computer Research and Development, 2010, 47(8):1362-1371.) [13] 刘鹏惠,陈子春,秦克云.区间值信息系统的决策属性约简[J].计算机工程与应用,2009,45(28):148-151. (LIU P H, CHEN Z C, QIN K Y. Decision attribute reduction of interval-valued information system[J]. Computer Engineering and Applications, 2009, 45(28):148-151.) [14] 徐菲菲,雷景生,毕忠勤,等.大数据环境下多决策表的区间值全局近似约简[J].软件学报,2014,25(9):2119-2135. (XU F F, LEI J S, BI Z Q, et al. Approaches to approximate reduction with interval-valued multi-decision tables in big data[J]. Journal of Software, 2014, 25(9):2119-2135.) [15] DAI J, WANG W, XU Q, et al. Uncertainty measurement for interval-valued decision systems based on extended conditional entropy[J]. Knowledge-Based Systems, 2012, 27:443-450. [16] SHU W, QIAN W, XIE Y. Incremental approaches for feature selection from dynamic data with the variation of multiple objects[J]. Knowledge-Based Systems, 2019, 163:320-331. [17] JING Y, LI T, FUJITA H, et al. An incremental attribute reduction method for dynamic data mining[J]. Information Sciences, 2018, 465:202-218. [18] WEI W, WU X, LIANG J, et al. Discernibility matrix based incremental attribute reduction for dynamic data[J]. Knowledge-Based Systems, 2018, 140:142-157. [19] XIE X, QIN X. A novel incremental attribute reduction approach for dynamic incomplete decision systems[J]. International Journal of Approximate Reasoning, 2018, 93:443-462. [20] HU F, WANG G Y, HUANG H, et al. Incremental attribute reduction based on elementary sets[C]//Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, LNCS 3641. Berlin:Springer, 2005:185-193. [21] XU Y, WANG L, ZHANG R. A dynamic attribute reduction algorithm based on 0-1 integer programming[J]. Knowledge-Based Systems, 2011, 24(8):1341-1347. [22] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-822. (YANG M. An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J]. Chinese Journal of Computers, 2007, 30(5):815-822.) [23] 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. [24] SHU W, QIAN W. An incremental approach to attribute reduction from dynamic incomplete decision systems in rough set theory[J]. Data and Knowledge Engineering, 2015, 100(Part A):116-132. [25] YU J, XU W. Incremental knowledge discovering in interval-valued decision information system with the dynamic data[J]. International Journal of Machine Learning and Cybernetics, 2017, 8(3):849-864. [26] WANG F, LIANG J, QIAN Y. Attribute reduction:a dimension incremental strategy[J]. Knowledge-Based Systems, 2013, 39:95-108. [27] LIU D, LI T, ZHANG J. Incremental updating approximations in probabilistic rough sets under the variation of attributes[J]. Knowledge-Based Systems, 2015, 73:81-96. [28] CHENG Y. The incremental method for fast computing the rough fuzzy approximations[J]. Data and Knowledge Engineering, 2011, 70(1):84-100. [29] 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. [30] 张楠,许鑫,童向荣,等.不协调区间值决策系统的知识约简[J].小型微型计算机系统,2017,38(7):1585-1589. (ZHANG N, XU X, TONG X R, et al. Knowledge reduction in inconsistent interval-valued decision systems[J]. Journal of Chinese Computer Systems, 2017, 38(7):1585-1589.) [31] DAI J-H, HU H, ZHENG G-J, et al. Attribute reduction in interval-valued information systems based on information entropies[J]. Frontiers of Information Technology and Electronic Engineering, 2016, 17(9):919-928. [32] ZHANG X, MEI C, CHEN D, et al. Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems[J]. International Journal of Approximate Reasoning, 2014, 55(8):1787-1804.
2019, Vol. 39 
