机器学习入门 | 【01】K近邻算法

快来打我* 2022-08-30 05:29 184阅读 0赞

### 文章目录 ###

*   *   *  1、K近邻算法【通过你的邻居来判断你的类别】
         *   *  1、简介
             *  2、电影案例分析
             *  3、api的初步使用
             *   *  3.1 一般的流程：
                 *  3.2 sklearn模块介绍
                 *  3.3 API的使用
                 *  3.4 距离度量
                 *   *  3.4.1 欧式距离【前面已提到】
                     *  3.4.2 曼哈顿距离
                     *  3.4.3 切比雪夫距离
                     *  3.4.4 闵可夫斯基距离【一组距离的定义】
                     *  3.4.5 标准欧式距离
                     *  3.4.6 余弦距离
                     *  3.4.7汉明距离
                     *  3.4.8 杰卡德距离
                     *  3.4.9 马氏距离
             *  4、k值的选择
             *  5、kd树【提高KNN搜索效率】
             *   *  5.1 原理
                 *  5.2 最近邻域搜索
                 *  5.3 构造方法
             *  6、 案例分析
             *   *  6.1 树的建立
             *  7、数据集介绍
             *   *  7.1 scikit-learn数据集API
                 *  7.2 scikit-learn大数据集
                 *  7.3 数据集返回值介绍
             *  8、数据集的划分
             *   *  8.1 划分为俩个部分
                 *  8.2 api的使用
             *  9、特征预处理
             *   *  9.1 定义
                 *  9.2 预处理API \`sklearn.preprossing\`
                 *  9.3 归一化
                 *  9.4 标准化
             *  10、交叉验证
             *   *  10.1 初步介绍
                 *  10.2 API
             *  11、总结
             *   *  11.1 优点
                 *  11.2 缺点

### 1、K近邻算法【通过你的邻居来判断你的类别】 ###

#### 1、简介 ####

> **定义**：若一个样本在特征空间中的k个`最相似(近邻)`的样本中的大多数属于一个类别，则该`样本也属于该类别`。

> **近邻的计算距离公式**：`欧式距离公式`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]

#### 2、电影案例分析 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]

> 通过k近邻计算后可得出结果，但一个结果进行对比效果较差。所以选择5对其进行判断，即`k的值`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]

#### 3、api的初步使用 ####

##### 3.1 一般的流程： #####

>  *  获取数据
>  *  数据处理
>  *  特征工程
>  *  机器学习
>  *  型评估

##### 3.2 sklearn模块介绍 #####

**安装**：`pip install scikit-learn`，前提需要有`Numpy`、`matplotlib`以及`Scipy`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]

##### 3.3 API的使用 #####

# _*_ coding:utf-8 _*_
    # @File : KNNDemo.py
    # @Author: Jxiepc
    # @Time : 2021-07-19 17:27
    from sklearn.neighbors import KNeighborsClassifier
    
    # 获取数据
    x = [[2], [4], [5], [0], [0]]
    y = [1, 1, 1, 0, 0]
    
    # 实例化训练模型
    # n_neighbors:结果与之最小的值的个数
    estimator = KNeighborsClassifier(n_neighbors=2)
    
    estimator.fit(x, y)
    
    result = estimator.predict([[0]])
    print(result)

##### 3.4 距离度量 #####

###### 3.4.1 欧式距离【前面已提到】 ######

###### 3.4.2 曼哈顿距离 ######

> 在曼哈顿街区要从一个十字路口开车到另一个十字路口， 驾驶距离显然不是两点间的直线距离。这个`实际驾驶距离就是“曼哈顿距离"`。曼哈顿距离也称为`城市街区距离`(City Block distance)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 6]

###### 3.4.3 切比雪夫距离 ######

> 国际象棋中，国王可以`直行、横行、斜行`，所以国王走一步可以移动到相邻8个方格中的任意一个。 国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?这个距离就叫`切比雪夫距离`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 8]

###### 3.4.4 闵可夫斯基距离【一组距离的定义】 ######

> 对多个距离度量公式的概括性表述。

补充

**总结**：

>  *  都存在前三个距离的缺点；
>  *  将各个分量的量纲（单位）都相同看待了；
>  *  未考虑各个分量（期望、方差）可能是不同的。

###### 3.4.5 标准欧式距离 ######

>  *  针对欧式距离的缺点进行改进；
>  *  先将各个分量都标准化到均值、方差相等

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 9]

###### 3.4.6 余弦距离 ######

> 几何中，夹角余弦可用来衡量两个`向量方向的差异`；机器学习中，借用这一概念来衡量`样本向量之间的差异`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 10]

###### 3.4.7汉明距离 ######

> 一个字符串变成另外一个字符串需要的距离。把2个向量之间的汉明距离定义为2个向量不同的分量所占百分比。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 11]

