01 KNN算法 - 概述

1. 01 KNN算法 - 概述

  KNN算法 全称是K近邻算法 （K-nearst neighbors，KNN）
   KNN是一种基本的机器学习算法，所谓K近邻，就是k个最近的邻居。即每个样本都可以用和它 最接近的k个邻近位置的样本 来代替。
   KNN是个相对比较简单的算法，比起之前提过的回归算法和分类算法更容易。如果一个人从来没有接触过机器学习的算法，拿到数据后最容易想到的分类方式就是K近邻。打个比方：你们想了解我是个怎样的人，然后你们发现我的身边关系最密切的朋友是一群逗逼，所以你们可以默认我也是一个逗逼。
   KNN算法即可以应用于 分类算法 中，也可以应用于 回归算法 中。
   KNN在做回归和分类的主要区别，在于最后做预测时候的决策不同。在分类预测时，一般采用 多数表决法 。在做回归预测时，一般使用 平均值法 。
    多数表决法： 分类时，哪些样本离我的目标样本比较近，即目标样本离哪个分类的样本更接近。
    平均值法：  预测一个样本的平均身高，观察目标样本周围的其他样本的平均身高，我们认为平均身高是目标样本的身高。
   
                                           
    再举个例子：    分别根据甜度和脆度两个特征来判断食物的种类。   根据样本我们普遍发现：   比较甜，比较脆的食物都是水果。   不甜，不太脆的食物是蛋白质。   不甜，比较脆的食物是蔬菜。   于是根据目标的样本甜度和脆度两个特征，我们可以对其进行分类了。
                                                                                    k值的选择:    先选一个较小的值，然后通过交叉验证选择一个合适的最终值。   k越小，即使用较小的领域中的样本进行预测，训练误差会减小，但模型会很复杂，以至于过拟合。   k越大，即使用交大的领域中的样本进行预测，训练误差会增大，模型会变得简单，容易导致欠拟合。
    距离的度量:    使用欧几里得距离：欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
                                            决策规划:    分类：多数表决法、加权多数表决法。   回归：平均值法、加权平均值法。
   加权多数表决法：
                                           平均值法和加权平均值法：   同样看上面的图，上方的三个样本值为3，下面两个样本值为2，预测？的值。   如果不考虑加权，直接计算平均值：   (3 * 3 + 2 * 2) / 5 = 2.6
   加权平均值：权重分别为1/7和2/7。计算加权平均值：   (3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
    1、蛮力实现(brute)：    计算预测样本到所有训练集样本的距离，然后选择最小的k个距离，即可得到k个最邻近点。   缺点：当特征数多、样本数多时，算法的效率比较低。
    2、KD树 (kd_tree)：    首先对训练数据进行建模，构建KD树，然后根据建好的模型来获取邻近样本数据。   后续内容会介绍KD树搜索最小值的方式，让大家直观感受到KD树比蛮力实现要少检索多少数据。

2. knn算法是什么？

KNN（K- Nearest Neighbor）法即K最邻近法，最初由Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。
作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。


介绍
KNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O(n)。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3. Knn算法原理

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 看下面这幅图：
                                                                                    
 KNN的算法过程是是这样的： 从上图中我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。 如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形 如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形 我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。 KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。 具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。
  
 KNN算法的实现就是取决于，未知样本和训练样本的“距离”。我们计算“距离”可以利用欧式距离算法：
                                                                                                                                                                      
 求出K个最相近的元组后，用这些元组对应的数值的平均值作为最终结果。
  
 可以从K=1开始，逐步增加，用检验数据来分析正确率，从而选择最优K。这个结果要均衡考虑正确率与计算量，比如K=3时，正确率为90%，而K=10时，正确率为91%，则需要考虑计算量换来的1%提升是否合算了。
  
 （1）如果可能的话先对样本数据进行排序，从而知道只需要与哪些数据进行比较。但对于高维数据，这几乎是不可行的。
  
 （2）将样本数据划分为多个子集合，待分类数据只需要与其中的一个或者多个子集合进行比较。比如属性是经纬度，距离是2个经纬度点之间的距离，则可以将样本根据经纬度的整数部分将各个样本分到不同的子集合去，待分类元组只需要跟与自己整数部分相同的子集合进行比较即可，当子集合内的样本数据不足K时，再和邻近的集合进行比较。
  
 （1）理论成熟，思想简单，既可以用来做分类又可以做回归
  
 （2）可以用于非线性分类
  
 （3）训练时间复杂度比支持向量机之类的算法低
  
 （4）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
  
 （5）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合
  
 （6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况
  
 （1）计算量大，尤其是特征数非常多的时候
  
 （2）样本不平衡的时候，对稀有类别的预测准确率低
  
 （3）KD树，球树之类的模型建立需要大量的内存
  
 （4）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
  
 （5）相比决策树模型，KNN模型的可解释性不强
  
 
  
  
 
  
  
 注：图片来源于：https://blog.csdn.net/wstz_5461/article/details/78018099

4. 什么叫做knn算法？

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。
在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。
1、在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。
2、在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。
最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。
K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。
无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。
邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作是此算法的一个训练样本集。
k-近邻算法的缺点是对数据的局部结构非常敏感。
K-均值算法也是流行的机器学习技术，其名称和k-近邻算法相近，但两者没有关系。数据标准化可以大大提高该算法的准确性。

参数选择
如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术（见超参数优化）来获取。
噪声和非相关性特征的存在，或特征尺度与它们的重要性不一致会使K近邻算法的准确性严重降低。对于选取和缩放特征来改善分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。
在二元（两类）分类问题中，选取k为奇数有助于避免两个分类平票的情形。在此问题下，选取最佳经验k值的方法是自助法。

5. 什么是机器学习中的knn算法

算法思路：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。看下面这幅图：
KNN的算法过程是是这样的：
从上图中我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。
如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形
我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。
KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。
具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。
再举一个例子，Locally weighted regression (LWR)也是一种 memory-based 方法，如下图所示的数据集。
用任何一条直线来模拟这个数据集都是不行的，因为这个数据集看起来不像是一条直线。但是每个局部范围内的数据点，可以认为在一条直线上。每次来了一个位置样本x，我们在X轴上以该数据样本为中心，左右各找几个点，把这几个样本点进行线性回归，算出一条局部的直线，然后把位置样本x代入这条直线，就算出了对应的y，完成了一次线性回归。也就是每次来一个数据点，都要训练一条局部直线，也即训练一次，就用一次。LWR和KNN很相似，都是为位置数据量身定制，在局部进行训练。