参考
Python—KNN分类算法
K-近邻算法： k-nearest neighbor classification (kNN) 详细介绍
一文掌握KNN

其实没什么必要单独讲，思想不算很难，看看能不能合并到哪篇里吧

KNN算法概述

KNN（K Nearest Neighbors）算法是一种基于距离的分类算法，原理是通过比较待预测点与训练集中每个点的距离，选取最近的 $K$ 个邻居点来判断该点所属的类别。

通过遍历训练集中的每一个点，然后计算与预测点的距离，最后选取距离最小的k个点，判断哪种类型占比最大就把这个预测点归于那个类别(计算量其实挺大的)。

距离度量

  1. 欧氏距离（Euclidean Distance）
    直线距离
    $$
    d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}
    $$

  2. 曼哈顿距离（Manhattan Distance）
    沿着坐标轴方向的总距离
    $$
    d(x, y) = \sum_{i=1}^{n}|x_i - y_i|
    $$

  3. 切比雪夫距离（Chebyshev Distance）
    任一维度上最大的差异
    $$
    d(x, y) = \max_i |x_i - y_i|
    $$

  4. 余弦相似度（Cosine Similarity）
    方向上的相似度，值越接近1表示越相似
    $$
    \text{Cosine Similarity}(x, y) = \frac{x \cdot y}{|x| |y|}
    $$
    其中，$x \cdot y$ 是向量的点积，$|x|$ 和 $|y|$ 是它们的模（欧几里得范数）。

KD树（K-dimensional Tree）

怎么确定还没加上，虽然划分可以加速但是在交界的影响会怎么样还是值得考虑的……有兴趣再做吧做机器学习也不用深入那么多，何况这个现在很少用了

KD树是一种用于加速 KNN 搜索的空间划分方法，通过二叉树的结构递归地划分数据点，减少不必要的距离计算，从而提高查询效率。

  1. 选择维度：在构建树时，轮流选择每个维度来进行切分。通常选择当前维度的中位数来划分数据。例如，第一层选择 $x$ 维，第二层选择 $y$ 维，依此类推。

  2. 选择中位数：每次选择当前维度的中位数作为切分点，保证树的平衡性，使得每个子树大小大致相等。

  3. 递归划分：通过递归构建子树，直到每个节点的区域足够小。

通过构建KD树，KNN查询时可以快速定位到可能包含最近邻的子树，减少了计算距离的次数，提高查询速度。

KNN是一种非参的、惰性的算法模型。什么是非参，什么是惰性呢？

非参的意思并不是说这个算法不需要参数，而是意味着这个模型不会对数据做出任何的假设，与之相对的是线性回归（我们总会假设线性回归是一条直线）。也就是说 KNN 建立的模型结构是根据数据来决定的，这也比较符合现实的情况，毕竟在现实中的情况往往与理论上的假设是不相符的。

惰性又是什么意思呢？想想看，同样是分类算法，逻辑回归需要先对数据进行大量训练（tranning），最后才会得到一个算法模型。而 KNN 算法却不需要，它没有明确的训练数据的过程，或者说这个过程很快。
此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理

KNN模型优化

由于KNN是基于距离计算的，当数据的量纲不统一时，会导致某些维度对距离的影响过大，从而影响模型的效果。因此，在使用KNN时，需要对数据进行归一化处理，使得所有特征的尺度一致。

权重加权

在KNN算法中，常见的优化方法是对每个最近邻点的影响进行加权，权重通常设置为距离的倒数。这样距离较近的点对分类结果的影响更大，远离的点影响较小。

注意，关于模型的优化方法只是在理论上优化会提升模型判别效力，但实际应用过程中最终能否发挥作用，本质上取决于优化方法和实际数据情况的契合程度，如果数据本身存在大量异常值点，则采用距离远近作为惩罚因子则会有较好的效果，反之则不然。

选择K值

K值的选择对KNN算法的性能有重要影响。较小的K值会使模型过拟合，较大的K值则可能使模型欠拟合。可以通过交叉验证方法来选择最优的K值，即将数据集分为训练集和验证集，测试不同的K值，选择性能最佳的K值(可以看图像粗判)。