为什么Weka中的KNN实现运行更快？

Question

1) 我们知道KNN在训练阶段不执行任何计算，而是将所有计算推迟到分类阶段，因此我们称其为惰性学习器。它应该在分类中花费比训练更多的时间，但是我发现对于weka来说这个假设几乎相反。在weka中，KNN在训练时需要比测试更多的时间。

为什么在weka中KNN在分类方面表现得更快？这是为什么？是否也会导致计算错误？

2) 当我们说KNN中的特征加权可能会提高高维数据的性能时，我们指的是什么？我们是指特征选择和选择具有高信息增益的特征吗？

- Kashif Khan

Answer 1

问题1的回答：

我猜测Weka实现使用某种数据结构来高效地执行（近似）最近邻查询。

使用这样的数据结构，查询可以比以朴素方式执行时更加高效。

这样的数据结构示例包括KD树和SR树。

在训练阶段，需要创建数据结构，因此它将比分类花费更多的时间。

问题2的回答：

对于最相关的特征使用更高的权重，对不太相关的特征使用较低的权重，可能会提高预测性能。

另一种提高预测性能的方法是进行特征选择。使用互信息或其他一些单变量关联（例如连续变量的Pearson相关系数）是执行特征选择的最简单和最容易的方法。请注意，减少变量数量可以在计算时间方面提供显着的加速。

当然，您可以两者兼顾，即首先执行特征选择，然后对剩余特征使用权重。例如，您可以使用互信息来对剩余特征进行加权。对于文本分类，您还可以使用TF-IDF对特征进行加权。

- George

---

除了构建邻域数据结构之外，“训练”阶段的含义也不是很清楚。由于这是一种惰性学习算法，正如OP所评论的那样，在任何训练阶段都没有要拟合或校准的参数集。您只需针对组成分类器的数据集计算任何传入观察结果（无论您是否想将其称为“训练”观察结果）的相关信息即可。 - ely

@George，感谢你的回复。能否详细说明一下你的第二个答案？一种方法是通过信息增益等特征选择方法去除不相关的特征，这可能会提高性能。我曾经在某处读到过将特征的权重乘以其频率（TF-IDF）的方法，这也可以使具有更大权重的特征更加重要。提前致谢 :) - Kashif Khan

@EMS，让我更担心的是K-Neighbors算法。即使我们假设它内部实现了高效的数据结构，正如George所说，对于10(K=10)个邻居进行分类计算距离所需的时间仍然比拟合边缘函数（SVM）要长。但是我观察到的是两者几乎相同。除非我们看到结果，否则无法确定其邻居。 - Kashif Khan