机器学习笔记——KNN（K-Nearest Neighbors，K 近邻算法）

本笔记介绍机器学习中的 KNN（K-Nearest Neighbors，K 近邻算法）

文章目录

• 思想
• 工作原理
• K 值选择
• • 交叉验证
  • 类似K-means的肘部法
  • 经验选择法/奇数优先
  • 加权 KNN
• 距离度量
• • 欧氏距离（Euclidean Distance）
  • • 特点
  • 曼哈顿距离（Manhattan Distance）
  • • 特点
  • 切比雪夫距离（Chebyshev Distance）
  • • 特点
  • 闵可夫斯基距离（Minkowski Distance）
  • • 特点
  • 余弦相似度（Cosine Similarity）
  • • 特点
  • 总结
• 维度灾难
• • 1. 降维技术
  • • 主成分分析（PCA, Principal Component Analysis）
    • 线性判别分析（LDA, Linear Discriminant Analysis）
    • T-SNE（t-Distributed Stochastic Neighbor Embedding）
  • 2. 特征选择（Feature Selection）
  • • 过滤法（Filter Methods）
    • 包裹法（Wrapper Methods）
    • 嵌入法（Embedded Methods）
  • 3. 使用合适的距离度量
  • • 马氏距离（Mahalanobis Distance）
    • 余弦相似度（Cosine Similarity）
• 数据结构来加速最近邻搜索
• • KD 树与 Ball 树的比较
  • KD 树（KD-Tree）
  • • 工作原理
    • 特点
  • Ball 树（Ball Tree）
  • • 工作原理
    • 特点
• KNN优缺点
• 历史文章

思想

KNN（K-Nearest Neighbors，K 近邻算法）是一种基于实例的监督学习算法，广泛应用于分类和回归任务中。它的主要思想是：对于给定的样本点，找到其在特征空间中距离最近的 K 个训练样本，并以这些最近邻的样本的类别或数值来预测该样本的类别或数值。

工作原理

1. 计算距离：计算待分类的样本点与所有训练样本点之间的距离。
2. 选择 K 个最近邻样本：根据计算出的距离，从训练集中选择 K 个距离最近的样本点。
3. 投票或平均：
   • 对于分类任务，选择这K 个样本中出现次数最多的类别作为预测结果。
   • 对于回归任务，取这 K 个样本的平均值作为预测结果。

K 值选择

• K 值是 KNN 算法中的一个超参数，表示选择的邻居数量。K 值的选择非常关键：
  • 如果 K 值过小（如 K=1），模型可能会过拟合，对噪声数据过于敏感。
  • 如果 K 值过大，模型可能会欠拟合，因为更多的邻居可能会包含不同类别的样本，从而影响分类结果。

交叉验证

• 交叉验证是选择合适 K 值的常用方法。通过交叉验证，我们可以尝试多个不同的 K 值，并通过在验证集上的表现（如准确率、F1分数等）来选择表现最好的 K 值。

• 步骤：
  1. 将训练数据集划分为若干个子集（如 5 折或 10 折交叉验证），每次取其中一个子集作为验证集，剩下的 ( k-1 ) 个子集作为训练集。。
  2. 对于每个候选 K 值，进行 KNN 训练并计算验证集上的预测性能（例如准确率）。
  3. 选择在交叉验证中性能最佳的 K 值作为最终模型的参数。

类似K-means的肘部法

• 在某些情况下，可以绘制不同 K 值下模型的误差曲线或分类错误率曲线，观察曲线的趋势。当误差随着 K 值减小而急剧下降，然后趋于平缓时，那个转折点（类似“肘部”）的 K 值就是理想的选择。

误差曲线或分类错误率曲线：

• X 轴 表示 K 值（即最近邻的个数）
• Y 轴 表示 模型的误差值/分类错误率

本质上也是使用类似交叉验证，多个K值验证最好的是哪个值

• 步骤：
  1. 选择不同的 K 值，计算每个 K 值下的测试误差。
  2. 绘制误差随着 K 值变化的曲线。
  3. 找到误差曲线的拐点，即误差下降速度变缓的地方（通常 K 值稍小的点）。

经验选择法/奇数优先

• 在很多情况下，K 值的选择可以通过经验来做出初步估计，通常选取较小的奇数值，如 ( K=3, 5, 7 )。这样做的目的是避免平票的情况（即 KNN 中相同数量的邻居属于不同类别）。

