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

doi:10.11772/j.issn.1001-9081.2018122518

计算机应用 ›› 2019, Vol. 39 ›› Issue (8): 2288-2296.DOI: 10.11772/j.issn.1001-9081.2018122518

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

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

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

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

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

摘要/Abstract

摘要： 实际应用中存在大量动态增加的区间型数据，若采用传统的非增量正域属性约简方法进行约简，则需要对更新后的区间值数据集的正域约简进行重新计算，导致属性约简的计算效率大大降低。针对上述问题，提出区间值决策表的正域增量属性约简方法。首先，给出区间值决策表正域约简的相关概念；然后，讨论并证明单增量和组增量的正域更新机制，提出区间值决策表的正域单增量和组增量属性约简算法；最后，通过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。实验结果表明，提出的区间值决策表的正域增量式属性约简算法具有高效性。

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

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

中图分类号:

TP181

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

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王小荣, 张玉召, 张振江. 基于双论域粗糙集的快捷货物运输方案选择[J]. 计算机应用, 2021, 41(5): 1500-1505.
[2]	彭莉, 张海清, 李代伟, 唐聃, 于曦, 何磊. 基于粗糙集理论的不完备数据分析方法的混合信息系统填补算法[J]. 计算机应用, 2021, 41(3): 677-685.
[3]	王磊. 改进粗糙集属性约简结合K-means聚类的网络入侵检测方法[J]. 计算机应用, 2020, 40(7): 1996-2002.
[4]	张伍, 陈红梅. 基于多核模糊粗糙集与蝗虫优化算法的高光谱波段选择[J]. 计算机应用, 2020, 40(5): 1425-1430.
[5]	章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 计算机应用, 2020, 40(2): 518-523.
[6]	欧彬利, 钟夏汝, 代建华, 杨田. 基于变精度覆盖粗糙集的入侵检测方法[J]. 计算机应用, 2020, 40(12): 3465-3470.
[7]	张伍, 陈红梅. 基于核模糊粗糙集的高光谱波段选择算法[J]. 计算机应用, 2020, 40(1): 258-263.
[8]	徐怡, 肖鹏. 基于容差关系的多粒度粗糙集中近似集动态更新方法[J]. 计算机应用, 2019, 39(5): 1247-1251.
[9]	孔贺庆, 张楠, 岳晓冬, 童向荣, 于天佑. 基于多特定决策类的不完备决策系统正域约简[J]. 计算机应用, 2019, 39(5): 1252-1260.
[10]	陈曼如, 张楠, 童向荣, 东野升龙, 杨文静. 基于多尺度属性粒策略的快速正域约简算法[J]. 计算机应用, 2019, 39(12): 3426-3433.
[11]	郑文彬, 李进金, 于佩秋, 林艺东. 变精度多粒度粗糙集近似集更新的矩阵算法[J]. 计算机应用, 2019, 39(11): 3140-3145.
[12]	谭永奇, 樊建聪, 任延德, 周晓明. 改进的属性约简算法及其在肝癌微血管侵犯预测中的应用[J]. 计算机应用, 2019, 39(11): 3221-3226.
[13]	李旭, 荣梓景, 阮晓曦. 关系决策系统中相对不可区分和区分关系的约简[J]. 计算机应用, 2019, 39(10): 2852-2858.
[14]	袁钟, 冯山. 基于邻域值差异度量的离群点检测算法[J]. 计算机应用, 2018, 38(7): 1905-1909.
[15]	万志超, 宋杰, 沈永良. 可变直觉模糊多粒度粗糙集模型及其近似分布约简算法[J]. 计算机应用, 2018, 38(2): 390-398.