为什么KNN比决策树快得多？

在面试中，我遇到了雇主提出的问题。他问我为什么KNN分类器比字母识别或人脸识别中的决策树快得多？为什么KNN比决策树快得多？

我当时完全不知道。所以我想知道在哪些方面我应该比较速度性能中的两种分类方法？谢谢。

2013-03-15 zfz

网上有很多比较 – Dreamwalker 2013-03-15 09:03:48

考虑以下数据集：N个样本，每个样本都有k个属性。一般：
1.天真KNN：O（1）[训练时间] + O（NK）[查询时间] = O（NK）
2.天真决策树：O（N^2 * K * log（N））[训练时间] + O（log（N））[查询时间] = O（N^2 * K） - 同样对于查询时间，我们假定树是平衡的。
为了计算复杂性，我认为每个分类器的实现都非常简单。对于实施KNN和决策树已经没有多少改进。

来源

2013-03-15 09:35:45

非常感谢您的回答。你能否更详细地解释每个分类器的训练时间？谢谢。 – zfz 2013-03-16 08:18:19

@Majid，你能否为进一步阅读提供参考？ – jsb 2017-10-24 18:01:22

为什么KNN比决策树快得多？

回答

相关问题