正确实施加权 K 最近邻

Question

据我了解，classical KNN 算法是这样工作的（对于离散数据）：

让 x 成为您要 classify
令 dist(a,b) 为点 a 和 b[=34= 之间的欧氏距离]

迭代训练集点 pᵢ，取距离 dist(pᵢ,x)

将x分类为K点之间最近的class（根据dist ) 到 x.

我如何在这个 classic KNN 上引入权重？我读到应该更重视更近的点，我读到 this，但不明白这将如何应用于离散数据。

对我来说，首先，使用 argmax 没有任何意义，如果权重增加了距离，那么它会使距离变差。对不起，我在胡说八道。

Answer 1

好吧，坦白说我不是你提供的 link 的粉丝，它有图像方程式并且在图像中遵循不同的符号和正文。

因此，让我们看看常规的 k-NN 算法。 regulark-NN其实只是weightedk-NN的一个特例。您将权重 1 分配给 k 个邻居，将 0 分配给其余邻居。

令W_qj表示一个点j相对于一个点的权重q
设 y_j 为与数据点 j 关联的 class 标签。为简单起见，让我们假设我们 class 将鸟类定义为乌鸦、母鸡或火鸡 => 离散的 classes。所以对于所有 j，y_j <- {乌鸦，火鸡，母鸡}
一个好的权重度量是距离的倒数，无论距离是欧几里德、马氏等
考虑到所有这些，class 标签 y_q 您将与点 q 相关联 您试图预测的是 w_qj 的总和。 y_j 项除以所有权重的总和。如果先对权重进行归一化，则无需除法。
你最终会得到如下等式 somevalue₁ 。乌鸦 + somevalue₂ 。母鸡 + somevalue₃ 。火鸡
其中一个 classes 将具有更高的 somevalue。具有最高值的 class 是您将预测的点 q
为了训练的目的，您可以根据需要考虑任何错误。由于 classes 是离散的，因此调整权重以提高准确性的简单方法数量有限

Answer 2

考虑一个包含三个分类（红绿蓝）和用 R、G、B 表示的六个最近邻居的简单示例。我将其设为线性以简化可视化和算术

R B G x G R R

列出距离的点是

class dist
  R     3
  B     2
  G     1
  G     1
  R     2
  R     3

因此，如果我们使用未加权的最近邻，简单的 "voting" 算法是 3-2-1，有利于 Red。但是，由于加权影响，我们有 ...

red_total   = 1/3^2 + 1/2^2 + 1/3^2  = 1/4 + 2/9 ~=  .47
blue_total  = 1/2^2 ..............................=  .25
green_total = 1/1^2 + 1/1^2 ......................= 2.00

... 并且 x 由于距离接近 Green 而结束。

那个lower-delta函数仅仅是分类函数；在这个简单的例子中，它 returns red | green | blue。在一个更复杂的例子中，......好吧，我会把它留给后面的教程。

正确实施加权 K 最近邻

Correct implementation of weighted K-Nearest Neighbors

algorithm

classification

machine-learning

knn