A (N2) Algorithm for the Maximum Sum-of-Splits Clustering Problem

, , and

BibTeX reference

Consider N entities to be classified, and a matrix of dissimilarities between pairs of them. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside it. The single-linkage algorithm provides partitions into M clusters for which the smallest split is maximum. We study here the average split of the clusters or, equivalently, the sum of splits. A (N2) algorithm is provided to determine maximum sum-of-splits partitions into M clusters for all M between N - 1 and 2, using the dual graph of the single-linkage dendrogram.

, 24 pages