当前位置：首页 > news >正文

【机器学习】非线性分类算法详解（下）：决策树（最佳分裂特征选择的艺术）与支持向量机（最大间隔和核技巧）

news 2025/8/3 6:14:08

文章目录

三、决策树：基于规则的"层层筛选"
- 1、核心思想：分而治之
- 2、分裂准则：信息增益（减少不确定性）
- - 数学公式
  - 具体例子
  - 作用总结
- 3、基尼指数（数据纯度衡量）：CART算法的选择
- - 数学公式
  - 例子
  - 在决策树中的应用
- 4、工作原理：递归构建
- 5、优势与适用场景
四、支持向量机（SVM）：基于间隔的"边界守卫"
- 1、核心思想：最大间隔分类
- - 1.1、数学表达
  - 1.2、具体例子
  - 1.3、支持向量：决策边界的核心
  - 1.4、SVM间隔设计的优势总结
- 2、优化目标：间隔最大化
- 3、对偶形式：核技巧的基础（ing）
- 4、核技巧：非线性分类的关键
- 5、SVM的工作步骤
- 6、SVM算法总结
四种算法综合对比

在上一篇中，我们深入解析了KNN和朴素贝叶斯这两种基于距离和概率的分类算法。本篇将继续探讨两种更复杂的非线性分类算法：决策树和支持向量机（SVM）。这两种算法分别代表了基于规则的"层层筛选"和基于间隔的"边界守卫"思想。

三、决策树：基于规则的"层层筛选"

1、核心思想：分而治之

决策树的核心思想非常直观：通过一系列"是/否"问题逐步缩小搜索空间，最终将复杂问题分解为简单的规则组合。就像医生诊断疾病时，会先问"有没有发烧"，再问"有没有咳嗽"，通过层层筛选最终确定病因。

根节点：特征1 < 阈值1?
├─ 是 → 叶节点1：预测类别A（80%样本）
└─ 否 → 特征2 < 阈值2?├─ 是 → 叶节点2：预测类别B（90%样本）└─ 否 → 叶节点3：预测类别C（85%样本）

数学表达：
决策树通过递归地分割特征空间来构建分类规则。每个内部节点代表一个特征测试，每个叶节点代表一个类别预测：

$\sum_{m=1}^M c_m \mathbb{I}(x \in R_m)$

各部分含义：

$f (x)$ ：决策树的预测函数
$M$ ：决策树中叶节点的总数
$R_m$ ：第 $m$ 个区域（对应一个叶节点）
$c_m$ ：第 $m$ 个区域的预测值（通常是该区域中多数类别的标签）
$I(x∈Rm)\mathbb{I}(x \in R_m)$ ：指示函数，判断样本 $x$ 是否属于区域 $R_m$

指示函数 $I(x∈Rm)\mathbb{I}(x \in R_m)$

$Rm\mathbb{I}(x \in R_m) = \begin{cases} 1 & \text{如果 } x \text{ 属于区域 } R_m \\ 0 & \text{如果 } x \text{ 不属于区域 } R_m \end{cases}$

例子说明

假设我们有一个决策树，有3个叶节点（区域）：

决策树结构：

根节点：年龄 < 30?
├─ 是 → 叶节点1：预测"年轻"
└─ 否 → 收入 > 50000?├─ 是 → 叶节点2：预测"高收入"└─ 否 → 叶节点3：预测"普通"

公式计算：
$c_1 \cdot \mathbb{I}(x \in R_1) + c_2 \cdot \mathbb{I}(x \in R_2) + c_3 \cdot \mathbb{I}(x \in R_3)$

其中：

$c_1 = "年轻"$
$c_2 = "高收入"$
$c_3 = "普通"$

预测过程：

如果样本 $x$ 属于区域 $R_1$ ： $\cdot 1 + "高收入" \cdot 0 + "普通" \cdot 0 = "年轻"$
如果样本 $x$ 属于区域 $R_2$ ： $\cdot 0 + "高收入" \cdot 1 + "普通" \cdot 0 = "高收入"$
如果样本 $x$ 属于区域 $R_3$ ： $\cdot 0 + "高收入" \cdot 0 + "普通" \cdot 1 = "普通"$

