Table of Contents
This tutorial shows how to use the K-means algorithm using the VlFeat implementation of Llloyd's algorithm as well as other faster variants.
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) ;
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
centers contains the cluster centers and the
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
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,
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
ANN, an approximated algorithm using
approximate nearest neighbours.
These optimization methods can be enabled by setting the
'Algorithm' parameter to
'ANN' respectively. When using
'ANN' algorithm, the user can also specify the
'NumTrees' to configure
the KD-tree used used as ANN. In
'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
'MaxNumIterations' option) is selected. Note that the
speedup factor are in general much more dramatic when truly large
datasets are considered.