二、KNN算法详解

---

---

前言

• KNN(K-Nearest Neighbors) 是一种监督学习算法，它可以用来解决分类问题也可以用来解决回归问题。其主要思想是基于输入实例的特征空间中的“邻居”来进行预测。

---

一、KNN 算法思想

• KNN算法的核心思想是：对于一个新的、未知类别的数据点，通过比较其与已知类别训练集中的数据点的距离，找出与其最近的K个邻居
• 并依据这K个邻居的多数类别来决定新数据点的类别归属（用于分类）
• 或取这K个邻居的目标值的均值作为新数据点的预测值（用于回归）

二、实现步骤

2.1 收集数据

• 获取训练数据集，其中每个数据点都包含特征向量和对应的标签。

2.2 准备数据

• 预处理数据，如标准化/归一化特征值，确保不同特征之间的比较公平。

2.3 选择K值

• 确定K的大小，K是最近邻居的数量。

2.4 计算距离

• 对于新的输入实例，计算它与训练集中的每个点之间的距离。

2.5 找到最近的邻居

• 找到最近邻居：根据计算出的距离，找出距离最近的K个邻居。

2.6 决策

• 根据这K个邻居的信息做出决策。
• 如果是分类任务，则采用多数表决的方式决定新实例的类别
• 如果是回归任务，则可能是取这K个邻居目标值的平均或加权平均。

三、关键要素（细节）

3.1 K值的选择

• K是一个预先设定的正整数，表示在训练集中选取与待分类点最近的邻居数量。
• K值的选择对最终预测结果有显著影响，需根据具体问题和数据特性进行合理选择。
  • K值过小：容易受到异常点的影响，模型变得复杂，只要改变一点点就可能导致分类结果出错，泛化性不佳。
  • K值过大：相当于用较大的领域中的训练实例进行预测，与输入实例较远的实例也会对预测结果产生影响，模型变得简单，可能预测出错。极端情况下，当K=N（N为训练样本个数）时，结果只取决于数据集中不同类别数量占比，得到的结果一定是占比高的类别，此时模型过于简单，忽略了训练实例中大量有用信息。

3.2 距离的计算

• 距离度量用于计算样本间的相似度。

3.2.1 欧氏距离

• 欧式距离（Euclidean distance）是一个常见的用于测量两点之间距离的概念，起源于欧几里得几何。
• 

3.2.2 曼哈顿距离

• 曼哈顿距离表示两个点在标准坐标系上的绝对轴距总和。
• 

3.2.3 切比雪夫距离

• 切比雪夫距离（Chebyshev Distance）是向量空间中的一种度量方式
• 

3.2.4 闵氏距离

• 闵可夫斯基距离 Minkowski Distance 闵氏距离，不是一种新的距离的度量方式。而是距离的组合 是对多个距离度量公式的概括性的表述
• 

3.3 决策规则

• 在分类任务中，一旦找到了K个最近邻样本，就需要根据这些邻居的类别来预测未知样本的类别。
• 最常见的决策规则是多数表决法（majority voting），即未知样本的类别被赋予出现次数最多的邻居类别。
• 另一种策略是加权投票法，其中每个邻居的投票权重与其距离成反比。

四、API介绍

4.1 分类API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)

4.1.1 主要参数

• n_neighbors：int类型，默认值为5。
  • 表示k-nn算法中选取离测试数据最近的k个点。这些点的类别投票结果将决定测试数据的类别。
• weights：str、callable类型或None，默认值为’uniform’。
  • 表示k近邻点对分类结果的影响权重。
  • ‘uniform’：表示所有点的权重相等，即每个邻域中的所有点都被等权重加权。
  • ‘distance’：表示权重是距离的倒数，即距离近的点对分类结果的影响大于距离远的点。
  • callable：用户自定义函数，该函数接受一个距离数组，并返回一个形状相同的数组，其中包含权重。
• algorithm：{‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}，默认值为’auto’。
  • 用于计算最近邻的算法。
  • ‘ball_tree’：使用BallTree算法，适用于维数大于20的情况。
  • ‘kd_tree’：使用KDTree算法，原理是数据结构的二叉树，以中值为划分，每个节点是一个超矩形，适用于维数小于20的情况。
  • ‘brute’：使用暴力搜索算法，即线性扫描，当训练集很大时，计算非常耗时。
  • ‘auto’：根据传递给fit方法的值尝试确定最合适的算法。在稀疏输入上进行拟合时，将使用暴力搜索覆盖此参数的设置。
    leaf_size：int类型，默认值为30。
    传递给BallTree或KDTree的叶节点大小。这个值的设置会影响树构建和查询的速度，以及存储树所需的内存。最佳值取决于问题的性质。
• p：float类型，默认值为2。
  • Minkowski度量的幂参数。
  • 当p=1时，等价于使用曼哈顿距离（l1）。
  • 当p=2时，等价于使用欧几里德距离（l2）。
  • 对于任意的p，使用闵可夫斯基距离（lp）。
