树模型(一) 分支准则

这里我们结合《机器学习》书中内容和sklearn代码，深入了解机器学习中常用的树模型。

什么是树模型

人的决策方式与树模型

人通常在面对决策问题时，会通过将问题分解为一系列的子问题，然后层层递进，对每个子问题回答是与不是，通过这种方式得到最终的答案。例如医生如何判断一个人是不是感冒了呢？首先医生会通过望闻问切等方式收集一系列信息，然后可能通过面色判断，面色如常还是泛红，然后再看体温是正常还是偏高，再进一步看有没有咳嗽流鼻涕等症状，最终下一个判断，这个过程如下图所示：

人的决策过程.png

这个过程就是一个典型的通过分而治之思想建立树模型的过程：从根节点的问题出发，在每个节点上我们通过对一个属性的测试，对该节点进行划分，直到叶节点。每个叶节点都代表一个决策结果，它可以是分类标签或者数值结果。

树模型的优缺点

树模型的优点有：

• 树模型建立方式和人的思维方式很相近，非常便于理解；
• 对于数据要求较低，可以处理连续数据、离散数据以及缺失值等，不需要预先对输入数据进行正则化、归一化等处理；
• 可以处理多输出问题；
• 作为白箱模型，如果我们从训练集中建立一个树模型，那么我们可以非常容易的解释为什么这个模型对特定输入能得到特定结果；反之，类似深度神级网络之类的黑箱模型，其可解释性就比较差；

树模型的缺点有：

• 如果训练不当，容易过拟合，因此要应用剪枝或者限制每个叶节点包含的最小样本数、限制树的最大深度等方法来减轻过拟合；
• 决策树对训练数据比较敏感，如果训练集中包含一些噪声，那么受到噪声影响，我们在仅受少许噪声影响的数据集上就会创建出完全不同的树模型；通过集成学习，可以一定程度上避免这种情况；
• 树模型不适合作为外插模型，因为它的决策边界总是不连续不光滑的（而是一系列的垂直或倾斜于坐标轴的直线组成）；
• 对某些其他模型易于处理的情形，树模型却很难学到较好的决策边界，例如XOR；
• 在处理不平衡数据集时，即某类数据标签远多于另一类，树模型很容易偏向于主要标签，产生biased trees，因此在训练树模型时，应该尽可能对训练数据集进行平衡。

对于这些细节我们将在后面的代码中逐步体会。

建立树模型

划分选择

在决策的时候，我们希望总希望问一个最关键的子问题，帮助我们直接做出决策。譬如决策剩饭能不能吃的时候，味道显然是比容器颜色更好的属性，如果味道发酸，那肯定是不能吃的；反之装饭的碗是不是白色的这个问题不能为我们的决策提供有用信息，对我们的决策并没有帮助；
同样的，在建立树模型的时候，我们也希望找到“最关键”的属性，帮我们尽快的找到问题的答案。那么自然而然的，在建立树模型时一个重要的问题是，每次划分节点时，我们要挑选哪一些属性来进行节点划分？

信息增益(Information Gain)

一种思路是，我们用一个量来表征数据集中的信息含量，然后对于每个属性，依次计算用该属性划分之后，获得的新数据集的信息含量，然后选择给我们信息含量最多的划分方式。
那么一个对应的问题是，如何衡量数据集中包含的信息含量？
信息熵
根据一般的思路，我们在进行测量时，需要选择一个标定物，然后通过标定物与被测量物的属性之间的关系，来量化被测量物的属性；例如说我们在衡量物体的重量时，首先选择一个物体，将它的重量定为1kg，然后再衡量被测量物的重量相当于几个标定物，得到被测量物体的重量；对于时间、长度等等的度量莫不如此；
同样的，对于不确定性，我们也需要一个标定物，通常这个标定的选择是我们最常见的随机事件 -- 抛硬币。抛硬币是两种可能结果的等概率事件，定义它的不确定性为 1bit，那么我们可以用同样的思想，思考我们需要衡量的事情的不确定性相当于几次抛硬币；
用我们做选择题举例，对于一个有4个选项的单选题，如果我们没有任何先验知识，那么等可能的结果有4种，也就相当于我们抛两次硬币得到的结果数量 -- ，因此这个单选题系统中的不确定性为。
如果我们有8个选项，那就相当于抛3次硬币得到的结果数量 -- ，那么不确定性为。
上面我们提到的不确定性，就叫做信息熵；在信息论中，信息熵(Information Entropy)是对系统内的不确定性的度量；

如果事件并非等可能性的又如何呢？
如果我们知道答案是A的概率有50%，剩下三个答案正确的可能性还是等概率，那么我们这道单选题的不确定性有多少呢？
在概率的世界中，我们对于不确定的东西往往需要用期望去量化平均意义下的可能结果。同样的，我们可以对不确定性求期望；但是这里还有一个问题没有解决，就是对于概率为的单个事件，其不确定性是多少呢？我们可以这样考虑：如果事件发生概率为，我们可以认为它是在个等可能事件中发生该事件，因此，对于这个事件，它所在系统的不确定性可以用我们上面描述的方式求得，也就是；
因此，我们可以得到离散事件组成的系统中，信息熵的计算公式：

