监督学习之树模型(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
因为和比积好,接下来我们把这个公式变形。

log2(ab) = log2(a) + log2(b)

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

0.75x0.75x0.75x0.25 = 0.105
log2(0.75)+log2(0.75)+log2(0.75)+log2(0.25) = -3.245

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

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

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

这就是1948年香农提出的信息熵(Entropy)的概念。
假如事件A的分类划分是(A1,A2,…,An),每部分发生的概率是(p1,p2,…,pn),那信息熵定义为公式如下:

3、信息增益

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

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

4、信息增益的直观理解

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

第一种分法,能提供的信息变化较少。

第二种分法很糟糕,没有提供任何信息增益。

第三种分法很完美,完美地分割了数据。

5、条件熵

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

$$条件熵 = \sum_{i=1}^n(\frac{子数据集大小}{数据集大小}*子数据集的信息熵 )$$

6、信息增益公式

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

$$信息增益 = 信息熵-条件熵$$

三、常见的决策树

0%