New and efficient DCA based algorithms for minimum sum-of-squares clustering
作者：
Highlights：
• The purpose of this paper is to develop new efficient approaches based on DC programming and DCA for clustering.
• We consider the two models for the Minimum Sum-of-Squares Clustering (MSSC): a mixed integer program and a bilevel programming formulation.
• The mixed integer program is reformulated as a DC program via an exact penalty technique for which DCA is investigated.
• A Gaussian kernel version of the bilevel programming formulation is introduced and a simple and efficient DCA scheme is developed.
• The two main features of DCA, say the effect of DC decomposition and of starting points, are carefully studied.
摘要
Highlights•The purpose of this paper is to develop new efficient approaches based on DC programming and DCA for clustering.•We consider the two models for the Minimum Sum-of-Squares Clustering (MSSC): a mixed integer program and a bilevel programming formulation.•The mixed integer program is reformulated as a DC program via an exact penalty technique for which DCA is investigated.•A Gaussian kernel version of the bilevel programming formulation is introduced and a simple and efficient DCA scheme is developed.•The two main features of DCA, say the effect of DC decomposition and of starting points, are carefully studied.
论文关键词：Clustering,MSSC,Gaussian kernel,Combinatorial optimization,Nonsmooth nonconvex programming,DC programming,DCA,Exact penalty
论文评审过程：Received 12 September 2012, Revised 10 June 2013, Accepted 22 July 2013, Available online 3 August 2013.
论文官网地址：https://doi.org/10.1016/j.patcog.2013.07.012