公式的直观理解:

决策树将特征空间分割成 $M$ 个区域
每个区域 $R_m$ 对应一个预测值 $c_m$
对于新样本 $x$ ，找到它属于哪个区域
返回该区域的预测值

注意：每个样本只能属于一个区域

2、分裂准则：信息增益（减少不确定性）

数学公式

决策树的关键在于如何选择最佳分裂特征。最常用的分裂准则是信息增益：

$\sum_{v=1}^V \frac{|D_v|}{|D|} H(D_v)$

其中， $H (D)$ 是数据集 $D$ 的熵：

$-\sum_{k=1}^K p_k \log_2 p_k$

$H (D)$ ：分裂前数据集的熵（不确定性）
$∑v=1V∣Dv∣∣D∣H(Dv)\sum_{v=1}^V \frac{|D_v|}{|D|} H(D_v)$ ：分裂后各子集的加权平均熵
$V$ ：特征 $A$ 的可能取值数量
$D_v$ ：特征 $A$ 取值为 $v$ 的子集
$∣Dv∣∣D∣\frac{|D_v|}{|D|}$ ：子集 $D_v$ 在总数据集中的比例

熵的含义：衡量数据集的不确定性或混乱程度

简单理解：

熵越大，数据集越混乱，越难分类
熵越小，数据集越纯净，越容易分类

信息增益衡量的是分裂前后不确定性的减少程度。信息增益越大，说明分裂越有效，能够更好地区分不同类别。

具体例子

假设我们有一个数据集，包含10个样本：

分裂前：

类别A：6个样本
类别B：4个样本

计算分裂前熵：
$-\left(\frac{6}{10}\log_2\frac{6}{10} + \frac{4}{10}\log_2\frac{4}{10}\right) = 0.971$

考虑按特征"年龄"分裂：

年龄<30：5个样本（3个A，2个B）
年龄≥30：5个样本（3个A，2个B）

计算分裂后熵：

年龄<30的熵： $H(D<30)=−(35log⁡235+25log⁡225)=0.971H(D_{<30}) = -\left(\frac{3}{5}\log_2\frac{3}{5} + \frac{2}{5}\log_2\frac{2}{5}\right) = 0.971$
年龄≥30的熵： $H(D≥30)=−(35log⁡235+25log⁡225)=0.971H(D_{\geq30}) = -\left(\frac{3}{5}\log_2\frac{3}{5} + \frac{2}{5}\log_2\frac{2}{5}\right) = 0.971$

加权平均熵：
$510×0.971+510×0.971=0.971\frac{5}{10} \times 0.971 + \frac{5}{10} \times 0.971 = 0.971$

信息增益：
$I G (D, 年龄) = 0.971 - 0.971 = 0$

结果解释：信息增益为0，说明按年龄分裂没有减少不确定性。

更好的分裂例子

考虑按特征"收入"分裂：

收入<50000：6个样本（1个A，5个B）
收入≥50000：4个样本（5个A，0个B）

计算分裂后熵：

收入<50000的熵： $H(D<50000)=−(16log⁡216+56log⁡256)=0.650H(D_{<50000}) = -\left(\frac{1}{6}\log_2\frac{1}{6} + \frac{5}{6}\log_2\frac{5}{6}\right) = 0.650$
收入≥50000的熵： $H(D≥50000)=−(55log⁡255+05log⁡205)=0H(D_{\geq50000}) = -\left(\frac{5}{5}\log_2\frac{5}{5} + \frac{0}{5}\log_2\frac{0}{5}\right) = 0$

加权平均熵：
$610×0.650+410×0=0.390\frac{6}{10} \times 0.650 + \frac{4}{10} \times 0 = 0.390$

信息增益：
$I G (D, 收入) = 0.971 - 0.390 = 0.581$

结果解释：信息增益为0.581，说明按收入分裂显著减少了不确定性。

作用总结

工作原理

