一、机器学习算法与实践_04信息论与决策树算法笔记

标签：right 04 算法 train split print left best 决策树

1 信息论基础知识介绍

信息论是运用概率论与数理统计的方法，去研究信息、信息熵、通信系统、数据传输、密码学、数据压缩等问题的应用数学学科，熵（Entropy）是信息论中的一个重要概念，由克劳德·香农（Claude Shannon）提出，用于衡量信息的不确定性或系统的混乱程度

在机器学习中，熵的概念被用来评估数据集的不纯度，进而指导决策树等算法的构建

1.1 熵（Entropy）

• 定义：熵是衡量数据集混乱程度的指标，熵越大，混乱程度越高。

  • 在分类问题中，数据的类别越多，或每个类别的概率越均等，熵就越大
  • 在回归问题中，数据越集中，方差越小，熵越小；数据越分散，方差越大，熵越大

• 热力学第二定律中的熵增原理： 在一个孤立系统中，如果没有外力做功，系统会自然趋向于熵增，也就是混乱度或无序度的增加，例如：

  • 笔记和书籍如果长时间不整理，则桌面和书架上的东西就会越来越乱
  • 屋子如果长时间不打扫，则屋内卫生会越来越乱
  • 日程和待办事项如果长时间不办理，则工作进展会越来越乱

• 熵的计算公式：对于一个数据集，熵的计算公式为：

  

  其中，是数据集中第 i 个类别的概率，n是数据集的类别数量

  在log2的对数函数图像中，x从0到1的区间对应的y值都是负数，而作为一个概率，其大小也是在0到1的区间内，又因为熵不可能是负数，所以这个公式前面会有负号，使得最终结果是一个正数值

• 信息熵： 信息熵是熵在信息论中的应用，用于衡量信息的不确定性，信息熵越高，信息的不确定性越大

1.2 基尼系数（Gini Impurity）

• 定义：与熵的作用类似，基尼系数是一种衡量数据集不纯度的指标，用于决策树算法中，基尼系数越低，表示数据集的纯度越高，其不确定性也就越低

• 本质：基尼系数本质上是一种在工程上对熵计算的数学化简，可以省去一些较为麻烦的计算，从而降低工程的计算代价

• 计算公式：基尼系数的计算公式为：

  

  其中，是数据集中第 i 个类别的概率，n是数据集的类别数量

1.3 香农的观点

• 初始混乱：一个模型在没有训练时，其混乱程度（熵）是最高的，因为此时模型对数据的预测没有任何依据
• 训练过程：随着模型的训练，通过学习数据中的规律，模型的预测能力逐渐提高，系统的熵逐渐降低（即：模型训练的过程，本质上就是系统熵在不断下降的过程）
• 好的算法：一个好的算法应该能够快速降低系统的熵，即快速提高模型的预测准确性

2 熵的计算示例

一枚硬币有正反两面，假设有三个模型，分别能对我抛出这枚硬币的结果做预测

A模型：预测出结果是正面的概率为0.5，结果是反面的概率为0.5

B模型：预测出结果是正面的概率为0.7，结果是反面的概率为0.3

C模型：预测出结果是正面的概率为0.9，结果是反面的概率为0.1

则对于上面三个模型的熵计算方法如下：

# 引入numpy库，提供一些科学计算方法
import numpy as np

# 定义计算熵的函数
def entropy(probabilities):
    return -np.sum(probabilities * np.log2(probabilities))

# 定义每个模型对于抛此枚硬币的正反面结果概率预测
A = np.array([0.5, 0.5])
B = np.array([0.7, 0.3])
C = np.array([0.9, 0.1])

# 计算每个模型的熵
entropy_A = entropy(A)
entropy_B = entropy(B)
entropy_C = entropy(C)
print("模型A的熵为：", entropy_A)
print("模型B的熵为：", entropy_B)
print("模型C的熵为：", entropy_C)

运行结果：

模型A的熵为： 1.0
模型B的熵为： 0.8812908992306927
模型C的熵为： 0.4689955935892812

根据运行结果可知：

• 模型A的熵值最大（因为它的答案模棱两可，本身抛出一枚硬币的正反面概率就都是1/2，这是一个谁都清楚的道理，说明这个模型可能根本没有被训练过，很混乱）

