一、决策树简介

1.1 什么是决策树

        分类决策树模型是一种描述对实例进行分类的树形结构，由结点和有向边组成。结点包括两种类型：内部结点和叶结点，其中内部结点表示一个特征和属性，叶结点表示一个类。

□ 决策过程中提出的每个判定问题都是对某个属性的“测试”；

□ 决策过程的最终结论对应了我们所希望的判定结果；

□ 每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围内；

□ 从根结点到每个叶结点的路径对应了一个判定测试序列；

□ 决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

        如图3-1所示的流程图就是一个决策树，长方形代表判断模块，椭圆形代表终止模块，表示已经得出结论，可以终止运行；从判断模块引出的左右箭头称作分支 ，它可以到达另一个判断模块或终止模块。

1.2 决策树的构造

        构造决策树的三个步骤：特征选择，决策树生成，决策树剪枝。

        特征选择：当前数据集可能有多个特征(即属性)，每个特征的影响各不相同，这时就需要决定哪个特征在划分数据分类时起决定性作用，即筛选出跟分类结果相关性较高的特征；

        决策树生成：构建根结点，将所有训练数据放在根结点，然后基于最佳特征值划分数据集；如果这些数据子集已基本正确分类，那么构造叶结点，并将数据子集放到叶结点中去；如果还有子集不能正确分类，那么就对这些子集选择新的最佳特征值继续分割，构造相应的结点；按照上述过程对子集进行递归处理，直至满足终止条件；

终止条件：① 纯结点：当前结点的数据子集全属于同一个类别；

                  ② 空结点：当前结点的数据子集为空；

                  ③ 当前特征集为空，或者数据子集在特征值上取值相同，无法划分；

        决策树剪枝：剪枝是决策树学习算法处理“过拟合”的主要手段，可通过剪枝来一定程度避免因决策分支过多，以至于把训练集自身的特点当作所有数据都具有的一般性质而导致的过拟合； 

剪枝的基本策略：预剪枝，后剪枝；

判断决策树泛化性能是否提升的方法：留出法，即预留部分数据作为验证集以进行性能评估

 二、特征评价指标

        决策树的构建首先从根结点开始，选择最优的特征进行分类，“最优”是通过评价指标来决定的：信息增益(ID3算法)、信息增益率(C4.5算法)、基尼指数(CATR算法)。

2.1 信息增益

        在划分数据集之前之后信息发生的变化称为信息增益。

        首先我们要知道集合信息的度量方式称为香农熵或者简称为熵，熵定义为信息的期望值。那么什么是信息？如果待分类的事务可能划分在多个分类之中，则符号x_i{}的信息定义为：

                          l(x_i{}) = -\log _2{}p(x_i{})，其中p(x_i{})是选择该分类的概率。

        为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面公式得到： 

                              H = -\Sigma _{i-1}^{n}p(x_i{})\log _2{}p(x_i{})，其中n是分类的数目。

    如果一个数据集的熵值较低，说明数据集中大部分样本属于同一类别，纯度较高；反之，如果熵值较高，则说明数据集的类别分布较为均匀，纯度较低。

        离散属性a有v个可能取值{a1,a2,...,av}，用a来进行划分，则会产生v个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为av的样本，记为D^{v}，则可计算出属性a对样本集D进行划分所获得的信息增益：

                               Gain(D,a) = Ent(D) - \sum_{v=1}^{v}\frac{D^{v}}{\left | D \right |}Ent(D^{v}) 

                               \frac{D^{v}}{\left | D \right |}为分支结点权重，样本数越多的分支结点的影响越大。

        一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。 

        ID3(迭代二分器)算法以信息增益为指标来选择划分属性，选择信息增益最大的属性作为最优化分属性。

2.2 增益率

        属性a对训练集D的信息增益率定义为其信息增益与训练集D的关于特征A的值的熵之比，即：

           Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}，其中IV(a) = -\sum_{v=1}^{v}\frac{\left | D^{v} \right |}{\left | D \right |}\log _2{}\frac{\left | D^{v} \right |}{\left | D \right |} 

        IV(a)称为属性a的“固有值”，属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。

        C4.5算法以增益率为指标来选择划分属性，选择增益率最高的属性作为最优划分属性。

        增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法克服了ID3仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题。

2.3 基尼指数 

        分类问题中，假设有k个类，样本点属于第k类的概率为p_k{}，则概率分布的基尼值定义为：

        ​​​​​​​        ​​​​​​​             Gini(p) = \sum_{k=1}^{k}p_k{}(1-p_k{}) = 1-\sum_{k=1}^{k}p_k{}^{2}

        Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，数据集D的纯度越高；

        给定数据集D，属性a的基尼指数定义为：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        Gini_i{}(D,a) = \sum_{v=1}^{v}\frac{\left | D^{v} \right |}{\left | D \right |}Gini(D^{v}) 

        CART算法以基尼指数为指标来选择划分属性，在候选属性集A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

三、示例：根据四种属性来决定是否给予贷款

3.1 准备数据集

