K近邻法详解_详细介绍k近邻法

K近邻法（又名KNN）是一种基本的分类方法。K近邻法假设给定一个训练数据集，其中训练集的类别已定，分类时，对于新的实例，通过K个最近邻的训练实例的类别，来判断输入的实例的类别，K近邻法简单，直观，且没有显式的学习过程。

输入：训练集

                               

               实例特征向量x

其中为特征向量，n为训练集的样本容量，为类别

输出：实例x所属的类别

KNN的思想是”物以类聚“，意思就是如果将训练集中的实例点分布在向量空间中，那么聚集在一块儿的点是因为拥有相同的特性，当输入一个实例，如果它周围离它最近的K个点是同一标注的类别（比如都是红色），那么判断它是红色，如果有多个红色一个蓝色一个黄色·，那么根据少数服从多数，该实例也判断为红色。

关于K值的选择

K值较小：如果选择的K值较小，那么预测结果对周围实例点非常敏感，假如邻近的实例点恰巧是噪声，那预测就会出错

K值过大：如果K值较大，比如K取1000，那么可能把其较远的点都算进来了，会导致误差变大

在应用中，K一般取一个较小的数，通常采用交叉验证的方法选取最优k值。

距离度量：

设特征空间是n维实数向量空间，其中$x_{i}=\left \( x_{i}^{1} ,x_{i}^{2},x_{i}^{3},....,x_{i}^{n}\right$^{T}\)，$x_{j}=\left \( x_{j}^{1} ,x_{j}^{2},x_{j}^{3},....,x_{j}^{n}\right$^{T}\)

欧氏距离（空间中两点距离):

曼哈顿距离：

 p范数：

可以看出当p=2和1时，分别是欧氏距离和曼哈顿距离，一般来说最常用的为欧式距离。

通过距离度量，可以计算出实例与邻近点的距离。一般来说，当训练集很小时，可以计算训练集每个点与实例的距离，但是当训练集很大时，这时如果这样做，会非常耗时，这时需要构造kd树，通过搜索kd树，来找邻近点。