机器学习——决策树

优点简单易理解：决策树的结构类似于人类的决策过程，具有很好的可解释性。可以通过树状图直观地展示决策过程和规则，易于理解和解释。非线性关系：决策树能够处理线性和非线性关系，不要求数据线性可分。通过分裂节点，决策树可以捕捉复杂的模式和关系。特征选择：决策树可以自动进行特征选择，重要特征会被优先分裂，提高了模型的性能和效率。处理缺失值：决策树在处理缺失值时具有一定的鲁棒性，能够有效地处理部分缺失的数据。

杨珊珊珊珊

912人浏览 · 2025-04-21 22:38:07

杨珊珊珊珊 · 2025-04-21 22:38:07 发布

1 决策树算法介绍

决策树(Decision Tree,又称为判定树)算法是机器学习中常见的一类算法，是一种以树结构形式表达的预测分析模型。决策树属于监督学习（Supervised learning），根据处理数据类型的不同，决策树又为分类决策树与回归决策树。最早的的决策树算法是由Hunt等人于1966年提出，Hunt算法是许多决策树算法的基础，包括ID3、C4.5和CART等。

1.1 决策树原理

决策树的主要思想是根据已知数据构建一棵树，通过对待分类或回归的样本进行逐步的特征判断，最终将其分类或回归至叶子节点。

决策树学习的关键在于如何选择最优的划分属性，所谓的最优划分属性，对于二元分类而言，就是尽量使划分的样本属于同一类别，即“纯度”最高的属性。那么如何来度量特征（features）的纯度，这时候就要用到“信息熵（information entropy）”。先来看看信息熵的定义：假如当前样本集D中第k类样本所占的比例为Pk(k=1,2,3,......|y|)，|y|为类别的总数（对于二元分类来说，|y|=2）。则样本集的信息熵为：

Ent(D)的值越小，则D的纯度越高。再来看一个概念信息增益（information gain），假定离散属性有V个可能的取值{a1,a2,......av}，如果使用特征a来对数据集D进行划分，则会产生V个分支结点，其中第v（小v）个结点包含了数据集D中所有在特征a上取值为av的样本总数，记为Dv。因此可以根据上面信息熵的公式计算出信息熵，再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予权重|Dv|/|D|，从这个公式能够发现包含的样本数越多的分支结点的影响越大（这样是信息增益的一个缺点，即信息增益对可取值数目多的特征有偏好（即该属性能取得值越多，信息增益，越偏向这个），待会后面会举例子说明，这个缺点可以用信息增益率来解决）。因此，能够计算出特征a对样本集D进行划分所获得的“信息增益”:

一般而言，信息增益越大，则表示使用特征a对数据集划分所获得的“纯度提升”越大。所以信息增益可以用于决策树划分属性的选择，其实就是选择信息增益最大的属性，ID3算法就是采用的信息增益来划分属性。

1.2 决策树中的关键概念

节点：决策树由许多节点组成，其中分为两种类型：内部节点和叶子节点。内部节点表示某个特征，而叶子节点表示某个类别或回归值。
分支：每个内部节点连接着一些分支，每个分支代表着某个特征取值，表示样本在该特征上的取值。
根节点：决策树的根节点是整棵树的起点，即第一个判断特征的节点。
决策规则：决策树的每个节点表示一条决策规则，即对某个特征的判断，其决策规则是由已知数据集计算而得的。
剪枝：决策树为了避免过度拟合（Overfitting），通常会在构建好树之后进行剪枝操作，即去掉一些决策规则，以避免模型过于复杂。

1.3 决策树的实现流程

数据预处理：将原始数据转换成决策树可处理的数据格式。对于分类问题，需要将类别变量编码为数字；对于连续变量，需要进行离散化处理。
特征选择：从所有可用的特征中选择一个最佳的特征，用于划分数据集。常用的特征选择算法有信息增益、信息增益比和基尼指数等。
决策树的构建：将数据集递归地划分成越来越小的子集，直到数据集不能再被划分，或者达到预定的停止条件。在每个节点上选择最佳的特征，将数据集划分成两个子集，并在子集上递归地执行此过程，直到子集不能再被划分。
剪枝：为了避免过拟合，可以在构建完整棵树之后，对决策树进行剪枝。剪枝分为预剪枝和后剪枝两种方法。预剪枝是在决策树构建过程中，通过限制树的深度、节点数或其他条件，避免过拟合。后剪枝是在决策树构建完成之后，通过对子树进行剪枝，来减少决策树的复杂度。
决策树的评估：通过测试集或交叉验证等方法，对决策树的性能进行评估。评估指标包括准确率、精确率、召回率、F1分数等。
预测：将待预测的样本依次从根节点开始进行判断，按照决策规则向下移动，直到到达某个叶子节点，将样本归类于该叶子节点所代表的类别。