用这套公式，我们可以回答上面的问题：

不确定性的期望.png
也就是说我们对其中某个选项把握变高之后，我们系统的不确定性下降了；
这就是信息(Information)对不确定性的消除作用；信息一般通过三种方式来降低系统的不确定性：

• 修改概率分布：就像我们的例子中一样，我们对某个答案的把握变大了，系统的不确定性相应降低。
• 排除错误答案：这也很好理解，如果我们排除答案C，那么我们这道选择题的不确定性也会相应降低；
• 确定结果：比如我们知道答案就是A，那么这时候系统不确定为，也就是系统不确定性完全消除

回到树的问题
在建立树的过程中，我们可以对每个属性分割出的节点计算信息熵，信息熵越低，说明这个节点的“纯度”越高；通过比较分支前后的不确定性变化，我们可以计算出在该节点分支对于不确定性的减少，我们叫做信息增益(Information Gain)：

信息增益.png

更具体可以定义为：

其中，为所有分支可能性的集合，为落在分支出的第个节点中的样本数量，为样本集中所有样本的数量；
经典的ID3决策树(Iterative Dichotomiser3)就是以信息增益为准则来选择划分属性的。
这个准则的缺点在于信息增益会比较偏好“能分出枝丫最多的属性”，但是这种划分往往对模型的泛化产生困难；举个例子，如果我们要预测每个人的月均消费是否大于5000，那么在“名字”属性上进行分支，信息增益肯定远大于“收入”，因为基本上按照名字分支之后，就是一个人（和少数重名的人）占据一个标签了；但是显然，这样建出来的树在泛化上毫无效果；

增益率(Gain Ratio)

为了克服信息增益的选择偏好，C4.5决策树使用了增益率来选择进行划分的属性，即

其中称为节点a的固有值(Intrinsic Value)，其实就是节点a处的信息熵；
增益率是为了纠正信息增益的偏颇，然而过犹不及，它会倾向于选择可分支数较少的属性；因此C4.5中不是直接选择增益率最大的属性进行划分，而是采用一个启发式方法，先筛选信息增益高于平均水平的属性，再在选出的属性中选择增益率最高的；

基尼指数(Gini Index)

用熵作为分类准则有个缺点：对数运算较为复杂，计算效率不高；
基尼系数是对熵准则的一种逼近，我们可以这样理解节点的纯度度量：在一个节点中，我们选择两个样本，这两个样本标签不同的概率有多少。
用数学表达这种概率，就是，当这个值较小时，我们认为节点的纯度比较高 -- 因为任取两个样本都有比较高的几率是属于同一类的。
出于这样的直觉，基尼指数定义为：

基尼系数越小，说明节点纯度越高；当节点下只包含一种标签时，基尼系数为0；
下面的图描述了Gini Index和Information Entropy之间的关系，可以看到，这两类准则的曲线非常接近。此时基尼系数计算代价低的优势就显得非常突出了；

entropy_and_gini.png

CART决策树(Classification And Regression Tree)就使用了基尼指数作为划分节点的准则。

代码部分

在代码部分我们手写一下几种分支准则的计算方式，并在Iris数据集上进行测试；
注意这里我们简单的使用离散数值的处理方式来对待每个变量，而在实际建树时，这几个特征理应当成连续变量处理；

数据准备

数据准备部分如下：

## 模块导入
from sklearn.datasets import load_iris
import numpy as np
plt.style.use("seaborn")

## 读入iris数据集
# 数据集中包含4个特征：
# - sepal length in cm
# - sepal width in cm
# - petal length in cm
# - petal width in cm
# 三个类：
# - Iris-Setosa
# - Iris-Versicolour
# - Iris-Virginica
data = load_iris()

信息熵

首先是信息熵的计算方式：

# 计算某个节点处的信息熵
def information_entropy(labels: np.array) -> float:
    """
    计算给定标签对应的信息熵
    Parameters
    ----------
    labels : np.array
        当前节点下所有样本对应的标签
    """
    n_samples: int = len(labels)
    unique, counts = np.unique(labels, return_counts=True)
    # 计算每个标签对应的概率
    prob = counts / n_samples
    return -np.sum(prob * np.log2(prob))

# 计算根节点处的系统信息熵
information_entropy(data["target"])

可以得到根节点处的信息熵为1.584962500721156

信息熵增益

