机器学习与深度学习12-K近邻算法

前文回顾

上一篇文章地址：链接

1.K近邻算法定义

K近邻（K-Nearest Neighbors，简称KNN）算法是一种基本的机器学习算法，常用于分类和回归问题，工作原理很简单，概括为以下步骤：

• 训练阶段：在训练阶段，算法会存储所有的训练样本数据及其所属的类别或标签
• 测试阶段：在测试阶段，对于待分类或回归的样本，算法会找出与该样本最近的K个训练样本
• 分类：对于分类问题，KNN算法使用这K个最近的训练样本中最常见的类别来预测待分类样本的类别。例如，如果K=3，这三个最近的训练样本分别属于类别A、B、B，那么待分类样本将被预测为类别B
• 回归：对于回归问题，KNN算法使用这K个最近的训练样本的平均值或加权平均值来预测待回归样本的输出。例如，如果K=3，这三个最近的训练样本的目标值分别为5、6、7，那么待回归样本的输出将被预测为它们的平均值或加权平均值

2.KNN中的K值

在KNN（k-最近邻）算法中，K值代表选择最近邻居的数量。KNN算法的基本原理是，在给定一个新的样本点时，它会寻找训练集中与该样本点距离最近的K个邻居，并根据这些邻居的标签来进行分类或回归。选择合适的K值非常重要，因为它会影响KNN算法的性能和准确度。以下是一些常用的方法来选择合适的K值：

• 经验法则：根据经验法则，通常选择较小的K值可以减少噪声的影响，但也可能导致过拟合。而较大的K值可以平滑决策边界，但容易受到不相关数据的干扰。常见的K值范围通常是1到10之间
• 交叉验证：使用交叉验证来选择最佳的K值。将训练集分成K个子集，然后对每个子集进行KNN分类，计算预测准确率或其他评价指标。通过在不同的K值上进行交叉验证，选择使得模型性能最好的K值
• 考虑数据集大小：如果数据集较小，选择较小的K值通常更好，以避免过拟合。而对于较大的数据集，可以选择较大的K值
• 可视化和分析：对数据进行可视化和分析可以帮助选择合适的K值。通过尝试不同的K值并观察决策边界的变化，可以判断哪些K值能够更好地拟合数据

需要注意的是，选择适当的K值是一项经验性任务，既取决于数据集的特征，也取决于具体的应用场景。因此，在使用KNN算法时，通常需要尝试不同的K值，并评估它们的性能以选择最佳的K值

3.KNN中的距离度量

KNN算法通过计算样本之间的距离来衡量它们的相似性，进而进行分类或回归。常用的距离度量方法包括以下几种：

• 欧氏距离（Euclidean Distance）：欧氏距离是最常用的距离度量方法。对于两个样本点x和y，它们在n维特征空间中的欧氏距离可以表示为：
  $$d(x,y)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$
• 曼哈顿距离（Manhattan Distance）：曼哈顿距离也称为城市街区距离，它是两点间在各个坐标轴上绝对值差的总和。对于两个样本点x和y，它们在n维特征空间中的曼哈顿距离可以表示为：$$d(x,y)=\sum _{i=1}^n|x_i-y_i|$$
• 个样本点x和y，它们在n维特征空间中的切比雪夫距离可以表示为：
  $$d(x,y)=\underset{i=1}{\overset{n}{\max }}|x_i-y_i|$$
• 闵可夫斯基距离（Minkowski Distance）：闵可夫斯基距离是欧氏距离和曼哈顿距离的一般化形式，其中p是一个参数。对于两个样本点x和y，它们在n维特征空间中的闵可夫斯基距离可以表示为：
  $$d(x,y)={\left(\sum _{i=1}^n|x_i-y_i{|}^p\right)}^{\frac{1}{p}}$$
• 马氏距离（Mahalanobis Distance）：马氏距离考虑了变量之间的相关性，通过计算样本之间的协方差矩阵来度量它们之间的距离。马氏距离可以表示为（其中S是协方差矩阵）：
  $$d(x,y)=\sqrt{(x-y{)}^T{S}^{-1}(x-y)}$$

在KNN算法中选择合适的距离度量方法取决于数据的特点和应用场景。通常情况下，欧氏距离是最常用的距离度量方法，但如果特征具有不同的尺度或权重，可以考虑使用其他的距离度量方法。此外，有时候还可以根据领域专家的经验或通过交叉验证来选择最适合的距离度量方法

4.KNN的局限性

KNN算法虽然简单且易于实现，但也有一些局限性，它在以下情况下可能不适用：

• 高计算成本：KNN算法需要计算新样本与所有训练样本之间的距离。随着训练集的规模增加，计算成本会显著增加，尤其是在大型数据集上
• 内存消耗：KNN算法需要将所有训练样本保存在内存中以进行预测。如果训练集很大，这会占用大量的内存资源
• 数据不平衡问题：在具有不平衡类别分布的数据集上，KNN算法可能会偏向于多数类别，从而导致分类错误
• 存在噪声和异常值：KNN算法对噪声敏感，异常值可能会对最近邻的选择产生较大影响，从而导致误分类
• 维度灾难：当特征维度非常高时，KNN算法的效果可能会受到影响。高维空间中的点之间的距离会变得更加稀疏，导致KNN算法无法准确地找到最近邻居
• 参数选择：选择合适的K值对KNN算法的性能至关重要。但是，在现实问题中很难确定最佳的K值，需要进行交叉验证或其他方法来选择

总而言之，KNN算法在处理高维、大规模和不平衡数据集时可能会遇到挑战。它更适用于具有相对较小特征空间和平衡类别分布的问题。在面对上述情况时，可以考虑其他机器学习算法来取代KNN算法，比如决策树、支持向量机（SVM）或深度学习模型等

5.KNN的时空复杂度

时间复杂度

• 计算距离：对于每个测试样本，KNN算法需要计算新样本与所有训练样本之间的距离。这个步骤的时间复杂度取决于数据集的大小N和特征的数量D。具体而言，计算距离的时间复杂度为O(N * D)
• 排序：在找到最近的K个邻居后，KNN算法需要对这些邻居进行排序，以确定最终的预测。排序的时间复杂度通常为O(K * log(K))
• 预测：对于每个测试样本，预测的时间复杂度为O(1)

因此，KNN算法的总体时间复杂度约为O(N * D + K * log(K))

数据集大小的影响：随着训练集大小N的增加，计算距离的时间复杂度将线性增长。因为需要计算新样本与所有训练样本之间的距离，所以数据集越大，计算距离所需的时间就越多。数据集维度的影响：随着特征数量D的增加，计算距离的时间复杂度也会增加。在高维空间中，点与点之间的距离计算变得更加复杂，因为需要考虑更多的特征
空间复杂度
存储训练集：KNN算法需要将所有训练样本保存在内存中以供预测使用。因此，其空间复杂度等于训练集的大小乘以特征的数量，即O(N * D)。

• 数据集大小的影响：随着训练集大小N的增加，所需的存储空间也会线性增长
• 数据集维度的影响：随着特征数量D的增加，存储训练集所需的空间也会增加

需要注意的是，这里的时间复杂度和空间复杂度仅考虑了基本的KNN算法实现。实际应用中，还可能有一些优化策略，如KD树、球树等，可以减少计算距离的时间复杂度，但会增加构建数据结构的时间和空间开销。因此，在实际应用中，最好根据具体问题的规模和要求来选择适合的算法和数据结构