K-最近邻（K-Nearest Neighbors, KNN）算法 K-最近邻算法是一种基本且直观的监督学习算法，常用于分类和回归任务。其核心思想是：一个样本的类别或数值可以由其“邻居”的多数意见或平均值来决定。简单来说，“物以类聚，人以群分”。 1. 算法基本描述 假设我们有一个已经标注好类别的数据集（称为训练集）。当输入一个没有标签的新数据点时，KNN算法的工作流程如下： 确定参数K的值，即要考虑的“邻居”的数量。 计算这个新数据点与训练集中每一个数据点的距离。 从训练集中找出距离新数据点最近的K个点。 对于分类任务：这K个最近邻点进行投票，将新数据点分配给得票最多的类别。 对于回归任务：取这K个最近邻点的目标值的平均值，作为新数据点的预测值。 2. 关键组成部分的深入解析 2.1 距离度量 “最近”是如何定义的？这依赖于距离度量函数。选择不同的度量标准，会改变“邻居”的集合，从而影响结果。 欧氏距离 ：最常用、最直观的距离。在n维空间中，两点之间的直线距离。公式为： d = √(Σ(x_i - y_i)^2) 。 曼哈顿距离 ：在网格状路径（如城市街区）上两点之间的距离。公式为： d = Σ|x_i - y_i| 。 闵可夫斯基距离 ：欧氏距离和曼哈顿距离的泛化形式。 余弦相似度 ：更关注两个向量方向上的差异，而非绝对距离，常用于文本分类。 2.2 K值的选择 K是一个超参数，需要我们在算法运行前手动设定。它的选择对结果有决定性影响，体现了偏差与方差的权衡。 K值过小（例如K=1） ： 模型变得复杂，只依赖于最邻近的单个样本。 对噪声数据异常敏感，容易过拟合。决策边界会变得非常不规则。 低偏差，高方差。 K值过大（例如K=训练集大小） ： 模型变得简单，无论输入什么，预测结果都将是训练集中最常见的类别。 忽略了数据中可能存在的局部模式，容易欠拟合。 高偏差，低方差。 如何选择K？ 通常通过交叉验证来评估不同K值下的模型性能（如准确率），并选择性能最好的那个K。 2.3 决策规则 找到K个邻居后，如何做出最终决策？ 分类：多数投票法 。每个邻居投自己类别一票，得票最多的类别胜出。为了更精细，可以采用 加权投票 ，距离近的邻居权重更高，其投票更有影响力。 回归：平均值法 。取K个邻居目标值的算术平均值。同样，也可以采用 加权平均 ，距离近的邻居对最终结果的贡献更大。 3. 算法的优缺点 优点 ： 原理简单，易于理解和实现 。 无需训练过程 。算法是“懒惰学习”的典型代表，它实际上没有显式的训练阶段，只是将训练数据存储起来。预测时才会进行计算。 对数据分布没有假设 。适用于各种类型的数据。 缺点 ： 计算成本高 。预测时需计算新样本与所有训练样本的距离，当训练集很大时，预测速度非常慢。时间复杂度为O(N)，其中N是训练集大小。 对不相关的特征和尺度差异敏感 。如果某个特征的数值范围远大于其他特征，它在距离计算中会占据主导地位，需要进行特征缩放（如归一化或标准化）。 维数灾难 。当特征数量（维度）非常多时，所有数据点在高维空间中都会显得彼此“遥远”，距离度量会失去意义，导致性能下降。 需要大量内存 。因为需要存储整个训练集。 4. 优化与改进 为了解决计算效率低下的问题，可以采用以下方法： 使用高效的数据结构 ：如KD树或球树来组织训练数据，可以将最近邻搜索的时间复杂度从O(N)降低到O(logN)（在低维情况下）。 数据编辑 ：移除对分类决策影响不大的训练样本（如冗余样本、噪声样本），减少计算量。 总结来说，KNN是一种基于实例的简单而强大的算法。理解其核心思想、K值的影响以及距离度量的选择，是掌握并应用该算法的关键。