全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

信息熵最小约简问题的若干随机优化算法

, PP. 96-104

Keywords: 随机优化算法,粗糙集,信息熵,最小属性约简,全息粒子群

Full-Text   Cite this paper   Add to My Lib

Abstract:

现有的启发式属性约简算法一般无法得到信息熵意义下的最小属性约简。为此,文中探讨应用随机优化算法计算信息熵意义下最小属性约简的问题。首先通过定义适当的适应值函数,将信息熵意义下的最小属性约简问题转化为不含约束的适应值优化问题,证明问题转化的等价性。研究基于遗传算法、粒子群优化算法、禁忌搜索以及蚁群算法等若干随机优化算法的求解效率和求解质量,并用一批UCI数据集来加以测试。实验结果表明,文中设计的带增强策略的基于全息粒子群的属性约简算法,具有较高的获得信息熵意义下最小属性约简的概率和较优的算法性能。关键词随机优化算法,粗糙集,信息熵,最小属性约简,全息粒子群中图法分类号TP181ResearchonComputingMinimumEntropyBasedAttributeReductionviaStochasticOptimizationAlgorithmsMASheng-Lan,YEDong-Yi(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350108)ABSTRACTExistingheuristicattributereductionalgorithmsgenerallyfailtogetaminimumentropy-basedattributereductionofadecisiontable。Somestochasticoptimizationalgorithmsarediscussedtosolvetheproblemofentropy-basedattributereduction。Firstly,aproperfitnessfunctionisdefinedtotransformtheminimumattributereductionproblemintoafitnessoptimizationproblemwithoutadditionalconstraintsandtheequivalenceoftransformationisproved。Then,thesolvingefficiencyandthesolutionqualityofsomestochasticoptimizationalgorithmsarestudiedsuchasGeneticAlgorithm,ParticleSwarmOptimization,TabusearchandAntColonyOptimization。SomeUCIdatasetsareappliedtotestthoseperformances。TheexperimentalresultsshowthatthefullyinformedPSObasedattributereductionalgorithmwithrefineschemehasahigherprobabilitytofindaminimumentropy-basedattributereductionandgoodperformance。

References

[1]  Swiniarski R W,Skowron A. Rough Set Methods in Feature Selection and Recognition.Pattern Recognition Letters,2003,24(6): 833-849
[2]  Chouchoulas A,Shen Q.Rough Set-Aided Keyword Reduction for Text Categorization.Applied Artificial Intelligence,2001,15(9): 843-873
[3]  Skowron A,Rauszer C.The Discernibility Matrices and Functions in Information Systems // Huang Shiyu,ed.Intelligent Decision Support: Handbook of Application and Advances of the Rough Sets Theory.New York,USA: Springer,1992: 331-362
[4]  Hu Xiaohua.Knowledge Discovery in Databases: An Attribute-Oriented Rough Set Approach.Ph.D Dissertation.Saskatchewan,Canada: University of Regina,1995
[5]  Wong S K M,Ziarko W.On Optimal Decision Rules in Decision Tables.Bulletin of the Polish Academy of Sciences,1985,33(11/12): 693-696
[6]  Wroblewski J.Finding Minimal Reducts Using Genetic Algorithms // Proc of the 2nd Annual Join Conference on Information Sciences.Warsaw,Poland,1995: 186-189.
[7]  Jensen R,Shen Qiang.Finding Rough Set Reducts with Ant Colony Optimization // Proc of the UK Workshop on Computational Intelligence.Bristol,UK,2003: 15-22
[8]  Hedar A R,Wang Jue,Fukushima M.Tabu Search for Attribute Reduction in Rough Set Theory.Soft Computing: A Fusion of Foundations,Methodologies and Applications,2008,12(9): 909–918
[9]  Ye Dongyi,Liao JianKun.Minimum Attribute Reduction Algorithm Based on Binary Particle Swarm Optimization.Pattern Recognition and Artificial Intelligence,2007,20(3): 295-300 (in Chinese)(叶东毅,廖建坤.基于二进制粒子群优化的最小属性约简算法.模式识别与人工智能,2007,20(3): 295-300)
[10]  Ye Dongyi,Chen Zhaojiong,Liao Jiankun.A New Algorithm for Minimum Attribute Reduction Based on Binary Particle Swarm Optimization with Vaccination // Proc of the 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining.Nanjing,China,2007: 1029-1036
[11]  Wang Guoyin,Yu Hong,Yang Dachun.Decision Table Reduction Based on Conditional Information Entropy.Chinese Journal of Computers,2002,25(7): 759-766 (in Chinese)(王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报,2002,25(7): 759-766)
[12]  Wang Guoyin.Rough Set Theory and Knowledge Acquisition.Xian,China: Xian Jiaotong University Press,2001 (in Chinese)(王国胤.Rough集理论与知识获取.西安:西安交通大学出版社,2001)
[13]  Zhang Wenxiu,Liang Yi,Wu Weizhi.Information System and Knowledge Discovery.Beijing,China: Science Press,2003 (in Chinese)(张文修,梁 怡,吴伟志.信息系统与知识发现.北京:科学出版社,2003)
[14]  Liang Yanchun.Swarm Intelligence Optimization Algorithms Theory and Applications.Beijing,China: Science Press,2009 (in Chinese)(梁艳春.群智能优化算法理论与应用.北京:科学出版社,2009)
[15]  Spall J C.Introduction to Stochastic Search and Optimization.London,UK: John Wiley Sons,2003.
[16]  Kennedy J,Eberhart R C.Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks.Perth,Australia,1995: 1942-1948
[17]  Kennedy J,Eberhart R C.A Discrete Binary Version of the Particle Swarm Algorithm // Proc of the IEEE International Conference on Systems,Man and Cybernetics.Piscataway,USA,1997: 4104-4109
[18]  Holland J H.Adaptation in Natural and Artificial Systems.London,UK: MIT Press,1992
[19]  Glover F.Tabu Search-Part I.ORSA Journal on Computing,1989,1(3): 190-206
[20]  Dorigo M,Maniezzo V,Colorni A.The Ant System: Optimization by a Colony of Cooperating Agents.IEEE Trans on Systems,Man and Cybernetics,1996,26(1): 29-41
[21]  Mendes R,Kennedy J,Neves J.The Fully Informed Particle Swarm: Simpler,Maybe Better.IEEE Trans on Evolutionary Computation,2005,1(1): 204-210
[22]  Deng Tingquan,Yang Chengdong.An Improved Ant Colony Optimization Applied to Attributes Reduction.Advances in Soft Computing,2009,54: 1-6
[23]  Montgomery D C,Runger G C.Applied Statistics and Probability for Engineers.3rd Edition.London,UK: John Wiley Sons,2003: 278-326

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133