决策树算法在机器学习中算是很经典的一个算法系列了,被认为是监督学习方法中最好的并且是最常用的方法之一,特别适合作为集成学习的基学习器。
我们可以将决策树看作是if- then规则的集合,使用决策树模型进行预测的过程就相当于对if - then规则进行判断,那我们可以想到如果if -then规则越多,也就是决策树越复杂,那么预测所需要的时间越长,所以为了不断优化决策树的决策过程,我们需要合理的构建决策树,那么如何来选择if - then的决策规则至关重要。
一、基本概念
1、节点
(1)按照位置来分:
- 根节点
它标识整个样本,会被进一步分割成两个或多个子集合。 - 决策节点
当一个子节点进一步分裂成子节点的时候,它被称为决策节点。 - 叶子/终端节点
不会被分割的节点被称为叶子或终端节点。
(2)按照关系来分:
- 父节点
决策节点被子节点称为父节点。 - 子节点
子节点是父节点的孩子节点。
2、分裂与剪枝
(1)分枝
将一个节点分割为两个或多个子节点的过程。
(2)剪枝
当我们移除掉父节点的子节点时,这个过程成为剪枝。他是分枝的反过程。
3、最大深度
决策树的最大深度指树根和叶子之间的最大距离。当决策树的最大深度为 k 时,它最多可以拥有 2k 片叶子。
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的分类划分是(A1,A2,...,An),每部分发生的概率是(p1,p2,...,pn),那信息熵定义为公式如下:
3、信息增益
信息增益又称相对熵(relative entropy),是针对一个一个的特征而言的,就是看一个特征X,系统有它和没它的时候信息量各是多少,两者的差值就是这个特征给系统带来的信息增益。
信息增益的公式很简单,就是信息熵的变化。
当两个子节点大小一致时,就是父节点的熵减去子节点熵的平均值。
4、信息增益的直观理解
现在来比较以下三种不同的分枝(假设每个子集大小一样都是10个点),哪种效果最好
第一种分法,能提供的信息变化较少。
第二种分法很糟糕,没有提供任何信息增益。
第三种分法很完美,完美地分割了数据。
5、条件熵
条件熵是为了计算信息增益而引出的概念,可以表示为
6、信息增益公式
有了条件熵的概念后,信息增益的公式可以改写为
网友评论