Resolução do Problema de Agrupamento Segundo o Critério da Soma de Distâncias
Autores
5200 |
1834,131
|
|
5237 |
1834,131
|
Informações:
Publicações do PESC
Este trabalho considera a resolução do problema de agrupamento correspondente à minimização da soma das distâncias euclideanas das observações aos seus centróides, através do uso da técnica de suavização hiperbólica. A modelagem matemática deste problema leva a uma formulação min-sum-min que, além de sua intrínseca natureza bi-nível, tem a importante característica de ser um problema fortemente não-diferenciável e não-convexo, com um grande número de mínimos locais. A estratégia de suavização hiperbólica resolve uma seqüência de subproblemas diferenciáveis de otimização irrestrita de baixa dimensão, que gradualmente se aproxima do problema original. A confiabilidade e a eficiência do método são ilustradas através de um conjunto de experimentos computacionais. Deve-se enfatizar que a metodologia proposta pode ser aplicada para a resolução do problema de localização de Fermat-Weber, que é análogo ao problema tratado.
This work considers the clustering problem corresponds to the minimization of the sum of the euclidean distances of observations to their cluster centroids. The mathematical modeling of this problem leads to a min-sum-min formulations which in addition to its intrinsic bi-level nature, has the significant characteristic of being strongly non-differentiable and non-convex problem with a large number of local minima. The hyperbolic smoothing strategy solves a sequence of low dimension differentiable unconstrained optimization sub-problems, which gradually approaches the original problem. The reliability and efficiency of the method are illustrated via a set of computational experiments. It must be emphasized that the proposed methodology can be analogously applied to the solving of the Fermat-Weber location problem.