决策树是机器学习中的经典监督学习算法，具有直观易懂的树形结构和出色的可解释性。深入剖析了 ID3、C4.5 和 CART 三大核心算法的原理与实现。ID3 基于信息增益构建多叉树；C4.5 引入信息增益比并支持连续特征及剪枝；CART 采用基尼指数构建二叉树，适用于分类与回归任务。文章通过天气数据集演示了熵与信息增益的计算过程，提供了 Python 代码实现，并对比了三种算法在划分准则、树结构及适用场景上的差异，帮助读者掌握决策树的核心机制与应用选择。
决策树是一种监督学习算法，它通过递归地将数据集划分为子集，构建出一个类似流程图的树形结构。每个内部节点代表一个特征的判断，每个分支代表判断的结果，每个叶节点代表最终的分类或回归值。
决策树具有极强的可解释性，就像一个专家系统，能够清晰地展示决策的过程。
要理解决策树的构建过程，我们首先需要掌握两个核心概念：。
熵是信息论中的基本概念，用于衡量数据集的纯度或混乱程度。对于一个包含 n 个类别的数据集，其熵的计算公式为：
H(S)=−∑i=1npilog2(pi)
其中 pi 是第 i 个类别在数据集中的比例。熵值越高，说明数据越混乱；熵值越低，说明数据越纯净。
以我们使用的天气数据集为例，14 天的记录中有 9 天去打球（Yes），5 天不去（No）。整个数据集的熵为：
H(S)=−14/9log2(14/9)−14/5log2(14/5)≈0.940
这个值表示在没有任何特征信息的情况下，我们对是否去打球的不确定性。
信息增益表示通过某个特征划分数据集后，熵的减少量。它反映了该特征对降低数据不确定性的贡献。信息增益的计算公式为：
IG(S,A)=H(S)−∑v∈Values(A)|S|/|Sv|H(Sv)
其中 Sv 是特征 A 取值为 v 的子集。信息增益越大，说明该特征对分类的贡献越大，越适合作为当前节点的划分特征。
ID3（Iterative Dichotomiser 3）是由 Ross Quinlan 于 1986 年提出的决策树算法。它以信息增益为准则，选择最优特征作为当前节点的划分依据，递归地构建决策树。
ID3 算法的核心步骤：
让我们用经典的天气数据集来演示 ID3 算法的具体实现。
我们的数据集包含 14 条记录，每个记录包含 5 个特征：Outlook（天气状况）、Temperature（温度）、Humidity（湿度）、Windy（是否有风），以及一个目标变量 Play（是否去打球）。
首先，我们已经知道整个数据集的熵 H (S) ≈ 0.940。接下来，我们计算每个特征的信息增益。
1. Outlook 特征的信息增益 Outlook 有三个取值：Sunny（5 天）、Overcast（4 天）、Rainy（5 天）。
Outlook 特征的信息增益：IG(S,Outlook)≈0.247
2. Temperature 特征的信息增益 Temperature 有三个取值：Hot（4 天）、Mild（6 天）、Cool（4 天）。
Temperature 特征的信息增益：IG(S,Temperature)≈0.029
3. Humidity 特征的信息增益 Humidity 有两个取值：High（7 天）、Normal（7 天）。
Humidity 特征的信息增益：IG(S,Humidity)≈0.151
4. Windy 特征的信息增益 Windy 有两个取值：False（8 天）、True（6 天）。
Windy 特征的信息增益：IG(S,Windy)≈0.048
比较四个特征的信息增益：
显然，Outlook 特征的信息增益最大，因此我们选择它作为根节点。
优点：
缺点：
C4.5 算法同样由 Ross Quinlan 提出，是 ID3 算法的改进版本。它解决了 ID3 算法的多个缺陷，成为更实用的决策树算法。
C4.5 的主要改进点：
信息增益比是在信息增益的基础上，除以特征的固有值（Split Information），以平衡取值较多的特征。
信息增益比的计算公式为：IGR(S,A)=SI(S,A)/IG(S,A)
其中，固有值 SI (S, A) 的计算公式为：SI(S,A)=−∑v∈Values(A)|S|/|Sv|log2(|S|/|Sv|)
对于我们的天气数据集，Outlook 特征的固有值为：SI(S,Outlook)≈1.577
因此，Outlook 特征的信息增益比为：IGR(S,Outlook)≈0.157
C4.5 通过二分法处理连续型特征：
C4.5 采用后剪枝策略，即先构建完整的决策树，再从叶节点向上剪枝。它通过计算剪枝前后的误差率，判断是否保留该分支，从而提高模型的泛化能力。
C4.5 通过加权的方式处理缺失值：
CART（Classification and Regression Tree）是由 Leo Breiman 等人提出的决策树算法。它既可以用于分类任务，也可以用于回归任务，是目前应用最广泛的决策树算法之一。
CART 与 ID3、C4.5 的主要区别：
基尼指数是另一种衡量数据集不纯度的指标，其计算公式为：
Gini(S)=1−∑i=1npi2
其中 pi 是第 i 个类别在数据集中的比例。基尼指数越小，说明数据越纯净。
对于我们的天气数据集，整体的基尼指数为：Gini(S)≈0.459
CART 算法选择基尼指数增益最大的特征作为划分依据。对于特征 A，其基尼指数增益为：
GiniGain(S,A)=Gini(S)−∑v∈Values(A)|S|/|Sv|Gini(Sv)
以 Outlook 特征为例，其基尼指数增益为：GiniGain(S,Outlook)≈0.157
与 ID3 和 C4.5 不同，CART 算法构建的是二叉树。对于离散型特征，CART 会将其划分为 "等于某个值" 和 "不等于某个值" 两个分支；对于连续型特征，CART 会将其划分为 "小于等于某个值" 和 "大于某个值" 两个分支。
这种二叉树结构使得 CART 算法更加灵活，能够处理更复杂的决策边界。
CART 采用代价复杂度剪枝（Cost-Complexity Pruning），通过引入复杂度参数 α，平衡模型的拟合能力和复杂度。剪枝的目标是找到最优的 α 值，使得模型在验证集上的表现最佳。
| 特性 | ID3 | C4.5 | CART |
|---|---|---|---|
| 划分准则 | 信息增益 | 信息增益比 | 基尼指数（分类）/ 平方误差（回归） |
| 树结构 | 多叉树 | 多叉树 | 二叉树 |
| 连续型特征 | 不支持 | 支持（二分法） | 支持（二分法） |
| 缺失值处理 | 不支持 | 支持 | 支持 |
| 剪枝机制 | 无 | 后剪枝 | 代价复杂度剪枝 |
| 适用任务 | 分类 | 分类 | 分类 / 回归 |
下面我们用 Python 实现 ID3 算法，完整地构建天气数据集的决策树：
import math
from collections import Counter
class ID3DecisionTree:
def __init__(self):
self.tree = {}
def entropy(self, data):
"""计算数据集的熵"""
labels = [row[-1] for row in data]
label_counts = Counter(labels)
entropy = 0.0
total = len(labels)
for count in label_counts.values():
p = count / total
entropy -= p * math.log2(p) if p > 0 else 0
return entropy
def split_dataset(self, data, feature_idx, value):
"""根据特征和值划分数据集"""
subset = []
for row in data:
if row[feature_idx] == value:
reduced_row = row[:feature_idx] + row[feature_idx+1:]
subset.append(reduced_row)
return subset
def choose_best_feature(self, data):
"""选择信息增益最大的特征"""
num_features = len(data[0]) - 1
base_entropy = self.entropy(data)
best_info_gain = 0.0
best_feature_idx = -1
for i in range(num_features):
feature_values = [row[i] for row in data]
unique_values = set(feature_values)
new_entropy = 0.0
for value in unique_values:
subset = self.split_dataset(data, i, value)
p = len(subset) / len(data)
new_entropy += p * self.entropy(subset)
info_gain = base_entropy - new_entropy
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature_idx = i
return best_feature_idx
def majority_vote(self, labels):
"""多数投票决定叶节点的类别"""
label_counts = Counter(labels)
return max(label_counts, key=label_counts.get)
def build_tree(self, data, feature_names):
"""递归构建决策树"""
labels = [row[-1] for row in data]
# 如果所有标签相同，返回该标签
if labels.count(labels[0]) == len(labels):
return labels[0]
# 如果没有特征可用，返回多数标签
if len(data[0]) == 1:
return self.majority_vote(labels)
# 选择最优特征
best_feature_idx = self.choose_best_feature(data)
best_feature_name = feature_names[best_feature_idx]
# 构建树
tree = {best_feature_name: {}}
del(feature_names[best_feature_idx])
# 获取最优特征的所有取值
feature_values = [row[best_feature_idx] for row in data]
unique_values = set(feature_values)
# 递归构建子树
for value in unique_values:
sub_feature_names = feature_names[:]
subset = self.split_dataset(data, best_feature_idx, value)
tree[best_feature_name][value] = self.build_tree(subset, sub_feature_names)
return tree
# 天气数据集
data = [
['Sunny', 'Hot', 'High', 'False', 'No'],
['Sunny', 'Hot', 'High', 'True', 'No'],
['Overcast', 'Hot', 'High', 'False', 'Yes'],
['Rainy', 'Mild', 'High', 'False', 'Yes'],
['Rainy', 'Cool', 'Normal', 'False', 'Yes'],
['Rainy', 'Cool', 'Normal', 'True', 'No'],
['Overcast', 'Cool', 'Normal', 'True', 'Yes'],
['Sunny', 'Mild', 'High', 'False', 'No'],
['Sunny', 'Cool', 'Normal', 'False', 'Yes'],
['Rainy', 'Mild', 'Normal', 'False', 'Yes'],
['Sunny', 'Mild', 'Normal', 'True', 'Yes'],
['Overcast', 'Mild', 'High', 'True', 'Yes'],
['Overcast', 'Hot', 'Normal', 'False', 'Yes'],
['Rainy', 'Mild', 'High', 'True', 'No']
]
feature_names = ['Outlook', 'Temperature', 'Humidity', 'Windy']
# 构建 ID3 决策树
id3_tree = ID3DecisionTree()
tree = id3_tree.build_tree(data, feature_names)
print("构建的 ID3 决策树：")
print(tree)
决策树算法以其直观的结构和强大的性能，在机器学习领域占据着重要的地位。从 ID3 到 C4.5 再到 CART，每一次算法的演进都解决了前一代的缺陷，使得决策树越来越实用和高效。
单一的决策树模型存在过拟合和对噪声敏感等局限性。集成学习方法如随机森林（Random Forest）、梯度提升树（Gradient Boosting Tree）应运而生。这些方法通过组合多个决策树，显著提高了模型的稳定性和泛化能力。
随着大数据时代的到来，决策树算法也在不断发展和创新。未来，我们可以期待更高效的并行化决策树算法、更强大的特征选择能力，以及与深度学习的深度融合。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online