Clustering via Mode Seeking by Direct Estimation of the Gradient of a Log-Density

By Hiroaki Sasaki, Aapo Hyvärinen, Masashi Sugiyama. 2014

46 citations recorded by the source corpus.

Mean shift clustering finds the modes of the data probability density by identifying the zero points of the density gradient. Since it does not require to fix the number of clusters in advance, the mean shift has been a popular clustering algorithm in various application fields. A typical implementation of the mean shift is to first estimate the density by kernel density estimation and then compute its gradient. However, since a good density estimation does not necessarily imply an accurate estimation of the density gradient, such an indirect two-step approach is not reliable. In this paper, we propose a method to directly estimate the gradient of the log-density without going through density estimation. The proposed method gives the global solution analytically and thus is computationally efficient. We then develop a mean-shift-like fixed-point algorithm to find the modes of the density for clustering. As in the mean shift, one does not need to set the number of clusters in advance. We experimentally show that the proposed clustering method significantly outperforms the mean shift especially for high-dimensional data.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

PixelDefend: Leveraging Generative Models to Understand and Defend against Adversarial Examples (2017, methodology): “…not speciﬁcally designed for handling adversarial data; for example, the manifold denoising method of Hein & Maier (2007), the direct density gradient estimation of Sasaki et al. (2014), and the denoising autoencoders of Vincent et al. (2008) all move data points from low to high-density regions.”
Density Estimation in Infinite Dimensional Exponential Families (2013, background): “An important application that does not require the computation of A(θ) is in finding modes of the distribution, which has recently become very popular in image processing (Comaniciu and Meer, 2002), and has already been investigated in the score matching framework (Sasaki et al., 2014).”
Sliced Score Matching: A Scalable Approach to Density and Score Estimation (2019, background): “Beyond training unnormalized models, sliced score matching can also be naturally adapted as an objective for estimating the score function of a data generating distribution (Sasaki et al., 2014; Strathmann et al., 2015) by training a score function model parameterized by deep neural networks.”
Learning deep kernels for exponential family densities (2018, methodology): “…applications of the kernel exponential family model have exclusively employed simple kernels, such as the Gaussian kernel, with a small number of parameters (e.g. the length scale) either chosen heuristically or selected via cross-validation (e.g. Sasaki et al. 2014; Strathmann et al. 2015).”
Regularized Multitask Learning for Multidimensional Log-Density Gradient Estimation (2014, methodology): “For the accelerometry data whose dimensionality is only five, S-LSLDGC gives the best performance and MT-LSLDGC does not improve the performance, although MT-LSLDGC performs better than C-LSLDGC.”
Gradient Estimators for Implicit Models (2017, methodology): “[34] and [40] derived a parametric solution by ﬁrst approximating the log density up to a constant with the RBF kernel K ( x , x 5) to obtain the coefﬁcients a k .”
Efficient Learning of Generative Models via Finite-Difference Score Matching (2020, methodology): “SM methods can be also used in score estimation [35, 54, 61].”