计算机视觉/人工智能之深入理解KNN算法

深入理解使用KNN算法

• • 一. KNN 是什么？
  • • KNN用于分类
    • KNN用来回归
  • 二. KNN算法要注意什么问题？
  • • K值的选择
    • 距离度量选择
  • 三. KNN的优缺点是什么？
  • 四. KNN的应用和它的场景？
  • • 1. 将数据集分割成测试数据集和训练数据集
    • 3 使用KNeighborsClassifier 对象进行fit创建出模型，得出分类准确度
    • KNN的初始函数(构造函数)的参数和默认参数是：

一. KNN 是什么？

KNN(K-Nearest Neighbor)是最简单的机器学习算法之一，可以用于分类和回归，是一种监督学习算法。它的思路是这样，如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。也就是说，该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

KNN用于分类

如上图所示，图中的正方形和三角形是打好了label的数据，分别代表不同的标签，那个绿色的圆形是我们待分类的数据。

如果选K=3，那么离绿色点最近K个点中有2个三角形和1个正方形，这3个点投票，三角形的比例占2/3，于是绿色的这个待分类点属于三角形类别。

如果选K=5，那么离绿色点最近K个点中有2个三角形和3个正方形，这5个点投票，蓝色的比例占3/5，于是绿色的这个待分类点属于正方形类别。

从上述例子看到，KNN本质是基于一种数据统计的方法，其实很多机器学习算法也是基于数据统计的。同时， KNN是一种instance-based learning，属于lazy learning， 即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，就可以直接开始分类。其中，每次判断一个未知的样本点时，就在该样本点附近找K个最近的点进行投票，这就是KNN中K的意义，通常K是不大于20的整数。

一般来说，KNN分类算法的计算过程：

1）计算待分类点与已知类别的点之间的距离

2）按照距离递增次序排序

3）选取与待分类点距离最小的K个点

4）确定前K个点所在类别的出现次数

5）返回前K个点出现次数最高的类别作为待分类点的预测分类

KNN用来回归

要预测的点的值通过求与它距离最近的K个点的值的平均值得到，这里的“距离最近”可以是欧氏距离，也可以是其他距离，具体的效果依数据而定，思路一样。如下图，x轴是一个特征，y是该特征得到的值，红色点是已知点，要预测第一个点的位置，则计算离它最近的三个点（黄色线框里的三个红点）的平均值，得出第一个绿色点，依次类推，就得到了绿色的线，可以看出，这样预测的值明显比直线准。

二. KNN算法要注意什么问题？

无论是分类还是回归，我们可以从中看出KNN算法的几个关键点：

（1）算法超参数K

（2）距离度量，特征空间中样本点的距离是样本点间相似程度的反映

（3）分类决策规则，少数服从多数。

其中，K值的选择和设置距离度量是最应该注意的几个问题。

K值的选择

作为KNN算法中唯一的一位超参数，K值的选择对最终算法的预测结果会产生直观重要的影响。

如果选择较小的K值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有输入实例较近的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻实例点非常敏感。如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，K值得减小就意味着整体模型非常复杂，容易发生过拟合。

如果选择较大的K值，就相当于用较大邻域中的训练实例进行预测，其实优点是减少学习的估计误差，但缺点是学习的近似误差会增大。这时与输入实例较远的训练实例也会起预测作用，使预测发生错误，k值的增大就意味着整体的模型变得简单，容易发生欠拟合。可以假定极端条件K=N，那么无论输入实例是什么，都将简单的预测它属于训练实例中最多的类。这时，模型过于简单，完全忽略训练中的大量有用信息，是不可取的。

在应用中，通常采用交叉验证法来选择最优K值。从上面的分析也可以知道，一般K值取得比较小。我们会选取K值在较小的范围，同时在验证集上准确率最高的那一个确定为最终的算法超参数K。

距离度量选择

样本空间中两个点之间的距离度量表示的是两个样本点之间的相似程度：距离越小，表示相似程度越高；相反，距离越大，相似程度越低。

在KNN算法中，常用的距离有三种，分别为曼哈顿距离、欧式距离和闵可夫斯基距离。为了方便下面的解释和举例，先设定我们要比较X个体和Y个体间的差异，它们都包含了N个维的特征。它们的数学描述如下

1. 闵可夫斯基距离（Minkowski distance）

闵可夫斯基距离不是一种距离，而是一类距离的定义。其数学定义如下：

其中p可以随意取值，可以是负数，也可以是正数，或是无穷大。当p=1时，又叫做曼哈顿距离，当p=2时，又叫做欧式距离，当p=∞时，又叫做契比雪夫距离。

2.欧式距离

欧式距离（L2范数）其实就是空间中两点间的距离，是我们最常用的一种距离计算公式。因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。所以在使用欧氏距离时，应该尽量将特征向量的每个分量归一化，以减少因为特征值的刻度级别不同所带来的干扰。

3.曼哈顿距离

