概述
决策树
- 前言
- 一、工作原理
- 1. 定义
- 2. 优缺点
- 3. 结构
- 4. 决策树与条件概率分布
- 二、决策树训练过程
- 1. 训练策略
- 2. 特征选择
- 2.1 信息增益
- 2.1.1 定义
- 2.1.2 条件熵和信息增益
- 3. 决策树的生成
- 3.1 ID3算法
- 3.2 C4.5算法
- 3.3 CART算法
- 3.4 小结
- 4. 决策树的剪枝
- 总结
前言
- 在现实生活中,我们会遇到各种选择,不论是选择男女朋友,还是挑选商品,都是基于以往的经验来做判断。如果把判断背后的逻辑整理成一个结构图,你会发现它实际上是一个树状图,这就是我今天介绍的决策树。
一、工作原理
- 下面介绍相亲这样一个场景:
母亲:给你介绍个男朋友
女儿:年龄多大?
母亲:26
女儿:长得帅不帅?
母亲:挺帅的
女儿:收入高不高?
母亲:不是很高,也不算太低
女儿:是公务员吗?
母亲:是,在党政机关上班
女儿:那好,我去见见 - 我们把女儿选择的逻辑整理成一个简单的结构图:
可以看出女儿是根据已知的男方的若干条件,来对是否去见他作出判断。上面这个图就是一棵典型的决策树。
1. 定义
- 决策树是一种基本的分类和回归方法,其模型呈树形结构,可以认为是if-then的规则集合。
- 训练时,利用训练数据,根据损失函数最小化的原则建立决策树模型,预测时,直接利用模型进行分类或回归。
2. 优缺点
- 优点:其优点是具有很好的可读性,训练和预测的速度快。
- 缺点:决策树的其中一个缺点是容易过拟合,因此在生成决策树之后需要对其进行修剪处理。
3. 结构
- 决策树有三个节点:
根节点:就是树的最顶端,最开始的那个节点。在上图中,“天气”就是一个根节点;
内部节点:就是树中间的那些节点,比如说“温度”、“湿度”、“刮风”;
叶节点:就是树最底部的节点,也就是决策结果。 - 每个非叶节点表示一个特征属性测试;
每个分支代表这个特征属性在某个值域上的输出;
每个叶子节点存放一个类别;
每个节点包含的样本集合通过属性测试被划分到子节点中,根节点包含样本全集。
#其中属性测试的目标是让各个划分出来的子节点尽可能低“纯”,即属于同一类别。
4. 决策树与条件概率分布
- 决策树本质上是对于给定特征空间上的一个划分,树上的每一条从根节点到叶节点的路径将特征空间划分成互不相交的一个区域。每个区域的类别分布构成了条件概率分布,假设X为表示特征的随机变量,Y为表示类的随机变量,则这个条件概率分布可以表示为P(X|Y),各个叶节点上的条件概率往往偏向与某一个类,也就是属于某一个类的概率比较高。决策树在分类时则将落到改叶节点的事例划分为概率最高的类别。
二、决策树训练过程
- 我们在做决策树的时候,会经历两个阶段:构造和剪枝,再细分就是特征选择、决策树生成以及修剪。
1. 训练策略
决策树的学习本质是从训练数据中归纳出一组与其吻合的规则,或者说是通过对特征空间的划分使每个子空间的分类与训练数据吻合,同时能够有较好的泛化能力。这种划分一般来说有无穷多个,因此需要一个策略来进行决策树的生成。
决策树用损失函数来实现这一个目标,通过建立一个正则化后的损失函数,采取最小化损失函数的策略来建立决策树。
即使确立了最小化损失函数的目标,在无穷多个决策树中选取最优的一个仍然是一个非常困难的问题。
为了解决这一问题,采取贪心算法构建决策树,可以获得近似最优解。在构建决策树时,不断递归地选取能够时损失函数最小化的特征来对样本进行划分并构建子树根节点,直到某一个节点上所有的样本都位于同一类,或者满足于其他条件时,停止划分该子树。按照这样方法,总决策树下边的每一个子树都是在当前条件下面的一个最好的分类。
以上的方法可以构建一个对训练样本表现很完美的决策树,但是对未知的数据确未必。当树的深度过大时,或者子树上的样本过少时,再对其进行划分可能会造成过拟合。因此在生成决策树之后,需要对其剪枝,删除过于细分的叶节点,使其退回到父节点。
原文链接:https://blog.csdn.net/a136522541/article/details/87596068
2. 特征选择
- 在构建决策树的时候,最重要的一步是要决定需要选取的特征。通常来说,选取的特征要与最终的分类结果有一定的相关性,如果选取该特征后与随机分类的结果没有太大分布,这样的特征是无效的。
下边用一个简单的例子对选取过程作一个介绍:
- 表中是一个由15个训练样本组成的西瓜数据集,每个样本有6个特征。第一个特征是色泽,分为青绿、乌黑、浅白3类,第二个特征是根蒂形状,有蜷缩、稍蜷和硬挺三类…
- 在构建决策树时,我们首先想从6个特征中选取一个,比如色泽一项,将训练数据分成三类。或者选取根蒂形状,将数据分成3类。这样就构建出不同的决策树。如下图:
- 这样的决策树可以有多种,但是哪一种是最好的呢? 直观上说,如果按照特征分类结束后,叶节点中的样本类别是更加偏向某一类的,那么按照这个特征分类就比较好了。在数学上可以通过信息增益来描述这一情况。
2.1 信息增益
2.1.1 定义
- 假定数据集 D 中离散属性 a 有 V 个可能的取值,若使用 a 对数据进行划分,则会产生 V 个分支节点,其中第 V 个分支节点包含了 D 中所有在属性 a 上取值为 av 的样本,记为 Dv,可以用属性 a 对 样本集D 进行划分所得的信息增益(Information Gain):
G a i n ( D , a ) = E n t ( D ) − ∑ i = 1 v D v D E n t ( D v ) Gain(D,a)=Ent(D)-sum_{i=1}^v frac {D^v}{D} Ent(D^v) Gain(D,a)=Ent(D)−i=1∑vDDvEnt(Dv)
描述了在知道 a 之后数据集D不确定性减少的程度,后面部分越小,减少的程度越小,增益越大。
2.1.2 条件熵和信息增益
- 数学上用熵来表示随机变量的混乱度,设有一个随机变量X,其概率分布为:
P ( X = x i ) = P i P(X=x_i)=P_i P(X=xi)=Pi
则其熵可以定义为:
H ( p ) = − ∑ i = 1 n p i l o g p i H(p)=-sum_{i=1}^n p_ilogp_i H(p)=−i=1∑npilogpi
即熵可以定义为信息的期望值,信息熵越小,代表事件越确定,换到决策树中可以表示某类样本所占总样本的比例很大。 - 在计算经过决策树分类后的样本的熵时,需要用到条件熵,定义如下:
设有随机变量(X,Y),其联合概率分布为:
P ( X = x i , Y = y j ) = P i j P(X=x_i,Y=y_j)=P_{ij} P(X=xi,Y=yj)=Pij
则条件熵定义为:
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=sum_{i=1}^n p_iH(Y|X=x_i) H(Y∣X)=i=1∑npiH(Y∣X=xi)
表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。则样本的熵和条件熵的差g(D,A) 即为信息增益:
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)
就是信息增益 = 信息熵 - 条件熵。
3. 决策树的生成
3.1 ID3算法
- ID3算法的核心是在决策树的各个节点上利用信息增益来选取特征,递归构建决策树。具体方法为:
从根节点开始,对其包含的所有样本的所有特征计算信息增益,选取增益最大的特征作为节点特征,建立子节点,再对子节点递归进行以上操作,直到没有再能够分类的特征,或分类后信息增益小于某个阈值,停止构建树。 - 缺点:
1.只能处理离散型属性,并且对倾向于选择取值较多的属性;
2.对于缺失值的情况没有做考虑;
3.没有考虑过拟合的问题。 - 原因:信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大。
3.2 C4.5算法
- 与ID3算法相似,但是做了改进,将信息增益比作为选择特征的标准。
- 信息增益比:特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比:
G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain_ratio(D,a)=frac {Gain(D,a)}{IV(a)} Gain_ratio(D,a)=IV(a)Gain(D,a)
I V ( a ) = − ∑ i = 1 V D v D l o g D v D ( 特 征 a 的 熵 ) IV(a)=- sum_{i=1}^V frac {D^v}{D} logfrac {D^v}{D} text (特征a的熵) IV(a)=−i=1∑VDDvlogDDv(特征a的熵) - 缺点:增益率对可取值数目较少的属性有所偏好,所以倾向于选择取值较少的属性。
3.3 CART算法
- 无论是ID3还是C4.5,它们都是基于信息论的熵模型的,这里面不可避免的会涉及大量对数运算,那我们能不能在简化模型的同时也不至于完全丢失熵模型的优点呢?
- CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。这和信息增益(比)是相反的。
- 在分类问题中,假设有 k 个类别,第 k 个类别的概率为 pk, 则基尼系数的表达式为:
G i n i ( D ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 0 K p k 2 Gini(D)=sum_{k=1}^K p_k(1-p_k) = 1-sum_{k=0}^K p_k^2 Gini(D)=k=1∑Kpk(1−pk)=1−k=0∑Kpk2
对于二分类问题:
G i n i = 2 p ( 1 − p ) Gini=2p(1-p) Gini=2p(1−p)
对于给定的 样本D 假设有 V 个类别的数量为 Dv,则 样本D 的基尼系数表达式为:
G i n i ( D ) = 1 − ∑ v = 1 V ( D v D ) 2 Gini(D)=1-sum_{v=1}^V (frac {D^v}{D})^2 Gini(D)=1−v=1∑V(DDv)2
对于 样本D,如果根据特征 A 的某个值 a,把 D 分成 D1 和 D2 两个部分,则在特征 A 的条件下,D 的基尼系数表达式为:
G i n i ( D , a ) = D 1 D G i n i ( D 1 ) + D 2 D G i n i ( D 2 ) Gini(D,a)=frac {D_1}{D} Gini(D_1) + frac {D_2}{D} Gini(D_2) Gini(D,a)=DD1Gini(D1)+DD2Gini(D2) - 基尼系数的特质是:
1.类别个数越少,基尼系数越低;
2.类别个数相同时,类别集中度越高,基尼系数越低。
3.4 小结
- 分享一幅三种算法的对比图,方便记忆:
4. 决策树的剪枝
- 以上方法在生成决策树时往往能够对训练数据表现很好,但是在测试集数据表现得并不理想,这是由于在训练过程中树的深度过大,产生了过拟合。为了解决这个问题,我们可以减少其“深度”,也就是在树生成之后,要对其进行剪枝处理,对于删除分类过细的叶节点,使其退化回其父节点。
下边介绍一种正则化剪枝方式: - 剪枝通常是通过最小化损失函数来进行的,设树 T 的叶节点个数为 |T|,t 是树的叶节点,每个叶节点有 Nt 个样本,其中属于类 k 的样本有 Ntk 个,Ht(T) 为叶节点 t 上的熵,α≥0 是待定参数,则决策树的损失函数可以定义为:
C α ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_alpha(T)= sum_{t=1}^T N_tH_t(T)+ alpha |T| Cα(T)=t=1∑TNtHt(T)+α∣T∣
对于上式第一项,当某个叶节点t中的各类样本分布越均匀,证明该节点的分类效果越差,得到的熵也就越大,因此该项可以表示决策树的分类误差。式中第二项是描述决策树的复杂度的,当决策树越复杂,叶节点也就越多,该项也就越大,参数 α 是自定义参数,用于决定此项在损失函数的占的比例,当此项为0时,损失函数不考虑决策树的复杂度。 - 定义好决策树的损失函数后,对其剪枝就十分简单了,对于一棵生成好的树,计算每个叶节点的熵,再递归计算删除该节点后父节点的熵,然后得出损失函数,如果删除节点后损失函数变小,则该节点予以删除,否则保留,直至所有叶节点计算完毕。
总结
- 决策树是一种基本的分类和回归方法,其模型呈树形结构;
- 决策树训练过程大致分为:特征选择、决策树生成以及修剪;
- 介绍了决策树构造过程的其中三种算法:ID3、C4.5和CART算法;
- 为避免产生过拟合现象,我们通过最小化决策树的损失函数来对决策树进行“剪枝”。
本篇文章到此结束,谢谢大家的观看,欢迎各位批评指正!
最后
以上就是辛勤菠萝为你收集整理的决策树前言一、工作原理二、决策树训练过程总结的全部内容,希望文章能够帮你解决决策树前言一、工作原理二、决策树训练过程总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复