×

A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems. (English) Zbl 1085.90045

Summary: The minimum sum-of-squares clustering problem is formulated as a problem of nonsmooth, nonconvex optimization, and an algorithm for solving the former problem based on nonsmooth optimization techniques is developed. The issue of applying this algorithm to large data sets is discussed. Results of numerical experiments have been presented which demonstrate the effectiveness of the proposed algorithm.

MSC:

90C26 Nonconvex programming, global optimization
62H30 Classification and discrimination; cluster analysis (statistical aspects)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Al-Sultan, K.S., A tabu search approach to the clustering problem, Pattern recognition, 28, 9, 1443-1451, (1995)
[2] Al-Sultan, K.S.; Khan, M.M., Computational experience on four algorithms for the hard clustering problem, Pattern recognition letters, 17, 295-308, (1996)
[3] Bagirov, A.M., Minimization methods for one class of nonsmooth functions and calculation of semi-equilibrium prices, (), 147-175 · Zbl 1016.90048
[4] Bagirov, A.M., A method for minimization of quasidifferentiable functions, Optimization methods and software, 17, 1, 31-60, (2002) · Zbl 1040.90038
[5] Bagirov, A.M.; Rubinov, A.M.; Yearwood, J., Using global optimization to improve classification for medical diagnosis and prognosis, Topics in health information management, 22, 65-74, (2001)
[6] Bagirov, A.M.; Rubinov, A.M.; Yearwood, J., Global optimization approach to classification, Optimization and engineering, 22, 65-74, (2001)
[7] Bock, H.H., Automatische klassifikation, (1974), Vandenhoeck & Ruprecht Göttingen · Zbl 0207.19202
[8] Bock, H.H., Clustering and neural networks, (), 265-277 · Zbl 1051.91523
[9] Brown, D.E.; Entail, C.L., A practical application of simulated annealing to the clustering problem, Pattern recognition, 25, 401-412, (1992)
[10] Clarke, F.H., Optimization and nonsmooth analysis, (1983), Wiley New York · Zbl 0727.90045
[11] Demyanov, V.F.; Rubinov, A.M., Constructive nonsmooth analysis, (1995), Peter Lang Frankfurt am Main · Zbl 0887.49014
[12] Dhillon, I.S.; Fan, J.; Guan, Y., Efficient clustering of very large document collections, ()
[13] Diehr, G., Evaluation of a branch and bound algorithm for clustering, SIAM J. scientific and statistical computing, 6, 268-284, (1985) · Zbl 0561.65097
[14] Dubes, R.; Jain, A.K., Clustering techniques: the user’s dilemma, Pattern recognition, 8, 247-260, (1976)
[15] du Merle, O.; Hansen, P.; Jaumard, B.; Mladenovic, N., An interior point method for minimum sum-of-squares clustering, SIAM journal on scientific computing, 21, 1485-1505, (2001) · Zbl 1049.90129
[16] Fisher, R.A., The use of multiple measurements in taxonomic problems, Annals of eugenics, VII part II, 179-188, (1936), (Reprinted in: R.A. Fisher (Ed.), Contributions to Mathematical Statistics, Wiley, 1950)
[17] Hanjoul, P.; Peeters, D., A comparison of two dual-based procedures for solving the p-Median problem, European journal of operational research, 20, 387-396, (1985) · Zbl 0565.90011
[18] Hansen, P.; Jaumard, B., Cluster analysis and mathematical programming, Mathematical programming, 79, 1-3, 191-215, (1997) · Zbl 0887.90182
[19] Hansen, P.; Mladenovic, N., J-means: A new heuristic for minimum sum-of-squares clustering, Pattern recognition, 4, 405-413, (2001) · Zbl 1012.68873
[20] Hansen, P.; Mladenovic, N., Variable neighborhood decomposition search, Journal of heuristic, 7, 335-350, (2001) · Zbl 1041.68623
[21] P. Hansen, E. Ngai, B.K. Cheung, N. Mladenovic, Analysis of global k-means, an incremental heuristic for minimum sum-of-squares clustering, Research Paper G-2002-43, GERAD, Montreal, Canada, 2002. · Zbl 1336.62182
[22] Hiriart-Urruty, J.-P.; Lemarechal, C., Convex analysis and minimization algorithms, vols. 1&2, (1993), Springer-Verlag Berlin
[23] Houkins, D.M.; Muller, M.W.; ten Krooden, J.A., Cluster analysis, () · Zbl 0466.62051
[24] Jain, A.K.; Murty, M.N.; Flynn, P.J., Data clustering: A review, ACM computing surveys, 31, 3, 264-323, (1999)
[25] Jensen, R.E., A dynamic programming algorithm for cluster analysis, Operations research, 17, 1034-1057, (1969) · Zbl 0183.49103
[26] Kiwiel, K.C., Methods of descent for nondifferentiable optimization, () · Zbl 0602.90122
[27] Koontz, W.L.G.; Narendra, P.M.; Fukunaga, K., A branch and bound clustering algorithm, IEEE transactions on computers, 24, 908-915, (1975) · Zbl 0308.68039
[28] Likas, A.; Vlassis, M.; Verbeek, J., The global k-means clustering algorithm, Pattern recognition, 36, 451-461, (2003)
[29] Mangasarian, O.L., Mathematical programming in data mining, Data mining and knowledge discovery, 1, 183-201, (1997)
[30] Mladenovic, N.; Hansen, P., Variable neighborhood search, Computer and operations research, 24, 1097-1100, (1997) · Zbl 0889.90119
[31] P.M. Murphy, D.W. Aha, UCI repository of machine learning databases, Technical report, Department of Information and Computer Science, University of California, Irvine, 1992. Available from: <http://www.ics.uci.edu/mlearn/MLRepository.html>.
[32] Nelder, J.A.; Mead, R., A simplex method for function minimization, Computer journal, 7, 308-313, (1965) · Zbl 0229.65053
[33] Powell, M.J.D., UOBYQA: unconstrained optimization by quadratic approximation, Mathematical programming, series B, 92, 3, 555-582, (2002) · Zbl 1014.65050
[34] ()
[35] Reinelt, G., TSP-LIB-A traveling salesman library, ORSA journal of computation, 3, 319-350, (1991)
[36] Selim, S.Z.; Ismail, M.A., k-means-type algorithm: generalized convergence theorem and characterization of local optimality, IEEE transactions on pattern analysis and machine intelligence, 6, 81-87, (1984) · Zbl 0546.62037
[37] Selim, S.Z.; Al-Sultan, K.S., A simulated annealing algorithm for the clustering, Pattern recognition, 24, 10, 1003-1008, (1991)
[38] Spath, H., Cluster analysis algorithms, (1980), Ellis Horwood Limited Chichester
[39] Sun, L.X.; Xie, Y.L.; Song, X.H.; Wang, J.H.; Yu, R.Q., Cluster analysis by simulated annealing, Computers and chemistry, 18, 103-108, (1994) · Zbl 0825.92149
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.