• metric：str或callable类型，默认值为’minkowski’。
  • 用于距离计算的度量标准。
  • 默认为’minkowski’，当p=2时，结果为标准欧几里德距离。
  • 如果metric是’precomputed’，则假定X是一个距离矩阵，并且在拟合期间必须是方阵。
  • 如果metric是一个可调用函数，则它接受表示1D向量的两个数组作为输入，并且必须返回一个表示这些向量之间距离的值。这适用于Scipy的度量，但比将度量名称作为字符串传递效率低下。
• metric_params：dict类型，默认值为None。
  • 度量函数的其他关键字参数。一般情况下不需要设置。
• n_jobs：int或None类型，默认值为None。
  • 用于邻居搜索的并行作业数。
  • None表示1，即不使用并行处理。
  • -1表示使用所有处理器核心进行并行处理。
  • 注意，这个参数不会影响fit方法的执行。

4.1.2 分类代码演示

代码如下（示例）：

# 1. 导包
from sklearn.neighbors import KNeighborsClassifier# 2. 创建 (分类)算法对象.
# estimator 单词的意思是 => 估量值, 评估值...
# Neighbors 单词的意思是 => 近邻(邻居)...
# estimator = KNeighborsClassifier(n_neighbors=1)  # 即: k=1, 找最近的哪个样本.
estimator = KNeighborsClassifier(n_neighbors=3)  # 即: k=1, 找最近的哪个样本.# 3. 准备 训练集数据, 即: x_train, y_train
x_train = [[0], [1], [2], [3]]
y_train = [0, 0, 1, 1]  # 分类 => 2分类# 4. 训练模型 => 机器学习.
estimator.fit(x_train, y_train)  # fitting => 拟合# 5. 模型预测(评估)
my_result = estimator.predict([[4]])# 6. 打印模型预测的结果.
print(f'预估值: {my_result}')

4.2 回归API

sklearn.neighbors.KNeighborsRegressor(n_neighbors=5)

4.2.1 主要参数

• 同 4.1.1 一样

4.2.2 回归代码演示

代码如下（示例）：

# 1.导包
from sklearn.neighbors import KNeighborsRegressor# 2.数据(特征工程)
# 分类
x = [[0,1,2],[1,2,3],[2,3,4],[3,4,5]]
y = [0.1,0.2,0.3,0.4]# 3.实例化
estimator = KNeighborsRegressor(n_neighbors=3)# 4.训练
estimator.fit(x,y)# 5.预测
print(estimator.predict([[4,4,5]]))

五、注意事项

• KNN算法简单易用，但随着数据集的增大，计算量也会增加。对于大规模数据集，可以使用 kd树(实际上是一棵二叉搜索树) 等数据结构来提高查找最近邻的效率。
• 在应用KNN之前，通常需要对数据进行标准化处理，以消除不同特征尺度的影响。
• KNN算法对数据集的不平衡问题较为敏感，因此在处理不平衡数据集时需要注意调整 K 值或使用加权投票等策略。

六、举例说明

• 6.1 收集数据
  • 假设我们有一组二维数据，代表不同类型的花朵：

特征1(花瓣长度)	特征2(花瓣宽度)	类别
1	2	A
5	4	B
1.5	7	A
6	6	B
4	1.5	A

• 6.2 选择K值
  • 假设我们选择K=3。
• 6.3 计算距离（使用欧式距离）
  • 假设我们有个新样本（花瓣长度为2，花瓣宽度为5）进行分类
  • 计算(2, 5) 到 各个点的距离
  • 到（1， 2）的距离为$\sqrt{(2-1{)}^2+(5-2{)}^2}=\sqrt{10}$
  • 到（5， 4）的距离为$\sqrt{(2-5{)}^2+(5-4{)}^2}=\sqrt{10}$
  • 到（1.5， 7）的距离为$\sqrt{(2-1.5{)}^2+(5-7{)}^2}=\sqrt{4.25}$
  • 到（6， 6）的距离为$\sqrt{(2-6{)}^2+(5-6{)}^2}=\sqrt{17}$
  • 到（4，1.5）的距离为$\sqrt{(2-4{)}^2+(5-1.5{)}^2}=\sqrt{16.25}$
• 6.4 选择邻居
  • 根据距离从小到大排序，选择最近的3个邻居
  • （1.5， 7），类别A
  • （1， 2），类别A
  • （5， 4），类别B
• 6.5 决策
  • 在这 3个邻居中，类别A出现了2次，类别B出现了1次。因此，根据多数表决法，新样本的类别被预测为A。

---

总结

• 文章首先总结了KNN的算法流程、注意事项，接下介绍了API和其中的参数，而且使用代码演示API的使用，最后使用一个实例来演示算法流程，帮助提升大家的理解。