### Table of Contents

**VLFeat** offers a hierarchical version of integer k-means, which
recursively applies `vl_ikmeans`

to compute finer and finer
partitions. For more details see
Hierarchical Integer
k-means API reference and the Integer
k-means tutorial.

# Usage

First, we generate some random data to cluster in `[0,255]^2`

:

```
data = uint8(rand(2,10000) * 255) ;
datat = uint8(rand(2,100000)* 255) ;
```

To cluster this data, we simply use `vl_hikmeans`

:

```
K = 3 ;
nleaves = 100 ;
[tree,A] = vl_hikmeans(data,K,nleaves) ;
```

Here `nleaves`

is the desired number of leaf
clusters. The algorithm terminates when there are at least
`nleaves`

nodes, creating a tree with ```
depth =
floor(log(K nleaves))
```

To assign labels to the new data, we use `vl_hikmeanspush`

:

```
AT = vl_hikmeanspush(tree,datat) ;
```

# Tree structure

The output `tree`

is a MATLAB structure representing the tree of
clusters:

```
> tree
tree =
K: 3
depth: 5
centers: [2x3 int32]
sub: [1x3 struct]
```

The field `centers`

is the matrix of the cluster centers at the
root node. If the depth of the tree is larger than 1, then the field
`sub`

is a structure array with one entry for each cluster. Each
element is in turn a tree:

```
> tree.sub
ans =
1x3 struct array with fields:
centers
sub
```

with a field `centers`

for its clusters and a field
`sub`

for its children. When there are no children, this
field is equal to the empty matrix

```
> tree.sub(1).sub(1).sub(1).sub(1)
ans =
centers: [2x3 int32]
sub: []
```

# Elkan

VLFeat supports two different implementations of k-means. While they
produce identical output, the Elkan method is sometimes faster.
The `method`

parameters controls which method is used. Consider the case when `K=10`

and our data is now 128 dimensional (e.g. SIFT descriptors):

```
K=10;
nleaves = 1000;
data = uint8(rand(128,10000) * 255);
tic;
[tree,A] = vl_hikmeans(data,K,nleaves,'method', 'lloyd') ; % default
t_lloyd = toc
tic;
[tree,A] = vl_hikmeans(data,K,nleaves,'method', 'elkan') ;
t_elkan = toc
t_lloyd =
8.0743
t_elkan =
3.0427
```