0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

I think you need to take a step back and figure out what you're trying to do at a higher level.

How were the existing classes built? If they were built by clustering unlabeled data, then with this new data point you're continuing with the clustering process.

If the existing classes are labeled data, then k-NN is one possible classification method, and there are plenty more (decision trees, naive bayes, neural networks, etc.).

If you're doing clustering, then there are several ways of assigning a point to a cluster, among measuring the distances from the point to cluster centroids is one. There's also single-linkage (distance is min of distances from point to points of cluster), complete-linkage (max of distances). These different methods will give clusters with different shapes and there's no universally best approach. You could test them with points that are already in clusters... but then if you're certain of what classes they re in, then you have a classification problem.

So... if it's classification, then you can use k-NN, that's similar to the idea of assigning a point to a cluster according to distance. But it's not defined as finding the nearest cluster, it's defined as finding the classes of the k nearest points, then applying a vote or something. 1-NN is basically like single-linkage clustering. kNN does require finding the most similar (training) data points to your new data point. Sampling is definitely sub-optimal, but it may be good enough if you classes are well separated. If the cost of calculating distances is high, then one way of reducing the cost of calculation is the idea of skyline clustering: use a cheap distance metric to determine a subset of points that are likely to be among the k nearest neighbours, then compute these neighbours using the more expensive distance metric.

Finally, if you will be classifying many points and not updating your model, it may be worth training a model (e.g. a decision tree) on the existing classes.

$\endgroup$
  • $\begingroup$ Thanks a lot! your are really inspiriting! are there standard/classical methods to check/quantify if the classes are well separated or overlaps? $\endgroup$ – user1830108 Apr 15 '15 at 15:47
  • $\begingroup$ I would say classes are well separated if you can train a classifier on them and it gets very high accuracy. But if you can do that you probably don't need to do any sampling for k-NN... Or if when you apply k-NN, the top-k classes are consistently the same... you could try k-NN on a subset of your data, then try the "sampling" way, and try to quantify your loss. $\endgroup$ – user3780968 Apr 15 '15 at 23:55
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! But one thought about using a cluster centroid, it would require each cluster has similar volume/or radius. if all potential clusters are significantly differ in volume, I do not sure the method can work in the case? $\endgroup$ – user1830108 Apr 14 '15 at 15:01
  • $\begingroup$ @tomc4yt how do you calculate the distance of a new data point from existing cluster centroid using sql? $\endgroup$ – Rut Nov 14 '18 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.