基于局部距离分布自适应估计聚类规模,无需人工设定参数。
Local Cluster Cardinality Estimation for Adaptive Mean Shift
- 用点到其他点的距离分布找局部密度极小值来估计聚类基数。
- 在9个数据集上7个表现优于已有方法,最高提升0.03。
- 无需预设聚类数,适合未知簇数的自适应聚类任务。
本文提出一种自适应均值漂移算法,每个点的参数均由该点自身到其他点的距离分布决定。通过识别距离分布密度的局部最小值来估计局部聚类基数,进而确定该点的带宽与核半径阈值。该估计器具有尺度不变性,因所依赖的γ函数在数据乘以正常数时保持不变,无需人为设定数据尺度。同时具备局部性:γ在秩k处的取值仅依赖于前k个最近距离,且均值漂移核在估计的聚类半径处截断,使超出半径的数据既不参与聚类估计也不影响加权均值。这与固定邻域大小的核密度估计不同,后者需整体选定带宽。本算法在自适应均值漂移家族中表现优异:在Ren等(2014)研究的9个数据集上,7个取得更高兰德指数,其中4个提升超过0.03,3个提升低于0.012;在更广泛的聚类基准测试中也表现良好,且无需提供聚类数量。
原文摘要 · Abstract (English)
This article presents an adaptive mean shift algorithm in which every parameter used at a point is derived from that point's own distance distribution. The distance distribution from a point to all others is used to estimate the cardinality of the local cluster by identifying a local minimum in the density of that distribution; the statistics of the identified subset then set the bandwidth and the kernel radius threshold applied at that point. The estimator built this way is scale invariant, since the $γ$ function it rests on is unchanged when the data is multiplied by a positive constant, so no length constant has to be chosen for the scale of the data. It is also local: $γ$ evaluated at rank $k$ depends only on the $k$ nearest distances, and the mean shift kernel is truncated at the estimated cluster radius, so data lying beyond that radius neither enters the estimate of the local cluster nor contributes to the weighted mean. This contrasts with kernel density estimation, which in its basic form measures density in a neighborhood of fixed size and needs a bandwidth chosen for the dataset as a whole. Our algorithm is competitive within the adaptive mean shift family: it obtains a higher Rand index than the weighted adaptive mean shift method of Ren et al. (2014) on seven of the nine datasets of that study, four of them by more than 0.03 and three by less than 0.012, and it performs competitively on a broader clustering benchmark, in both cases without being given the number of clusters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。