A new efficient algorithm based on DC programming and DCA for clustering

被引：0
作者：
Le Thi Hoai An
M. Tayeb Belghiti
Pham Dinh Tao
机构：
[1] University of Paul,Laboratory of Theoretical and Applied Computer Science, UFR MIM
[2] National Institute for Applied Sciences - Rouen,Laboratory of Modelling, Optimization and Operations Research
[3] National Institute for Applied Sciences - Rouen,Laboratory of Modelling, Optimization and Operations Research
来源：
Journal of Global Optimization | 2007年 / 37卷
关键词：
Clustering; K-median problem; K-means algorithm; DC programming; DCA; Nonsmooth nonconvex programming; 65K05; 65K10; 90C26; 90C90; 15A60; 90C06;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, a version of K-median problem, one of the most popular and best studied clustering measures, is discussed. The model using squared Euclidean distances terms to which the K-means algorithm has been successfully applied is considered. A fast and robust algorithm based on DC (Difference of Convex functions) programming and DC Algorithms (DCA) is investigated. Preliminary numerical solutions on real-world databases show the efficiency and the superiority of the appropriate DCA with respect to the standard K-means algorithm.
引用
收藏
页码：593 / 608
页数：15
相关论文
共 40 条
  • [1] Al-Sultan K.(1995)A Tabu search approach to the clustering problem Pattern Recogn. 28 443-1453
  • [2] De Leeuw J.(1988)Convergence of the majorization method for multidimensional scaling J. Classi. 5 163-180
  • [3] Fisher D.(1988)Knowledge acquisition via incremental conceptual clusterin Mach. Learning, 2 139-172
  • [4] LeThi Hoai An(1997)Solving a class of linearly constrained indefinite quadratic problems by DC algorithms J. Global Optim. 11 253-285
  • [5] Pham Dinh Tao(2003)Large Scale Molecular Optimization from distances matrices by a DC optimization approach SIAM J. Optim. 14 77-116
  • [6] LeThi Hoai An(2005)The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems Ann. Oper. Res. 133 23-46
  • [7] Pham Dinh Tao(1997)Mathematical programming in data mining Data Mining and Knowl. discov. 1 183-201
  • [8] LeThi Hoai An(2004)A k-Median algorithm with running time independent of data size Machine Learn. 56 61-87
  • [9] Pham Dinh Tao(1984)Convergence of subgradient method for computing the bound-norm of matrices. Linear Algebra Appl. 62 163-182
  • [10] Mangasarian O.L.(1984)Algorithmes de calcul d’une forme quadratique sur la boule unité de la norme du maximum Numer. Math. 45 377-440
1234