Mean Shift Clustering
The mean shift algorithm is a nonparametric clustering technique which does not require prior
knowledge of the number of clusters, and does not constrain the shape of the clusters.
Given n data p oints x
i
, i = 1, ..., n on a d-dimensional space R
d
, the multivariate kernel density
estimate obtained with kernel K(x) and window radius h is
f(x) =
1
nh
d
n
X
i=1
K
x − x
i
h
. (1)
For radially symmetric kernels, it suffices to define the profile of the kernel k(x) satisfying
K(x) = c
k,d
k(kxk
2
) (2)
where c
k,d
is a normalization constant which assures K(x) integrates to 1. The modes of the density
function are located at the zeros of the gradient function ∇f (x) = 0.
The gradient of the density estimator (1) is
∇f(x) =
2c
k,d
nh
d+2
n
X
i=1
(x
i
− x)g
x − x
i
h
2
!
=
2c
k,d
nh
d+2
"
n
X
i=1
g
x − x
i
h
2
!#
P
n
i=1
x
i
g
x−x
i
h
2
P
n
i=1
g
x−x
i
h
2
− x
. (3)
where g(s) = −k
0
(s). The first term is proportional to the density e stimate at x computed with
kernel G(x) = c
g,d
g(kxk
2
) and the second term
m
h
(x) =
P
n
i=1
x
i
g
x−x
i
h
2
P
n
i=1
g
x−x
i
h
2
− x (4)
is the mean shift. The mean shift vector always points toward the direction of the maximum increase
in the density. The mean shift procedure, obtained by successive
• computation of the mean shift vector m
h
(x
t
),
• translation of the window x
t+1
= x
t
+ m
h
(x
t
)
is guaranteed to converge to a point where the gradient of density function is zero. Mean shift mode
finding process is illustrated in Figure 1.
The mean shift clustering algorithm is a practical application of the mode finding procedure:
1
