监督学习之树模型（1）

决策树算法在机器学习中算是很经典的一个算法系列了，被认为是监督学习方法中最好的并且是最常用的方法之一，特别适合作为集成学习的基学习器。
我们可以将决策树看作是if- then规则的集合，使用决策树模型进行预测的过程就相当于对if - then规则进行判断，那我们可以想到如果if -then规则越多，也就是决策树越复杂，那么预测所需要的时间越长，所以为了不断优化决策树的决策过程，我们需要合理的构建决策树，那么如何来选择if - then的决策规则至关重要。

一、基本概念

1、节点

（1）按照位置来分：

• 根节点
  它标识整个样本，会被进一步分割成两个或多个子集合。
• 决策节点
  当一个子节点进一步分裂成子节点的时候，它被称为决策节点。
• 叶子/终端节点
  不会被分割的节点被称为叶子或终端节点。

（2）按照关系来分：

• 父节点
  决策节点被子节点称为父节点。
• 子节点
  子节点是父节点的孩子节点。

2、分裂与剪枝

（1）分枝
将一个节点分割为两个或多个子节点的过程。
（2）剪枝
当我们移除掉父节点的子节点时，这个过程成为剪枝。他是分枝的反过程。

3、最大深度

决策树的最大深度指树根和叶子之间的最大距离。当决策树的最大深度为 k 时，它最多可以拥有 2^k 片叶子。

4、每片叶子的最小样本数

在分裂节点时，很有可能一片叶子上有 99 个样本，而另一片叶子上只有 1 个样本。这将使我们陷入困境，并造成资源和时间的浪费。如果想避免这种问题，我们可以设置每片叶子允许的最小样本数。

这个数字可以被指定为一个整数，也可以是一个浮点数。如果它是整数，它将表示这片叶子上的最小样本数。如果它是个浮点数，它将被视作每片叶子上的最小样本比例。比如，0.1 或 10% 表示如果一片叶子上的样本数量小于该节点中样本数量的 10%，这种分裂将不被允许。

二、树模型的原理

理解树模型离不开最大熵模型。

1、熵

为了理解熵，必须讲一点物理学。热力学第二定律表达了有很多种解释，有一种最容易懂：能量转换的时候，大部分能量会转换成预先设定的状态，比如热能变成机械能、电能变成光能。但是，还有一部分能量会生成新的状态。
状态多，就是可能性多，表示比较混乱；状态少，就是可能性少，相对来说就比较有秩序。因此，能量转换会让系统的混乱度增加，熵就是系统的混乱度。
"熵"是一种无序程度的量度，意思是越混乱越无规律熵值就越大，反之熵值越小。

熵低则混乱度低，熵高则混乱度高
水的三相中，冰块是分子的有序排列，吸收能量后，变成液体水，分子排列变得无序，变成气体后更加无序。因此气体的熵最高。

熵让我们理解了一件事，如果不施加外力影响，事物永远向着更混乱的状态发展。

2、信息熵

假设我们要做一个游戏，每次从盒子中抽一个小球记录颜色后放回，如果抽4次的结果和盒子中球的分布一致的话我们获胜，这三种不同组合中第一个盒子最容易获胜，第二个次之，第三个获胜概率最低。

第一个盒子：1x1x1x1=1
第二个盒子：0.75x0.75x0.75x0.25=0.105
第三个盒子：0.5x0.5x0.5x0.5=0.0625
因为和比积好，接下来我们把这个公式变形。

log(ab) = log(a) + log(b)

根据上面的公式，第二个盒子的获胜概率可以换一种形式表示

0.75x0.75x0.75x0.75 = 0.105
log(0.75)+log(0.75)+log(0.75)+log(0.75) = -3.245

那么获胜几率可以转换成如下的表格。

接着增大球的数量，有如下公式

两种颜色的球时当前状态的熵（混乱程度）的计算

这就是1948年香农提出的信息熵（Entropy）的概念。
假如事件A的分类划分是（A₁,A₂,...,A_n），每部分发生的概率是(p₁,p₂,...,p_n)，那信息熵定义为公式如下：

3、信息增益

信息增益又称相对熵（relative entropy），是针对一个一个的特征而言的，就是看一个特征X，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息增益。
信息增益的公式很简单，就是信息熵的变化。

当两个子节点大小一致时，就是父节点的熵减去子节点熵的平均值。

4、信息增益的直观理解

现在来比较以下三种不同的分枝（假设每个子集大小一样都是10个点），哪种效果最好

第一种分法，能提供的信息变化较少。
第二种分法很糟糕，没有提供任何信息增益。
第三种分法很完美，完美地分割了数据。

5、条件熵

条件熵是为了计算信息增益而引出的概念，可以表示为

6、信息增益公式

有了条件熵的概念后，信息增益的公式可以改写为

三、常见的决策树