In this paper, we introduce a new approach called Competitive Agglomeration (CA), which combines the advantages of hierarchical and partitional clustering techniques. The CA algorithm starts by partitioning the data set into a large number of small clusters. As the algorithm progresses, adjacent clusters compete for data points, and clusters that lose in the competition gradually become depleted and vanish. Thus, as the iterations proceed, we obtain a sequence of partitions with a progressively diminishing number of clusters. The final partition is taken to have the "optimal" number of clusters from the point of view of the objective function. Since the algorithm starts with an overspecified number of clusters, the final results are quite insensitive to the initialization and to local minima. In addition, we can incorporate different distance measures in the objective function of the CA algorithm to find an unknown number of clusters of various shapes. We illustrate the performance of the CA algorithm for the special cases of spherical, ellipsoidal, linear, and shell clusters.
展开▼