• 模型C的熵值最小（因为它的答案很明确，它表明这枚硬币抛出后结果为正面的概率非常大，说明这是应该是经过了优秀的训练后得到的模型）

3 决策树算法基本介绍

3.1 定义

决策树是一种非常流行和好用的监督式学习算法，用于分类和回归任务，它通过从数据中学习决策规则来预测目标变量的值

决策树由节点（nodes）、分支（branches）和叶节点（leaves）组成，其中：

• 节点：代表一个特征或属性（分为根节点和子节点）
• 分支：代表决策规则或特征的测试结果
• 叶节点：代表最终的决策或预测结果

以实际生活中的场景来做一个简单的举例，现在有一段情景对话如下： 【母亲】：闺女啊，你也不小了，到现在还没有对象！妈很揪心啊，这不托王阿姨给你找了个几个相亲对象，这周挨个去见一面吧！ 【女儿】：年纪多大？ 【母亲】：25 【女儿】：长的帅不帅？ 【母亲】：挺帅的！ 【女儿】：收入高不高？有没有上进心？ 【母亲】：收入还行，蛮有上进心！

基于上述对话，母亲根据女儿对于相亲对象所关注的关键特征，建立了如下决策树

这种简单的决策树在生活中随处可见，根据女儿对于相亲对象所关注的重要特征（年龄、长相、收入等），来一步步构建特征分割方式（年纪大小、长相帅不帅、收入高不高等），从而让其进行最优的决策

3.2 核心思想

• 递归分割：决策树通过递归选择最佳特征进行数据分割的方式，来构建树的每个节点，这个过程一直持续到满足特定的停止条件，如达到最大树深、节点中的样本数小于某个阈值，或者分类的纯度已经足够高

• 特征选择：在每个节点，算法会选择一个特征和该特征的一个阈值来分割数据，特征选择的目的是最大化节点的“信息增益”或“基尼不纯度”的减少

• 信息增益：信息增益基于熵的概念，用于衡量使用某个特征进行分割后，数据集的不确定性减少的程度

• 基尼不纯度：基尼不纯度是一种衡量数据集纯度的方法，它基于数据集中一个随机选中的样本被错误分类到任意一个子集的概率

• 剪枝：为了防止过拟合，决策树算法通常会进行剪枝，剪枝可以是预剪枝（在树生长过程中提前停止），也可以是后剪枝（在树生长完成后移除不必要的分支）

• 处理缺失值：决策树可以处理数据中的缺失值，因为它可以在每个节点中考虑缺失值的情况，并为缺失值设计特定的分支

• 多类别分类：对于多类别的分类问题，决策树可以为每个类别构建一个独立的树，或者在树的叶节点使用多类别的分类器

3.3 加权信息增益

加权信息增益（Weighted Information Gain）是决策树算法中用于选择最佳分裂特征的一个核心概念，它基于信息增益的理论，但进一步考虑了数据集中每个子集的大小（权重），从而提高决策树的分类或回归性能

公式一：基于熵（entropy）

其中：

• Entropy_all​ 是分裂后整体数据集的加权熵
• Entropy_left​ 和 Entropy_right​ 分别是左子节点和右子节点的熵
• n_left​ 和 n_right​ 分别是左子节点和右子节点中的样本数量
• N 是总样本数量，即左子节点和右子节点样本数量之和

公式二：基于基尼系数（gini）

其中：

• Gini_all​ 是分裂后整体数据集的加权基尼系数
• Gini_left​ 和 Gini_right​ 分别是左子节点和右子节点的基尼系数
• n_left​ 和 n_right​ 分别是左子节点和右子节点中的样本数量
• N 是总样本数量，即左子节点和右子节点样本数量之和

3.4 关键特点与应用

决策树算法有着解释性强、特征重要性排序、可大可小等关键特点：

• 易于理解和解释：决策树的结构清晰，可以直观地展示数据的决策过程，使得模型的解释性很强

• 特征重要性排序：决策树可以评估各个特征对预测结果的影响程度，从而对特征的重要性进行排序

• 灵活性：决策树可以处理各种规模的数据集，既可以用于小规模数据集，也可以扩展到大规模数据集

• 集成学习的基础：决策树是许多集成学习算法的基础，如随机森林、梯度提升树等

决策树可应用于分类和回归任务之中：

• CART（Classification and regression tree，即：分类和回归树）：CART是一种常用的决策树算法，它可以用于分类和回归问题

