Dendrograms, minimum spanning trees and feature selection

doi:10.1016/j.ejor.2022.11.031

Return

Dendrograms, minimum spanning trees and feature selection

2023-07-01

Martine Labbé

Marina Leal *

DOI：10.1016/j.ejor.2022.11.031

Original

Save

View PDF

Abstract

En 中文

Feature selection is a fundamental process to avoid overfitting and to reduce the size of databases with-out significant loss of information that applies to hierarchical clustering. Dendrograms are graphical rep-resentations of hierarchical clustering algorithms that for single linkage clustering can be interpreted as minimum spanning trees in the complete network defined 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 different formulations that include the minimum spanning tree problem constraints as well as the feature selection constraints. Different 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 computa-tional study, the effectiveness of the different 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.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )

Keywords:

Combinatorial optimization

Feature selection

Hierarchical clustering

Single linkage

Minimum spanning tree

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.