Regression as a way to determine variable importance 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?
 A: 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.

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)

A: 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.