• 训练：构建决策树的过程通常包括选择最佳分裂点、递归地构建树直到满足停止条件（如树的深度、节点中的最小样本数等）

• 推理：在决策树构建完成后，可以使用树中的决策规则对新数据进行推理，以预测目标变量的值

3.5 优缺点

• 决策树的优点包括：

  • 模型简单，易于理解和实现

  • 对于非线性关系也能很好地建模

  • 不需要数据标准化或归一化

• 决策树的缺点包括：

  • 容易过拟合，特别是在决策树很深的情况下

  • 对于某些类型的数据，如高维数据，可能不是最有效的算法

为了克服这些缺点，通常会使用剪枝（pruning）技术来减少树的复杂度，或者使用集成方法（随机森林、梯度提升树等）来提高模型的泛化能力

4 决策树算法实践

以鸢尾花的分类任务为例，下面介绍通过决策树算法来进行预测

4.1 以熵为特征分裂指标

# 引入load_iris，获取鸢尾花数据集
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)

# 引入train_test_split，将数据集切分为训练集和测试集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

# 在python中，sklearn.tree是 sklearn 库中的一个模块，它提供了决策树、随机森林等基于树的算法的实现
# 在sklearn.tree中，DecisionTreeClassifier就是用于决策树算法的分类器，所以我们需要先对其进行引入
from sklearn.tree import DecisionTreeClassifier

# DecisionTreeClassifier是一个类，所以应该用面向对象的思想对其进行使用（即：实例化对象）
# DecisionTreeClassifier的分裂指标有gini、entropy、log_loss这三种，默认为gini
# 1、gini（Gini Impurity）: 基尼不纯度是决策树算法中常用的一种度量，用于衡量一个节点内样本的不纯度。它基于每个类别的概率来计算，值越小表示节点越纯
# 2、entropy（Entropy）: 熵是信息论中的一个概念，用于衡量数据的不确定性，在决策树中，熵用于衡量一个节点的不纯度，其值越高表示节点的不确定性越大
# 3、log_loss（Log-Loss or Cross-Entropy Loss）: 对数损失（或交叉熵损失）是评估概率预测准确性的常用方法，通常用于多分类问题，它衡量的是模型预测概率分布与真实标签的概率分布之间的差异
# 在实际开发过程中，没有一刀切的答案，在不同的数据集和问题上，不同指标的表现可能会有很大差异，需要尝试多种设置，并根据最终表现来选择最符合需求的指标
# 这里为了学习熵这种指标的表现情况，设置criterion="entropy"
# 此外，还可以用max_depth指定分裂多少层（指定了就只分裂到指定层，不指定则决策树将完全生长，直到所有叶子节点都纯净
dtc = DecisionTreeClassifier(criterion="entropy")

# 训练模型时，需要将训练集（X_train和y_train）作为参数传入fit方法中
dtc.fit(X=X_train, y=y_train)
# 预测模型时，需要将测试集（X_test）作为参数传入predict方法中
y_pred = dtc.predict(X=X_test)

#将y_test与y_pred进行对比，看有多少个数是相等的，就可以得到预测的准确率
acc = (y_pred == y_test).mean()
print(f"预测的准确率为:{acc}")

为便于直观地理解决策树模型是如何进行决策的，下面用绘图的方法将上面代码对应的决策树进行绘制

# 引入matplotlib的pyplot函数，为绘图做准备
import matplotlib.pyplot as plt
# 如果是用pycharm等后端工具绘图，需要指定图形用户界面工具包
# import matplotlib
# matplotlib.use('TkAgg')  # 设置绘图后端为 TkAgg
# 在sklearn.tree中，plot_tree函数可以将训练好的决策树模型以图形的方式展示出来
from sklearn.tree import plot_tree

# 创建一个画布，并设置图形的宽度*高度为10*10英寸
plt.figure(figsize=(10, 10))

# 使用plot_tree函数，绘制上面dtc对象的决策树图形，并使用filled=True让树中的节点用颜色填充
# 颜色的深浅通常表示了不同的类别或基于某种度量（如gini、entropy）的值
plot_tree(dtc, filled=True)

# 显示图表
plt.show()

绘制后的图像如下：

4.2 以基尼系数为特征分裂指标

# 引入load_iris，获取鸢尾花数据集
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)

