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

决策树：ID3、C4.5和CART特征选择方式

news 来源：原创 2025/5/13 12:09:40

1 前言

该文章主要目的是记录ID3、C4.5和CART特征选择方式，这里只对决策树进行简单介绍。
决策树（Decision Tree）算法是一种有监督学习算法，它利用分类的思想，根据数据的特征构建数学模型，从而达到数据的筛选和决策的目标。它的重点是将看似无序、杂乱的已知数据，通过某种技术手段转化成可以预测未知数据的树状模型。每一条从根节点（对最终分类结果贡献最大的属性）到叶子节点（最终分类结果）的路径都代表一条决策的规则。

在预测时，从根节点出发，根据特征实际值，转移至某个子节点，直至叶子节点，从而完成决策。
在决策树构建的过程中，首先由所有的数据构成根节点，根据某种策略对某个特征进行划分，数据集被分割成若干份，每一份构成一个子节点。进而对子节点继续划分，直至决策树生成完毕。
常用的决策树构建算法有ID3、C4.5和CART等，它们之间关键区别是用于划分数据集的特征的选择策略不同，以下对其策略进行介绍。

2 ID3

ID3算法使用信息增益指导决策树的划分。
首先介绍概念：熵。熵表示随机变量不确定性的度量。先给出公式：
$Info(Y)=-\sum_{y}{p(y)\log{p(y)}}$
对于决策树中的某一个节点，可以通过上述公式计算熵，其中 $Y$ 表示类别， $y$ 表示具体的类别值。熵越小越好。
信息增益表示特征 $A$ 使得类Y的不确定性减小的程度。公式如下：
$G ain (D, A) = I n f o (D) - I n f o (D, A)$
D是数据集， $A$ 表示被划分的特征。 $I n f o (D)$ 表示某个节点的熵， $I n f o (X, D)$ 表示当前节点按照 $A$ 划分之后，得到的子节点的熵的加权和。
$Info(D,A)=\sum_{a}{\frac{|D_{A=a}|}{|D|}Info(D_{A=a})}$
$D_{A=a}$ 表示 $A$ 为a的样本组成的子节点，权重是 $D_{A=a}$ 的样本数量与 $D$ 的样本数量的比值。
每次划分，计算每个特征的 $G ain (D, A)$ ，选择 $G ain (D, A)$ 最大的特征划分数据集。

3 C4.5

C4.5相比于ID3的主要区别是使用信息增益率替代信息增益。信息增益率是信息增益与自身熵 $I V (D, A)$ 的比值。
$Gain\_ratio(D,A)=\frac{Gain(D,A)}{IV(D,A)}$
自身熵表示当前节点划分的程度，划分的子节点越少，越均匀，自身熵越小，信息增益率越大。
$IV(D,A)=-\sum_a{\frac{|D_{A=a}|}{|D|}\log{\frac{|D_{A=a}|}{|D|}}}$
每次划分，计算每个特征的信息增益率，选择信息增益率最大的特征划分数据集。

4 CART

相比于上面的方法，CART使用基尼（Gini）指数选择特征。
基尼（Gini）指数使用 $p (y) (1 - p (y))$ 替代 $p(y)\log{p(y)}$ ，公式如下：
$Gini(D)=\sum_{i}p(y)(1-p(y))=1-\sum_i{p^2(y)}$
做这个替代有什么影响呢。可以看一下图像。
$p(y)\log{p(y)}$ 为：

$p (y) (1 - p (y))$ 为：

可以看到 $p(y)\log{p(y)}$ 图像比较倾斜，而 $p (y) (1 - p (y))$ 比较对称，在0.5取到最大值。一个类别准确率为0.5是最具不确定性的，也就是最差的，所以从图像上看明显 $p (y) (1 - p (y))$ 更符合目标。
D根据特征A被划分为多个子结点后，得到的子节点的基尼（Gini）指数的加权和。
$Gini(D,A)=\sum_{a}{\frac{|D_{A=a}|}{|D|}Gini(D_{A=a})}$
每次划分，计算每个特征的 $G ini (D, A)$ ，选择 $G ini (D, A)$ 最大的特征划分数据集。

1 前言

2 ID3

3 C4.5

4 CART

相关文章：