CURE: an efficient clustering algorithm for large databases
CURE: an efficient clustering algorithm for large databases
复制标题
DOI：
10.1145/276304.276312
复制
发表时间：
1998-06
期刊：
影响因子：
--
通讯作者：
S. Guha;R. Rastogi;Kyuseok Shim
中科院分区：
文献类型：
--
作者：
S. Guha;R. Rastogi;Kyuseok Shim
在数据挖掘中，聚类对于在底层数据中发现组和识别感兴趣的分布非常有用。传统的聚类算法要么倾向于球形和相似大小的聚类，要么在异常值存在时非常脆弱。我们提出了一种新的聚类算法，称为CURE，它对异常值具有更强的鲁棒性，并且可以识别具有非球形形状和大小差异较大的聚类。CURE通过从聚类中选择分散良好的点，然后将它们向聚类中心缩小一个指定的分数，从而生成一定固定数量的点来表示每个聚类，从而实现了这一点。每个簇有多个代表点可以使CURE很好地适应非球形的几何形状，并且缩小有助于抑制异常值的影响。为了处理大型数据库，CURE结合了随机抽样和分区。首先对从数据集中抽取的随机样本进行分区，然后对每个分区进行部分聚类。然后在第二步中对部分聚类进行聚类，以产生所需的聚类。我们的实验结果证实，CURE生成的聚类质量比现有算法的聚类质量好得多。此外，他们证明了随机抽样和分区使CURE不仅优于现有算法，而且在不牺牲聚类质量的情况下可以很好地扩展到大型数据库。
Clustering, in data mining, is useful for discovering groups and identifying interesting distributions in the underlying data. Traditional clustering algorithms either favor clusters with spherical shapes and similar sizes, or are very fragile in the presence of outliers. We propose a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size. CURE achieves this by representing each cluster by a certain fixed number of points that are generated by selecting well scattered points from the cluster and then shrinking them toward the center of the cluster by a specified fraction. Having more than one representative point per cluster allows CURE to adjust well to the geometry of non-spherical shapes and the shrinking helps to dampen the effects of outliers. To handle large databases, CURE employs a combination of random sampling and partitioning. A random sample drawn from the data set is first partitioned and each partition is partially clustered. The partial clusters are then clustered in a second pass to yield the desired clusters. Our experimental results confirm that the quality of clusters produced by CURE is much better than those found by existing algorithms. Furthermore, they demonstrate that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.