Clustering in High-Dimensional Feature Spaces

Matthew Gray

May 12, 1998

m_{ν} = ∑_{j=1}^{M} γ_{νj}Φ(x_{j}).  (1)

Now, the distance between a mean m_{ν} and a mapped vector Φ(x) can be expressed in terms of dot products:

||Φ(y) − ∑_{j=1}^{M} γ_{νj}Φ(x_{j})||^{2} = k(y, y) − 2 ∑_{j=1}^{M} γ_{νj}k(y, x_{j}) + ∑_{i,j=1}^{M} γ_{νi}γ_{νj}k(x_{i}, x_{j})  (2)

This allows us to determine which cluster is nearest for any given point. For training points, the means should be updated according to:

m_{α}^{new} = m_{α}^{old} + ζ(Φ(x_{new}) − m_{α}^{old})  (3)

where ζ is 1 over the number of points closest to m_{α}. Therefore, to update γ, we do:

γ_{αj}^{new} = \{ \begin{matrix}γ_{αj}^{old}(1 − ζ) & for all j other than the current training point \\ ζ + γ_{αj}^{old}(1 − ζ) & for j = the current training point \end{matrix}  (4)

Modifying this for fixed variance gaussian clusters is easy, in that calculating the centroid in our basis space, given the responsibilities h_{ν}^{(i)} is trivial:

γ_{νi} = h_{ν}^{(i)} = \frac{e^{−∥y−m_{ν}∥^{2}}}{∑_{i=1}^{N} e^{∥y−m_{i}∥}}  (5)

Φ ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} ) = ( \begin{matrix}1 \\ x_{1} \\ x_{2} \\ x_{1}^{2} \\ x_{2}^{2} \\ x_{1}x_{2} \end{matrix} )  (6)

In this case,

k(x, y) = Φ(x) · Φ(y) = (x · y + 1)^{2}  (7)

The RBF kernel I used:

k(x, y) = e^{− \frac{∥x−y∥^{2}}{σ^{2}}}  (8)