4
$\begingroup$

I've searched quite a bit and haven't landed on any useful results.

The problem statement is: Given a set of vectors, I wish to find its approximate k-nearest neighbors. The caveat here is that each of my dimensions resemble a different entity and hence we cannot use the same weight for each dimension while computing the distance. Thus, solutions like kd-tree don't work as is.

Is there any data-structure or any alternate algorithm that I can use to find such approximate weighted k-nearest neighbors.

Note: Multiplying the initial input data with their weights so as to get a uniform weight is not an option.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Assuming you do have a set of weights for each component, why not use a metric like $d(x,y)=\sqrt{\sum_{i=1}^nw_i(x_i-y_i)^2}$ to figure out the closest neighbors? $\endgroup$
    – Alex R.
    Commented Aug 13, 2015 at 20:27
  • 3
    $\begingroup$ Have you considered scaling your data before applying K-nerarest neighbours ? $\endgroup$
    – image_doctor
    Commented Aug 14, 2015 at 0:40
  • 5
    $\begingroup$ If you want to weight one dimension higher than others then I suggest you standardize all of your data so that the mean is zero and the standard deviation is one. Then you can multiply the less important dimensions by a factor (2-10) so that they appear farther away to the KNN distance metric and leave the most important dimension un-scaled. Note that both standardizing and scaling are completely reversible processes, so there is very little reason not to use this simple solution. $\endgroup$
    – AN6U5
    Commented Aug 14, 2015 at 23:29
  • 1
    $\begingroup$ @AN6U5 Thanks. That certainly makes sense. However, my k-d tree is not constant. It needs to support both adding nodes (which is less frequent) and the k-neighbor search query(which is very frequent). In that case standardizing the data won't be a good option correct. $\endgroup$
    – sushant-hiray
    Commented Aug 17, 2015 at 13:05
  • 1
    $\begingroup$ The definition of "nearest" becomes meaningless in multiple dimensions with un-standardized data. If Alice has 2 dogs and 10 apples and Bobby has 4 dogs and 5 apples, the distance between them without standardization is measured as some fractional power law of dog-apples, which changes as the distance vector changes orientation. Its absolute garbage! Once you standardize, the distance metric is measured in units of standard deviation of the population. I understand the you have some sort of online learning algo, but the math only makes sense if you can define a mean and std. $\endgroup$
    – AN6U5
    Commented Aug 17, 2015 at 15:35

2 Answers 2

Reset to default
2
$\begingroup$

I strongly recommend using scaling as described above because it is faster than the manual method. If for some reason, scaling/preprocessing is unavailable, please use the metric parameter to pass a custom weighting function. See the example below.

import numpy as np

from sklearn.neighbors import KNeighborsClassifier as KNN

arr = np.random.randn(500, 10) # train X data
y = np.random.randint(2, size=(500,)) # train y data

# define custom weight function
weights = np.abs(np.random.randn(100)) # set up the desired weights
def weighted_distance(sample_x, sample_y):
    global weights
    return np.sqrt(sum((w * w * x * x * y * y) for w, x, y in zip(weights, sample_x, sample_y)))

knn = KNN(n_neighbors=3, metric=weighted_distance)
knn.fit(arr, y)
test = np.random.randn(5,10) # validation or test data
knn.predict(np.random.randn(5,10)) # predict
```
Improve this answer
$\endgroup$
1
$\begingroup$

As per @an6u5's comment:

If you want to weight one dimension higher than others then I suggest you standardize all of your data so that the mean is zero and the standard deviation is one. Then you can multiply the less important dimensions by a factor (2-10) so that they appear farther away to the KNN distance metric and leave the most important dimension un-scaled. Note that both standardizing and scaling are completely reversible processes, so there is very little reason not to use this simple solution

Improve this answer
$\endgroup$

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.