基于小生境离散差分演化的粗糙集属性约简方法研究
|
摘要
高效的属性约简算法是粗糙集理论在智能决策和数据挖掘等领域应用的必要基础。有研究者已经从理论上证明找出一个信息系统的最小约简是一个属性组合的爆炸性增长问题，不存在统一并且高效规范的约简算法。因此，探求更为有效的属性约简算法，快速地找到更多的最优约简或次优约简，使得算法的时间复杂度与空间复杂度更低，是粗糙集理论深入研究的重要课题。
本文首先阐述了粗糙集、差分演化和小生境等基础理论知识，研究了粗糙集理论的属性约简一般方法，如基于差别矩阵的属性约简算法、基于差别函数的属性约简算法和基于属性依赖度的属性约简方法等，重点研究了基于属性依赖度的差分演化属性约简方法，同时也分析比较了各约简算法的优缺点。
在分析和研究的基础上，针对原始的差分演化属性约简算法可能出现早熟现象而容易陷入局部最优解的情况，设计出了一种新的基于属性依赖度的小生境离散差分演化粗糙集属性约简算法。该算法主要特点是将生物学中小生境的概念引入到粗糙集属性约简中，采用基于类似于淘汰模式的小生境排斥运算机制，通过引入惩罚函数的方式调整种群中个体的适应度，让种群中的个体在不同的生存环境中进化，从而维持群体的多样性，确保约简算法能够在整个可行解空间里搜索，找到更多的属性相对最小约简。
最后，通过实验进行分析和比较，验证了基于属性依赖度的小生境离散差分演化粗糙集属性约简算法是可行有效的，它在求解出决策表更多的属性相对最小约简方面有明显的优势。
Efficient attribute reduction algorithm is the necessary foundation of applicationin the field of intelligent decision and data mining with rough set theory. Someresearchers have proven that it is hard to find the minimal reduction of aninformation system because of the explosive growth of a property combination, andthere is no unified and standard reduction algorithm. Therefore, to explore moreefficient attribute reduction algorithm to quickly find the optimal reduction orsuboptimal reduction is an important issue of rough set theory.
This paper first elaborate on the rough set theory, differential evolution theory,niche theory and some general methods to decision table’s attribute reduction inrough set theory, such as attribute reduction algorithms based on discernibilitymatrix, attribute reduction algorithms based on discernibility function and attributereduction algorithms based on attribute dependency and so on, with special emphasison analysis of differential evolution reduction algorithm base on the attributedependency. At the same time, also analyze the advantages and disadvantages ofeach algorithm.
Then, on the basis of analysis and comparison, to deal with the problems ofpremature convergence, a novel attribute reduction algorithm is proposed—the nichediscrete differential evolution reduction algorithm based on attribute dependency.The main feature of the algorithm is the introduction of niche that is the concept ofbiology to attribute reduction. On the one hand, the new algorithm uses nicheexcluded mechanism as like as eliminative method. On the other hand, in order tomaintain the diversity of the population, the new algorithm introduces a penaltyfunction to adjust the fitness of individuals in the population, so that the individualsevolve in different living environments and more relative minimum reductions canbe found.
Finally, the analysis and comparison of experiments proved that the nichediscrete differential evolution reduction algorithm based on attribute dependency iseffective and has its own advantages on finding more relative minimum reductions.
本文首先阐述了粗糙集、差分演化和小生境等基础理论知识，研究了粗糙集理论的属性约简一般方法，如基于差别矩阵的属性约简算法、基于差别函数的属性约简算法和基于属性依赖度的属性约简方法等，重点研究了基于属性依赖度的差分演化属性约简方法，同时也分析比较了各约简算法的优缺点。
在分析和研究的基础上，针对原始的差分演化属性约简算法可能出现早熟现象而容易陷入局部最优解的情况，设计出了一种新的基于属性依赖度的小生境离散差分演化粗糙集属性约简算法。该算法主要特点是将生物学中小生境的概念引入到粗糙集属性约简中，采用基于类似于淘汰模式的小生境排斥运算机制，通过引入惩罚函数的方式调整种群中个体的适应度，让种群中的个体在不同的生存环境中进化，从而维持群体的多样性，确保约简算法能够在整个可行解空间里搜索，找到更多的属性相对最小约简。
最后，通过实验进行分析和比较，验证了基于属性依赖度的小生境离散差分演化粗糙集属性约简算法是可行有效的，它在求解出决策表更多的属性相对最小约简方面有明显的优势。
Efficient attribute reduction algorithm is the necessary foundation of applicationin the field of intelligent decision and data mining with rough set theory. Someresearchers have proven that it is hard to find the minimal reduction of aninformation system because of the explosive growth of a property combination, andthere is no unified and standard reduction algorithm. Therefore, to explore moreefficient attribute reduction algorithm to quickly find the optimal reduction orsuboptimal reduction is an important issue of rough set theory.
This paper first elaborate on the rough set theory, differential evolution theory,niche theory and some general methods to decision table’s attribute reduction inrough set theory, such as attribute reduction algorithms based on discernibilitymatrix, attribute reduction algorithms based on discernibility function and attributereduction algorithms based on attribute dependency and so on, with special emphasison analysis of differential evolution reduction algorithm base on the attributedependency. At the same time, also analyze the advantages and disadvantages ofeach algorithm.
Then, on the basis of analysis and comparison, to deal with the problems ofpremature convergence, a novel attribute reduction algorithm is proposed—the nichediscrete differential evolution reduction algorithm based on attribute dependency.The main feature of the algorithm is the introduction of niche that is the concept ofbiology to attribute reduction. On the one hand, the new algorithm uses nicheexcluded mechanism as like as eliminative method. On the other hand, in order tomaintain the diversity of the population, the new algorithm introduces a penaltyfunction to adjust the fitness of individuals in the population, so that the individualsevolve in different living environments and more relative minimum reductions canbe found.
Finally, the analysis and comparison of experiments proved that the nichediscrete differential evolution reduction algorithm based on attribute dependency iseffective and has its own advantages on finding more relative minimum reductions.
引文
[1] Pawlak Z. Routh set[J]. International Journal of Computer and Information Sciences, 1982,11:341-356.
[2] Pawlak Z. Routh sets-Theoretical Aspects of Reasoning about Data[M]. Dordrecht:KluwerAcademic Publish, 1991.
[3] Pawlak Z. Routh set theory and its application to data analysis[J]. Cybernetics and System,1998, 29(27):661-688.
[4] Amitava R, Pa Sankar K. Fuzzy discretization of feature space for a rough set classifier[J].Pattern Recognition Letters, 2003(24):895-902.
[5] Frank W, Hans T. The application of Rough Sets analysis in activity-based modeling:opportunities and constraints[J]. Expert Systems with Application, 2004(162):65-80.
[6] Wang J, Miao D Q. Analysis on attribute reduction strategies of rough set[J]. Journal ofComputer Science and Technology, 1998, 13(2):189-192.
[7] Bag A.K, Tudu B, Roy J, Optimization of Sensor Array in Electronic Nose:A RoughSet-Based Approach[J]. Sensors Journal, 2011, 11(11):3001-3008.
[8] Bilski P, Wojciechowshi J M, Rough-Sets-Based Reduction for Analog SystemsDiagnostics[J]. Instrumentation and Measurement, 2011, 60(3):880-890.
[9] Hassanien A E, Abraham A, Peters J F, Rough Sets and Near Sets in Medical Imaging: AReview[J]. Information Technology in Biomedicine, 2009, 13(6):955-968.
[10]苗夺谦. Rough Set理论及其在机器学习中的应用研究[D].博士学位论文，中国科学院自动化研究所，北京，1997.
[11]曾黄麟.粗集理论及其应用[M].重庆:重庆大学出版社, 1996.
[12]刘清，黄兆华，姚力文.粗糙集理论：现状与前景[J].计算机科学, 1997, 24(4):1-5.
[13]苗夺谦，王珏. Analysis on Attribute Reduction Strategies of Rough Set[J]. Journal ofComputer Science and Technology, 1998, 13(2):189-194.
[14]苗夺谦，王珏.粗糙集理论中知识粗糙性与信息熵关系的讨论[J].模式识别与人工智能, 1998, 11(1):30-40.
[15]苗夺谦，王珏.粗糙集理论中概念与运算的信息表示[J].软件学报, 1999,10(2):113-116.
[16]常梨云，王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报, 1999, 10(11):1206-1211.
[17]王国胤. Rough集理论在不完备信息系统中的扩充[J].计算机研究与发展, 2002,39(10):1238-1243.
[18]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报, 2002,25(7):759-766.
[19]王国胤.决策表核属性的计算方法[J].计算机学报, 2003, 26(5):611-615.
[20]赵军,王国胤,吴中福等.基于粗集理论的数据离散化方法[J].小型微型计算机系统, 2004, 25(1):59-64.
[21]王国胤. Rough集理论与适应获取[M].西安:西安交通大学出版社, 2001.
[22]颜艳,杨慧中.基于遗传算法的粗集属性约简算法[J].计算机工程与应用, 2007,43(31):156-158.
[23]袁晓峰,许化龙,陈淑红.基于量子遗传算法的粗集属性约简新算法[J].计算机工程, 2007, 33(15):184-186.
[24]姚跃华，洪杉.基于自适应蚁群算法的粗糙集属性约简[J].计算机工程, 2011,37(3):198-200.
[25] Hu Keyun, Lu Yuchang, Shi Chunyi. Feature Ranking in Rough Sets[J]. AICommunications, 2003, 16(1):41-50.
[26]杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报, 2007,30(5):815-822.
[27]杨明.一种基于一致性准则的属性约简算法[J].计算机学报, 2010, 30(5):231-239.
[28]胡清华,于达仁,谢宗霞.基于领域粒化和粗糙逼进的数值属性约简[J].软件学报,2007, 19(3):640-649.
[29]陈玉明,苗夺谦.基于幂图的属性约简搜索式算法[J].计算机学报, 2009,32(8):1486-1492.
[30]甄宇峰,施化吉.基于条件信息熵和相关系统的属性约简算法[J].计算机工程与应用, 2011, 47(16):26-28.
[31]吴静,邹海.基于属性重要性的属性约简新算法[J].计算机应用与软件, 2010,27(2):255-257.
[32] Wong S.K.M, Ziarko W. On optional decision rules in decision tables[J]. Bulletin ofPolish Academy of Sciences, 1985, 33(11/12):693-696.
[33] Stron R, Price K. Differential evolution-a simple and efficient adaptive scheme for globaloptimization over continuous spaces[R]. Technical Report TR-95-012. Berkeley:International Computer Science Institute, 1995.
[34] Stron R, Price K. Differential evolution-a simple and efficient heuristic for globaloptimization over contiuous spaces[J]. Journal of Global Optimization, 1997,11(4):341-359.
[35] Versterstrom J, Thomsen R. A comparative study of differential evolution,particle swarmoptimization,and evolutionary algorithm on numerical benchmark problem[C]//Evolutionary Computation,CEC2004. Portland OR:IEEE Press, 2004, 2:1980-1987.
[36] Slowik A. Application of an Adaptive Differential Evolution Algorithm With MultipleTrial Vectors to Artificial Neural Network Training [J]. Industrial Electronics, 2011,58(8):3160-3167.
[37] Neri F, Mininno E. Mimetic Compact Differential Evolution for Cartesian Robot Control[J]. Computational Intelligence Magazine. 2010, 5(2):54-65.
[38] Pandit M. Discussion of“Hybrid Differential Evolution With Biogeography-BasedOptimization for Solution of Economic Load Dispatch”[J]. Power Systems, 2012,27(1):574-575.
[39] Yikai Chen, Shiwen Yang, Zaiping Nie. The Application of a Modified DifferentialEvolution Strategy to some Array Pattern Synthesis Problems[J]. Antennas andPropagation. 2008, 56(7):1919-1927.
[40] Hannan M, Freeman J. Organizational ecology[M]. Cambridge, MA: Harvard UniversityPress, 1989.
[41] Qian Yan, Ren Hao, Research on the Competitive Relationship of Enterprises Based onNiche Theory[J]. Finance and Trade Research, 2006.(2):123-127.
[42] Yan Aimin. Study on Human Resource ecosystem [J]. Journal of Central SouthUniversity, 2006, 12(1):67-71.
[43] Zhu Chunquan. The Niche Ecostate-Ecorole Theory and Expansion Hypothesis[J]. ActsEcological Science, 1997, 17(3):324-332.
[44]苗夺谦,李道国.粗糙集理论、算法与应用[M].北京:清华大学出版社, 2008.
[45]杨启文,蔡亮,薛云灿.差分进化算法综述[J].模式识别与人工智能, 2008,21(4):506-513.
[46]李旭渊,许化龙.一种基于免疫小生境思想的粒子群优化算法[J].计算机工程与应用, 2008, 44(8):95-97.
[47] UCI repository of machine learning database[EO/OL]. http://www.cs.uci.edu/~mlearn/MLRepository.html.
[48]陶志,许国栋,汪定伟等.基于遗传算法的粗糙集知识约简方法[J].系统工程, 2003,21 (4):116-122.
[49]王杨.基于小生境遗传算法的粗糙集属性约简方法[J].计算机工程, 2008, 34(5):66-70.
[2] Pawlak Z. Routh sets-Theoretical Aspects of Reasoning about Data[M]. Dordrecht:KluwerAcademic Publish, 1991.
[3] Pawlak Z. Routh set theory and its application to data analysis[J]. Cybernetics and System,1998, 29(27):661-688.
[4] Amitava R, Pa Sankar K. Fuzzy discretization of feature space for a rough set classifier[J].Pattern Recognition Letters, 2003(24):895-902.
[5] Frank W, Hans T. The application of Rough Sets analysis in activity-based modeling:opportunities and constraints[J]. Expert Systems with Application, 2004(162):65-80.
[6] Wang J, Miao D Q. Analysis on attribute reduction strategies of rough set[J]. Journal ofComputer Science and Technology, 1998, 13(2):189-192.
[7] Bag A.K, Tudu B, Roy J, Optimization of Sensor Array in Electronic Nose:A RoughSet-Based Approach[J]. Sensors Journal, 2011, 11(11):3001-3008.
[8] Bilski P, Wojciechowshi J M, Rough-Sets-Based Reduction for Analog SystemsDiagnostics[J]. Instrumentation and Measurement, 2011, 60(3):880-890.
[9] Hassanien A E, Abraham A, Peters J F, Rough Sets and Near Sets in Medical Imaging: AReview[J]. Information Technology in Biomedicine, 2009, 13(6):955-968.
[10]苗夺谦. Rough Set理论及其在机器学习中的应用研究[D].博士学位论文，中国科学院自动化研究所，北京，1997.
[11]曾黄麟.粗集理论及其应用[M].重庆:重庆大学出版社, 1996.
[12]刘清，黄兆华，姚力文.粗糙集理论：现状与前景[J].计算机科学, 1997, 24(4):1-5.
[13]苗夺谦，王珏. Analysis on Attribute Reduction Strategies of Rough Set[J]. Journal ofComputer Science and Technology, 1998, 13(2):189-194.
[14]苗夺谦，王珏.粗糙集理论中知识粗糙性与信息熵关系的讨论[J].模式识别与人工智能, 1998, 11(1):30-40.
[15]苗夺谦，王珏.粗糙集理论中概念与运算的信息表示[J].软件学报, 1999,10(2):113-116.
[16]常梨云，王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报, 1999, 10(11):1206-1211.
[17]王国胤. Rough集理论在不完备信息系统中的扩充[J].计算机研究与发展, 2002,39(10):1238-1243.
[18]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报, 2002,25(7):759-766.
[19]王国胤.决策表核属性的计算方法[J].计算机学报, 2003, 26(5):611-615.
[20]赵军,王国胤,吴中福等.基于粗集理论的数据离散化方法[J].小型微型计算机系统, 2004, 25(1):59-64.
[21]王国胤. Rough集理论与适应获取[M].西安:西安交通大学出版社, 2001.
[22]颜艳,杨慧中.基于遗传算法的粗集属性约简算法[J].计算机工程与应用, 2007,43(31):156-158.
[23]袁晓峰,许化龙,陈淑红.基于量子遗传算法的粗集属性约简新算法[J].计算机工程, 2007, 33(15):184-186.
[24]姚跃华，洪杉.基于自适应蚁群算法的粗糙集属性约简[J].计算机工程, 2011,37(3):198-200.
[25] Hu Keyun, Lu Yuchang, Shi Chunyi. Feature Ranking in Rough Sets[J]. AICommunications, 2003, 16(1):41-50.
[26]杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报, 2007,30(5):815-822.
[27]杨明.一种基于一致性准则的属性约简算法[J].计算机学报, 2010, 30(5):231-239.
[28]胡清华,于达仁,谢宗霞.基于领域粒化和粗糙逼进的数值属性约简[J].软件学报,2007, 19(3):640-649.
[29]陈玉明,苗夺谦.基于幂图的属性约简搜索式算法[J].计算机学报, 2009,32(8):1486-1492.
[30]甄宇峰,施化吉.基于条件信息熵和相关系统的属性约简算法[J].计算机工程与应用, 2011, 47(16):26-28.
[31]吴静,邹海.基于属性重要性的属性约简新算法[J].计算机应用与软件, 2010,27(2):255-257.
[32] Wong S.K.M, Ziarko W. On optional decision rules in decision tables[J]. Bulletin ofPolish Academy of Sciences, 1985, 33(11/12):693-696.
[33] Stron R, Price K. Differential evolution-a simple and efficient adaptive scheme for globaloptimization over continuous spaces[R]. Technical Report TR-95-012. Berkeley:International Computer Science Institute, 1995.
[34] Stron R, Price K. Differential evolution-a simple and efficient heuristic for globaloptimization over contiuous spaces[J]. Journal of Global Optimization, 1997,11(4):341-359.
[35] Versterstrom J, Thomsen R. A comparative study of differential evolution,particle swarmoptimization,and evolutionary algorithm on numerical benchmark problem[C]//Evolutionary Computation,CEC2004. Portland OR:IEEE Press, 2004, 2:1980-1987.
[36] Slowik A. Application of an Adaptive Differential Evolution Algorithm With MultipleTrial Vectors to Artificial Neural Network Training [J]. Industrial Electronics, 2011,58(8):3160-3167.
[37] Neri F, Mininno E. Mimetic Compact Differential Evolution for Cartesian Robot Control[J]. Computational Intelligence Magazine. 2010, 5(2):54-65.
[38] Pandit M. Discussion of“Hybrid Differential Evolution With Biogeography-BasedOptimization for Solution of Economic Load Dispatch”[J]. Power Systems, 2012,27(1):574-575.
[39] Yikai Chen, Shiwen Yang, Zaiping Nie. The Application of a Modified DifferentialEvolution Strategy to some Array Pattern Synthesis Problems[J]. Antennas andPropagation. 2008, 56(7):1919-1927.
[40] Hannan M, Freeman J. Organizational ecology[M]. Cambridge, MA: Harvard UniversityPress, 1989.
[41] Qian Yan, Ren Hao, Research on the Competitive Relationship of Enterprises Based onNiche Theory[J]. Finance and Trade Research, 2006.(2):123-127.
[42] Yan Aimin. Study on Human Resource ecosystem [J]. Journal of Central SouthUniversity, 2006, 12(1):67-71.
[43] Zhu Chunquan. The Niche Ecostate-Ecorole Theory and Expansion Hypothesis[J]. ActsEcological Science, 1997, 17(3):324-332.
[44]苗夺谦,李道国.粗糙集理论、算法与应用[M].北京:清华大学出版社, 2008.
[45]杨启文,蔡亮,薛云灿.差分进化算法综述[J].模式识别与人工智能, 2008,21(4):506-513.
[46]李旭渊,许化龙.一种基于免疫小生境思想的粒子群优化算法[J].计算机工程与应用, 2008, 44(8):95-97.
[47] UCI repository of machine learning database[EO/OL]. http://www.cs.uci.edu/~mlearn/MLRepository.html.
[48]陶志,许国栋,汪定伟等.基于遗传算法的粗糙集知识约简方法[J].系统工程, 2003,21 (4):116-122.
[49]王杨.基于小生境遗传算法的粗糙集属性约简方法[J].计算机工程, 2008, 34(5):66-70.