【课程总结】Day4：信息论和决策树算法

前言

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

熵的介绍

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

熵的定义

简言之，熵就是描述一个系统的混乱程度，熵越高，混乱程度越高。
在一个孤立系统里，如果没有外力做功，其总混乱度（即熵）会不断增大

熵的含义

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

例如：

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

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

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

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

例如：考试做选择题，一个选择题有四个A、B、C、D选项；明确知道选择题选哪个，熵越小脑子越不混乱；不知道选哪个，4个选项看着都像，代表熵越大脑子越混乱。
一个模型，在给定输入后，模型能够越肯定得输出结果，那么代表模型是一个好的模型；相反，如果不能确定的给定结果(甚至是瞎猜)，那么就不能算做好的模型。

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

熵的计算

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

$\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]的输出越不确定(一半概率输出第一种结果，一半输出第二种结果)，所以其越混乱熵越大。

决策树

决策树的概念

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

一个例子

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

ID	有房者	婚姻	年收入	是否拖欠贷款者
1	是	单身	10万	否
2	否	已婚	8万	否
3	是	离异	12万	否
4	是	已婚	15万	否
5	否	单身	6万	是
6	是	已婚	18万	否
7	是	单身	9万	否
8	否	离异	7万	是
9	是	已婚	14万	否
10	否	单身	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步骤，直到满足停止条件。
- 停止条件可以是：达到最大深度、节点包含的样本数小于阈值等。
生成叶节点：
- 当满足停止条件时，生成叶节点并确定叶节点的类别(或数值)。

构建过程推导(降熵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('------------')