×

zbMATH — the first resource for mathematics

Application of the DIRECT algorithm to searching for an optimal \(k\)-partition of the set \(\mathcal {A}\subset \mathbb {R}^n\) and its application to the multiple circle detection problem. (English) Zbl 07069294
Summary: In this paper, we propose an efficient method for searching for a globally optimal \(k\)-partition of the set \(\mathcal {A}\subset \mathbb {R}^n\). Due to the property of the DIRECT global optimization algorithm to usually quickly arrive close to a point of global minimum, after which it slowly attains the desired accuracy, the proposed method uses the well-known \(k\)-means algorithm with a initial approximation chosen on the basis of only a few iterations of the DIRECT algorithm. In case of searching for an optimal \(k\)-partition of spherical clusters, the method is not worse than other known methods, but in case of solving the multiple circle detection problem, the proposed method shows remarkable superiority.

MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
90C27 Combinatorial optimization
90C56 Derivative-free methods and methods using generalized derivatives
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
05E05 Symmetric functions and generalizations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahn, SJ; Rauh, W.; Warnecke, HJ, Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola, Pattern Recognit., 34, 2283-2303, (2001) · Zbl 0991.68127
[2] Akinlar, C.; Topal, C., Edcircles: a real-time circle detector with a false detection control, Pattern Recognit., 46, 725-740, (2013)
[3] Bagirov, AM, Modified global \(k\)-means algorithm for minimum sum-of-squares clustering problems, Pattern Recognit., 41, 3192-3199, (2008) · Zbl 1147.68669
[4] Bagirov, AM; Ugon, J.; Webb, D., Fast modified global \(k\)-means algorithm for incremental cluster construction, Pattern Recognit., 44, 866-876, (2011) · Zbl 1213.68514
[5] Bezdek, J.C., Keller, J., Krisnapuram, R., Pal, N.R.: Fuzzy Models and Algorithms for Pattern Recognition and Image Processing. Springer, New York (2005) · Zbl 0998.68138
[6] Butenko, S., Chaovalitwongse, W.A., Pardalos, P.M. (eds.): Clustering Challenges in Biological Networks. World Scientific Publishing Co, Singapore (2009)
[7] Chernov, N.: Circular and Linear Regression: Fitting Circles and Lines by Least Squares. Monographs on Statistics and Applied Probability, vol. 117. Chapman & Hall, London (2010)
[8] Chung, KL; Huang, YH; Shen, SM; Yurin, ASKDV; Semeikina, EV, Efficient sampling strategy and refinement strategy for randomized circle detection, Pattern Recognit., 45, 252-263, (2012)
[9] Gablonsky, J.M.: DIRECT Version 2.0. Technical Report. Center for Research in Scientific Computation. North Carolina State University (2001)
[10] Grbić, R.; Grahovac, D.; Scitovski, R., A method for solving the multiple ellipses detection problem, Pattern Recognit., 60, 824-834, (2016)
[11] Grbić, R.; Nyarko, EK; Scitovski, R., A modification of the DIRECT method for Lipschitz global optimization for a symmetric function, J. Glob. Optim., 57, 1193-1212, (2013) · Zbl 1279.65076
[12] Horst, R., Tuy, H.: Global Optimization: Deterministic Approach, 3rd Revised and Enlarged Edition. Springer, Berlin (1996)
[13] Hüllermeier, E.; Rifqi, M.; Henzgen, S.; Senge, R., Comparing fuzzy partitions: a generalization of the Rand index and related measures, EEE Trans. Fuzzy Syst., 20, 546-556, (2012)
[14] Jones, DR; Floudas, CA (ed.); Pardalos, PM (ed.), The direct global optimization algorithm, 431-440, (2001), Dordrect
[15] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[16] Kogan, J.: Introduction to Clustering Large and High-dimensional Data. Cambridge University Press, New York (2007) · Zbl 1183.62106
[17] Kvasov, DE; Sergeyev, YD, Lipschitz gradients for global optimization in a one-point-based partitioning scheme, J. Comput. Appl. Math., 236, 4042-4054, (2012) · Zbl 1246.65091
[18] Leisch, F., A toolbox for k-centroids cluster analysis, Comput. Stat. Data Anal., 51, 526-544, (2006) · Zbl 1157.62439
[19] Likas, A.; Vlassis, N.; Verbeek, JJ, The global \(k\)-means clustering algorithm, Pattern Recognit., 36, 451-461, (2003)
[20] Locatelli, M., Schoen, F.: Global Optimization: Theory, Algorithms, and Applications. SIAM, Philadelphia (2013) · Zbl 1286.90003
[21] Morales-Esteban, A.; Martínez-Álvarez, F.; Scitovski, S.; Scitovski, R., A fast partitioning algorithm using adaptive Mahalanobis clustering with application to seismic zoning, Comput. Geosci., 73, 132-141, (2014)
[22] Nievergelt, Y., A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres, Numer. Math., 91, 257-303, (2002) · Zbl 0999.65008
[23] Paulavičius, R.; Sergeyev, Y.; Kvasov, D.; Žilinskas, J., Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59, 545-567, (2014) · Zbl 1297.90130
[24] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, Berlin (2014a) · Zbl 1401.90017
[25] Paulavičius, R.; Žilinskas, J., Simplicial Lipschitz optimization without Lipschitz constant, J. Glob. Optim., 59, 23-40, (2014) · Zbl 1300.90031
[26] Paulavičius, R.; Žilinskas, J., Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints, Optim. Lett., 10, 237-246, (2016) · Zbl 1342.90151
[27] Pelleg, D., Moore, A.W.: X-means: extending k-means with efficient estimation of the number of clusters, In: Proceedings of the Seventeenth International Conference on Machine Learning, ICML’00, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 727-734 (2000)
[28] Qiao, Y.; Ong, SH, Connectivity-based multiple-circle ftting, Pattern Recognit., 37, 755-765, (2004)
[29] Sabo, K.; Scitovski, R.; Vazler, I., One-dimensional center-based \(l_1\)-clustering method, Optim. Lett., 7, 5-22, (2013) · Zbl 1283.90034
[30] Scitovski, R., A new global optimization method for a symmetric Lipschitz continuous function and application to searching for a globally optimal partition of a one-dimensional set, J. Glob. Optim., 68, 713-727, (2017) · Zbl 1377.65067
[31] Scitovski, R.; Marošević, T., Multiple circle detection based on center-based clustering, Pattern Recognit. Lett., 52, 9-16, (2014)
[32] Scitovski, R.; Sabo, K., Analysis of the \(k\)-means algorithm in the case of data points occurring on the border of two or more clusters, Knowl. Based Syst., 57, 1-7, (2014)
[33] Scitovski, R.; Scitovski, S., A fast partitioning algorithm and its application to earthquake investigation, Comput. Geosci., 59, 124-131, (2013)
[34] Sergeyev, YD; Kvasov, DE, A deterministic global optimization using smooth diagonal auxiliary functions, Commun. Nonlinear Sci. Numer. Simul., 21, 99-111, (2015) · Zbl 1329.90112
[35] Späth, H.: Cluster-Formation und Analyse. R. Oldenburg Verlag, München (1983) · Zbl 0536.62048
[36] Thomas, JCR; Martin, CS (ed.); Kim, SW (ed.), A new clustering algorithm based on k-means using a line segment as prototype, 638-645, (2011), Berlin
[37] Tîrnăucă, C.; Gómez-Pérez, D.; Balcázar, JL; Montaña, JL, Global optimality in k-means clustering, Inf. Sci., 439, 79-94, (2018)
[38] Vidović, I.; Scitovski, R., Center-based clustering for line detection and application to crop rows detection, Comput. Electron. Agric., 109, 212-220, (2014)
[39] Weise, T.: Global Optimization Algorithms. Theory and Application. http://www.it-weise.de/projects/book.pdf (2008) · Zbl 1142.81304
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.