K近邻算法

Question

使用KNN算法，比如k=5。现在我尝试通过获取一个未知对象的5个最近邻居来对其进行分类。如果在确定了4个最近的邻居之后，接下来的2个(或更多)最近的对象具有相同的距离，该怎么办？这2个或更多的对象中的哪一个应该被选为第五个最近邻居？

Answer 1

应选择这2个或更多对象中的哪个对象作为第五个最近邻居？

这真的取决于你想要如何实现它。

大多数算法会做三件事中的一件：

1. 包括所有相等距离的点，因此对于此估计，它们将使用6个点，而不是5个。
2. 使用两个相等距离的点中的“第一个”找到的点。
3. 从找到的2个点中随机选择一个点(通常具有一致的种子，因此结果是可重现的)。

也就是说，大多数基于径向搜索的算法都有一个固有的平稳性假设，在这种情况下，你选择上面的哪个选项真的无关紧要。一般来说，从理论上讲，它们中的任何一个都应该提供合理的默认值(特别是因为它们是近似值中最远的点，并且应该具有最低的有效权重)。

Answer 2

另一个有趣的选择是使用最近的邻居，如下所示：

• 计算每个类到样本的5个最近邻居的距离:每个类之间有5个距离。
• 然后得到每个类的平均距离。
• 较低的平均距离将是您将分配给样本的类。

这种方法对于重叠类的数据集是有效的。

Answer 3

如果你有另一个距离函数，你可以用它来打破平局。即使是一个糟糕的人也可以完成这项工作，如果你有一些启发式的话会更好。例如，如果您知道计算主距离时考虑的某个特征更重要，则仅使用此特征来求解平局。

如果不是这样，请随机选择。在同一测试集上多次运行您的程序，以检查随机选择是否重要。