A randomized algorithm for two-cluster partition of a set of vectors

A. V. Kel'manov   ; V. I. Khandeev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 2, pp. 335-344

Résumé

A randomized algorithm is substantiated for the strongly NP-hard problem of partitioning a finite set of vectors of Euclidean space into two clusters of given sizes according to the minimum-of-the sum-of-squared-distances criterion. It is assumed that the centroid of one of the clusters is to be optimized and is determined as the mean value over all vectors in this cluster. The centroid of the other cluster is fixed at the origin. For an established parameter value, the algorithm finds an approximate solution of the problem in time that is linear in the space dimension and the input size of the problem for given values of the relative error and failure probability. The conditions are established under which the algorithm is asymptotically exact and runs in time that is linear in the space dimension and quadratic in the input size of the problem.

Bibliographie

[1] Anil K., Jain K., “Data clustering: 50 years beyond $k$-means”, Pattern Recognition Letters, 31 (2010), 651–666 | DOI

[2] MacQueen J. B., “Some methods for cassification and analysis of multivariate observations”, Proc. 5-th Berkeley Symp. of Mathematical Statistics and Probability, v. 1, Univ. of California Press, Berkeley, 281–297

[3] Rao M., “Cluster analysis and mathematical programming”, J. Amer. Statist. Assoc., 66 (1971), 622–626 | DOI

[4] Galashov A. E., Kelmanov A. V., “2-priblizhennyi algoritm dlya odnoi zadachi poiska semeistva neperesekayuschikhsya podmnozhestv vektorov”, Avtomatika i telemekhanika, 2014, no. 4, 5–17

[5] Dolgushev A. V., Kelmanov A. V., “K voprosu ob algoritmicheskoi slozhnosti odnoi zadachi klasternogo analiza”, Diskret. analiz i issled. operatsii, 17:2 (2010), 39–45

[6] Hansen P., Jaumard B., “Cluster analysis and mathematical programming”, Math. Programming, 79 (1997), 191–215

[7] Hansen P., Jaumard B., Mladenovich N., “Minimum sum of squares clustering in a low dimensional space”, J. Classification, 15 (1998), 37–55 | DOI

[8] Inaba M., Katch N., Imai H., “Applications of weighted Voronoi diagrams and randomization to variance-based clustering”, Proc. Annual Symp. on Comput. Geom., Stony Brook, New York, 1994, 332–339

[9] Aloise D., Deshpande A., Hansen P., Popat P., “NP-hardness of Euclidean sum-of-squares clustering”, Machine Learning, 75:2 (2009), 245–248 | DOI

[10] Ageev A. A., Kel'manov A. V., Pyatkin A. V., “NP-hardness of the Euclidean max-cut problem”, Doklady Mathematics, 89:3 (2014), 343–345 | DOI | DOI

[11] Dolgushev A. V., Kelmanov A. V., “Priblizhennyi algoritm resheniya odnoi zadachi klasternogo analiza”, Diskretnyi analiz i issledovanie operatsii, 18:2 (2011), 29–40

[12] Dolgushev A. V., Kelmanov A. V., Shenmaier V. V., “Priblizhennaya polinomialnaya skhema dlya odnoi zadachi klasternogo analiza”, Intellektualizatsiya obrabotki informatsii, 9-ya mezhdunarodnaya konferentsiya. Respublika Chernogoriya. Sb. dokl., Torus Press, M., 2012, 242–244

[13] Eremin I. I., Gimadi E. Kh., Kelmanov A. V., Pyatkin A. V., Khachai M. Yu., “2-priblizhennyi algoritm poiska kliki s minimalnym vesom vershin i reber”, Tr. In-ta matematiki i mekhaniki UrO RAN, 19, no. 2, 2013, 134–143

[14] Kelmanov A. V., “O slozhnosti nekotorykh zadach klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 51:11 (2011), 2106–2112

[15] Kelmanov A. V., “O slozhnosti nekotorykh zadach analiza dannykh”, Zh. vychisl. matem. i matem. fiz., 50:11 (2010), 2045–2051

[16] Kelmanov A. V., “Problema off-line obnaruzheniya povtoryayuschegosya fragmenta v chislovoi posledovatelnosti”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14, no. 2 (2008), 81–88

[17] Kelmanov A. V., Romanchenko S. M., Khamidullin S. A., “Tochnye psevdopolinomialnye algoritmy dlya nekotorykh trudnoreshaemykh zadach poiska podposledovatelnosti vektorov”, Zh. vychisl. matem. i matem. fiz., 53:1 (2013), 143–153 | DOI

[18] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach klasternogo analiza vektornykh posledovatelnostei”, Diskretnyi analiz i issledovanie operatsii, 20:2 (2013), 47–57

[19] Kelmanov A. V., Pyatkin A. V., “O slozhnosti nekotorykh zadach poiska podmnozhestv vektorov i klasternogo analiza”, Zh. vychisl. matem. i matem. fiz., 49:11 (2009), 2059–2065

[20] Kelmanov A. V., Pyatkin A. V., “O slozhnosti odnogo iz variantov zadachi vybora podmnozhestva “pokhozhikh” vektorov”, Dokl. AN, 421:5 (2008), 590–592

[21] Kelmanov A. V., Khandeev V. I., “Polinomialnyi algoritm s otsenkoi tochnosti 2 dlya resheniya odnoi zadachi klasternogo analiza”, Diskretnyi analiz i issledovanie operatsii, 20:4 (2013), 36–45

[22] Rajeev M., Prabhakar R., Randomized algorithms, Cambridge University Press, New York, 1995

[23] Markov A. A., Ischislenie veroyatnostei, Izd-vo Tipografiya Imperatorskoi Akademii Nauk, SPb, 1900