Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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) ?
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).
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.
