决策树法的基本步骤
决策树是一种常用的机器学习算法,它可以用于分类和回归问题。下面是决策树算法的基本步骤:
1. 收集数据:收集一组带有标签的数据集,其中每个样本包含若干个特征和一个标签。特征是用于决策的信息,标签是我们需要预测的结果。
2. 准备数据:对数据进行预处理,包括数据清洗、特征选择和特征转换等操作。这一步是为了使得数据更加规范化和易于处理。
3. 选择特征:根据一定的准则选择最优的特征,将数据集分成更小的子集。
4. 构建决策树:使用递归的方法构建决策树,每个非叶子节点表示一个特征,每个叶子节点表示一个类别或一个回归值。
5. 对新样本进行分类或预测:使用构建好的决策树对新样本进行分类或预测。从根节点开始,依次比较特征的取值,直到到达叶子节点为止。
6. 评估模型:使用测试集评估决策树的性能,可以使用准确率、精确率、召回率等指标评估。
7. 调整参数:根据评估结果调整决策树的参数,如选择不同的特征选择方法、调整决策树的深度等。
8. 预测未知数据:使用调整后的决策树对新的未知数据进行预测。
决策树的使用之分类树
5.2 决策树的基本流程可以简单概括为:
5.3 DecisionTreeClassifier参数之random_state splitter
random_state用来设置分枝中随机模式的参数,默认为none,在高维度时随机性会表现更明显。输入任意整数,会一直长出同一棵树,让模型稳定下来。
splitter有两种输入值,输入”best”,决策树在分枝时虽然随机,但是还是会优先选择更重要的特征进行分枝(重要性可以通过属性feature_importances_查看),输入“random”,决策树在分枝时会更加随机,树会因为含有更多的不必要信息而更深更大,并因这些不必要信息而降低对训练集的拟合。这也是防止过拟合的一种方式。当你预测到你的模型会过拟合,用这两个参数来帮助你降低树建成之后过拟合的可能性。当然,树一旦建成,我们依然是使用剪枝参数来防止过拟合。
5.4 剪枝参数
我们收集的样本数据不可能和整体的状况完全一致,因此当一棵决策树对训练数据有了过于优秀的解释性,它找出的规则必然包含了训练样本中的噪声,并使它对 未知数据 的拟合程度不足。(过拟合指的是在训练集上表现很好,在测试集上却表现糟糕)
为了让决策树有更好的泛化性,我们要对决策树进行剪枝。剪枝策略对决策树的影响巨大,正确的剪枝策略是优化决策树算法的核心。sklearn为我们提供了不同的剪枝策略:
5.4.1 max_depth
限制树的最大深度,超过设定深度的树枝全部剪掉。这是用得最广泛的剪枝参数,在高维度低样本量时非常有效。
5.4.2 min_samples_leaf
min_samples_leaf 限定,一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练本,否则分枝就不会发生,或者分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生。一般搭配max_depth使用,在回归树中有神奇的效果,可以让模型变得更加平滑。这个参数的数量设置得太小会引起过拟合,设置得太大就会阻止模型学习数据。一般来说,建议从=5开始使用。如果叶节点中含有的样本量变化很大,建议输入浮点数作为样本量的百分比来使用。对于类别不多的分类问题,=1通常就是最佳选择。
5.4.3 min_samples_split
min_samples_split限定,一个节点必须要包含至少min_samples_split个训练样本,这个节点才允许被分枝,否则分枝就不会发生。
5.4.4 max_features
max_features限制分枝时考虑的特征个数,超过限制个数的特征都会被舍弃。和max_depth异曲同工,max_features是用来限制高维度数据的过拟合的剪枝参数,但其方法比较暴力,是直接限制可以使用的特征数量而强行使决策树停下的参数,在不知道决策树中的各个特征的重要性的情况下,强行设定这个参数可能会导致模型学习不足。如果希望通过降维的方式防止过拟合,建议使用PCA,ICA或者特征选择模块中的降维算法。
5.4.5 min_impurity_decrease
min_impurity_decrease限制信息增益的大小,信息增益小于设定数值的分枝不会发生。这是在0.19版本种更新的功能,在0.19版本之前时使用min_impurity_split。
5.4.6 确认最优的剪枝参数
我们要使用确定超参数的曲线来进行判断了,继续使用我们已经训练好的决策树模型clf。超参数的学习曲线,是一条以超参数的取值为横坐标,模型的度量指标为纵坐标的曲线,它是用来衡量不同超参数取值下模型的表现的线。在我们建好的决策树里,我们的模型度量指标就是score。
5.5 目标权重参数
5.5.1 class_weight
完成样本标签平衡的参数。样本不平衡是指在一组数据集中,标签的一类天生占有很大的比例。因此我们要使用class_weight参数对样本标签进行一定的均衡,给少量的标签更多的权重,让模型更偏向少数类,向捕获少数类的方向建模。该参数默认None,此模式表示自动给与数据集中的所有标签相同的权重。
5.5.2 min_weight_fraction_leaf
有了权重之后,样本量就不再是单纯地记录数目,而是受输入的权重影响了,因此这时候剪枝,就需要搭配min_ weight_fraction_leaf这个基于权重的剪枝参数来使用。如果样本是加权的,则使用基于权重的预修剪标准来更容易优化树结构,这确保叶节点至少包含样本权重的总和的一小部分。
5.6 红酒数据实例
1)加载红酒数据集
2)查看标签数据
3)查看标签名称
4)划分训练集和测试集,random_state可以使拆分出的训练集、测试集是相同的
5)建立决策树,训练模型
6)导出决策树结构
7)查看每个特征的重要性
决策树法分为那几个步骤
1、特征选择
特征选择决定了使用哪些特征来做判断。在训练数据集中,每个样本的属性可能有很多个,不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征,也就是分类能力较强的特征。在特征选择中通常使用的准则是:信息增益。
2、决策树生成
选择好特征后,就从根节点触发,对节点计算所有特征的信息增益,选择信息增益最大的特征作为节点特征,根据该特征的不同取值建立子节点;对每个子节点使用相同的方式生成新的子节点,直到信息增益很小或者没有特征可以选择为止。
3、决策树剪枝
剪枝的主要目的是对抗「过拟合」,通过主动去掉部分分支来降低过拟合的风险。
【简介】
决策树是一种解决分类问题的算法,决策树算法采用树形结构,使用层层推理来实现最终的分类。
决策树的适用范围是什么?
决策树的适用范围:
科学的决策是现代管理者的一项重要职责。我们在企业管理实践中,常遇到的情景是:若干个可行性方案制订出来了,分析一下企业内、外部环境,大部分条件是己知的,但还存在一定的不确定因素。每个方案的执行都可能出现几种结果,各种结果的出现有一定的概率,企业决策存在着一定的胜算,也存在着一定的风险。这时,决策的标准只能是期望值。即,各种状态下的加权平均值。
针对上述问题,用决策树法来解决不失为一种好的选择。
决策树法作为一种决策技术,已被广泛地应用于企业的投资决策之中,它是随机决策模型中最常见、最普及的一种规策模式和方法此方法,有效地控制了决策带来的风险。所谓决策树法,就是运用树状图表示各决策的期望值,通过计算,最终优选出效益最大、成本最小的决策方法。决策树法属于风险型决策方法,不同于确定型决策方法,二者适用的条件也不同。应用决策树决策方法必须具备以下条件:
1、具有决策者期望达到的明确目标;
2、存在决策者可以选择的两个以上的可行备选方案;
3、存在着决策者无法控制的两种以上的自然状态(如气候变化、市场行情、经济发展动向等);
5、不同行动方案在不同自然状态下的收益值或损失值(简称损益值)可以计算出来;
6、决策者能估计出不同的自然状态发生概率。
决策树(decisiontree)一般都是自上而下的来生成的。每个决策或事件(即自然状态)都可能引出两个或多个事件,导致不同的结果,把这种决策分支画成图形很像一棵树的枝干,故称决策树。
决策树(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:
整理得到最终的决策树: