决策树(decision tree)是一种基本的分类与回归方法。在分类问题中,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。在学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型;在预测时,对新的数据,利用决策树模型进行分类。
1、决策树
1)决策树是一种树形结构,其中每个内部节点表示在一个属性上的测试,每个分支代表一个测试输出,每个节点代表一种类别。
2)决策树学习是以实例为基础的归纳学习,在本质上是从训练数据集中归纳出一组分类规则,其学习的策略是以损失函数(损失函数通常是正则化的极大似然函数)为目标函数的极小化。
3)决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶子节点中的实例都属于一类。
2、特征选择
特征选择在于选取对训练数据具有分类能力的特征,以提高决策树学习的效率。通常特征选择的准则是信息增益或信息增益比,在CART树里使用的是Gini指数。
2.1 信息增益(information gain)
首先来了解下熵和条件熵的定义。
熵(entropy)是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其概率分布为
则随机变量X的熵定义为
在上式中的对数通常以2为底或以e为底(自然对数),这时熵的单位是比特(bit)或纳特(nat).
**条件熵(conditional entropy)**H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。定义为X给定条件下随机变量Y的条件概率分布的熵对X的数学期望
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别成为经验熵和经验条件熵
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
定义:特征A对训练数据集D的信息增益g(D,A),定义集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
一般地,熵与条件熵之差成为互信息(mutual information),决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
2.2 信息增益比(information gain ratio)
信息增益的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益比可以对这一问题进行校正。
定义:特征A对训练数据集D的信息增益比定义为信息增益g(D,A)与训练集D的经验熵H(D)之比:
2.3 Gini指数
定义:分类问题中,假设有K个类,样本点属于第k类的概率为pk,则概率分布的基尼指数定义为
对于给定的样本集合D,其基尼指数为
这里Ck是D中属于第k类的样本子集,K是类的个数。
基尼指数Gini(D)表示集合D的不确定性。基尼指数越大,样本集合的不确定性也就越大,这一点与熵值类似。
关于基尼指数的讨论,邹博老师也给除了如下图所示的解释:
总结:一个属性的信息增益(率)/gini指数越大,表明属性对样本的熵减少的能力更强,这个属性使得数据由不确定性变成确定性的能力越强。
3、决策树的生成
3.1 ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则来选择特征,递归地构建决策树。ID3相当于用极大似然法进行概率模型的选择。
算法1 (ID3算法)
输入:训练数据集D,特征集A,阈值;
输出:决策树T。
(1)若D中所有实例属于同一类Ck,则T为单节点树,并将类Ck作为该节点的类标记,返回T;
(3)否则,计算A中各特征的对D的信息增益,选择信息增益最大的特征Ag;
(4)如果Ag的信息增益小于阈值,则置T为单结点树,并将D中实例数最大的类为该节点的类标记,返回T;
(5)否则,对Ag的每一可能值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例数最大的类作为标记,构建子节点,由结点及其子结点构成树T,返回T;
(6)对第i个子节点,以Di为训练集,以A-{Ag}为特征集,递归地调用步(1)~步(5),得到子树Ti,返回Ti。
3.2 C4.5的生成算法
C4.5算法与ID3算法相似,C4.5是对ID3的改进,C4.5在生成的过程中,用信息增益比来选择特征,其他步骤与ID3一样。
3.3 CART算法
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树,内部节点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入控件即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。
算法2(CART生成算法)
输入:训练数据集D,停止计算的条件;
输出:CART决策树。
根据训练数据集,从根节点开始,递归地对每个结点进行以下操作,构建二叉决策树:
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数,此时,对每一个特征A,对其可能取的每个值a,根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分,利用上述所给的gini求解公式计算A=a的基尼指数。
(2)在所有可能的特征A以及它们所有可能的切分点a中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子节点中去。
(3)对两个子节点递归地调用步骤(1)、(2),直至满足停止条件。
(4)生成CART决策树。
算法停止的条件是节点中的样本个数小于预定的阈值,或样本集的基尼指数小于预定阈值,或者没有更多特征。
4、决策树的剪枝
决策树生成算法递归地产生决策树,直到不能继续为止,这样产生的树容易过拟合。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树。解决这个问题的办法就是简化决策树,即剪枝。
三种决策树的剪枝过程算法相同,区别的仅是对于当前树的评价标准不同。(信息增益,信息增益率,基尼指数)
通常情况下剪枝有两种:
先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。 后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。数据分析师培训
剪枝的总体思路:
由完全树T0开始,剪枝部分结点得到T1,再次剪枝部分结点得到T2,……,直到仅剩树根的树Tk;
在验证数据集上对这K个树分别评价,选择损失函数最小的树Ta
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树T的叶结点个数为|T|,t是树T的叶结点,该叶节点有个样本点,其中k类的样本点有个,k=1,2,…,K,为叶节点t上的经验熵,为参数,则决策树学习的损失函数可以定义为:
其中经验熵为
在上述损失函数的式中,第一项表示模型对训练数据的预测误差,|T|表示模型复杂度,参数控制两者之间的影响,较大的促使选择较简单的模型(树),较小的a促使选择较复杂的模型(树)。a=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。
剪枝,就是当s确定时,选择损失函数最小的模型,即损失函数最小的子树。利用损失函数的极小化等价于正则化的极大似然估计进行模型选择。
剪枝系数a的确定,如下所示:
剪枝算法:
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14