# 引入train_test_split，将数据集切分为训练集和测试集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

# 在python中，sklearn.tree是 sklearn 库中的一个模块，它提供了决策树、随机森林等基于树的算法的实现
# 在sklearn.tree中，DecisionTreeClassifier就是用于决策树算法的分类器，所以我们需要先对其进行引入
from sklearn.tree import DecisionTreeClassifier

# DecisionTreeClassifier是一个类，所以应该用面向对象的思想对其进行使用（即：实例化对象）
# DecisionTreeClassifier的分裂指标有gini、entropy、log_loss这三种，默认为gini
# 1、gini（Gini Impurity）: 基尼不纯度是决策树算法中常用的一种度量，用于衡量一个节点内样本的不纯度。它基于每个类别的概率来计算，值越小表示节点越纯
# 2、entropy（Entropy）: 熵是信息论中的一个概念，用于衡量数据的不确定性，在决策树中，熵用于衡量一个节点的不纯度，其值越高表示节点的不确定性越大
# 3、log_loss（Log-Loss or Cross-Entropy Loss）: 对数损失（或交叉熵损失）是评估概率预测准确性的常用方法，通常用于多分类问题，它衡量的是模型预测概率分布与真实标签的概率分布之间的差异
# 在实际开发过程中，没有一刀切的答案。在不同的数据集和问题上，不同指标的表现可能会有很大差异，需要尝试多种设置，并根据最终表现来选择最符合需求的指标
# 这里为了学习熵这种指标的表现情况，设置criterion="gini"（或不填写，采用默认值）
# 此外，还可以用max_depth指定分裂多少层（指定了就只分裂到指定层，不指定则决策树将完全生长，直到所有叶子节点都纯净
dtc = DecisionTreeClassifier(criterion="gini")

# 训练模型时，需要将训练集（X_train和y_train）作为参数传入fit方法中
dtc.fit(X=X_train, y=y_train)
# 预测模型时，需要将测试集（X_test）作为参数传入predict方法中
y_pred = dtc.predict(X=X_test)

#将y_test与y_pred进行对比，看有多少个数是相等的，就可以得到预测的准确率
acc = (y_pred == y_test).mean()
print(f"预测的准确率为:{acc}")

用绘图的方法将上面代码对应的决策树进行绘制

# 引入matplotlib的pyplot函数，为绘图做准备
import matplotlib.pyplot as plt
# 如果是用pycharm等后端工具绘图，需要指定图形用户界面工具包
# import matplotlib
# matplotlib.use('TkAgg')  # 设置绘图后端为 TkAgg
# 在sklearn.tree中，plot_tree函数可以将训练好的决策树模型以图形的方式展示出来，使得用户能够直观地理解模型是如何进行决策的
from sklearn.tree import plot_tree

# 创建一个画布，并设置图形的宽度*高度为10*10英寸
plt.figure(figsize=(10, 10))

# 使用plot_tree函数，绘制上面dtc对象的决策树图形，并使用filled=True让树中的节点用颜色填充
# 颜色的深浅通常表示了不同的类别或基于某种度量（如gini、entropy）的值
plot_tree(dtc, filled=True)

# 显示图表
plt.show()

绘制后的图像如下：

5 构建决策树过程的算法分析

5.1 降熵法

先定义两个函数，分别用于计算原数据集的熵，以及分裂后两个子数据集的加权熵

# 引入numpy库，提供一些科学计算方法
import numpy as np

# 定义计算熵的函数
def get_entropy(y_arr):
    _, counts = np.unique(y_arr, return_counts=True)
    probabilities = counts / counts.sum()
    return -np.sum(probabilities * np.log2(probabilities))

# 定义计算加权熵的函数
def get_entropy_all(N, n_left, entropy_left, n_right, entropy_right):
    return ((n_left / N) * entropy_left) + ((n_right / N) * entropy_right)

调用上面的函数，循环计算：按照每一列的每一个数据分裂之后，看哪次得到的两个分子数据集的加权熵最小，最小的即为最佳分裂点

# 引入load_iris，获取鸢尾花数据集
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)

# 引入train_test_split，将数据集切分为训练集和测试集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

# 切分之后，X_train.shape=(120, 4)，即：X_train有4个特征，共有120条数据
# 既然X_train.shape的结果是一个元组，那么就可以通过索引的方式来取出样本的特征个数
n_features = X_train.shape[1]

