Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Solving the Minimum Sum of L1 Distances Clustering Problem by Hyperbolic Smoothing and Partition into Boundary and Gravitational Regions
verfasst von : Adilson Elias Xavier, Vinicius Layter Xavier, Sergio B. Villas-Boas
Erschienen in: Algorithms from and for Nature and Life
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The article considers the minimum sum of distances clustering problem, where the distances are measured through the L1 or Manhattan metric (MSDC-L1). The mathematical modelling 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 non differentiable.
We propose the AHSC-L1 method to solve this problem, by combining two techniques. The first technique is Hyperbolic Smoothing Clustering (HSC), that adopts a smoothing strategy using a special C
∞
completely differentiable class function. The second technique is the partition of the set of observations into two non overlapping groups: “data in frontier” and “data in gravitational regions”. We propose a classification of the gravitational observations by each component, which simplifies of the calculation of the objective function and its gradient. The combination of these two techniques for MSDC-L1 problem drastically simplify the computational tasks.