# fast distance metric between a new data entry and available clusters of data

Assume we divide a large data set D into m different partitions of data in a distributed learning case, using K-means clustering. We do the training in the clusters and they are local experts. Now, we have some new test points that we want to assign to the partitions and obtain the predictions. An initial guess is we can find the distance between new points the centroids of the clusters which may take time in large data sets. I want to know if there is any faster method that works faster when the number of the new points increases? Also, except distance metrics, it there any similarity-based measures that can be used to make a connection between new entries and available partitions' centroids?

• It is a bit strange to start asking what measure is faster to compute, without first deciding on what can conceptually serve a proximity between a cluster and a point. Will that be a distance to centroid? medoid? nearest neighbour? etc. Commented Mar 5, 2022 at 8:56
• @ttnphns You are right. I updated the question. Assume K-means clustering has been used to divide a data set into some partitions. Then, the initial solution for the question is we can find the distance between new points and the centroids of the clusters. But in this question, I want to know is there any effienct substitute for that? Commented Mar 6, 2022 at 10:56
• Computing a distance between a point and a centroid is fast. Centroid is a fixed location in space, a "point" on its own, so as soon as you've got a cluster, you can compute the coordinates of the centroid. Then, when needed, you compute the distance from every newcomer data points to this "point". Commented Mar 6, 2022 at 12:28
• Fun question (+1). I think we can turn this task to its head and get a very elegant solution via classification. Please see my answer below. Commented Mar 7, 2022 at 0:38

Don't cluster. Classify.

I have expanded on this topic here How to assign new data to an existing clustering but to give some more details why this allows us to have a "fast approximate distance metric".

Especially if we use a classifier $$C$$ based on trees (e.g. random forests, gradient boosting, etc.) what we would have learned through the training of it will be a recursive partitioning of our sample space (through piece-wise flat functions) such that it aligns as closely as possible with the class/cluster labels. This recursive partitioning is exactly what will allow us now to compute a fast approximate distance from the cluster centres/exemplars in the form of our class/cluster membership probabilities. (where for example, a high probability of being in class $$A$$ suggest someone "very close" to a typical class/cluster $$A$$ instance.

To that extent, this "trick" of recursive partitioning our sample space via a tree-based classifier is exactly the "trick" we use when calculating approximate distances between points from a large high-dimensional sample via ball trees.

(Do note though that, unlike ball trees we don't have to use a tree-based classifier, I used it as an example, any classifier with probabilistic outputs will do.)

• I didn't understand your first sentence. The speach, as I understand, is about assignment, not clustering. Given some "small" number of new data cases, we simply assign them to the nearest clusters, we don't recalculate clusters (e.g., their centroids) after every assignment or even all the "small" number of assignments is done. Commented Mar 7, 2022 at 9:56
• (cont.) You are suggesting to perform an additional analytic procedure after the initial clustering, classification, to derive another rule of assignment of cases than the "distance to centroid" rule having come from the clustering procedure. The another rule can be potentially better and more sophisticated than it, but how can it speed up the whole job? Can you explain how adding a classification analysis will make the whole project of new assignments faster in the end. This might be so, only that you haven't explained it in more detail. Commented Mar 7, 2022 at 9:56
• No worries, the first sentence is a bit tongue-in-cheek that if you can't classify based on your clustering then probably it is not really useful. :) (And I never suggested we recalculated clusters...) For the main part: If we resort to "simply assign them to the nearest clusters" we don't have an idea about how the metric is interpreted between clusters/classes, probability is much more interpretable. Also, assuming we do brute force calculations of (Euclidean) distances that can be slower than using recursive partitioning (that's why the link to the ball trees in my answer). Commented Mar 7, 2022 at 12:39