Abstract: Since the existing clustering synchronization clustering algorithm Sync is highly complex in time, and it cannot be applied into the case of large sample, it proposes a new algorithm named Fast Clustering by Synchronization on Large Sample（FCSLS）. To apply this algorithm, it firstly condenses the large sample dataset by using the KDE based sampling method, and then, carries out the cluster synchronization of compressed dataset, finding out the best clustering data by using the Davies-Bouldin clustering criterion, finally, gets the final clustering results by clustering the rest objects in the large dataset. Based on the empirical result from the synthetic datasets and UCI real-world datasets, it concludes that FCSLS can detect clusters of any shape density and size without pre-setting the cluster number. Meanwhile, comparing with the compression algorithm based on RSDE and CCMEB, FCSLS can significantly reduce the operation time of the cluster synchronization algorithm without losing the clustering accuracy.

Key words: Kernel Density Estimate（KDE）, sampling, synchronization, large sample, clustering

摘要： 针对现有的Sync算法具有较高时间复杂度，在处理大样本数据集时有相当的局限性，提出了一种快速大样本同步聚类算法（Fast Clustering by Synchronization on Large Sample，FCSLS）。首先将基于核密度估计（KDE）的抽样方法对大样本数据进行抽样压缩，再在压缩集上进行同步聚类，通过Davies-Bouldin指标自动寻优到最佳聚类数，最后，对剩下的大规模数据进行聚类，得到最终聚类结果。通过在人造数据集以及UCI真实数据集上的实验，FCSLS可以在大规模数据集上得到任意形状、密度、大小的聚类且不需要预设聚类数。同时与基于压缩集密度估计和中心约束最小包含球技术的快速压缩方法相比，FCSLS在不损失聚类精度的情况下，极大地缩短了同步聚类算法的运行时间。

关键词: 核密度估计（KDE）, 抽样, 同步, 大样本, 聚类