# 计算分裂的数据集本身的熵
y_train_entropy = get_entropy(y_train)
# 计算分裂的数据集本身的样本数
y_train_num = len(y_train)

# 初始化最佳分裂数据：：
#     初始化最佳分裂的特征列为空
best_split_feature_idx = None
#     初始化最佳分裂的特征列中最佳分裂特征点为空
best_split_feature_value = None
#     初始化最佳分裂之后的加权熵为无穷大（后面再做比较，并赋值为最小的加权熵）
#     备注：在Python中，表示无穷大主要有以下几种方式：
#     （1）float('inf')：这是最常用的表示正无穷大的方式，它是一个浮点数，表示大于任何其他浮点数的值
#     （2）float('-inf')：表示负无穷大，小于任何其他浮点数的值
#     （3）numpy.inf 或 numpy.infty：这是NumPy库中用于表示正无穷大的常量，numpy.inf 和 numpy.infty 是等价的
#     （4）numpy.NINF：这是NumPy库中用于表示负无穷大的常量
#     （5）math.inf：在Python的标准库 math 模块中，math.inf 也被用来表示正无穷大，但需要注意：math 模块本身没有明确地定义 math.inf，这个用法依赖于具体的Python实现
best_split_entropy_all = float('inf')
#     初始化最佳分裂点时，左右两边节点的样本数、样本内容及熵
best_split_left_num = None
best_split_right_num = None
best_split_left_X_content = None
best_split_left_y_content = None
best_split_right_X_content = None
best_split_right_y_content = None
best_split_left_entropy = None
best_split_right_entropy = None

# 根据特征数量，去逐个遍历各特征（X_train中的每一列数据）
for feature_idx in range(n_features):

    print(f">>>开始遍历第{feature_idx + 1}列特征数据...")

    # X_train是一个二维数组，feature_idx的值会依次采用0、1、2、3
    # 所以X_train[:, feature_idx]代表从X_train中分别取出第1列、第2列、第3列、第4列的特征数据
    # 用set函数，可进行数据去重，即：将每一列的数据去重，去重后的数据更具代表性
    X_train_idx_value = set(X_train[:, feature_idx])

    print(f"第{feature_idx + 1}列特征数据去重后的值为：{X_train_idx_value}")

    for idx, value in enumerate(X_train_idx_value):
        print(f">开始从去重后的第{feature_idx + 1}列特征数据值中进行遍历：当前为此列的第{idx + 1}轮遍历，遍历的数据为{value}")

        # 将X_train中第feature_idx列的所有数据，都与当前value值做对比,然后尝试做分裂，并计算分裂后的熵
        # 取出小于等于当前value值的数据，视为分裂后左边节点的数据
        y_left = y_train[(X_train[:, feature_idx] <= value)]
        entropy_left = get_entropy(y_left)
        print(f"[DecisionTree]分裂后左边节点的数据为：{y_left}")
        print(f"[DecisionTree]分裂后左边节点数据的熵为：{entropy_left}")
        # 取出大于当前value值的数据，视为分裂后右边节点的数据
        y_right = y_train[(X_train[:, feature_idx] > value)]
        entropy_right = get_entropy(y_right)
        print(f"[DecisionTree]分裂后右边节点的数据为：{y_right}")
        print(f"[DecisionTree]分裂后右边节点数据的熵为：{entropy_right}")

        # 分裂的总样本数量
        N = len(X_train[:, feature_idx])
        # 分裂后左边节点样本数量
        n_left = len(y_left)
        # 分裂后右边节点样本数量
        n_right = len(y_right)
        # 计算加权熵
        entropy_all = get_entropy_all(N, n_left, entropy_left, n_right, entropy_right)

        print(f"[DecisionTree]分裂后的加权熵为：{entropy_all}")

        # 比较加权熵，获得最小的熵，以及对应的特征列、数据点
        if entropy_all <= best_split_entropy_all:

            # 获取更小的加权熵
            best_split_entropy_all = entropy_all
            # 获取当前特征列的索引
            best_split_feature_idx = feature_idx

            # 获取做分裂的数据点（一般是要找到大于这个数据值的最小数，然后与其求均值，这样能更好针对测试集中大于分裂点的数据做预测）
            sorted_list = sorted(X_train_idx_value)
            min_greater = None
            for number in sorted_list:
                if number > value:
                    min_greater = number
                    break
            #     如果没有比这个数据点大的数，则min_greater会为空，不能与value相加以及求均值，所以要加条件判断
            if min_greater is not None:
                best_split_feature_value = (value + min_greater) / 2
            else:
                best_split_feature_value = value

            # 获取左边分支的样本数量
            best_split_left_num = n_left
            # 获取右边分支的样本数量
            best_split_right_num = n_right

            # 获取左边分支的X和y内容
            best_split_left_X_content = X_train[(X_train[:, feature_idx] <= value)]
            best_split_left_y_content = y_left
            # 获取右边分支的X和y内容
            best_split_right_X_content = X_train[(X_train[:, feature_idx] > value)]
            best_split_right_y_content = y_right

            # 计算左边分支中y的熵
            best_split_left_entropy = entropy_left
            # 计算右边分支中y的熵
            best_split_right_entropy = entropy_right

            print(f"[Better]找到了一个更好的分裂点，信息如下：")
            print(f"[Better]：特征列的索引为：{best_split_feature_idx}")
            print(f"[Better]：分裂的数据为：{best_split_feature_value}")
            print(f"[Better]：加权熵为：{best_split_entropy}")
            print("-" * 66)
            print(f"[Better]：左边样本的熵为：{best_split_left_entropy}")
            print(f"[Better]：左边样本的数量为：{best_split_left_num}")
            print("-" * 66)
            print(f"[Better]：右边样本的熵为：{best_split_right_entropy}")
            print(f"[Better]：右边样本的数量为：{best_split_right_num}")
        print("-" * 77)
    print("-" * 88)
