Incremental attribute reduction algorithm of positive region in interval-valued decision tables

doi:10.11772/j.issn.1001-9081.2018122518

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (8): 2288-2296.DOI: 10.11772/j.issn.1001-9081.2018122518

• Data science and technology • Previous Articles Next Articles

Incremental attribute reduction algorithm of positive region in interval-valued decision tables

BAO Di^1,2, ZHANG Nan^1,2, TONG Xiangrong^1,2, YUE Xiaodong³

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

Received:2018-12-21 Revised:2019-04-01 Online:2019-08-10 Published:2019-04-17
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61403329, 61572418, 61702439, 61572419, 61502410), the Shandong Provincial Natural Science Foundation (ZR2016FM42, ZR2018BA004).

区间值决策表的正域增量式属性约简算法

鲍迪^1,2, 张楠^1,2, 童向荣^1,2, 岳晓冬³

1. 数据科学与智能技术山东省高校重点实验室 (烟台大学), 山东烟台 264005;
2. 烟台大学计算机与控制工程学院, 山东烟台 264005;
3. 上海大学计算机工程与科学学院, 上海 200444

通讯作者: 张楠
作者简介:鲍迪(1994-),女,山东诸城人,硕士研究生,主要研究方向:粗糙集、数据挖掘、机器学习;张楠(1979-),男,山东烟台人,讲师,博士,CCF会员,主要研究方向:粗糙集、认知信息学、人工智能;童向荣(1975-),男,山东烟台人,教授,博士,主要研究方向:多Agent系统、数据挖掘、分布式人工智能;岳晓冬(1981-),男,山西太原人,副教授,博士,主要研究方向:机器学习、软计算、数据挖掘。
基金资助:
国家自然科学基金资助项目（61403329，61572418，61702439，61572419，61502410）；山东省自然科学基金资助项目（ZR2016FM42，ZR2018BA004）。

Abstract

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.

Key words: rough set, interval-valued decision table, tolerance relation, positive region, incremental attribute reduction

摘要： 实际应用中存在大量动态增加的区间型数据，若采用传统的非增量正域属性约简方法进行约简，则需要对更新后的区间值数据集的正域约简进行重新计算，导致属性约简的计算效率大大降低。针对上述问题，提出区间值决策表的正域增量属性约简方法。首先，给出区间值决策表正域约简的相关概念；然后，讨论并证明单增量和组增量的正域更新机制，提出区间值决策表的正域单增量和组增量属性约简算法；最后，通过8组UCI数据集进行实验。当8组数据集的数据量由60%增加至100%时，传统非增量属性约简算法在8组数据集中的约简耗时分别为36.59 s、72.35 s、69.83 s、154.29 s、80.66 s、1498.11 s、4124.14 s和809.65 s，单增量属性约简算法的约简耗时分别为19.05 s、46.54 s、26.98 s、26.12 s、34.02 s、1270.87 s、1598.78 s和408.65 s，组增量属性约简算法的约简耗时分别为6.39 s、15.66 s、3.44 s、15.06 s、8.02 s、167.12 s、180.88 s和61.04 s。实验结果表明，提出的区间值决策表的正域增量式属性约简算法具有高效性。

关键词: 粗糙集, 区间值决策表, 相容关系, 正域, 增量式属性约简

CLC Number:

TP181

BAO Di, ZHANG Nan, TONG Xiangrong, YUE Xiaodong. Incremental attribute reduction algorithm of positive region in interval-valued decision tables[J]. Journal of Computer Applications, 2019, 39(8): 2288-2296.

鲍迪, 张楠, 童向荣, 岳晓冬. 区间值决策表的正域增量式属性约简算法[J]. 计算机应用, 2019, 39(8): 2288-2296.

References

[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.

Incremental attribute reduction algorithm of positive region in interval-valued decision tables

区间值决策表的正域增量式属性约简算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Xiaorong, ZHANG Yuzhao, ZHANG Zhenjiang. Selection of express freight transportation schemes based on rough set over two universes [J]. Journal of Computer Applications, 2021, 41(5): 1500-1505.
[2]	PENG Li, ZHANG Haiqing, LI Daiwei, TANG Dan, YU Xi, HE Lei. Imputation algorithm for hybrid information system of incomplete data analysis approach based on rough set theory [J]. Journal of Computer Applications, 2021, 41(3): 677-685.
[3]	WANG Lei. Network intrusion detection method based on improved rough set attribute reduction and K-means clustering [J]. Journal of Computer Applications, 2020, 40(7): 1996-2002.
[4]	ZHANG Wu, CHEN Hongmei. Hyperspectral band selection based on multi-kernelized fuzzy rough set and grasshopper optimization algorithm [J]. Journal of Computer Applications, 2020, 40(5): 1425-1430.
[5]	ZHANG Xiajie, ZHU Jinghua, CHEN Yang. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[6]	OU Binli, ZHONG Xiaru, DAI Jianhua, YANG Tian. Intrusion detection method based on variable precision covering rough set [J]. Journal of Computer Applications, 2020, 40(12): 3465-3470.
[7]	ZHANG Wu, CHEN Hongmei. Hyperspectral band selection algorithm based on kernelized fuzzy rough set [J]. Journal of Computer Applications, 2020, 40(1): 258-263.
[8]	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.
[9]	KONG Heqing, ZHANG Nan, YUE Xiaodong, TONG Xiangrong, YU Tianyou. Positive region preservation reduction based on multi-specific decision classes in incomplete decision systems [J]. Journal of Computer Applications, 2019, 39(5): 1252-1260.
[10]	CHEN Manru, ZHANG Nan, TONG Xiangrong, DONGYE Shenglong, YANG Wenjing. Multi-scale attribute granule based quick positive region reduction algorithm [J]. Journal of Computer Applications, 2019, 39(12): 3426-3433.
[11]	ZHENG Wenbin, LI Jinjin, YU Peiqiu, LIN Yidong. Matrix-based algorithm for updating approximations in variable precision multi-granulation rough sets [J]. Journal of Computer Applications, 2019, 39(11): 3140-3145.
[12]	TAN Yongqi, FAN Jiancong, REN Yande, ZHOU Xiaoming. Improved attribute reduction algorithm and its application to prediction of microvascular invasion in hepatocellular carcinoma [J]. Journal of Computer Applications, 2019, 39(11): 3221-3226.
[13]	LI Xu, RONG Zijing, RUAN Xiaoxi. Attribute reduction of relative indiscernibility relation and discernibility relation in relation decision system [J]. Journal of Computer Applications, 2019, 39(10): 2852-2858.
[14]	YUAN Zhong, FENG Shan. Outlier detection algorithm based on neighborhood value difference metric [J]. Journal of Computer Applications, 2018, 38(7): 1905-1909.
[15]	WAN Zhichao, SONG Jie, SHENG Yongliang. Variable intuitionistic fuzzy multi-granulation rough set model and its approximate distribution reduction algorithms [J]. Journal of Computer Applications, 2018, 38(2): 390-398.