[算法学习] KNN近邻算法分类/回归/聚类

基础概念

KNN算法，全称为K-Nearest Neighbors（K-最近邻）算法，是一种基本的分类和回归算法。它的工作原理非常直观：通过测量不同特征值之间的距离来进行分类或回归预测。

优势/劣势

KNN算法简单易懂，并且无需训练过程，缺点是计算成本高（尤其是在大数据集上），对噪声数据敏感，以及需要合理选择K值和距离度量方法。

此外，KNN是一种惰性学习算法，它在训练阶段不进行模型训练，而是在预测阶段直接使用整个训练数据集。

计算步骤

我们用一个简单的三维数据集做例子，每个点由其三维坐标(x, y, z)和对应的类别标签组成

已知：

点1: (1, 2, 3), 类别A

点2: (2, 3, 4), 类别A

点3: (6, 5, 3), 类别B

点4: (7, 7, 8), 类别B

点5: (5, 5, 5), 类别C

在已知数据的基础上，我们要预测一个新的点（4, 5, 6)的类别。

步骤1：确定K值

假设我们选择K = 4，即距离最近的4个点。（由于一共只有5个数据，K=1，2，3都有可能造成无法分类的情况，所以这里选择4）

注意：K值的选择并不是恒定的，取决于多种因素：

数据集的大小：较小的数据集可能需要较小的K值，以避免过拟合；较大的数据集可能允许使用较大的K值。
数据的维度：高维数据集可能需要较大的K值，因为高维空间中的点之间的距离较为分散。
噪声和异常值的影响：较小的K值可能对噪声和异常值更敏感。如果数据集中存在噪声或异常值，较大的K值可以帮助减少这些因素的影响。
类别的分布：如果数据集中的类别分布不均匀，可能需要调整K值来平衡不同类别的影响。
实验和验证：通常通过交叉验证等实验方法来确定最佳的K值。通过在不同的K值上测试模型的性能，选择能够提供最佳分类准确率的K值。
计算资源：较小的K值可以减少计算量，因为需要计算的距离更少。但是，如果计算资源充足，可以选择较大的K值。
问题的特性：某些问题可能天然适合使用较小或较大的K值。例如，如果问题需要捕捉非常细微的模式，可能需要较小的K值。

步骤2：距离度量

通常KNN会选择欧式距离作为度量方法，欧氏距离是最直观的距离度量方式，用来测量两点在多维空间中的直线距离。与其他距离度量方法相比，欧氏距离的计算相对简单，特别是在低维空间中。

计算公式为：

distance = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

而在高维空间中，欧氏距离具有局限性，因为数据点之间的距离会趋向于相同，这种现象被称为“维度的诅咒”。在特定情况下，可能需要考虑其他距离度量方法，如曼哈顿距离、切比雪夫距离、闵可夫斯基距离或余弦相似度等，以更好地适应数据的特性和问题的需求。

步骤3：寻找最近邻

计算新点(4, 5, 6)与训练集中每个点的距离：

点1： \sqrt{(4-1)^2+(5-2)^2+(6-3)^2}= \sqrt{27}

点2： \sqrt{(4-2)^2+(5-3)^2+(6-4)^2}= \sqrt{12}

点3： \sqrt{(4-6)^2+(5-5)^2+(6-3)^2}= \sqrt{13}

点4： \sqrt{(4-7)^2+(5-7)^2+(6-8)^2}= \sqrt{17}

点5： \sqrt{(4-5)^2+(5-5)^2+(6-5)^2}= \sqrt{2}

由于K = 4，最近的3个点为：点5，点2，点3，点4

步骤4: 决策规则

点5 = C，点2 = A，点3 = B，点4 = B。所以我们可以得出，新的点的归类 = B

加权投票法：在机器学习中，除了投票法，也可能会应用到加权法来确定分类，即每个邻居的投票权重可能与其距离成反比，即距离未知样本越近的邻居对预测结果的影响越大。

处理平票：如果K个最近邻居中存在多个类别的票数相同，可能需要额外的规则来解决平票问题，例如随机选择其中一个类别，或者选择距离最近的类别。

计算步骤比较简单，我就不写代码块了，有需要大家可以自己用AI写

应用场景

分类问题：例如文本分类、图像识别、手写数字识别、医学诊断等。

回归问题：例如房价预测、股票价格预测等。

异常检测：由于KNN可以识别与大多数邻居不同的点，它常用于识别异常值或离群点。

推荐系统：在推荐系统中，KNN可以用来找到与用户兴趣最相似的其他用户或物品，并基于这些相似性进行推荐。

图像分割：在图像处理中，KNN可以用来识别图像中的区域，并进行图像分割。

聚类分析：KNN也可以用于聚类任务，尤其是当数据集中的簇不是明显的球形或高斯分布时。

回归问题的计算实例

假设一个数据集：每个样本包含三个特征：房屋面积（平方米）、房间数、离地铁站的距离（公里），以及对应的房价（万元）

样本1: 面积=100, 房间数=2, 距离=2, 房价=150

样本2: 面积=120, 房间数=3, 距离=1, 房价=180

样本3: 面积=80, 房间数=1, 距离=3, 房价=120

样本4: 面积=150, 房间数=4, 距离=2, 房价=210

样本5: 面积=200, 房间数=5, 距离=1, 房价=300

新样本的特征为：面积=130平方米，房间数=3，离地铁站的距离=2公里。

我们选择K = 3 作为近邻数

距离计算：

样本1： \sqrt{(130-100)^2+(3-2)^2+(2-2)^2}=\sqrt{901}

样本2： \sqrt{(130-120)^2+(3-3)^2+(2-1)^2}=\sqrt{101}

样本3： \sqrt{(130-80)^2+(3-1)^2+(2-3)^2}=\sqrt{2505}

样本4： \sqrt{(130-150)^2+(3-4)^2+(2-2)^2}=\sqrt{401}

样本5： \sqrt{(130-200)^2+(3-5)^2+(2-1)^2}=\sqrt{4905}

根据距离，最近的3个样本是2，4，1

根据这三个样本的房价求平均数 = 180 （使用加权平均的话，在距离的基础上加上权重系数就可以）

所以预测新样本的房价为 180万元

[算法学习] KNN近邻算法 分类/回归/聚类