• 对于大多数分类任务，K 值的初始范围通常是：
  - 小规模数据集：K=3、K=5 或 K=7 常常是一个不错的起点。
  - 大规模数据集：可以选择较大的 K 值，具体取决于数据集的规模和类别分布。

加权 KNN

• 对距离的样本希望赋予不同的权重，可以使用加权 KNN。在加权 KNN 中，距离样本越近的邻居会赋予更高的权重，常见的权重分配方式是反比例加权：

$$\text{Weight}(x_i)=\frac{1}{d(x_i,x)}$$

这种方式在 K 值较大时，能够有效增强模型对近邻样本的关注，避免远离的噪声样本影响分类结果。

距离度量

欧氏距离（Euclidean Distance）

欧氏距离是最常用的距离度量方式，用于度量两个点在 n 维空间中的直线距离。它是两个点之间的“直线”距离，表示为：
$$d(x,y)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$
其中：

• $x$ 和 $y$ 表示两个样本点。
• $x_i$ 和 $y_i$ 分别是样本 $x$ 和 $y$ 在第 $i$ 个特征上的取值。
• $n$ 是特征的维度数。

特点

• 适合度量连续数据的距离。
• 受数据量纲影响较大，不适用于不同量纲的数据比较。

量纲是（如重量、温度、距离等），可以使用特征缩放（归一化和标准化），减少特征之间的量纲差异。

曼哈顿距离（Manhattan Distance）

曼哈顿距离也称为L1 距离或城市街区距离 ，它是两个点在 n 维空间中各维度之差的绝对值之和。表示为：

$$d(x,y)=\sum _{i=1}^n|x_i-y_i|$$
其中：

• $x$ 和 $y$ 表示两个样本点。
• $x_i$ 和 $y_i$ 分别是样本 $x$ 和 $y$ 在第 $i$ 个特征上的取值。
• $n$ 是特征的维度数。

特点

• 适用于离散数据和分布不均匀的数据。
• 更加鲁棒，适用于高维空间中。

切比雪夫距离（Chebyshev Distance）

切比雪夫距离表示在所有维度上最大的差距，即两个向量在每个坐标维度上最大距离的最小值。其公式为：

$$d(x,y)=\underset{i}{\max }|x_i-y_i|$$
其中：

• $x$ 和 $y$ 表示两个样本点。
• $x_i$ 和 $y_i$ 分别是样本 $x$ 和 $y$ 在第 $i$ 个特征上的取值。

特点

• 适用于棋盘格状的空间度量，例如国际象棋中的国王步数。
• 衡量所有维度中最大的距离，适用于某一维度差距明显的情况。

闵可夫斯基距离（Minkowski Distance）

闵可夫斯基距离是欧氏距离和曼哈顿距离的广义形式，它引入了一个参数 ( p )，用于控制距离的度量方式。其公式为：

$$d(x,y)={\left(\sum _{i=1}^n|x_i-y_i{|}^p\right)}^{\frac{1}{p}}$$

其中：

• $x$ 和 $y$ 表示两个样本点。
• $x_i$ 和 $y_i$ 分别是样本 $x$ 和 $y$ 在第 $i$ 个特征上的取值。
• $n$ 是特征的维度数。
• $p$ 是一个可调参数，常见的取值为 1（曼哈顿距离）和 2（欧氏距离）。

特点

• 适用于不同 $p$ 值下的多种度量方式。
• 参数 $p$ 的选择决定了距离的特性。

余弦相似度（Cosine Similarity）

• 余弦相似度是用来度量两个向量在空间中的夹角，用于判断两个向量之间的方向差异。它适用于高维稀疏数据，例如文本分类问题。
• 值越接近 1，说明两个向量越相似；值为 0 表示两者垂直无相似性。

$$\text{Cosine Similarity}(x,y)=\frac{x\cdot y}{\Vert x\Vert \Vert y\Vert }=\frac{{\sum }_{i=1}^n{x}_i{y}_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2}\sqrt{{\sum }_{i=1}^n{y}_i^2}}$$

其中：

• $x\cdot y$ 是向量 $x$ 和 $y$ 的点积。
• $\Vert x\Vert$ 和 $\Vert y\Vert$ 分别是两个向量的范数。
• $x_i$ 和 $y_i$ 是向量 $x$ 和 $y$ 在第 $i$ 个维度上的分量。

特点

• 基于高维稀疏数据的应用中，常用于度量文本之间的相似性。如文本分类、文档相似度、推荐系统等

总结

