为什么K-最近邻居中的K减少会增加复杂性？

Question

在我的教科书的摘录中,它说减少K运行这个算法的价值实际上增加了复杂性,因为它必须运行更"平滑".

任何人都可以向我解释这个吗？

我的理解是1NN,你在训练集中喂它.您在测试集上进行测试.假设您的测试集中有一个点.它在训练集中找到与它最接近的一个点,并返回该值.

当然,这比找到最近的3个点更简单3NN,加上它们的值并除以3？

我误解或忽视了什么？

Answer 1

读这个公理时,我有同样的难以置信的时刻; 一个降低复杂性的较高值的参数起初似乎有点违反直觉.

为了直观地说明这一点,让我们比较一个最近邻训练的模型和一个N >> 1最近邻模型.让我们使用带有二进制分类的简化二维图(双特征数据集)(每个"点"具有A或B的类或标签).

对于1最近邻模型,训练集的每个示例可能是预测A类或B类的区域的中心,其大多数邻居是预测另一类的区域的中心.你的情节可能看起来像世界各地的种族,语言或宗教地图之一,它们深深交织在一起(巴尔干或中东浮现在脑海中):复杂形状和交替颜色的小片,没有明显的逻辑,因此"高度复杂".

如果增加k,预测每个类的区域将更加"平滑",因为它是决定任意点类的k个最近邻居的大多数.因此,这些区域的数量较少,尺寸较大,形状可能较简单,如世界同一地区的国家边界政治地图.因此"复杂性降低".

(本课程的直觉和来源.)