机器学习-决策树算法

前言

本篇介绍决策树与随机森林的内容，先完成了决策树的部分。

决策树

决策树(Decision Tree)是一种有监督学习的方法，可以同时解决分类和回归问题，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决问题。

决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，在各个行业领域都有广泛的应用。

举例分析

我们来简单了解一下决策树是如何工作的。决策树算法的本质是一种树结构，我们只需要问一系列问题就可以对数据进行分类了。比如说，来看看下面的一组数据集，这是一些列已知物种以及所属类别的数据：

我们现在的目标是，将动物们分为哺乳类和非哺乳类。那根据已经收集到的数据，决策树算法为我们算出了下面的这棵决策树：

这时，假如我们现在发现了一种新物种，它是冷血动物，体表带鳞片，并且不是胎生，我们就可以通过这棵决策树来判断它的所属类别。

可以看出，在这个决策过程中，我们一直在对记录的特征进行提问。最初的问题所在的地方叫做根结点，在得到结论前的每一个问题都是中间结点，而得到的每一个结论(动物的类别)都叫做叶子结点。

定义

通过上述例子，我们可以总结，决策树算法的本质就是树形结构，我们可以通过一些精心设计的问题，就可以对数据进行分类（训练），一个决策树建立好之后，就可以基于该树的相关分支得到不同分类的预测结果。

• 树的根节点和中间节点对应的是某一种类型特征，那么这些节点（特征）自上而下的重要性应该是由大到小进行排列的。而所谓重要性并没有一定的标准，都是根据问题而决定的。

---

原理

决策树算法的核心是要解决两个问题:

1.如何从数据表中找出最佳节点或最佳分枝?

2.如何让决策树停止生长，防止过拟合?

• 决策树是基于训练集数据构建出来的，如果树长的越大分支越细致，则对训练数据的描述越清楚，但是不一定会很好的作用到测试数据中。

构建决策树

那如何根据已有的数据集来建立有效的决策树？原则上讲，任意一个数据集上的所有特征都可以被拿来分枝，特征上的任意节点又可以自由组合，所以一个数据集上可以发展出非常非常多棵决策树，其数量可达指数级。但是在这些树中，总有那么一棵树比其他的树分类效力都好，那样的树叫做”全局最优树“。

• 全局最优:经过某种组合形成的决策树，整体来说分类效果为最好的模型
• 局部最优:每一次分枝的时候都向着更好的分类效果分枝，但无法确认如此生成的树在全局上是否是最优的

要在这么多棵决策树中去一次性找到分类效果最佳的那一棵是不可能的，如果通过排列组合来进行筛选，计算量过于大而且低效，因此我们不会这样做。相对的，机器学习研究者们开发了一些有效的算法，能够在合理的时间内构造出具有一定准确率的次最优决策树，接下来要介绍熵的知识了。

不纯度

决策树需要找出最佳节点和最佳的分枝方法，对分类树来说，衡量这个“最佳”的指标叫做“不纯度”。通常来说，不纯度越低，决策树对训练集的拟合越好。不纯度基于节点来计算，树中的每个节点都会有一个不纯度，并且子节点的不纯度一定是低于父节点的。

我们一般采用熵和基尼系数来衡量不纯度。

熵

熵（Entropy) 是对于随机变量不确定性的度量。熵值越小，对于数据分类的越干净，当然有利于后续的预测等其他工作的进行。对于决策树的某个结点而言，它在对样本数据进行分类后，我们希望分类后的结果能使得整个样本集在各自的类别中尽可能有序，也就是希望某个特征在被用于分类后，能最大程度地降低样本数据的熵。

计算公式如下：
$$H(X)=-\sum P(x)log2P(x)$$
其中，X 是一个离散随机变量，P(X) 是 X 取某个值的概率。

根据我们总是要选取最优的特征，以及熵的定义，在构建决策树时我们可采用一种很简单的思路来进行熵减：每当要选出一个内部结点时，考虑样本中的所有尚未被使用的特征，并基于该特征计算出来的熵对样本数据进行划分。

条件熵

条件熵就是含有条件概率时的熵，它描述的是在已知随机变量X的条件下随机变量Y的不确定性。假设有两个随机变量X和Y，Y的条件熵H(Y|X)定义为X给定的条件下Y的平均熵，可以通过以下公式计算：
$$H(Y|X)=\sum P(x)H(Y|X=x)$$

其中，P(x)是随机变量X取某个值的概率，H(Y|X=x)是在X取某个值的条件下Y的熵。

条件熵H(Y|X)可以理解为在已知随机变量X的值的情况下，随机变量Y的不确定性。

如果Y的值完全由X的值决定，那么条件熵H(Y|X)就为0，表示在已知X的值的情况下，Y的值没有不确定性。如果Y的值与X的值无关，那么条件熵H(Y|X)就等于Y的原始熵H(Y)，表示在已知X的值的情况下，Y的不确定性没有任何减少。

