K-Nearest Neighbors Algorithm

K近邻算法。

KNN算法非常简单，非常有效。KNN算法适合样本较少典型性较好的样本集。

KNN的模型表示是整个训练数据集。也可以说是：KNN的特点是完全跟着数据走，没有数学模型可言。

对一个新的数据点进行了预测，通过对K个最类似的实例(邻居)的整个训练集进行搜索，并对这些K实例的输出变量进行汇总。对于回归问题，这可能是平均输出变量，用于分类问题，这可能是模式(或最常见的)类值。

诀窍在于如何确定数据实例之间的相似性。如果你的属性都是相同的比例(例如英寸)，最简单的方法就是使用Euclidean距离，你可以根据每个输入变量之间的差异直接计算一个数字。

KNN可能需要大量的内存或空间来存储所有数据，但只在需要时执行计算(或学习)，及时进行预测。你也可以更新和管理你的训练实例，以保持预测的准确性。

距离或接近的概念可以在非常高的维度(大量的输入变量)中分解，这会对算法在你的问题上的性能产生负面影响。这被称为维度诅咒。它也暗示了你应该只使用那些与预测输出变量最相关的输入变量。

适用情景：

优点：

1.简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；

2.可用于数值型数据和离散型数据；

3.训练时间复杂度为O(n)；无数据输入假定；

4.对异常值不敏感

缺点：

1.计算复杂性高；空间复杂性高；

2.样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

3.一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少否则容易发生误分。

4.最大的缺点是无法给出数据的内在含义。

巴特西