DOI: 10.17586/2226-1494-2019-19-3-508-515


S. B. Muravyov, V. A. Efimova, V. V. Shalamov, A. A. Filchenkov, I. B. Smetannikov

Read the full article  ';
For citation:
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

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.

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.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2020 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.