Analysis of Agglomerative Clustering

Details Analysis of Agglomerative Clustering Analysis of Agglomerative Clustering

2010-12-16

arxiv.org/abs/1012.3697v2

Computer Science

Data Structures and Algorithms

A preliminary version of this article appeared in Proceedings of the 28th International Symposium on Theoretical Aspects of Co

Scientific paper

The diameter k-clustering problem is the problem of partitioning a finite subset of R^d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem (for all values of k) is the agglomerative clustering algorithm with the complete linkage strategy. For decades, this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper, we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension d is a constant, we show that for any k the solution computed by this algorithm is an O(log k)-approximation to the diameter k-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we adapt our analysis to the closely related k-center and discrete k-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of O(log k) as well. However, we are able to improve the dependency on d.

Affiliated with

Also associated with

No associations

Rating

Analysis of Agglomerative Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of Agglomerative Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of Agglomerative Clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-220115