机器学习_KNN算法(保证写得很通俗易懂)

快来打我* 2023-06-12 08:35 50阅读 0赞

刚学完了，还是写博客记上，忘了好回头看。里面有个小问题没明白，算了，自当过几天就能搞懂吧。

## KNN算法原理 ##

**KNN(K-nearst neighbors KNN)**，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻居来代表。在现实生活中，有点\*\*“近朱者赤，近墨者黑”\*\*的意思。  
（**看完后边再回来看这个，能理解**）**KNN既可用在分类应用中，也可应用在回归应用中。不同之处在于：KNN在做分类预测时，一般采用多数表决法，做回归时采用平局值法**，这样说可能不直观，下面的例子说明，多数表决法。  
**例1：下面是一个做分类预测时的例子，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70]  
例2：  
假如不知道什么食物的情况下，我们来对这些食物进行分类。已知这些食物中每种食物都有两种属性，甜度（取值范围1-10）和脆度（取值范围1-10），按照这三个属性，把食物分成三类，水果、蔬菜和蛋白质。如下表所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 1]  
对上面的表格，以甜度**为横坐标轴，**脆度**为纵坐标轴做出二维散点图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 2]  
对水果进行分类，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 3]  
那么问题来了，再来一个西红柿，会是图中的哪个点呢？如果把西红柿放在图上，应该是下图的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 4]  
**那么它应该属于哪种食物呢？影响这个决策分类的主要啊因素有如下三个：**

1.  **K值的选择：一般选择较小的值，通过交叉验证最终选择一个合适的终值。选择K值有两种情况，太小和太大。  
    K选的太小，表示用较小的领域的样本进行预测，训练误差就会变小，模型会过复杂， 容易过拟合**。  
    **K值选太大**，表示用较大领域的样本进行预测，**训练误差会变大**，模型变得简单，容易**欠拟合**。
2.  \*\*度量：\*\*上面的西红柿到选择的样本值之间用欧氏距离计算。
3.  **决策规则：在分类模型中，主要使用多数表决法**或者**加权多数表决法**；  
    在回归模型中（**请看下面的线性回归预测讲解**），主要使用\*\*“平局值法”**或者**加权平均值法\*\*

## 什么是多数表决法和加权多数表决法 ##

**多数表决法**  
每个邻近样本的**权重**是一样的，也就是说最终预测的结果为出现**类别最多的那个类**，比如下图中蓝色问号的最  
终类别为红色；  
![在这里插入图片描述][20191101123654412.png]  
**加权多数表决法**  
每个邻近样本的权重是不一样的，一般情况下采用权重和距离成反比的方式来计算。**上图中**，假如三个红点到蓝色问号的距离是2，相应地权重就会变小。两个黄色五角星到预测样本的距离为1，但是权重会变大，最终蓝色圆圈的**最\*\*\*\*终类别是黄色五角星。**

## 那么KNN做线性回归的时候如何预测呢 ##

**在做线性回归的时候采用平均值法和加权平均值法**  
**平均值法：每个邻近的样本的权重是一样的，也就是说最终预测的结果为所有邻近样本的目标属性均值**，请看下图：  
![在这里插入图片描述][20191101124752998.png]  
蓝色问号最终的值为：(3+3+3+2+2)/5=2.6  
**加权平均值法：**  
每个邻近样本的权重是不一样的，一般情况下采用权重和距离成反比的方式来计算，也就是说在计算均值的时候进行加权操作。如下图所示，假如上面三个圈权重为3，下面两个圈权重为2，那么？就是  
![在这里插入图片描述][2019110112502175.png]  
假设上面三个点到待预测样本点的距离均为2，下面两个点到待预测样本点距离为1，**蓝色圆圈**的最终预测值为：2.43

## **算法的实现** ##

\*\*蛮力实现：\*\*计算预测样本到所有训练样本之间的距离，然后选择最小的K个距离即可得到K个最近邻点。这个方法适合小样本情况，否则执行效率极低。  
**KD树**首先构建KD树，再进行求解，样本大的时候的一种解决方案。

## KD Tree构建方式 ##

**KD树**采用从m个样本的n维特征中，分别计算n个特征取值的方差，用方差最大的第k维特征n k 作为根节点。对于这个特征，选择取值的中位数n kv 作为样本的划分点，对于小于该值的样本划分到左子树，对于大于等于该值的样本划分到右子树，对左右子树采用同样的方式找方差最大的特征作为根节点，递归即可产生KD树。构建方式如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 6]  
构建好KD树之后，就可以去预测测试集里的样本节点了。

## KD tree查找最近邻 ##

对于一个目标节点首先在KD树里面找到包含**目标节点的叶子节点**。以目标节点为圆心，以目标节点到叶子节点的样本的示例为半径，得到一个超球体，最近邻的点在超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。  
**请看下面的例子理解这段话：**  
![在这里插入图片描述][20191101193153592.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 7]  
下面这张图是做出的圆，从图中可以看出以（2,4.5）为圆心，d2为半径做出的圆。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][20191101193625595.png]  
![在这里插入图片描述][20191101193645210.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70]: /images/20230531/4f40fbe8215b4ec8810d17da498c4637.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/29ddf3e9032245f7a31f5f27cd389b8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/83880f3d7b57469a8fc599c0072dfdfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/23f77ab10259441db2d9176bc0d47d1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 4]: /images/20230531/e933d3e6ed1e468d825b6c725eef956c.png
[20191101123654412.png]: /images/20230531/6b5389df95794310a9fdc131dcabc64f.png
[20191101124752998.png]: /images/20230531/cacda61a7c8846b8843c42d29191a57b.png
[2019110112502175.png]: /images/20230531/567713dfaa4344fb83eae212951d8b32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 5]: /images/20230531/2a61bbce864b4f9fa9c342c5b4d2ef3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 6]: /images/20230531/84d3776b7ccf4d69bde016f86dc628df.png
[20191101193153592.png]: /images/20230531/c11dc09b41c74cf7a5a502007bb55b23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 7]: /images/20230531/f739c497fc024a548055a9049527fbb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNjc1NQ_size_16_color_FFFFFF_t_70 8]: /images/20230531/d4dcfdb455c94fd69ab0b6f01599c354.png
[20191101193625595.png]: /images/20230531/b8fdf43cd1b54d4397e90aff30ef1ebd.png
[20191101193645210.png]: /images/20230531/2dee94086ae54304945d51dc197c0720.png