about predict the class for a new datapoint I have a new data point and want to classify it into the existing classes.I can calculate pairwise distance for the new point to all existing points(in the existing classes). I know using KNN would be a straightforward to classify this point. Is there a way I could randomly sampling existing classes and then correlated the new point to a potential classes without calculating all pairwise distances?
Since you have your clusters set up already you should be able to calculate cluster centroids and then determine the distance between a each cluster centroid and the new data point. You could follow the same process with random samples of each cluster.