1
$\begingroup$

Let's say that you embed a collection of items belonging to multiple classes into a multidimensional space for predicting unseen future items by K Nearest Neighbors.

And in a particular scenario it is okay to remove some items from the collection in order to improve the k-nearest neighbor classification that you get from the multidimensional embedding of the collection. What may be particular terms, algorithms or applicable areas of research that may fit this scenario?

Naively, one could prune away items which fail to correctly classify from the embedding or which participate many times in wrongly classifying other items by being their (incorrect class) closest neighbor until some overall accuracy measure is reached, but obviously this is an optimization problem.

Are there any known algorithms applicable to this use case?

$\endgroup$

1 Answer 1

1
$\begingroup$

When you have a complex dataset having multiple dimensions, one good approach is to start with a correlation heatmap in order to have a view of the influences between each variable, and remove the ones that don't have correlation (but keeping the anti correlated ones).

Then, the correlation between the data could be either linear, either non linear. In most cases, there are non linear correlations, and applying a linear algorithm like KNN could give worst result than non-linear ones.

That's why it is often better to use a non-linear multi dimensional reduction algorithm like t-SNE or UMAP (based on gaussians ~ "natural" proximity calculation between points).

However, starting with all the dimensions might generate blured result due to the curse of dimensionality. Consequently, in order to be efficient, you should start with the 2 or 3 most meaningful dimensions (or features), and then increase them with the next meaningful ones. This approach is safer than taking all features and then removing some of them to improve your results.

$\endgroup$
4
  • $\begingroup$ Thanks. I was actually looking at the particular scenario where one would like to reject items that fail a knn classification or falsely classify other items in the collection under a given feature set, rather than the usual scenario of feature selection that you have, as I understand, described. $\endgroup$
    – matanox
    Jun 13, 2022 at 18:19
  • $\begingroup$ You are actually doing a kind of reverse engineering of an existing classification done with KNN, in order to improve it removing features, is it correct? $\endgroup$ Jun 13, 2022 at 18:57
  • $\begingroup$ Not really, thanks. I am rather working under an assumption that removing items (not features) that don't play well in the classification is helpful for the scenario at hand. This is then more of an optimization problem ― which items to remove given the set of conflating pairs of items (items having a different class yet close up to the chosen k value, to one another). $\endgroup$
    – matanox
    Jun 14, 2022 at 19:10
  • $\begingroup$ In that case, you could use the standard deviation in order to remove the items that are far from the main distribution. For example: stats.stackexchange.com/questions/291449/… $\endgroup$ Jun 14, 2022 at 19:23

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.