前言

本章内容主要是学习机器学习中的一个重要模型：决策树，围绕决策树的应用，我们展开了解到：熵的定义、熵的计算、决策树的构建过程(基于快速降熵)、基尼系数等，从而使得我们对决策树有了直观认识。

熵的介绍

因为决策树主要思想是对数据集进行降熵，所以在了解决策树之前，有必要对熵再做下系统梳理。

熵的定义

• 简言之，熵就是描述一个系统的混乱程度，熵越高，混乱程度越高。

• 在一个孤立系统里，如果没有外力做功，其总混乱度（即熵）会不断增大

熵的含义

• 熵越大，系统越混乱的
• 熵越小，系统越有序的

例如：

生活上：如果房间(封闭系统)没有定期去打扫(外力引入)，屋子会变得越来越乱(熵增)，房间越乱熵越大。

工作上：如果电脑桌面的文件夹(封闭系统)没有施加一定的归类归档**工作(外力引入)，文件夹及桌面会越来越乱(熵增)，文件夹越乱熵越大。

联系到机器学习和信息论中：

• 熵（Entropy）是信息理论中用于衡量系统无序程度或不确定性的指标。

• 输出越确定越不混乱，越不确定越混乱。

  例如：考试做选择题，一个选择题有四个A、B、C、D选项；明确知道选择题选哪个，熵越小脑子越不混乱；不知道选哪个，4个选项看着都像，代表熵越大脑子越混乱。

• 一个模型，在给定输入后，模型能够越肯定得输出结果，那么代表模型是一个好的模型；相反，如果不能确定的给定结果(甚至是瞎猜)，那么就不能算做好的模型。

  例如：在鸢尾花的示例中，如果给定一个鸢尾花的数据让机器进行预测是哪种类型。如果模型能够99%确定给定数据是某一个类型，那么这个模型是我们需要的、是好的模型；如果模型给出的结果是1/3概率是1类型，1/3概率是2类型，1/3概率是3类型，那么这个实际是没有意义的。

• 机器学习的训练过程本质上就是对抗熵的过程。

熵的计算

• 对于一个包含多个类别的数据集，熵的计算公式为：

  H(S) = - \sum_{i=1}^{c} p_i \log_2(p_i)

  其中：
  H(S) 是数据集 S 的熵。
  c 是数据集中不同类别的数量。
  p_i 是数据集中第 i 个类别所占比例。

代码实现

"""
    假定一个系统输出有2种情况：
    - A:[0.9, 0.1] -0.9概率输出第一种结果，0.1概率输出第二种
    - B:[0.6, 0.4] -0.6概率输出第一种结果，0.4概率输出第二种
    - C:[0.5, 0.5] -0.5概率输出第一种结果，0.5概率输出第二种

    问题：计算以上A、B、C的熵，看哪一种情况熵比较大
"""

import numpy as np

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

# 定义每种情况的概率分布
A = np.array([0.9, 0.1])
B = np.array([0.6, 0.4])
C = np.array([0.5, 0.5])

# 计算每种情况的熵
entropy_A = entropy(A)
entropy_B = entropy(B)
entropy_C = entropy(C)

# 输出结果
print("情况A的熵：", entropy_A)
print("情况B的熵：", entropy_B)
print("情况C的熵：", entropy_C)

由上计算可知，C:[0.5, 0.5]的输出越不确定(一半概率输出第一种结果，一半输出第二种结果)，所以其越混乱熵越大。

决策树

决策树的概念

决策树是一种用于解决分类问题的算法。它通过树状结构来表示各种决策规则，并根据输入数据的特征逐步进行决策，直到达到最终的预测结果。

一个例子

假设我们有一批如下的数据集：

其中有房者、婚姻、年收入是特征(或者叫属性)，是否拖欠贷款者是标签。

如果我们想通过这些特征来预测下一个数据是否会拖欠贷款，那么我们就可以构建一个决策树：

决策树的推理过程：

• 每个节点都是一个判断过程

• 直到找到叶子结点没有子节点后，即输出返回

决策树的预测

在Python中sklearn有提供相关的决策树库函数，我们仍然以鸢尾花的分类来使用决策树进行预测。

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

# 加载开源库中的iris数据集
X,y = load_iris(return_X_y=True)

# 切分数据集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, 
                                                    shuffle=True, 
                                                    random_state=0) 

# 1,构建模型
dtc = DecisionTreeClassifier(criterion="entropy")

# 2,训练模型
dtc.fit(X=X_train, y=y_train)

# 3,预测数据
y_pred = dtc.predict(X=X_test)

# 4,查看准确率
acc = (y_pred == y_test).mean()
print("准确率：", acc)

# 使用 plot_tree 函数绘制决策树
plt.figure(figsize=(20, 20))
plot_tree(dtc, filled=True)
plt.show()

以上代码执行后，我们借助matplotlib和plot_tree将鸢尾花预测时的决策树以图形化的方式一并输出来了。

决策树的构建

决策树的应用(如上图)是相对比较简单的，而学习的重点所在：如何构建决策树。

