加权k最近邻搜索

Question

我搜索了很多次，没有得到任何有用的结果。

问题是:给定一组向量，我希望找到它的近似k近邻。这里的警告是，我的每个维度都类似于一个不同的实体，因此在计算距离时，我们不能对每个维度使用相同的权重。因此，像kd-tree这样的解决方案不能正常工作。

是否有任何数据结构或替代算法，我可以用它来寻找这样的近似加权k近邻。

注:将初始输入数据与其权重相乘，以获得统一的权重并不是一种选择。

Answer 1

我强烈建议使用上面描述的缩放，因为它比手动方法更快。如果由于某种原因，缩放/预处理不可用，请使用metric参数传递自定义加权函数。参见下面的示例。

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
```

Answer 2

根据@an6u5's的评论：

如果你想对一维的权重高于其他维度，那么我建议你标准化所有的数据，使平均值为零，标准差为1。然后，你可以用一个因子(2-10)把不太重要的维度相乘，这样它们就会出现在距离KNN距离的更远的地方，而使最重要的维数没有标度。请注意，标准化和缩放都是完全可逆的过程，所以没有什么理由不使用这个简单的解决方案。