Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Dendrograms, Minimum Spanning Trees and Feature Selection

Abstract : Feature selection is a fundamental process to avoid over tting and to reduce the size of databases without signi cant loss of information that applies to hierarchical clustering. Dendrograms are graphical representations of hierarchical clustering algorithms that for single linkage clustering can be interpreted as minimum spanning trees in the complete network de ned by the database. In this work, we introduce the problem that determines jointly a set of features and a dendrogram, according to the single linkage method. We propose di erent formulations that include the minimum spanning tree problem constraints as well as the feature selection constraints. Di erent bounds on the objective function are studied. For one of the models, several families of valid inequalities are proposed and the problem of separating them is studied. For another formulation, a decomposition algorithm is designed. In an extensive computational study, the e ectiveness of the di erent models is discussed, the model with valid inequalities is compared with the decomposition algorithm. The computational results also illustrate that the integration of feature selection to the optimization model allows to keep a satisfactory percentage of information.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Tuesday, July 19, 2022 - 1:35:44 PM
Last modification on : Friday, July 22, 2022 - 11:57:35 AM


Files produced by the author(s)


  • HAL Id : hal-03727566, version 1



Martine Labbé, Mercedes Landete, Marina Leal. Dendrograms, Minimum Spanning Trees and Feature Selection. 2022. ⟨hal-03727566⟩



Record views


Files downloads