淘先锋技术网

首页 1 2 3 4 5 6 7

决策树算法概述

决策树
  • 从根节点开始一步步走到叶子节点(决策)
  • 所有的数据最终都会落到叶子节点,既可以做分类也可以做回归

决策树从根节点开始到叶子节点中的判断条件是有先后的,要先进行尽可能对的分类任务,再往下的做更加细致的分类(微调)

树的组成
  • 根节点:第一个选择点
  • 非叶子节点与分支:中间过程
  • 叶子节点:最终的决策结果
决策树的训练与测试
  • 训练阶段:从给定的训练集构造出来一棵树(从跟节点开始选择特征,
    如何进行特征切分)
  • 测试阶段:根据构造出来的树模型从上到下去走一遍

熵的作用

如何切分特征(选择节点)
  • 问题:根节点的选择该用哪个特征呢?接下来呢?如何切分呢?
  • 目标:通过一种衡量标准,来计算通过不同特征进行分支选择后的分类
    情况,找出来最好的那个当成根节点,以此类推
衡量标准-熵

:熵是表示随机变量不确定性的度量

熵值,类比物体内部的混乱程度,越混乱的,熵值越大

怎么用熵值来做衡量?
决策树经过一次决策之后,通过看它结果的熵值来判断决策的好坏

公式:
H ( X ) = − ∑ P i ∗ l o g P i , i = 1 , 2 , 3 , . . . , n , P i ⊂ [ 0 , 1 ] H(X) = -\sum P_i*logP_i , i=1,2,3,...,n ,P_{i}\subset [0,1] H(X)=PilogPi,i=1,2,3,...,n,Pi[0,1]
公式解读:

P P P 为某个类别在数据总样本的概率
① ○○○○○○○○○○
② ○○○○○○△△△△
假设现在有两组数据,分别为①、②
以 ○ 为例, P ○ P_○ P 为 ○ 在数据总样本的概率, P △ P_△ P 为 △ 在数据总样本的概率:
P ○ 1 = 1 P_{○1}=1 P1=1 P ○ 2 = 0.6 P_{○2}=0.6 P2=0.6 P △ 2 = 0.4 P_{△2}=0.4 P2=0.4
∵ P i ⊂ [ 0 , 1 ] \because P_{i}\subset [0,1] Pi[0,1]
∴ l o g P i < = 0 \therefore logP_{i} <= 0 logPi<=0
∴ l o g P ○ 1 > l o g P ○ 2 + l o g P △ 2 \therefore logP_{○1} > logP_{○2}+logP_{△2} logP1>logP2+logP2
∴ P ○ 1 ∗ l o g P ○ 1 > P ○ 2 ∗ l o g P ○ 2 + P △ 2 ∗ l o g P △ 2 \therefore P_{○1}*logP_{○1} > P_{○2}*logP_{○2}+P_{△2}*logP_{△2} P1logP1>P2logP2+P2logP2
∴ − P ○ 1 ∗ l o g P ○ 1 < − P ○ 2 ∗ l o g P ○ 2 − P △ 2 ∗ l o g P △ 2 \therefore -P_{○1}*logP_{○1} < -P_{○2}*logP_{○2}-P_{△2}*logP_{△2} P1logP1<P2logP2P2logP2
∴ − ∑ P 1 ∗ l o g P 1 < − ∑ P 2 ∗ l o g P 2 \therefore -\sum P_{1}*logP_{1} < -\sum P_{2}*logP_{2} P1logP1<P2logP2

由此可见,① 的熵值要低,因为 ① 里面只有一种类别,而 ② 中有两个类别,① 相对于 ② 的熵值就会小很多。

信息增益

在分类任务中我们希望通过节点分支后数据类别的熵值大还是小,来判断该分类有没有用,那么如何决策一个节点的选择呢?

信息增益:表示特征X使得类Y的不确定性减少的程度。(分类后的专一性,希望分类后的结果是同类在一起)

决策树构造实例

在这里插入图片描述
这是一个记录了一个人14天打球的情况的数据集,此数据集中有四种环境变化,我们要用它来构建一个决策树分类方法

对此数据集共有4种数据特征,所以我们有四种分类方式

那么问题来了,决策树是由根节点起始的,这四种分类方式里,谁来当这个根节点呢?
这里就需要通过计算来衡量了,衡量的依据就是信息增益

在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
假设:当这四种分类方式分别为根节点时,得到的分类结果

在原始数据中共14天,其中有9天打球,5天不打球,所以此时的熵应为:

− 9 14 l o g 2 9 14 − 5 14 l o g 2 5 14 = 0.940 -\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940 149log2149145log2145=0.940

所以我们得到了原始数据的熵值为 0.940 0.940 0.940

下面我们看一下基于 o u t l o o k outlook outlook 特征分类的结果:

o u t l o o k = s u n n y outlook = sunny outlook=sunny 时,熵值为 − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 = 0.971 -\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}=0.971 52log25253log253=0.971
o u t l o o k = o v e r c a s t outlook = overcast outlook=overcast 时,熵值为 − l o g 2 1 = 0 -log_21=0 log21=0
o u t l o o k = r a i n y outlook = rainy outlook=rainy 时,熵值为 − 3 5 l o g 2 3 5 − 2 5 l o g 2 2 5 = 0.971 -\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971 53log25352log252=0.971

算出每个分类结果的熵值之后,需要乘上权重再加和

根据数据统计, o u t l o o k outlook outlook 取值分别为 s u n n y sunny sunny o v e r c a s t overcast overcast r a i n y rainy rainy 的概率分别为 P s u n n y = 5 14 P_{sunny} = \frac{5}{14} Psunny=145 P o v e r c a s t = 4 14 P_{overcast}=\frac{4}{14} Povercast=144 P r a i n y = 5 14 P_{rainy}=\frac{5}{14} Prainy=145

此时熵值计算结果为:
5 14 ∗ 0.971 + 4 14 ∗ 0 + 5 14 ∗ 0.971 = 0.693 \frac{5}{14} * 0.971 + \frac{4}{14} * 0 + \frac{5}{14} * 0.971 = 0.693 1450.971+1440+1450.971=0.693

信息增益:系统的熵值从原始的 0.940 0.940 0.940 下降到了 0.693 0.693 0.693,增益为 0.247 0.247 0.247
同样的方式可以计算出其他特征的信息增益,计算完的四种分类结果所得的信息增益如下:

g a i n ( o u t l o o k ) = 0.247 gain(outlook)=0.247 gain(outlook)=0.247
g a i n ( t e m p e r a t u r e ) = 0.029 gain(temperature)=0.029 gain(temperature)=0.029
g a i n ( h u m i d i t y ) = 0.152 gain(humidity)=0.152 gain(humidity)=0.152
g a i n ( w i n d y ) = 0.048 gain(windy)=0.048 gain(windy)=0.048

那么我们选择最大的信息增益的分类特征作为根节点就可以了,相当于是遍历了一遍特征,找出来了最大的信息增益,然后再其余的中继续使用以上的方法计算信息增益往下寻找

信息增益与 g i n i gini gini 系数

关于信息增益(ID3),有一个问题,就是不适合去解决种类特别多的数据分类,例如:像ID 这类数据,将其作为数据集中的一种特征放入分类训练中时,ID = 1.2.3.4… 它确实可以很好的做出分类,甚至分类后的熵值可以为0,但是,如果是我们在判断是否出门打球的分诶任务中,ID 是没有用的,我们不可能通过一个 ID 的序列号就来断定一个人去不去打球。

为了解决 ID3 的问题,就出现了信息增益率(C4.5),它考虑到了自身的熵值,计算方法: C 4.5 = 信 息 增 益 自 身 熵 值 C4.5 = \frac{信息增益}{自身熵值} C4.5=

CART:使用 g i n i gini gini 系数来当做衡量标准

g i n i gini gini 系数:
G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p) = \sum_{k=1}^{K}p_k(1-p_k)=1- \sum_{k=1}^{K}p_k^2 Gini(p)=k=1Kpk(1pk)=1k=1Kpk2

(和熵的衡量标准类似,计算方式不相同, g i n i gini gini 系数越小效果越好)

剪枝方法

为什么要进行剪枝?

想象一下,如果树足够庞大,理论上可以完全分得开数据,每个叶子节点就只会剩一个数据,这样决策树过拟合风险很大

决策树剪枝策略分为预剪枝和后剪枝,预剪枝是边建立决策树边进行剪枝的操作,后剪枝是当建立完决策树后来进行剪枝操作

预剪枝:在建立决策树的过程当中,就可以进行剪枝操作。即限制深度、叶子节点个数、叶子节点样本数、信息增益量等

后剪枝:

后剪枝:当建立完决策树后来进行剪枝操作

公式:
C α ( T ) = C ( T ) + α ∗ ∣ T l e a f ∣ C_{\alpha}(T)=C(T)+\alpha*|T_{leaf}| Cα(T)=C(T)+αTleaf

C ( T ) = g i n i ∗ s a m p l e s C(T)=gini*samples C(T)=ginisamples
T l e a f T_{leaf} Tleaf:叶子节点的个数
α \alpha α:自定义参数。 α \alpha α 越大,树模型越不过拟合,效果不一定太好; α \alpha α 越小,效果会好,但可能会出现过拟合,
C α ( T ) C_{\alpha}(T) Cα(T)相当于一个损失,叶子节点越多,损失越大

关于决策树的回归问题解决

分类问题中,可用熵值判断
回归问题中,可用方差判断


算法模型可调参数

预剪枝:限制深度、叶子节点个数、叶子节点样本数、信息增益量
后剪枝: α \alpha α