【Python-AI篇】K近邻算法(KNN)

0. 前置----机器学习流程

1. 获取数据集
2. 数据基本处理
3. 特征工程
4. 机器学习
5. 模型评估
6. 在线服务

1. KNN算法概念

如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中大多数属于某一个类别，则该样本也属于这一个类别

1.1 KNN算法流程总结

1. 计算已知类别数据集中的点与当前点之间的距离
2. 按距离递增次序排序
3. 选取与当前点距离最小的k个点
4. 统计前k个点所在的类别出现的频率
5. 返回前k个点出现频率最高的类别作为当前点的预测分类

2. KNN算法api ---- Scikit-learn

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, algorithm='auto')

参数含义：

1. n_neighbors： 查询默认使用的邻居数，默认为5
2. algorithm：
   1. 快速K近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法，除此之外，用户也可以自己指定搜索算法进行搜索
   2. bruth： 蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时
   3. kd_tree： 构造kd树存储数据以便对其进行快速搜索的树形数据结构，kd树也就是数据结构
   4. ball_tree： 为了克服kd树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体

简单示例：

from sklearn.neighbors import KNeighborsClassifier# 构造数据集
x = [[0], [1], [2], [3]]  # 特征
y = [0, 0, 1, 1]          # 标签# 实例化 KNN 分类器
estimator = KNeighborsClassifier(n_neighbors=2)# 使用 fit 方法进行训练
estimator.fit(x, y)# 数据预测
ret = estimator.predict([[10]])  # 输入一个新的特征
print(ret)

详细解释：

1. 训练数据
   x 是特征向量，y 是对应的标签：
   x[0] = [0] 对应 y[0] = 0
   x[1] = [1] 对应 y[1] = 0
   x[2] = [2] 对应 y[2] = 1
   x[3] = [3] 对应 y[3] = 1
2. 使用训练数据进行拟合
   estimator.fit(x, y) 训练模型后，它将 KNN 分类器的内部数据结构用训练数据（x 和 y）初始化，并准备进行预测。
3. 当输入特征 [[10]] 进行预测时，KNN 会执行以下操作：
   （1）计算距离：计算 10 与训练集中每个点的距离（使用欧几里得距离作为默认度量）：
   距离到 0 是 10 - 0 = 10
   距离到 1 是 10 - 1 = 9
   距离到 2 是 10 - 2 = 8
   距离到 3 是 10 - 3 = 7
   由于 10 远离了所有训练样本，因此它与所有训练样本间的距离都非常大。
   （2）选择 K 个最近邻：因为设置了 n_neighbors=2，KNN 会选择最近的 2 个邻居。在这种情况下，它将选择距离和标签如下的最近的两个样本：
   x[3] = [3]， y[3] = 1（距离第三小）
   x[2] = [2]， y[2] = 1（距离第四小）
   （3）投票决定输出：在仅考虑 2 个邻居的情况下，两个邻居的标签均为 1。因此，投票结果显示 1 是最多的，因此预测 ret 为 1。

3. 距离度量

3.1 距离公式

1. 欧式距离：
   1. 二维空间距离：d₁₂ = $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$
   2. 三维空间距离：d₁₂ = $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$
   3. n维空间的距离：d₁₂ = $\sqrt{\sum _{k=1}^n(x_{1k}-x_{2k}{)}^2}$
2. 曼哈顿距离：
   1. 二维平面上的两点距离：d₁₂ = $\mid x_1-x_2\mid$ + $\mid y_1-y_2\mid$
   2. n维空间的两点距离：d₁₂ = $\sum _{k=1}^n\mid x_{1k}-x_{2k}\mid$
3. 切比雪夫距离：
   1. 二维平面上两点距离：d₁₂ = max($\mid x_1-x_2\mid$, $\mid y_1-y_2\mid$)
   2. n维空间上两点距离：d₁₂ = max($\mid x_{1i}-x_{2i}\mid$)
