An Asymptotic Equivalence between the Mean-Shift Algorithm and the Cluster Tree
Two important nonparametric approaches to clustering emerged in the 1970's: clustering by level sets or cluster tree as proposed by Hartigan, and clustering by gradient lines or gradient flow as proposed by Fukunaga and Hosteler. In a recent paper, we argue the thesis that these two approaches are fundamentally the same by showing that the gradient flow provides a way to move along the cluster tree. In making a stronger case, we are confronted with the fact the cluster tree does not define a partition of the entire support of the underlying density, while the gradient flow does. In the present paper, we resolve this conundrum by proposing two ways of obtaining a partition from the cluster tree -- each one of them very natural in its own right -- and showing that both of them reduce to the partition given by the gradient flow under standard assumptions on the sampling density.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Stopping Criterion for the Mean Shift Iterative Algorithm
Image segmentation is a critical step in computer vision tasks constituting an essential issue for pattern recognition and visual interpretation. In this paper, we propose a new stopping criterion for the mean shift iter…
Image SegmentationSegmentationSemantic SegmentationKernel Tests of Equivalence
We propose novel kernel-based tests for assessing the equivalence between distributions. Traditional goodness-of-fit testing is inappropriate for concluding the absence of distributional differences, because failure to r…
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning ar…
Space Partitioning and Regression Mode Seeking via a Mean-Shift-Inspired Algorithm
The mean shift (MS) algorithm is a nonparametric method used to cluster sample points and find the local modes of kernel density estimates, using an idea based on iterative gradient ascent. In this paper we develop a mea…
regressionMean-Shift PCA by Knockoff Mean
Removing noise is difficult, but adding noise is easy. In this work, we show how to eliminate mean-shift noisy components from PCA by deliberately introducing knockoff mean-shift perturbation. Standard PCA is highly sens…