6
$\begingroup$

At my work, we employ a nearest neighbor algorithm to classify records. Part of this process, of course, includes determining which features to use as auxiliary information in the algorithm. Also, we allow the features we select to be weighted so that more important features have higher weight in the distance calculation.

When it comes to selecting which features to use and how to weight them, the first thought my colleagues often have is to run a regression on the variable of interest using the auxiliary information and then use the coefficients and/or the p-values obtained from that regression to decide which features and their weights to use in the nearest neighbor algorithm.

My initial thought is that this method is probably not the best way to go about it, but I can't come up with any concrete reasons against it other than saying that what features may work well in the regression context may not work well in the nearest neighbor context.

Does anyone have any thoughts on the validity of this method? Is it an appropriate feature selection method or am I correct in thinking that it is not the best way?

$\endgroup$
4
  • 1
    $\begingroup$ Are you normalizing the auxiliary variables so that they are on the same scale? If not, importance measured in this way will depend on the units of measurement in an arbitrary way. $\endgroup$ – Dimitriy V. Masterov Aug 24 '18 at 18:33
  • $\begingroup$ I agree that yes if you are going to do the above method than normalizing the variables is a must, but is that enough? Is there anything else preventing this from being a viable method? $\endgroup$ – astel Aug 27 '18 at 4:12
  • $\begingroup$ I like to use "Boruta" and "permutation variable importance", but I'm not then transforming the space using that in any sort of a Mahalanobis sense. How are you accounting for "weight"? Is that already encoded for in more than one way in your approach? $\endgroup$ – EngrStudent Aug 27 '18 at 18:28
  • $\begingroup$ When I was referring to weight in my original post I meant it in this sense: We use a function created in house to calculate distance as follows, for each auxiliary variable distance is calculated using some measure (can vary for different variable types) and is scaled down to be between 0 and 1. Total distance is simply the addition of all such scaled down distances. Since all distances are on the same scale when you add all of the together, if you believe some have more importance than others you can assign higher weights to them in the addition. D = W1D1 + W2D2 + ... + WpDp $\endgroup$ – astel Aug 27 '18 at 18:36
5
+100
$\begingroup$

Does anyone have any thoughts on the validity of this method?

The main issue I can see is that the linear regression proposes to split the sample space in two (the two "sides" of a hyperplane), whereas the nearest neighbors will split it in regions (maybe a lot), depending on how the different classes are sampled on the sample space.

The worst case scenario I can see is the following. Your data shows a distribution that KNN can handle well, but that a linear regression will perform miserably at, like a chessboard on the following picture (the code is at the bottom of the post). Though this is a caricature, many other datasets will exhibit the same behavior.

enter image description here

A linear regression would discard both features if you select your features based on the p-values :

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)  1.538955   0.041424  37.151   <2e-16 ***
x1          -0.037032   0.027543  -1.345    0.179    
x2          -0.006612   0.027526  -0.240    0.810    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

If you decide to weight the features based on the weights of the linear regression, note that the weights may be order of magnitudes different, though there is no reason for them to be ! This would be equivalent to project your data on a single axe, on which the KNN could not learn anything relevant (think about the colors of the dots if you look at them from a single dimension).

Therefore, I would not use such an approach to calibrate the weights of a KNN (or select the attributes).

Edit

You can increase any goodness of fit measure adding variables showing a linear dependency with respect to the target. In this case, the goodness of fit would not be trivial any longer, but you would lose the information that comes from the first two variables.

On weighted KNN

However, there is a possibility to change the distance function, from an Euclidean distance to a distance where the dimensions have different weights. This approach is long to tune because you have to evaluate the model each time you change the weight of one attribute. If $p$ is your number of features and you want to replace a feature $x$ by $x/2$ and $x\times2$, you have $3^p$ models to evaluate (with a naive strategy).

Note that you may have a significant improvement if you treat the features independently (not every combination of them), running only $3\times p$ models.

Other improvements for KNN

J. Wang, P. Neskovic, and L. N. Cooper, “Improving nearest neighbor rule with a simple adaptive distance measure,” Pattern Recognition Letters, vol. 28, no. 2, pp. 207–213, Jan. 2007.

"Random KNN feature selection - a fast and stable alternative to Random Forests" Shengqiao Li, E James Harner and Donald A Adjeroh, Bioinformatics 2011 12:450

Code

N <- 2000

decision_function <- function(x){
  (((x[1]%%1-0.5)*(-x[2]%%1-0.5))>0)+1
}

x <- abs(matrix(runif(n = N, min = 0, max = 2), ncol = 2))
y <- apply(X = x, MARGIN = 1, FUN = decision_function)

plot(x, col=y)

model <- lm(y ~ x, data = cbind.data.frame(x,y))

summary(model)
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the example, illustrates well the point I was trying to make about features being important in the regression context not necessarily being important in the nearest neighbors space. I guess my only counter point to your example, is that the R squared in your example would be so low that it would be obvious that feature selection using regression would be a bad idea. I am wondering if there exist less obvious cases where features would be bad in regression and good in KNN but the regression still performs well on the whole. $\endgroup$ – astel Aug 27 '18 at 19:23
  • $\begingroup$ @astel Indeed, the goodness of fit is low in this case. I edited the post to show that you can increase the goodness of fit of the regression, but where you would still lose information $\endgroup$ – RUser4512 Aug 28 '18 at 9:38
4
$\begingroup$

In the classical regression situation the problem has given rise to a number of solutions. In an article outlining her software for calculating a number of these methods entitled "Relative importance for linear regression in R: the package relaimpo" available here Ulricke Grömping gives a number of different metrics for deciding on the relative importance of predictors in a regression model. Simple ones include: which variable alone does best, which variable adds most conditional on all the others. More complex ones include some relying on standardising first and computer-intensive ones which involve optimising over possible orders of entry of variables into the model. Since the article is open access I will not attempt a more detailed summary here. The software is open source.

$\endgroup$

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.