基于多目标邻域差分进化和模糊粗糙集的属性约简算法
|
摘要
作为粗糙集的一种推广,模糊粗糙集在属性约简中的应用尤为重要.约简规模和约简依赖度作为评判约简性能的两个重要指标,分别对应着约简的效率以及精度.传统的约简算法通常以追求约简的最大依赖度为导向进行寻优,并没有直接考虑约简的规模大小.基于此,强调所得约简的规模大小在约简运算中的重要性,并提出一种基于邻域变异信息的多目标差分算法,在约简运算中将约简的规模也作为单独的优化目标,将属性约简问题转化为多目标优化问题,综合考虑约简在属性数量和依赖度两方面的性能.通过引入目标支配排序,使得可以从属性数量和依赖度误差两方面对所得约简的性能进行约束,并得到目标约束内的约简结果.选取UCI上的数据集进行实验分析,实验结果表明,所提算法可以在目标约束内得到更加全面的约简结果,具有一定的可行性,是一种有效的约简算法.
As a generalization of rough set, fuzzy rough set plays a significant role in attribute reduction. Reduct size and dependency degree are two important evaluation criteria to measure reduction performance. Traditional reduction algorithms are mainly designed with the direction of maximizing dependency degree and reduct size is not taken into consideration. This paper emphasizes the significance of reduct size and proposes an multiobjective difference algorithm based on neighborhood mutation information, which makes reduct size a separate objective in attribute reduction. Hence the reduction problem is turned into multiobjective optimization problem, which considers reduction performance from aspects of both attribute number and dependency degree. By using goal-sequence domination scheme, the reduction performance can be stipulated from aspects of attribute number and dependency degree and satisfactory reduction results can be obtained. Several UCI data sets are applied to analyze the algorithm performance. The experimental results show that this method can obtain more comprehensive reduction results, which is feasible and effective.
As a generalization of rough set, fuzzy rough set plays a significant role in attribute reduction. Reduct size and dependency degree are two important evaluation criteria to measure reduction performance. Traditional reduction algorithms are mainly designed with the direction of maximizing dependency degree and reduct size is not taken into consideration. This paper emphasizes the significance of reduct size and proposes an multiobjective difference algorithm based on neighborhood mutation information, which makes reduct size a separate objective in attribute reduction. Hence the reduction problem is turned into multiobjective optimization problem, which considers reduction performance from aspects of both attribute number and dependency degree. By using goal-sequence domination scheme, the reduction performance can be stipulated from aspects of attribute number and dependency degree and satisfactory reduction results can be obtained. Several UCI data sets are applied to analyze the algorithm performance. The experimental results show that this method can obtain more comprehensive reduction results, which is feasible and effective.
引文
[1] Pawlak Z. Rough sets[J]. Int J of Computer and Information Science, 1982, 11(5):341-356.
[2] Dubois D, Prade H. Rough fuzzy sets and fuzzy rough sets[J]. Int J of General Systems, 1990, 17(2/3):191-208.
[3] An S, Hu Q H, Pedrycz W, et al. Data-distribution-aware fuzzy rough set model and its application to robust classification[J]. IEEE Trans on Cybernetics, 2016,46(12):3073-3085.
[4]付志耀,高岭,孙骞,等.基于粗糙集的漏洞属性约简及严重性评估[J].计算机研究与发展, 2016, 53(5):1009-1017.(Fu Z Y, Gao L, Sun Q, et al. Evaluation of vulnerability severity based on rough sets and attributes reduction[J].J of Computer Research and Development, 2016, 53(5):1009-1017.)
[5]张清华,胡荣德,姚龙洋,等.基于属性重要度的风险决策粗糙集属性约简[J].控制与决策, 2016, 31(7):1199-1205.(Zhang Q H, Hu R D, Yao L Y, et al. Risk DTRS attribute reduction based on attribute importance[J]. Control and Decision, 2016, 31(7):1199-1205.)
[6]叶东毅,陈昭炯.最小属性约简问题的一个有效的组合人工蜂群算法[J].电子学报, 2015, 43(5):1014-1020.(Ye D Y, Chen Z J. An efficient combinatorial artificial bee colony algorithm for solving minimum attribute reduction problem[J]. Acta Electronica Sinica, 2015,43(5):1014-1020.)
[7] Gu X P, Li Y, Jia J H. Feature selection for transient stability assessment based on kernelized fuzzy rough sets and memetic algorithm[J]. Int J of Electrical Power and Energy Systems, 2015, 64:664-670.
[8] Chen L, Liu H L, Wan Z L. An attribute reduction algorithm based on rough set theory and an improved genetic algorithm[J]. J of Software, 2014, 9(9):2276-2282.
[9] Chebrolu S, Sanjeevi S G. Attribute reduction on real-valued data in rough set theory using hybrid artificial bee colony:Extended FTSBPSD algorithm[J]. Soft Computing, 2016, 21(24):7543-7569.
[10] Zouache D, Ben A F. A cooperative swarm intelligence algorithm based on quantum-inspired and rough sets for feature selection[J]. Computers and Industrial Engineering, 2018, 115:26-36.
[11]徐雪松,陈荣元.融合粗糙集与小生境免疫优化的属性约简方法[J].电子学报, 2014, 42(8):1545-1550.(Xu X S, Chen R Y. Attribute decision reduction method based on hybrid rough sets and niche immune optimization[J]. Acta Electronica Sinica, 2014, 42(8):1545-1550.)
[12]续欣莹,张扩,谢珺,等.基于互信息下粒子群优化的属性约简算法[J].电子学报, 2017, 45(11):2695-2704.(Xu X Y, Zhang K, Xie J, et al. An attribute reduction algorithm based on mutual information of particle swarm optimization[J]. Acta Electronica Sinica, 2017, 45(11):2695-2704.)
[13]段洁,胡清华,张灵均,等.基于邻域粗糙集的多标记分类特征选择算法[J].计算机研究与发展, 2015,52(1):56-65.(Duan J, Hu Q H, Zhang L J, et al. Feature selection for multi-label classification based on neighborhood rough sets[J]. J of Computer Research and Development, 2015,52(1):56-65.)
[14]张腾飞,肖健梅,王锡淮.粗糙集理论中属性相对约简算法[J].电子学报, 2005, 33(11):2080-2083.(Zhang T F, Xiao J M, Wang X H. Algorithms of attribute relative reduction in rough set theory[J]. Acta Electronica Sinica, 2005, 33(11):2080-2083.)
[15] Li F, Hu B Q, Wang J. Stepwise optimal scale selection for multi-scale decision tables via attribute significance[J].Knowledge-Based Systems, 2017, 129:4-16.
[16] Hu Q H, Zhang L, Chen D G, et al. Gaussian kernel based fuzzy rough sets:Model, uncertainty measures and applications[J]. Int J of Approximate Reasoning, 2010,51(4):453-457.
[17] Raza M S, Qamar U. Feature selection using rough set-based direct dependency calculation by avoiding the positive region[J]. Int J of Approximate Reasoning, 2018,92:175-197.
[18]何松华,康婵娟,鲁敏,等.基于邻域组合测度的属性约简方法[J].控制与决策, 2016, 31(7):1225-1230.(He S H, Kang C J, Lu M, et al. Attribute reduction method based on neighborhood combination measure[J].Control and Decision, 2016, 31(7):1225-1230.)
[19] Wang C Z, Qi Y L, Shao M W, et al. A fitting model for feature selection with fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems, 2017, 25(4):741-753.
[20] Hu Q H, Zhang L J, Zhou Y C, et al. Large-scale multimodality attribute reduction with multi-kernel fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems, 2018, 26(1):226-238.
[21] Du W S, Hu B Q. A fast heuristic attribute reduction approach to ordered decision systems[J]. European J of Operational Research, 2018, 264(2):440-452.
[22]马福民,陈静雯,张腾飞.基于双重粒化准则的邻域多粒度粗集快速约简算法[J].控制与决策, 2017, 32(6):1121-1127.(Ma F M, Chen J W, Zhang T F. Quick attribute reduction algorithm for neighborhood multi-granulation rough set based on double granulate criterion[J]. Control and Decision, 2017, 32(6):1121-1127.)
[23] Wei W, Wu X Y, Liang J Y, et al. Discernibility matrix based incremental attribute reduction for dynamic data[J].Knowledge-Based Systems, 2018, 140:142-157.
[24] Chen D G, Yang Y Y. Attribute reduction for heterogeneous data based on the combination of classical and fuzzy rough set models[J]. IEEE Trans on Fuzzy Systems, 2014, 22(5):1325-1334.
[25] He Q, Wu C X, Chen D G, et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems, 2011, 24(5):689-696.
[26] Liu G L, Hua Z. Partial attribute reduction approaches to relation systems and their applications[J].Knowledge-Based systems, 2018, 139:101-107.
[27] Dai J H, Hu Q H, Zhang J H, et al. Attribute selection for partially labeled categorical data by rough set approach[J]. IEEE Trans on Cybernetics, 2017, 47(9):2460-2471.
[28] Yeung D, Chen D G, Tsang E, et al. On the generalization of fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems,2005, 13(3):343-361.
[29] Tan K, Khor E, Lee T, et al. An evolutionary algorithm with advanced goal and priority specification for multi-objective optimization[J]. J of Artificial Intelligence Research, 2003, 18(1):183-215.
[30] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2):182-197.
[2] Dubois D, Prade H. Rough fuzzy sets and fuzzy rough sets[J]. Int J of General Systems, 1990, 17(2/3):191-208.
[3] An S, Hu Q H, Pedrycz W, et al. Data-distribution-aware fuzzy rough set model and its application to robust classification[J]. IEEE Trans on Cybernetics, 2016,46(12):3073-3085.
[4]付志耀,高岭,孙骞,等.基于粗糙集的漏洞属性约简及严重性评估[J].计算机研究与发展, 2016, 53(5):1009-1017.(Fu Z Y, Gao L, Sun Q, et al. Evaluation of vulnerability severity based on rough sets and attributes reduction[J].J of Computer Research and Development, 2016, 53(5):1009-1017.)
[5]张清华,胡荣德,姚龙洋,等.基于属性重要度的风险决策粗糙集属性约简[J].控制与决策, 2016, 31(7):1199-1205.(Zhang Q H, Hu R D, Yao L Y, et al. Risk DTRS attribute reduction based on attribute importance[J]. Control and Decision, 2016, 31(7):1199-1205.)
[6]叶东毅,陈昭炯.最小属性约简问题的一个有效的组合人工蜂群算法[J].电子学报, 2015, 43(5):1014-1020.(Ye D Y, Chen Z J. An efficient combinatorial artificial bee colony algorithm for solving minimum attribute reduction problem[J]. Acta Electronica Sinica, 2015,43(5):1014-1020.)
[7] Gu X P, Li Y, Jia J H. Feature selection for transient stability assessment based on kernelized fuzzy rough sets and memetic algorithm[J]. Int J of Electrical Power and Energy Systems, 2015, 64:664-670.
[8] Chen L, Liu H L, Wan Z L. An attribute reduction algorithm based on rough set theory and an improved genetic algorithm[J]. J of Software, 2014, 9(9):2276-2282.
[9] Chebrolu S, Sanjeevi S G. Attribute reduction on real-valued data in rough set theory using hybrid artificial bee colony:Extended FTSBPSD algorithm[J]. Soft Computing, 2016, 21(24):7543-7569.
[10] Zouache D, Ben A F. A cooperative swarm intelligence algorithm based on quantum-inspired and rough sets for feature selection[J]. Computers and Industrial Engineering, 2018, 115:26-36.
[11]徐雪松,陈荣元.融合粗糙集与小生境免疫优化的属性约简方法[J].电子学报, 2014, 42(8):1545-1550.(Xu X S, Chen R Y. Attribute decision reduction method based on hybrid rough sets and niche immune optimization[J]. Acta Electronica Sinica, 2014, 42(8):1545-1550.)
[12]续欣莹,张扩,谢珺,等.基于互信息下粒子群优化的属性约简算法[J].电子学报, 2017, 45(11):2695-2704.(Xu X Y, Zhang K, Xie J, et al. An attribute reduction algorithm based on mutual information of particle swarm optimization[J]. Acta Electronica Sinica, 2017, 45(11):2695-2704.)
[13]段洁,胡清华,张灵均,等.基于邻域粗糙集的多标记分类特征选择算法[J].计算机研究与发展, 2015,52(1):56-65.(Duan J, Hu Q H, Zhang L J, et al. Feature selection for multi-label classification based on neighborhood rough sets[J]. J of Computer Research and Development, 2015,52(1):56-65.)
[14]张腾飞,肖健梅,王锡淮.粗糙集理论中属性相对约简算法[J].电子学报, 2005, 33(11):2080-2083.(Zhang T F, Xiao J M, Wang X H. Algorithms of attribute relative reduction in rough set theory[J]. Acta Electronica Sinica, 2005, 33(11):2080-2083.)
[15] Li F, Hu B Q, Wang J. Stepwise optimal scale selection for multi-scale decision tables via attribute significance[J].Knowledge-Based Systems, 2017, 129:4-16.
[16] Hu Q H, Zhang L, Chen D G, et al. Gaussian kernel based fuzzy rough sets:Model, uncertainty measures and applications[J]. Int J of Approximate Reasoning, 2010,51(4):453-457.
[17] Raza M S, Qamar U. Feature selection using rough set-based direct dependency calculation by avoiding the positive region[J]. Int J of Approximate Reasoning, 2018,92:175-197.
[18]何松华,康婵娟,鲁敏,等.基于邻域组合测度的属性约简方法[J].控制与决策, 2016, 31(7):1225-1230.(He S H, Kang C J, Lu M, et al. Attribute reduction method based on neighborhood combination measure[J].Control and Decision, 2016, 31(7):1225-1230.)
[19] Wang C Z, Qi Y L, Shao M W, et al. A fitting model for feature selection with fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems, 2017, 25(4):741-753.
[20] Hu Q H, Zhang L J, Zhou Y C, et al. Large-scale multimodality attribute reduction with multi-kernel fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems, 2018, 26(1):226-238.
[21] Du W S, Hu B Q. A fast heuristic attribute reduction approach to ordered decision systems[J]. European J of Operational Research, 2018, 264(2):440-452.
[22]马福民,陈静雯,张腾飞.基于双重粒化准则的邻域多粒度粗集快速约简算法[J].控制与决策, 2017, 32(6):1121-1127.(Ma F M, Chen J W, Zhang T F. Quick attribute reduction algorithm for neighborhood multi-granulation rough set based on double granulate criterion[J]. Control and Decision, 2017, 32(6):1121-1127.)
[23] Wei W, Wu X Y, Liang J Y, et al. Discernibility matrix based incremental attribute reduction for dynamic data[J].Knowledge-Based Systems, 2018, 140:142-157.
[24] Chen D G, Yang Y Y. Attribute reduction for heterogeneous data based on the combination of classical and fuzzy rough set models[J]. IEEE Trans on Fuzzy Systems, 2014, 22(5):1325-1334.
[25] He Q, Wu C X, Chen D G, et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems, 2011, 24(5):689-696.
[26] Liu G L, Hua Z. Partial attribute reduction approaches to relation systems and their applications[J].Knowledge-Based systems, 2018, 139:101-107.
[27] Dai J H, Hu Q H, Zhang J H, et al. Attribute selection for partially labeled categorical data by rough set approach[J]. IEEE Trans on Cybernetics, 2017, 47(9):2460-2471.
[28] Yeung D, Chen D G, Tsang E, et al. On the generalization of fuzzy rough sets[J]. IEEE Trans on Fuzzy Systems,2005, 13(3):343-361.
[29] Tan K, Khor E, Lee T, et al. An evolutionary algorithm with advanced goal and priority specification for multi-objective optimization[J]. J of Artificial Intelligence Research, 2003, 18(1):183-215.
[30] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2):182-197.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |