文章目录K近邻KNN1. KNN算法核心思想与步骤1.1 算法思想1.2 具体算法步骤2. 相似性度量KNN的“距离”是什么2.1 欧氏距离Euclidean Distance2.2 曼哈顿距离Manhattan Distance2.3 切比雪夫距离Chebyshev Distance2.4 闵可夫斯基距离Minkowski Distance2.5 距离对比与选择3. 高效检索KD树加速最近邻搜索3.1 为什么需要KD树3.2 KD树的构建用平面反复切割空间3.3 KD树的搜索过程回溯与“画圆”3.4 sklearn中的算法选择4. K值的选择过拟合与欠拟合的权衡4.1 K值过小 过拟合4.2 K值过大欠拟合4.3 如何找到合适的K5. sklearn API 实战5.1 主要类与模块5.2 关键参数详解5.3 代码示例6. KNN算法优缺点总结7. 机器学习知识补充超参数的确定7.1 交叉验证Cross-Validation7.2 网格搜索Grid Search7.3 sklearn实现GridSearchCVK近邻KNN1. KNN算法核心思想与步骤1.1 算法思想KNNK-Nearest Neighbors是一种直观且经典的监督学习算法。它的核心思想简单来说一个样本的标签应该和它在特征空间里最相似的 K 个邻居的标签一致。1.2 具体算法步骤计算距离计算待预测样本与训练集中每一个样本的相似性通常用距离来衡量。排序取K将计算出的所有距离递增排序选出相似度最高距离最小的 K 个样本。投票/平均分类问题统计这 K 个样本中每个类别的出现次数取出现次数最多的类别作为预测结果多数表决。回归问题计算这 K 个样本目标值的平均值作为预测结果。输出结果。疑惑KNN在预测时要依赖训练集那它算不算监督学习答案是是的。 KNN在训练阶段实际上只是“记住”了整个训练集没有显式的模型训练过程当新样本到来时才去寻找训练集中的近邻。它必须使用带标签的训练数据因此是典型的监督学习。预测时并不需要测试集的真实标签只是利用训练集的标签来推断。2. 相似性度量KNN的“距离”是什么“距离”是KNN判断相似性的核心。在原理上距离公式是可以自定义的但在scikit-learn中默认使用欧氏距离也可以通过修改参数选择其他距离。下面介绍几种常用的距离公式及其直观理解。2.1 欧氏距离Euclidean Distance公式d ∑ i 1 n ( x i − y i ) 2 d \sqrt{\sum_{i1}^{n}(x_i - y_i)^2}di1∑n(xi−yi)2通俗理解就是我们最熟悉的“两点之间的直线距离”。可以沿着任意方向移动所以我们可以理解为朝着目标点的方向移动的距离。2.2 曼哈顿距离Manhattan Distance公式d ∑ i 1 n ∣ x i − y i ∣ d \sum_{i1}^{n}|x_i - y_i|di1∑n∣xi−yi∣通俗理解好比你在城市里开车只能沿着纵横的街道走不能斜穿街区。也就是说可以沿着x方向和y方向移动所以从一点到另一点必须走的水平方向距离加上垂直方向距离之和。来源得名于曼哈顿的街区网格布局适用于特征相互独立、各维度差异需同等对待的场景。2.3 切比雪夫距离Chebyshev Distance公式d max i ( ∣ x i − y i ∣ ) d \max_i(|x_i - y_i|)dimax(∣xi−yi∣)通俗理解假设你是一个国际象棋里的王每次可以向八个方向上下左右、四个斜角移动一格。也就是说可以沿着八个方向移动从一点到另一点的距离就取决于各坐标差值中最大的那个。因为在你移动的过程中斜向移动可以同时减少两个坐标的差值所以步数由最大的差距决定较小差距早就被“顺路”处理了。来源常用于网格、物流调度等场景衡量某一维度的最大偏差。2.4 闵可夫斯基距离Minkowski Distance公式d ( ∑ i 1 n ∣ x i − y i ∣ p ) 1 / p d \left( \sum_{i1}^{n}|x_i - y_i|^p \right)^{1/p}d(i1∑n∣xi−yi∣p)1/p这是上面几种距离的统一定义形式。当 (p1) 时就是曼哈顿距离(p2) 时是欧氏距离(p \to \infty) 时就是切比雪夫距离。2.5 距离对比与选择距离类型特点适用场景欧氏距离直线距离各方向等权重大多数连续特征数据集曼哈顿距离坐标轴方向累加对异常值较不敏感特征间差异需要独立累加时如文档分析切比雪夫距离只看最大差值忽略其他维度微小变动强调极端维度差异的场合闵可夫斯基距离可以通过p调节侧重需要灵活调整距离度量时在sklearn中通过metric参数即可自由切换同时也可以传入自定义的距离函数。3. 高效检索KD树加速最近邻搜索如果每预测一个点都要和全部训练样本算一次距离当数据量很大时会非常慢。KD树K-Dimensional Tree正是为了加速这一过程而生的数据结构。3.1 为什么需要KD树暴力计算的时间复杂度为 O(n×d)n为样本数d为维度。KD树通过提前将空间分层划分可以将最近邻搜索的平均复杂度降到 O(log n)。它本质上是一种“空间换时间”的策略。3.2 KD树的构建用平面反复切割空间在R维空间中每次选择一个维度例如先从第1维开始。找到当前样本在该维度上的中位值用一个垂直于该坐标轴的超平面将空间一分为二。左子节点存放该维度值 ≤ 中位值的样本右子节点存放 中位值的样本。切换到下一维度对两个子空间递归执行同样的分割直到每个叶子节点只包含少数样本或达到预定深度。形象比喻像切蛋糕第一刀竖直切成左右两块接着把左块横着切右块也横着切……每一刀都是在一个维度上取中间点不断将空间划分为更小的超矩形。这样树中的每个非叶节点就是一个“切割点”叶子节点就是不能再分的“小空间”。[按维度1分割] / \ (左空间) (右空间) [按维度2分割] [按维度2分割] / \ / \ 叶子A 叶子B 叶子C 叶子D例子理解使用二维数据点每层切换划分维度第一层按 x第二层按 y以此类推( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) (2,3),\ (5,4),\ (9,6),\ (4,7),\ (8,1),\ (7,2)(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)根节点(7,2)按 x 划分分割值 7。左子树节点(5,4)按 y 划分分割值 4其左子(2,3)右子(4,7)。右子树节点(9,6)按 y 划分分割值 6其左子(8,1)。3.3 KD树的搜索过程回溯与“画圆”当你查询一个测试点时先像插入一样从根节点沿分支走到对应的叶子节点把这个叶子里的点当作“当前最近邻”。但最近邻不一定就在该叶子空间内于是我们执行回溯向上回溯父节点分割点对路径上的每一个节点执行以下操作计算与该节点所存数据点的距离。若该距离小于当前最近距离则更新最近点和最近距离(r) 。当前节点在维度 d上把空间一分为二Q 落在一侧另一侧未被搜索。所以以查询点为圆心、(r) 为半径画一个超球面。检查该超球面是否与回溯路径上的分割超平面相交。如果相交说明另一侧分支中可能存在更近的点则必须进入该分支重新搜索。若不相交则另一侧不可能有更近的点直接剪枝不搜索另一侧。继续向上回溯直到根节点处理完毕搜索结束。最终得到的最近点即为查询点的最近邻为什么这样能找到真实最近邻因为如果超球面与某分割面相交就代表可能存在落在分割面另一侧、但离查询点比 (r) 更近的点若不相交则该侧所有点距离一定大于 (r)可以直接剪枝。这种机制保证了查找效率。例子理解设查询点Q ( 2 , 4.5 ) Q (2, 4.5)Q(2,4.5)搜索其最近邻。第一步向下到达叶节点从根(7,2)[x] 开始Q . x 2 7 Q.x 2 7Q.x27→ 进入左子树到达(5,4)[y]。(5,4)按 y 划分Q . y 4.5 4 Q.y 4.5 4Q.y4.54→ 进入右子树到达叶节点(4,7)。将(4,7)设为当前最近点距离d ( 2 − 4 ) 2 ( 4.5 − 7 ) 2 4 6.25 ≈ 3.201 d \sqrt{(2-4)^2 (4.5-7)^2} \sqrt{4 6.25} \approx 3.201d(2−4)2(4.5−7)246.25≈3.201第二步回溯到(5,4)计算Q QQ到(5,4)的距离d ( 2 − 5 ) 2 ( 4.5 − 4 ) 2 9 0.25 ≈ 3.041 d \sqrt{(2-5)^2 (4.5-4)^2} \sqrt{9 0.25} \approx 3.041d(2−5)2(4.5−4)290.25≈3.0413.041 3.201 3.041 3.2013.0413.201更新最近点为(5,4)最近距离 ≈ 3.041。判断另一子树即(5,4)的左子树包含(2,3)(5,4)的分割维度是 y分割值 4。Q QQ在分割面的右侧y4.5 4另一侧是 y 4 的半空间。到分割面的距离 ∣ 4.5 − 4 ∣ 0.5 |4.5 - 4| 0.5∣4.5−4∣0.5。0.5 3.041 0.5 3.0410.53.041说明另一侧可能存在更近的点必须搜索。进入(5,4)的左子节点(2,3)。第三步搜索(2,3)并返回(2,3)为叶节点计算Q QQ到它的距离d ( 2 − 2 ) 2 ( 4.5 − 3 ) 2 1.5 d \sqrt{(2-2)^2 (4.5-3)^2} 1.5d(2−2)2(4.5−3)21.51.5 3.041 1.5 3.0411.53.041更新最近点为(2,3)最近距离 1.5。回溯至(5,4)已处理完毕。第四步回溯到根(7,2)计算Q QQ到(7,2)的距离d ( 2 − 7 ) 2 ( 4.5 − 2 ) 2 25 6.25 ≈ 5.590 d \sqrt{(2-7)^2 (4.5-2)^2} \sqrt{25 6.25} \approx 5.590d(2−7)2(4.5−2)2256.25≈5.5905.590 1.5 5.590 1.55.5901.5不更新最近点。判断另一子树根节点的右子树包含(9,6)和(8,1)根按 x 划分分割值 7。Q . x 2 Q.x2Q.x2在分割面左侧另一侧是 x 7 的半空间。到分割面的距离 ∣ 2 − 7 ∣ 5 |2 - 7| 5∣2−7∣5。5 ≥ 1.5 5 \ge 1.55≥1.5另一侧不可能有比 1.5 更近的点剪枝不搜索右子树。第五步回溯结束当前最近点为(2,3)最近距离 1.5即为最终结果。3.4 sklearn中的算法选择在sklearn的KNN中通过参数algorithm控制搜索算法auto自动根据数据选择最合适的算法。ball_tree球树高维数据下效果更好。kd_treeKD树适合低维数据一般20维。brute暴力搜索直接计算所有距离。通常保留auto即可它会智能选择。可以看到距离和排序实现并不是固定的我们可以通过metric和algorithm参数灵活调整。4. K值的选择过拟合与欠拟合的权衡K是KNN里最重要的超参数它直接控制着模型的复杂度。理解它对偏差与方差的影响是关键。4.1 K值过小 过拟合当 K1 时预测只依赖最近的那个邻居。这意味着模型变得非常复杂完全贴合训练数据。对噪声点和异常点极度敏感每一个孤立样本都可能形成小的“决策孤岛”。训练集上表现好测试集上表现差 →过拟合。4.2 K值过大欠拟合当 K 接近训练集总样本数时分类将总是预测频率最高的类别回归就是全局平均值。模型过于简单很多无关的远距离样本也参与投票/平均导致决策边界过于平滑。学习的“特征”太少无法捕捉数据的真实结构训练集和测试集表现都差 →欠拟合。“K过大时因为加了远距离的样本作平均难道不是引入了噪声让模型复杂吗”实际上这些远距离点把预测值向全局均值拉扯抑制了决策边界的复杂性使得模型的偏差增大整体表达能力下降。噪声虽然进入了投票但其效果是被平均掉的更多表现为欠拟合而非过拟合。过拟合的根源在于模型对训练集中的细微信号和噪声过于忠实K越小越忠实K越大越“糊化”信息导致欠拟合。4.3 如何找到合适的K选择K没有绝对公式一般通过交叉验证和网格搜索来确定详见第7节。常见经验K一般选奇数避免投票平局。从较小的K开始尝试观察验证曲线。数据量越大K可相对选大一些数据维度高时则要小心维度灾难。5. sklearn API 实战5.1 主要类与模块sklearn.neighbors.KNeighborsClassifier用于分类。sklearn.neighbors.KNeighborsRegressor用于回归。5.2 关键参数详解以分类器为例KNeighborsClassifier(n_neighbors5,# K值默认5weightsuniform,# uniform: 所有邻居权重相同distance: 距离倒数加权更近的邻居影响更大algorithmauto,# 搜索算法ball_tree, kd_tree, brute, autometricminkowski,# 距离度量默认闵可夫斯基(p2即欧氏距离)p2,# 闵可夫斯基距离的参数pn_jobsNone# 并行搜索的CPU核数)常用方法fit(X, y)训练模型KNN在这里实际上只是存储数据。predict(X)对测试样本进行预测。kneighbors(X, n_neighborsNone, return_distanceTrue)返回每个测试样本的K个最近邻居的距离及索引。score(X, y)返回预测的准确率分类或R²回归。5.3 代码示例fromsklearn.neighborsimportKNeighborsClassifierfromsklearn.datasetsimportload_irisfromsklearn.model_selectionimporttrain_test_split# 数据准备irisload_iris()X_train,X_test,y_train,y_testtrain_test_split(iris.data,iris.target,test_size0.2,random_state42)# 建立KNN分类器K3使用距离加权knnKNeighborsClassifier(n_neighbors3,weightsdistance)knn.fit(X_train,y_train)# 训练存储数据y_predknn.predict(X_test)# 预测accuracyknn.score(X_test,y_test)# 评估print(fTest accuracy:{accuracy:.3f})6. KNN算法优缺点总结优点原因简单直观易于理解实现原理完全基于距离和投票无需复杂数学推导无需训练过程懒惰学习只需存储数据新数据到来时即时计算天然支持多分类多数表决机制自然支持任意类别数能处理非线性问题决策边界可以是任意复杂形状不假设数据分布对异常值不敏感K较大时K值增大时个别离群点被多数邻居稀释缺点原因计算开销大预测慢每次预测都需要遍历或搜索大量训练样本内存消耗高需要存储全部训练数据数据量大时不适用维度灾难高维空间中距离区分度下降几乎所有点都差不多远对特征缩放敏感距离计算受量纲影响大必须做标准化或归一化样本不平衡问题多数类容易主导投票结果需要适当加权或重采样7. 机器学习知识补充超参数的确定K就是一个典型的超参数需要人为设定。如何系统化地选出最优K这就要用到交叉验证和网格搜索。7.1 交叉验证Cross-Validation思想将训练数据分成n份依次用其中1份作为验证集其余n-1份作为训练集重复n次训练和验证得到n个评估分数最终取平均作为模型的性能指标。这就是n折交叉验证。为什么要这样做单次划分的训练/验证集可能带有偶然性交叉验证通过多次“换着来”使得评估结果更加稳定、可信。能有效检测模型是否稳定防止因某次数据分割的“运气”而得到误导性的好成绩。单独使用交叉验证也是有意义的它可以用来评估给定超参数下模型的泛化能力而不仅仅是服务于网格搜索。7.2 网格搜索Grid Search当有多个超参数需要调节时手动尝试每一种组合非常繁琐。网格搜索的做法是为每个超参数指定一个候选值的列表。生成所有参数组合的“网格”。对每一组组合使用交叉验证评估模型表现。选出交叉验证平均得分最高的那一组参数作为最终选择。比如我们为KNN设定候选n_neighbors[3,5,7,9]weights[uniform,distance]网格搜索会遍历这 4×28 种组合找出最优搭配。7.3 sklearn实现GridSearchCVfromsklearn.model_selectionimportGridSearchCVfromsklearn.neighborsimportKNeighborsClassifier# 定义KNN模型knnKNeighborsClassifier()# 超参数网格param_grid{n_neighbors:[3,5,7,9,11],weights:[uniform,distance],metric:[euclidean,manhattan]}# 5折交叉验证的网格搜索grid_searchGridSearchCV(knn,param_grid,cv5,scoringaccuracy)grid_search.fit(X_train,y_train)print(最佳参数组合:,grid_search.best_params_)print(最佳交叉验证分数:,grid_search.best_score_)# 使用最佳模型预测best_knngrid_search.best_estimator_ test_scorebest_knn.score(X_test,y_test)print(测试集准确率:,test_score)常用参数说明estimator待调参的模型。param_grid参数字典键为参数名值为要尝试的列表。cv交叉验证折数默认为5。scoring评估指标如accuracy、f1等。训练完后best_params_和best_score_可查看最优结果。希望这篇笔记能帮你理清 KNN。KNN作为最“佛系”的机器学习算法不训练模型靠“邻里关系”做决策。理解它的距离度量、KD树加速原理、K值对偏差方差的影响以及如何用交叉验证和网格搜索调优。以上为个人学习总结旨在梳理个人理解。如有疏漏或不当之处欢迎指正与交流。如果文章对你有帮助别忘了点个赞、留个言让更多的小伙伴看到 我们下篇再见
【机器学习|DAY03】K近邻算法（KNN）笔记
发布时间：2026/7/22 9:37:19
文章目录K近邻KNN1. KNN算法核心思想与步骤1.1 算法思想1.2 具体算法步骤2. 相似性度量KNN的“距离”是什么2.1 欧氏距离Euclidean Distance2.2 曼哈顿距离Manhattan Distance2.3 切比雪夫距离Chebyshev Distance2.4 闵可夫斯基距离Minkowski Distance2.5 距离对比与选择3. 高效检索KD树加速最近邻搜索3.1 为什么需要KD树3.2 KD树的构建用平面反复切割空间3.3 KD树的搜索过程回溯与“画圆”3.4 sklearn中的算法选择4. K值的选择过拟合与欠拟合的权衡4.1 K值过小 过拟合4.2 K值过大欠拟合4.3 如何找到合适的K5. sklearn API 实战5.1 主要类与模块5.2 关键参数详解5.3 代码示例6. KNN算法优缺点总结7. 机器学习知识补充超参数的确定7.1 交叉验证Cross-Validation7.2 网格搜索Grid Search7.3 sklearn实现GridSearchCVK近邻KNN1. KNN算法核心思想与步骤1.1 算法思想KNNK-Nearest Neighbors是一种直观且经典的监督学习算法。它的核心思想简单来说一个样本的标签应该和它在特征空间里最相似的 K 个邻居的标签一致。1.2 具体算法步骤计算距离计算待预测样本与训练集中每一个样本的相似性通常用距离来衡量。排序取K将计算出的所有距离递增排序选出相似度最高距离最小的 K 个样本。投票/平均分类问题统计这 K 个样本中每个类别的出现次数取出现次数最多的类别作为预测结果多数表决。回归问题计算这 K 个样本目标值的平均值作为预测结果。输出结果。疑惑KNN在预测时要依赖训练集那它算不算监督学习答案是是的。 KNN在训练阶段实际上只是“记住”了整个训练集没有显式的模型训练过程当新样本到来时才去寻找训练集中的近邻。它必须使用带标签的训练数据因此是典型的监督学习。预测时并不需要测试集的真实标签只是利用训练集的标签来推断。2. 相似性度量KNN的“距离”是什么“距离”是KNN判断相似性的核心。在原理上距离公式是可以自定义的但在scikit-learn中默认使用欧氏距离也可以通过修改参数选择其他距离。下面介绍几种常用的距离公式及其直观理解。2.1 欧氏距离Euclidean Distance公式d ∑ i 1 n ( x i − y i ) 2 d \sqrt{\sum_{i1}^{n}(x_i - y_i)^2}di1∑n(xi−yi)2通俗理解就是我们最熟悉的“两点之间的直线距离”。可以沿着任意方向移动所以我们可以理解为朝着目标点的方向移动的距离。2.2 曼哈顿距离Manhattan Distance公式d ∑ i 1 n ∣ x i − y i ∣ d \sum_{i1}^{n}|x_i - y_i|di1∑n∣xi−yi∣通俗理解好比你在城市里开车只能沿着纵横的街道走不能斜穿街区。也就是说可以沿着x方向和y方向移动所以从一点到另一点必须走的水平方向距离加上垂直方向距离之和。来源得名于曼哈顿的街区网格布局适用于特征相互独立、各维度差异需同等对待的场景。2.3 切比雪夫距离Chebyshev Distance公式d max i ( ∣ x i − y i ∣ ) d \max_i(|x_i - y_i|)dimax(∣xi−yi∣)通俗理解假设你是一个国际象棋里的王每次可以向八个方向上下左右、四个斜角移动一格。也就是说可以沿着八个方向移动从一点到另一点的距离就取决于各坐标差值中最大的那个。因为在你移动的过程中斜向移动可以同时减少两个坐标的差值所以步数由最大的差距决定较小差距早就被“顺路”处理了。来源常用于网格、物流调度等场景衡量某一维度的最大偏差。2.4 闵可夫斯基距离Minkowski Distance公式d ( ∑ i 1 n ∣ x i − y i ∣ p ) 1 / p d \left( \sum_{i1}^{n}|x_i - y_i|^p \right)^{1/p}d(i1∑n∣xi−yi∣p)1/p这是上面几种距离的统一定义形式。当 (p1) 时就是曼哈顿距离(p2) 时是欧氏距离(p \to \infty) 时就是切比雪夫距离。2.5 距离对比与选择距离类型特点适用场景欧氏距离直线距离各方向等权重大多数连续特征数据集曼哈顿距离坐标轴方向累加对异常值较不敏感特征间差异需要独立累加时如文档分析切比雪夫距离只看最大差值忽略其他维度微小变动强调极端维度差异的场合闵可夫斯基距离可以通过p调节侧重需要灵活调整距离度量时在sklearn中通过metric参数即可自由切换同时也可以传入自定义的距离函数。3. 高效检索KD树加速最近邻搜索如果每预测一个点都要和全部训练样本算一次距离当数据量很大时会非常慢。KD树K-Dimensional Tree正是为了加速这一过程而生的数据结构。3.1 为什么需要KD树暴力计算的时间复杂度为 O(n×d)n为样本数d为维度。KD树通过提前将空间分层划分可以将最近邻搜索的平均复杂度降到 O(log n)。它本质上是一种“空间换时间”的策略。3.2 KD树的构建用平面反复切割空间在R维空间中每次选择一个维度例如先从第1维开始。找到当前样本在该维度上的中位值用一个垂直于该坐标轴的超平面将空间一分为二。左子节点存放该维度值 ≤ 中位值的样本右子节点存放 中位值的样本。切换到下一维度对两个子空间递归执行同样的分割直到每个叶子节点只包含少数样本或达到预定深度。形象比喻像切蛋糕第一刀竖直切成左右两块接着把左块横着切右块也横着切……每一刀都是在一个维度上取中间点不断将空间划分为更小的超矩形。这样树中的每个非叶节点就是一个“切割点”叶子节点就是不能再分的“小空间”。[按维度1分割] / \ (左空间) (右空间) [按维度2分割] [按维度2分割] / \ / \ 叶子A 叶子B 叶子C 叶子D例子理解使用二维数据点每层切换划分维度第一层按 x第二层按 y以此类推( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) (2,3),\ (5,4),\ (9,6),\ (4,7),\ (8,1),\ (7,2)(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)根节点(7,2)按 x 划分分割值 7。左子树节点(5,4)按 y 划分分割值 4其左子(2,3)右子(4,7)。右子树节点(9,6)按 y 划分分割值 6其左子(8,1)。3.3 KD树的搜索过程回溯与“画圆”当你查询一个测试点时先像插入一样从根节点沿分支走到对应的叶子节点把这个叶子里的点当作“当前最近邻”。但最近邻不一定就在该叶子空间内于是我们执行回溯向上回溯父节点分割点对路径上的每一个节点执行以下操作计算与该节点所存数据点的距离。若该距离小于当前最近距离则更新最近点和最近距离(r) 。当前节点在维度 d上把空间一分为二Q 落在一侧另一侧未被搜索。所以以查询点为圆心、(r) 为半径画一个超球面。检查该超球面是否与回溯路径上的分割超平面相交。如果相交说明另一侧分支中可能存在更近的点则必须进入该分支重新搜索。若不相交则另一侧不可能有更近的点直接剪枝不搜索另一侧。继续向上回溯直到根节点处理完毕搜索结束。最终得到的最近点即为查询点的最近邻为什么这样能找到真实最近邻因为如果超球面与某分割面相交就代表可能存在落在分割面另一侧、但离查询点比 (r) 更近的点若不相交则该侧所有点距离一定大于 (r)可以直接剪枝。这种机制保证了查找效率。例子理解设查询点Q ( 2 , 4.5 ) Q (2, 4.5)Q(2,4.5)搜索其最近邻。第一步向下到达叶节点从根(7,2)[x] 开始Q . x 2 7 Q.x 2 7Q.x27→ 进入左子树到达(5,4)[y]。(5,4)按 y 划分Q . y 4.5 4 Q.y 4.5 4Q.y4.54→ 进入右子树到达叶节点(4,7)。将(4,7)设为当前最近点距离d ( 2 − 4 ) 2 ( 4.5 − 7 ) 2 4 6.25 ≈ 3.201 d \sqrt{(2-4)^2 (4.5-7)^2} \sqrt{4 6.25} \approx 3.201d(2−4)2(4.5−7)246.25≈3.201第二步回溯到(5,4)计算Q QQ到(5,4)的距离d ( 2 − 5 ) 2 ( 4.5 − 4 ) 2 9 0.25 ≈ 3.041 d \sqrt{(2-5)^2 (4.5-4)^2} \sqrt{9 0.25} \approx 3.041d(2−5)2(4.5−4)290.25≈3.0413.041 3.201 3.041 3.2013.0413.201更新最近点为(5,4)最近距离 ≈ 3.041。判断另一子树即(5,4)的左子树包含(2,3)(5,4)的分割维度是 y分割值 4。Q QQ在分割面的右侧y4.5 4另一侧是 y 4 的半空间。到分割面的距离 ∣ 4.5 − 4 ∣ 0.5 |4.5 - 4| 0.5∣4.5−4∣0.5。0.5 3.041 0.5 3.0410.53.041说明另一侧可能存在更近的点必须搜索。进入(5,4)的左子节点(2,3)。第三步搜索(2,3)并返回(2,3)为叶节点计算Q QQ到它的距离d ( 2 − 2 ) 2 ( 4.5 − 3 ) 2 1.5 d \sqrt{(2-2)^2 (4.5-3)^2} 1.5d(2−2)2(4.5−3)21.51.5 3.041 1.5 3.0411.53.041更新最近点为(2,3)最近距离 1.5。回溯至(5,4)已处理完毕。第四步回溯到根(7,2)计算Q QQ到(7,2)的距离d ( 2 − 7 ) 2 ( 4.5 − 2 ) 2 25 6.25 ≈ 5.590 d \sqrt{(2-7)^2 (4.5-2)^2} \sqrt{25 6.25} \approx 5.590d(2−7)2(4.5−2)2256.25≈5.5905.590 1.5 5.590 1.55.5901.5不更新最近点。判断另一子树根节点的右子树包含(9,6)和(8,1)根按 x 划分分割值 7。Q . x 2 Q.x2Q.x2在分割面左侧另一侧是 x 7 的半空间。到分割面的距离 ∣ 2 − 7 ∣ 5 |2 - 7| 5∣2−7∣5。5 ≥ 1.5 5 \ge 1.55≥1.5另一侧不可能有比 1.5 更近的点剪枝不搜索右子树。第五步回溯结束当前最近点为(2,3)最近距离 1.5即为最终结果。3.4 sklearn中的算法选择在sklearn的KNN中通过参数algorithm控制搜索算法auto自动根据数据选择最合适的算法。ball_tree球树高维数据下效果更好。kd_treeKD树适合低维数据一般20维。brute暴力搜索直接计算所有距离。通常保留auto即可它会智能选择。可以看到距离和排序实现并不是固定的我们可以通过metric和algorithm参数灵活调整。4. K值的选择过拟合与欠拟合的权衡K是KNN里最重要的超参数它直接控制着模型的复杂度。理解它对偏差与方差的影响是关键。4.1 K值过小 过拟合当 K1 时预测只依赖最近的那个邻居。这意味着模型变得非常复杂完全贴合训练数据。对噪声点和异常点极度敏感每一个孤立样本都可能形成小的“决策孤岛”。训练集上表现好测试集上表现差 →过拟合。4.2 K值过大欠拟合当 K 接近训练集总样本数时分类将总是预测频率最高的类别回归就是全局平均值。模型过于简单很多无关的远距离样本也参与投票/平均导致决策边界过于平滑。学习的“特征”太少无法捕捉数据的真实结构训练集和测试集表现都差 →欠拟合。“K过大时因为加了远距离的样本作平均难道不是引入了噪声让模型复杂吗”实际上这些远距离点把预测值向全局均值拉扯抑制了决策边界的复杂性使得模型的偏差增大整体表达能力下降。噪声虽然进入了投票但其效果是被平均掉的更多表现为欠拟合而非过拟合。过拟合的根源在于模型对训练集中的细微信号和噪声过于忠实K越小越忠实K越大越“糊化”信息导致欠拟合。4.3 如何找到合适的K选择K没有绝对公式一般通过交叉验证和网格搜索来确定详见第7节。常见经验K一般选奇数避免投票平局。从较小的K开始尝试观察验证曲线。数据量越大K可相对选大一些数据维度高时则要小心维度灾难。5. sklearn API 实战5.1 主要类与模块sklearn.neighbors.KNeighborsClassifier用于分类。sklearn.neighbors.KNeighborsRegressor用于回归。5.2 关键参数详解以分类器为例KNeighborsClassifier(n_neighbors5,# K值默认5weightsuniform,# uniform: 所有邻居权重相同distance: 距离倒数加权更近的邻居影响更大algorithmauto,# 搜索算法ball_tree, kd_tree, brute, autometricminkowski,# 距离度量默认闵可夫斯基(p2即欧氏距离)p2,# 闵可夫斯基距离的参数pn_jobsNone# 并行搜索的CPU核数)常用方法fit(X, y)训练模型KNN在这里实际上只是存储数据。predict(X)对测试样本进行预测。kneighbors(X, n_neighborsNone, return_distanceTrue)返回每个测试样本的K个最近邻居的距离及索引。score(X, y)返回预测的准确率分类或R²回归。5.3 代码示例fromsklearn.neighborsimportKNeighborsClassifierfromsklearn.datasetsimportload_irisfromsklearn.model_selectionimporttrain_test_split# 数据准备irisload_iris()X_train,X_test,y_train,y_testtrain_test_split(iris.data,iris.target,test_size0.2,random_state42)# 建立KNN分类器K3使用距离加权knnKNeighborsClassifier(n_neighbors3,weightsdistance)knn.fit(X_train,y_train)# 训练存储数据y_predknn.predict(X_test)# 预测accuracyknn.score(X_test,y_test)# 评估print(fTest accuracy:{accuracy:.3f})6. KNN算法优缺点总结优点原因简单直观易于理解实现原理完全基于距离和投票无需复杂数学推导无需训练过程懒惰学习只需存储数据新数据到来时即时计算天然支持多分类多数表决机制自然支持任意类别数能处理非线性问题决策边界可以是任意复杂形状不假设数据分布对异常值不敏感K较大时K值增大时个别离群点被多数邻居稀释缺点原因计算开销大预测慢每次预测都需要遍历或搜索大量训练样本内存消耗高需要存储全部训练数据数据量大时不适用维度灾难高维空间中距离区分度下降几乎所有点都差不多远对特征缩放敏感距离计算受量纲影响大必须做标准化或归一化样本不平衡问题多数类容易主导投票结果需要适当加权或重采样7. 机器学习知识补充超参数的确定K就是一个典型的超参数需要人为设定。如何系统化地选出最优K这就要用到交叉验证和网格搜索。7.1 交叉验证Cross-Validation思想将训练数据分成n份依次用其中1份作为验证集其余n-1份作为训练集重复n次训练和验证得到n个评估分数最终取平均作为模型的性能指标。这就是n折交叉验证。为什么要这样做单次划分的训练/验证集可能带有偶然性交叉验证通过多次“换着来”使得评估结果更加稳定、可信。能有效检测模型是否稳定防止因某次数据分割的“运气”而得到误导性的好成绩。单独使用交叉验证也是有意义的它可以用来评估给定超参数下模型的泛化能力而不仅仅是服务于网格搜索。7.2 网格搜索Grid Search当有多个超参数需要调节时手动尝试每一种组合非常繁琐。网格搜索的做法是为每个超参数指定一个候选值的列表。生成所有参数组合的“网格”。对每一组组合使用交叉验证评估模型表现。选出交叉验证平均得分最高的那一组参数作为最终选择。比如我们为KNN设定候选n_neighbors[3,5,7,9]weights[uniform,distance]网格搜索会遍历这 4×28 种组合找出最优搭配。7.3 sklearn实现GridSearchCVfromsklearn.model_selectionimportGridSearchCVfromsklearn.neighborsimportKNeighborsClassifier# 定义KNN模型knnKNeighborsClassifier()# 超参数网格param_grid{n_neighbors:[3,5,7,9,11],weights:[uniform,distance],metric:[euclidean,manhattan]}# 5折交叉验证的网格搜索grid_searchGridSearchCV(knn,param_grid,cv5,scoringaccuracy)grid_search.fit(X_train,y_train)print(最佳参数组合:,grid_search.best_params_)print(最佳交叉验证分数:,grid_search.best_score_)# 使用最佳模型预测best_knngrid_search.best_estimator_ test_scorebest_knn.score(X_test,y_test)print(测试集准确率:,test_score)常用参数说明estimator待调参的模型。param_grid参数字典键为参数名值为要尝试的列表。cv交叉验证折数默认为5。scoring评估指标如accuracy、f1等。训练完后best_params_和best_score_可查看最优结果。希望这篇笔记能帮你理清 KNN。KNN作为最“佛系”的机器学习算法不训练模型靠“邻里关系”做决策。理解它的距离度量、KD树加速原理、K值对偏差方差的影响以及如何用交叉验证和网格搜索调优。以上为个人学习总结旨在梳理个人理解。如有疏漏或不当之处欢迎指正与交流。如果文章对你有帮助别忘了点个赞、留个言让更多的小伙伴看到 我们下篇再见
