7
$\begingroup$

I'm quite new to this StackExchange, only been a lurker till now, but my StackOverflow fellows have said you'd be the best people to ask about this.

Anyway, enough introduction. I'm using the weighted k-Nearest-Neighbours algorithm. My original data set has 37 features. I've looked into using PCA to reduce dimensionality, and I'm going to follow this method.

For simplicity's sake, let us assume that two of the new features created account for 90% of the variance and I'm only going to use these two new features. Let us call them feature 1 and feature 2 ($f_1$, $f_2$). Let us say that $f_1$ accounts for 60% of the variance and $f_2%$ accounts for 30% of the variance. I know wish to select the weights ($w_1 , w_2$) for these two features. My initial intuition is that we could correlate the variance accounted for with the weight of the feature. Therefore, I would use a weight combination of $w_1 = 0.6$ and $w_2 = 0.3$ in my k-Nearest-Neighbours algorithm.

I am well aware that there is much literature suggesting the best way to select weights would be to use a lattice type of method where we select different combinations of weights and then follow through with combination that yields the best results. I was just wondering if the intuition of weights being related to total variance accounted for was. Also, as my dataset actually requires 11 features to be used to account for 90% of the variance, I'd like to have a starting point for determining combinations of weights.

Summary: When using PCA as a precursor for kNN, is it possible to base the weights of features in k-NN on the total variance said features accounts for in the data?

Sorry if there are any formatting errors or if I'm breaking any protocols. Let me know if I have, and I will update the post.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Can you please elaborate how exactly you wish to "base the weights of features in k-NN on the total variance of said features". For k-NN you need a distance metric for determining the closest neighbor. Do you intend to use some sort of weighted Euclidean metric, using the weights for PCA? Or maybe something else? $\endgroup$ – Leeor Sep 16 '13 at 13:16
  • $\begingroup$ Yes, I'll be using a weighted Euclidean metric to do my kNN. With normal k-NN, each feature has the same weight applied to it. Imagine two data sets (form of (x,y)): (5, 13) and (8, 17). The distance here is 5 if we weight both x and y evenly. If we double the weight of y, we end up with ((8-5)^2 + (2*(17-13))^2)^0.5, which is a higher score (y is the further away one). I am trying to determine the best weights to use. $\endgroup$ – Keshava Murthy Sep 16 '13 at 13:39
  • $\begingroup$ Another issue to consider when choosing the "best" algorithm is whether to choose supervised or unsupervised learning. Do you have any training examples (whose class are known)? $\endgroup$ – Leeor Sep 16 '13 at 13:47
  • $\begingroup$ I do have training classes. In fact, I have already developed an algorithm to use for testing the weights. I input the weights I've decided and it lets me know how successful it was. The problem is that if I decide each weight can be one of 0,0.1,0.2...0.9,1.0, there are 11 combinations. And since there are 37 parameters, this means 11^37 simulations. $\endgroup$ – Keshava Murthy Sep 16 '13 at 14:38
5
$\begingroup$

There are many options you could pursue, I can suggest a few. First, if you already have a training set, and assuming the training set is large enough, you could learn a distance metric instead of using PCA weights-based interpretation. See Mahalanobis Distance as an example of distance metric learning.

The main idea is that you intend to use a weighted Euclidean metric: $$ D(x_1,x_2)=\sqrt{(x_1-x_2)^TC(x_1-x_2)} $$ $$ C=diag(w_1...w_n) $$ The Mahalanobis distance is similarly defined, although it takes into account the cross correlation covariance between the variables (some of your features may be correlated) $$ D_M(x_1,x_2)=\sqrt{(x_1-x_2)^TC(x_1-x_2)} $$

where C is the covariance matrix.

Another option is instead of using PCA, which is an unsupervised method, use a supervised method, such as Class Augumented-PCA. Generally speaking, you could use any interpretable machine learning classification algorithm (gives you the weights) and use K-NN with the weights.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks Leeor. Read a bit into this and it looks like what I'll try out. However, out of curiosity, what do you mean "interpretable machine learning classification algorithm"? $\endgroup$ – Keshava Murthy Sep 18 '13 at 12:26
  • $\begingroup$ What I mean is an algorithm that not only outputs the class but also an "interpretation". For example, weights, whether from PCA or from a supervised algorithm, give an insight or interpretation of which features are "more important". $\endgroup$ – Leeor Sep 23 '13 at 8:22

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.