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）的距离为 ( 2 − 1 ) 2 + ( 5 − 2 ) 2 = 10 \sqrt{(2-1)^2+(5-2)^2} = \sqrt{10} (2−1)2+(5−2)2 =10
- 到（5， 4）的距离为 ( 2 − 5 ) 2 + ( 5 − 4 ) 2 = 10 \sqrt{(2-5)^2+(5-4)^2} = \sqrt{10} (2−5)2+(5−4)2 =10
- 到（1.5， 7）的距离为 ( 2 − 1.5 ) 2 + ( 5 − 7 ) 2 = 4.25 \sqrt{(2-1.5)^2+(5-7)^2} = \sqrt{4.25} (2−1.5)2+(5−7)2 =4.25
- 到（6， 6）的距离为 ( 2 − 6 ) 2 + ( 5 − 6 ) 2 = 17 \sqrt{(2-6)^2+(5-6)^2} = \sqrt{17} (2−6)2+(5−6)2 =17
- 到（4，1.5）的距离为 ( 2 − 4 ) 2 + ( 5 − 1.5 ) 2 = 16.25 \sqrt{(2-4)^2+(5-1.5)^2} = \sqrt{16.25} (2−4)2+(5−1.5)2 =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的使用，最后使用一个实例来演示算法流程，帮助提升大家的理解。