信息增益

是决策树算法中用来选择分割属性的一种度量方式。它表示的是通过某个特征而得到的“信息”的增加量，或者说，不确定性的减少量。具体来说，信息增益是数据集的原始熵与给定某个属性后的条件熵之差。如果一个属性能够使得信息增益最大，那么就选择这个属性进行分割。

让我们通过一个简单的例子来理解信息增益：

假设我们有一个数据集，包含了天气（晴、阴、雨）、温度（高、中、低）和是否打篮球（是、否）三个属性，其中前两个为特征。我们想要构建一个决策树模型，来预测在不同的天气和温度条件下，是否会打篮球。

• 首先，我们计算数据集的原始熵。假设数据集中有10个样本，其中5个样本是“打篮球”，5个样本是“不打篮球”，那么原始熵为1（因为两类样本的数量相等，所以此时熵最大，为1）。

• 然后，我们计算给定“天气”属性后的条件熵。假设在“晴”天气下，有3个样本是“打篮球”，2个样本是“不打篮球”；在“阴”天气下，有1个样本是“打篮球”，2个样本是“不打篮球”；在“雨”天气下，有1个样本是“打篮球”，1个样本是“不打篮球”。那么，给定“天气”属性后的条件熵为0.97。因此，天气属性的信息增益为原始熵与条件熵之差，即信息增益为：1 - 0.97 = 0.03。

• 同样，我们可以计算出温度属性的信息增益。假设温度属性的信息增益为0.01。

• 由于天气属性的信息增益大于温度属性的信息增益，因此我们选择天气属性进行分割。

这就是信息增益的基本概念和计算方法。在实际应用中，我们通常会计算所有属性的信息增益，然后选择信息增益最大的属性进行分割。

上述过程也就是ID3算法的过程。

基尼系数

基尼系数（Gini Index）也叫基尼不纯度（Gini Impurity）是一种用来度量数据集的不纯度的指标。基尼系数的值越小，数据集的纯度越高。

基尼系数的计算公式如下：
$$Gini(D)=1-\sum (P_i{)}^2$$
其中，D是数据集，Pi 是第 i 类样本在数据集D中出现的概率。

基尼系数的值域为[0, 1]。当数据集D中的所有样本都属于同一类时，基尼系数为0，表示数据集D的纯度最高；当数据集D中的样本均匀分布在各个类别中时，基尼系数为1-1/k，其中k是类别的数量，此时数据集D的纯度最低。

---

算法

ID3算法

ID3（Iterative Dichotomiser 3）由Ross Quinlan在1986年提出。这种算法使用信息增益作为属性选择的度量标准，选择信息增益最大的属性进行分割。ID3算法可以处理多值属性，但不能直接处理数值属性和缺失值，也没有剪枝操作，因此容易产生过拟合。

• 计算信息增益：首先，计算数据集D的熵H(D)，然后对每一个特征A，计算A对D的信息增益G(D,A)。信息增益定义为数据集D的熵与给定属性A值后的条件熵之差，即G(D,A)=H(D)-H(D|A)。
• 选择信息增益最大的属性：在所有特征中，选择信息增益最大的特征A。
• 分割数据集：根据特征A的每一个可能值ai，将D分割为若干个非空子集Di，每个子集Di包含D中所有在特征A上取值为ai的样本，然后对每个子集Di递归地应用上述过程。
• 生成决策树：将特征A作为测试条件，生成一个分支节点，对应于A的每一个可能值，从该节点引出一个分支，下接对应的子集Di的决策子树。

需要注意的是，ID3算法没有剪枝操作，因此生成的决策树可能会过于复杂，容易产生过拟合。此外，ID3算法不能直接处理数值属性和缺失值，这在实际应用中可能会带来一些问题。

C4.5算法

C4.5算法由Ross Quinlan在1993年提出，是ID3算法的改进版。C4.5算法引入了信息增益率作为属性选择的度量标准，以解决ID3算法对取值数目较多的属性有所偏好的问题。此外，C4.5算法还可以处理数值属性和缺失值，通过引入置信度因子进行剪枝，以防止过拟合。

• 计算信息增益率：首先，计算数据集D的熵H(D)，然后对每一个特征A，计算A对D的信息增益G(D,A)和信息增益率GR(D,A)。信息增益率定义为信息增益与属性A的熵之比，即：

$$GR(D,A)=G(D,A)/H_A(D)$$

• 选择信息增益率最大的属性：在所有属性中，选择信息增益率最大的特征A。
• 分割数据集：根据特征A的每一个可能值ai，将D分割为若干个非空子集Di，每个子集Di包含D中所有在特征A上取值为ai的样本，然后对每个子集Di递归地应用上述过程。
• 生成决策树：将特征A作为测试条件，生成一个分支节点，对应于A的每一个可能值，从该节点引出一个分支，下接对应的子集Di的决策子树。
• 剪枝：C4.5算法引入了置信度因子进行剪枝，以防止过拟合。具体来说，C4.5算法会计算每个节点的错误率，然后比较剪枝前后的错误率，如果剪枝后的错误率没有显著增加，那么就进行剪枝。

