Kernel Clustering in High-Dimensional Feature Spaces

Matthew Gray

May 15, 1998

1 Introduction

Support Vector Machines (SVMs) are a clever way to do structural risk minimization. The real trick of SVMs is the utilization of a kernel function to represent the dot product in a high dimensional feature space. This construction allows an algorithm which can be formulated in tears of dot products to be performed in an arbitrarily high-dimensional feature space without the computational burden. Schölkopf, Smola and Müller^{1} show that this technique can be applied to principal component analysis. They further suggest that one might use the same approach for projection pursuit, kmeans clustering, k nearest neighbor, or any other technique that can be cast in terms of dot products.

2 Algorithm

First we define a non-linear mapping Φ(x) of feature vectors x into our high dimensional feature space, and a kernel function k(x, y) = Φ(x)·Φ(y). Naturally, the means for our clustering lie in the span of the Φ(x) feature vectors. We will define the coefficients on these mapped feature vectors as:

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:

||Φ(x) − ∑_{j=1}^{M} γ_{νj}Φ(x_{j})||^{2} = k(x, x) − 2 ∑_{j=1}^{M} γ_{νj}k(x, 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:

1Nonlinear Component Analysis as a Kernel Eigenvalue Problem, TR #44, Max-Planck-Institut für biologische Kybernetic, 1996

γ_{α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)

After correcting γ for each new training point, we recalculate cluster assignments, and correct γ again, until it converges. To identify which cluster a test point belongs in, we simply calculate the distance using equation 2. This k-means implementation was tested on a variety of data with limited success, while it performed well on non-overlapping clusters, even those that were not linearly seperable, overlapping clusters, as would be expected, performed poorly. Modifying the algorithm to use E-M clustering with fixed width Gaussians is trivial. The expectation step is calculated as usual, using Formula 2 for distance. In the maximization step, The updated means in E-M are moved to the the responsibility weighted centroid of the data. Therefore, in our representation of the means, the coefficients γ_{νj} are equal to the responsibility cluster ν has for data point j. We now iterate to the expectation phase and iterate until the convergence. The choice of kernel function is the same constraint as it is under SVMs. Reasonable choices include k(x, y) = (x · y + 1)^{n}, which represents a feature space of polynomials, and k(x, y) =

e^{− \frac{∥x−y∥^{2}}{σ^{2}}} , which corresponds to an infinite feature space composed of features of the form e^{iωx} for all real values of ω, and generates RBF decision surfaces. For all of the problems used below the RBF kernel is used, with manually optimized parameters.

3 Toy Problem

An initial toy problem was generated to see the algorithm work. Two distributions in 2d were generated and the algorithm was run on the combined distribution. Distribution A was a unit variance Gaussian centered at [0,0]. Distribution B was a mixture of 4 unit variance Gaussians at [4,4], [5,5], [6,6], and [7,7]. The algorithm was run with 2 clusters and the densities for each cluster are shown in Figures 1 and 2. The overall distribution was zero-centered, so the distributions are shifted from their original locations in the figures. Given this performance with only 2 fixed width Gaussians in the high-dimensional feature space, the technique seems to have a lot of potential.

4 Application

The algorithm was tested on a set of hand gesture data from the Media Lab. The data was composed of two sets (s1 and s1) of three gestures (point, stop and wave) each. Each gesture is composed of some number of frames (usually about 50). Each frame is used to generate a feature vector composed of the 2-dimensional coordinates of the hand and the coefficients of the first 20 eigenimages of the frame. A preliminary examination of how well the algorithm produces density estimates in a real problem is promising. Figure 4 shows the density estimate of a 2-dimensional subset of the features for the “pointing” gesture, using a single high-dimensional Gaussian. Density estimation was performed for three different training/test data sets. First, all 20 gestures of a particular type (from sets s1 & s2) were combined, and a random set of 100 frames were selected.

Figure 1: The first cluster settled on Distribution A Figure 2: The second cluster settled on Distribution B Figure 3: Density estimate on a subset of the features for one frame of one gesture

4 The clustering was then performed on each gesture type to generate the density estimates. All the frames in the dataset were then classified using a 3-way Bayesian classifier based on these densities. Second, 50 samples from the 10 gestures from dataset s1 were taken as training data and densities were estimated. These densities were then used to classify the frames from datasets s1 and s2. Given these classifications of the individual frames, it is necessary to combine them somehow. An initial ad hoc simple majority voting scheme was tried initially and yielded surprisingly good results. Due to this, other combination techniques were not pursued. The total errors for the first experiment (training on 100 random samples and testing on the full data set) were

Gesture Per frame Accuracy Ad hoc voting accuracy
Point  76%  100%
Wave  50%  100%
Stop  61%  90%

For training on 50 samples from dataset s1, and testing on the dataset s1:

Gesture Per frame Accuracy Ad hoc voting accuracy
Point  62%  100%
Wave  79%  100%
Stop  68%  90%

and finally, for 50 samples from dataset s1, and testing on the dataset s2:

Gesture Per frame Accuracy Ad hoc voting accuracy
Point  65%  100%
Wave  20%  0%
Stop  57%  100%

5 Conclusion

The technique works quite well, but needs some refinement. Currently, it is rather slow, and initial estimates for parameters of the kernel function should be able to be gotten from the training data. I also want to see whether or not in certain cases it is similar or equivalent to other existing techniques. For example, I think the single Gaussian fit is essentially equivalent to Parzen windows, but this needs to be determined with rigor. Further, clusters should be able to be of variable width, and other applications are worth exploring.