Title :

Dendrograms, Minimum Spanning Trees and Feature Selection

Author(s) :

Labbé, Martine [Auteur]
Université libre de Bruxelles [ULB]
Integrated Optimization with Complex Structure [INOCS]
Landete, Mercedes [Auteur]
Universidad Miguel Hernández [Elche] [UMH]
Leal, Marina [Auteur]
Universidad Miguel Hernández [Elche] [UMH]

Journal title :

European Journal of Operational Research

Pages :

555-567

Publisher :

Elsevier

Publication date :

2023-07

ISSN :

0377-2217

English keyword(s) :

Mixed integer linear optimization
Feature selection
Hierarchical clustering
Single linkage
Minimum spanning tree

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL