Consider N entities to be classified, and a matrix of diffimilarities 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. An O(N3) algorithm is provided to determine maximum sum of splits partitions into M clusters for all M between N-1 and 2.
Published March 1988 , 22 pages