K-最近邻（K-Nearest Neighbors, KNN）算法 K-最近邻（KNN）是一种基本的分类与回归方法。它的核心思想是：如果一个样本在特征空间中的k个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法简单直观，不需要显式的训练过程，属于“懒惰学习”（lazy learning）的典型代表。 1. 算法基本思想 基本假设 ：相似的数据点在特征空间中距离较近。 工作原理 ：对于一个新的数据点，根据其k个最近邻的类别（或数值）来预测其类别（或数值）。 关键参数 ：k值的选择（通常为奇数，以避免平票）、距离度量（如欧氏距离、曼哈顿距离）。 2. 算法步骤详解 步骤1：选择距离度量 常用欧氏距离（Euclidean Distance）计算两个样本点之间的距离。对于两个n维向量 \( x = (x_ 1, x_ 2, ..., x_ n) \) 和 \( y = (y_ 1, y_ 2, ..., y_ n) \)，欧氏距离公式为： \[ d(x, y) = \sqrt{\sum_ {i=1}^{n}(x_ i - y_ i)^2} \] 其他距离度量（如曼哈顿距离）可根据数据特性选择。 步骤2：确定k值 k值过小（如k=1）：模型对噪声敏感，容易过拟合。 k值过大：模型过于平滑，可能忽略局部特征，导致欠拟合。 通常通过交叉验证（Cross-Validation）选择最优k值。 步骤3：计算待预测点与所有训练样本的距离 对于待预测点，计算它与训练集中每个样本点的距离。 例如：训练集有m个样本，需计算m个距离值。 步骤4：选取k个最近邻 将计算出的距离按升序排序。 选择距离最小的k个训练样本作为“最近邻”。 步骤5：根据k个最近邻进行预测 分类问题 ：统计k个最近邻的类别，采用多数投票法（Majority Voting）确定预测类别。 回归问题 ：取k个最近邻目标值的平均值作为预测值。 3. 算法特点与复杂度分析 优点 ：简单易实现，无需训练过程，对数据分布无假设。 缺点 ： 计算复杂度高：预测时需要计算与所有训练样本的距离，时间复杂度为O(m·n)（m为样本数，n为特征维数）。 对高维数据敏感（维数灾难）。 对不平衡数据敏感（可加权投票缓解）。 4. 优化策略 使用KD树或球树 ：加速最近邻搜索，将复杂度降至O(log m)（低维数据下）。 特征标准化 ：避免某些特征因量纲不同而主导距离计算。 距离加权 ：为更近的邻居分配更高权重，提高预测精度。 5. 示例说明（分类问题） 假设训练集包含两类样本（红色和蓝色），待预测点（绿色）的k=3： 计算绿色点与所有点的欧氏距离。 找出距离最近的3个点（2个红色，1个蓝色）。 根据多数投票，预测绿色点为红色类别。 6. 总结 KNN是一种基于实例的学习方法，适用于小规模数据集和低维特征空间。实际应用中需注意k值选择、距离度量和计算效率的优化。