print("-" * 99)
print(f"******为寻求第一次的最佳分裂点，已逐个遍历完毕******")
print(f"[Result]：找到了最好的分裂点，信息如下：")
print(f"[Result]：特征列的索引为：{best_split_feature_idx}")
print(f"[Result]：分裂的数据为：{best_split_feature_value}")
print(f"[Result]：数据集本身的熵为：{y_train_entropy}")
print(f"[Result]：数据集本身的样本数为：{y_train_num}")
print(f"[Result]：加权熵为：{best_split_entropy_all}")
print("-" * 66)
print(f"[Result]：左边样本的熵为：{best_split_left_entropy}")
print(f"[Result]：左边样本的数量为：{best_split_left_num}")
print(f"[Result]：左边样本的X特征数据为：{best_split_left_X_content}")
print(f"[Result]：左边样本的y标签数据为：{best_split_left_y_content}")
print("-" * 66)
print(f"[Result]：右边样本的熵为：{best_split_right_entropy}")
print(f"[Result]：右边样本的数量为：{best_split_right_num}")
print(f"[Result]：左边样本的X特征数据为：{best_split_right_X_content}")
print(f"[Result]：左边样本的y标签数据为：{best_split_right_y_content}")

备注：上面代码是求一次的最佳分裂点，如果要继续分裂（直至出现全部纯净的叶子节点），则可将上面代码中的X_train、y_train替换成上一步分裂后的数据集，并再次带入上面算法中进行计算，直至所有子节点的熵都为0（为0就是纯净的叶子节点了）

5.2 降基尼系数法

先定义两个函数，分别用于计算原数据集的基尼系数，以及分裂后两个子数据集的加权基尼系数

# 引入numpy库，提供一些其他的科学计算方法
import numpy as np

# 定义计算基尼系数的函数
def get_gini(y_arr):
    _, counts = np.unique(y_arr, return_counts=True)
    probabilities = counts / counts.sum()
    return 1 - (np.sum(probabilities ** 2))

# 定义计算加权基尼系数的函数
def get_gini_all(N, n_left, gini_left, n_right, gini_right):
    return ((n_left / N) * gini_left) + ((n_right / N) * gini_right)

调用上面的函数，循环计算：按照每一列的每一个数据分裂之后，看哪次得到的两个分子数据集的加权基尼系数最小，最小的即为最佳分裂点

# 引入load_iris，获取鸢尾花数据集
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)

# 引入train_test_split，将数据集切分为训练集和测试集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

# 切分之后，X_train.shape=(120, 4)，即：X_train有4个特征，共有120条数据
# 既然X_train.shape的结果是一个元组，那么就可以通过索引的方式来取出样本的特征个数
n_features = X_train.shape[1]