信息增益衡量分裂前后不确定性的减少程度：分裂前熵表示原始数据集的混乱程度，分裂后熵表示各子集的加权平均混乱程度，两者之差即为信息增益。信息增益越大，说明该特征的分裂效果越好，能够更有效地区分不同类别。

实际应用

在决策树构建过程中，算法会计算每个特征的信息增益，选择信息增益最大的特征进行分裂。这确保了每次分裂都能最大程度地减少数据的不确定性，从而构建出更有效的分类规则。

3、基尼指数（数据纯度衡量）：CART算法的选择

数学公式

除了信息增益，CART算法使用基尼指数作为分裂准则：

$\sum_{k=1}^K p_k^2$

$p_k$ ：第 $k$ 个类别在数据集中的比例
$∑k=1Kpk2\sum_{k=1}^K p_k^2$ ：所有类别比例平方的和

基尼指数衡量的是数据集的纯度。基尼指数越小，数据集越纯，即同一类别的样本越多。

例子

我们假设类别A、B：指的是垃圾邮件还是正常邮件
例子1：纯净数据集
假设数据集有10个样本，全部属于类别A：

类别A：10个样本（比例：1.0）
类别B：0个样本（比例：0.0）

计算基尼指数：
$Gini(D) = 1 - (1.0^2 + 0.0^2) = 1 - 1 = 0$

结果：基尼指数为0，表示数据集非常纯净。

例子2：混乱数据集
假设数据集有10个样本，均匀分布：

类别A：5个样本（比例：0.5）
类别B：5个样本（比例：0.5）

计算基尼指数：
$Gini(D) = 1 - (0.5^2 + 0.5^2) = 1 - (0.25 + 0.25) = 1 - 0.5 = 0.5$

结果：基尼指数为0.5，表示数据集比较混乱。

例子3：中等纯度数据集
假设数据集有10个样本：

类别A：7个样本（比例：0.7）
类别B：3个样本（比例：0.3）

计算基尼指数：
$Gini(D) = 1 - (0.7^2 + 0.3^2) = 1 - (0.49 + 0.09) = 1 - 0.58 = 0.42$

结果：基尼指数为0.42，表示数据集纯度中等。

在决策树中的应用

在决策树中，我们选择基尼指数减少最多的特征进行分裂。如下基尼增益公式：

$Gini_Gain(D,A)=Gini(D)−∑v=1V∣Dv∣∣D∣Gini(Dv)Gini\_Gain(D, A) = Gini(D) - \sum_{v=1}^V \frac{|D_v|}{|D|} Gini(D_v)$

简单理解：基尼增益 = 分裂前的不纯度 - 分裂后的加权平均不纯度

例子

假设按特征"年龄"分裂：

分裂前基尼指数：0.42
子集1（年轻组）基尼指数：0.3（权重：0.6）
子集2（年长组）基尼指数：0.2（权重：0.4）

基尼增益：
$Gini_Gain=0.42−(0.6×0.3+0.4×0.2)=0.42−0.26=0.16Gini\_Gain = 0.42 - (0.6 \times 0.3 + 0.4 \times 0.2) = 0.42 - 0.26 = 0.16$

结果：基尼增益为0.16，说明分裂后数据更纯了。

假设我们还有另一个特征"收入"：

按收入分裂：

分裂前基尼指数：0.42
子集1（高收入）基尼指数：0.1（权重：0.5）
子集2（低收入）基尼指数：0.1（权重：0.5）

基尼增益：
$Gini_Gain(收入)=0.42−(0.5×0.1+0.5×0.1)=0.42−0.1=0.32Gini\_Gain(收入) = 0.42 - (0.5 \times 0.1 + 0.5 \times 0.1) = 0.42 - 0.1 = 0.32$

比较：

年龄的基尼增益：0.16
收入的基尼增益：0.32

选择：选择基尼增益更大的特征，即"收入"特征。

4、工作原理：递归构建

决策树的构建过程可以概括为以下步骤：

特征选择：计算每个特征的信息增益（或基尼指数），选择增益最大的特征
节点分裂：根据选定的特征将数据集分割成子集
递归构建：对每个子集重复上述过程，直到满足停止条件
叶节点生成：当节点满足停止条件时，将其标记为叶节点

