最近邻查找最优算法_机器学习-KNN（k-nearest neighbor）最近邻算法

1、什么是KNN

k近邻法(k-nearest neighbor, kNN)是一种基本分类与回归方法，其基本做法是：给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。

通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。

k近邻法不具有显式的学习过程，事实上，它是懒惰学习(lazy learning)的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。

本文只讨论分类问题中的k近邻法，下一篇文章将会介绍KNN分类的实际案例。

2、KNN的算思想

KNN(k-NearestNeighbor)又被称为近邻算法，它的核心思想是：物以类聚，人以群分

假设一个未知样本数据x需要归类，总共有ABC三个类别，那么离x距离最近的有k个邻居，这k个邻居里有k1个邻居属于A类，k2个邻居属于B类，k3个邻居属于C类，如果k1>k2>k3，那么x就属于A类，也就是说x的类别完全由邻居来推断出来。