×

zbMATH — the first resource for mathematics

Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems. (English) Zbl 1412.68200
Summary: This paper introduces an algorithm for solving the minimum sum-of-squares clustering problems using their difference of convex representations. A non-smooth non-convex optimization formulation of the clustering problem is used to design the algorithm. Characterizations of critical points, stationary points in the sense of generalized gradients and inf-stationary points of the clustering problem are given. The proposed algorithm is tested and compared with other clustering algorithms using large real world data sets.

MSC:
68T10 Pattern recognition, speech recognition
62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Al-Sultan, K. S., A tabu search approach to the clustering problem, Pattern Recognit., 28, 9, 1443-1451 (1995)
[2] An, L. T.H.; Belghiti, M. T.; Tao, P. D., A new efficient algorithm based on DC programming and DCA for clustering, J. Global Optim., 37, 4, 593-608 (2007) · Zbl 1198.90327
[3] An, L. T.H.; Minh, L. H.; Tao, P. D., New and efficient DCA based algorithms for minimum sum-of-squares clustering, Pattern Recognit., 47, 388-401 (2014) · Zbl 1326.68225
[4] An, L. T.H.; Ngai, H. V.; Tao, P. D., Exact penalty and error bounds in DC programming, J. Global Optim., 52, 3, 509-535 (2012) · Zbl 1242.49037
[5] An, L. T.H.; Tao, P. D., Minimum sum-of-squares clustering by DC programming and DCA, (Huang, D.-S.; Jo, K.-H.; Lee, H.-H.; Kang, H.-J.; Bevilacqua, V., Emerging Intelligent Computing Technology and Applications. With Aspects of Artificial Intelligence, ICIC 2009, LNAI, vol. 5755 (2009), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 327-340
[6] Bagirov, A. M., Modified global k-means algorithm for minimum sum-of-squares clustering problems, Pattern Recognit., 41, 10, 3192-3199 (2008) · Zbl 1147.68669
[7] Bagirov, A. M.; Karmitsa, N.; Mäkelä, M., Introduction to Nonsmooth Optimization: Theory, Practice and Software (2014), Springer: Springer Cham, Heidelberg · Zbl 1312.90053
[8] Bagirov, A. M.; Mohebi, E., Nonsmooth optimization based algorithms in cluster analysis, (Celebi, Emre M., Partitional Clustering Algorithms (2015), Springer), 99-146
[9] Bagirov, A. M.; Ordin, B.; Ozturk, G.; Xavier, A. E., An incremental clustering algorithm based on hyperbolic smoothing, Comput. Optim. Appl., 61, 219-241 (2015) · Zbl 1309.90098
[10] Bagirov, A. M.; Rubinov, A. M.; Soukhoroukova, N. V.; Yearwood, J., Unsupervised and supervised data classification via nonsmooth and global optimization, Top, 11, 1-93 (2003) · Zbl 1048.65059
[11] Bagirov, A. M.; Ugon, J., An algorithm for minimizing clustering functions, Optimization, 54, 4-5, 351-368 (2005) · Zbl 1122.90059
[12] Bagirov, A. M.; Ugon, J.; Webb, D., Fast modified global k-means algorithm for incremental cluster construction, Pattern Recognit., 44, April (4), 866-876 (2011) · Zbl 1213.68514
[13] Bagirov, A. M.; Yearwood, J., A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, Eur. J. Oper. Res., 170, 2, 578-596 (2006) · Zbl 1085.90045
[14] Bai, L.; Liang, J.; Sui, C.; Dang, Ch., Fast global k-means clustering based on local geometrical information, Inf. Sci., 245, 168-180 (2013) · Zbl 1321.62066
[15] Clarke, F. H., Optimization and nonsmooth analysis, canadian mathematical society series of monographs and advanced texts (1983), Wiley: Wiley New York
[16] Demyanov, V. F.; Bagirov, A. M.; Rubinov, A. M., A method of truncated codifferential with application to some problems of cluster analysis, J. Global Optim., 23, 1, 63-80 (2002) · Zbl 1034.49009
[17] Demyanov, V. F.; Rubinov, A. M., Constructive Nonsmooth Analysis (1995), Peter Lang, Frankfurt am Main · Zbl 0887.49014
[18] Diehr, G., Evaluation of a branch and bound algorithm for clustering, SIAM J. Sci. Stat. Comput., 6), 268-284 (1985) · Zbl 0561.65097
[19] du Merle, O.; Hansen, P.; Jaumard, B.; Mladenovic, N., An interior point algorithm for minimum sum-of-squares clustering, SIAM J. Sci. Comput., 21, 4, 1485-1505 (1999) · Zbl 1049.90129
[20] Hansen, P.; Mladenovic, N., Variable neighborhood decomposition search, J. Heuristic, 7, 335-350 (2001) · Zbl 1041.68623
[21] Horst, R.; Thoai, N. V., DC programmingoverview, J. Optim. Theory Appl., 103, 1, 1-43 (1999) · Zbl 1073.90537
[22] Jain, A. K.; Murty, M. N.; Flynn, P. J., Data clusteringa review, ACM Comput. Surv., 31, 3, 264-323 (1999)
[23] Jain, A. K., Data clustering50 years beyond \(k\)-means, Pattern Recognit. Lett., 31, 8, 651-666 (2010)
[24] Kogan, J., Introduction to Clustering Large and High-dimensional Data (2007), Cambridge University Press: Cambridge University Press Cambridge, New York · Zbl 1183.62106
[25] Lai, J. Z.C.; Huang, T.-J., Fast global k-means clustering using cluster membership and inequality, Pattern Recognit., 43, 5, 1954-1963 (2010) · Zbl 1185.68600
[27] Likas, A.; Vlassis, N.; Verbeek, J., The global k-means clustering algorithm, Pattern Recognit., 36, 2, 451-461 (2003)
[28] Ordin, B.; Bagirov, A. M., A heuristic algorithm for solving the minimum sum-of-squares clustering problems, J. Global Optim., 61, 341-361 (2015) · Zbl 1311.90111
[29] Rahman, MdA.; Islam, MdZ., A hybrid clustering technique combining a novel genetic algorithm with k-means, Knowl.-Based Syst., 71, 345-365 (2014)
[30] Scitovski, R.; Scitovski, S., A fast partitioning algorithm and its application to earthquake investigation, Comput. Geosci., 59, 124-131 (2013)
[31] Selim, S. Z.; Al-Sultan, K. S., A simulated annealing algorithm for the clustering, Pattern Recognit., 24, 10, 1003-1008 (1991)
[32] Tao, P. D.; An, L. T.H., Convex analysis approach to DC programmingtheory, algorithms and applications, Acta Math. Vietnam., 22, 1, 289-355 (1997)
[33] Teboulle, M., A unified continuous optimization framework for center-based clustering methods, J. Mach. Learn. Res., 8), 65-102 (2007) · Zbl 1222.68318
[35] Wolfe, P. H., Finding the nearest point in a polytope, Math. Progr., 11, 2, 128-149 (1976) · Zbl 0352.90046
[36] Xavier, A. E., The hyperbolic smoothing clustering method, Pattern Recognit., 43, 731-737 (2010) · Zbl 1187.68514
[37] Xavier, A. E.; Xavier, V. L., Solving the minimum sum-of-squares clustering problem by hyperbolic smoothing and partition into boundary and gravitational regions, Pattern Recognit., 44, 1, 70-77 (2011) · Zbl 1207.68326
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.