核心思想

通过快速降熵的方式，找到分割的节点，从而构建树的左右子集

构建步骤

1. 选择最佳特征：

   • 对所有特征数据进行遍历，计算熵，找到熵降得最小的特征

2. 分裂数据集：

   • 将数据集根据选择的最佳特征进行分割，分为左边和右边两部分子集。

3. 递归构建：

   • 对每个子集重复1-2步骤，直到满足停止条件。

   • 停止条件可以是：达到最大深度、节点包含的样本数小于阈值等。

4. 生成叶节点：

   • 当满足停止条件时，生成叶节点并确定叶节点的类别(或数值)。

构建过程推导(降熵entropy)

在上述的决策树中，我们通过plot_tree打印了已经构建的决策树。其中在根节点：

• X[2] = 2.35，代表在特征2找到了最佳分裂点，最佳分裂值为1.581
• Entropy = 1.581，代表此时的熵值为1.581
• Samples = 120 ，代表此时的样本数量为120个

上述决策树通过代码来模拟决策过程，如下：

# 取特征的个数
n_features = X_train.shape[-1]

best_split_feature_idx = None
best_split_feature_value = None
best_split_entropy = float('inf')

# 遍历(0, 1, 2, 3)特征
for feature_idx in range(n_features):
    # ①特征值去重
    for value in set(X_train[:, feature_idx]):
        print('[iteration]分裂特征：', feature_idx)
        print('[iteration]分裂值：', value)

        # ②分裂值与特征对比，筛选出对应标签列
        # 左边的标签值
        y_left = y_train[(X_train[:, feature_idx] <= value)]
        entropy_left = get_entropy(y_left)
        print('[iteration]左边标签数据：', y_left)
        print('[iteration]左边的熵：', entropy_left)

        # 右边的标签值
        y_right = y_train[(X_train[:, feature_idx] > value)]
        entropy_right = get_entropy(y_right)
        print('[iteration]右边标签数据：', y_right)
        print('[iteration]右边的熵：', entropy_right)

        # ③计算融合的熵
        entropy_all = entropy_left * len(y_left) / len(X_train[:, feature_idx]) \
                    + entropy_right * len(y_right) / len(X_train[:, feature_idx])
        print('[iteration]融合的熵：', entropy_all)

        if entropy_all <= best_split_entropy:
            best_split_entropy = entropy_all
            best_split_feature_idx = feature_idx
            best_split_feature_value = value
            print(f'[result]找到了一个最好的分裂点：{best_split_feature_idx}, {best_split_feature_value}, {best_split_entropy}')

            # 打印左边和右边的样本数量和取值
            print('[result]左边样本数量：', len(y_left))
            print('[result]左边样本取值：', np.unique(y_left, return_counts=True))
            print('[result]右边样本数量：', len(y_right))
            print('[result]右边样本取值：', np.unique(y_right, return_counts=True))

        print('------------')

执行结果如下：

将以上输出的日志保存到本地的.log文件中，然后我们筛选出"[result]找到了一个最好的分裂点"这段日志：

通过上图可以看到，对120个数据集的每个特征进行遍历计算熵，计算之后找到了熵最小的分裂点有两个，分别为：

2, 1.7, 0.6713590373778532

3, 0.6, 0.6713590373778532

这两个分裂值的熵均为0.67135，一个是特征2类别下的特征值1.7，一个是特征3类别下的特征值0.6。对比plot_tree打印的决策树：

• x[2] < = 2.35：即系统选择的是特征2下2.35(即：(1.7+3.0) / 2 = 2.35)这个最佳分裂点。

其过程用图来表示过程如下：

由此可知，决策树整体的运行方式为：

• 构建模型：通过对训练的数据进行遍历计算，通过计算熵值找到最佳分裂点，然后递归计算直到达到停止条件，同时生成叶节点。

• 预测数据：传入新的数据进行分类时，决策树进行特征的匹配计算从而找到对应的叶子节点。

  例如：假设需要预测一个[ 1, 2, 3, 4]的样本，那么决策树

  • 首先对特征2(即3)进行判断，发现3小于2.35不成立，向右走；
  • 然后对特征3(即4)进行判断，发现4<=1.75不成立，向右走；
  • 然后对特征2(即3)进行判断，发现3<=4.85成立，向左走；
  • 然后对特征0(即1)进行判断，发现1<=5.95成立，向左走达到叶子节点，返回类别1

构建过程推导(基尼系数gini)

基尼系数的定义

定义：基尼系数（Gini Index）是决策树算法中用于衡量数据集纯度的指标之一。

基尼系数的推导

• 假设有三个概率[p1, p2, p3]

  • 计算其熵值方法为：

  -( p1 log2(p1) + p2 log2(p2) + p3 * log2(p3) ) →

  -p1 log2(p1) – p2 log2(p2) – p3 * log2(p3) ) →

  p1 log2(1/p1) + p2 log2(1/p2) + p3 * log2(1/p3) ) ~

  p1 ( 1 – p1) + p2 (1 – p2) + p3 * (1 – p3)

