%tableofcontents;

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