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) ;

Hierarchical integer K-means. Left: A depiction of the recursive clusters. Each node is a cluster center. The root note is not depicted (its center would be the mean of the dataset). Right: Clusters are represented as different colors (here are more than 100 clusters, but only three colors are used).

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

VLFeat.org

Table of Contents

Usage

Tree structure

Elkan