# k-means clustering with efficient point lookup?

What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still efficiently lookup a point $p$ and classify it into a cluster ID (an integer)?

Obviously standard $k$-means alone is not sufficient. Would putting the centroids of each cluster into a BSP or $k'$D-tree do the trick? I used $k'$ there because that $k'$ has nothing to do with $k$.

Instead of the classical $k$-means algorithm where you

• classify all points and then
• update the center of each cluster to be the average of all points of that cluster,

you could use the sequential variant of $k$-means:

centers = random(k)
while True:
p = next_point(points)
c = find_center(centers, p)
c = c + a * (p - c)


next_point iterates all the points and maybe prefers new points (online) for example by using deque and putting new points front.

find_center classifies a point. This takes $O(k)$ naive and $O(\log k)$ using a spacial datastructure like a k-d tree.

$a \in [0,1]$ says how much a center moves in the direction of the given point. Usually this is time dependent and gets lower with time, i.e. $a(t) = \lambda_1 e^{-\lambda_2 t}$. Maybe one could boost the weight of new points though.

• What is c = c + a * (p - c) doing? What is a? Also, why do you think that find_center can be done in $O(\log k)$ time? I don't think that's true -- the running time depends on the dimension, and if the number of dimensions is large, it might be slow. – D.W. Jan 20 '18 at 0:02
• Explained a in answer, thanks. Runtime: k-d trees and similar datastructures can find the nearest neighbor independently of the dimension because they build a search tree where each node halfes the search space along any dimension. But you are right, I did not think too hard about updating the position of a center in the tree. Wikipedia says it's O(log k) where k is the number of points in the tree, not the dimension. But you may have to rebuild the tree from time to time to balance it. – Hannes Jan 20 '18 at 9:15
• I know Wikipedia says it is $O(\log k)$, but Wikipedia leaves out something very important: the dependence on the dimension. In fact, the dependence on the dimension appears to be exponential in the number of dimensions, so the running time is more akin to $O((\log k)^d)$ where $d$ is the number of dimensions. Empirically, my experience is that once $d$ starts getting large, k-d trees aren't much faster than naive linear search through all the points. – D.W. Jan 20 '18 at 16:47