ID 年龄段 有工作 有自己的房子 信贷情况 类别(是否给予贷款)
1 青年 否 否 一般 否
2 青年 否 否 好 否
3 青年 是 否 好 是
4 青年 是 是 一般 是
5 青年 否 否 一般 否
6 中年 否 否 一般 否
7 中年 否 否 好 否
8 中年 是 是 好 是
9 中年 否 是 非常好 是
10 中年 否 是 非常好 是
11 老年 否 是 非常好 是
12 老年 否 是 好 是
13 老年 是 否 好 是
14 老年 是 否 非常好 是
15 老年 否 否 一般 否
16 老年 否 否 非常好 否

训练集(将特征描述数值化)：

测试集：

年龄段：0代表青年，1代表中年，2代表老年；
有工作：0代表否，1代表是；
有自己的房子：0代表否，1代表是；
信贷情况：0代表一般，1代表好，2代表非常好；
类别(是否给予贷款)：0代表否，1代表是。

 3.2 ID3算法实现决策树

        3.2.1 计算信息熵

        在分类问题中，信息熵用于衡量数据集的纯度。ID3算法用信息增益作为指标选择划分属性，而信息增益是通过计算划分前后数据集的信息熵变化来衡量属性的区分能力。因此ID3算法要先计算信息熵，了解数据集的初始混乱程度，为后续的特征选择和决策树构建提供基础。

        ①先统计各类别样本的数量：借助collections模块中的Counter类，对标签向量y里各个类别出现的次数进行统计;

        ②计算各类别样本的概率：使用列表推导式，将每个类别出现的次数除以样本总数，得到该类别出现的概率；

        ③依据信息熵公式进行计算：利用推导式计算 pi​log2​(pi​)，接着使用np.sum函数求和，最后取负得到信息熵的值。

        3.2.2 计算信息增益

        ①调用信息熵计算算法计算父结点的信息熵；

        ②从特征矩阵X中提取目标列的属性值，再用np.unqiue()函数用于找出该特征的所有不同取值并存储起来；

        ③对于特征的每个取值value，找出数据集中该属性取值为value的样本的索引，根据这些索引从标签向量y中提取对应的子集，计算该子集的信息熵，之后再计算每个子集的权重(即子集样本数与总样本数的比值)，并将其与子集信息熵相乘，进行累加；

        ④计算信息增益：用父结点的信息熵减去所有子集信息熵的加权和。

        信息增益越大，说明使用该特征进行划分后，数据集的不确定性减少得越多，该属性对分类的贡献越大。

        3.2.3 ID3决策树的构建

        根据选择的最优划分属性，将数据集划分为多个子集，对每个子集递归地重复进行计算信息熵、计算信息增益、选择最优划分属性这三个步骤，实现递归构建决策树，直到满足停止条件。

        ID3算法以信息熵为基础，通过不断选择信息增益最大的属性进行分裂，递归地构建决策树。这样可以保证构建出的决策树在给定的数据集上能够尽可能准确地进行分类，即通过最小化信息熵来实现决策树的优化，使得决策树的深度尽可能小，提高模型的泛化能力和分类效率。

3.3 CART算法实现决策树

        3.3.1 计算基尼指数

        ①统计各类别样本的数量：借助collections模块中的Counter类，对标签向量y里各个类别出现的次数进行统计;

        ②计算各类别样本的概率：使用列表推导式，将每个类别出现的次数除以样本总数，得到该类别出现的概率；

        ③依据基尼指数公式进行计算：使用列表推导式计算每个类别概率的平方，然后使用np.sum对这些平方值求和，最后用1减去这个和，得到基尼指数。

        3.3.2 计算特征的基尼指数

        ①获取属性的唯一值：从特征矩阵X中提取目标列的所有属性值，用np.unique函数找出该列属性值中的所有唯一值并存储起来；

        ②初始化加权基尼指数：初始化一个变量用于存储最终计算得到的该属性的加权基尼指数，初始值设为0；

        ③遍历属性的每个唯一取值：对于属性的每个唯一取值value，找出特征矩阵X中目标列取值等于value的样本索引，根据这些索引从标签数组y中提取对应的子集标签，调用之前定义的函数计算子集的基尼指数，计算该子集的权重(即子集样本数与总样本数的比值)，然后将其与子集的基尼指数相乘，进行累加；

        ④最终返回计算得到的该属性的加权基尼指数，这个值越小，说明使用该属性对数据集进行划分后，数据的总体纯度越高，该属性也就越适合作为划分属性。

        3.3.3 CART决策树的构建

        ①引入sklearn库中的DecisionTreeClassifier类用于构建CART决策树分类器，accuracy_score函数用于计算分类准确率；

        ②创建一个DecisionTreeClassifier对象，使用基尼指数作为特征选择的标准；

        ③使用训练集数据和对应的标签对CART决策树模型进行训练，通过不断选择最优的特征和划分点，递归构建出决策树。

3.4 代码实现

import numpy as np
from collections import Counter
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

#创建数据集dataset和testset
dataset = np.array([
    [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]
])
testset = np.array([
    [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]
])

