THE WEIGHTED SUM OF SPLIT AND DIAMETER CLUSTERING

In this paper, we propose a bicriterion objective function for cluster ing a given set of N entities, which minimizes [alpha d - (1 - alpha)s ], where 0 less than or equal to alpha less than or equal to 1, and d and s are the diameter and the split of the clustering, respectively. When alpha = 1, the problem reduces to minimum diameter clustering, an d when alpha = 0, maximum split clustering. We show that this objectiv e provides an effective way to compromise between the two often confli cting criteria. While the problem is NP-hard in general, a polynomial algorithm with the worst-case time complexity O(N-2) is devised to sol ve the bipartition version. This algorithm actually gives all the Pare to optimal bipartitions with respect to diameter and split, and it can be extended to yield an efficient divisive hierarchical scheme. An ex tension of the approach to the objective [alpha(d(1) + d(2)) - 2(1 - a lpha)s] is also proposed, where d(1) and d(2) are diameters of the two clusters of a bipartition.