[机器学习] 决策树

决策树

决策树是一种常用的机器学习算法，用树形结构解决分类和回归问题。它是一种监督学习算法，通过学习简单的决策规则从数据特征中推断出目标变量。

• 输出变量是离散的——分类问题
• 输出变量是连续的——回归问题

核心思想

模仿人类决策过程，通过一系列的问题（通常是二元选择）来逐步缩小选择范围，最终达到一个结论。

主要特点

• 树形结构：决策树由节点（Node）和边（Edge）组成，形似树状结构。每个内部节点代表一个特征上的测试，每条边代表测试的结果，每个叶节点（Leaf Node）代表一个决策结果。
• 易于理解：决策树的树形结构直观，易于理解和解释，使得模型的预测过程透明。
• 适用性广：既可以用于分类问题（如CART、ID3、C4.5），也可以用于回归问题（如回归树）。

构建过程

1. 评估并选择最佳特征：在每个节点，算法会评估所有可能的特征和切分点，选择能够最好地区分数据的特征和切分点。

2. 分裂数据集：根据选择的特征和切分点，将数据集分割成两个或多个子集。

3. 递归构建：对每个子集重复上述过程，直到满足停止条件（如达到最大深度、节点中的样本数太少、或进一步分裂不能显著提高模型性能）。

4. 剪枝：为了防止过拟合，决策树可能会进行剪枝处理，包括预剪枝和后剪枝。

5. 输出结果：叶节点通常代表最终的分类结果或回归预测值。

分类

根据特征的重要性评判可以分成以下几种：

ID3算法——基于信息增益

基于信息增益，选择能够最大程度减少熵（不确定性）的特征作为分裂节点。

信息增益（Information Gain）

用来衡量通过一个特征将数据集分割后，能够获得多少关于目标变量的信息。

信息增益越高，说明该特征对于预测目标变量的值越有用。

信息增益的计算：

信息增益是基于信息论中的熵（Entropy）概念计算的。

1. 计算数据集的熵：
   熵是衡量数据集不确定性的指标，熵越高，数据集的不确定性越大。
   $$H(D)=-\sum _{i=1}^n{p}_i{\log }_2{p}_i$$
   其中，$H(D)$是数据集(D)的熵，$p_i$是数据集中第$i$个类别的概率。

2. 计算特征的条件熵：
   条件熵用于衡量在已知一个随机变量的条件下，另一个随机变量的不确定性。
   $$H(D|A)=\sum _{j=1}^m\frac{|D_j|}{|D|}H(D_j)$$
   其中，$H(D|A)$是特征$A$的条件熵，$D_j$是根据特征$A$的第$j$个值分割后的子数据集，$|D_j|$是子数据集$D_j$的大小，$|D|$是原始数据集的大小。

3. 计算信息增益：
   $$\text{Gain}(D,A)=H(D)-H(D|A)$$
   其中，$\text{Gain}(D,A)$ 是特征 $A$ 在数据集 $D$上的信息增益。

C4.5算法——基于信息增益比

基于信息增益比（Gain Ratio），在ID3的基础上进行了改进。与ID3算法不同，C4.5不仅能够处理离散属性，还能处理连续属性，同时在处理缺失值和剪枝（Pruning）方面也有较大的改进

核心思想：通过信息增益比选择最优的划分属性，构建决策树。

信息增益比计算

1. 计算信息增益：
   $$\text{Gain}(D,a)=H(D)-H(D|a)$$
   其中，$H(D)$是数据集$D$的熵，$H(D|a)$是属性$a$的条件熵。

2. 计算固有值：
   固有值衡量了属性的离散性，属性取值越多，固有值越大。
   $$\text{IV}(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$
   其中，$V$是属性$a$可能的值的数目，$D^v$是属性$a$的值为$v$时的子集，$|D^v|$和$|D|$分别是子集$D^v$和数据集$D$的样本数目。

3. 计算信息增益比：
   $$\text{Gain Ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV}(a)}$$
   其中，$\text{Gain}(D,a)$是特征$a$在数据集$D$上的信息增益，$\text{IV}(a)$是属性$a$的固有值。

CART算法

分类问题

用基尼不纯度 / 基尼指数作为特征选择的标准，它衡量了数据集的不纯度，选择能够最大程度减少不纯度的特征。
基尼不纯度的计算公式：
$$\text{Gini}(D)=1-\sum _{i=1}^n{p}_i^2$$
其中，$p_i$是数据集中第$i$个类别的概率。

回归问题

用均方误差作为特征选择的标准。

均方误差的计算公式：
$$\text{MSE}(D)=\frac{1}{|D|}\sum _{i=1}^{|D|}(y_i-\bar{y}{)}^2$$
其中，$y_i$是数据集$D$中第$i$个样本的目标值，$\bar{y}$是数据集$D$中所有样本目标值的平均值，$|D|$是数据集$D$的样本数目。

Random Forest算法

构建多个决策树，每棵树在构建时随机选择特征子集，通过集成多个树的结果来提高模型的稳定性和准确性。

回归树

数学表达式

回归树是一种决策树，用于解决回归问题。

它通过将数据集分割成多个子集，每个子集对应一个叶节点，叶节点包含该子集目标值的平均值。

回归树的数学表达式可以表示为：

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$

其中，$M$是叶节点的数量，$c_m$是第$m$个叶节点的目标值平均数，$R_m$是第$m$个叶节点对应的子集，$I(x\in R_m)$是指示函数，如果$x$属于$R_m$则为1，否则为0。