4. 闵可夫斯基距离：
   1. n维变量间的闵可夫斯基距离为：d₁₂ = $\sqrt[p]{\sum _{k=1}^n\mid x_{1k}-x_{2k}{\mid }^p}$
   2. 其中p是一个可变参数
      1. p=1，就是曼哈顿距离
      2. p=2，就是欧式距离
      3. p $\to \infty$，就是切比雪夫距离

3.2 其他距离公式

3.2.1 标准化欧式距离

1. 针对欧式距离的改进
2. 数据各维度分量分布不一样，先将各个分量标准化到均值，方差相等
3. 标准化欧式距离公式：d₁₂ = $\sqrt{\sum _{k=1}^n(\frac{x_{1k}-x_{2k}}{S_k}{)}^2}$
4. 如果将方差的倒数看成一个权重，也可称之为加权欧式距离

3.2.2 余弦距离

1. 几何中，夹角余弦可以用来衡量两个方向上的差异，机器学习中，借用这一概念来衡量样本向量之间的差异
2. 二维空间中向量A(x₁, y₁)与向量B(x₂, y₂)的夹角余弦公式：$\cos \theta =\frac{x_1{x}_2+y_1{y}_2}{\sqrt{x_1^2+y_1^2}+\sqrt{x_2^2+y_2^2}}$
3. 两个n维样本点a(x₁₁, x₁₂,… ,x_1n)和b(y₂₁, y₂₂,… ,y_2n)的夹角余弦为：$\cos (\theta )=\frac{a\cdot b}{\mid a\mid \mid b\mid }$
   即：$\cos (\theta )=\frac{\sum _{k=1}^n{x}_{1k}{x}_{2k}}{\sqrt{\sum _{k=1}^n{x}_{1k}^2}\sqrt{\sum _{k=1}^n{x}_{2k}^2}}$
4. 夹角的余弦范围为[-1, 1]，余弦越大表示两个向量的夹角越小，余弦越小表示两个向量的夹角越大，当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反余弦取最小值-1

3.2.3 汉明距离

两个等长字符串s1与s2的汉明距离为：将其中一个变换成另一个所需要做的最小字符替换次数

3.2.4 杰卡德距离

1. 杰卡德相似系数：两个集合A和B的交集元素在A,B并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示：$J(A,B)=\frac{\mid A\cap B\mid }{\mid A\cup B\mid }$
2. 杰卡德距离：$J_{\delta }(A,B)=1-J(A,B)=\frac{\mid A\cup B\mid -\mid A\cap B\mid }{\mid A\cup B\mid }$

3.2.5 马氏距离

1. 基于样本分布的一个距离，表示数据协方差距离，有效计算两个位置样本集的相似度方法
2. 马氏距离定义： 设总体G为m维总体(考察m个指标)，均值向量为$\mu =({\mu }_1,{\mu }_2,...,{\mu }_m)$，协方差阵为：$\sum =({\sigma }_{ij})$
   则样本x = ($x_1,x_2,...,x_m$)与总体G的马氏距离定义为：$d^2(X,G)=(X-\mu {)}^{\prime }{\sum }^{-1}(X-\mu )$
   当m=1时，$d^2(x,G)=\frac{(x-\mu {)}^{\prime }(x-\mu )}{{\sigma }^2}=\frac{(x-\mu {)}^2}{{\sigma }^2}$

4. KNN算法中k值如何选择

4.1 K值影响

1. K值过小：容易受到异常点影响
2. K值过大：受样本均衡问题

4.2 两个概念

1. 近似误差：
   1. 对现有训练集的训练误差，关注训练集
   2. 近似误差过小可能会出现过拟合情况，对现有训练集能有很好的预测，但是对未知测试样本将会出现比较大的偏差
   3. 模型本身不是接近最佳模型
2. 估计误差：
   1. 对测试集的测试误差，关注测试集
   2. 估计误差小说明对未知数据预测能力好
   3. 模型本身是接近最佳模型

5. kd树