1.4 决策树的划分选择

熵：物理意义是体系混乱程度的度量。

信息熵：表示事物不确定性的度量标准，可以根据数学中的概率计算，出现的概率就大，出现的机会就多，不确定性就小（信息熵小）。

（1）信息增益

假设训练数据集D和特征A，根据如下步骤计算信息增益：

第一步：计算数据集D的经验熵：

第二步：计算特征A对数据集D的经验条件熵Ent(D|A)：

第三步：计算信息增益：

一般而言，信息增益越大，则意味着使用属性A来进行划分所获得的“纯度提升” 越大。因此，我们可使用信息增益来进行决策树的划分属性选择。ID3决策树学习算法就是以信息增益为准则来选择划分属性的。

（2）信息增益率

特征A对于数据集D的信息增益比定义为：

其中，

称为数据集D关于A的取值熵。

增益率准则就可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

（3）基尼指数

二分类问题：

对给定的样本集合D，基尼指数：

CART决策树使用“基尼指数”来选择划分属性。数据集D的纯度可用基尼值来度量，Gini(D)越小，则数据集的纯度越高。CART生成的是二叉树，计算量相对来说不是很大，可以处理连续和离散变量，能够对缺失值进行处理。

1.5ID3算法：

ID3（Iterative Dichotomiser 3）算法是决策树算法中最早的一种，使用信息增益来选择最优特征。ID3算法基于贪心思想，一直选择当前最优的特征进行分割，直到数据集分割完成或没有特征可分割为止。

1.6 剪枝处理

决策树算法很容易过拟合，剪枝算法就是用来防止决策树过拟合，提高泛华性能的方法。剪枝分为预剪枝与后剪枝。

预剪枝

预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。

预剪枝方法有：
（1）当叶节点的实例个数小于某个阈值时停止生长；
（2）当决策树达到预定高度时停止生长；
（3）当每次拓展对系统性能的增益小于某个阈值时停止生长；

预剪枝不足就是剪枝后决策树可能会不满足需求就被过早停止决策树的生长。

后剪枝

后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。

后剪枝决策树通常比预剪枝决策树保留了更多的分枝，一般情形下，后剪枝决策树的欠拟合风险很小，泛化能力往往优于预剪枝决策树。但后剪枝决策树是在生产完全决策树之后进行的，并且要自底向上地对所有非叶子节点进行逐一考察，因此其训练时间开销比未剪枝的决策树和预剪枝的决策树都要大很多。

1.7算法实现

数据集的准备

训练集

测试集

ID3算法实现：

import pandas as pd
import math
from pprint import pprint
 
# 加载训练集和测试集数据
train_data = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 1, 0, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 2, 1],
    [1, 0, 1, 2, 1],
    [2, 0, 1, 2, 1],
    [2, 0, 1, 1, 1],
    [2, 1, 0, 1, 1],
    [2, 1, 0, 2, 1],
    [2, 0, 0, 0, 0],
    [2, 0, 0, 2, 0]
]
 
test_data = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 0, 1, 2, 1],
    [1, 0, 0, 1, 0],
    [2, 1, 0, 2, 1],
    [2, 0, 0, 0, 0],
    [2, 0, 0, 2, 0]
]
 
columns = ['年龄', '工作', '房子', '信贷', '类别']
 
# 创建DataFrame
df_train = pd.DataFrame(train_data, columns=columns)
df_test = pd.DataFrame(test_data, columns=columns)
 
 
# 熵计算函数
def entropy(s):
    counts = s.value_counts()
    proportions = counts / len(s)
    return -sum(proportions * proportions.apply(math.log2))
 
 
# 信息增益计算
def info_gain(data, feature, target):
    total_entropy = entropy(data[target])
    weighted_entropy = 0
 
    for value in data[feature].unique():
        subset = data[data[feature] == value]
        weighted_entropy += (len(subset) / len(data)) * entropy(subset[target])
 
    return total_entropy - weighted_entropy
 
 
# 选择最佳特征
def choose_best_feature(data, features, target):
    gains = {feature: info_gain(data, feature, target) for feature in features}
    return max(gains, key=gains.get)
 
 
# 递归构建决策树
def build_tree(data, features, target):
    # 终止条件1: 所有样本属于同一类别
    if len(data[target].unique()) == 1:
        return data[target].iloc[0]
 
    # 终止条件2: 没有可用特征
    if not features:
        return data[target].mode()[0]
 
    best_feature = choose_best_feature(data, features, target)
    tree = {best_feature: {}}
 
    # 递归构建子树
    remaining_features = [f for f in features if f != best_feature]
    for value in data[best_feature].unique():
        subset = data[data[best_feature] == value]
        if subset.empty:
            tree[best_feature][value] = data[target].mode()[0]
        else:
            subtree = build_tree(subset, remaining_features, target)
            tree[best_feature][value] = subtree
 
    return tree
 
 
