决策树原理解析

决策树原理解析

---

1.决策树算法以及基本流程

决策树是基于树结构进行决策的,其机制就是通过判定每个属性分类的纯度来进行自上而下决策分类

决策树包含 根结点 ,内部结点, 叶结点; 根结点和内部结点对应与分类的属性(也就是分类的基准),叶结点对应决策结果(也就是纯度很高且不需要继续分裂的类别);从根结点到某一个叶结点的路径便是当前叶结点对应类的整个决策过程,下面来看决策树的算法流程:

可以看到决策树决策的过程是一个递归的过程:

• 条件1:当前所有样本均属于同一个类别C,则 无需划分,返回全部node
• 条件2: 属性集为空,或者 样本集在属性集上的取值相同,则返回其类标记为D中样本最多的类
  • 样本集在属性集上的取值相同 我认为是样本在属性集上的映射均等,所以当前样本不再分类,根据标签类进行命名当前结点类型
• 条件3: 将样本根据属性集映射出子样本集,然后根据 信息熵 或者 基尼不纯度 进行决策划分

下面是 iris 数据集的决策树分裂的可视图:

2.划分选择

如何选择最优的划分属性是决策树的关键,随着划分的进行我们希望样本划分的结果纯度越来越高;下面介绍两种划分标准

2.1 ID3算法 — 信息增益

2.1.1 算法介绍

ID3算法是决策树生成的经典算法,每次分裂时候就是计算***信息增益***,然后选择***信息增益***最大的作为标准进行结点分裂

"信息熵"是度量样本集合纯度的一个指标,首先定义全局变量:

• 当前决策分裂之前的样本集合 $D$D
• 样本类别为$K$K
• 根据标签(如 鸢尾花数据集(iris)的类别就是3种:setosa,versicolor,virginca)D中k类样本所占比率$p_k(k = 1,2,3 ...)$pk​(k=1,2,3...)
• 根据标签(如 鸢尾花数据集(iris)的类别就是3种:setosa,versicolor,virginca)D中k类样本数$D_k$Dk​
• 属性集 $a (a^1,a^2…a^V)$a(a1,a2…aV)
• 根据属性集映射样本分类,该分支结点根据属性$a^V$aV决策分裂所得样本子集$D^v$Dv

则信息熵定义:

$Ent(D) = - \sum_{k=1}^K p_k log_2p_k$Ent(D)=−k=1∑K​pk​log2​pk​

那么接着计算信息增益,样本根据属性集$a (a^1,a^2…a^V)$a(a1,a2…aV)进行分裂输出每个属性下的样本子集​$D^v$Dv,然后根据样本子集$D^v$Dv中的类别进行单子集的信息熵计算:

$Ent(D^v) = - \sum_{k=1}^K p_k log_2p_k$Ent(Dv)=−k=1∑K​pk​log2​pk​

然后对于样本子集中根据分支结点样本数与所有样本数的比率($|D^v|/|D|$∣Dv∣/∣D∣)进行权重赋值,未分裂之前的信息熵减去按照当前属性分裂之后结果所机算的信息熵只差就是信息增益:

$Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{D^v}{D}Ent(D^v)$Gain(D,a)=Ent(D)−v=1∑V​DDv​Ent(Dv)

换言之就是求 $a^v = argmax Gain(D,a)$av=argmaxGain(D,a)的极大似然过程

2.1.2 范例演示

公式总是不直观的,这里我们使用周志华老师—<机器学习>一书中的例子进行上述的论证:

• 下面是上述树中所用到的 西瓜 数据集

首先计算根结点的信息熵:

• 上述样本好瓜有8个,坏瓜有9个,所以$p_{好瓜} = \frac{8}{17} \;\;\;\; p_{坏瓜} = \frac{9}{17}$p好瓜​=178​p坏瓜​=179​

$Ent(D) = - \sum_{k=1}^2p_k\;log_2p_k = -(\frac{8}{17}log_2\frac{8}{17} + \frac{9}{17}log_2\frac{9}{17}) = 0.998$Ent(D)=−k=1∑2​pk​log2​pk​=−(178​log2​178​+179​log2​179​)=0.998