1. 树的建立
2. 最近邻域搜索：
   kd树是一种对k维空间中的实例点进行存储以便对其快速检索的树形数据结构，kd树是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断的用垂直于坐标的超平面将k维空间切割构成一系列k维超矩形区域，kd树的每一个节点对应一个k维超矩形区域，利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量

5.1 构造方法

1. 构造根节点，使根节点对应于K维空间包含所有实例节点的超矩形区域
2. 通过递归的方法，不断的对k维空间进行划分，生成子节点
3. 上述过程直到子区域没有实例为止（终止时的节点为叶节点）
4. 循环的选择坐标对空间切分，选择训练实例点在坐标轴上中位数为切分点，这样得到的kd树是平衡的

6. scikit-learn数据集API的介绍

6.1 调用参数

• sklearn.datasets
  • 加载获取流行的数据集
  • datasets.load*()
    • 获取小规模数据集，数据包含在datasets里
  • datasets.fetch_*(data_home=None)
    • 获取大规模数据集，需要从网络上下载，函数的第一个参数是data_home，表示数据下载的目录

6.2 sklearn数据集返回值

• 返回的是datasets.base.Bunch(字典格式)
  • data： 特征数据数组，是[n_samples * n_features]的二维numpy.ndarray数组
  • target： 标签数组，是n_samples的一维numpy.ndarray数组
  • DESCR： 数据描述
  • feature_names： 特征名，新闻数据，手写数字，回归数据集
  • target_names： 标签名

from sklearn.datasets import load_irisiris = load_iris()# 特征值
# print(iris.data)
# 目标值
# print(iris.target)
# 特征值名字
print(iris.feature_names)
# 目标值名字
print(iris.target_names)
# 描述
# print(iris.DESCR)

6.3 数据可视化

import seaborn as sns
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets import load_irisiris = load_iris()
# 把数据转化成dataFrame格式
iris_d = pd.DataFrame(iris['data'], columns=['Sepal_Length', 'Sepal_Width', 'Petal_Length', 'Petal_Width'])
iris_d['Species'] = iris.targetdef plot_iris(iris_d, col1, col2):sns.lmplot(x=col1, y=col2, data=iris_d, hue='Species', fit_reg=False)# 设置字体plt.rcParams['font.sans-serif'] = ['SimHei']plt.xlabel(col1)plt.ylabel(col2)plt.title('鸢尾花分布图')plt.savefig('./pic.png', dpi=100)plt.show()plot_iris(iris_d, 'Petal_Length', 'Sepal_Length')

6.4 数据集划分

sklearn.model_selection.train_test_split(arrays, *options)

• 参数
  • x： 数据的特征值
  • y： 数据的标签值
  • test_size： 测试集的大小，一般为float
  • random_state： 随机数种子，不同种子会造成不同的随机采样结果，相同种子采样结果相同
• return
  • x_train x_test y_train y_test： 特征值的训练集、测试集，目标值的训练集、测试集

# -*- coding: utf-8 -*-            
# @Time: 2024/11/3 20:13
# @File: 数据集的划分.py
# @Author: xujie.qu
# @Des:
import pandas as pd
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_splitiris = load_iris()
# 把数据转化成dataFrame格式
iris_d = pd.DataFrame(iris['data'], columns=['Sepal_Length', 'Sepal_Width', 'Petal_Length', 'Petal_Width'])
iris_d['Species'] = iris.target
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)
print("训练集的特征值是：\n",x_train)
print("训练集的目标值是：\n", y_train)
print("测试集的特征值是：\n",x_test)
print("测试集的目标值是：\n", y_test)

7. 特征值

7.1 特征预处理

7.1.1 定义

通过一些转换函数将特征数据转换成更加适合算法模型的特征数据过程

7.1.2 原因

特征的单位或者大小相差较大，或者某特征的方差相比其他的特征要大出几个数量级，容易影响或支配目标结果，使得一些算法无法学习到其他特征

7.2 归一化和标准化

7.2.1 归一化

7.2.1.1 定义

