多元宇宙优化算法应用于聚类分析（英文）
|
摘要
【目的】聚类是数据分析和数据挖掘技术中最重要的概念,其中,k-均值聚类算法是最常用的方法之一。然而,k-均值聚类算法高度依赖于初值,容易陷入局部最优解。为了克服k-均值聚类算法存在的不足,【方法】本研究提出一种利用多元宇宙算法(MVO)解决聚类分析问题的新算法,并进行一些数据集测试实验。【结果】数值模拟实验表明多元宇宙算法解决聚类问题效果优于人工蜂群(ABC)算法,布谷鸟搜索(CS)算法、粒子群优化(PSO)算法等。【结论】在大多数测试数据集的情况下多元宇宙算法解决聚类分析问题具有收敛速度快、聚类精度高和稳定性好的优点。
【Objective】Clustering is a popular data analysis and data mining technique.The k-means clustering algorithm is one of the most commonly used methods.However the k-means clustering algorithm is highly dependent on the initial solution and it is easy to fall into local optimal solutions.【Methods】For overcoming these disadvantages of the k-means method,this paper proposed Multi-verse Optimization Algorithm for the cluster analysis and experiment on synthetic and real life data sets.The numerical simulation experiments and comparisons were carried out based on a set of test data.The MVO algorithm was compared with Artificial Bee Colony(ABC)algorithm,Cuckoo Search(CS),Particle Swarm Optimization(PSO).【Results】From the experimental result,we could discover that MVO performed the best in most data set cases.We could easily find that the convergence speed of MVO was faster than other algorithms mentioned in this paper in most cases.Another fact could be found that the stability of MVO could reach a relatively high level as well.【Conclusion】Both numerical experiment results and the graphical experiment results show that Multi-verse Optimization Algorithm is more competitive than other algorithms for solving the clustering problem.
【Objective】Clustering is a popular data analysis and data mining technique.The k-means clustering algorithm is one of the most commonly used methods.However the k-means clustering algorithm is highly dependent on the initial solution and it is easy to fall into local optimal solutions.【Methods】For overcoming these disadvantages of the k-means method,this paper proposed Multi-verse Optimization Algorithm for the cluster analysis and experiment on synthetic and real life data sets.The numerical simulation experiments and comparisons were carried out based on a set of test data.The MVO algorithm was compared with Artificial Bee Colony(ABC)algorithm,Cuckoo Search(CS),Particle Swarm Optimization(PSO).【Results】From the experimental result,we could discover that MVO performed the best in most data set cases.We could easily find that the convergence speed of MVO was faster than other algorithms mentioned in this paper in most cases.Another fact could be found that the stability of MVO could reach a relatively high level as well.【Conclusion】Both numerical experiment results and the graphical experiment results show that Multi-verse Optimization Algorithm is more competitive than other algorithms for solving the clustering problem.
引文
[1]SPIELMAN S E,THILL J C.Social area analysis,data mining,and GIS[J].Computers Environment and Urban Systems,2008,32(2):110-122.
[2]RAO M R.Cluster analysis and mathematical programming[J].Journal of the American Statistical Association,1971,66(335):622-626.
[3]HENDRICKS D,GEBBIE T,WILCOX D.High-speed detection of emergent market clustering via an unsupervised parallel genetic algorithm[J].South African Journal of Science,2016,112(2):57-65.
[4]TSAI C F,WU H C,TSAI C W.A new data clustering approach for data mining in large databases[C]//Proceedings of International Symposium on Parallel Architectures,Algorithms and Networks.Metro Manila:IEEE,2002.
[5]BLATT M,WISEMAN S,DOMANY E.Superparamagnetic clustering of data[J].Physical Review Letters,1996,76(18):3251-3254.
[6]FRIGUI H,KRISHNAPURAM R.A robust competitive clustering algorithm with applications in computer vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(5):450-465.
[7]ZAMANI K,MADADGAR S,BATENI S.Estimating soil thermal properties from land surface temperature measurements using ant colony optimization approach[C]//IEEE International Conference on Acoustics,Speech,and Signal Processing.Toronto,Ont,Canada:IEEE,1991:873-876.
[8]SHELOKAR P S,JAYARAMAN V K,KULKARNI BD.Ant algorithm for single and multiobjective reliability optimization problems[J].Quality and Reliability Engineering International,2002,18(6):497-514.
[9]KENNEDY J,EBERHART R C.The particle swarm:Social adaptation in information-processing systems[M]//CORNE D,DORIGO M,GLOVER F(eds.).New Ideas in Optimization.Maidenhead,UK:McGrawHill Ltd,1999:379-388.
[10]MIRJALILI S,MIRJALILI S M,HATAMLOU A.Multi-verse optimizer:A nature-inspired algorithm for global optimization[J].Neural Computing and Applications,2016,27(2):495-513.
[11]MORRIS M S,THORNE K S.Wormholes in spacetime and their use for interstellar travel:A tool for teaching general relativity[J].American Journal of Physics,1988,56(5):395-412.
[12]GUTH A H.Eternal inflation and its implications[J].Journal of Physics A:Mathematical and Theoretical,2007,40(25):6811-6826.
[13]HAWKING S W.Black hole explosions?[J].Nature,1974,248(5443):30-31.
[14]HALLIDAY D,RESNICK R,WALKER J.Fundamentals of physics extended[M].8th edition.New York:Wiley,2008.
[15]SCHUTZ B.Book review:Gravity from the ground up[M].New York:Cambridge University Press,2004,18:22.
[16]ZHAO M R,TANG H L,GUO J,et al.A data clustering algorithm using cuckoo search[M]//HUNG J,YEN N,LI K C(eds.).Frontier Computing.Singapore:Springer,2016.
[17]BOUYER A.An optimized k-harmonic means algorithm combined with modified particle swarm optimization and cuckoo search algorithm[J].Foundations of Computing and Decision Sciences,2016,41(2):99-121.DOI:10.1515/fcds-2016-0006.
[18]SENTHILNATH J,DAS V,OMKAR S N,et al.Clustering using levy flight cuckoo search[C]//Proceedings of Seventh International Conference on Bio-Inspired Computing:Theories and Applications.India:Springer,2013,202:65-75.
[19]ELKERAN A.A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J].European Journal of Operational Research,2013,231(3):757-769.
[20]BENAMEUR L,ALAMI J,IMRANI A H E.A new hybrid particle swarm optimization algorithm for handling multiobjective problem using fuzzy clustering technique[C]//Proceedings of the 2009International Conference on Computational Intelligence,Modelling and Simulation.Washington DC,USA:IEEE Computer Society,2009:48-53.
[21]SHI Y L,NAN J Z.Fuzzy c-means and fuzzy adaptive particle swarm optimization for clustering problem[J].Journal of Computational and Theoretical Nanoscience,2016,13(1):270-273.
[22]SUN L L,CHEN H N.Artificial bee colony algorithm based on clustering method and its application for optimal power flow problem[M]//GONG M,PAN L,SONG T,et al(eds.).Bio-inspired Computing-Theories and Applications.Singapore:Springer,2016.
[23]KARABOGA D,OKDEM S,OZTURK C.Cluster based wireless sensor network routing using artificial bee colony algorithm[J].Wireless Networks,2012,18(7):847-860.
[24]ZHANG Y D,WU L N,WANG S H,et al.Chaotic artificial bee colony used for cluster analysis[M]//CHENR(ed.).Intelligent Computing and Information Science.Berlin Heidelberg:Springer,2011:205-211.
[2]RAO M R.Cluster analysis and mathematical programming[J].Journal of the American Statistical Association,1971,66(335):622-626.
[3]HENDRICKS D,GEBBIE T,WILCOX D.High-speed detection of emergent market clustering via an unsupervised parallel genetic algorithm[J].South African Journal of Science,2016,112(2):57-65.
[4]TSAI C F,WU H C,TSAI C W.A new data clustering approach for data mining in large databases[C]//Proceedings of International Symposium on Parallel Architectures,Algorithms and Networks.Metro Manila:IEEE,2002.
[5]BLATT M,WISEMAN S,DOMANY E.Superparamagnetic clustering of data[J].Physical Review Letters,1996,76(18):3251-3254.
[6]FRIGUI H,KRISHNAPURAM R.A robust competitive clustering algorithm with applications in computer vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(5):450-465.
[7]ZAMANI K,MADADGAR S,BATENI S.Estimating soil thermal properties from land surface temperature measurements using ant colony optimization approach[C]//IEEE International Conference on Acoustics,Speech,and Signal Processing.Toronto,Ont,Canada:IEEE,1991:873-876.
[8]SHELOKAR P S,JAYARAMAN V K,KULKARNI BD.Ant algorithm for single and multiobjective reliability optimization problems[J].Quality and Reliability Engineering International,2002,18(6):497-514.
[9]KENNEDY J,EBERHART R C.The particle swarm:Social adaptation in information-processing systems[M]//CORNE D,DORIGO M,GLOVER F(eds.).New Ideas in Optimization.Maidenhead,UK:McGrawHill Ltd,1999:379-388.
[10]MIRJALILI S,MIRJALILI S M,HATAMLOU A.Multi-verse optimizer:A nature-inspired algorithm for global optimization[J].Neural Computing and Applications,2016,27(2):495-513.
[11]MORRIS M S,THORNE K S.Wormholes in spacetime and their use for interstellar travel:A tool for teaching general relativity[J].American Journal of Physics,1988,56(5):395-412.
[12]GUTH A H.Eternal inflation and its implications[J].Journal of Physics A:Mathematical and Theoretical,2007,40(25):6811-6826.
[13]HAWKING S W.Black hole explosions?[J].Nature,1974,248(5443):30-31.
[14]HALLIDAY D,RESNICK R,WALKER J.Fundamentals of physics extended[M].8th edition.New York:Wiley,2008.
[15]SCHUTZ B.Book review:Gravity from the ground up[M].New York:Cambridge University Press,2004,18:22.
[16]ZHAO M R,TANG H L,GUO J,et al.A data clustering algorithm using cuckoo search[M]//HUNG J,YEN N,LI K C(eds.).Frontier Computing.Singapore:Springer,2016.
[17]BOUYER A.An optimized k-harmonic means algorithm combined with modified particle swarm optimization and cuckoo search algorithm[J].Foundations of Computing and Decision Sciences,2016,41(2):99-121.DOI:10.1515/fcds-2016-0006.
[18]SENTHILNATH J,DAS V,OMKAR S N,et al.Clustering using levy flight cuckoo search[C]//Proceedings of Seventh International Conference on Bio-Inspired Computing:Theories and Applications.India:Springer,2013,202:65-75.
[19]ELKERAN A.A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J].European Journal of Operational Research,2013,231(3):757-769.
[20]BENAMEUR L,ALAMI J,IMRANI A H E.A new hybrid particle swarm optimization algorithm for handling multiobjective problem using fuzzy clustering technique[C]//Proceedings of the 2009International Conference on Computational Intelligence,Modelling and Simulation.Washington DC,USA:IEEE Computer Society,2009:48-53.
[21]SHI Y L,NAN J Z.Fuzzy c-means and fuzzy adaptive particle swarm optimization for clustering problem[J].Journal of Computational and Theoretical Nanoscience,2016,13(1):270-273.
[22]SUN L L,CHEN H N.Artificial bee colony algorithm based on clustering method and its application for optimal power flow problem[M]//GONG M,PAN L,SONG T,et al(eds.).Bio-inspired Computing-Theories and Applications.Singapore:Springer,2016.
[23]KARABOGA D,OKDEM S,OZTURK C.Cluster based wireless sensor network routing using artificial bee colony algorithm[J].Wireless Networks,2012,18(7):847-860.
[24]ZHANG Y D,WU L N,WANG S H,et al.Chaotic artificial bee colony used for cluster analysis[M]//CHENR(ed.).Intelligent Computing and Information Science.Berlin Heidelberg:Springer,2011:205-211.