目录

1.决策树的基本概念

 2.决策树的构造算法

2.1 ID3(Iterative Dichotomiser 3)

2.2 C4.5

2.3基尼指数(CART)

3决策树代码实战

3.1 使用ID3构造决策树

3.2使用C4.5构造决策树

3.3两种算法的代码分析

4.总结

1.决策树的基本概念

决策树是一种基于树结构的机器学习算法，用于分类和回归任务。它通过对数据集进行递归地划分，每次选择最优特征进行分裂，直到满足停止条件为止。在分类任务中，每个叶节点表示一个类别；在回归任务中，每个叶节点表示一个数值。

决策树优缺点

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

缺点：可能会产生过度匹配问题。

适用数据类型：数值型和标称型。

决策树的主要组成包括：

  1. 根节点（Root Node）：决策树的起始节点，代表整个数据集。

  2. 内部节点（Internal Nodes）：非叶子节点，表示一个特征属性及其对应的判断条件。

  3. 叶节点（Leaf Nodes）：最终的输出节点，表示一个类别或者数值。

  4. 分裂条件（Splitting Criteria）：决定在每个内部节点如何分裂数据集的条件，常见的包括基尼系数、信息增益、信息增益率等。

  5. 决策规则（Decision Rules）：由决策树的结构和节点组成，用于对新样本进行分类或回归预测。

  6. 剪枝（Pruning）：一种防止过拟合的技术，通过删除一些不必要的节点来简化树结构。

  7. 特征重要性（Feature Importance）：衡量每个特征对模型预测的贡献程度。

  8. 深度（Depth）：决策树的层数，表示树的复杂度和泛化能力。

决策树的一般流程

（1）收集数据：可以使用任何方法

（2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化

（3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期

（4）训练算法：构造树的数据结构

（5）测试算法：使用经验树计算错误率

（6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义

 2.决策树的构造算法

2.1 ID3(Iterative Dichotomiser 3)

ID3算法采用信息增益（Information Gain）作为特征选择的标准。信息增益是基于信息论的概念，表示使用特征A对样本集合进行划分所获得的信息增益。信息增益越大，表示特征A对分类的能力越强。

信息增益的计算基于信息熵（Entropy）的概念，信息熵定义为信息的期望值，信息熵越大，则表明数据集的混乱程度越大。

数据集D的信息熵用如下公式表示：

 H(D)=- \sum_{i-1}^{n}p(x_{i})\log _{2}p(x_{i})

在给定特征 ( A ) 的条件下，数据集 ( D ) 的信息熵为：

H(D|A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i)

信息增益公式为：

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

2.2 C4.5

C4.5算法是ID3算法的改进版本，它在信息增益的基础上引入了信息增益比（Gain Ratio）来解决ID3算法对取值较多特征的偏向性问题。

下面是C4.5算法中使用的公式，前面的公式和ID3一样，最后多加了两个公式

分裂信息（Split Information）：

SplitInfo(A) = - \sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}

信息增益比（Gain Ratio）：

GainRatio(D,A) = \frac{G(D,A)}{SplitInfo(A)}

2.3基尼指数(CART)

决策树中的基尼指数是用来衡量节点的纯度或不纯度的指标之一。在构建决策树时，基尼指数通常用于选择最佳的划分特征，以便将数据集划分为纯度更高的子集。

基尼指数计算公式：

\text{Gini}(D) = 1 - \sum_{k=1}^{n} (p_k)^2

基尼指数的取值范围在0到1之间，数值越低表示节点的纯度越高，即样本的类别分布越趋于一致；而数值越高则表示节点的不纯度越高，即样本的类别分布越杂乱。

在构建决策树时，基尼指数通常与信息增益或信息增益比等指标一起使用，以帮助选择最佳的划分特征。通过选择基尼指数最小的划分点，可以使得子节点的纯度更高，从而提高了决策树的分类性能。

3决策树代码实战

对下面给出的数据构造出决策树

编号  色泽  根蒂  敲声  纹理  脐部  触感 好瓜

0       青绿  蜷缩  浊响  清晰  凹陷  硬滑  是

1       乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  是

2       乌黑  蜷缩  浊响  清晰  凹陷  硬滑  是

3       青绿  蜷缩  沉闷  清晰  凹陷  硬滑  是

4       浅白  蜷缩  浊响  清晰  凹陷  硬滑  是

5       青绿  稍蜷  浊响  清晰  稍凹  软粘  是

6       乌黑  稍蜷  浊响  稍糊  稍凹  软粘  是

7       乌黑  稍蜷  浊响  清晰  稍凹  硬滑  是

8       乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  否

9       青绿  硬挺  清脆  清晰  平坦  软粘  否

10     浅白  硬挺  清脆  模糊  平坦  硬滑  否

11     浅白  蜷缩  浊响  模糊  平坦  软粘  否

12     青绿  稍蜷  浊响  稍糊  凹陷  硬滑  否

13     浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  否

14     乌黑  稍蜷  浊响  清晰  稍凹  软粘  否

15     浅白  蜷缩  浊响  模糊  平坦  硬滑  否