想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Blockdistance)。

具体选用哪种距离公式，我们也将其作为其中一种参数，在后面介绍另外一种调参方法的时候所提及。

三. KNN的优缺点是什么？

优点：

1）算法简单，理论成熟，既可以用来做分类也可以用来做回归。

2）可用于非线性分类。

3）没有明显的训练过程，而是在程序开始运行时，把数据集加载到内存后，不需要进行训练，直接进行预测，所以训练时间复杂度为0。

4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合。

5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况。

缺点：

1）需要算每个测试点与训练集的距离，当训练集较大时，计算量相当大，时间复杂度高，特别是特征数量比较大的时候。

2）需要大量的内存，空间复杂度高。

3）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少），对稀有类别的预测准确度低。

4）是lazy learning方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。

注意，为了克服降低样本不平衡对预测准确度的影响，我们可以对类别进行加权，例如对样本数量多的类别用较小的权重，而对样本数量少的类别，我们使用较大的权重。 另外，作为KNN算法唯一的一个超参数K,它的设定也会算法产生重要影响。因此，为了降低K值设定的影响，可以对距离加权。为每个点的距离增加一个权重，使得距离近的点可以得到更大的权重。

4）是lazy learning方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。

注意，为了克服降低样本不平衡对预测准确度的影响，我们可以对类别进行加权，例如对样本数量多的类别用较小的权重，而对样本数量少的类别，我们使用较大的权重。 另外，作为KNN算法唯一的一个超参数K,它的设定也会算法产生重要影响。因此，为了降低K值设定的影响，可以对距离加权。为每个点的距离增加一个权重，使得距离近的点可以得到更大的权重。

四. KNN的应用和它的场景？

我们用sklearn库来看看如何使用KNN，并会简单介绍一下KNN的场景。

1. 将数据集分割成测试数据集和训练数据集

  from sklearn.model_selection import train_test_split  X_train,X_test,y_train,y_test =train_test_split(X,y)

1.创建一个KNeighborsClassifier 对象

    from sklearn.neighbors import KNeighborsClassifier    knn= KNeighborsClassifier()

3 使用KNeighborsClassifier 对象进行fit创建出模型，得出分类准确度

  knn.fit(X_train,y_train)  knn.score(X_test,y_test)4 使用我们的模型预测测试集  y_predict = knn.predict(X_test)

KNN的初始函数(构造函数)的参数和默认参数是：

  (n_neighbors=5,weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2,   metric=’minkowski’,metric_params=None, n_jobs=1, **kwargs)

它主要有以下几个参数：

[n_neighbors] 也就是K，默认参数为5。

[weights] str参数，为了降低k值的影响所设置的权重值，即每个拥有投票权的样本是按什么比重投票，'uniform’表示等比重投票，'distance’表示按距离 反比投票，[callable]表示自己定义的一个函数，这个函数接收一个距离数组，返回一个权值数组。默认参数为‘uniform’。

[algorithm] str参数，即内部采用什么数据结构实现。有以下几种选择参：‘ball_tree’:球树、‘kd_tree’:kd树、‘brute’:暴力搜索、‘auto’:自动根据数据的类型和结构选择合适的算法。默认情况下是‘auto’。暴力搜索就不用说了大家都知道。具体前两种树型数据结构哪种好视情况而定。KD树是依次对K维坐标轴，以中值切分构造的树，每一个节点是一个超矩形，在维数小于20时效率最高。ball tree 是为了克服KD树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每一个节点是一个超球体。一般低维数据用kd_tree速度快，用ball_tree相对较慢。超过20维之后的高维数据用kd_tree效果反而不佳，而ball_tree效果要好，具体构造过程及优劣势的理论大家有兴趣可以去具体学习。

[leaf_size] int参数，基于以上介绍的算法，此参数给出了kd_tree或者ball_tree叶节点规模，叶节点的不同规模会影响数的构造和搜索速度，同样会影响用于储存树的内存的大小。具体最优规模是多少视情况而定。

[matric] str或者距离度量对象，即怎样度量距离，前面有具体介绍。默认minkowski。

[p] int参数，就是以上闵氏距离各种不同的距离参数，默认为2，即欧氏距离。p=1代表曼哈顿距离等等。

[metric_params] 距离度量函数的额外关键字参数，一般不用管，默认为None。

[n_jobs] int参数，指并行计算的线程数量，默认为1表示一个线程，为-1的话表示为CPU的内核数，也可以指定为其他数量的线程，这里不是很追求速度的话不用管，需要用到的话去看看多线程。

KNN是一个特别容易理解的模型，因此，当需要一个特别容易解释的模型的时候，比如需要向用户解释原因的推荐算法，我们可以使用KNN。例如，我们可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻（长得最像的用户）买了什么产品来推荐，是一种基于电子商务和sns的精确营销，只需要定期维护更新最近邻表就可以，基于最近邻表做搜索可以很实时。