机器学习13-决策树2——决策树生成、剪枝

数据集划分为子集，构建出一棵树状结构。

---

---

前言

【机器学习】12-决策树1——概念、特征选择

• 特征选择：在构建决策树时，首先需要从数据集中选择最具分类能力的特征。这通常通过计算特征的信息增益、信息增益比或基尼指数等指标来完成

• 决策树的生成：根据选择的特征，将数据集划分为若干个子集，并为每个子集生成相应的子树。这个过程是递归进行的，直到满足某个停止条件。

• 停止条件
  为了防止决策树过拟合，常用的停止条件包括：
  – 树的深度达到预设的最大值：限制决策树的深度，避免树过度复杂。
  – 叶子节点的样本数量小于某个阈值：当某个节点上的样本数量过少时，停止继续分裂。
  – 信息增益、基尼指数或其他分裂标准的增益小于某个阈值：如果继续划分的收益不足，停止划分。
• 剪枝技术——由于决策树容易过拟合数据，生成过于复杂的树，因此在树生成之后通常会进行剪枝：
  – 预剪枝：在构建决策树的过程中，通过设定最大深度、最小样本数量等提前停止树的生长。
  – 后剪枝：先生成一棵完全树，然后从下往上修剪掉不必要的叶子节点，减少模型的复杂度。

---

1. 信息增益（ID3算法）（Iterative Dichotomiser 3）：选择信息增益最大的特征。

由Ross Quinlan于1986年提出。它使用 信息增益 作为选择最佳特征的标准

流程

• 1. 计算数据集的熵（Entropy）：熵越大表示数据集越不纯。熵的计算公式为：
     
• 2. 计算每个特征的信息增益： 信息增益公式为：
     
• 3. 选择信息增益最大的特征进行划分： 选择信息增益最大的特征来作为当前节点的划分标准。
• 4. 递归构建子树： 对每个子集递归地重复步骤1到3，直到数据集不可再划分或满足其他停止条件（如所有样本都属于同一类或没有可用的特征）。
• 5. 生成叶子节点： 当所有样本都属于同一类别时，生成叶子节点，并将该类别作为分类结果。如果没有可用的特征，使用多数类作为叶子节点的分类结果。

ID3 算法适用于小规模数据集的分类问题，特别是当特征数量较少且数据较为清晰时。

例子和代码

• 1. 我们计算是否适合出门的熵：有 5 个样本是“适合出门”，5 个样本是“不适合出门”
     
• 2. 为每个特征计算信息增益，选择信息增益最大的特征进行划分。
• • 第一个特征：天气
    
    四个晴天中，三个否，一个是
    
    多云
    
    雨天
    
    特征的熵
    
    信息增益
    
• • 第二个特征：温度
    
    
    
    信息增益0.029
• • 第三个特征：湿度
    同理：
    
    第四个特征省略
• 3. 选择“天气”作为当前节点进行分裂。将数据集根据“天气”特征的不同取值分裂成子集， 对于每个子集，检查以下情况：

完全纯净（Pure）： 如果子集中的所有实例属于同一类（如Overcast子集），则将该节点标记为该类，并停止分裂。
特征用尽： 如果没有更多的特征可以用来分裂数据集，则将该节点标记为子集中最多的类。
继续分裂： 如果以上条件均不满足，则计算当前子集中的每个特征的信息增益，选择信息增益最高的特征进行进一步分裂,重复步骤

构建代码

import math
import pandas as pd
from collections import Counter# 计算熵
def entropy(data):label_counts = Counter(data)total = len(data)return -sum((count/total) * math.log2(count/total) for count in label_counts.values())# 计算信息增益
def info_gain(data, feature, target):total_entropy = entropy(data[target])values = data[feature].unique()feature_entropy = sum((len(data[data[feature] == value]) / len(data)) * entropy(data[data[feature] == value][target]) for value in values)return total_entropy - feature_entropy# 构建ID3决策树
def id3(data, features, target):# 如果所有样本都属于同一类，返回该类if len(set(data[target])) == 1:return list(data[target])[0]# 如果没有特征可用，返回多数类if len(features) == 0:return data[target].mode()[0]# 选择信息增益最大的特征best_feature = max(features, key=lambda feature: info_gain(data, feature, target))tree = {best_feature: {}}# 根据最佳特征的每个取值划分子数据集，递归构建子树for value in data[best_feature].unique():sub_data = data[data[best_feature] == value]subtree = id3(sub_data, [f for f in features if f != best_feature], target)tree[best_feature][value] = subtreereturn tree# 示例数据集
data = pd.DataFrame({'天气': ['晴天', '晴天', '多云', '雨天', '雨天', '雨天', '多云', '晴天', '晴天', '雨天'],'温度': ['高温', '高温', '高温', '低温', '低温', '低温', '低温', '高温', '低温', '高温'],'湿度': ['高湿', '高湿', '高湿', '高湿', '低湿', '低湿', '低湿', '低湿', '低湿', '高湿'],'风力': ['弱', '强', '弱', '弱', '弱', '强', '强', '弱', '强', '弱'],'是否适合出门': ['否', '否', '是', '是', '是', '否', '是', '是', '否', '是']
})# 特征
features = ['天气', '温度', '湿度', '风力']# 构建决策树
tree = id3(data, features, '是否适合出门')
print(tree)