停止条件：

节点中所有样本属于同一类别
节点中样本数量少于预设阈值
树的深度达到预设最大值
信息增益小于预设阈值

5、优势与适用场景

核心优势
决策树具有高度可解释性和处理混合数据能力强两大核心优势。其决策过程可以转化为直观的"如果-那么"规则，能够同时处理数值型和分类型特征，通过信息增益自动识别重要特征，这使得决策树在需要透明决策过程的场景中表现突出。

主要局限
决策树面临容易过拟合和结构不稳定两个关键挑战。树深度过大时会记住训练数据细节，数据微小变化可能导致树结构大幅改变，虽然可以处理回归问题，但在连续输出任务中不如专门的回归算法。

四、支持向量机（SVM）：基于间隔的"边界守卫"

1、核心思想：最大间隔分类

SVM的核心思想是找到能最大化类别间隔的超平面，使得不同类别的数据点距离这个超平面尽可能远。这就像在两个国家之间建立边界线，不仅要分开两国，还要让边界线距离两国都尽可能远，以增加安全性。

1.1、数学表达

对于线性可分的数据，SVM寻找最优超平面 $w^T x + b = 0$ ，使得：

$yi(wTxi+b)≥1,∀iy_i(w^T x_i + b) \geq 1, \quad \forall i$

各部分含义：

$w$ ：法向量（垂直于超平面的向量）
$b$ ：偏置项（超平面的位置）
$x_i$ ：第 $i$ 个样本的特征向量
$y_i$ ：第 $i$ 个样本的标签（+1 或 -1）
$≥1\geq 1$ ：确保样本距离超平面至少为1个单位

间隔的概念：两个类别到超平面的距离之和

计算：

类别A到超平面的距离： $1∥w∥\frac{1}{\|w\|}$
类别B到超平面的距离： $1∥w∥\frac{1}{\|w\|}$
总间隔： $2∥w∥\frac{2}{\|w\|}$

目标：最大化间隔，即最小化 $∥w∥\|w\|$

1.2、具体例子

假设我们有一个二分类问题：

数据：

类别A（ $y_i = +1$ ）：红色点
类别B（ $y_i = -1$ ）：蓝色点

超平面： $w^T x + b = 0$

约束条件：

对于类别A的样本： $\times (w^T x_i + b) \geq 1$
对于类别B的样本： $\times (w^T x_i + b) \geq 1$

1.3、支持向量：决策边界的核心

只有距离超平面最近的样本（支持向量）影响决策边界。这些样本满足：

$y_i(w^T x_i + b) = 1$

支持向量的稀疏性使得SVM具有良好的泛化能力，因为其他样本的移动不会影响超平面。

1.4、SVM间隔设计的优势总结

优势	核心作用	具体表现
鲁棒性	间隔越大，模型对噪声越不敏感	即使数据有微小变化，分类结果也不会改变，确保模型稳定性
泛化能力	间隔越大，模型在新数据上的表现越好	有效减少过拟合风险，提升模型预测准确性
唯一性	间隔最大的超平面是唯一的	确保模型最优性和可重现性，避免多个解的选择问题

2、优化目标：间隔最大化

SVM的优化目标是最大化间隔，同时最小化误分类：

$min⁡w,b12∥w∥2+C∑i=1Nξi\min_{w, b} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i$

$约束条件yi(wTxi+b)≥1−ξi,ξi≥0\text{约束条件} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0$

优化公式：

第一部分： $12∥w∥2\frac{1}{2} \|w\|^2$

目标：最小化 $∥w∥\|w\|$ ，即最大化间隔
原因：间隔 = $2∥w∥\frac{2}{\|w\|}$ ，所以最小化 $∥w∥\|w\|$ 等价于最大化间隔

第二部分： $\sum_{i=1}^N \xi_i$

目标：最小化误分类的惩罚
$C$ ：正则化参数，控制误分类的惩罚程度
$ξi\xi_i$ ：松弛变量，允许部分样本违反约束