# 计算分裂的数据集本身的基尼系数
y_train_gini = get_gini(y_train)
# 计算分裂的数据集本身的样本数
y_train_num = len(y_train)

# 初始化最佳分裂数据：：
#     初始化最佳分裂的特征列为空
best_split_feature_idx = None
#     初始化最佳分裂的特征列中最佳分裂特征点为空
best_split_feature_value = None
#     初始化最佳分裂之后的加权基尼系数为无穷大（后面再做比较，并赋值为最小的加权基尼系数）
#     备注：在Python中，表示无穷大主要有以下几种方式：
#     （1）float('inf')：这是最常用的表示正无穷大的方式，它是一个浮点数，表示大于任何其他浮点数的值
#     （2）float('-inf')：表示负无穷大，小于任何其他浮点数的值
#     （3）numpy.inf 或 numpy.infty：这是NumPy库中用于表示正无穷大的常量，numpy.inf 和 numpy.infty 是等价的
#     （4）numpy.NINF：这是NumPy库中用于表示负无穷大的常量
#     （5）math.inf：在Python的标准库 math 模块中，math.inf 也被用来表示正无穷大，但需要注意：math 模块本身没有明确地定义 math.inf，这个用法依赖于具体的Python实现
best_split_gini_all = float('inf')
#     初始化最佳分裂点时，左右两边节点的样本数、样本内容及基尼系数
best_split_left_num = None
best_split_right_num = None
best_split_left_X_content = None
best_split_left_y_content = None
best_split_right_X_content = None
best_split_right_y_content = None
best_split_left_gini = None
best_split_right_gini = None

# 根据特征数量，去逐个遍历各特征（X_train中的每一列数据）
for feature_idx in range(n_features):

    print(f">>>开始遍历第{feature_idx + 1}列特征数据...")

    # X_train是一个二维数组，feature_idx的值会依次采用0、1、2、3
    # 所以X_train[:, feature_idx]代表从X_train中分别取出第1列、第2列、第3列、第4列的特征数据
    # 用set函数，可进行数据去重，即：将每一列的数据去重，去重后的数据更具代表性
    X_train_idx_value = set(X_train[:, feature_idx])

    print(f"第{feature_idx + 1}列特征数据去重后的值为：{X_train_idx_value}")

    for idx, value in enumerate(X_train_idx_value):
        print(f">开始从去重后的第{feature_idx + 1}列特征数据值中进行遍历：当前为此列的第{idx + 1}轮遍历，遍历的数据为{value}")

        # 将X_train中第feature_idx列的所有数据，都与当前value值做对比,然后尝试做分裂，并计算分裂后的基尼系数
        # 取出小于等于当前value值的数据，视为分裂后左边节点的数据
        y_left = y_train[(X_train[:, feature_idx] <= value)]
        gini_left = get_gini(y_left)
        print(f"[DecisionTree]分裂后左边节点的数据为：{y_left}")
        print(f"[DecisionTree]分裂后左边节点数据的基尼系数为：{gini_left}")
        # 取出大于当前value值的数据，视为分裂后右边节点的数据
        y_right = y_train[(X_train[:, feature_idx] > value)]
        gini_right = get_gini(y_right)
        print(f"[DecisionTree]分裂后右边节点的数据为：{y_right}")
        print(f"[DecisionTree]分裂后右边节点数据的基尼系数为：{gini_right}")

        # 分裂的总样本数量
        N = len(X_train[:, feature_idx])
        # 分裂后左边节点样本数量
        n_left = len(y_left)
        # 分裂后右边节点样本数量
        n_right = len(y_right)
        # 计算加权基尼系数
        gini_all = get_gini_all(N, n_left, gini_left, n_right, gini_right)

        print(f"[DecisionTree]分裂后的加权基尼系数为：{gini_all}")

        # 比较加权基尼系数，获得最小的基尼系数，以及对应的特征列、数据点
        if gini_all <= best_split_gini_all:

            # 获取更小的加权基尼系数
            best_split_gini_all = gini_all
            # 获取当前特征列的索引
            best_split_feature_idx = feature_idx

            # 获取做分裂的数据点（一般是要找到大于这个数据值的最小数，然后与其求均值，这样能更好针对测试集中大于分裂点的数据做预测）
            sorted_list = sorted(X_train_idx_value)
            min_greater = None
            for number in sorted_list:
                if number > value:
                    min_greater = number
                    break
            #     如果没有比这个数据点大的数，则min_greater会为空，不能与value相加以及求均值，所以要加条件判断
            if min_greater is not None:
                best_split_feature_value = (value + min_greater) / 2
            else:
                best_split_feature_value = value

            # 获取左边分支的样本数量
            best_split_left_num = n_left
            # 获取右边分支的样本数量
            best_split_right_num = n_right

            # 获取左边分支的X和y内容
            best_split_left_X_content = X_train[(X_train[:, feature_idx] <= value)]
            best_split_left_y_content = y_left
            # 获取右边分支的X和y内容
            best_split_right_X_content = X_train[(X_train[:, feature_idx] > value)]
            best_split_right_y_content = y_right

            # 计算左边分支中y的基尼系数
            best_split_left_gini = gini_left
            # 计算右边分支中y的基尼系数
            best_split_right_gini = gini_right

            print(f"[Better]找到了一个更好的分裂点，信息如下：")
            print(f"[Better]：特征列的索引为：{best_split_feature_idx}")
            print(f"[Better]：分裂的数据为：{best_split_feature_value}")
            print(f"[Better]：加权基尼系数为：{best_split_gini_all}")
            print("-" * 66)
            print(f"[Better]：左边样本的基尼系数为：{best_split_left_gini}")
            print(f"[Better]：左边样本的数量为：{best_split_left_num}")
            print("-" * 66)
            print(f"[Better]：右边样本的基尼系数为：{best_split_right_gini}")
            print(f"[Better]：右边样本的数量为：{best_split_right_num}")
        print("-" * 77)
    print("-" * 88)
