决策树的构成要素(下列哪一项不属于树形决策树的构成要素)
本篇文章给大家谈谈决策树的构成要素,以及下列哪一项不属于树形决策树的构成要素对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
定量决策方法的决策种类
定量决策的方法主要包括风险型决策、确定型决策和非确定型决策两种。
1.风险型决策方法
风险型决策方法是指决策者在对未可能发生的情况无法作出肯定判断的情况下,通过预测各种情况发生,根据不同概率来进行决策的方法。风险型决策的方法很多,最常用的是决策树法。
决策树法是把每一决策方案各种状态的相互关系用树形图表示出来,并且注明对应的概率及其报酬值,从而选择出最优决策方案。由于根据这种方法的基本要素就可以描画出一个树状的图形,因而管理学把这一树状图形野胡称作为决策树。决策树的构成一般有五个要素:一是决策点;二是方案枝;三是自然状态点;闭脊明四是概率枝;五是概率枝末端。决策树法在决策的定量分析中应用相当广泛,有许多优点:第一,可以明确地比较轿告各种方案的优劣;第二,可以对某一方案有关的状态一目了然;第三,可以表明每个方案实现目标的概率;第四,可以计算出每一方案预期的收益和损失;第五,可以用于某一个问题的多级决策分析。
2.确定型决策方法
确定型决策问题,即只存在一种确定的自然状态,决策者可依科学的方法作出决策。确定型决策的方法有以下几类:
(1) 线性规划、库存论、排队论、网络技术等数学模型法。
(2) 微分极值法。
(3) 盈亏平衡分析法。
3.非确定型决策方法
(1)非确定型决策方法的涵义:非确定型决策方法是指决策者在对决策问题不能确定的情况下,通过对决策问题变化的各种因素分析,估计其中可能发生的自然状态,并计算各个方案在各种自然状态下的损益值,然后按照一定的原则进行选择的方法。
(2)非确定型决策方法的准则:由于非确定性决策各种自然状态出现的概率难以估计出来,因而现代决策理论根据非确定型决策问题的特点,总结出一套方便可行的方法,即先假定一些准则,根据这些准则求出方案的期望值,然后再确定每一决策问题的最优值。非确定型决策方案的准则主要有:乐观准则、悲观准则、等概率准则、决策系数准则、遗憾准则。
决策树(decisionTree)
决策树(decisionTree)是一种基本的分类和回归方法穗唯。此文仅讨论用于分类方法的决策树。
决策树的学习通常分为3步:
决策树的学习的思想主要源于
定义决策树 :
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点又分为内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性,叶结点表示一个类。
形如:
其中,圆表示内部结点,方框表示叶结点。
if-then规则,简单来说就是 :
举例:对于一个苹果,外表是红色的是红苹果,外表是绿色的是青苹果。可以表示为:
if-then规则集合具有一个重要的性质:
这就是说每一个实例都被一条路径或规则覆盖,并且只被一条路径或规则覆盖。这里所谓的覆盖是指实例的特征与路径上的特征一致,或实例满足规则的条件。
给定数据集:
其中, 为输入实例(特征向量),含有 个特征, 为类标记, , 为样本容量。
目标 :
根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确分类。
特征选择在于选取对训练数据具有分类能力的特征,这样可以提高决策树学习的效率。
如果我们利用某一个特征进行分类的结果与随机分类的结果没什么很大的差别的话,则称这个特征没有分类能力。
那么问题来了,怎么选择特征呢?
通常特征选择的准则是
下面通过例子来说明一下。
目标 :
希望通过所给的训练集数据,学习一个贷款申请的决策树。当新的客户提出贷款申请的时候,根据申请人的特征利用决策树决定是否批准贷款申请。
可见这里共有4个特征可供选择。用特征选择的准则是 。接下来介绍 。
:
熵是表示随机变量不确定性的度量。
设 是一个取有限个值的随机变量,其概率分布为
则随机变量 的熵定义为
若 ,则定义 。通常对数取以2为底,或是以 为底,熵的单位分布为比特(bit)或是纳特(nat)。
由上式可知,熵只依赖 的分布,而已 的值无关,则 的熵还可记作 ,即
则从定义可凳族碰知
当随机变量只取2个值的时候,例如 时, 的分布为
熵为
熵随概率变化的曲线为
当 或 时 ,随机变量完全没有不确定性,当 时 ,熵取值最大,随机变量不确定性最大。
设随机变量 ,其联合概率分布
条件熵 表示在已知随机变量 的条件下随机变量 的不枣谈确定性。随机变量 给定条件下随机变量 的条件熵(conditional entropy),定义为 给定条件下 的条件概率分布的熵对 的数学期望
信息增益
特征 对训练集 的信息增益
根据信息增益准则的特征选择方法:对训练集 ,计算其每个特征的信息增益,并比较大小,选择信息增益最大的特征。
前期定义各个量:
信息增益的算法
输入:训练集 和特征 ;
输出:特征 对训练集 的信息增益
回看刚才的例子,
解 :
这一次我很无聊的想用一下.csv文件类型。
所以训练数据集部分如下,我存在一个loan.csv文件里了。对.csv文件的各种处理一般由python的pandas模块完成。
第一步,导入相关模块
第二步,读入数据
若是使用jupyter,可以即刻查看一下数据,和数据标签。
可以看出,除了'ID'之外前4个标签 'age', 'work', 'own house', 'Credit conditions'为我们一直在说的特征 ,而最后一个标签'label'是我们所说的类 ,所以要处理一下这些标签,
第三步,计算训练集 的熵 :
这里会用到pandas的一个统计数据的功能, groupby(by = [列]).groups ,将数据统计成字典的形式,这么说比较抽象,看下图,将我们用pandas读入的data,分为2类, , Index 表示索引,即第0,1,4,5,6,14(python计数从0开始)个数据的 ,第2,3,7,8,9,10,11,12,13个数据的 .
那么计算训练集 的熵
第四步,计算特征 对数据集 的条件熵
第五步 ,计算信息增益
输入:训练集 和特征 和阈值 ;
输出:决策树
(1) 中所有实例都属于同一类 ,则 为单结点树,并将类 作为该结点的类标记,返回 ;
(2) 若 ,则 为单结点树,并将 中实例数最大的类 作为该结点的类标记,返回 ;
(3)否则,按照上述信息增益的算法,计算 中各个特征对 的信息增益,选择信息增益最大的特征 ;
(4)如果特征 的信息增益小于阈值 ,将置 为单结点树,并将 中实例数最大的类 作为该结点的类标记,返回 ;
(5)否则,对 的每一个可能值 ,依 将 分割为若干非空子集 ,将 中实例数最大的类 作为该结点的类标记,构建子结点,由结点及其子结点构成树 ,返回 ;
(6)对第 个子结点,以 为训练集,以 为特征集,递归的调用步骤(1)~步骤(5),得到子树 ,返回 。
对上述表的训练集数据,利用ID3算法建立决策树。
解 :
第一次迭代 :
【特征:有自己的房子】将数据集 划分为2个子集 (有自己的房子)和 (没有自己的房子),观察一下 和 :
:
由于 所有实例都属于同一类 ,所以它是一个叶结点,结点的类标记为“是”。
:
对于 则需从特征 中选择新的特征。
第二次迭代 :
将 看作新的数据集 。【特征:有工作】有2个可能值,划分为2个子集 (有工作)和 (没有工作),观察一下 和 :
:
由于 所有实例都属于同一类 ,所以它是一个叶结点,结点的类标记为“是”。
:
决策树(Decision Tree)
决策树(Decision Tree)是一种基本的分类与回归方法,其模型呈树状结构,在分类问题中,表示基于特征对实例进行分类的过程。本质上,决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤: 特征选择 、 决策树的生成 和 决策树的修剪 。
分类决策树模型是一种描述对实例进行分类的树形结构,决策树由节点(node)和有向边(directed edge)组成。节点有两种类型:内部节点(internal node)和叶节点(leaf node)。内部节点表示一个特征或属性,叶节点表示一个类。
利用决策树进行分类,从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点;这时,每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶节点。最后将实例分到叶节点的类中。
决策树是给定特征条件下类的条件概率分布,这一条件概率分布定义在特征区间的一个划分(partiton)上。将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元,决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量,Y为表示类的随机变量,那么这个条哗举枯件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合,Y取值于类的集合,各叶节点(单元)上的条件概率往往偏向于某一个类,即属于某一类的概率较大乱洞,决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程,这些基于特征区间划分的类的条件概率模型由无穷多个,在进行选择时,不仅要考虑模型的拟合能力还要考虑其泛化能力。
为了使模型兼顾模型的拟合和泛化能力,决策树学习使用正则化的极大似然函数来作为损失函数,以最小化损失函数为目标,寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题,所以在实际中通常采用启发式的方法,近似求解这一最优化问题: 通过递归的选择最优特征,根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类,最终生成特征树 。当然,这样得到的决策树实际上是次最优(sub-optimal)的。进一步的,由于决策树的算法特性,为了防止模型过拟合,需要对已生成的决策树自下而上进行剪枝,将树变得更简单,提升模型的泛化能力。具体来说,就是去掉过于细分的叶节点,使其退回到父节点,甚至更高的节点,然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多,也可以在进行决策树学习之前,对数据集进行特征筛选。
由于决策树是一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型,决策树的生成对应模型的局部选择,决策树的剪枝对应着模型的全局选择。
熵(Entropy) 的概念最早起源于物理学,最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年, 克劳德·艾尔伍德·香农 将热力学的熵,引入到 信息论 ,因此它又被称为 香农熵 。在信息论中,熵是对不确定性的量度,在一条信息的熵越高则能传输越多的信息,反之,则意味着传输的信息越少。
如果有一枚理想的硬币,其出现正面和反面的机会相等,则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么,因此每一次抛硬币都是不可预测的。因此,使用一枚正常硬币进行若干次抛掷,这个事件的熵是一 比特 ,因为结果不外乎两个——正面或者反面,可以表示为 0, 1 编码,而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ,则熵为 n ,因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同,那个这个系列抛硬币事件的熵等于零,因为 结果能被准确预测 。现实世界里,我们收集到的数答拿据的熵介于上面两种情况之间。
另一个稍微复杂的例子是假设一个 随机变量 X ,取三种可能值 ,概率分别为 ,那么编码平均比特长度是: 。其熵为 。因此u熵实际是对随机变量的比特量和顺次发生概率相乘再总和的/u 数学期望 。
依据玻尔兹曼H定理,香农把随机变量X的熵 定义为:
其中 是随机变量X的信息量,当随机变量取自有限样本时,熵可以表示为:
若 ,则定义 。
同理可以定义条件熵 :
很容易看出,条件熵(conditional entropy) 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时,所对应的熵和条件熵分别称为检验熵(empirical entropy)和经验条件熵(empirical conditional entropy).
熵越大,随机变量的不确定性就越大,从定义可以验证:
当底数 时,熵的单位是 ;当 时,熵的单位是 ;而当 时,熵的单位是 .
如英语有26个字母,假如每个字母在文章中出现的次数平均的话,每个字母的信息量 为:
同理常用汉字2500有个,假设每个汉字在文章中出现的次数平均的话,每个汉字的信息量 为:
事实上每个字母和汉字在文章中出现的次数并不平均,少见字母和罕见汉字具有相对较高的信息量,显然,由期望的定义,熵是整个消息系统的平均消息量。
熵可以用来表示数据集的不确定性,熵越大,则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果(类似于深度学习的代价函数)。对于待划分的数据集 ,其划分前的数据集的熵 是一定的,但是划分之后的熵 是不定的, 越小说明使用此特征划分得到的子集的不确定性越小(也就是纯度越高)。因此 越大,说明使用当前特征划分数据集 时,纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集,这一点可以参考优化算法中的梯度下降算法,每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理:在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展,因此我们总是选择使得信息增益最大的特征来划分当前数据集 。
显然这种划分方式是存在弊端的,按信息增益准则的划分方式,当数据集的某个特征B取值较多时,依此特征进行划分更容易得到纯度更高的数据子集,使得 偏小,信息增益会偏大,最终导致信息增益偏向取值较多的特征。
设 是 个数据样本的集合,假定类别属性具有 个不同的值: ,设 是类 中的样本数。对于一个给定样本,它的信息熵为:
其中, 是任意样本属于 的概率,一般可以用 估计。
设一个属性A具有 个不同的值 ,利用属性A将集合 划分为 个子集 ,其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性,则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数,则根据属性A划分样本的信息熵为:
其中 , 是子集 中类别为 的样本的概率。最后,用属性A划分样本子集 后所得的 信息增益(Gain) 为:
即,u属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵/u。 信息增益(information gain)又称为互信息(matual information)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小, 的值越大,说明选择测试属性A对于分类提供的信息越多,选择A之后对分类的不确定程度越小。
经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征,为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大(类似于正则化)。这个惩罚参数就是 分裂信息度量 的倒数 。
不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则u基尼指数(基尼不纯度)= 样本被选中的概率 * 样本被分错的概率/u。Gini指数越小表示集合中被选中的样本被分错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。
样本集合的基尼指数:
样本集合 有m个类别, 表示第 个类别的样本数量,则 的Gini指数为:
基于某个特征划分样本集合S之后的基尼指数:
CART是一个二叉树,也就是当使用某个特征划分样本集合后,得到两个集合:a.等于给定的特征值的样本集合 ;b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。
对于上述的每一种划分,都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度:
因而对于一个具有多个取值(超过2个)的特征,需要计算以每个取值为划分点,对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分,这个划分的划分点,就是使用特征 对样本集合 进行划分的最佳划分点。
参考文献 :
决策树--信息增益,信息增益比,Geni指数的理解
【机器学习】深入理解--信息熵(Information Entropy)
统计学习方法 (李航)
为了便于理解,利用以下数据集分别使用三种方法进行分类:
在进行具体分析之前,考虑到收入是数值类型,要使用决策树算法,需要先对该属性进行离散化。
在机器学习算法中,一些分类算法(ID3、Apriori等)要求数据是分类属性形式,因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说,连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点,将值域划分为若干区间,然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以,离散化最核心的两个问题是:如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 , 等频法 以及 一维聚类法 等。
在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化:
可以看到与手工计算的离散化结果相同,需要注意的是,u 等宽法对于离群点比较敏感,倾向于不均匀地把属性值分布到各个区间,导致某些区间数据较多,某些区间数据很少,这显然不利用决策模型的建立。 /u
使用四个分位数作为边界点,对区间进行划分:
u 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 /u
使用一维聚类的离散化方法后得到数据集为:
在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务,使用A(拥有房产)、B(婚姻情况)、C(年收入)等属性来进行数据集的划分最终构建决策树。
单身 :
离婚 :
已婚 :
显然,由B属性取值'已婚'划分得到的子数据集属于同一个叶节点,无法再进行分类。
接下来,对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择:
1)计算数据集 总的信息熵,其中4个数据中,能否偿还债务为'是'数据有3,'否'数据有1,则总的信息熵:
2)对于A(拥有房产)属性,其属性值有'是'和'否'两种。其中,在A为'是'的前提下,能否偿还债务为'是'的有1、'否'的有0;在A为'否'的前提下,能否偿还债务为'是'的有2、为'否'的有1,则A属性的信息熵为:
3)对于B(婚姻情况)属性,由于已被确定,在这个数据子集信息熵为0
4)对于C(年收入)属性,其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下,能否偿还作为为'是'的有1,为'否'的有0;在C为'低收入'的前提下,能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为:
5)最后分别计算两个属性的信息增益值:
信息增益值相同,说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的,此时任选其一成为叶节点即可。
同理,对数据子集 进行最优特征选择,发现信息熵为0:
整理得到最终的决策树:
关于管理学中决策树的问题怎么做?
决策树法用于风险性决策,就是在比较和选择活动方案时未来情况不止一种,管理者无法确定那种情况将发生,但是知道每种情况发生的概率。
决策树法是用树状图来描述各种方案在不同情况(或自然状态)下的收益,据此计算每种方案的期望收益从而作出决策的方法。
举例:
某企业为了扩大某产品的生产,拟建设新厂。据市场预测,产品销敬团睁路好的概率为0.7,销路差的概率为0. 30有三种方案可供企业选择:
方案1、新建大厂,需投资300万元。据初步估计,销路好时,每年可获利100万元;销路差时,每年亏损20万元。服务期为10年。
方案2、新建小厂,需投资140万元。销路好时,每或段年可获利40万元;销路差时,每年仍可亮岁获利30万元。服务期为10年。
方案3 、 先建小厂,三年后销路好时再扩建,需追加投资200万元,服务期为7年,估计每年获利95万元。
问哪种方案最好?
决策树中,
矩形结点称为决策点,从决策点引出的若干条树枝枝表示若干种方案,称为方案枝。圆形结点称为状态点,从状态点引出的若干条树枝表示若干种自然状态,称为状态枝。图中有两种自然状态:销路好和销路差,自然状态后面的数字表示该种自然状态出现的概率。位于状态枝末端的是各种方案在不同自然状态下的收益或损失。据此可以算出各种方案的期望收益。
决策树如下图:
方案1的期望收益为:
[0.7×100+0.3×(-20)]×10 - 300=340(万元)
方案2的期望收益为:
(0.7×40+0.3×30) - 140= 230(万元)
至于方案3,由于结点④的期望收益465(= 95×7- 200)万元,大于结点⑤的期望收益280(= 40×7)万元,所以销路好时,扩建比不扩建好。
方案3(结点③)的期望收益为:(0.7×40×3+0.7 X465 +0.3×30×10) - 140= 359.5(万元)
计算结果表明,在三种方案中,方案3最好
在复杂的决策树中还会将利率(货币的时间价值因素)考虑进去,简单建模做出决策树以后计算收益或损失即可。
[img]决策树构成的基本要素( )
决策树构成的基本要素包括:节点、分支、根节点、叶节点、特征、特征值、决策规则等。
决策树是一种基于树形结构来进行决策分析的模型。它通过将样本数据集分成许多小的子集,每个子集包含具有相似特征的数据点。在每个子集中,决策树通过对特征进行判断和分析,以确定样本数据点的分类或预测结果。决策树是一察镇种简单而有效的机器学习算法,它广泛应用于分类、回归和特征选择等领域。
决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解贺没扮法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型禅灶,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
关于决策树的构成要素和下列哪一项不属于树形决策树的构成要素的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。