决策树--它即能做分类又能做回归我们用ID3（信息增益）,C4.5（信息增溢率）,CART（Gini系数）创建的决策树树可以做分类，我们用CART（方差）创建的树可以做回归。 数据结构中有一个树状结构叫做二叉树，二叉树上每个非叶子结点都有一个条件，满足条件的放到结点的右边，不满足条件的放到结点的左边。 决策树类似于二叉树，它每个非叶子结点上都有一个根据样本特征判断的条件，这个条件叫做决策，满足决策的放到结点的右边，不满足决策的放到结点的左边。 决策树的例子现在我们有五个人，我们把他们看成是五个样本，每个样本有两个特征，分别是年龄和性别，现在我们要构造一个决策树，来判断这五个人中谁喜欢踢足球，判断的条件是，年龄小于15的男性，于是我们构造出了右边的这样的一颗决策树，我们将所有的数据样本输入到这个决策树中，他们就将先根据年龄进行决策，然后符合年龄小于15的在根据性别进行决策，根据这个构造的决策树，可以知道只有这个小男生是喜欢踢足球的。这个例子是决策树的分类问题。 这就是决策树的直观体现，决策树中每一个非叶子结点就是一个决策点，每个决策点实际上就是一个具有离散输出的测试函数 决策树是一个一个特征进行处理，之前线性回归和逻辑回归是所有特征给予权重相加得到一个新的值。  这个例子就是在各种天气情况下是否要玩球，我们可以看出该数据集中有9个样本是玩的，5个样本是不玩的，那么我们就通过决策树算法来学习出什么情况下是玩的，什么情况下是不玩的。 第一个结点中有两类，一类玩9个人，一类不玩5个人，第一个决策条件是天气，它有三种可能，分别是sunny，overcast，rain，我们拿sunny来举例，当sunny的时候有2个人玩3个人不玩，玩的和不玩的并没有完全分开。那么说明此时还得继续决策，决策调价是湿度，我们这里设置的阈值是70，所以分为小于70和大于70，可以看出小于70的有两个样本是玩的，大于70的三个样本是不玩的。这样玩的和不玩的样本已经完全分开了。这样这条线就决策完成了。当所有都决策完成的时候，我们就可以看到如图所示的决策树了。 决策树是概率模型决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分（partition）上。将特征空间划分为互不相交的单元（cell）或区域 （region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的 一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点（单元）上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。 知识准备-----熵熵指的是一个物体内部的混乱程度，越混乱熵越大，或者说变量的不确定性越大，类别越多，熵就越大 事件X和事件Y相互独立，则p(XY）=p(X)*P(Y)，Log（XY）=Log（X）+Log（Y） H(X),H(Y)分别表示事件X，Y发生的不确定性 所以一个事件的发生概率p很大，那么这件事不确定性H就会很小，同理，如果一个事件的发生概率p很小，那么这件事情的不确定性H就会很大 假设随机变量X的可能取值有x1，x2， ... , xn，对于每一个可能的取值xi，其概率 P(X=xi) = pi , ( i = 1,2, ... , n)，因此随机变量X的熵：  这个经验熵的公式应该这样理解，熵指的是一个物体内部的混乱程度，类别越多越混乱，越混乱熵越大。 举例有两个集合，集合A（1，2，3，4，5），集合B（1，1，1，1，1），则集合A有五个类别，但是结合B只有一个类别，所以集合A更加混乱，所以集合A的熵比集合B大。 从数学角度分析，首先pi的值肯定小于等于1，所以ln（pi）肯定是负的或0，我们试着想象一下ln这条曲线，可以知道pi越小ln（pi）越小 集合b中只有一个类别，所以pi等于1，而ln（pi）等于0，所以集合b的熵为0 集合a中有五个类别，每个类别的pi分别为五分之一，然后ln（pi）肯定为负，pi*ln（pi）为负，然后这五个类别的piln（pi）加起来还为负，最后前面有一个负号，就变成正了，所以集合a的熵肯定大于0 这就证明了，集合a比集合b混乱，集合a的熵比集合b的熵大。 对于样本D来说，随机变量X是样本的类别，即，假设样本有k个类别，每个类别的概率是  ，其中|Ck|表示类别k的样本个数，|D|表示样本总数，则对于样本集合D来说某个节点分割前的熵值（经验熵empirical entropy）为：  假如一个节点的类别有三种，那么这个节点计算经验熵时k为3，C1表示第一类的数量，D表示总量 分割后的熵值：经验条件熵  A表示某一种分割，H（D|A）就表示在按照A这种分割的情况下的条件熵 这个表示一个节点分成n个分支，每个分支的节点计算信息熵，具体的计算公式是  信息增益：以某特征划分数据集前后的熵的差值（ 在熵的理解那部分提到了，熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征A对于样本集合D划分效果的好坏。）  信息增益的缺点：信息增益偏向取值较多的特征 原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。为了解决这个办法我们使用信息增益率 信息增益率：    g（D，A）表示信息增益率=初始集合D的熵H（D）-以A为特征决策时的集合的熵H（D|A） HA（D）表示我们按照A特征进行分类，和样本标签没有关系 对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。之前是把集合类别y作为随机变量，现在把某个特征作为随机变量，按照此特征的特征取值对集合D进行划分，计算熵HA(D) HA（D）这样理解，就是说我们不管样本的y是什么了，我们只按照特征A分类，假如分为两个类，一类7个，一类3个，那么我们就是-（7/10log7/10+3/10log3/10），这完全是按照特征A进行分类，把样本y给省略了。 Gini系数 分割后的基尼系数 和熵一样前面呈上每个分支的样本占比然后求和，也就是对每个子节点加权求和 Gini系数其实和熵的衡量指标其实是差不多的，只不过计算方式是不一样的，但从结果上他们表达的都是一层含义，也就是说Gini系数越大表示越混乱，类别越多，越小表示类别越少，越不混乱。 从数学角度来分析，还是有上面的那两个集合，分别是集合A和集合B，集合B中只有一个类别，pi等于1.所以带入到Gini系数的公式中，得到的Gini系数为0. 集合A中，有五个类别，p1，p2，p3,p4,p5分别为0.2，带入到公式中就是0.2的平方为0.04，五个进行累加，结果为0.2，然后1-0.2就是0.8 0.8大于0，就表示集合A的Gini系数大于集合B的，就表示集合A的比集合B混乱，事情确实如此 这是计算基尼系数的代码，我们有一个数据集data，我们首先遍历这个数据集，统计它的类别，假如y有两种情况0或1，分别为3个和7个，那么for循环完成之后classNumber中索引0为3，索引1为7. 然后classNumber[k]*classNumber[k]/data.length/data.length表示的意思是(classNumber[k]/data.length)的平方，然后不断累加，最终返回1-sum，就是当前这个数据集的gini系数 我们根据信息增益、信息增溢率、基尼系数的建树标准我们在建造决策树的过程中我们选择信息增溢最高的作为根节点，或者选择信息增溢率最高的作为根节点，而基尼系数选择最小的作为根节点 决策树的熵，和Gini系数的含义这两个是一致的，总的来说就是越大，表示越混乱，表示类别多，间接表示为分类效果并不好。越低表示分类效果越好，模型越纯 决策树的构造的例子演示数据集有了，那么我们要来根据这个数据集来构造一个决策树，那么问题来了，到底哪个特征要作为根节点了，这个根节点可不能随便的选择，它必须满足上面的决策树的构造基本思想。 数据集 假设我们现在有这样一个数据集，14个样本，每个样本有四个特征，分别是outlook，temperature，humidity，windy，每个样本表示当前这一天的天气情况。最后一列，为标注，表示在当前这一样本的情况下有没有去踢足球，分为两类，分别是yes和no 我们先来看一个标注play，它分为两类，一类是yes，一类是no，其中yes为9个，no为4个，所以我们可以通过这两个类计算出此时它的信息熵值为： 0.940表示我们在什么都没有做的前提下，当前数据集固有的熵值，那么我们下面构造决策树的标准之一就是尽快的降低这个熵，而且降低的速度越快越好，我们下面有四种分类的方式，究竟哪个特征作为决策树的根节点最好呢？ 我们只需要计算出这四种分类所对应的熵值，就可以判断出究竟是哪一个特征作为根节点是最好的。 拿天气来举例，它分为三个集合（看作是集合不是类别，类别只有play的yes和no），分别为sunny，overcast，rainy，其中第一个sunny集合为两类（yes，no），这个集合的熵为0.971，第二个overcast集合只有一类（yes），这个集合的熵为0，第三个rainy集合也分为两类，这个集合的熵为0.971。然后根据历史数据统计，outlook取值为sunny、overcast、rainy的概率分别为5/14、4/14、5/14（以天气来说，其中数据集中sunny有5个样本，overcast有4个样本，rainy有5个样本），所以当outlook为根节点时熵为：5/14*0.971+4/14*0+5/14*0.971=0.694 这样系统的熵就从0.940下降到0.693，信息的增溢gain（outlook）为0.940-0.693=0.247，信息增溢就是熵值的变化，这个表示为当以天气为分类的信息获取量（信息的增溢gain） 同样可以计算出gain（temperature）=0.029、gain（humidity）=0.152、gain（windy）=0.048 gain（outlook）最大，就是说outlook第一步使的系统的信息熵下降的最快，所以决策树的根节点就去outlook。 那么我们使用outlook发现熵是下降了，这说明纯度上升了，这说明当前的一个分类效果，要比上一步强一些。 现在我们确定根节点就是天气，由此天气会产生三个分支 然后sunny分支就是将天气等于sunny的数据从整体数据集中挑出来，overcast就是将天气等于overcast的数据从整体数据集中挑出来，rainy分支就是将天气为rainy的数据从整体数据集中挑出来。然后观察y的情况，我们会发现当天气等于overcast的时候，y的值全为yes 我们就可以说overcast这个分支不用建立新的结点来分了，这就表示决策树在这个方向就建立完成了。 而当天气为sunny和rainy的时候y还是有两种yes和no，所以这两个分支的根节点，我们要从当前分支挑出来的数据集中，用类似的方法来其他的三个特征中在选择一个节点作为分支的根节点，看这三个节点的信息增溢哪个最大，依此类推,构造决策树。当系统的信息熵降为0时,就没有必要再往下构造决策树了,此时叶子节点都是纯的--这是理想情况。最坏的情况下,决策树的高度为属性(决策变量)的个数,叶子节点不纯(这意味着我们要以-定的概率来作出决策，或者多数优先原则)（有可能再我们的样本中特征一样但是标签不一样，这种情况也有可能出现，比如某个特征是缺失值的时候就有可能出现这种情况的）。 执行一个分割的信息增益越大，表明这个分割对样本的熵减少的能力越强，这个分割所在的特征使得数据由不确定性变成确定性的能力强。 上面的算法叫做决策树的归纳算法-ID3算法ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策 树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益， 选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点 递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择 为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。 它的执行步骤是：
递归划分步骤仅当下列条件之一成立停止：
在第二种情况下我们把当前节点标记为叶节点，并将其类别设定为该节点所含类别最多的样本；在第三种情况下，同样把当前节点标记为叶子节点，但是其类别设定为其父节点所包含样本最多的类别。注意这两种情况的处理实质是不同的，情况二是再利用当前节点的后验分布，而情况三是把父结点的样本分布为当前节点的先验分布。 决策树ID3算法的不足（1）ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。因为那个时候并没有考虑到二分法，所以他没有办法处理连续值，但是它和二分法结合是可以处理连续值的。 （2）ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？ （3） ID3算法对于缺失值的情况没有做考虑 （4）没有考虑过拟合的问题 信息增益的问题--信息增溢率C4.5算法针对第一个问题，ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法。C4.5的思路是使用二分法将连续的特征离散化，这样它就可以处理连续数据了。 针对第二个问题，我们看起来信息增益很好用，只要谁的信息增益最大就是谁了，但是很有可能出现这种情况，就是有一个特征种类很多，但是每个特征种类对应的样本数量很少，有可能一个特征对应一个样本，所以该特征的每个分支节点熵值都为0，然后最终导致这个特征作为根节点的熵特别小（因为产生的结点都只有一类，特别纯,所以都是0），然后这个特征的信息增益就很大，就把这个节点放到了根节点的位置了。但是恰巧这个特征和标签的关系还不大，或者说这个特征根本就不会影响整个样本的标签，那么此时把它放到决策树的根节点是非常错误的。 那么这种情况下，信息增益就不靠谱了，为了解决这个问题，引入了信息增益率，它的计算方式是该特征的信息增益/该特征自身的熵，就比如上面的这个问题，它的信息增溢大，但是因为它的类别多，不纯，所以它自身的熵也大，结果就是它的信息增益率不大。所以以后我们就通过信息增益率还选择节点，使用信息增益率来选择的节点的方法叫做c4.5（可以看作是ID3的扩展）。需要注意的一点是，信息增溢率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择信息增溢率最大的候选划分的属性，而是使用启发式算法，先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择信息增溢率最高的。 针对第三个问题，缺失值处理问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。 对于第一个子问题，我们将信息增益的计算式推广为： 其中p、pk、rv为： 这个公式看起来有些乱，我们通过一个案例来解决这个问题。 我们现在有一个下面的数据集 其中它有一些地方是缺失的，我们以色泽为例，我们如何计算它的信息增益呢？ 我们首先把缺失的去掉，那么我们现在的样本是14个{2，3，4，6，7，8，9，10，11，12，13，14，15，16，17} 这样我们把样本的缺失值去掉之后，我们的样本如上所示，下面我们就来计算我们的初始熵以及条件熵： 其中初始熵为： 条件熵为： 4/14*1.000+6/14*0.918+4/14*0.000=0.679 则我们此时在这14个样本上的信息增益为：0.985-0.679=0.306 此时在17个样本（包含缺失值）的信息增益为：p*0.306=14/17*0.306=0.252 这个就是我们的带有缺失值的按色泽决策的信息增益，其它的特征如果有缺失值也按照这样的方式来算，这里我们可以找到信息增益最大的作为我们的决策特征。其实这个缺失的特征和没有缺失的特征相比，第一步就是去掉缺失的特征，然后在这个样本的上计算信息增益（但是比值不仅仅是个数之间的比例，而是权重和之间的比例），和以前一样，只不过最后还要乘上一个比例，这个比例就是非缺失的样本权重/总样本数权重 对于第二个子问题，我们可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9，我们拿纹理来举例： 我们的{8，10}的样本在“纹理”这个属性上是缺失的，该被划分到哪个分支里？ 我们上面已经说过了，缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。 那么此时我们的各个节点中的样本的权重就不在是1了，有个别样本的权重发生了变化，那么下面在每一个节点中选择使用哪个特征进行决策的时候，此时的信息增益是怎么算的呢？ 我们拿最左边这个节点，也就是分支等于模糊的节点进行举例，看它是如何选择特征进行决策的？ 此时的样本集为： 我们下面计算色泽的信息增益 该属性中无缺失值的样本集为{7，8，9，10，14，17}共六个样本，但是样本8和样本10的权重都是1/3，因此无缺失值的样本集的权重为：4+2/3=14/3，有缺失值的样本的权重为：17/3。所以p=（14/3）/（17/3）=14/17，这就是我们所要计算的p。 我们无缺失数据集中正样本的比例（正样本权重占总样本权重的比例）为（1+1/3）/（4+2/3）=4/14 我们无缺失数据集中负样本的比例（负样本权重占总样本权重的比例）为（3+1/3）/（4+2/3）=10/14 那么初始熵为： 我们下面计算条件熵 此时，各个节点的熵分别为： 每个节点所占的比例为： 所以条件熵为： 所以无缺失值的数据集信息增益为： 所以色泽最终的信息增益（全部数据包含缺失值）： 针对第四个问题：使用剪枝的方式进行处理。 我们前面已经知道了ID3算法和C4.5算法，它们使用较为复杂的多叉树，都只能处理分类，而不能处理回归，而CART算法形成的决策树是即可以做回归，也可以做分类的二叉树 CART算法，使用CART算法创建分类决策树CART分类决策树使用的是“基尼指数”来选择划分属性，在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为： 如果我们的当前的节点的类别只有两个，属于第一个类别输出的概率是p，那么第二个类别的概率就是1-p，则基尼系数的表达式为： 特别的，如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即 则在特征A的条件下，D的基尼系数表达式为： 我们建造一棵分类决策树的过程是： 输入：训练数据集D，停止计算的条件； 输出：CART决策树。 根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树： （1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A＝a的测试为“是”或“否”将D分割成D1 和D2两部分（左子树D1为特征值为a，右子树D2为特征值为非a的），计算A＝a时的基尼指数。 （2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成 两个子结点，将训练数据集依特征分配到两个子结点中去。 （3）对两个子结点递归地调用（1），（2），直至满足停止条件。 （4）生成CART决策树。 算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征了。 下面我们通过一个实例来完成CART算法的特征选择 是否贷款 分别以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征，并以1，2，3表示年龄的值为青年、中年和老年，以1，2表示有工作和有自己的房子的值为是和否，以1，2，3表示信贷情况的值为非常好、好和一般。 我们下面来计算各个特征对应各个特征值的Gini系数 我们先来计算特征A1,其中特征值为1的个数为5人，特征值为2的人数为5人，特征值为3的人数为5个人，那么我们有三种建造树的方式： 方式一 方式二 方式三 这个就是我们特征A1，进行决策树构建的三种情况，我们来算出此时上面三种分叉方式的Gini系数，最小的那个基尼系数就是此时特征A1最优的基尼系数 因为有两个相等，所以A1=1和A1=3都可以作为A1的最优切分点。同理我们再来计算出其它特征的最优切分点 特征A2和A3很特殊，特征值只有两类，所以它的切分点只有一个，它们两个的Gini系数为： 而特征A4的基尼指数为： Gini(D，A4＝3)最小，所以A4＝3为A4的最优切分点。 在A1，A2，A3，A4几个特征中，Gini(D，A3＝1)＝0.27最小，所以选择特征A3为最优 特征，A3＝1为其最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结 点继续使用以上方法在A1，A2，A4（这句话说明了离散属性已经切分，下面不会再次被切分了）中选择最优特征及其最优切分点，结果是A2＝1。依此 计算得知，所得结点都是叶结点。 CART分类树算法对于连续特征处理和C4.5一样都是进行离散化，进行二分方式找到基尼系数最小点作为该连续特征的二元离散分类点，对于缺失值的处理方法和C4.5算法里描述的相同。 CART算法，使用CART算法创建回归决策树假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集 考虑如何生成回归树。 生成回归树的方式和生成分类树构造方式是一样的。只不过选择某个特征的某个切分点的方式不同了，分类树使用的是Gini系数，回归树使用的平方误差的方式来确定最优切分特征及该特征的最优切分点。 一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元R1,R2,…,RM，并且在每个单元Rm上有一个固定的输出值cm，于是回归树模型可表示为： 当输入空间的划分确定时，可以用平方误差 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元Rm上的cm的最优值是Rm上的所有输入实例xi对应的输出yi的均值（就是说每个节点的值就是当前这个节点中所有样本的均值），即 问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第j个变量x(j)和它取的值s，作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域： 然后寻找最优切分变量j和最优切分点s。具体地，求解 内部是寻找每一个特征的最优切分点，外面的min是求解所有特征中的最小，这样最小的那个就是最优特征的最优切分点，对固定输入变量j可以找到最优切分点s 遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)。依此将输入空间划分为两个 区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回 归树。这样的回归树通常称为最小二乘回归树（least squares regression tree），现将算法叙述如下： 输入：训练数据集D； 输出：回归树f(x)。 在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子 区域上的输出值，构建二叉决策树： 连续型属性怎么处理？因为决策树要求数据必须是离散的，不能是连续的，所以连续型的属性我们必须离散化处理。 方法一： 首先将连续属性离散化，把连续型的属性的值分为不同的区间，比如年龄可以分为[10,30],[30,50],[50,70],这样年龄就变成了离散值了。 方法二： 由于连续属性的可取值数目不在有限，因此，不能直接根据连续属性的可取值来对节点进行划分。此时，我们可以使用二分法对连续属性进行处理，这正是C4.5决策树算法中采用的机制。 具体来说我们有一个连续的属性，其值为： {0.243，0.245，0.343，0.360，0.403，0.437，0.481，0.556，0.593，0.608，0.634，0.639，0.657，0.666，0.697，0.719，0.774} 我们先来求出每两个值的中心点 {0.244，0.294，0.351，0.381，0.420，0.459，0.518，0.574，0.600，0.621，0.636，0.648，0.661，0.681，0.708，0.746} 也就是我们有上面16个可以切分的点，那么究竟在哪里进行切分呢？ 哪个地方的信息增益最大，我们就在哪个地方进行切分。 实际上应该在0.381上进行切分时最合适，我们来算一下此时的信息增益是多少？ 初始样本的信息熵为：[-8/17log(8/17)]+[-9/17log(9/17)]=0.998 条件熵为：13/17[-5/13log(5/13)-8/13log(8/13)]+4/17[0log0+4/4log4/4]=0.734 所以0.381对应的信息增益：0.998-0.734=0.264 0.264就是此时在0.381作为划分点的信息增益，实际上在0.381位置划分是此特征的最佳的划分位置，然后算出此时的信息增益率就是当前特征的的信息增益率了。 需要注意的是。与离散的属性不同，若当前节点划分属性为连续属性，该属性还可以作为其后代节点的划分属性。例如在父结点上使用了“密度≤0.381”，不会禁止在子节点上使用“密度”≤0.294 个人认为之所以还可以继续使用连续属性是因为，我们如果只是简单的通过一个条件（0.381）把连续属性分成两瓣，那么会有很大的一部分并不满足这样的划分，所以我们应该可以继续使用连续属性，再次的进行划分，这样就会划分的很细，让大多数样本满足划分。 多变量决策树若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对 应d为空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。 如果我们要生成下面这样的决策树： 对应的分类边界为： 显然，分类边界的每一段都是与坐标轴平行的，这样的分类使得学习结果有较好的可解释性， 因为每一段划分都直接对应了某个属性取值。但在学习任务的真是分类边界比较复杂，必须使用很多段划分才能获得较好的近似，如下图： 此时决策树会非常复杂，由于要进行大量的测试属性，测试时间开销会很大。 若能使用斜的划分边界，如上图的红线所示，则决策树模型将大为简化，“多 变量决策树”就能实现这样的“斜划分”甚至更加复杂划分的决策树。 在实现这类决策树时，非叶 节点不仅仅是对某个属性， 而是对属性的线性组合进行 测试。于是，与传统的“单 变量决策树”不同，在多变 量决策树的学习过程中，不 是为每个非叶节点寻找一个 最优划分属性，而是试图建 立一个合适的线性分类器。 该图对应的分类边界如图： 衡量决策树的效果现在我们已经知道了如何选择节点，那就意味着我们建立一个决策树已经是非常简单了，那么我们建立一颗决策树之后，如何评价这个决策树好坏呢？ 这里我们引进了一个评价函数，对所有的叶子节点的熵进行加权求和，它就类似于损失函数，也就是说它越小越好. 评价函数 我们来思考一下叶子结点，它表示的是什么意思，他表示从根节点到叶子结点所有符合决策的样本，所以它是一个集合，而Nt表示这个叶子节点集合中的样本数，比如叶子节点中的样本为[1,1,1,2]则表示这个叶子节点中有四个样本，H（t）表示这个叶子结点的熵。 决策树构造的基本思想是：随着树深度的增加，节点的熵迅速降低。熵降低的速度越快越好，这样我们有望得到一颗高度最矮的一颗决策树 如果决策树太高，说明有大量的分支，最终叶子节点会很纯，那么就会导致过拟合，为了防止过拟合，应将上面的损失函数进行改变，改变为 这就是在原有的损失函数上面加上了a乘以T，这个T表示叶子节点的个数，决策树深度越大那么叶子节点的个数就会越多，那么这个公式就将逼迫着决策树矮一点。因为越矮叶子节点越少，那么损失也就越少。a越大说明叶子节点个数对这个式子影响很大，a小说明叶子节点对这个式子影响小，我们可以多加一点叶子节点，就是深度可以大一些。 C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T| 表示模型复杂度，参数a≥0控制两者之间的影响。较大的a促使选择较简单的模型（树低，叶子节点少)， 较小的a促使选择较复杂的模型（树高，叶子节点多）。a＝0意味着只考虑模型与训练数据的拟合程度， 不考虑模型的复杂度。 剪枝，就是当a确定时，选择损失函数最小的模型，即损失函数最小的子树。当a值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示了对两者的平衡。 可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行 更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。 为了让树变矮，叶子节点变少，我们构造决策树的时候有两种方式：预剪枝和后剪枝，树的剪枝就是为了挑出完整树的子树 我们如何判断是否要剪枝呢？两种方式，方式一，确定一个验证集，根据验证集的准确度以此来确定是否需要进行剪枝。方式二，根据评价函数来确定是否是需要进行剪枝地操作，如果要是剪枝之后地评价函数比剪枝之后地评价函数低地话，那么我们就可以进行剪枝。 预剪枝：在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶子节点。 实际开发中可以设置决策树的深度，建造决策树的过程中只要达到决策树的深度的时候就停止建造决策树，还可以判断当前节点的样本数量，假如我们设置阈值为50，也就是说只要样本个数小于50就不用再往下构造了，具体可以看代码。 后剪枝：后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上的对非叶子节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。 后剪枝第一种方法：固定某个经验值a，从非叶子节点开始，计算未剪枝验证准确度以及剪枝后地准确度，如果两者地准确度是相等或者剪枝后准确度更高，当然剪掉是更好地，但是如果剪掉后地准确度低了，那就不要剪了。剪枝后原内部节点会变成新地叶节点，其决策类别由多数表决法决定，不断重复这个过程网上进行剪枝，直到准确度最好为止。这个是通过使用验证集地方式来验证地，我们还可以损失函数地角度来判断是剪枝还是不要剪枝。 后剪枝第二种方法：通过迭代操作，构造一系列不同的a值，选择几颗评价函数相同的树，然后通过交叉验证的方法选择最好的树。 具体来说就是从完整地树开始，当a为的时候，明显完整的树就是最优树，即第一个备选树，评价函数值就是C(T0) 现在裁剪一个r非叶子节点，其它部分不动，因此我们可以独立考察r节点构成的单节点（去掉r节点的所有分支，只要一个r节点）和以r节点为根节点的树这二者的评价函数的变化。 第一个式子是单个节点时的评价函数，此时T为1，第二个式子是以节点为根节点子树时的评价函数，初始a很小，当a很小的时候，Ca（Tr）<Ca(tr),因为分支的纯度会高，可以慢慢增加a，使得不等式变成等式，此时这个a就是我们所需要计算的那个a。 我们要循环遍历所有的节点的a值，然后选出最小的那个a值的节点，我们就把这个节点下的分支砍掉，然后这个分支作为一个叶子节点存在，又得到一棵备选树 在这棵树的基础上继续执行这个步骤，然后再次选出最小的a的那个节点，然后砍掉，又得到一棵备选树，如此往复最后砍到只剩下一个根节点，最终形成一系列决策树，然后通过验证集来验证里面最好的那一棵，或者选择损失函数最小的那一棵。 |
|
|