优缺点

优点：
原理简单，易于理解。
能够处理具有缺失值的数据集。
生成的决策树结构清晰，易于解释。
缺点：
只能处理分类问题，不能处理回归问题。
对噪声和异常值敏感，容易过拟合。
倾向于选择取值较多的特征作为分裂特征（因为信息增益会偏向取值多的特征）。
无法处理连续型特征，需要先进行离散化处理。

2. 信息增益比（C4.5算法）：对信息增益进行修正

与 ID3 算法的不同之处

• 可以处理连续属性
  在 ID3 算法中，只能处理离散属性。而 C4.5 算法能够将连续属性进行离散化处理，从而可以处理连续属性值的情况。
  对于连续属性，C4.5 算法首先将其值排序，然后逐一尝试在不同取值点将数据集划分为两部分，计算信息增益比，选择信息增益比最大的划分点进行离散化。
• 使用信息增益比代替信息增益

计算流程一样，只不过根据信息增益比选择特征

代码

import numpy as np
import pandas as pdclass C45:def __init__(self, min_samples_split=2):self.min_samples_split = min_samples_splitself.tree = Nonedef fit(self, X, y):self.tree = self._build_tree(X, y)def _build_tree(self, X, y):num_samples, num_features = X.shapeunique_classes = np.unique(y)# Stop conditionsif num_samples < self.min_samples_split or len(unique_classes) == 1:return self._most_common_class(y)# Calculate gain ratio for each featuregain_ratios = []for feature_index in range(num_features):gain_ratio = self._gain_ratio(X, y, feature_index)gain_ratios.append(gain_ratio)# Select the feature with the highest gain ratiobest_feature_index = np.argmax(gain_ratios)best_feature = X[:, best_feature_index]# Create the tree nodetree = {best_feature_index: {}}unique_values = np.unique(best_feature)for value in unique_values:sub_X = X[best_feature == value]sub_y = y[best_feature == value]# Recursively build the tree for the subsetsubtree = self._build_tree(sub_X, sub_y)tree[best_feature_index][value] = subtreereturn treedef _gain_ratio(self, X, y, feature_index):feature_values = X[:, feature_index]unique_values = np.unique(feature_values)# Calculate entropy of the parentparent_entropy = self._entropy(y)# Calculate weighted average entropy of the childrenweighted_entropy = 0split_info = 0for value in unique_values:sub_y = y[feature_values == value]prob = len(sub_y) / len(y)weighted_entropy += prob * self._entropy(sub_y)split_info -= prob * np.log2(prob)# Information gaingain = parent_entropy - weighted_entropy# Gain ratioif split_info == 0:return 0else:return gain / split_infodef _entropy(self, y):unique_classes, counts = np.unique(y, return_counts=True)probs = counts / len(y)return -np.sum(probs * np.log2(probs + 1e-10))  # Adding a small constant to avoid log(0)def _most_common_class(self, y):return np.bincount(y).argmax()def predict(self, X):return np.array([self._predict(sample, self.tree) for sample in X])def _predict(self, sample, tree):if not isinstance(tree, dict):return treefeature_index = next(iter(tree))feature_value = sample[feature_index]if feature_value in tree[feature_index]:subtree = tree[feature_index][feature_value]return self._predict(sample, subtree)else:return None  # Unknown value# 示例使用
if __name__ == "__main__":# 示例数据集data = {'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rainy', 'Rainy', 'Rainy', 'Overcast', 'Sunny', 'Sunny', 'Rainy', 'Sunny', 'Overcast', 'Overcast'],'Temperature': ['Hot', 'Hot', 'Hot', 'Mild', 'Cool', 'Cool', 'Mild', 'Mild', 'Hot', 'Mild', 'Mild', 'Hot', 'Cool'],'Humidity': ['High', 'High', 'High', 'High', 'Normal', 'Normal', 'Normal', 'High', 'Normal', 'Normal', 'High', 'Normal', 'Normal'],'Windy': [False, True, False, False, False, True, True, False, False, False, True, True, False],'Play': [False, False, True, True, True, False, True, False, True, True, False, True, True]}# 将数据转换为DataFrame并编码df = pd.DataFrame(data)X = df.drop('Play', axis=1).apply(lambda col: pd.factorize(col)[0]).valuesy = df['Play'].values# 训练C4.5决策树c45 = C45(min_samples_split=2)c45.fit(X, y)# 进行预测predictions = c45.predict(X)print("预测结果:", predictions)

