This tutorial shows how to use the K-means algorithm using the VlFeat implementation of Llloyd's algorithm as well as other faster variants.

Running K-means

KMeans is a clustering algorithm. Its purpose is to partition a set of vectors into $K$ groups that cluster around common mean vector. This can also be thought as approximating the input each of the input vector with one of the means, so the clustering process finds, in principle, the best dictionary or codebook to vector quantize the data.

Consider a dataset containing 1000 randomly sampled 2D points:

numData = 5000 ;
dimension = 2 ;
data = rand(dimension,numData) ;

The function vl_kmeans can be used to cluster the data into, say, 30 groups:

numClusters = 30 ;
[centers, assignments] = vl_kmeans(data, numClusters);

By default, this uses the the Lloyd algorithm, a method that alternates between optimizing the cluster centers and the data-to-center assignments. Once this process terminates, the matrix centers contains the cluster centers and the vector assignments the (hard) assignments of the input data to the clusters. The cluster centers are also called means because it can be shown that, when the clustering is optimal, the centers are the means of the corresponding data points. The cluster centers and assignments can be visualized as follows:

KMeans clustering of 5000 randomly sampled data points. The black dots are the cluster centers.

Given a new data point x, this can be mapped to one of the clusters by looking for the closest center:

x = rand(dimension, 1) ;
[~, k] = min(vl_alldist(x, centers)) ;

For larger datastes, this process may be significantly accelerated by using KDTrees or other approximate nearest neighbor procedures.

Choosing an initialization method

K-means uses local optimization algorithms and is therefore sensitive to initalization. By default, vl_kmeans initializes the cluster centers by picks $K$ data points at random. Other initalization strategies can be selected as well. kmeans++ is a popular method that greedily pick $K$ data points that are maximally different, and can be use as follows:

[centers, assignments] = vl_kmeans(data, numClusters, 'Initialization', 'plusplus') ;

Choosing an optimization algorithm

In addition to the original KMeans algorithm proposed by Lloyd, vl_kmeans supports two additional algorithms: Elkan's variant, an exact algorithm using an acceleration technique based the triangular inequality, and ANN, an approximated algorithm using approximate nearest neighbours.

These optimization methods can be enabled by setting the 'Algorithm' parameter to 'Lloyd', 'Elkan' or 'ANN' respectively. When using the 'ANN' algorithm, the user can also specify the parameters 'MaxNumComparisons' and 'NumTrees' to configure the KD-tree used used as ANN. In particular, 'MaxNumComparisons' controls the trade-off between approximation quality and speed.

vl_demo_kmeans_ann_speed compares the speed of the three algorithms. Because of the random initialization, each of the KMeans calls converges to a different local minimum in a different amount of iterations. In order to measure more accurately the speed of each pass, a relatively small number of 'MaxNumIterations' option) is selected. Note that the speedup factor are in general much more dramatic when truly large datasets are considered.

Comparisons of Elkan, Lloyd and ANN for different values of MaxNumComparison, expressed as a fraction of the number of clusters. The figure reports the duration, final energy value, and speedup factor, using both the serial and parallel versions of the code. The figure was generated using vl_demo_kmeans_ann_speed.