Elsevier, Pattern Recognition, 1(44), p. 70-77
DOI: 10.1016/j.patcog.2010.07.004
Full text: Download
This article considers the minimum sum-of-squares clustering (MSSC) problem. The mathematical modeling of this problem leads to a min-sum-min formulation which, in addition to its intrinsic bi-level nature, has the significant characteristic of being strongly nondifferentiable. To overcome these difficulties, the proposed resolution method, called hyperbolic smoothing, adopts a smoothing strategy using a special C∞ differentiable class function. The final solution is obtained by solving a sequence of low dimension differentiable unconstrained optimization subproblems which gradually approach the original problem. This paper introduces the method of partition of the set of observations into two nonoverlapping groups: “data in frontier” and “data in gravitational regions”. The resulting combination of the two methodologies for the MSSC problem has interesting properties, which drastically simplify the computational tasks.