通过对原始数据进行变化把数据映射到[0,1]之间

7.2.1.2 公式

$X^{\prime }=\frac{x-min}{max-min}$
$X^{\prime \prime }=X^{\prime }\ast (mx-mi)+mi$

7.2.1.3 API

sklearn.preprocessing.MinMaxScaler(feature_range=(0, 1)...)

• MinMaxScaler.fit_transform(X)
  • X： numpy array格式化数据[n_namespaces, n_features]
• 返回值
  • 转换后的形状相同的array

7.2.1.4 数据计算

from sklearn.preprocessing import MinMaxScaler
import pandas as pddef minmax_demo():data = pd.read_csv('dating.txt')print('归化前：\n',data)# 实例化一个转换器transfer = MinMaxScaler(feature_range=(0, 1))# 调用fit_transformdata = transfer.fit_transform(data[['milage','Liters','Consumtime']])print('处理结果：\n',data)return Noneminmax_demo()

7.2.1.5 缺点

最大值最小值是变化的，非常容易受到异常点的影响，鲁棒性较差，只适合传统精确小数据场景

7.2.2 标准化

7.2.2.1 定义

通过对原始数据进行变换把数据变换到均值为0，标准差为1的范围内

7.2.2.2 公式

$X^{\prime }=\frac{x-mean}{\sigma }$

7.2.2.3 API

sklearn.preprocessing.StandardScaler()

• 处理之后每列来说所有数据都聚集在均值0附近标准差差为1
• sklearn.preprocessing.StandardScaler.fit_transform(X)
  • X： numpy array格式化数据[n_namespaces, n_features]
• 返回值
  • 转换后的形状相同的array

7.2.2.4 数据计算

from sklearn.preprocessing import StandardScaler
import pandas as pddef stand_demo():data = pd.read_csv('dating.txt')# 实例化一个转换器类transfer = StandardScaler()# 调用fit_transformdata = transfer.fit_transform(data[['milage','Liters','Consumtime']])print('处理结果：\n', data)print('每一列特征值的平均值：\n', transfer.mean_)print('每一列特征值的方差：\n', transfer.var_)return Nonestand_demo()

8. 案例

1. 鸢尾花案例

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
# 1. 获取数据
iris = load_iris()# 2. 数据基本处理
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2, random_state=22)# 3. 特征工程 - 特征预处理
transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)# 4. 机器学习KNN
# 1. 实例化一个估计器
estimator = KNeighborsClassifier(n_neighbors=5)# 使用估计器进行模型训练
estimator.fit(x_train, y_train)# 5. 模型评估
# 1. 预测值结果输出
y_pre = estimator.predict(x_test)
print("预测值是：\n", y_pre)
print("预测值和真实值对比：\n", y_pre == y_test)# 2. 准确率计算
score = estimator.score(x_test, y_test)
print("准确率是：\n", score)

9. 交叉验证&网格搜索

9.1 交叉验证定义

1. 将拿到的训练数据，分为训练集和测试集，例：将数据分为4份，其中一份作为验证集，然后经过4次测试，每次都更换不同的验证集，即得到4组模型的结果，取平均值作为最终的结果
2. 为了让被评估的模型更加准确可信

9.2 网格搜索定义

1. 超参数：需要手动指定的参数(KNN中的K值)
2. 手动过程繁杂，需要对模型预设几种超参数组合，每组超参数都采用交叉验证来进行评估，最后选出最优参数组合建立模型

9.3 模型选择与调优API

sklearn.model_selection.GridSearchCV(estimator, param_grid=None, cv=None)

• 对估计器的指定参数进行详尽搜索
• estimator： 估计器对象
• param_grid： 估计器参数(dict)
• cv： 指定几折交叉验证
• fit： 输入训练数据
• score： 准确率
• 结果分析
  • bestscore_： 在交叉验证中验证的最好结果
  • bestestimator： 最好的参数模型
  • cvesults： 每次交叉验证后的验证集准确率结果和训练集准确率结果