基尼系数的意义

基尼系数本质上是一种工程上对熵计算的数学化简，可以省去较为麻烦的log2(1/P)的计算，取而代之的变为P * (1-P)，从而降低工程的计算代价。

以上决策树改为使用gini系数来进行构建：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.tree import plot_tree
import matplotlib.pyplot as plt

# 加载开源库中的iris数据集
X,y = load_iris(return_X_y=True)

# 切分数据集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, 
                                                    shuffle=True, 
                                                    random_state=0) 

# 1,构建模型
dtc = DecisionTreeClassifier(criterion="gini")

# 2,训练模型
dtc.fit(X=X_train, y=y_train)

# 3,预测数据
y_pred = dtc.predict(X=X_test)

# 4,查看准确率
acc = (y_pred == y_test).mean()
print("准确率：", acc)

# 使用 plot_tree 函数绘制决策树
plt.figure(figsize=(20, 20))
plot_tree(dtc, filled=True)
plt.show()

运行结果：

模拟决策树构建过程改为gini系数如下：

import numpy as np

# 计算传入的logits概率
# 计算方法：
# 1、对logits进行去重
# 2、计算每个label（例如：0,1,2）出现的次数
# 3、概率=出现次数/总的logits个数
def get_gini(logits = [2, 1, 0, 2, 2, 1, 0, 2]):

    # 类型转换为np数组
    logits = np.array(logits)

    # 获得不同类型的标签数量
    num_logits = len(logits)

    # 特殊处理：没有样本或者样本类型都一样，则混乱程度一样，熵为0
    if num_logits < 2:
        return 0

    # 计算对应标签的概率，即：概率 = 出现次数/总的个数
    probs = np.array([(logits == label).sum() for label in set(logits)]) / len(logits)

    # 计算系统的熵
    gini = (probs * (1 - probs)).sum()

    print("[get_entropy]传入的logits值为：", logits)
    print("[get_entropy]去重后的label为：", set(logits))
    print("[get_entropy]每个lable的概率为：", probs)
    print("[get_entropy]计算得到的gini为：", gini)

    return gini

# 取特征的个数
n_features = X_train.shape[-1]

best_split_feature_idx = None
best_split_feature_value = None
best_split_gini = float('inf')

# 遍历(0, 1, 2, 3)特征
for feature_idx in range(n_features):
    # ①特征值去重
    for value in set(X_train[:, feature_idx]):
        print('[iteration]分裂特征：', feature_idx)
        print('[iteration]分裂值：', value)

        # ②分裂值与特征对比，筛选出对应标签列
        # 左边的标签值
        y_left = y_train[(X_train[:, feature_idx] <= value)]
        gini_left = get_gini(y_left)
        print('[iteration]左边标签数据：', y_left)
        print('[iteration]左边的熵：', gini_left)

        # 右边的标签值
        y_right = y_train[(X_train[:, feature_idx] > value)]
        gini_right = get_gini(y_right)
        print('[iteration]右边标签数据：', y_right)
        print('[iteration]右边的熵：', gini_right)

        # ③计算融合的熵
        gini_all = gini_left * len(y_left) / len(X_train[:, feature_idx]) \
                    + gini_right * len(y_right) / len(X_train[:, feature_idx])
        print('[iteration]融合的熵：', gini_all)

        if gini_all <= best_split_gini:
            best_split_gini = gini_all
            best_split_feature_idx = feature_idx
            best_split_feature_value = value
            print(f'[result]找到了一个最好的分裂点：{best_split_feature_idx}, {best_split_feature_value}, {best_split_gini}')

            # 打印左边和右边的样本数量和取值
            print('[result]左边样本数量：', len(y_left))
            print('[result]左边样本取值：', np.unique(y_left, return_counts=True))
            print('[result]右边样本数量：', len(y_right))
            print('[result]右边样本取值：', np.unique(y_right, return_counts=True))

        print('------------')

运行对比，gini系数的计算与plot_tree输出一致。

决策树的意义

决策树可以用于进行特征筛选。

例如：通过鸢尾花分类问题对比发现，在决策树计算过程中，通过dtc.feature_importances_可以看到特征1的重要性为0，基本上没有什么作用；而特征3比较重要。

优点：解释性比较好，可以对特征进行重要性排序，模型可大可小(可以进行剪枝)

本章小结

• 熵是衡量一个系统的混乱程度。熵越大，系统越混乱的；熵越小，系统越有序的。
• 一个模型输出越确定越不混乱，越不确定越混乱。
• 决策树是一种用于解决分类问题的算法，它通过一定的规则对每一个节点进行判断，直到找到叶子节点后输出返回。
• 基于降熵的思想，决策树在构建过程中，对数据进行遍历计算熵，找到熵降得最小的，然后将该熵对应的值作为分裂值，分为左边和右边两部分，直到结束。
• 为了简化熵的计算，也可以使用gini系数来进行计算，从而简化工程计算代价。
• 除了决策树进行预测之外，也可以用于进行特征筛选。