Fast Nonparametric Density-Based Clustering of Large Data Sets Using a Stochastic Approximation Mean-Shift Algorithm.
Fast Nonparametric Density-Based Clustering of Large Data Sets Using a Stochastic Approximation Mean-Shift Algorithm.
复制标题
DOI：
10.1080/10618600.2015.1051625
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Baran A
中科院分区：
文献类型：
--
作者：
Hyrien O;Baran A
均值漂移是一种迭代过程，通常用作非参数聚类算法，它基于密度函数的模态区域定义聚类。该算法在概念上是有吸引力的，既不对集群的形状也不对它们的数量做假设。然而，由于每次迭代的复杂度为O（n2），它不能很好地扩展到大型数据集。我们提出了一种新的算法，执行密度为基础的聚类速度比均值漂移，但提供几乎相同的结果。该算法结合了子采样和随机逼近过程，以实现在每一步的潜在复杂度为O（n）。它的收敛性是成立的。它的性能进行了评估，使用模拟和图像分割的应用程序，该算法是几十倍或几百倍的速度比均值漂移，但造成的聚类错误可以忽略不计。该算法可以与现有的方法相结合，以进一步加快聚类。
Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n2) per iteration, it does not scale well to large data sets. We propose a novel algorithm which performs density-based clustering much quicker than mean-shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. Its performances are evaluated using simulations and applications to image segmentation, where the algorithm was tens or hundreds of times faster than mean-shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with existing approaches to further accelerate clustering.