Optimization based DC programming and DCA for hierarchical clustering. (English) Zbl 1149.90117

A hierarchical clustering of a set of objects can be described as a tree, in which the leaves are precisely the objects to be clustered. In this work different mathematical programs have been proposed for the bilevel hierarchical clustering problem. The proposed approach is based on DC (Difference of Convex functions) programming “which deals with DC programs, i.e., the minimization of a DC function over a convex set” and DC optimization Algorithm called DCA. They are all nonconvex, nonsmooth optimization problems that can be reformulated as DC programs in a suitable matrix space for which the resulting DCA schemes are all explicit, and very inexpensive. Numerical results on some artificial and real-world databases demonstrate that the proposed algorithms are more efficient than some existing optimization based clustering algorithms.


90C26 Nonconvex programming, global optimization
Full Text: DOI


[1] Tayeb Belghiti, M.; Hoai An, Le Thi; Tao, Pham Dinh, Clustering via DC programming and DCA, (), 499-507 · Zbl 1237.90234
[2] Fisher, D., Iterative optimization and simplification of hierarchical clusterings, Journal of artificial intelligence research, 4, 147-180, (1996) · Zbl 0900.68173
[3] Gill Waters, Sei Guan Lim, Applying clustering algorithms to multicast group hierarchies, Technical Report No. 4-03, August 2003.
[4] Waters, Gill; Crawford, John; Lim, Sei Guan, Optimising multicast structures for grid computing, Computer communications, 27, 1389-1400, (2004)
[5] Jain, A.K.; Murty, M.N.; Flynn, P.J., Data clustering: A review, ACM computing surveys, 31, 3, 264-323, (1999)
[6] Neumann, Julia; Schnörr, Christoph; Steidl, Gabriele, SVM-based feature selection by direct objective minimisation, pattern recognition, () · Zbl 1137.90643
[7] Hiriart Urruty, J.B.; Lemarechal, C., Convex analysis and minimization algorithms I & II, (1993), Springer-Verlag
[8] Le Thi Hoai An, Contribution à l’optimisation non convexe et l’optimisation globale: Théorie, Algorithmes et Applications, Habilitation, July 1997, Université de Rouen.
[9] Hoai An, Le Thi; Tao, Pham Dinh, Solving a class of linearly constrained indefinite quadratic problems by DC algorithms, Journal of global optimization, 11, 3, 253-285, (1997) · Zbl 0905.90131
[10] Hoai An, Le Thi; Tao, Pham Dinh; Muu, Le Dung, Exact penalty in DC programming, Vietnam journal of mathematics, 27, 2, 169-178, (1999) · Zbl 1006.90062
[11] Le Thi Hoai An, Pham Dinh Tao, DC programming: Theory, algorithms and applications. The state of the art, in: Proceedings of the First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos’02), Valbonne-Sophia Antipolis, France, 2-4 October 2002, 28pp.
[12] Hoai An, Le Thi; Tao, Pham Dinh, Large scale molecular optimization from distances matrices by a DC optimization approach, SIAM journal of optimization, 14, 1, 77-116, (2003) · Zbl 1075.90071
[13] Hoai An, Le Thi; Tao, Pham Dinh, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of operations research, 133, 23-46, (2005) · Zbl 1116.90122
[14] Long Jia, A. Bagirov, I. Ouveysi, A.M. Rubinov, Optimization based clustering algorithms in Multicast group hierarchies, in: Proceedings of the Australian Telecommunications, Networks and Applications Conference (ATNAC), 2003, Melbourne Australia (published on CD, ISNB 0-646-42229-4).
[15] Murtagh, F., A survey of recent advances in hierarchical clustering algorithms, The computer journal, 26, 4, (1983) · Zbl 0523.68030
[16] Tao, Pham Dinh; Hoai An, Le Thi, Convex analysis approach to d.c. programming: theory, algorithms and applications, Acta Mathematica vietnamica, 22, 1, 289-355, (1997), (dedicated to Professor Hoang Tuy on the occasion of his 70th birthday) · Zbl 0895.90152
[17] Tao, Pham Dinh; Hoai An, Le Thi, DC optimization algorithms for solving the trust region subproblem, SIAM journal of optimization, 8, 476-505, (1998) · Zbl 0913.65054
[18] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton · Zbl 0229.90020
[19] Stefan Weber, Christoph Schnörr, Thomas Schüle, Joachim Hornegger, Discrete tomography by convex – concave regularization and DC programming, Technical Report 15/2003, Computer Science Series.
[20] Weber, Stefan; Schnörr, Christoph; Schüle, Thomas; Hornegger, Joachim, Binary tomography by iterating linear programs, () · Zbl 1113.68625
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.