需要注意的是，C4.5算法可以处理数值属性和缺失值。对于数值属性，C4.5算法会找出一个最佳的分割点，将属性的值分为两个区间；对于缺失值，C4.5算法会根据数据的分布，将缺失值分配到各个子节点。

CART算法

CART（Classification and Regression Tree）算法是既可以用于分类也可以用于回归的决策树学习算法，由Breiman等人在1984年提出。CART算法使用基尼指数作为属性选择的度量标准，选择基尼指数最小的属性进行分割。CART算法生成的决策树是二叉树，可以处理数值属性和缺失值，通过设定复杂度参数进行剪枝，以防止过拟合。

• 计算基尼指数：首先，计算数据集D的基尼指数G(D)，然后对每一个特征A，计算A对D的基尼指数G(D,A)。
• 选择基尼指数最小的属性：在所有特征中，选择基尼指数最小的特征A。
• 分割数据集：根据特征A的每一个可能值ai，将D分割为两个子集Di和Dj，Di包含D中所有在属性Ag上取值小于等于ai的样本，Dj包含D中所有在特征A上取值大于ai的样本，然后对每个子集Di和Dj递归地应用上述过程。
• 生成决策树：将属性Ag和分割点ai作为测试条件，生成一个二叉节点，左分支下接对应的子集Di的决策子树，右分支下接对应的子集Dj的决策子树。
• 剪枝：CART算法通过设定复杂度参数进行剪枝，以防止过拟合。具体来说，CART算法会计算每个节点的复杂度代价，然后比较剪枝前后的复杂度代价，如果剪枝后的复杂度代价没有显著增加，那么就进行剪枝。

CART算法可以处理数值属性和缺失值*。对于数值属性，CART算法会找出一个最佳的分割点，将属性的值分为两个区间；对于缺失值，CART算法会根据数据的分布，将缺失值分配到各个子节点。

---

运用实现

库

决策数的调用包含在skleran.tree中：

重要参数

criterion

这个参数用来决定不纯度的计算方法的。

sklearn提供了两种选择：

输入”entropy“，使用信息熵（Entropy）

输入”gini“，使用基尼系数（Gini Impurity）

random_state & splitter

random_state随机模式参数，默认None，在高维度时随机性会表现更明显，低维度的数据（比如鸢尾花数据集），随机性几乎不会显现。输入任意整数，会一直长出同一棵树，让模型稳定下来。

splitter 也是用来控制决策树中的随机选项的，有两种输入值

输入”best"，决策树在分枝时虽然随机，但是还是会优先选择更重要的特征进行分枝。

输入“random"，决策树在分枝时会更加随机，树会因为含有更多的不必要信息而更深更大。这也是防止过拟合的一种方式。当然，我们经常会使用剪枝参数来防止过拟合。

剪枝参数

剪枝策略对决策树的影响巨大，正确的剪枝策略是优化决策树算法的核心。

sklearn为我们提供了不同的剪枝策略：

max_depth

限制树的最大深度，超过设定深度的树枝全部剪掉，这是用得最广泛的剪枝参数，在高维度低样本量时非常有效。决策树多生长一层，对样本量的需求会增加一倍，所以限制树深度能够有效地限制过拟合。在集成算法中也非常实用。实际使用时，一般从=3开始尝试，看看拟合的效果再决定是否增加设定深度。

min_samples_leaf

限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生 。一般搭配max_depth使用，可以让模型变得更加平滑。这个参数的数量设置得太小会引起过拟合，设置得太大就会阻止模型学习数据。一般来说，建议从=5开始使用。如果叶节点中含有的样本量变化很大，建议输入浮点数作为样本量的百分比来使用。

max_features限制分枝时考虑的特征个数，超过限制个数的特征都会被舍弃。

max_features是用来限制高维度数据的过拟合的剪枝参数，但其方法比较暴力，是直接限制可以使用的特征数量而强行使决策树停下的参数，在不知道决策树中的各个特征的重要性的情况下，强行设定这个参数可能会导致模型学习不足。

min_samples_split

min_impurity_decrease限制信息增益的大小，信息增益小于设定数值的分枝不会发生。

重要的属性和接口

决策树来说，最重要的属性是feature_importances_，能够查看各个特征对模型的重要性。

除了这两个接口之外，决策树最常用的接口还有apply和predict。apply中输入测试集返回每个测试样本所在的叶子节点的索引，predict输入测试集返回每个测试样本的标签。

可视化

想要做好决策树的最后一步就是将树给画出来，但是因为侧重点不同，暂时就先不介绍。