scikit-learn/scikit-learn — Issue #442: Add Gaussian kernel to mean shift clustering
Author: conradlee
Created: 2011-11-15 00:16:30+00:00
State: open

# Motivation

Currently the mean shift clustering uses a flat kernel.

While this is quick and simple, there are some disadvantages. There is no guarantee that the center will be the densest part a flat kernel---it might be that the center is sparse and that a single kernel covers the centers of two or more clusters at its periphery (If you mess around a bit with the test case by changing the bandwidth or seeding method, this disturbing behavior comes out---the center of the found clusters are in fact *between* the true cluster centers).

I propose that we should also implement a Gaussian kernel because such a kernel would prefer to have dense regions near the center (and this is a common kernel in the literature). The bandwidth parameter would act as the standard deviation for the gaussian kernel. I propose that we use the same standard deviation in all dimensions (just as we used the same radius in all dimensions for the flat kernel).

# Efficiency considerations

The flat kernel is efficient, because only points with a certain radius (specified by the bandwidth parameter) are relevant for the mean shift calculation. These points can be efficiently looked up from the larger dataset using the BallTree.

In theory, each time we update a Gaussian kernel we should also consider all points in the dataset, but in practice the method may work well if we ignore all points beyond some distance--let's call this the "cutoff distance". Given that we expect over 99% of points to fall within three standard deviations of the center of a gaussian distribution, perhaps we could set this cutoff to 3X the bandwidth.