然后计算上述数据表中所有属性{色泽,根蒂,敲声,纹理,脐部,触感}的信息增益:

以色泽为例: $D^1(色泽=青绿) \;\; D^2(色泽=乌黑) \;\; D^3(色泽=浅白)$D1(色泽=青绿)D2(色泽=乌黑)D3(色泽=浅白)

• $D^1(色泽=青绿): p_1 =3/6 \;\; p_2 = 3/6$D1(色泽=青绿):p1​=3/6p2​=3/6
• $D^2(色泽=乌黑): p_1 = 4/6\;\;p_2 = 2/6$D2(色泽=乌黑):p1​=4/6p2​=2/6
• $D^3(色泽=浅白):p_1 = 1/5\;\;p_2 = 4/5$D3(色泽=浅白):p1​=1/5p2​=4/5

所以这三个支点的信息熵(只输出结果):

$Ent(D^1) = - \sum_{k=1}^2p_klog_2p_k = -(\frac{3}{6}log_2\frac{3}{6} + \frac{3}{6}log_2\frac{3}{6}) = 0.998$Ent(D1)=−k=1∑2​pk​log2​pk​=−(63​log2​63​+63​log2​63​)=0.998

$Ent(D^2) = - \sum_{k=1}^2p_klog_2p_k = -(\frac{4}{6}log_2\frac{4}{6} + \frac{2}{6}log_2\frac{2}{6}) = 0.998$Ent(D2)=−k=1∑2​pk​log2​pk​=−(64​log2​64​+62​log2​62​)=0.998

$Ent(D^3) = - \sum_{k=1}^2p_klog_2p_k = -(\frac{8}{17}log_2\frac{8}{17} + \frac{9}{17}log_2\frac{9}{17}) = 0.998$Ent(D3)=−k=1∑2​pk​log2​pk​=−(178​log2​178​+179​log2​179​)=0.998

则:

$Gain(D,色泽) = 0.998 - (\frac{6}{17}*1.000 + \frac{6}{17}*0.918 + \frac{5}{17}*0.722) = 0.109$Gain(D,色泽)=0.998−(176​∗1.000+176​∗0.918+175​∗0.722)=0.109

同理可以计算其他属性的信息增益:

$Gain(D,根蒂) = 0.143; \;\;Gain(D,敲声) = 0.141; \;\; Gain(D纹理) = 0.381$Gain(D,根蒂)=0.143;Gain(D,敲声)=0.141;Gain(D纹理)=0.381

$Gain(D,脐部) = 0.289; \;\;Gain(D,触感) = 0.006;$Gain(D,脐部)=0.289;Gain(D,触感)=0.006;

之后基于$D^1$D1分裂,递归上述过程

2.2 C4.5算法 — 信息增益率

继续来看上一个决策树(好瓜-坏瓜):

我们来计算下,如果将编号也做为属性来看,那么编号 1~17,每个编号可取值所对应的子样本的类别只能是好瓜或者坏瓜,所以编码作为决策属性,子样本的$Ent(D,编号) = 0$Ent(D,编号)=0,所以此时的信息熵增益是不合理的,此时的决策树泛化能力很差,无法对新样本本进行预测

为了平衡这一个问题,我们使用 增益率 来选择最优划分属性,下面是增益率的公式:

$Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$Gain_ratio(D,a)=IV(a)Gain(D,a)​

$IV(a) = -\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​

• 上式中可以看到属性$a$a的取值数目越多,$V$V就越大,同时$IV$IV也就越大
• 增益率对取值较少的属性有所偏好,而从前面可知,信息增益对取值较多的属性有所偏好,所以一般先从候选划分属性中找出信息增益高出平均水平的属性,再从中选择增益率最高的

2.3 基尼指数

数据集的纯度不仅可以用信息熵来判定,还可以使用基尼值来进行决策,下面先来看基尼值的公式:

$Gini(D) = \sum_{k=1}^K \sum_{k^+ \neq k^-}p_k^+p_k^- = 1- \sum_{k=1}^Kp_k^2$Gini(D)=k=1∑K​k+​=k−∑​pk+​pk−​=1−k=1∑K​pk2​