###### 3.4.8 杰卡德距离 ######

> **杰卡德相似系数**：俩个集合的`交集`在`并集`中所占的比例`J(集合1， 集合2)`。  
> **杰卡德距离**：与杰卡德相似系数相反，用俩个集合`不同的元素`与`相同元素`的所占比例。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 12]

###### 3.4.9 马氏距离 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 13]

> 基于样本分布。由哈拉诺比斯提出，表示数据的协方差距离。有效计算俩个位置样本集的相似度方法；  
> 与欧式距离不同，它考虑到各种特征之间的联系【独立于测量尺度】；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 14]

**特性**：

>  *  量纲无关，排除变量之间的相关性干扰；
>  *  该计算是建立在总体样本的基础上；
>  *  要求总体样本大于样本的维数。

#### 4、k值的选择 ####

>  *  **k值过小**：意味着整体模型变得复杂，易发生过拟合。
>  *  **k值过大**：整体的模型变简单。
>  *  在实际应用中，k值一般取较小的数值，采用交叉验证将数据划分为训练集和验证集，来选择最优的K值。

>  *  **近似误差**：（训练集）过小，造成过拟合现象。过现有数据可以很好预测，但对未知数据会有较大偏差。
>  *  **估计误差**：（测试集）对未知数据有好的预测能力。

#### 5、kd树【提高KNN搜索效率】 ####

>  *  根据`KNN`每次需要预测一个点时， 我们都需要计算训练数据集里每个`点到这个点的距离`，然后`选出距离最近的k个`点进行投票。当数据集很大时，这个计算成本非常高，针对N个样本，D个特征的数据集，其算法复杂度为`O(DN^2^)`。
>  *  kd树：为了避免每次都重新计算一遍距离，`算法会把距离信息保存在一棵树里`， 这样在计算之前从树里查询距离信息，尽量`避免重新计算`。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。时间复杂度为O(DNlogN)。

##### 5.1 原理 #####

![在这里插入图片描述][f02d2dcc121f24e0a71b41f94b958c13.png]

> 黄色点为根节点，之间的线为分割超平面。后不断的进行划分。

![在这里插入图片描述][a43ac4b170310ca67a052430178d1f4a.png]

##### 5.2 最近邻域搜索 #####

> 一种对`k维空间`中实例点进行存储以便对其进行`快速检索`的树形数据结构。构建kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而`减少搜索的计算量`。

##### 5.3 构造方法 #####

>  *  构造根结点，使根结点对应于K维空间中包含所有实例点的超矩形区域；
>  *  通过递归方法，对K维空间进行切分生成子结点；
>  *  上述过程直到子区域内没有实例时终止（该结点为叶子结点）。将实例保存到相应的结点；
>  *  且该kd树为平衡二叉树。

#### 6、 案例分析 ####

##### 6.1 树的建立 #####

>  *  将点的坐标x轴排序；
>  *  选取中间的数值将其划分；
>  *  在对每个区域逐步划分。

#### 7、数据集介绍 ####

##### 7.1 scikit-learn数据集API #####

`sklearn.datasets`：加载数据集；  
`sklearn.datasets.load_*()`：获取小规模数据集，数据包含在datasets；  
`sklearn.datasets.fetch_*(data_home=None)`：获取大规模数据集，第一个参数为下载目录。

##### 7.2 scikit-learn大数据集 #####

`sklearn,datasets.fetch_20newsgroups(data_home=None, subset='train')`

>  *  `subset`：`train、test、all`要加载的数据集，默认为`train`；

##### 7.3 数据集返回值介绍 #####

`load`和`fetch`返回的数据类型`datasets.base.Bunch【字典】`

>  *  `data`：特征数据数组，二维的`ndarray`；
>  *  `target`：标签数组，二维的`ndarray`；
>  *  `DESCR`：数据描述；
>  *  `feature_names`：特征名；
>  *  `target_names`：标签名。

获取方式可用`.属性`或者`["属性"]`

#### 8、数据集的划分 ####

##### 8.1 划分为俩个部分 #####

>  *  训练数据：用于训练，构建模型；
>  *  测试数据：检验以及评估模型。

##### 8.2 api的使用 #####

`sklearn.model_selection.train_test.split(arrays, *options)`：

>  *  x数据集的`特征值`；
>  *  y数据集的`标签纸`；
>  *  `test_size`：【`float`】测试集的大小；
>  *  `random_state`：随机种子，相同的种子采样结果相同；
>  *  `return`：测试集特征 训练集特征 训练标签 测试标签。

#### 9、特征预处理 ####

##### 9.1 定义 #####

>  *  通过一些转换函数将特征数据转化成更加合适的算法模型。
>  *  包含`归一化`，`标准化`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 15]

