1
$\begingroup$

I have run $k$-means on a large set of high-dimensional data, and now I want to find the distance from a point $x$ to the Voronoi cell associated with one of the $k$ centroids. (In a previous version of the question, I called this cell a "cluster", but that terminology might be confusing since one might think of a cluster as simply a set of points in the dataset.)

Can this be done efficiently? If not, can I efficiently approximate it? If I actually need the distance from the point to all $k$ Voronoi cells, is there anything faster than just running the point-to-cell distance computation $k$ times?

Also, I am not wedded to $k$-means. Actually, the question could be interesting for many types of clustering, and I would love to know about others too!

$\endgroup$
5
  • $\begingroup$ About the second problem: notice that in $d$ dimensions, it takes at least $d$ distances between an unknown point and known points to locate the former. So you must compute at least $d$ distances, making the problem $\Omega(d^2)$. $\endgroup$
    – user16034
    Sep 29, 2022 at 15:11
  • $\begingroup$ Hi, I'm not sure which problem you mean by "the second problem", but in general I don't understand how this observation about locating unknown points implies anything about my problem(s). If $k=2$, for example, you could just explicitly compute the decision boundary and figure out the distance to it and which side the point is on in a constant number of operations with complexity $O(d)$. $\endgroup$
    – gmr
    Sep 29, 2022 at 16:04
  • $\begingroup$ I am commenting on the existence of a shortcut to computing the $k$ distances. $\endgroup$
    – user16034
    Sep 29, 2022 at 16:09
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – gmr
    Sep 29, 2022 at 16:11
  • $\begingroup$ A rough rule of thumb is: when the dimension $d$ is large, everything is hard and you're just hosed (for worst-case running time). So I don't hold out much hope for an efficient ($o(kd)$ time) answer to your question. When $d=2$, there are lots of clever algorithms. $\endgroup$
    – D.W.
    Sep 29, 2022 at 17:04

1 Answer 1

1
$\begingroup$

If you want to compute distance to the closest (different) cluster, then problem is $\Theta(kd)$ as you just need to compute distance to $k$ hyperplanes. However, if you want to compute distance (of a point $p$) to a general cluster, you need to solve a Quadratic program (QP). Voronoi cell is a solution to a set of linear inequalities, say $\{x | Ax \leq b\}$. Then the quadratic program is: $$ \min ||x-p||^2$$ $$ s.t. Ax \leq b.$$

It is a convex quadratic program in a general form. Generally, they are all different and solving one does not help with solving the others. If you implement this yourself, you can however benefit from warm restarts. When you know the closest point in one Voronoi cell, the closest point in the neighbouringcell is likely to be very close (or even the same point.)

In 2d I'm pretty sure it can be done in an efficient way using some smart data structure and algorithm, but I would be very surprised if there is an easier solution than I described in dimension d > 3 (for d = 3 I have no opinion).

$\endgroup$
2
  • $\begingroup$ Thanks! This makes a lot of sense. Unfortunately, I don't have any experience with convex QP. I spent some time Googling, but I was still unsure what performance to expect (or even whether the problem is $O(kd)$) and what software package would be good. In my application, $k$ and $d$ are both in the range 100-1000. $\endgroup$
    – gmr
    Sep 29, 2022 at 21:46
  • $\begingroup$ The performance of QP solvers varies a lot by the problem structure. E.g., if we expect just a few constraints to be active - as it is probably here - it could be beneficial to solve the dual problem via coordinatewise descent since the dual solution will be probably sparse. See en.wikipedia.org/wiki/Quadratic_programming for the dual problem. On the other hand, before implementign it yourself, you should probably try the available solvers (e.g., pypi.org/project/qpsolvers) With k,d = 1000 I would expect very roughly 0.1 sec per QP. The $O(kd)$ is not for QP. $\endgroup$
    – V.V.
    Sep 29, 2022 at 22:30

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.