Autores

4451
47,1834
4452
47,1834

Informações:

Publicações do PESC

Título
Solving the Minimum Sum-of-Squares Clustering Problem by Hyperbolic Smoothing and Partition into Boundary and Gravitational Regions
Linha de pesquisa
Otimização
Tipo de publicação
Relatório Técnico
Número de registro
ES-731/10
Data
1/2010
Resumo
Abstract

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 non overlapping groups: ”data in frontier” and ”data in gravitational regions”. The resulting combination of the two methotologies for the MSSC problem has interesting properties, which drastically simplify the computational tasks.

Keywords: Cluster Analysis, Pattern Recognition, Min-Sum- Min Problems, Nondifferentiable Programming, Smoothing.

Topo