1决策树的算法
决策树的算法是以树状结构表示数据分类的结果。一般情况，一棵决策树包含一个根节点、若干个内部结点和若干个叶结点。而叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的就是为了产生一棵泛化能力强，即能处理未见示例能力强的决策树。这些就是决策树算法的结构。
2决策树的原理
一般来说，决策树归纳的基本算法是贪心算法，自顶向下以递归方式构造决策树。而贪心算法在每一步选择中都采取在当前状态下最优的选择。在决策树生成过程中，划分选择即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。这样就能够方便数据属性的划分，然后，下一步是树的剪枝。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，这样才能够使用决策树解决很多的问题。而分类是数据挖掘中的一种应用方法，而决策树则是一种典型的普遍使用的分类方法，并且决策树技术早已被证明是利用计算机模拟人决策的有效方法。
3决策树的现状
近年来随着信息技术、计算机科学的迅速发展，决策树作为重要方法之一，越来越受到人们的关注。而其在人工智能方面的潜力以及与越来越多新技术的结合，由此可见，决策树在数据挖掘乃至数据分析中还是有很长的使用时间，这就是决策树至今经典的原因。
在这篇文章中我们给大家介绍了关于数据挖掘中决策树的知识，当大家学习了决策树的概念，决策树的结构以决策树的原理，就能够掌握决策树的基础知识。不过要想学习数据挖掘，还是要学习更多的知识，希望这篇文章能够帮助到大家。
这一章主要介绍了决策树是什么，如何构建决策树；前三节针对离散值来对决策树的构建进行说明，而第四小节针对连续值如何处理构建决策树进行说明。
决策树： 基于树状结构，根据样本的属性来对样本进行判断、决策。如：给一个西瓜的各种属性，色泽=“青绿”、根蒂=“缩卷”、声音=“浊响”，通过这些属性来判断这一个西瓜是否为好瓜。
决策树的 叶结点 对应 决策结果 ，而其他结点则对应一个属性的测试， 根结点 则是包括全部样本。
怎样来选择最优属性呢？按属性来划分目的就是让决策树的每一分结点的样本尽可能是同一类，即结点的 “纯度” 越来越高。
判断纯度的高低有三种常用的指标，也是三种决策树算法常使用的。
我们先来看一个新定义， 信息熵 用来度量样本集合纯度的常用指标。 假定当前样本集合D中第K类样本所占比例为 ,则D的信息熵为：
注 信息熵越小，D的纯度越高
假定离散属性 有V个可能取值 ，若用 属性对样本集合D进行分类则有V个分支结点，第v个分支结点包含D中所有在属性 取值为 的样本，记为 ； 表示 的 信息熵 ； 表示属性 取值为 的样本占总样本的比重。
定义都清楚后，我们就来看看什么是信息增益了。 信息增益： ，简单点说就是D的信息熵减去按 属性分类后各子集的信息熵的加权平均。
注信息增益越大，说明按这个属性分类后对纯度的提高越大；信息增益是ID3决策树学习算法的常用指标。
增益率是C45决策树算法的常用指标，它是信息增益的改进。
定义： ,被称为属性a的“固有值”。
先将各个属性的 信息增益 算出来。得到其 平均值 ，将高于平均值的那些属性选出，再选择其中 增益率 最高的属性。
基尼指数：反映从数据集D中随机抽取两个样本，其类别标记不一致的概率，也可以理解为1-随机抽取两个样本类别一致的概率。
公式：
当我们要计算一个属性a的基尼指数时：
注基尼指数最小的属性为最优划分属性
剪枝处理是决策树学习算法应付“过拟合”的主要手段，基本策略有 “预剪枝” 和 “后剪枝” 。
预剪枝：在生成决策树过程中，对每个结点在划分前先估计，若划分后可以提高决策树的泛化能力则划分，否则就以当前结点为叶结点。
后剪枝：先从训练集生成完整的决策树，再自底向上进行判断，将当前结点替换为叶结点能否提高泛化能力，若可以则替换。
要如何判断泛化性能是否提高，这用到前面第二章提到的性能评估，以留出法为例，预剪枝在生成结点前判断生成前后的精度，精度大则泛化能力强，来看是否生成；后剪枝则生成决策树后判断替代前后的精度，看是否替换（书本的例子简单易懂，我这里就不过多简述）。
前面三节的决策树生成都以离散值为例，这里讲一下连续值如何生成决策树。
额外提一下：第三章的线性回归则需要将离散值化通过序连续化或向量化转化为连续值。第四章决策树则需要将连续值离散化。
二分法： 假定连续属性 在样本集D上有n个不同的取值，将这些值从小到大排序，记为 ,我们可以取一个划分点t将D分为子集 ，其中 包含那些在属性a上取值小于t的样本，而 则是取值大于t的样本集合。将集合D一分为二，故称为二分法。
注t一般选择两个相邻属性值的中心点，
在使用二分法后，对于划分的点，我们需要判断这样划分是否最优，所以就需要用到前面提到的 信息增益 ， 连续值的信息增益：
注信息增益越大，则其划分越优；且连续值属性作为当前结点的划分属性后，该属性还能作为后代结点的划分属性，这是与离散值属性不同的地方。
面对样本部分属性缺失的情况下，丢弃这些样本会造成信息浪费，且样本数本来有限丢失后有可能使学习器欠拟合。
面对缺失部分属性值的样本集，我们需要解决两个问题：①如何确定划分属性②给定划分属性后，那些缺失属性值的样本怎么划分。
首先，确定划分属性，我们从没有属性值缺失的样本入手来判断属性a的优劣；划分则将给样本赋予一个权重，有确定属性值的样本权重为一，缺失属性值的样本按权重划分。
给定训练集D和属性 ,令 表示D中在属性 上没有缺失值的样本子集，假定 有V个取值 ,令 表示 中在属性 上取值为 的样本子集， 表示 中属于第k类 的样本子集，给每个样本 赋予一个权重 ，并定义：
对属性a,表示缺失值样本所占比例。
对属性a,表示无缺失值样本中第k类所占的比例。
对属性a,表示无缺失值样本中在属性a上取值 的样本所占比例。
信息增益： ,其中
通过上面的信息增益来判断出将哪个属性作为划分属性最优，这样划分属性就确定下来了，第二个问题就是将缺失属性值的样本按权重分入各个分支中。 举个例子更容易懂：如以属性a为划分属性，a有三个取值1,2,3先将有确定属性值的样本放入分支，假设共有10个样本其a属性有确定属性值，属性值为1有5个，属性值为2有3个，属性值为3有2个，那么这时候某个没有确定属性值的样本则在各分支点权重为 。
将每个属性视为坐标空间的一个坐标轴，那么d个属性的样本对于d维空间的一个点。
决策树形成的分类边界有一个明显特点： 轴平行，即它的分类边界若干个与坐标轴平行的分段组成。
画决策树的步骤如下：
A、先画一个方框作为出发点，又称决策节点；
B、从出发点向右引出若干条直线，这些直线叫做方案枝；
C、在每个方案枝的末端画一个圆圈，这个圆圈称为概率分叉点，或自然状态点；
D、从自然状态点引出代表各自然状态的分枝，称为概率分枝；
E、如果问题只需要一级决策，则概率分枝末端画三角形，表示终点 。
例题）
假设有一项工程，施工管理人员需要决定下月是否开工。如果开工后天气好，则可为国家创收4万元，若开工后天气坏，将给国家造成损失1万元，不开工则损失1000元。根据过去的统计资料，下月天气好的概率是03,天气坏的概率是07。请做出决策。现采用决策树方法进行决策
解第一步：将题意表格化
第二步：画决策树图形，根据第一步所列的表格，再绘制决策树，如下图；
回归决策树树是用于回归的决策树模型，回归决策树主要指CART算法， 同样也为二叉树结构。以两个特征预测输出的回归问题为例，回归树的原理是将特征平面划分成若干单元，每一个划分单元都对应一个特定的输出。因为每个结点都是yes和no的判断，所以划分的边界是平行于坐标轴的。对于测试数据，我们只要将特征按照决策过程将其归到某个单元，便得到对应的回归输出值。
如上图所示的划分和相应的回归树，如果现在新来一个数据的特征是(6,75)，按照回归树，它对应的回归结果就是C5。节点的划分的过程也就是树的建立过程，每划分一次，随即确定划分单元对应的输出，也就多了一个结点。当根据相应的约束条件终止划分的时候，最终每个单元的输出也就确定了，输出也就是叶结点。这看似和分类树差不多，实则有很大的区别。划分点的寻找和输出值的确定是回归决策树的两个核心问题。
一个输入空间的划分的误差是用真实值和划分区域的预测值的最小二乘来衡量的：
其中， 是每个划分单元的预测值，这个预测值是该单元内每个样本点的值的某种组合，比如可取均值：
（输入特征空间划分为 ）
那么求解最优划分即是求解最优化问题：
其中， 和 是每次划分形成的两个区域。
关于该最优化问题的求解这里不再介绍，下面直接使用skleaen中的决策回归树来看一下决策树的回归效果，数据集使用Boston房价数据：
不进行调参的话，可以看到在测试集上R方是059，显然这是不太好的结果，但是一个有趣的现象是，在训练集上：
R方值是10，也就是在训练集上决策树预测的回归结果完全吻合毫无偏差，这显然是过拟合。这个例子也说明了决策树算法是非常容易产生过拟合的，当然我们可以通过调参来缓解过拟合。
下面绘制学习曲线来直观看一下决策树回归模型的表现，首先绘制基于MSE的学习曲线：
学习曲线如下：
再绘制基于R方的学习曲线：
上面两种都是在默认情况下也就是不进行决策树深度和叶子节点个数等条件的限制得到的结果。发现在训练集上，如果不进行限制，可以做到0偏差，这是明显的过拟合。接下来调节参数再绘制学习曲线，为节约篇幅，只调节决策树深度这一个参数，而且只绘制基于R方的学习曲线：
max_depth=1时
max_depth=3时
max_depth=5时
随着深度的增加，模型复杂度越来越高，过拟合现象也越来越明显，可以测试，当max_depth=20时，在训练集上又为一条y=1的无偏差直线。有兴趣的仍然可以修改其它参数绘制学习曲线。
决策树的局限性：
使用本系列上篇文章中的鸢尾花数据，来看一下决策树对个别数据敏感会导致的结果，在本系列上篇文章中，使用信息熵划分，其余参数默认情况下绘制的决策边界是：
接着我们删除索引为138的数据，再来绘制决策边界：
发现此时的决策边界已经完全不同了，而这仅仅只是一个数据点的影响。
综上我们知道决策树实际是一种不够稳定的算法，它的表现极度依赖调参和数据，不过虽然决策树本身不是一种高效的机器学习算法，但是它们基于集成学习的组合——随机森林(RF)却是一个很鲁棒的机器学习算法，这将在下篇开始介绍。
通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，图1表示了女孩的决策逻辑。
如果你作为一个女生，你会优先考虑哪个条件：长相？收入？还是年龄。在考虑年龄条件时使用25岁为划分点，还是35岁为划分点。有这么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？还有怎么确定用特征中的哪个数值作为划分的标准。这就是决策树机器学习算法的关键了。
首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
如抛一枚硬币为事件 ， ， ，
掷一枚骰子为事件 ， ，
，显然掷骰子的不确定性比投硬币的不确定性要高。
熟悉了单一变量的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：
有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们在知道Y以后X剩下的不确定性。表达式：
我们刚才提到 度量了 的不确定性，条件熵 度量了我们在知道 以后 剩下的不确定性，那么 呢？它度量了 在知道 以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为 。
信息熵 ，联合熵 ，条件熵 ，互信息 之间的关系由图2所示：
在决策树的ID3算法中，互信息 被称为信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
下面我们用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：
设L、F、H和D表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益：
因此日志密度的信息增益是0276。用同样方法得到H和F的信息增益分别为0033和0553。因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示：
在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
但是ID3算法中还存在着一些不足之处：
1ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为 ，另一个变量为3个值，各为 ，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。（信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大）如河校正这个问题呢？为了解决这些问题我们有了C45算法。
对于第一个问题，不能处理连续特征， C45的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为 。则C45取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点 表示为： 。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 ，取大于 为类别1，小于 为类别2。这样我们就做到了连续特征的离散化。
对于第二个问题，信息增益作为标准容易偏向于取值较多的特征。C45中提出了信息增益比：
即特征 的对数据集 的信息增益与特征 信息熵的比，信息增益比越大的特征和划分点，分类效果越好。某特征中值得种类越多，特征对应的特征熵越大，它作为分母，可以校正信息增益导致的问题。
回到上面的例子：
同样可得： ， 。
因为F具有最大的信息增益比，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示。
再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
看完上述材料，我们知道在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C45算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值种类多的特征的问题。但是无论是ID3还是C45,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
在分类问题中，假设有 个类别，第 个类别的概率为 ,则基尼系数为：
对于给定的样本 ，假设有 个类别，第 个类别的数量为 ，则样本的基尼系数为:
特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数为：
回到上面的例子：
同理得： ， 。
因为L具有最小的基尼系数，所以第一次分裂选择L为分裂属性。
再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
小伙伴们如果觉得文章还行的请点个赞呦！！同时觉得文章哪里有问题的可以评论一下 谢谢你！
决策树是一种常用的机器学习算法，它可以用于分类和回归问题。下面是决策树算法的基本步骤：
1 收集数据：收集一组带有标签的数据集，其中每个样本包含若干个特征和一个标签。特征是用于决策的信息，标签是我们需要预测的结果。
2 准备数据：对数据进行预处理，包括数据清洗、特征选择和特征转换等 *** 作。这一步是为了使得数据更加规范化和易于处理。
3 选择特征：根据一定的准则选择最优的特征，将数据集分成更小的子集。
4 构建决策树：使用递归的方法构建决策树，每个非叶子节点表示一个特征，每个叶子节点表示一个类别或一个回归值。
5 对新样本进行分类或预测：使用构建好的决策树对新样本进行分类或预测。从根节点开始，依次比较特征的取值，直到到达叶子节点为止。
6 评估模型：使用测试集评估决策树的性能，可以使用准确率、精确率、召回率等指标评估。
7 调整参数：根据评估结果调整决策树的参数，如选择不同的特征选择方法、调整决策树的深度等。
8 预测未知数据：使用调整后的决策树对新的未知数据进行预测。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）