以下是 欧氏距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离 和 余弦相似度 在 KNN 中的原理、优点和适应场景的对比表格：

欧氏距离、曼哈顿距离、切比雪夫距离 和 闵可夫斯基距离 在低维空间中都可以很好地使用，具体适合场景如下：

• 欧氏距离：适合物理空间中的几何距离，如二维或三维空间的点距离。
• 曼哈顿距离：适合具有正交结构的路径距离，如城市街区或简单的网格路径。适用于高维空间中
• 切比雪夫距离：适合棋盘路径或二维网格中的最大步数距离问题。
• 闵可夫斯基距离：通过调整参数 ( p )，可以模拟欧氏或曼哈顿距离，适合不同的场景。适用于高维空间中
• 余弦相似度：特别适合高维稀疏数据，如文本相似度计算。

维度灾难

维度灾难（Curse of Dimensionality） 是指当数据的维度增高时，传统的机器学习算法在高维空间中的表现急剧下降，主要原因是距离度量、数据稀疏性以及模型复杂度在高维空间中变得难以处理。常见的表现包括：

1. 距离趋于相同：在高维空间中，不同数据点之间的距离差异会减小，距离度量如欧氏距离、曼哈顿距离等在高维空间中失去分辨能力。
2. 数据稀疏性：高维数据空间变得稀疏，大部分数据点远离彼此，导致模型难以找到有效的模式。
3. 模型复杂度增加：随着维度增加，模型需要更多的样本来学习有效的决策边界，否则容易出现过拟合或欠拟合。

维度灾难是高维数据中的常见问题，解决这一问题的主要方法有：

• 降维技术（如 PCA、LDA、T-SNE、UMAP）。
• 特征选择（如过滤法、包裹法、嵌入法）。
• 合适的距离度量（如马氏距离、余弦相似度）。
• 正则化技术（L1、L2 正则化、Elastic Net）。
• 核方法来处理非线性问题。

根据具体的应用场景和数据类型，选择合适的技术和方法，可以有效应对维度灾难，提高模型在高维数据下的性能。

1. 降维技术

通过降维，减少数据的维度，从而使模型更加有效地处理数据。常见的降维方法有：

维度通常指的是特征数量

主成分分析（PCA, Principal Component Analysis）

• PCA 是通过线性变换将高维数据投影到低维空间，保持投影方向上的方差最大化，进行无监督的降维方法。。
• 它适用于具有线性关系的数据集，在保留数据主要信息的同时降低维度。
• 适用场景：当特征之间具有一定的线性相关性，且希望减少数据的维度时使用。

线性判别分析（LDA, Linear Discriminant Analysis）

• LDA 通过最大化类间方差与最小化类内方差，寻找最有助于分类的低维子空间。
• 适用于有监督学习中的分类问题。
• 适用场景：适用于分类任务中，特征与类别标签存在一定关联。

T-SNE（t-Distributed Stochastic Neighbor Embedding）

• T-SNE通过在高维和低维空间中分别计算点对之间的相似度，然后最小化两个分布之间的差异 ，使相似数据点在低维空间中靠近。将高维数据映射到二维或三维空间中。
• 适用场景：数据可视化，尤其是高维数据集的降维以便于观察聚类或分类结构。

详细参考：机器学习——降维

2. 特征选择（Feature Selection）

特征选择是通过选择与目标变量相关的特征，去掉那些不相关或冗余的特征，从而降低维度。常用的方法有：

过滤法（Filter Methods）

• 根据特定的统计指标（如方差、卡方检验、互信息等）对每个特征进行评分，并选择得分较高的特征。
• 适用场景：适合大规模数据集的初步特征筛选。

包裹法（Wrapper Methods）

• 使用模型性能评估特征子集的表现，逐步添加或删除特征以找到最佳特征组合。常见方法包括递归特征消除（RFE）。
• 适用场景：特征数量不多时，找到最优的特征组合。

嵌入法（Embedded Methods）

• 特征选择直接嵌入模型的训练过程，例如 Lasso 回归（L1 正则化）会自动选择重要特征，树模型（如随机森林）可以给出特征重要性。
• 适用场景：结合模型的特征选择，可以自动识别出对模型影响较大的特征。

详细参考：机器学习——特征工程、正则化、强化学习

3. 使用合适的距离度量

在高维空间中，某些距离度量失效（如欧氏距离），可以选择更加适合高维数据的距离度量：

马氏距离（Mahalanobis Distance）