软间隔约束： $yi(wTxi+b)≥1−ξiy_i(w^T x_i + b) \geq 1 - \xi_i$

允许部分样本违反原始约束
$ξi\xi_i$ 表示违反约束的程度

C值的作用：

C很大：误分类惩罚很重，模型倾向于完美分类，间隔较小
C很小：误分类惩罚较轻，模型倾向于最大化间隔，允许更多误分类
C适中：在间隔最大化和误分类最小化之间找到平衡

松弛变量ξ的作用

ξi的含义：

ξi = 0：样本满足原始约束，距离超平面≥1
0 < ξi < 1：样本在间隔内，但分类正确
ξi ≥ 1：样本被误分类

具体例子

假设我们有一个二分类问题，其中大部分样本可以完美分开，但少数样本存在重叠。在这种情况下，SVM的优化过程分为三个关键步骤：

首先通过最小化 $12∥w∥2\frac{1}{2} \|w\|^2$ 来最大化间隔，提升模型的鲁棒性；
然后通过最小化 $\sum_{i=1}^N \xi_i$ 来控制误分类，确保分类的准确性；
最后通过调节参数C来平衡间隔最大化和误分类最小化这两个目标。

经过这样的优化过程，SVM能够找到一个既最大化间隔又最小化误分类的超平面，从而构建出具有良好泛化能力和鲁棒性的分类模型。

3、对偶形式：核技巧的基础（ing）

SVM的对偶形式为：

$max⁡α∑i=1Nαi−12∑i,j=1NαiαjyiyjxiTxj\max_{\alpha} \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i,j=1}^N \alpha_i \alpha_j y_i y_j x_i^T x_j$

$to0≤αi≤C,∑i=1Nαiyi=0\text{subject to} \quad 0 \leq \alpha_i \leq C, \quad \sum_{i=1}^N \alpha_i y_i = 0$

对偶形式的重要性在于它引入了核技巧，使得SVM能够处理非线性分类问题。

4、核技巧：非线性分类的关键

核技巧通过将数据映射到高维空间来处理非线性分类问题。常用的核函数包括：

RBF核（高斯核）：
$K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$

多项式核：
$K(xi,xj)=(γxiTxj+r)dK(x_i, x_j) = (\gamma x_i^T x_j + r)^d$

线性核：
$K(x_i, x_j) = x_i^T x_j$

为什么核技巧有效？

核技巧允许SVM在高维空间中寻找复杂的非线性边界，同时保持计算效率。通过核函数，我们可以在高维空间中计算内积，而无需显式地映射数据。

5、SVM的工作步骤

数据映射：通过核函数将数据映射到高维空间
间隔最大化：寻找能最大化类别间隔的超平面
支持向量识别：识别影响决策边界的关键样本
正则化控制：通过参数 $C$ 控制误分类的惩罚程度

6、SVM算法总结

核心优势

SVM算法具有强泛化能力、处理高维数据、支持向量稀疏性和多种核函数选择四大优势，通过最大化间隔提升模型鲁棒性，核技巧有效处理高维特征空间，只有少数支持向量影响决策边界，能够适应不同的数据分布。

适用场景

SVM特别适合中等规模数据集、高维特征空间、需要高精度预测和数据分布复杂的场景，在文本分类、图像识别、生物信息学和金融风险评估等领域表现优异。
然而，SVM也面临大规模数据集训练时间复杂度高、特征尺度差异大需要标准化预处理和需要概率输出的场合等局限，这些因素限制了SVM在某些特定场景下的应用。

四种算法综合对比

算法	数学核心	主要作用	适用场景	计算复杂度
KNN	距离度量+投票	无需训练，直观分类	小数据、特征相似性强	$O (n)$
朴素贝叶斯	贝叶斯定理+条件独立	概率推断，速度快	文本分类、高维稀疏数据	$\times d)$
决策树	信息增益/基尼指数	规则生成，可解释	规则明确、混合类型数据	$\log n)$
SVM	最大间隔+核技巧	精准分界，泛化强	高维、复杂边界、精度优先	$O(n^2)$