深入理解KNN扩展到ANN

一、KNN原理

一句话就可以概括出KNN（K最近邻算法）的算法原理：综合k个“邻居”的标签值作为新样本的预测值。更具体来讲KNN分类过程，给定一个训练数据集，对新的样本Xu，在训练数据集中找到与该样本距离最邻近的K（下图k=5）个样本，以这K个样本的最多数所属类别（标签）作为新实例Xu的预测类别。

由上，可以总结出KNN算法有距离度量、 K值的选择 和 决策方法等三个基本要素，如下分别解析：

1.1 距离度量

KNN算法用距离去度量两两样本间的临近程度，最终为新实例样本确认出最临近的K个实例样本（这也是算法的关键步骤），常用的距离度量方法有曼哈顿距离、欧几里得距离：

• 曼哈顿距离 公式：

• 欧几里得距离 公式：

曼哈顿