16     青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  否

3.1 使用ID3构造决策树

import math


Data = [
        # 1
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 2
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        # 3
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 4
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        # 5
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        # 6
        ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
        # 7
        ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
        # 8
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
        # 9
        ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
        # 10
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
        # 11
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
        # 12
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
        # 13
        ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
        # 14
        ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
        # 15
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
        # 16
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
        # 17
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
]#引入数据集




def entropy(data):
    # 计算数据集的总体熵
    labels = [row[-1] for row in data]
    label_counts = {}
    for label in labels:
        if label not in label_counts:
            label_counts[label] = 0
        label_counts[label] += 1
    entropy = 0.0
    for count in label_counts.values():
        prob = count / len(data)
        entropy -= prob * math.log2(prob)
    return entropy

def split_data(data, column, value):
    # 根据特征列的值将数据集分割成子集
    sub_data = []
    for row in data:
        if row[column] == value:
            sub_row = row[:column] + row[column+1:]
            sub_data.append(sub_row)
    return sub_data

def information_gain(data, base_entropy, column):
    # 计算特征列的信息增益
    unique_values = set([row[column] for row in data])
    new_entropy = 0.0
    for value in unique_values:
        sub_data = split_data(data, column, value)
        prob = len(sub_data) / len(data)
        new_entropy += prob * entropy(sub_data)
    information_gain = base_entropy - new_entropy
    return information_gain

def choose_best_feature(data):
    # 选择信息增益最大的特征作为划分特征
    num_features = len(data[0]) - 1
    base_entropy = entropy(data)
    best_information_gain = 0.0
    best_feature = -1
    for i in range(num_features):
        info_gain = information_gain(data, base_entropy, i)
        if info_gain > best_information_gain:
            best_information_gain = info_gain
            best_feature = i
    return best_feature

def create_tree(data, labels):
    # 递归构造决策树
    class_list = [row[-1] for row in data]
    if class_list.count(class_list[0]) == len(class_list):
        # 如果所有样本属于同一类别，则返回该类别
        return class_list[0]
    if len(data[0]) == 1:
        # 如果所有特征已经使用完毕，则返回样本数最多的类别
        label_counts = {}
        for label in class_list:
            if label not in label_counts:
                label_counts[label] = 0
            label_counts[label] += 1
        sorted_label_counts = sorted(label_counts.items(), key=lambda x: x[1], reverse=True)
        return sorted_label_counts[0][0]
    best_feature = choose_best_feature(data)
    best_feature_label = labels[best_feature]
    tree = {best_feature_label: {}}
    del(labels[best_feature])
    feature_values = [row[best_feature] for row in data]
    unique_values = set(feature_values)
    for value in unique_values:
        sub_labels = labels[:]
        tree[best_feature_label][value] = create_tree(split_data(data, best_feature, value), sub_labels)
    return tree

# 构造决策树
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
tree = create_tree(data=Data, labels=labels)
print(tree)

运行结果为：{'纹理': {'稍糊': {'触感': {'软粘': '好瓜', '硬滑': '坏瓜'}}, '模糊': '坏瓜', '清晰': {'根蒂': {'硬挺': '坏瓜', '稍蜷': {'色泽': {'乌黑': {'触感': {'软粘': '坏瓜', '硬滑': '好瓜'}}, '青绿': '好瓜'}}, '蜷缩': '好瓜'}}}}

3.2使用C4.5构造决策树

在前面的基础上进行修改，计算信息增益比，即可得到下面的代码

def entropy(data):
    # 计算数据集的总体熵
    labels = [row[-1] for row in data]
    label_counts = {}
    for label in labels:
        if label not in label_counts:
            label_counts[label] = 0
        label_counts[label] += 1
    entropy = 0.0
    for count in label_counts.values():
        prob = count / len(data)
        entropy -= prob * math.log2(prob)
    return entropy


def split_data(data, column, value):
    # 根据特征列的值将数据集分割成子集
    sub_data = []
    for row in data:
        if row[column] == value:
            sub_row = row[:column] + row[column + 1:]
            sub_data.append(sub_row)
    return sub_data


def information_gain_ratio(data, base_entropy, column):
    # 计算特征列的信息增益比
    unique_values = set([row[column] for row in data])
    new_entropy = 0.0
    split_info = 0.0
    for value in unique_values:
        sub_data = split_data(data, column, value)
        prob = len(sub_data) / len(data)
        new_entropy += prob * entropy(sub_data)
        split_info -= prob * math.log2(prob)
    if split_info == 0:
        return 0  # 避免出现除以零的情况
    information_gain_ratio = (base_entropy - new_entropy) / split_info
    return information_gain_ratio


def choose_best_feature(data):
    # 选择信息增益比最大的特征作为划分特征
    num_features = len(data[0]) - 1
    base_entropy = entropy(data)
    best_information_gain_ratio = 0.0
    best_feature = -1
    for i in range(num_features):
        info_gain_ratio = information_gain_ratio(data, base_entropy, i)
        if info_gain_ratio > best_information_gain_ratio:
            best_information_gain_ratio = info_gain_ratio
            best_feature = i
    return best_feature