这个表达式的意思是，对于任意输入 $x$，预测函数 $f(x)$ 会根据 $x$ 属于哪个叶节点的子集 $R_m$，来返回一个预测值。这个预测值一般是该叶子节点的子集$R_m$所有输出的平均值 $c_m$。如果 $x$ 属于第 $m$ 个叶节点的子集 $R_m$，则 $I(x\in R_m)=1$，其他所有 $I(x\in R_k)=0$（对于 $k\ne m$）。因此，$f(x)$ 的值就是 $c_m$。

损失函数

回归树的损失函数通常使用均方误差（MSE）：

$$\text{MSE}(D)=\frac{1}{|D|}\sum _{i=1}^{|D|}(y_i-\bar{y}{)}^2$$

其中，$y_i$是数据集$D$中第$i$个样本的目标值，$\bar{y}$是数据集$D$中所有样本目标值的平均值，$|D|$是数据集$D$的样本数目。

树如何构建

树的构建通常要解决三个问题：

1. 树的深度如何决定——决定训练什么时候停止
   树的深度可以通过多种方式决定，大多数情况下是自己定义

   • 直接指定叶子结点个数或树的深度（无法控制精度）
   • 子节点所包含的样本数小于k个时停止划分
   • 当增加深度不再显著提高模型精度时停止
   • ……

2. 划分节点如何选取
   划分节点的选取通常基于损失函数的减少。对于回归树，这通常是均方误差MSE的减少。选择能够最大化损失函数减少的特征和切分点作为划分节点。

3. 叶子节点代表的值$c_m$如何定
   叶子节点的 $c_m$ 值取该叶子节点中所有训练样本$y_i$的平均值时，得到损失最小，。数学表达式为：
   $$c_m=\frac{1}{|S_m|}\sum _{x_i\in S_m}{y}_i$$
   其中，$S_m$ 是第 $m$ 个叶子节点的样本集合，$y_i$ 是样本 $x_i$ 的目标值，$|S_m|$ 是叶子节点 $S_m$ 中样本的数量。
   推导过程：
   损失函数从按样本遍历的形式转化为按叶子节点进行两次遍历的形式，外部对节点遍历，内部遍历节点内所有的样本
   
   由于y确定（数据集给定的），现在只剩下一个要优化的变量$c_m$。
   
   直接对J求导，使导数为0，得到最优解
   
   
   

优化求解

回归树的优化求解过程是通过最小化均方误差来选择最佳的分裂点。具体步骤如下：

1. 计算当前节点的MSE：在当前节点，计算所有样本的MSE。
2. 尝试所有可能的分裂：对于每个特征，尝试所有可能的切分点，计算分裂后的MSE。
3. 选择最佳分裂：选择能够最小化MSE的特征和切分点。
4. 递归优化：对每个子集重复上述过程，直到满足停止条件。

代码实现

from sklearn.datasets import fetch_california_housing
from sklearn.tree import DecisionTreeRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error


california_housing = fetch_california_housing(as_frame=True)
X, y = california_housing.data, california_housing.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)


regressor = DecisionTreeRegressor(max_depth=2, random_state=42)


regressor.fit(X_train, y_train)


y_pred = regressor.predict(X_test)


mse = mean_squared_error(y_test, y_pred)
print(f"Mean Squared Error: {mse}")

分类树

分类树的特征选择方式

分类树在构建过程中，特征选择是一个关键步骤，它决定了树的分裂方式。有两种常用的特征选择标准：

1. 信息增益（Information Gain）criterion = ‘entropy’：
   信息增益是基于熵的概念，用于衡量一个特征对于目标变量的不确定性减少的程度。信息增益越大，表示该特征对于分类越有帮助。
   $$\text{Gain}(D,a)=H(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}H(D^v)$$
   其中，$H(D)$ 是数据集 $D$ 的熵，$D^v$ 是特征 $a$ 取值为 $v$ 时的子集。

2. 基尼不纯度（Gini Impurity）criterion = ‘gini’：
   基尼不纯度衡量了一个节点的不纯度，即样本类别分布的不均匀性。基尼不纯度越低，表示节点越纯。
   $$\text{Gini}(D)=1-\sum _{i=1}^n{p}_i^2$$
   其中，$p_i$ 是数据集中第 $i$ 个类别的概率。

分类树的算法流程

1. 选择最佳特征：在当前节点，根据信息增益或基尼不纯度选择最佳特征进行分裂。

2. 分裂数据集：根据选择的特征和切分点，将数据集分裂成两个或多个子集。

3. 递归构建：对每个子集重复步骤1和2，直到满足停止条件。

4. 停止条件：当节点中的样本数太少、纯度已经很高、或达到预设的最大深度时，停止分裂。

5. 叶节点分类：对于每个叶节点，根据该节点中的样本类别分布，确定最终的分类结果。

代码实现

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
import matplotlib.pyplot as plt

# 加载数据集
iris = load_iris()
X, y = iris.data, iris.target

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 创建决策树分类器实例
clf = DecisionTreeClassifier(max_depth=3, random_state=42)

# 训练模型
clf.fit(X_train, y_train)

# 预测测试集
y_pred = clf.predict(X_test)

# 评估模型
accuracy = clf.score(X_test, y_test)
print(f"Accuracy: {accuracy}")

# 可视化决策树
plt.figure(figsize=(12, 8))
tree.plot_tree(clf, filled=True, feature_names=iris.feature_names, class_names=iris.target_names)
plt.show()