对于K近邻K-NN算法的理解 March 9, 2018 [TOC] ### 整体思想 今天看了K-NN算法，该算法适用于分类，整体思想是把训练数据集当成了一个数据库，在训练数据集找与输入数据最临近的k个数据，这k个数据中的多数属于某个类，这个输入就输入某个类。特别地， k=1 是称为最近邻算法。 ### 如何定义近邻 可以用欧氏距离，$$L_p$$距离，Minkowski距离等。 ### k值的选择 k太小，学习的近似误差会减小，估计误差会增大，比如遇到噪声，这时候容易发生过拟合。 k过大，会增加不相近的数据对输入的干扰，虽然增大了学习的近似误差，但是减少了估计误差，k的增大意味着整体模型变得简单。 k=N，对于一个输入用上了全部数据，不可取。 ### 分类决策规则 多数投票表决规则等价于经验风险最小化，除了投票还有求均值等规则。 ### 实现 书上介绍通过kd树实现训练数据存储，然后在kd树上查找最近邻。除了kd树还有很多优化算法。