X_train = dataset[:,:-1]
y_train = dataset[:,-1]
X_test = testset[:,:-1]
y_test = testset[:,-1]
features = np.array(['年龄段','有工作','有自己的房子','信贷情况'])

#计算熵
def entropy(y):
    counter = Counter(y)
    probabilities = [count / len(y) for count in counter.values()]
    return -np.sum([p * np.log2(p) for p in probabilities])

#计算信息增益
def information_gain(X, y, feature_index):
    parent_entropy = entropy(y)
    unique_values = np.unique(X[:, feature_index])
    weighted_entropy = 0
    for value in unique_values:
        subset_indices = X[:, feature_index] == value
        subset_y = y[subset_indices]
        subset_entropy = entropy(subset_y)
        weighted_entropy += (len(subset_y) / len(y)) * subset_entropy
    return parent_entropy - weighted_entropy

#计算基尼指数
def gini_index(y):
    counter = Counter(y)
    probabilities = [count / len(y) for count in counter.values()]
    return 1 - np.sum([p ** 2 for p in probabilities])

#计算特征的基尼指数
def feature_gini_index(X, y, feature_index):
    unique_values = np.unique(X[:, feature_index])
    weighted_gini = 0
    for value in unique_values:
        subset_indices = X[:, feature_index] == value
        subset_y = y[subset_indices]
        subset_gini = gini_index(subset_y)
        weighted_gini += (len(subset_y) / len(y)) * subset_gini
    return weighted_gini

#ID3算法构建决策树
def id3(X, y, features):
    if len(np.unique(y)) == 1:
        return np.unique(y)[0]
    if len(features) == 0:
        return Counter(y).most_common(1)[0][0]
    best_feature_index = np.argmax([information_gain(X, y, i) for i in range(X.shape[1])])
    best_feature = features[best_feature_index]
    tree = {best_feature: {}}
    new_features = np.delete(features, best_feature_index)
    unique_values = np.unique(X[:, best_feature_index])
    for value in unique_values:
        subset_indices = X[:, best_feature_index] == value
        subset_X = X[subset_indices]
        subset_y = y[subset_indices]
        subtree = id3(subset_X, subset_y, new_features)
        tree[best_feature][value] = subtree
    return tree

#使用ID3决策树进行预测
def predict_id3(tree, sample, features):
    if not isinstance(tree, dict):
        return tree
    feature = list(tree.keys())[0]
    feature_index = np.where(features == feature)[0][0]
    value = sample[feature_index]
    subtree = tree[feature].get(value)
    if subtree is None:
        return Counter(sample).most_common(1)[0][0]
    return predict_id3(subtree, sample, features)

#计算每个特征的信息增益和基尼指数
print("每个特征的信息增益和基尼指数：")
for i, feature in enumerate(features):
    info_gain = information_gain(X_train, y_train, i)
    gini = feature_gini_index(X_train, y_train, i)
    print(f"{feature}: 信息增益 = {info_gain:.4f}, 基尼指数 = {gini:.4f}")

#使用ID3算法
id3_tree = id3(X_train, y_train, features)
id3_predictions = [int(predict_id3(id3_tree, sample, features)) for sample in X_test]
id3_accuracy = accuracy_score(y_test, id3_predictions)
print("ID3 算法详细结果：")
print("预测结果:", id3_predictions)
print("真实结果:", y_test.tolist())
print(f"准确率: {id3_accuracy * 100:.2f}%")

#使用CART算法
cart_model = DecisionTreeClassifier(criterion='gini')
cart_model.fit(X_train, y_train)
cart_predictions = cart_model.predict(X_test)
cart_accuracy = accuracy_score(y_test, cart_predictions)
print("CART 算法详细结果：")
print("预测结果:", cart_predictions.tolist())
print("真实结果:", y_test.tolist())
print(f"准确率: {cart_accuracy * 100:.2f}%")

运行测试结果截图：

四、实验小结

        决策树的优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据，可解释性强；

        缺点：容易过拟合，对数据分布敏感，特征选择的局限性，不适合处理高维数据。

        实验收获：深入理解了ID3、C4.5、CART算法的原理，掌握了信息熵、信息增益、增益率、基尼指数等核心概念及其计算方法，以及它们在衡量数据纯度和特征重要性方面的作用。

        学会使用sklearn库便捷地实现CART算法，了解了库函数的参数设置和使用方法；

        认识到决策树作为一种直观的机器学习模型，在分类问题中具有良好的可解释性，能够清晰地展示决策过程和特征对结果的影响，可广泛应用于多个领域。

# 机器学习 # 决策树 # 人工智能
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

识别物体 3D 位置 + 自动生成机器人抓取位姿」

的 3 条主流实现路径，从到，每条都讲清楚原理、硬件、流程、怎么生成抓取点。

avatar DAMO开发者矩阵
cover

Unitree MuJoCo 键盘替代手柄控制说明

avatar DAMO开发者矩阵
cover

机器人顶会和期刊

avatar DAMO开发者矩阵