Menu
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2019-19-3-508-515
AUTOMATIC HYPERPARAMETER OPTIMIZATION FOR CLUSTERING ALGORITHMS WITH REINFORCEMENT LEARNIN
Read the full article
';
For citation:
Abstract
Muravyov S.B., Efimova V.A., Shalamov V.V., Filchenkov A.A., Smetannikov I.B. Automatic hyperparameter optimization for clustering algorithms with reinforcement learning. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2019, vol. 19, no. 3, pp. 508–515 (in Russian). doi: 10.17586/2226-1494-2019-19-3-508-515
Abstract
Subject of Research. The paper deals with research of clustering algorithms for hyperparameters optimization used in machine learning. Model selection problem is comprehensively studied, and the need of the tradeoff between exploration and exploitation is identified. Thus, the problem is reduced to multi-armed bandit problem. Method. The paper presented the approach for simultaneous algorithm selection and hyperparameters optimization. We used solution of the Multiarmed Bandit problem and considered Softmax- and UCB1-based algorithm variants in combination with different reward functions. Main Results. Experiments on various datasets from UCI repository were carried out. The results of experiments confirmed that proposed algorithms in general achieve significantly better results than exhaustive search method. It also helped to determine the most promising version of the algorithm we propose. Practical Relevance. The suggested algorithm can be successfully used for model selection and configuration for clustering algorithms, and can be applied in a wide range of clustering tasks in various areas, including biology, psychology, and image analysis.
Keywords: machine learning, clustering, algorithm selection, hyperparameter optimization, multi-armed bandit, reinforcement learning
Acknowledgements. This work was financially supported by the Government of Russian Federation, grant 08-08 and the Russian Foundation for Basic Research, Grant 16-37-60115 mol_a_dk.
References
Acknowledgements. This work was financially supported by the Government of Russian Federation, grant 08-08 and the Russian Foundation for Basic Research, Grant 16-37-60115 mol_a_dk.
References
1. Halkidi M., Batistakis Y., Vazirgiannis M. On clustering validation techniques. Journal of Intelligent Information Systems, 2001, vol. 17, no. 2–3, pp. 107–145. doi: 10.1023/a:1012801612483
2. Jain A.K., Murty M.N., Flynn P.J. Data clustering: a review. ACM Computing Surveys, 1999, vol. 31, no. 3, pp. 264–323. doi: 10.1145/331499.331504
3. Mirkin B. Clustering for Data Mining: a Data Recovery Approach. CRC Press, 2005, 296 p. doi: 10.1201/9781420034912
4. Schlee D., Sneath P.H., Sokal R.R., Freman W.H. Numerical taxonomy. The principles and practice of numerical classification. Systematic Zoology, 1975, vol. 24, no. 2, pp. 263–268. doi: 10.2307/2412767
5. Holzinger K.J.,Harman H.H. Facto rAnalysis:A Synthesis o fFactorial Methods. Chicago, University of Chicago Press, 1941, 417 p.
6. Chou C.H., Su M.C., Lai E. A new cluster validity measure and its application to image compression. Pattern Analysis and Applications, 2004, vol. 7, no. 2, pp. 205–220. doi: 10.1007/s10044-004-0218-1
7. Luo M., Wang L.N., Zhang H.G. An unsupervised clustering- based intrusion detection method. Acta Electronica Sinica, 2003, vol. 31, no. 11, pp. 1713–1716.
8. Von Luxburg U., Williamson R.C., Guyon I. Clustering: science or art. Proc. ICML Workshop on Unsupervised and Transfer Learning. Bellevue, USA, 2012, vol. 27, pp. 65–79.
9. Aggarwal C.C., Reddy C.K. Data Clustering: Algorithms and Applications. CRC press, 2013, 674 p. doi: 10.1201/b15410
10. Fraley C., Raftery A.E. How many clusters? Which clustering method? Answers via model-based cluster analysis. The Computer Journal, 1998, vol. 41, no. 8, pp. 578–588. doi: 10.1093/comjnl/41.8.578
11. Hennig C. What are the true clusters? Pattern Recognition Letters, 2015, vol. 64, pp. 53–62. doi: 10.1016/j.patrec.2015.04.009
12. Pal N.R., Biswas J. Cluster validation using graph theoretic concepts. Pattern Recognition, 1997, vol. 30, no. 6, pp. 847–857. doi: 10.1016/s0031-3203(96)00127-6
13. Ferrari D.G., De Castro L.N. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods. Information Sciences, 2015, vol. 301, pp. 181–194. doi: 10.1016/j.ins.2014.12.044
14. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2001, vol. 63, no. 2, pp. 411–423. doi: 10.1111/1467-9868.00293
15. Sugar C.A., James G.M. Finding the number of clusters in a dataset. Journal of the American Statistical Association, 2003, vol. 98, no. 463, pp. 750–763. doi: 10.1198/016214503000000666
16. Pelleg D., Moore A.W. X-means: Extending k-means with efficient estimation of the number of clusters. Proc. 17th Int. Conf. on Machine Learning. Stanford, USA, 2000, part 1, pp. 727– 734.
17. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. Proc. 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Chicago, USA, 2012, pp. 847–855. doi: 10.1145/2487575.2487629
18. Olson R.S., Bartley N., Urbanowicz R.J., Moore J.H. Evaluation of a tree-based pipeline optimization tool for automating data science. Proc. Genetic and Evolutionary Computation Conference. Denver, USA, 2016, pp. 485–492. doi: 10.1145/2908812.2908918
19. Feurer M., Klein A., Eggensperger K., Springenberg J., Blum M., Hutter F. Efficient and robust automated machine learning. Advances in Neural Information Processing Systems, 2015, vol. 2, pp. 2962–2970.
20. Efimova V.A., Filchenkov A.A., Shalyto A.A. Reinforcement- based simultaneous classification model and its hyperparameters selection. Machine Learning and Data Analysis, 2016, no. 2, pp. 244–254. (in Russian)
21. Kotthoff L., Thornton C., Hoos H.H., Hutter F., Leyton-Brown K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA. The Journal of Machine Learning Research, 2017, vol. 18, no. 1, pp. 826–830.
22. Sutton R.S., Barto A.G. Introduction to Reinforcement Learning. Cambridge, MIT press, 1998, 322 p.
23. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model- based optimization for general algorithm configuration. Lecture Notes in Computer Science, 2011, vol. 6683, pp. 507–523. doi: 10.1007/978-3-642-25566-3_40
24. Arbelaitz O., Gurrutxaga I., Muguerza J., Perez J. M., Perona I. An extensive comparative study of cluster validity indices. Pattern Recognition, 2003, vol. 46, no. 1, pp. 243–256. doi: 10.1016/j.patcog.2012.07.021
25. Filchenkov A., Muravyov S., Parfenov V. Towards cluster validity index evaluation and selection. Proc. IEEE Artificial Intelligence and Natural Language Conference. St. Petersburg, Russia, 2016, pp. 1–8.
2. Jain A.K., Murty M.N., Flynn P.J. Data clustering: a review. ACM Computing Surveys, 1999, vol. 31, no. 3, pp. 264–323. doi: 10.1145/331499.331504
3. Mirkin B. Clustering for Data Mining: a Data Recovery Approach. CRC Press, 2005, 296 p. doi: 10.1201/9781420034912
4. Schlee D., Sneath P.H., Sokal R.R., Freman W.H. Numerical taxonomy. The principles and practice of numerical classification. Systematic Zoology, 1975, vol. 24, no. 2, pp. 263–268. doi: 10.2307/2412767
5. Holzinger K.J.,Harman H.H. Facto rAnalysis:A Synthesis o fFactorial Methods. Chicago, University of Chicago Press, 1941, 417 p.
6. Chou C.H., Su M.C., Lai E. A new cluster validity measure and its application to image compression. Pattern Analysis and Applications, 2004, vol. 7, no. 2, pp. 205–220. doi: 10.1007/s10044-004-0218-1
7. Luo M., Wang L.N., Zhang H.G. An unsupervised clustering- based intrusion detection method. Acta Electronica Sinica, 2003, vol. 31, no. 11, pp. 1713–1716.
8. Von Luxburg U., Williamson R.C., Guyon I. Clustering: science or art. Proc. ICML Workshop on Unsupervised and Transfer Learning. Bellevue, USA, 2012, vol. 27, pp. 65–79.
9. Aggarwal C.C., Reddy C.K. Data Clustering: Algorithms and Applications. CRC press, 2013, 674 p. doi: 10.1201/b15410
10. Fraley C., Raftery A.E. How many clusters? Which clustering method? Answers via model-based cluster analysis. The Computer Journal, 1998, vol. 41, no. 8, pp. 578–588. doi: 10.1093/comjnl/41.8.578
11. Hennig C. What are the true clusters? Pattern Recognition Letters, 2015, vol. 64, pp. 53–62. doi: 10.1016/j.patrec.2015.04.009
12. Pal N.R., Biswas J. Cluster validation using graph theoretic concepts. Pattern Recognition, 1997, vol. 30, no. 6, pp. 847–857. doi: 10.1016/s0031-3203(96)00127-6
13. Ferrari D.G., De Castro L.N. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods. Information Sciences, 2015, vol. 301, pp. 181–194. doi: 10.1016/j.ins.2014.12.044
14. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2001, vol. 63, no. 2, pp. 411–423. doi: 10.1111/1467-9868.00293
15. Sugar C.A., James G.M. Finding the number of clusters in a dataset. Journal of the American Statistical Association, 2003, vol. 98, no. 463, pp. 750–763. doi: 10.1198/016214503000000666
16. Pelleg D., Moore A.W. X-means: Extending k-means with efficient estimation of the number of clusters. Proc. 17th Int. Conf. on Machine Learning. Stanford, USA, 2000, part 1, pp. 727– 734.
17. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. Proc. 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining. Chicago, USA, 2012, pp. 847–855. doi: 10.1145/2487575.2487629
18. Olson R.S., Bartley N., Urbanowicz R.J., Moore J.H. Evaluation of a tree-based pipeline optimization tool for automating data science. Proc. Genetic and Evolutionary Computation Conference. Denver, USA, 2016, pp. 485–492. doi: 10.1145/2908812.2908918
19. Feurer M., Klein A., Eggensperger K., Springenberg J., Blum M., Hutter F. Efficient and robust automated machine learning. Advances in Neural Information Processing Systems, 2015, vol. 2, pp. 2962–2970.
20. Efimova V.A., Filchenkov A.A., Shalyto A.A. Reinforcement- based simultaneous classification model and its hyperparameters selection. Machine Learning and Data Analysis, 2016, no. 2, pp. 244–254. (in Russian)
21. Kotthoff L., Thornton C., Hoos H.H., Hutter F., Leyton-Brown K. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA. The Journal of Machine Learning Research, 2017, vol. 18, no. 1, pp. 826–830.
22. Sutton R.S., Barto A.G. Introduction to Reinforcement Learning. Cambridge, MIT press, 1998, 322 p.
23. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model- based optimization for general algorithm configuration. Lecture Notes in Computer Science, 2011, vol. 6683, pp. 507–523. doi: 10.1007/978-3-642-25566-3_40
24. Arbelaitz O., Gurrutxaga I., Muguerza J., Perez J. M., Perona I. An extensive comparative study of cluster validity indices. Pattern Recognition, 2003, vol. 46, no. 1, pp. 243–256. doi: 10.1016/j.patcog.2012.07.021
25. Filchenkov A., Muravyov S., Parfenov V. Towards cluster validity index evaluation and selection. Proc. IEEE Artificial Intelligence and Natural Language Conference. St. Petersburg, Russia, 2016, pp. 1–8.