# 计算不同属性进行分支得到的information gain
def information_gain(features: np.array, labels: np.array, selected_feature_idx: int) -> float:
    """
    Parameters
    ----------
    features : np.array
        当前节点下所有样本的特征
    labels : np.array
        当前节点下所有样本对应的标签
    selected_feature_idx : np.array
        选择哪个特征计算信息熵增益
    """
    root_entropy: float = information_entropy(labels)
    unique, counts = np.unique(features[:, selected_feature_idx], return_counts = True)
    prob = counts / len(labels)
    branch_entropy: list = list()
    for i, val in enumerate(unique):
        mask = features[:, selected_feature_idx] == val
        branch_entropy.append(information_entropy(labels[mask]))
    return root_entropy - np.sum(prob * np.asarray(branch_entropy))

# 对每个属性计算在该属性进行分支得到的信息熵增益
feature_names = ["Sepal length", "Sepal width", "Petal length", "Petal width"]
for idx, feature_name in enumerate(feature_names):
    gain = information_gain(data["data"], data["target"], idx)
    unique = np.unique(data["data"][:, idx])
    print("特征名称：{}，特征可取值数目{}，对应信息增益：{:.4f}".format(feature_name, len(unique), gain))

结果如下：

特征名称：Sepal length，特征可取值数目35，对应信息增益：0.8769
特征名称：Sepal width，特征可取值数目23，对应信息增益：0.5166
特征名称：Petal length，特征可取值数目43，对应信息增益：1.4463
特征名称：Petal width，特征可取值数目22，对应信息增益：1.4359

增益率

def information_gain_ratio(features: np.array, labels: np.array, selected_feature_idx: int) -> float:
    """
    Parameters
    ----------
    features : np.array
        当前节点下所有样本的特征
    labels : np.array
        当前节点下所有样本对应的标签
    selected_feature_idx : np.array
        选择哪个特征计算信息熵增益
    """
    root_entropy: float = information_entropy(labels)
    unique, counts = np.unique(features[:, selected_feature_idx], return_counts = True)
    prob = counts / len(labels)
    branch_entropy: list = list()
    for i, val in enumerate(unique):
        mask = features[:, selected_feature_idx] == val
        branch_entropy.append(information_entropy(labels[mask]))
    return (root_entropy - np.sum(prob * branch_entropy)) / root_entropy

# 对每个属性计算在该属性进行分支得到的信息熵增益率
feature_names = ["Sepal length", "Sepal width", "Petal length", "Petal width"]
for idx, feature_name in enumerate(feature_names):
    gain = information_gain_ratio(data["data"], data["target"], idx)
    unique = np.unique(data["data"][:, idx])
    print("特征名称：{}，特征可取值数目{}，对应信息增益：{:.4f}".format(feature_name, len(unique), gain))

结果如下：

特征名称：Sepal length，特征可取值数目35，对应信息增益率：0.5533
特征名称：Sepal width，特征可取值数目23，对应信息增益率：0.3260
特征名称：Petal length，特征可取值数目43，对应信息增益率：0.9125
特征名称：Petal width，特征可取值数目22，对应信息增益率：0.9060

基尼指数

def gini_val(labels: np.array) -> float:
    """
    计算给定标签对应的基尼指数
    Parameters
    ----------
    labels : np.array
        当前节点下所有样本对应的标签
    """
    n_samples: int = len(labels)
    unique, counts = np.unique(labels, return_counts=True)
    # 计算每个标签对应的概率
    prob = counts / n_samples
    return 1 - np.sum(np.square(prob))

def gini_index(features: np.array, labels: np.array, selected_feature_idx: int) -> float:
    """
    计算在给定特征进行分支的基尼指数
    Parameters
    ----------
    features : np.array
        当前节点下所有样本的特征
    labels : np.array
        当前节点下所有样本对应的标签
    selected_feature_idx : np.array
        选择哪个特征计算信息熵增益
    """
    unique, counts = np.unique(features[:, selected_feature_idx], return_counts = True)
    prob = counts / len(labels)
    branch_gini: list = list()
    for i, val in enumerate(unique):
        mask = features[:, selected_feature_idx] == val
        branch_gini.append(gini_val(labels[mask]))
    return np.sum(prob * np.asarray(branch_gini))

feature_names = ["Sepal length", "Sepal width", "Petal length", "Petal width"]
for idx, feature_name in enumerate(feature_names):
    gain = gini_index(data["data"], data["target"], idx)
    unique = np.unique(data["data"][:, idx])
    print("特征名称：{}，特征可取值数目{}，对应基尼指数：{:.4f}".format(feature_name, len(unique), gain))

结果如下：

特征名称：Sepal length，特征可取值数目35，对应基尼指数：0.3194
特征名称：Sepal width，特征可取值数目23，对应基尼指数：0.4677
特征名称：Petal length，特征可取值数目43，对应基尼指数：0.0627
特征名称：Petal width，特征可取值数目22，对应基尼指数：0.0628

参考文献

《机器学习》- 周志华
树模型与集成学习
sklearn-Decision trees