### 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.

# 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:

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.