print("-" * 99)
print(f"******为寻求第一次的最佳分裂点，已逐个遍历完毕******")
print(f"[Result]：找到了最好的分裂点，信息如下：")
print(f"[Result]：特征列的索引为：{best_split_feature_idx}")
print(f"[Result]：分裂的数据为：{best_split_feature_value}")
print(f"[Result]：数据集本身的基尼系数为：{y_train_gini}")
print(f"[Result]：数据集本身的样本数为：{y_train_num}")
print(f"[Result]：加权基尼系数为：{best_split_gini_all}")
print("-" * 66)
print(f"[Result]：左边样本的基尼系数为：{best_split_left_gini}")
print(f"[Result]：左边样本的数量为：{best_split_left_num}")
print(f"[Result]：左边样本的X特征数据为：{best_split_left_X_content}")
print(f"[Result]：左边样本的y标签数据为：{best_split_left_y_content}")
print("-" * 66)
print(f"[Result]：右边样本的基尼系数为：{best_split_right_gini}")
print(f"[Result]：右边样本的数量为：{best_split_right_num}")
print(f"[Result]：左边样本的X特征数据为：{best_split_right_X_content}")
print(f"[Result]：左边样本的y标签数据为：{best_split_right_y_content}")

备注：上面代码是求一次的最佳分裂点，如果要继续分裂（直至出现全部纯净的叶子节点），则可将上面代码中的X_train、y_train替换成上一步分裂后的数据集，并再次带入上面算法中进行计算，直至所有子节点的基尼系数都为0（为0就是纯净的叶子节点了）

5.3 备注

在进行上面算法分析的过程中，使用的算法原理为：按照每一列的每一个数据分裂之后，看哪次得到的两个分子数据集的加权信息增益最小，最小的即为最佳分裂点

如果出现了“两个或多个分裂后计算得出的加权信息增益都是最小”的情况，则上面代码对于分裂采取的是最后一次出现加权信息增益最小的数据点

这其实和sklearn.tree中标准的DecisionTreeClassifier算法有略微差异：

        标准的DecisionTreeClassifier对于“加权信息增益并列最小的数据点”，是会随机采取其中的某一点，而不是像上面算法一样“采取最后那一点”（这个可以通过pycharm画图验证，多次运行采取的数据点会在X[2]<=2.35和X[3]<=0.8之间随机选取，但通过jupyterLab视乎不易复现这种随机情况）

不过，这个细微差异并不影响我们对于算法的理解，以及对上述算法的应用

标签：right,04,算法,train,split,print,left,best,决策树
From： https://blog.csdn.net/weixin_43767064/article/details/142491149