K近邻 - 有监督 - 一种多类划分的模型

K近邻

K近邻 - 有监督 - 一种多类划分的模型（K近邻不像感知机只能划分两种类，K近邻是一种多类划分的模型）

K近邻算法缺点：

1、在预测样本类别时，待预测样本需要与训练集中所有样本计算距离，当训练集数量过高时（例如Mnsit训练集有60000个样本），每预测一个样本都要计算60000个距离，计算代价过高，尤其当测试集数目也较大时（Mnist测试集有10000个）。

2、K近邻在高维情况下时（高维在机器学习中并不少见），待预测样本需要与依次与所有样本求距离。向量维度过高时使得欧式距离的计算变得不太迅速了。本文在60000训练集的情况下，将10000个测试集缩减为200个，整个过程仍然需要308秒（曼哈顿距离为246秒，但准确度大幅下降）。

使用欧氏距离还是曼哈顿距离，性能上的差别相对来说不是很大，说明欧式距离并不是制约计算速度的主要方式。最主要的是训练集的大小，每次预测都需要与60000个样本进行比对，同时选出距离最近的K项。

为了解决这一问题，前人提出了KD树算法。

KD树

KD树将整个特征空间划分成多个区域，直观上来看，首先将整个空间分成A、B区域，待测样本判断在A区的时候，那B区过远，内部的点就不需要再判断了，大幅度减少需要比较的样本数量。