北京网站建设龙鹏,wordpress 手机号注册,福州网,合肥住房和城乡建设局决策树算法
模拟相亲的过程#xff0c;通过相亲决策图#xff0c;男的去相亲#xff0c;会先选择性别为女的#xff0c;然后依次根据年龄、长相、收入、职业等信息对相亲的另一方有所了解。 通过决策图可以发现#xff0c;生活中面临各种各样的选择#xff0c;基于我们的…决策树算法
模拟相亲的过程通过相亲决策图男的去相亲会先选择性别为女的然后依次根据年龄、长相、收入、职业等信息对相亲的另一方有所了解。 通过决策图可以发现生活中面临各种各样的选择基于我们的经验和自身需求进行一些筛选把判断背后的逻辑整理成结构图会发现呈现树状的结构也就是所说的树状图。 我们在做决策的时候会经历两个阶段构造和剪枝。
构造树
构造就是生成一颗完整的决策树简单来说构造的过程就是选择什么属性作为节点的过程那么在构造过程中会存在三种节点
根节点位置位于树的最顶端可以最大化的去划分类别帮助我们筛选数据内部节点位于树中间的节点也为子节点。叶节点每个节点决策的结果不存在子节点。
所以在构造树的过程中我们要解决三个重要的问题
选择哪个属性作为根节点选择哪些属性作为内部节点(子节点)什么时候停止并且得到目标状态(叶节点)
根节点选择的不同会导致树的选择也存在差异。 问题 我们怎么来用程序选择根节点呢 目标通过一种衡量标准来计算通过不同特征进行分支选择后的分类情况找出来最好的那个当成根节点依次类推。 利用根节点可以更好的去切分数据内部节点是为了更好的细分数据。
信息熵(Entropy)
信息熵是表示随机变量不确定性的度量。熵是物理学中的知识点表示物体内部的混乱程度比如口红种类色号繁多意味着在商场中轻松买到一支完全满意的口红的概率非常低说明当种类比较混乱的话不确定性就越大熵值也就越大比如要买华为的手机进入华为专卖店就可以购买确定性越大意味着熵值就越小。
熵与分类的关系 1图进行分类后更混乱了混乱程度越大不确定性越大熵值就越大2图分类后数据比较纯分类明确规整熵值就越小。 用程序去实现的话就要把指标进行量化。
信息熵的度量
单位1bit 一枚硬币有正反两面抛硬币出现反面的概率是50%出现证明的概率也是50%这是最简单的二分类的问题抛一个硬币的不确定性记为1bit抛硬币的个数与它呈现的不确定的结果是指数的关系。
1枚硬币不确定性为2正反
2枚硬币不确定性为4全正全反一正一反一反一正
3枚硬币不确定性为8
n枚硬币不确定性为2^n等概率均匀分布
4种不确定结果 2 2 2^2 22熵为2bit 2 l o g 2 4 2log_24 2log24 8种不确定结果 2 3 2^3 23熵为3bit 3 l o g 2 8 3log_28 3log28 m种不确定结果 2 n 2^n 2n熵为nbit n l o g 2 m nlog_2m nlog2m 概率都是相等的情况 n l o g 2 m nlog_2m nlog2mm为不确定性结果的个数。
概率不等分布 把 D D D分为6种情况不确定性结果为6也即为 m 6 m6 m6 D D D的熵为 E n t ( D ) l o g 2 6 Ent(D)log_26 Ent(D)log26 真实的情况可能更加复杂如下图 D D D的不确定性分为 A 、 B 、 C A、B、C A、B、C三种 A A A又有三种情况为1/2的概率 B B B有两种情况为1/3的概率 C C C有一种情况为1/6的概率。 A A A有三种可能对应的m(A)3单个A的熵为 l o g 2 3 log_23 log23 D D D的数据更纯纯度高的减去纯度低的得到数据本身的纯度再考虑概率的问题乘以权重。 A A A处的熵为 E n t ( A ) 1 2 ( l o g 2 6 − l o g 2 3 ) Ent(A)\frac{1}{2}(log_26-log_23) Ent(A)21(log26−log23)。 B 、 C B、C B、C的熵依此类推。 E n t ( B ) 1 3 ( l o g 2 6 − l o g 2 2 ) Ent(B)\frac{1}{3}(log_26-log_22) Ent(B)31(log26−log22) E n t ( C ) 1 6 ( l o g 2 6 − l o g 2 1 ) Ent(C)\frac{1}{6}(log_26-log_21) Ent(C)61(log26−log21) D D D的熵为 E n t ( D ) E n t ( A ) E n t ( B ) E n t ( C ) Ent(D)Ent(A)Ent(B)Ent(C) Ent(D)Ent(A)Ent(B)Ent(C)推导之后可得 下图为对数的图形必要过点 ( 1 , 0 ) (1,0) (1,0)横坐标为 P k P_k Pk纵坐标为 E n t ( A ) Ent(A) Ent(A) P k 1 P_k1 Pk1的时候意味着概率为1熵为0表示数据纯度最高。 P k 1 P_k1 Pk1的作用域为0到1之间所以图形中大于1的部分是没有的。 也就是说概率越大混乱程度越低熵值就越低。
练习1
下图中图2的熵值大混乱程度高图1数据比较纯都是圆圈不确定性小熵值就越小。
练习2 集合A[1,2,3,4,5,6,7,8,9,10] 集合B[1,1,1,1,1,1,1,1,9,10] 集合B的熵值小B的数据相对比较纯出现1的概率比较大熵值小稳定性比较高。 做决策树的时候熵值越低表示数据越纯分类的效果就会更明显在数模型中希望熵值越来越小
信息增益
熵可以表示样本集合的不确定性熵越大样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合Y划分结果的好坏。 信息增益表示特征X使得类Y的不确定性减少的程度决策一个节点的选择。 下图中根节点Y的熵数据比较大为0.9数据比较混乱现对Y划分为Y_1和Y_2熵分布为0.2和0.5可以看出Y_1的分类效果比较明显。 0.9 − 0.2 0.9 − 0.5 0.9-0.20.9-0.5 0.9−0.20.9−0.5
特征A对训练数据集D的信息增益 g ( D , A ) g(D,A) g(D,A)定义为集合 D D D的信息熵 H ( D ) H(D) H(D)与特征 A A A给定条件下 D D D的信息条件熵 H ( D ∣ A ) H(D|A) H(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) 本质上为初始熵和信息熵的差距。
信息增益计算例题 如下图我们根据天气、温度、湿度、刮风四个特征来判断是否打球。 特征天气、温度、湿度、刮风 标签是否打篮球 每个特征都决定着标签对最终结果的影响如下图所示 计算过程 单单从数据上无法判断哪个特征作为根节点要根据信息增益来选择作为根节点的特征信息增益越大越好增益越大说明划分的越有效果从数据不纯往数据数据越纯的方向上移动。 1.计算初始熵2.计算各特征的熵3.进行球差得到信息增益4.选择信息增益大的特征作为根节点 计算结果为温度的信息增益最大选择温度作为根节点再从湿度、天气、刮风中选择子节点构建完整的决策树。 通过信息增益获得决策树是决策算法的一种称为ID3算法。
ID3算法的缺陷 如果在刚才的表格上增加一列IDID列的每个数字都不一样以ID特征来进行分类每一个ID值不相等且均为单独的一类每个类都只有自己意味着数据比较纯每个数据出现的概率都是100%意味着ID为0它的熵为0ID为6熵依然为0。如果使用信息增益的话ID列被作为根节点它跟最后的结果打球不打球没有关系。 所以ID3算法是由缺陷的信息增益倾向于分类较多的特征有些噪音数据就会影响整体的分类甚至整个树的构造为了解决这个缺陷提出了信息增益率。
信息增益率(C4.5)
ID3在计算的时候倾向于选择取值比较多的属性。为了避免这个问题C4.5采用信息增益率的方式来选择属性。信息增益率 信息增益 / 属性熵属性就是特征。熵代表数据的混乱程度数据的不确定性。如果一个属性有多个值数据就会被划分为多份数据的概率变大了虽然信息增益变大了属性熵也会变大整体的信息增益率就没有变的那么大。分成多份后每个类别的熵变低了对于整个样本来说不确定性增强了熵变大了分类越多信息增益就越大信息熵也就变大了。信息增益和熵是同时同向变化的所以二者的比值就会减少影响二者成正比的关系减少信息增益的变大。
CART算法
CART算法英文全名为(Classification And Regression Tree)中文叫做分类回归树。ID3和C4.5算法可以生成二叉树或多叉树而CART只支持二叉树。同时CART决策树比较特殊既可以作分类树又可以作回归树。 CART分类树与C4.5算法类似只是在属性选择的衡量指标采用的是基尼系数用的不再是信息增益或信息增益率。基尼系数是用来衡量一个国家收入差距的常用指标。基尼系数本身反映了样本的不确定度当基尼系数越小的时候说明样本之间的差异性小不确定程度低。分类的过程本身就是提纯的过程使用CART算法在构造分类树的时候会选择基尼系数最小的作为属性的划分跟熵是相反的。 GINI系数公式 G i n i ( D ) 1 − ∑ k 1 ∣ y ∣ P k 2 Gini(D) 1-\displaystyle{\sum_{k1}^{|y|}P_k^2} Gini(D)1−k1∑∣y∣Pk2 如果概率为1数据的纯度越高基尼系数就为0。二分类的问题y不是0就为1 基尼系数构建决策树
计算初始基尼系数分别计算各特征的基尼系数做差计算基尼系数增益 通过计算得知温度的基尼系数最大可以选择作为根节点。
连续性数据处理实现
在实际过程中我们有很多连续值比如下图年收益就是连续的值其实就是数值型的属性那我们怎么来计算基尼系数呢 流程如下
将乱序的值进行从小到大排序不断的二分 对数据两两数据取中间值如60和70的中间值是6570和75的中间值为72.5依次类推。以65作为分割点小于65的数只有1个占数据的十分之一剩下十分之九里面6个无贷款3个有贷款计算出基尼增益为0.02依次以72.5为分割点进行计算得到上图中的Gini系数增益得到基尼增益最好的点作为根节点。 连续性数据的处理过程是将连续值进行离散化的过程。
剪枝
剪枝就是给决策树瘦身这一步想实现的目标就是不需要太多的判断同样可以得到不同的结果。比如梯度下降的时候进行了1万次可能在几百次的时候已经出现了最好的结果剪枝是为了防止“过拟合”(Overfitting)现象的发生得到最好结果的时候就停止。过拟合训练集太过完美测试集在测试的时候结果就会不是很满意。 需要使用剪枝防止过拟合的发生如果不剪枝一直进行分裂那样本数据100%会被分割到一个正确的结果。如下图所示一直进行分裂。
不停的分下去跟分到一半的效果是一样的就没有必要一直往下分了否则会一直占用计算机的资源。
预剪枝
在构造树枝前进行一些设定
指定树的高度或者深度比如上图对10进行分裂了4次如果指定高度为3则第4次就不会被执行每一个结点所包含的最小样本数目比如说指定最小样本数为3则到3之后也不会往下执行了指定结点的熵小于某个值不再划分比如指定熵为0.2恰好2处的熵为0.2则也不会往下执行了
后剪枝
在已生成过拟合决策树上进行剪枝可以得到简化版的剪枝决策树。
