
Optimal clustering by merge-based branch-and-bound
Author(s) -
Pasi Fränti,
Olli Virmajoki
Publication year - 2022
Publication title -
applied computing and intelligence
Language(s) - English
Resource type - Journals
ISSN - 2771-392X
DOI - 10.3934/aci.2022004
Subject(s) - merge (version control) , cluster analysis , branch and bound , upper and lower bounds , mathematics , search tree , computer science , algorithm , search algorithm , artificial intelligence , mathematical analysis , information retrieval
We present a method to construct optimal clustering via a sequence of merge steps. We formulate the merge-based clustering as a minimum redundancy search tree, and then search the optimal clustering by a branch-and-bound technique. Optimal clustering is found regardless of the objective function used. We also consider two suboptimal polynomial time variants based on the proposed branch-and-bound technique. However, all variants are slow and has merely theoretical interest. We discuss the reasons for the results.