# 构建决策树
features = ['年龄', '工作', '房子', '信贷']
target = '类别'
decision_tree = build_tree(df_train, features, target)
 
print("生成的决策树结构：")
pprint(decision_tree)
 
 
# 预测函数
def predict(sample, tree):
    while isinstance(tree, dict):
        feature = next(iter(tree))  # 获取当前节点特征
        value = sample[feature]
        if value not in tree[feature]:  # 处理未见过的特征值
            return None
        tree = tree[feature][value]
    return tree
 
 
# 在测试集上进行预测
correct = 0
total = len(df_test)
predictions = []
 
for idx, row in df_test.iterrows():
    sample = row[features].to_dict()
    true_label = row[target]
    pred_label = predict(sample, decision_tree)
    predictions.append(pred_label)
    if pred_label == true_label:
        correct += 1
 
# 添加预测结果到测试集DataFrame
df_test['预测类别'] = predictions
 
# 计算准确率
accuracy = correct / total
print("\n测试集预测结果：")
print(df_test[['年龄', '工作', '房子', '信贷', '类别', '预测类别']])
print(f"\n准确率: {accuracy:.2%}")

结果：

CART算法实现

import pandas as pd
from pprint import pprint
 
# 加载训练集和测试集数据
train_data = [
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1],
    [0, 1, 1, 0, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 2, 1],
    [1, 0, 1, 2, 1],
    [2, 0, 1, 2, 1],
    [2, 0, 1, 1, 1],
    [2, 1, 0, 1, 1],
    [2, 1, 0, 2, 1],
    [2, 0, 0, 0, 0],
    [2, 0, 0, 2, 0]
]
 
test_data = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 0, 1, 2, 1],
    [1, 0, 0, 1, 0],
    [2, 1, 0, 2, 1],
    [2, 0, 0, 0, 0],
    [2, 0, 0, 2, 0]
]
 
columns = ['年龄', '工作', '房子', '信贷', '类别']
 
df_train = pd.DataFrame(train_data, columns=columns)
df_test = pd.DataFrame(test_data, columns=columns)
 
 
# 基尼系数计算
def gini(s):
    counts = s.value_counts()
    return 1 - sum((counts / len(s)) ** 2)
 
 
# 寻找最佳分割点
def find_best_split(data, features, target):
    best_gini = float('inf')
    best_feature = None
    best_split = None
 
    for feature in features:
        for value in data[feature].unique():
            left = data[data[feature] == value]
            right = data[data[feature] != value]
 
            if len(left) == 0 or len(right) == 0:
                continue
 
            curr_gini = (len(left) * gini(left[target]) + len(right) * gini(right[target])) / len(data)
 
            if curr_gini < best_gini:
                best_gini = curr_gini
                best_feature = feature
                best_split = value
 
    return best_feature, best_split
 
 
# 递归构建二叉树
def build_tree(data, features, target):
    # 终止条件：所有样本类别相同
    if len(data[target].unique()) == 1:
        return {'class': data[target].iloc[0]}
 
    # 寻找最佳分割
    best_feature, best_split = find_best_split(data, features, target)
 
    # 终止条件：无法找到有效分割
    if best_feature is None:
        return {'class': data[target].mode()[0]}
 
    # 分割数据
    left_data = data[data[best_feature] == best_split]
    right_data = data[data[best_feature] != best_split]
 
    # 递归构建子树
    return {
        'feature': best_feature,
        'split': best_split,
        'left': build_tree(left_data, features, target),
        'right': build_tree(right_data, features, target)
    }
 
 
# 构建决策树
features = ['年龄', '工作', '房子', '信贷']
target = '类别'
cart_tree = build_tree(df_train, features, target)
 
print("生成的CART决策树结构：")
pprint(cart_tree, depth=4)
 
 
# 预测函数
def predict(sample, tree):
    if 'class' in tree:
        return tree['class']
    feature_val = sample[tree['feature']]
    if feature_val == tree['split']:
        return predict(sample, tree['left'])
    else:
        return predict(sample, tree['right'])
 
 
# 测试集预测
df_test['预测类别'] = df_test.apply(lambda row: predict(row, cart_tree), axis=1)
 
# 计算准确率
accuracy = (df_test['类别'] == df_test['预测类别']).mean()
print("\n测试集预测结果：")
print(df_test)
print(f"准确率: {accuracy:.2%}")

结果