04 · 从问题进入原章节
kNN 的 k 与 KDE 的带宽 h 都影响平滑,结果为何不同?
kNN 先找邻居再投票或平均;KDE 把每个样本变成密度贡献。决策树又用另一种方式保存局部结构。
读后可检查:能按输出类型、平滑旋钮和预测成本选择方法,而不把非参数等同于保存全部样本。
📑 本页目录(点开跳转)
04 · 非参数方法:从邻居投票到密度估计
⏱ 26 分钟 | 原预计,仅供参考;可以分次读 | ⭐ 核心概念
🎯 一句话
kNN 用附近样本的答案预测新样本;KDE 用样本的位置估计哪里更常出现数据。 两者都利用局部信息,但一个预测标签或数值,一个估计密度。
“非参数”不是“没有参数”,也不是“完全不做假设”。更准确地说,这类方法通常不把可学习的函数限制在一个固定有限个参数描述的函数族里,复杂度可以随数据量调整。
第一次读,先完成一个 3-NN 例子,再看三种“邻近加权”的区别。一致性定理可以第二遍再读。
⚖️ 一、两种范式的根本区别
先比较具体模型,别把某个例子的特点当成整类方法的定律。
| 要比较什么 | 参数方法的例子:线性回归 | 非参数方法的例子:kNN |
|---|---|---|
| 预测依据 | 特征与已学到的权重 | 查询点附近的训练样本 |
| 数据增加后 | 特征数不变时,权重个数不变 | 可存入更多样本,并重新选择邻居数 |
| 学习时做什么 | 拟合权重 | 保存样本;也可能建立检索索引 |
| 部署时保留什么 | 通常保留权重与预处理信息 | 通常保留样本、标签与检索所需信息 |
“要不要保存全部数据”不是分类标准。 决策树通常归为非参数方法,却可以只保存树结构、阈值与叶子输出;不必把训练数据全部带到预测环境。
参数方法也不等于“只能画直线”:固定结构的神经网络同样属于参数模型,能表示很复杂的非线性关系。
🔬 偏差与方差:看约束强弱,不只看分类名
- 约束太强:模型可能抓不住真实规律。这是偏差偏大的风险。
- 过度追随样本:换一批训练数据,预测就变很多。这是方差偏大的风险。
- 约束合适:在当前数据下兼顾拟合与稳定,需要用验证结果判断。
非参数方法仍依赖假设,例如“在选定的距离下,附近样本的答案有参考价值”。参数方法也可能因参数很多、正则化不足而有很高的方差。
这里先记住一个动作:观察验证表现如何随复杂度变化。第 8 章会进一步解释偏差与方差。
🎯 二、kNN:先找邻居,再汇总答案
kNN 中的小写 $k$ 表示“参考几个邻居”。先看一维数据:输入 $x$ 是一个数,分类标签用 0 和 1 表示两类。
要预测的新输入是 2.2,选 3 个最近邻,采用等权投票。
| 训练输入 $x_i$ | 类别 | 与 2.2 的距离 | 选入最近 3 个? |
|---|---|---|---|
| 0 | 0 | 2.2 | 否 |
| 1 | 0 | 1.2 | 是,第 2 近 |
| 3 | 1 | 0.8 | 是,第 1 近 |
| 4 | 1 | 1.8 | 是,第 3 近 |
结果:预测类别 1。 入选邻居的标签是 1、0、1,类别 1 得到两票。
同样三个邻居也可以用于回归。如果它们对应的目标数值依次是 30、10、40,预测就是三者的平均值,约 26.67。
运行这个例子:核对邻居顺序、分类与回归结果
需要已安装 NumPy 和 scikit-learn。下面是完整代码,可以放进一个新的 Python 文件运行,不依赖前文变量。
import numpy as np
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
X = np.array([[0.0], [1.0], [3.0], [4.0]])
query = np.array([[2.2]])
class_labels = np.array([0, 0, 1, 1])
regression_targets = np.array([0.0, 10.0, 30.0, 40.0])
classifier = KNeighborsClassifier(n_neighbors=3)
classifier.fit(X, class_labels)
distances, indices = classifier.kneighbors(query)
print("邻居输入:", X[indices[0], 0].tolist())
print("邻居距离:", distances[0].round(1).tolist())
print("分类结果:", int(classifier.predict(query)[0]))
regressor = KNeighborsRegressor(n_neighbors=3)
regressor.fit(X, regression_targets)
print("回归结果:", round(float(regressor.predict(query)[0]), 2))
duplicate_X = np.array([[0.0], [0.0]])
duplicate_y = np.array([0, 1])
one_neighbor = KNeighborsClassifier(n_neighbors=1)
one_neighbor.fit(duplicate_X, duplicate_y)
accuracy = one_neighbor.score(duplicate_X, duplicate_y)
print("冲突标签例的训练准确率:", accuracy)
这里的 kneighbors 返回距离和训练行号;X[indices[0], 0] 才是按距离排好的输入值。分类器统计标签票数,回归器对目标数值取平均。
| 观察哪一行输出 | 本例结果 | 它说明什么 |
|---|---|---|
| 邻居输入 | 3.0、1.0、4.0 | 先按距离选样本,不按类别选 |
| 邻居距离 | 0.8、1.2、1.8 | 与上表一致 |
| 分类结果 | 1 | 三票中两票为 1 |
| 回归结果 | 26.67 | 同一组邻居,可以汇总不同类型的答案 |
| 冲突标签例的训练准确率 | 0.5 | 同一个输入有两个相反标签,1-NN 也不能全对 |
这只是核对算法的微型例子,不是模型效果评估。真实任务仍需在没参与拟合的数据上验证。
k 是局部平滑的旋钮
| 等权 kNN 的选择 | 预测会发生什么 | 要防什么 |
|---|---|---|
| $k=1$ | 只参考最近一个样本 | 对噪声或个别样本敏感 |
| $k$ 增大 | 汇总更多邻居 | 太远的样本可能混进来 |
| $k=n$ | 分类输出全体的多数类;回归输出全体均值 | 忽略输入差异;分类平票还需约定规则 |
这些是常见趋势,不是“某个 $k$ 一定过拟合”的判决。上表的常数输出结论针对等权汇总,不能直接套到距离加权版本。
1-NN 的训练误差并非恒为零。 只有把训练点本身放在候选邻居中,且没有冲突的重复输入等问题时,才会出现“每个点找回自己,训练集全对”。
前面代码的反例只有两个样本:输入都为 0,标签分别为 0 和 1。对相同输入给同一预测的分类器,不可能同时答对两个标签。
用验证集或交叉验证选择 $k$,不要凭训练集全对就宣布学会了。这和基础教程第 1 章的决策树例子相通:复杂度旋钮需要用未参与拟合的数据来选择。
四个实践要点
1.先检查特征尺度。 如果一个特征用元、另一个用岁,欧氏距离可能主要受金额影响。经常需要标准化,但要先判断不同特征的差异应该如何比较。
标准化的均值与标准差只能从训练数据拟合;交叉验证时放进 Pipeline,每折只用该折训练部分拟合。不要先对全量数据标准化再划分。
2.距离必须符合任务。 欧氏距离、曼哈顿距离、余弦距离各有适用语境。曼哈顿距离对单维大差异的惩罚不同,但这不等于它天然能处理所有离群点;余弦常用于比较向量方向,零向量还需单独处理。
3.可以给近邻更高权重。 距离反比或高斯型权重都可用于加权投票、加权平均。但仍要说明“从哪些样本中加权”,并处理零距离,不能直接算出 1/0。
4.奇数 k 只解决一种平票。 对二分类、等权投票,奇数票数能避免类别票数相同。多分类、距离加权,以及第 $k$ 个与第 $k+1$ 个样本等距的问题,仍需要平票约定。
这些实现细节与 scikit-learn 的近邻使用说明对应。
⚡ 预测慢怎么办
先明确成本:朴素 kNN 对一次查询逐个计算 $n$ 个训练点的距离,每点有 $d$ 个特征,距离计算量是 $O(nd)$。
找出最近的 $k$ 个还需要选择或排序。若把全部距离完整排序,会再有 $O(n\log n)$ 的成本;不必每次都这样实现。
| 可尝试的办法 | 可能得到什么 | 需要实测的代价 |
|---|---|---|
| KD-Tree / Ball-Tree | 在适合的维度、分布下减少搜索量 | 建索引成本;高维时加速可能变差 |
| HNSW / IVF 等近似最近邻索引 | 更快找到“足够近”的候选 | 召回率、延迟、内存与更新成本 |
| PCA 等降维后再检索 | 缩小表示,减少距离计算量 | 是否丢失了与任务有关的信息 |
没有统一的“低于 20 维就快”或“必定加速几百倍”。索引方法、数据量、数据分布和机器环境都会影响结果。
向量检索是 RAG、以图搜图和推荐系统的一项基础能力,但这些系统还包含编码、过滤、排序等环节,不能把整个系统都等同于 kNN。
🌾 三、同样利用邻近信息,输出却不同
先分清三个问题,再看公式。
| 方法 | 参考哪些数据 | 输出是什么 |
|---|---|---|
| 加权 kNN | 通常先选最近 $k$ 个,再汇总它们的标签或数值 | 预测类别或数值 |
| 核回归 | 按距离给目标数值加权,再除以总权重 | 预测数值 |
| 核密度估计 KDE | 只用输入的位置,不需要目标标签 | 估计输入的概率密度 |
因此,加权 kNN 不会自动变成“所有点都参与”。高斯核回归通常让所有点都有非零权重;使用有限支撑的核时,远处点也可能权重为零。
KDE:每个点贡献一个小钟形
继续使用输入 0、1、3、4。这里不再使用它们的类别或回归目标,只问:“数据在哪些位置更密集?”
下面取高斯核,带宽 $h=1$。四条虚线各贡献总面积的四分之一;实线是它们逐点相加的结果。
在 2.2 处,四个样本的贡献约为:
| 样本位置 | 对密度高度的贡献 |
|---|---|
| 0 | 0.00887 |
| 1 | 0.04855 |
| 3 | 0.07242 |
| 4 | 0.01974 |
相加得到密度约 0.14958。 这不是“输入恰好等于 2.2 的概率是 14.958%”。连续变量的区间概率看曲线下的面积,不看单点高度。
想核对公式:每一项怎么对应上面的曲线?
一维 KDE 的公式是:
$$\hat p(x)=\frac{1}{nh}\sum_{i=1}^{n}K\!\left(\frac{x-x_i}{h}\right)$$
- $x$:现在想查看密度的位置,本例是 2.2。
- $x_i$:第 $i$ 个训练输入;$n=4$ 是样本数。
- $h>0$:带宽,决定每个钟形的宽度。
- $K(u)$:核函数。本例用标准高斯密度:
$$K(u)=\frac{1}{\sqrt{2\pi}}e^{-u^2/2}$$
先算与一个样本相差多远,除以带宽,把结果送进 $K$;再除以 $nh$,得到它对总密度的贡献。最后对所有样本相加。
核需要满足非负、积分为 1;外面的 $1/h$ 补偿横向伸缩,$1/n$ 把总面积保持为 1。这里的核函数 $K$ 不是 kNN 的邻居数 $k$。
高维版本仍保留。 若输入有 $d$ 维、使用同一带宽缩放所有坐标,归一化因子变成 $h^d$:
$$\hat p(x)=\frac{1}{nh^d}\sum_{i=1}^{n}K\!\left(\frac{x-x_i}{h}\right)$$
这里 $K$ 是在 $d$ 维空间上积分为 1 的核。不能把一个未经归一化的距离反比权重直接当成密度核。
密度可以大于 1。 只有一个样本、带宽为 0.1 时,高斯 KDE 在样本中心的密度约 3.989;整条曲线的面积仍是 1。这与概率不能超过 1 并不矛盾。
带宽 h 控制平滑程度
- h 小:单个钟形窄,容易看出局部细节,也更容易追随采样噪声。
- h 大:单个钟形宽,估计更平滑,也可能把几个不同的峰混在一起。
邻居数 $k$ 和带宽 $h$ 都影响平滑,但不是同一个量。$k$ 固定参考点的数量;$h$ 固定距离的尺度,同样的带宽在密集区和稀疏区覆盖的样本数量会不同。KDE 的实现与带宽示例见官方密度估计说明。
核回归与 SVM 的“核”,又分别指什么?
核回归用得到目标值 $y_i$。 设 $w_i$ 是按查询位置计算出的非负权重;总权重大于 0 时,预测为:
$$\hat y(x)=\frac{\sum_i w_i y_i}{\sum_i w_i}$$
用前面四个输入、高斯权重、$h=1$,但加入目标值 0、10、30、40,查询 2.2 的核回归结果约为 23.05。KDE 对同一位置输出的却是密度 0.14958:两者回答的是不同问题。
SVM 的核见第 6 章:它表示特征空间中的内积,用来计算相似性,不要求像概率密度一样积分为 1。
高斯型函数可以同时出现在这两类语境中,但它的作用、归一化条件不同。不要因名称相同就把公式互换。
🌲 四、决策树:非参数不等于保存全部样本
决策树在训练时决定在哪里分裂、形成多少叶子,通常归入非参数方法。它训练后只保留树也能预测,这不是它“又变成参数方法”的理由。
若提前限制最大深度或叶子数,容量就受到上限约束。因此,讨论学习能力时还要说明这些限制是否允许随数据量改变。
另一个独立的分类维度是“把主要工作放在什么时候”。
| 学习方式 | 训练与预测时的工作 | 常见例子 |
|---|---|---|
| 惰性学习 | 保存数据,可能先建索引;查询时再做局部计算 | kNN;直接实现的核回归、KDE |
| 急切学习 | 训练时先归纳结构或权重;预测时使用已学表示 | 决策树、线性模型、神经网络 |
这不是“前者完全不训练、后者预测必定很快”的定律。建索引也要计算;很大的树或网络也有预测成本。
新增样本通常不必重新拟合一整组 kNN 权重,但更新不是免费的。 新物品仍需要可用特征或向量,还可能需要标签、索引维护和质量检查。把新物品放进检索索引,并不自动解决冷启动时缺少偏好信息的问题。
🔬 五、非参数方法的理论性质
一致性:更多数据最终能到哪里?
在规定条件下,kNN 分类器的平均测试误差可以趋近贝叶斯最优误差。 贝叶斯最优误差是:在当前输入信息与数据分布下,理论上能达到的最低分类错误率。
它不一定为零。例如同一种输入有时对应类别 0、有时对应类别 1,只看输入就不可能总是猜对。
定理的条件:为什么不能一直固定 k?
这里讨论有限维欧氏空间中的二分类。训练数据与新测试样本独立地来自同一个固定分布;对等距离的邻居采用与标签无关的随机破平规则。
随着样本数 $n$ 增长,邻居数 $k_n$ 要同时满足:
$$k_n\longrightarrow\infty$$
参考样本逐渐增加,才能减小局部投票的波动。
$$\frac{k_n}{n}\longrightarrow 0$$
参考的比例逐渐减小,才能继续关注查询点附近,而不是把整个人群混在一起。
在这些条件下,对训练样本随机性取平均的测试错误率趋近贝叶斯最优误差。这是弱一致性的结论,不是在保证每个有限训练集都表现好,也不是在这里证明更强的逐样本几乎处处收敛。
$k_n=\lfloor\sqrt n\rfloor$ 是满足上述两个极限的一个例子,不是通用的最优调参公式。始终固定 $k=1$ 或 $k=5$ 则不满足第一条,不能据此声称普遍一致。
这里没有把分类定理直接推广到所有回归目标;回归还需要相应的矩条件等假设。定理及平票处理可查 Collins、Kumari 与 Pestov 对 Stone 定理的说明,定理 3.6。
⚠️ 但“足够多”是多少?
一致性描述无限增加数据时的极限,不直接告诉你现在这几千条数据够不够。
用一个几何计数理解高维的困难:把每个坐标都限制在 0 到 1,每轴分成 10 格。
| 维度 | 小格子数 |
|---|---|
| 1 维 | 10 |
| 2 维 | 100 |
| 20 维 | $10^{20}$ |
一般地,若每轴小格边长为 $\varepsilon$,且 $1/\varepsilon$ 是整数,格子数是 $\varepsilon^{-d}$。这是覆盖空间的格子数,不是任意数据、任意预测误差都适用的样本量公式。
数据若集中在低维结构上,或只有少量特征真正有关,困难可能比这张满空间网格小得多。20 维、50 维都不是算法必然失效的分界线。
因此要检查距离是否仍有意义,并用验证结果判断,而不是把理论结论当成有限样本保证。下一章的维度灾难会继续这个问题。
⚖️ 六、什么时候值得试?
| 当前情况 | 可以做的尝试 | 不要直接得出的结论 |
|---|---|---|
| 特征不多,邻近样本的答案相似 | 把 kNN 当基线,验证距离与 $k$ | “非参数一定更准” |
| 关系非线性、分布多峰 | 比较 kNN、树、核方法及合适的参数模型 | “参数模型只能拟合简单规律” |
| 样本常更新 | 评估追加数据、维护索引的成本 | “无需任何更新工作” |
| 向量维度高 | 检查表示质量、有效维度与检索召回率 | “超过 50 维就彻底失效” |
| 数据少或噪声多 | 控制平滑强度,与简单正则化模型比较 | “小数据绝不能用非参数方法” |
| 对延迟或解释有要求 | 测试索引;展示参考邻居并检查它们是否可靠 | “邻居例子就是因果解释” |
核心权衡是当前假设、样本量、表示质量与计算成本是否匹配。 不知道函数长什么样时,仍然需要判断“相近输入的答案应当相近”是否合理。
🔗 七、和站内其他章的关系
| 去哪里 | 带着什么问题去 |
|---|---|
| 基础教程第 4 章决策树 | 树如何在训练时学出结构,而不是在查询时找邻居? |
| 推荐算法的 ItemCF | 物品相似性如何计算?如何汇总相似物品的信号? |
| 推荐算法的向量检索 ANN | 检索速度、召回率和内存如何取舍? |
| RAG 的向量检索 | 检索到相近内容以后,还需要哪些过滤与生成步骤? |
| 第 6 章核技巧 | “局部加权”和“特征空间内积”有什么区别? |
| 第 5 章维度灾难 | 维度、距离与样本覆盖怎么相互影响? |
ItemCF 经常利用近邻思想,但相似度构建、预测或排序方式与本章的 kNN 分类器不必完全相同。向量数据库也不只是“给 kNN 加速”:数据管理、过滤和索引更新都是它的工作。
✅ 检查点
- “非参数”是什么意思?是否代表没有假设、必须保存全部数据?
- 偏差与方差为什么不能仅凭“参数 / 非参数”的名字判断?
- $k$ 控制什么?1-NN 训练集全对需要什么条件?
- 什么时候应检查标准化?为什么轴对齐树通常不依赖这种缩放?
- KDE 的 $h$ 与 kNN 的 $k$ 有何区别?KDE 是否使用目标标签?
- 惰性学习在更新时有什么便利,又有哪些成本?
- 一致性保证什么、不保证什么?高维网格计数能否当成普遍误差公式?
- 比较两类方法时,应该验证哪些取舍?
核对答案:每题只看对应的一项
-
非参数方法通常不固定在有限参数的函数族中,容量可以随数据调整;仍有距离等假设,也不一定保存全部样本。
-
偏差与方差受模型容量、平滑或正则化强度、样本量与数据分布共同影响。名字不是误差的保证。
-
$k$ 决定参考多少邻居。把自己放进参考集且没有冲突重复输入等问题时,1-NN 才能轻易获得零训练误差;这不代表测试集表现好。
-
距离受各维数值尺度影响;需要结合单位和任务判断是否缩放。常见轴对齐树按特征值顺序找阈值,严格单调缩放不改变可作出的分割;它不按欧氏距离找邻居。
-
$k$ 控制数量,$h$ 控制距离尺度。KDE 只用输入位置估计密度;核回归才汇总目标数值。
-
kNN 可以追加样本而不重新拟合整组权重;仍可能需要特征处理、标签、索引更新和验证。
-
条件成立时,平均测试误差渐近达到贝叶斯最优;不保证有限样本够好。$\varepsilon^{-d}$ 在这里是网格数量,不是通用样本复杂度。
-
比较验证误差、距离或模型假设、样本量与维度、存储、更新和查询成本;不要预设某一类必胜。
本节回顾
先记住这三件事
- kNN 汇总邻居的答案;KDE 估计输入的密度,两者的输出不同。
- 先检查距离与尺度,再验证邻居数或带宽;训练集全对不等于泛化好。
- 非参数不等于没有假设;一致性也不等于现在的数据量已经足够。
下一节 👉 05-维度灾难.md