3. 基尼指数（CART算法）（Classification and Regression Tree）：选择基尼指数最小的特征。

既可以用于分类任务，也可以用于回归任务

生成二叉树结构。

• 在分类任务中，选基尼指数小的特征作为划分数据集的特征

• 在回归任务中，用均方误差作为准则
  

• 对每个特征，遍历所有可能的切分点。对于每个切分点，将数据集分为两个子集：
  L左子集：特征值小于或等于切分点的样本。
  R右子集：特征值大于切分点的样本。
  计算每个切分点的均方误差，选择使得均方误差最小化的特征和切分点。（特征，特征取值）

例子

从“面积”特征开始，尝试不同的切分点。假设我们选择一个切分点，比如2000平方英尺。
左子集（面积 ≤ 2000）
右子集（面积 > 2000）
这个2000是要通过计算求的，最小化均方误差得到的值这里只是举例计算argmin MSE，得到2000这个结果，这是一个特征的，对不同特征，用相同思想计算切分点（这里的2000）的值

这屋里总的误差可以加权，也可以左右子集的结果直接相加

找到MSE最小的切分点。（特征，特征取值）对每个子集进行相同的切分过程

剪枝

预剪枝（Pre-Pruning）

在构建决策树的过程中，提前停止树的生长。在创建每
个节点时，会根据某些准则决定是否继续分裂。

假设我们有一个决策树节点，包含10个样本，如果设置的最小样本数为5，则不再对该节点进行分裂，而是将其标记为叶节点。

• 优点：降低过拟合风险，减少训练时间和空间复杂度。
• 缺点：可能会因过早停止划分而欠拟合，错过一些有价值的划分。

后剪枝（Post-Pruning）

去掉一些不必要的分支来提高模型的泛化能力。

• 从下到上，逐步检查每个非叶节点的子树。如果该子树的替代叶节点（即将该节点变为叶节点）在验证集上的性能更好，则进行剪枝。
• 如果替代叶节点的误差率低于子树的误差率，则将该子树替换为该叶节点。
  
  
  

假设有一个用于分类的决策树，有以下几个节点：

节点 A：特征为“是否有工作”，分为有工作和无工作两个分支。

• 有工作分支节点 B：特征为“是否有房产”，分为有房产和无房产两个分支。
  • 有房产分支节点 C：类别为“批准贷款”。
  • 无房产分支节点 D：类别为“不批准贷款”。
• 无工作分支节点 E：特征为“收入水平”，分为高收入和低收入两个分支。
  • 高收入分支节点 F：类别为“批准贷款”。
  • 低收入分支节点 G：类别为“不批准贷款”。

1. 错误率降低剪枝示例：

   • 假设在验证集上，节点 B 及其子树的错误率为 30%，将节点 B 替换为叶节点，类别标记为该节点子树中样本数量最多的类别（假设为“批准贷款”），此时错误率为 25%。由于错误率降低了，所以进行剪枝，将节点 B 标记为叶节点，类别为“批准贷款”。

2. 悲观错误剪枝示例：

   • 假设节点 B 在训练集上的错误率为 20%，样本数量为 100。根据悲观错误率计算公式，$p=e+\frac{k}{2m}=0.2+\frac{0.5}{2\times 100}=0.2025$。将节点 B 替换为叶节点后，假设错误率为 18%。比较替换前后的悲观错误率，发现降低了，所以进行剪枝。

3. 代价复杂度剪枝示例：

   • 假设决策树在训练集上的错误率为 15%，叶节点数量为 7。对于节点 B，计算其子树的代价复杂度指标。假设参数$\alpha$为 0.1。根据代价复杂度指标计算公式，$R_{\alpha }(T)=R(T)+\alpha |T_{leaf}|=0.15+0.1\times 7=0.85$。依次计算其他节点的代价复杂度指标，选择代价复杂度最小的子树进行剪枝。