Splitting an ordering into a partition to minimize diameter

Splitting an ordering into a partition to minimize diameter

0.00 Avg rating0 Votes
Article ID: iaor1999906
Country: United States
Volume: 14
Issue: 1
Start Page Number: 51
End Page Number: 74
Publication Date: Jan 1997
Journal: Journal of Classification
Authors: ,
Keywords: partitioning
Abstract:

Many algorithms can find optimal bipartitions for various objectives including minimizing the maximum cluster diameter (‘min-diameter’); these algorithms are often applied iteratively in top-down fashion to derive a partition P-k consisting of k clusters, with k > 2. Bottom-up agglomerative approaches are also commonly used to construct partitions, and we discuss these in terms of worst-case performance for metric data sets. Our main contribution derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered. Dynamic programming can optimally split such an ordering into a partition P-k for a large class of objectives that includes min-diameter. We explore a variety of ordering heuristics and show that our algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.

Reviews

Required fields are marked *. Your email address will not be published.