Given a set of objects and their pairwise distances, the aim is to determine a visual representation of the data. The quartet paradigm is used to compute a hierarchy of clusters of the objects. The method is based on an NP-hard graph optimization problem called the Minimum Quartet Tree Cost problem. This presentation shows and compares several suitable metaheuristic approaches to approximate the optimal hierarchy. The performance of the algorithms was tested through extensive computational experiments and it is shown that the Reduced Variable Neighborhood Search metaheuristic is the most effective approach to the problem, obtaining high quality solutions in short computational running times.
Clustering, heuristic methods, combinatorial optimization, graphs and networks
Consoli S., Darby-Dowman K., Geleijnse G., Korst J., Pauws S.. (2010)
Heuristic approaches for the quartet method of hierarchical clustering,
IEEE Transactions on Knowledge and Data Engineering, 22(10):1428-1443.