从“找邻居”到“做判断”:理解 K 近邻与决策树
前言
学习机器学习时,一个很自然的问题是:给计算机一些已经标注好的例子,它怎样判断一个没见过的新样本?
比如,我们记录了一批水果的重量和直径,也知道它们分别是苹果还是橘子。现在拿来一个新水果,只告诉模型它的重量和直径,希望模型预测它的类别。
K 近邻和决策树给出了两种直观的思路:前者寻找相似的例子,后者沿着学到的判断规则一步步做决定。
这篇文章以分类问题为主,介绍它们的原理、容易踩的坑和基本用法。
一、先分清特征与标签
在水果分类中,一条数据可以写成这样:
| 重量(克) | 直径(厘米) | 类别 |
|---|---|---|
| 150 | 7.0 | 苹果 |
| 130 | 6.5 | 橘子 |
重量和直径是特征,类别是标签。前两列组成输入 X,最后一列是目标 y。
训练时,模型能看到特征和标签;预测时,模型根据新样本的特征推断标签。这属于监督学习。
下面的水果例子只用于解释算法。现实中两种水果的重量和直径可能高度重叠,是否能分清,需要用实际数据检验。
二、K 近邻:看看附近的样本属于哪一类
K 近邻(K-Nearest Neighbors,简称 KNN)的核心步骤很简单:
- 计算新样本与训练样本之间的距离。
- 找到距离最近的 K 个样本。
- 根据这些邻居的标签投票,得到预测类别。
假设 K = 3,离新水果最近的三个邻居分别是苹果、苹果、橘子,那么在等权投票下,模型会预测它是苹果。
这里的 K 表示参与判断的邻居数量,和数据有多少个类别没有关系。KNN 也不同于 K-Means:前者在这里使用已有标签进行分类,后者是一种聚类算法。
1. “相近”怎样计算?
常见选择是欧氏距离。对于两个二维样本 (a₁, a₂) 和 (b₁, b₂):
1 | d(a, b) = √[(a₁ - b₁)² + (a₂ - b₂)²] |
推广到多个特征,就是把每一维的差的平方加起来,再开平方。
不过,距离的定义必须适合数据。数字接近不一定代表语义接近,比如把城市编码为 1、2、3,并不能据此说城市 1 比城市 3 更接近城市 2。
2. 为什么通常要缩放特征?
水果的重量可能相差几十克,直径却只相差几厘米。直接计算欧氏距离时,重量这一维可能主导结果,直径的影响被压小。
常见处理是标准化:
1 | 标准化后的值 = (原值 - 训练集均值) / 训练集标准差 |
它可以减少量纲带来的影响,但不会自动判断哪个特征更重要。
还有一个关键细节:均值和标准差应只从训练数据中计算,再用于转换验证集、测试集和新样本。 提前用完整数据标准化,会把测试集的信息带进训练流程,造成数据泄漏。
3. K 应该选多大?
K 太小,判断容易受局部噪声影响。例如 K = 1 时,最近的那个样本如果标错了,预测也可能跟着出错。
K 太大,又可能把较远、属于其他区域的样本一起纳入判断,抹平原本有意义的局部差异。
通常可以尝试多个 K 值,通过验证集或交叉验证选择。二分类中使用奇数 K 能减少等权投票的平票,但多分类或加权投票仍可能出现平局,不能把“选奇数”当成完整解决方案。
4. 邻居也可以有不同权重
除了每个邻居一票,还可以让距离更近的邻居有更大影响。例如使用与距离倒数相关的权重。
这样可以表达“特别接近的样本更值得参考”,但是否有效仍要验证。scikit-learn 提供了等权和距离加权两种常用设置,分别对应 weights="uniform" 和 weights="distance"。参见 KNN 官方文档。
5. KNN 的成本在哪里?
KNN 通常不需要训练一组复杂的模型参数,而是保存训练样本,并可能构建搜索索引,所以常被称为“惰性学习”。
预测时却需要寻找邻居。使用朴素遍历,对一个新样本计算全部距离的成本约为 O(n × d),其中 n 是训练样本数,d 是特征维度;筛选邻居还需要额外工作。
搜索索引可以改善部分场景,但高维数据会让距离变得不那么有区分力,索引的加速效果也可能下降。因此,KNN 在大样本、高维或严格低延迟的场景下需要谨慎评估。
三、决策树:把判断拆成一串问题
决策树可以理解为一套从数据中学到的条件判断。
下面是一棵用于解释结构的示意树,阈值是人为举例,并非对真实水果数据训练得到:
1 | 重量 ≤ 140 克? |
最上面的判断是根节点,中间的判断是内部节点,最后给出预测的是叶节点。新样本从根节点开始,根据条件选择分支,直到到达叶节点。
这种形式很像 if / else,区别在于:训练算法会从数据中选择特征和阈值。
1. 怎样选择一个“好问题”?
假设某个节点有 10 个水果,其中 5 个苹果、5 个橘子,类别很混杂。
如果按某个条件划分后,左边全是苹果、右边全是橘子,这次划分就很有价值。若划分后两边仍然各有一半苹果、一半橘子,帮助就很小。
决策树需要一个指标来衡量这种混杂程度。常见指标之一是基尼不纯度:
1 | Gini = 1 - Σ pᵢ² |
其中 pᵢ 表示节点中第 i 类样本的比例。
对于苹果和橘子各占一半的节点:
1 | Gini = 1 - 0.5² - 0.5² = 0.5 |
如果全是苹果:
1 | Gini = 1 - 1² - 0² = 0 |
基尼不纯度越低,节点中的类别越集中。
2. 划分后,要考虑子节点的大小
不能只看其中一个子节点有多纯,还要计算所有子节点的加权不纯度。
例如,原来的 10 个样本被分成两组:
- 左边 4 个,全是苹果,基尼不纯度为 0。
- 右边 6 个,包含 1 个苹果和 5 个橘子,基尼不纯度为
5/18。
划分后的加权不纯度是:
1 | (4/10) × 0 + (6/10) × (5/18) = 1/6 ≈ 0.167 |
相比原来的 0.5,这次划分减少了约 0.333 的不纯度。
训练算法会比较候选划分,并在当前节点选择较好的一个,再对子节点重复这个过程。常见建树方法是贪心的:每一步选择当前较好的划分,不保证得到全局最优的整棵树。
3. 熵、信息增益与不同树算法
另一个常见指标是熵:
1 | H = -Σ pᵢ log₂(pᵢ) |
计算时把 pᵢ = 0 的项视为 0。信息增益就是父节点的熵减去划分后子节点的加权熵。
入门时常见的几个算法名称,可以这样区分:
| 算法 | 常见划分准则与特点 |
|---|---|
| ID3 | 以信息增益选择划分 |
| C4.5 | 使用信息增益率,缓解信息增益偏好取值较多特征的问题 |
| CART | 构建二叉树;分类常用基尼不纯度,回归常用平方误差 |
这只是主要区别,具体实现还涉及连续特征、缺失值和剪枝等处理。scikit-learn 的决策树采用优化的 CART 实现;把 criterion 设置成 entropy 并不会让它变成完整的 ID3 或 C4.5。参见 决策树官方文档。
4. 树为什么容易过拟合?
如果不断划分,树可能长到几乎每个叶节点只剩一个训练样本。训练集上的表现很好,却可能把噪声也记了下来,导致新数据上的表现变差。
常见控制方法包括:
max_depth:限制树的最大深度。min_samples_leaf:限制每个叶节点至少包含多少训练样本。min_samples_split:限制节点继续划分所需的最少样本数。ccp_alpha:控制代价复杂度剪枝,数值越大通常剪枝越强。
具体参数需要通过验证选择。树太浅也可能欠拟合,不能只追求结构简单。
四、用 Python 做一次分类实验
下面使用鸢尾花数据集。它包含花萼、花瓣的长度和宽度,目标是区分三种鸢尾花。
先安装依赖:
1 | pip install scikit-learn |
然后在同一份训练集和测试集上比较两个模型:
1 | from sklearn.datasets import load_iris |
这里用 stratify 尽量保持训练集和测试集中的类别比例一致,用固定随机种子方便复现。Pipeline 将标准化与分类器放在同一流程里,后续做交叉验证时也能让预处理在各折的训练数据上拟合。参见 Pipeline 官方文档。
运行后可以观察准确率,也可以读一读决策树打印出来的规则,看看它主要使用了哪些特征。
这只是一个固定参数、单次划分的入门实验,不能根据它断言哪个算法普遍更好。实际调参应在训练集内部使用交叉验证,最后再用留出的测试集评估一次。类别不平衡时,还应结合精确率、召回率、F1 和混淆矩阵,而不是只看准确率。
五、两种方法怎么选?
| 对比项 | K 近邻 | 单棵决策树 |
|---|---|---|
| 判断依据 | 新样本附近的训练样本 | 从根节点到叶节点的规则 |
| 训练阶段 | 保存样本,可能构建搜索索引 | 搜索划分并构建树 |
| 单次预测 | 需要搜索邻居 | 沿树走一条路径 |
| 特征缩放 | 对距离计算通常很重要 | 通常不需要 |
| 主要调参方向 | K、距离度量、邻居权重 | 深度、叶节点样本数、剪枝 |
| 解释方式 | 展示邻居及其距离 | 展示判断路径,小树更易理解 |
| 常见困难 | 高维、无关特征、存储与搜索成本 | 过拟合,对数据扰动可能敏感 |
当特征之间的距离有明确意义,且数据规模适合做邻居搜索时,可以尝试 KNN。当希望读懂模型的判断规则,或者建立一个表格数据分类基线时,可以尝试浅层决策树。
两者也都能做回归:KNN 回归通常根据邻居目标值求平均或加权平均;常见的平方误差回归树在叶节点输出该节点训练样本目标值的均值。
对我来说,理解这两种算法最有帮助的,是把注意力放回“模型依据什么做判断”:KNN 的关键在于相似性是否合理,决策树的关键在于划分规则是否能适用于新数据。
接下来可以在同一数据集上改变 K 和树的深度,同时观察训练与验证表现。比起只记住算法名称,这样更容易看清欠拟合和过拟合是怎样发生的。
