3
$\begingroup$

I have an online k-means algorithm following this scheme:

Let x a new data-point, and c the nearest cluster center
if( distance(x, c) > threshold )
   x becomes a new cluster center
else assign x to c

In order to speed up the search for nearest center, is it possible to have a hierarchical structuring of centers, that we can incrementally update each time a new data-point is considered (i.e. without recomputing the whole hierarchy) ?

$\endgroup$

2 Answers 2

1
$\begingroup$

The first what would come to my mind is to use a spatial index structure such as the R-tree or kd-tree to find the nearest cluster center. The R-tree probably is better, because it keeps an optimal structure during changes, while a kd-tree will need to be rebuilt from time to time (it can't be "updated" very well).

$\endgroup$
3
$\begingroup$

If you use a hierarchical clustering algorithm instead of a partitional clustering algorithm like K-means, then a tree-like data structure is already generated for you. You could then search the tree as you would with a binary search tree, where you compare x with the centroid c at each node. In particular, BIRCH clustering might be a good fit for this, as it scales well and produces a balanced tree. My apologies if I'm missing something.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.