z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here