**为何要归一化和标准化？**

> 特征的`单位或者大小相差较大`，或者某特征的方差相比其他的特征要大出几个数量级，易影响目标结果。将特征转化在`0~1`之间。

##### 9.2 预处理API `sklearn.preprossing` #####

##### 9.3 归一化 #####

> **定义**：通过原始数据进行变换把数据映射到0~1间。

> **公式**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 16]

> **API**：`sklearn.preprossing.MinMaxScaler(feature_range=(0，1))`
> 
>  *  feature\_range：设置转换后数值的区间；
>     
>      *  `.fit_transform(X)`：X为ndarray数据类型；
>  *  返回值：转换后的相同形式的array。

**存在问题**：

> 数据中异常点较多，会受影响。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 17]

**总结**：

> 方法`鲁棒性【稳定性】较差`，只适合传统精确小数据场景。

##### 9.4 标准化 #####

> **定义**：通过原始数据进行变换把数据变换到`均值0，标准差为1`范围内。

> **异常点优化**：若有异常点，且有一定的数据量，少量异常点对于`平均值的影响并不大，从而方差改变较小`。

> **API**：`sklearn.preprossing.StandarScaler()`
> 
>  *  处理后每列来说所有数据都聚集在均值0附近标准差差为1；
>  *  `fit_trainsform(X)`：X为ndarray类型；
>  *  返回值：转换后的相同形式的array。

**总结**

>  *  异常值影响较小；
>  *  适合现代嘈杂大数据场景。

#### 10、交叉验证 ####

##### 10.1 初步介绍 #####

>  *  分割方式：
>     
>      *  训练集：训练集、验证集；
>      *  测试集：测试集。
>  *  为了让被评估的模型更加准确；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 18]

##### 10.2 API #####

`sklearn.model_selection.GridSearchCV(estimator, param_gid=None, cv=None)`：对估计器的指定参数值进行详尽搜索；

>  *  `estimator`：估计器对象；
>  *  `param_grid`：`{"n_neighbors": [1, 3, 5...]}`；
>  *  `cv`：指定几折交叉验证；
>  *  `fit`：输入训练数据；
>  *  `score`：准确率；
>  *  结果分析：
>     
>      *  `bestscore_`：交叉验证中的最好结果；
>      *  `bestestmator`：最好的参数模型；
>      *  `cvresult`：每次交叉验证后的验证集准确率结果和训练准确率即通过。

#### 11、总结 ####

##### 11.1 优点 #####

>  *  简单有效；
>  *  重新训练的代价低；
>  *  适合类域交叉样本；
>  *  适合大样本自动分类。

##### 11.2 缺点 #####

>  *  惰性学习；
>  *  类别评分不是规格化；
>  *  输出可解释性不强；
>  *  对不均衡的样本不擅长；
>  *  计算量较大。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70]: /images/20220829/17223ff3a9b54705b14ded4aeb7fb0b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 1]: /images/20220829/dd9eb6ede8554321aab9c8da51fb2970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 2]: /images/20220829/0e9997a2a83042b4bc42ec889752f449.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 3]: /images/20220829/136e7c66c9904a838f50f762cc694459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 4]: /images/20220829/37c5c1915e9f4d4abfbbb4a290da32da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 5]: /images/20220829/67b3371b0e45437492f7575b40e6bcf2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 6]: /images/20220829/072b737779f046368911afe306d9cbde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 7]: /images/20220829/f83f21d1bfb54e7e969cc9beb34c9100.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 8]: /images/20220829/10f2e870d8174fc184083178308291b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 9]: /images/20220829/bc1d273f332f48f6a6141743e0627e2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 10]: /images/20220829/058022eb7f0f46e291c9f0b3937c9729.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 11]: /images/20220829/3ab90bbe1a2748d1bc4b3a2613e1a166.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 12]: /images/20220829/d3c57ba068da40399a87eec7654f4a02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 13]: /images/20220829/fdc99dc4eb7343aa84cddeea9c960343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 14]: /images/20220829/a7adfac575e746b092da1a8b6f9190b9.png
[f02d2dcc121f24e0a71b41f94b958c13.png]: /images/20220829/8bcf1a7a632b4d6c81e9f262b0a99c47.png
[a43ac4b170310ca67a052430178d1f4a.png]: /images/20220829/241f51db872c4722887bcde2ffa84c4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 15]: /images/20220829/3f0f97ffe1ff45bc883fc11e2cf092fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 16]: /images/20220829/c4c2be98a82b4df9967bc993d2939114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 17]: /images/20220829/ad322eb06cd54a10bfc92afa1c650b16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkyNjU0Nw_size_16_color_FFFFFF_t_70 18]: /images/20220829/cbbf714ac1a64d0889c94c79e41558cd.png