def create_tree(data, labels):
    # 递归构造决策树
    class_list = [row[-1] for row in data]
    if class_list.count(class_list[0]) == len(class_list):
        # 如果所有样本属于同一类别，则返回该类别
        return class_list[0]
    if len(data[0]) == 1:
        # 如果所有特征已经使用完毕，则返回样本数最多的类别
        label_counts = {}
        for label in class_list:
            if label not in label_counts:
                label_counts[label] = 0
            label_counts[label] += 1
        sorted_label_counts = sorted(label_counts.items(), key=lambda x: x[1], reverse=True)
        return sorted_label_counts[0][0]
    best_feature_index = choose_best_feature(data)
    best_feature_label = labels[best_feature_index]
    decision_tree = {best_feature_label: {}}
    del (labels[best_feature_index])
    feature_values = [row[best_feature_index] for row in data]
    unique_values = set(feature_values)
    for value in unique_values:
        sub_labels = labels[:]
        decision_tree[best_feature_label][value] = create_tree(split_data(data, best_feature_index, value), sub_labels)
    return decision_tree

# 测试
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
tree = create_tree(Data, labels)
print(tree)

运行结果为：{'纹理': {'稍糊': {'触感': {'硬滑': '坏瓜', '软粘': '好瓜'}}, '模糊': '坏瓜', '清晰': {'触感': {'软粘': {'色泽': {'乌黑': '坏瓜', '青绿': {'根蒂': {'硬挺': '坏瓜', '稍蜷': '好瓜'}}}}, '硬滑': '好瓜'}}}}

3.3两种算法的代码分析

  1. ID3算法 (Iterative Dichotomiser 3):

    • 优点:
      • 算法简单易懂，易于实现和理解。
      • 对于具有较少属性的数据集和较小的数据量，通常具有较好的性能。
    • 缺点:
      • 对于连续型特征的处理较为困难，ID3算法只能处理离散型特征。
      • 对于具有缺失值的数据集，ID3算法的表现较差，因为它无法处理缺失值。
      • 生成的决策树可能过度拟合训练数据。

  2. C4.5算法:

    • 优点:
      • 能够处理连续型特征和离散型特征，具有更强的适用性。
      • 能够处理具有缺失值的数据集，在构建决策树时能够处理缺失值。
      • 通过使用信息增益率（Gain Ratio）来解决了ID3算法中对具有更多取值的特征偏向的问题。
      • 生成的决策树通常更加精简，减少了过拟合的风险。
    • 缺点:
      • 在处理大规模数据集时，由于C4.5算法需要多次扫描数据集以计算特征的信息增益率，因此算法效率较低。
      • 对于具有大量属性的数据集，C4.5算法倾向于选择取值较多的属性，导致决策树的构建过程较为耗时。

4.总结

优点：

  1. 适用性广泛： 决策树算法适用于分类和回归问题，并且在实际应用中被广泛使用。

  2. 对数据预处理要求低： 决策树算法对数据预处理的要求相对较低，能够处理缺失值和不完整数据，适用于处理实际中的复杂数据集。

  3. 处理多类别问题能力强： 决策树算法能够自然地处理多类别问题，无需额外的复杂处理。

  4. 易于实现和调试： 决策树算法的原理相对简单，易于实现和调试，适用于快速建立基准模型。

缺点：

  1. 容易过拟合： 决策树算法容易受到训练数据中噪声和异常值的影响，导致过拟合问题。为了减少过拟合，需要进行剪枝等操作。

  2. 对连续性特征处理能力不足： 传统的决策树算法如ID3在处理连续性特征时存在一定的局限性，可以通过改进算法如C4.5来解决。

  3. 不稳定性： 对数据的微小变化可能会导致生成的决策树发生较大变化，使得模型不稳定。

  4. 存在偏差： 决策树算法倾向于选择取值较多的属性进行分裂，可能导致生成的决策树存在一定的偏差。

  5. 处理特征关联性较差： 决策树算法在处理特征关联性较强的数据集时可能表现不佳，因为它们只考虑每个特征的独立性。

综上所述，决策树算法是一种简单而有效的机器学习算法，但在实际应用中需要注意过拟合、数据准备和特征选择等问题。

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

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

更多推荐

cover

适合新手小白本地部署的养‘虾‘之路

avatar DAMO开发者矩阵

OpenClaw 进阶实战：从“能用”到“好用”的 7 个自动化工作流

本文聚焦OpenClaw从基础安装到生产力提升的实战进阶，提出自动化工作流四层架构（触发→执行→整理→分发），并给出7个可直接套用的高频场景模板，如早报机器人、CSDN选题雷达等。核心避坑经验包括约束输出格式、分段执行链路及异常兜底策略。文章强调OpenClaw的价值在于“可执行闭环”而非问答交互，通过结构化工作流（附提示词模板）将其转化为稳定产出的“自动化同事”。适合创作者的写作模板突出痛点解决

avatar DAMO开发者矩阵
cover

Agent的大脑：大模型如何让AI从工具变伙伴

avatar DAMO开发者矩阵