• $Gini(D)$Gini(D)反应的是随机抽取两个样本,其类别不一致的概率,所以$Gini(D)$Gini(D)越小,样本纯度越高

所以属性a的基尼指数:

$Gini\_index(D,a) = \sum_{v=1}^V \frac{|D^v|}{|D|}Gini(D^v)$Gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

于是用基尼指数进行结点分裂其实就是计算$a_v = argmin Gini\_index(D,a)$av​=argminGini_index(D,a)的过程

具体怎么计算仿造信息增益即可,替换公式而已

3.剪枝

首先我们将表4.1分成训练数据和验证数据;训练数据用来计算信息增益来选择决策属性,验证数据用来验证是否进行结点的分裂

剪枝是决策树为了防止"过拟合"的处理方式,随着决策树的深度增加,有时候不可避免决策树会把训练数据的一些特征用来表征所有的数据,这就造成了过拟合,因此需要通过剪枝来规避过拟合

剪枝有两种策略:

• 预剪枝:在决策树生成过程中,对每个结点在划分前进行估计,若当前结点的划分不能带来决策树泛化能力的提升,则停止划分并将当前结点标记为叶结点
• 后剪枝:通过训练数据生成一个完整的决策树,然后自下而上的进行评估,如果当前叶结点对应的子树替换为叶结点可以提升决策树的泛化能力,则将该子树替换为叶结点;

3.1 预剪枝

我们根据上面的图来模拟预剪枝的过程:

• 1号结点 —— 根结点
  • 不分裂则将根结点划分为当前样本标记为训练样本样本数最多的类,也就是"好瓜",用验证集验证评估分类的性能,被正确分类的是{4,5,8},故精度就是$3/7 = 42.9\%$3/7=42.9%
  • 根据训练集,信息增益最高的属性是"脐部",基于此进行划分叶结点,则: “凹陷”—— “好瓜”, “稍凹”—— “好瓜”,“平坦”——" 坏瓜";则此时被正确分类的就是{4,5,8,11,12},那么精度就是$5/7 = 71.4\%$5/7=71.4%
  • 因为$71.4\% > 42.9\%$71.4%>42.9%,所以划分有效
• 2号结点
  • 不分裂的情况下,精度依然是是$71.4 \%$71.4%
  • 根据训练集,信息增益最高的属性是"色泽",基于此进行划分叶结点,则: “青绿”—— “好瓜”,“乌黑”—— “好瓜”,“浅白”—— “坏瓜”,此时"乌黑"依然分错,"浅白"由原来的好瓜分成坏瓜,精度:$4/7=57.1\%$4/7=57.1%
  • 因为$57.1\% < 71.4\%$57.1%<71.4%所以禁止划分
• 3号结点
  • 不分裂状态下,精度依然是$71.4\%$71.4%
  • 当前计算得到的划分属性是"根蒂",此时划分之后的精度依然是$71.4\%$71.4%,所以没必要划分
• 4号结点全是坏瓜不需要划分

可以看到 预训练 确实有效地规避了过拟合,但是由于预剪枝使得部分结点不再展开,所以在一定程度上增加欠拟合的风险

3.2 后剪枝

大致过程类似于预剪枝,但是后剪枝是自下而上(决策树建立之后进行剪枝),而预剪枝是自上而下;

我们接下来抽样来看两个结点,以此来理解后剪枝:

• 2号结点
  • 原分支"色泽"剪枝前精度:$57.1\%$57.1%
  • 剪枝后精度:$71.4\%$71.4%,所以后剪枝决策:剪枝
• 5号分支结点(“乌黑”)
  • 原分支"纹理"剪枝前精度:$42.9\%$42.9%
  • 剪枝后精度:$57.1\%$57.1%,所以后剪枝决策:剪枝

对比两种剪枝,后剪枝是在决策树生成之后进行的剪枝,所以保留了更多分支,可以有效的规避"欠拟合";但是自上而下,进行后剪枝,需要一个一个遍历树节点,所以时间和资源开销会大很多