前言

学习机器学习时,一个很自然的问题是:给计算机一些已经标注好的例子,它怎样判断一个没见过的新样本?

比如,我们记录了一批水果的重量和直径,也知道它们分别是苹果还是橘子。现在拿来一个新水果,只告诉模型它的重量和直径,希望模型预测它的类别。

K 近邻和决策树给出了两种直观的思路:前者寻找相似的例子,后者沿着学到的判断规则一步步做决定。

这篇文章以分类问题为主,介绍它们的原理、容易踩的坑和基本用法。

一、先分清特征与标签

在水果分类中,一条数据可以写成这样:

重量(克) 直径(厘米) 类别
150 7.0 苹果
130 6.5 橘子

重量和直径是特征,类别是标签。前两列组成输入 X,最后一列是目标 y。

训练时,模型能看到特征和标签;预测时,模型根据新样本的特征推断标签。这属于监督学习。

下面的水果例子只用于解释算法。现实中两种水果的重量和直径可能高度重叠,是否能分清,需要用实际数据检验。

二、K 近邻:看看附近的样本属于哪一类

K 近邻(K-Nearest Neighbors,简称 KNN)的核心步骤很简单:

  1. 计算新样本与训练样本之间的距离。
  2. 找到距离最近的 K 个样本。
  3. 根据这些邻居的标签投票,得到预测类别。

假设 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
2
3
4
5
重量 ≤ 140 克?
├── 是:预测为橘子
└── 否:直径 ≤ 7 厘米?
├── 是:预测为橘子
└── 否:预测为苹果

最上面的判断是根节点,中间的判断是内部节点,最后给出预测的是叶节点。新样本从根节点开始,根据条件选择分支,直到到达叶节点。

这种形式很像 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.metrics import accuracy_score

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
iris.data,
iris.target,
test_size=0.3,
random_state=42,
stratify=iris.target,
)

# 标准化只在训练集上拟合,预测时复用相同的转换。
knn = make_pipeline(
StandardScaler(),
KNeighborsClassifier(n_neighbors=5),
)

# 常规决策树按单个特征的阈值划分,通常不需要标准化。
tree = DecisionTreeClassifier(
max_depth=3,
min_samples_leaf=2,
random_state=42,
)

for name, model in [("KNN", knn), ("Decision Tree", tree)]:
model.fit(X_train, y_train)
prediction = model.predict(X_test)
print(f"{name} accuracy: {accuracy_score(y_test, prediction):.3f}")

print("\n决策树学到的规则:")
print(export_text(tree, feature_names=list(iris.feature_names)))
print("类别编号对应关系:", dict(enumerate(iris.target_names)))

这里用 stratify 尽量保持训练集和测试集中的类别比例一致,用固定随机种子方便复现。Pipeline 将标准化与分类器放在同一流程里,后续做交叉验证时也能让预处理在各折的训练数据上拟合。参见 Pipeline 官方文档。

运行后可以观察准确率,也可以读一读决策树打印出来的规则,看看它主要使用了哪些特征。

这只是一个固定参数、单次划分的入门实验,不能根据它断言哪个算法普遍更好。实际调参应在训练集内部使用交叉验证,最后再用留出的测试集评估一次。类别不平衡时,还应结合精确率、召回率、F1 和混淆矩阵,而不是只看准确率。

五、两种方法怎么选?

对比项 K 近邻 单棵决策树
判断依据 新样本附近的训练样本 从根节点到叶节点的规则
训练阶段 保存样本,可能构建搜索索引 搜索划分并构建树
单次预测 需要搜索邻居 沿树走一条路径
特征缩放 对距离计算通常很重要 通常不需要
主要调参方向 K、距离度量、邻居权重 深度、叶节点样本数、剪枝
解释方式 展示邻居及其距离 展示判断路径,小树更易理解
常见困难 高维、无关特征、存储与搜索成本 过拟合,对数据扰动可能敏感

当特征之间的距离有明确意义,且数据规模适合做邻居搜索时,可以尝试 KNN。当希望读懂模型的判断规则,或者建立一个表格数据分类基线时,可以尝试浅层决策树。

两者也都能做回归:KNN 回归通常根据邻居目标值求平均或加权平均;常见的平方误差回归树在叶节点输出该节点训练样本目标值的均值。

对我来说,理解这两种算法最有帮助的,是把注意力放回“模型依据什么做判断”:KNN 的关键在于相似性是否合理,决策树的关键在于划分规则是否能适用于新数据。

接下来可以在同一数据集上改变 K 和树的深度,同时观察训练与验证表现。比起只记住算法名称,这样更容易看清欠拟合和过拟合是怎样发生的。