Performance guarantees for hierarchical clustering
Performance guarantees for hierarchical clustering
复制标题
DOI：
10.1016/j.jcss.2004.10.006
复制
发表时间：
2005-06-01
影响因子：
1.1
通讯作者：
Long, PM
中科院分区：
文献类型：
--
作者：
Dasgupta, S;Long, PM
我们表明，对于任何度量空间中的任何数据集，都可以构造一个层次聚类，并保证对于每个k，诱导的k-聚类的成本最多是最佳k-聚类的8倍。这里，聚类的成本被认为是其聚类的最大半径。我们的算法是相似的简单性和效率流行的凝聚层次聚类，我们表明，这些凝聚具有无界的逼近因子。(c)2004爱思唯尔公司All rights reserved.
We show that for any data set in any metric space, it is possible to construct a hierarchical clustering with the guarantee that for every k, the induced k-clustering has cost at most eight times that of the optimal k-clustering. Here the cost of a clustering is taken to be the maximum radius of its clusters. Our algorithm is similar in simplicity and efficiency to popular agglomerative heuristics for hierarchical clustering, and we show that these heuristics have unbounded approximation factors. (c) 2004 Elsevier Inc. All rights reserved.