一、决策树的基本概念

决策树是一种树形结构，其中每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出，每个叶子节点代表一种分类结果或预测值。决策树通过递归地选择最优特征进行划分，直到满足停止条件（如节点中的样本数小于某个阈值，或划分后的纯度达到某个要求）为止。

二、ID3决策树

ID3决策树是决策树算法的一种早期实现，它使用信息增益作为特征选择的标准。

1. 信息熵

信息熵是信息论中代表随机变量不确定度的度量。熵越大，数据的不确定性度越高，信息就越多；熵越小，数据的不确定性越低。

2. 信息增益

信息增益是特征a对训练数据集D的信息增益g(D, a)，定义为集合D的熵H(D)与特征a给定条件下D的熵H(D|a)之差。数学公式为：

g(D, A) = H(D) - H(D|A)

信息增益越大，说明该特征对分类的贡献越大。

3. 构建流程

ID3决策树的构建流程如下：

• 计算每个特征的信息增益。
• 使用信息增益最大的特征将数据集拆分为子集。
• 使用该特征作为决策树的一个节点。
• 使用剩余特征对子集重复上述过程，直到满足停止条件。

4. 分支方式

ID3决策树按照信息增益划分节点，选择信息增益最大的特征进行划分。

5. 特点与不足

• ID3只能对离散属性的数据集构成决策树。
• 倾向于选择取值较多的属性，可能导致过拟合。
• 不足：偏向于选择种类多的特征作为分裂依据。

三、C4.5决策树

C4.5决策树是ID3决策树的改进版，它使用信息增益率作为特征选择的标准。

1. 信息增益率

信息增益率 = 信息增益 / 特征熵

信息增益率是对信息增益的修正，增加了对特征取值个数的惩罚。特征取值个数较多时，惩罚系数较小；特征取值个数较少时，惩罚系数较大。

2. 分支方式

C4.5决策树按照信息增益率选择节点，选择信息增益率最大的特征进行划分。

3. 特点

• 缓解了ID3分支过程中总喜欢偏向选择值较多的属性。
• 可处理连续数值型属性，也增加了对缺失值的处理方法。
• 只适合于能够驻留于内存的数据集，大数据集无能为力。

四、CART决策树

CART（Classification and Regression Trees）决策树既可以用于分类，也可以用于回归。

1. CART分类树

• 介绍：CART分类树采用基尼指数最小化策略进行特征选择。
• 基尼值：从数据集D中随机抽取两个样本，其类别标记不一致的概率。基尼值越小，数据集D的纯度越高。
• 基尼指数：选择使划分后基尼系数最小的属性作为最优化分属性。
• 分支方式：按照基尼指数选择节点，选择基尼指数最小的特征进行划分。
• 特点：
  • 可以进行分类和回归，可处理离散属性，也可以处理连续属性。
  • 采用基尼指数，计算量减小。
  • 一定是二叉树。

CART分类树API

from sklearn.tree import DecisionTreeClassifier 


# 模型 
model = DecisionTreeClassifier( 
criterion='gini', # 特征选择标准，'gini'代表基尼系数，'entropy'代表信息增益 
max_depth=None, # 决策树最大深度 
random_state=None # 随机数种子 
) 


# 画图 
from sklearn.tree import plot_tree 
import matplotlib.pyplot as plt 


plt.figure(figsize=(30, 20), dpi=100) # 画布尺寸和分辨率 
plot_tree( 
model, # 模型名称 
max_depth=10, # 最大深度 
filled=True, # 填充颜色 
feature_names=['Pclass', 'Age', 'Sex_female', 'Sex_male'], 
class_names=['died', 'survived'] 
) 
plt.xlabel('data') 
plt.ylabel('target') 
plt.title('CART Classification Tree') 
plt.legend() # 用于添加图例 
plt.show()

2. CART回归树

• 介绍：CART回归树使用平方误差最小化策略进行特征选择。
• 与CART分类树的不同之处：
  • CART分类树预测输出的是一个离散值，CART回归树预测输出的是一个连续值。
  • CART分类树使用基尼指数作为划分、构建树的依据，CART回归树使用平方损失。
  • 分类树使用叶子节点多数类别作为预测类别，回归树则采用叶子节点里均值作为预测输出。

CART回归树的构建过程

1. 选择一个特征，将该特征的值进行排序，取相邻点计算均值作为待划分点。
2. 根据所有划分点，将数据集分成两部分：R1、R2。
3. R1和R2两部分的平方损失相加作为该切分点平方损失。
4. 取最小的平方损失的划分点，作为当前特征的划分点。
5. 以此计算其他特征的最优划分点、以及该划分点对应的损失值。
6. 在所有的特征的划分点中，选择出最小平方损失的划分点，作为当前树的分裂点。

CART回归树API

from sklearn.tree import DecisionTreeRegressor 


# 模型 
model = DecisionTreeRegressor(max_depth=1) 


# 画图（与CART分类树相同） 
# ...（省略画图代码）

五、剪枝技术

剪枝是防止决策树过拟合的一种正则化方法，可以提高其泛化能力。

1. 预剪枝

• 概念：指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。
• 优点：预剪枝使决策树的很多分支没有展开，不仅降低了过拟合风险，还显著减少了决策树的训练、测试时间开销。
• 缺点：有些分支的当前划分虽不能提升泛化性能，但后续划分却有可能导致性能的显著提高；预剪枝决策树也带来了欠拟合的风险。

2. 后剪枝

• 概念：先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
• 优点：比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。
• 缺点：后剪枝先生成完整的决策树，再进行剪枝。自底向上地对树中所有非叶子节点进行逐一考察，训练时间开销比未剪枝的决策树和预剪枝的决策树都要大得多。

综上所述，决策树是一种强大的机器学习算法，广泛应用于分类和回归任务中。通过选择合适的特征选择标准和剪枝技术，可以有效地提高决策树的泛化能力和性能。