马氏距离通过协方差矩阵对不同特征进行归一化，因此能够处理具有不同尺度和相关性的特征，并衡量样本在数据分布中的“相似性”。

$$d(x,y)=\sqrt{(x-y{)}^T{\Sigma }^{-1}(x-y)}$$

其中：

• $x$ 和 $y$：是两个样本点的特征向量。
• $\Sigma$：是样本数据的协方差矩阵。
• ${\Sigma }^{-1}$：是协方差矩阵的逆矩阵。
• $(x-y{)}^T{\Sigma }^{-1}(x-y)$：是经过协方差矩阵标准化后的二次型。

协方差矩阵计算：$$\Sigma =\frac{1}{N-1}\sum _{i=1}^N(x_i-\mu )(x_i-\mu {)}^T$$

其中：

• $N$ 是样本的数量。
• $x_i$ 是第 $k$ 个样本（一个 $n$ 维向量）。
• $\mu$ 是特征均值向量（一个 $n$ 维向量），其中每个元素表示对应特征的均值。

特征均值向量计算：$$\mu =\frac{1}{N}\sum _{i=1}^N{x}_i$$

其中：

• $N$ 是样本的总数量。
• $x_i$ 是第 $i$ 个样本的特征向量，也是一个 $n$ 维向量。

适用场景：高维数据、特征存在相关性时，度量数据点与中心点的距离。

余弦相似度（Cosine Similarity）

同上

数据结构来加速最近邻搜索

KD 树与 Ball 树的比较

• KD 树是一种适合低维均匀分布（通常小于 10 维）的数据结构，能显著加速最近邻搜索，但在高维空间中效率下降。
• Ball 树在高维空间中性能更好，适合数据分布不均匀或维度较高的场景，是比 KD 树更通用的选择。

如果处理的是低维数据且数据较均匀分布，KD 树是一个较好的选择；而对于高维数据或分布不均的数据，Ball 树更适合。

KD 树（KD-Tree）

KD 树（K-Dimensional Tree）是用于快速查找低维均匀分布数据的最近邻点。一种适用于低维空间的二叉搜索树结构，用于加速最近邻搜索。

工作原理

1. 将数据集沿某一维度（例如方差最大的维度）进行分割，选择中位数作为分割点。
2. 递归地对子节点进行分割，直到每个叶子节点包含少量数据点。
3. 通过树的结构进行最近邻搜索，剪枝减少计算量。

特点

• 对低维数据（通常维度小于 10）效果较好。
• 数据分布均匀、样本数量较少的场景。

Ball 树（Ball Tree）

Ball 树是一种适用于高维非均匀分布数据最近邻查找的数据结构，它通过将数据集划分为球形区域（ball），并在树中进行组织。每个节点表示一个球体区域，该球体由一个中心点和一个半径定义，用于描述和分割数据空间。

工作原理

1. 将数据集划分为两个球形区域，确保每个区域中点的数量相等。
2. 递归地对每个球形区域进行分割，直到每个叶子节点包含少量数据点。
3. 通过树的结构进行最近邻搜索，根据球体之间的距离进行剪枝。

中心点和半径如何选择？

1. 确定中心点：通常选择数据点的质心、中位数或最远的两个点作为中心点，即数据点的几何中心。质心是所有点的坐标平均值。
   • 选择质心作为中心点时，它是所有数据点在每个维度上的平均值。
   • 选择中位数作为中心点时，通常也是针对每个维度独立计算中位数。
   • 选择数据集中找到两个距离最远的点，作为初始的两个种子点。
2. 划分子集：数据点分配给距离更近的中心点。
3. 计算每个子集的半径：以该中心点到所有点中最远点的距离作为球体的半径，这样球体能够覆盖所有子树中的点。

特点

• 高维数据（通常大于 10 维）。
• 数据分布不均匀，样本量大。

KNN优缺点

• 优点：
  • 简单、直观、无需训练过程，适用于多分类问题。
  • 对异常值不敏感。
• 缺点：
  • 计算复杂度高（随着样本数量增加而增加）。
  • 对高维数据不适用（维度灾难）。
  • 对噪声数据敏感，需合理选择 K 值。

历史文章

本系列其他相关笔记参考如下：
机器学习笔记——损失函数、代价函数和KL散度
机器学习笔记——特征工程、正则化、强化学习
机器学习笔记——30种常见机器学习算法简要汇总
机器学习笔记——感知机、多层感知机(MLP)、支持向量机(SVM)