决策树系列.docx

决策树系列（一）——基础知识回顾与总结 1.决策树的定义       树想必大家都会比较熟悉，是由节点和边两种元素组成的结构。理解树，就需要理解几个关键词：根节点、父节点、子节点和叶子节点。       父节点和子节点是相对的，说白了子节点由父节点根据某一规则分裂而来，然后子节点作为新的父亲节点继续分裂，直至不能分裂为止。而根节点是没有父节点的节点，即初始分裂节点，叶子节点是没有子节点的节点，如下图所示：   图1.1 树的结构示意图      决策树利用如上图所示的树结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论。从跟节点开始，经过多次判断得出结论。 2. 决策树如何做决策 从一个分类例子说起：       银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型。 表2.1 银行用户信息表 职业 年龄 收入 学历 是否贷款 自由职业 28 5000 高中 是 工人 36 5500 高中 否 工人 42 2800 初中 是 白领 45 3300 小学 是 白领 25 10000 本科 是 白领 32 8000 硕士 否 白领 28 13000 博士 是 自由职业 21 4000 本科 否 自由职业 22 3200 小学 否 工人 33 3000 高中 否 工人 48 4200 小学 否 （注：上表中的数据都由本人捏造，不具有任何实际的意义）       上边中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够“肯定地”判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止。 　　决策树用树结构实现上述的判断流程，如图2.1所示： 图2.1 银行贷款意向分析决策树示意图      通过图2.1的训练数据，我们可以建议图2.1所示的决策树，其输入是用户的信息，输出是用户的贷款意向。如果要判断某一客户是否有贷款的意向，直接根据用户的职业、收入、年龄以及学历就可以分析得出用户的类型。如某客户的信息为：{职业、年龄，收入，学历}={工人、39， 1800，小学}，将信息输入上述决策树，可以得到下列的分析步骤和结论。 第一步：根据该客户的职业进行判断，选择“工人”分支；   第二步：根据客户的年龄进行选择，选择年龄”<=40”这一分支；   第三步：根据客户的学历进行选择，选择”小学”这一分支，得出该客户无贷款意向的结论。     3. 决策树的构建      那么问题就来了，如何构建如图2.1所示一棵决策树呢？决策树的构建是数据逐步分裂的过程，构建的步骤如下: 步骤1：将所有的数据看成是一个节点，进入步骤2； 步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3； 步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2； 步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。         从上述步骤可以看出，决策生成过程中有两个重要的问题： （1）数据如何分割 （2）如何选择分裂的属性 （3）什么时候停止分裂 3.1 数据分割       假如我们已经选择了一个分裂的属性，那怎样对数据进行分裂呢？ 　　分裂属性的数据类型分为离散型和连续性两种情况，对于离散型的数据，按照属性值进行分裂，每个属性值对应一个分裂节点；对于连续性属性，一般性的做法是对数据按照该属性进行排序，再将数据分成若干区间，如[0,10]、[10,20]、[20,30]…，一个区间对应一个节点，若数据的属性值落入某一区间则该数据就属于其对应的节点。 例： 表3.1  分类信息表 职业 年龄 是否贷款 白领 30 否 工人 40 否 工人 20 否 学生 15 否 学生 18 是 白领 42 是 （1）属性1“职业”是离散型变量，有三个取值，分别为白领、工人和学生，根据三个取值对原始的数据进行分割，如下表所示: 表3.2  属性1数据分割表 取值 贷款 不贷款 白领 1 1 工人 0 2 学生 1 1 表3.2可以表示成如下的决策树结构：   （2）属性2是连续性变量，这里将数据分成三个区间，分别是[10，20]、[20,30]、[30,40]，则每一个区间的分裂结果如下： 表3.3 属性2数据分割表 区间 贷款 不贷款 [0,20] 1 2 (20,40] 0 2 (40,—] 1 0 表3.3可以表示成如下的决策树结构：   3.2 分裂属性的选择       我们知道了分裂属性是如何对数据进行分割的，那么我们怎样选择分裂的属性呢？ 　　决策树采用贪婪思想进行分裂，即选择可以得到最优分裂结果的属性进行分裂。那么怎样才算是最优的分裂结果？最理想的情况当然是能找到一个属性刚好能够将不同类别分开，但是大多数情况下分裂很难一步到位，我们希望每一次分裂之后孩子节点的数据尽量”纯”，以下图为例：      从图3.1和图3.2可以明显看出，属性2分裂后的孩子节点比属性1分裂后的孩子节点更纯：属性1分裂后每个节点的两类的数量还是相同，跟根节点的分类结果相比完全没有提高；按照属性2分裂后每个节点各类的数量相差比较大，可以很大概率认为第一个孩子节点的输出结果为类1，第2个孩子节点的输出结果为2。       选择分裂属性是要找出能够使所有孩子节点数据最纯的属性，决策树使用信息增益或者信息增益率作为选择属性的依据。 （1）信息增益       用信息增益表示分裂前后跟的数据复杂度和分裂节点数据复杂度的变化值，计算公式表示为：       其中Gain表示节点的复杂度，Gain越高，说明复杂度越高。信息增益说白了就是分裂前的数据复杂度减去孩子节点的数据复杂度的和，信息增益越大，分裂后的复杂度减小得越多，分类的效果越明显。 节点的复杂度可以用以下两种不同的计算方式： 　　a）熵 　　熵描述了数据的混乱程度，熵越大，混乱程度越高，也就是纯度越低；反之，熵越小，混乱程度越低，纯度越高。 熵的计算公式如下所示： 其中Pi表示类i的数量占比。以二分类问题为例，如果两类的数量相同，此时分类节点的纯度最低，熵等于1；如果节点的数据属于同一类时，此时节点的纯度最高，熵 等于0。 　　b）基尼值 　　基尼值计算公式如下： 　　其中Pi表示类i的数量占比。其同样以上述熵的二分类例子为例，当两类数量相等时，基尼值等于0.5 ；当节点数据属于同一类时，基尼值等于0 。基尼值越大，数据越不纯。   　　例： 　　以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。          属性1：   属性2：   由于  ，所以属性1与属性2相比是更优的分裂属性，故选择属性1作为分裂的属性。 （2）信息增益率       使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益（听起来很拗口），其计算公式如下：       其中 表示信息增益， 表示分裂子节点数据量的信息增益，其计算公式为： 其中m表示子节点的数量，表示第i个子节点的数据量，N表示父节点数据量，说白了， 其实是分裂节点的熵，如果节点的数据链越接近，越大，如果子节点越大，越大，而就会越小，能够降低节点分裂时选择子节点多的分裂属性的倾向性。信息增益率越高，说明分裂的效果越好。        还是信息增益中提及的例子为例： 属性1的信息增益率：   属性2的信息增益率：            由于 ，故选择属性2作为分裂的属性。 3.3 停止分裂的条件 　　决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高。一般情况下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂。 　　以下是决策树节点停止分裂的一般性条件： 　　（1）最小节点数 　　当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。 　　（2）熵或者基尼值小于阀值。      由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。 　　（3）决策树的深度达到指定的条件 　  节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。 　　（4）所有特征已经使用完毕，不能继续进行分裂。      被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。 3.4 决策树的构建方法       根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为具体的类别，而回归树输出的结果为一个确定的数值。 　　决策树的构建算法主要有ID3、C4.5、CART三种，其中ID3和C4.5是分类树，CART是分类回归树，将在本系列的ID3、C4.5和CART中分别讲述。 　　其中ID3是决策树最基本的构建算法，而C4.5和CART是在ID3的基础上进行优化的算法。 4. 决策树的优化      一棵过于复杂的决策树很可能出现过拟合的情况，如果完全按照3中生成一个完整的决策树可能会出现预测不准确的情况，因此需要对决策树进行优化，优化的方法主要有两种，一是剪枝，二是组合树，将在本系列的剪枝和组合树中分别讲述。 决策树系列（二）——剪枝 什么是剪枝？       剪枝是指将一颗子树的子节点全部删掉，根节点作为叶子节点，以下图为例：     为甚么要剪枝？       决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高。       考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都”准确划分”了，强化了噪声数据的作用。       剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率。   怎样剪枝？ 两种方案：先剪枝和后剪枝       先剪枝说白了就是提前结束决策树的增长，跟上述决策树停止生长的方法一样。       后剪枝是指在决策树生长完成之后再进行剪枝的过程。这里介绍三种后剪枝方案： （1）REP—错误率降低剪枝               顾名思义，该剪枝方法是根据错误率进行剪枝，如果一棵子树修剪前后错误率没有下降，就可以认为该子树是可以修剪的。       REP剪枝需要用新的数据集，原因是如果用旧的数据集，不可能出现分裂后的错误率比分裂前错误率要高的情况。由于使用新的数据集没有参与决策树的构建，能够降低训练数据的影响，降低过拟合的程度，提高预测的准确率。 （2）PEP—悲观剪枝       悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与剪枝前的效果一致，此时要进行剪枝。       进行剪枝必须满足的条件： 其中：     表示剪枝前子树的误差；    表示剪枝后节点的误差； 两者的计算公式如下：       令子树误差的经度满足二项分布，根据二项分布的性质， ， ，其中 ，N为子树的数据量；同样，叶子节点的误差。       上述公式中，0.5表示修正因子。由于子节点是父节点进行分裂的结果，从理论上讲，子节点的分类效果总比父节点好，分类的误差更小，如果单纯通过比较子节点和父节点的误差进行剪枝就完全没有意义了，因此对节点的误差计算方法进行修正。修正的方法是给每一个节点都加上误差修正因子0.5，在计算误差的时候，子节点由于加上了误差修正因子，就无法保证总误差低于父节点。 算例：                 由于 ，所以应该进行剪枝。 （3）CCP—代价复杂度剪枝       代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。 可描述如下：       令决策树的非叶子节点为。       a） 计算所有非叶子节点的表面误差率增益值         b）选择表面误差率增益值最小的非叶子节点（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）。       c）对选中的非叶子节点进行剪枝 表面误差率增益值的计算公式：   其中： 表示叶子节点的误差代价， ， 为节点的错误率， 为节点数据量的占比； 表示子树的误差代价，， 为子节点i的错误率，  表示节点i的数据节点占比； 表示子树节点个数。 算例： 下图是决策树A的其中一颗子树，决策树的总数据量为40。   该子树的表面误差率增益值可以计算如下：   求出该子树的表面错误覆盖率为 1/40，只要求出其他子树的表面误差率增益值就可以对决策树进行剪枝. 决策树系列（三）——ID3 初识ID3       回顾决策树的基本知识，其构建过程主要有下述三个重要的问题：      （1）数据是怎么分裂的      （2）如何选择分类的属性      （3）什么时候停止分裂      从上述三个问题出发，以实际的例子对ID3算法进行阐述。 例：通过当天的天气、温度、湿度和季节预测明天的天气 表1 原始数据 当天天气 温度 湿度 季节 明天天气 晴 25 50 春天 晴 阴 21 48 春天 阴 阴 18 70 春天 雨 晴 28 41 夏天 晴 雨 8 65 冬天 阴 晴 18 43 夏天 晴 阴 24 56 秋天 晴 雨 18 76 秋天 阴 雨 31 61 夏天 晴 阴 6 43 冬天 雨 晴 15 55 秋天 阴 雨 4 58 冬天 雨  1.数据分割       对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点，以“当前天气”为例对数据进行分割，如图1所示。         对于连续型数据，ID3原本是没有处理能力的，只有通过离散化将连续性数据转化成离散型数据再进行处理。       连续数据离散化是另外一个课题，本文不深入阐述，这里直接采用等距离数据划分的李算话方法。该方法先对数据进行排序，然后将连续型数据划分为多个区间，并使每一个区间的数据量基本相同，以温度为例对数据进行分割，如图2所示。    2. 选择最优分裂属性       ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准，信息增益的计算公式如下：       其中， 表示父节点的熵； 表示节点i的熵，熵越大，节点的信息量越多，越不纯； 表示子节点i的数据量与父节点数据量之比。 越大，表示分裂后的熵越小，子节点变得越纯，分类的效果越好，因此选择 最大的属性作为分裂属性。       对上述的例子的跟节点进行分裂，分别计算每一个属性的信息增益，选择信息增益最大的属性进行分裂。       天气属性：（数据分割如上图1所示）  　　       温度：（数据分割如上图2所示）             湿度：                季节：               由于最大，所以选择属性“季节”作为根节点的分裂属性。   3.停止分裂的条件      停止分裂的条件已经在决策树中阐述，这里不再进行阐述。      （1）最小节点数 　　当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。 　　（2）熵或者基尼值小于阀值。      由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度时，节点停止分裂。 　　（3）决策树的深度达到指定的条件 　  节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。 　　（4）所有特征已经使用完毕，不能继续进行分裂。      被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。   （1）数据处理        用二维数组存储原始的数据，每一行表示一条记录，前n-1列表示数据的属性，第n列表示分类的标签。 　　 为了方便后面的处理，对离散属性进行数字化处理，将离散值表示成数字，并用一个链表数组进行存储，数组的第一个元素表示属性1的离散值。 　　 static List<String>[] featureValues;        那么经过处理后的表1数据可以转化为如表2所示的数据： 表2 初始化后的数据 当天天气 温度 湿度 季节 明天天气 1 25 50 1 1 2 21 48 1 2 2 18 70 1 3 1 28 41 2 1 3 8 65 3 2 1 18 43 2 1 2 24 56 4 1 3 18 76 4 2 3 31 61 2 1 2 6 43 3 3 1 15 55 4 2 3 4 58 3 3       其中，对于当天天气属性，数字{1，2，3}分别表示{晴，阴，雨}；对于季节属性{1，2，3，4}分别表示{春天、夏天、冬天、秋天}；对于明天天气{1，2，3}分别表示{晴、阴、雨}。 （2）两个类：节点类和分裂信息 　　a）节点类Node       该类存储了节点的信息，包括节点的数据量、节点选择的分裂属性、节点输出类、子节点的个数、子节点的分类误差等。  View Code 　　b）分裂信息类SplitInfo       该类存储节点进行分裂的信息，包括各个子节点的行坐标、子节点各个类的数目、该节点分裂的属性、属性的类型等。  View Code （3）节点分裂方法findBestSplit(Node node,List<int> nums,int[] isUsed)，该方法对节点进行分裂，返回值Node 其中：     node表示即将进行分裂的节点；     nums表示节点数据对应的行坐标列表；     isUsed表示到该节点位置所有属性的使用情况（1：表示该属性不能再次使用，0：表示该属性可以使用）； findBestSplit主要有以下几个组成部分： 1）节点分裂停止的判定 判断节点是否需要继续分裂，分裂判断条件如上文所述。源代码如下： 2）寻找最优的分裂属性 寻找最优的分裂属性需要计算每一个分裂属性分裂后的信息增益，计算公式上文已给出. 3）进行分裂，同时子节点也执行相同的分类步骤 其实就是递归的过程，对每一个子节点执行findBestSplit方法进行分裂。  （注：上述代码只是ID3的核心代码，数据预处理的代码并没有给出，只要将预处理后的数据输入到主方法findBestSplit中，就可以得到最终的结果） 总结      ID3是基本的决策树构建算法，作为决策树经典的构建算法，其具有结构简单、清晰易懂的特点。虽然ID3比较灵活方便，但是有以下几个缺点： 　（1）采用信息增益进行分裂，分裂的精确度可能没有采用信息增益率进行分裂高    （2）不能处理连续型数据，只能通过离散化将连续性数据转化为离散型数据    （3）不能处理缺省值    （4）没有对决策树进行剪枝处理，很可能会出现过拟合的问题 决策树系列（四）——C4.5       如上一篇文章所述，ID3方法主要有几个缺点：一是采用信息增益进行数据分裂，准确性不如信息增益率；二是不能对连续数据进行处理，只能通过连续数据离散化进行处理；三是没有采用剪枝的策略，决策树的结构可能会过于复杂，可能会出现过拟合的情况。       C4.5在ID3的基础上对上述三个方面进行了相应的改进：       a）  C4.5对节点进行分裂时采用信息增益率作为分裂的依据；       b）  能够对连续数据进行处理；       c）  C4.5采用剪枝的策略，对完全生长的决策树进行剪枝处理，一定程度上降低过拟合的影响。 1.采用信息增益率作为分裂的依据      信息增益率的计算公式为：       其中表示信息增益，表示分裂子节点数据量的信息增益，计算公式为：       其中m表示节点的数量，Ni表示第i个节点的数据量，N表示父亲节点的数据量，说白了，其实是分裂节点的熵。 信息增益率越大，说明分裂的效果越好。       以一个实际的例子说明C4.5如何通过信息增益率选择分裂的属性： 表1 原始数据表 当天天气 温度 湿度 日期 逛街 晴 25 50 工作日 否 晴 21 48 工作日 是 晴 18 70 周末 是 晴 28 41 周末 是 阴 8 65 工作日 是 阴 18 43 工作日 否 阴 24 56 周末 是 阴 18 76 周末 否 雨 31 61 周末 否 雨 6 43 周末 是 雨 15 55 工作日 否 雨 4 58 工作日 否      以当天天气为例：      一共有三个属性值，晴、阴、雨，一共分裂成三个子节点。       根据上述公式，可以计算信息增益率如下： 所以使用天气属性进行分裂可以得到信息增益率0.44。 2.对连续型属性进行处理       C4.5处理离散型属性的方式与ID3一致，新增对连续型属性的处理。处理方式是先根据连续型属性进行排序，然后采用一刀切的方式将数据砍成两半。 那么如何选择切割点呢？很简单，直接计算每一个切割点切割后的信息增益，然后选择使分裂效果最优的切割点。以温度为例：         从上图可以看出，理论上来讲，N条数据就有N-1个切割点，为了选取最优的切割垫，要计算按每一次切割的信息增益，计算量是比较大的，那么有没有简化的方法呢？有，注意到，其实有些切割点是很明显可以排除的。比如说上图右侧的第2条和第3条记录，两者的类标签（逛街）都是“是”，如果从这里切割的话，就将两个本来相同的类分开了，肯定不会比将他们归为一类的切分方法好，因此，可以通过去除前后两个类标签相同的切割点以简化计算的复杂度，如下图所示：         从图中可以看出，最终切割点的数目从原来的11个减少到现在的6个，降低了计算的复杂度。       确定了分割点之后，接下来就是选择最优的分割点了，注意，对连续型属性是采用信息增益进行内部择优的，因为如果使用信息增益率进行分裂会出现倾向于选择分割前后两个节点数据量相差最大的分割点，为了避免这种情况，选择信息增益选择分割点。选择了最优的分割点之后，再计算信息增益率跟其他的属性进行比较，确定最优的分裂属性。 3. 剪枝       决策树只已经提到，剪枝是在完全生长的决策树的基础上，对生长后分类效果不佳的子树进行修剪，减小决策树的复杂度，降低过拟合的影响。       C4.5采用悲观剪枝方法（PEP）。悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与更佳，此时需要子树进行剪枝操作。 进行剪枝必须满足的条件： 其中：  表示子树的误差；  表示叶子节点的误差；        令子树误差的经度满足二项分布，根据二项分布的性质，，，其中，N为子树的数据量；同样，叶子节点的误差。       上述公式中，0.5表示修正因子。由于对父节点进行分裂总会得到比父节点分类结果更好的效果，因此，因此从理论上来说，父节点的误差总是不小于孩子节点的误差，因此需要进行修正，给每一个节点都加上0.5的修正因此，在计算误差的时候，子节点由于加上了修正的因子，就无法保证总误差总是低于父节点。 算例：   由于，所以应该进行剪枝。 程序设计及源代码（C#版） 程序的设计过程 （1）数据格式          对原始的数据进行数字化处理，并以二维数据的形式存储，每一行表示一条记录，前n-1列表示属性，最后一列表示分类的标签。          如表1的数据可以转化为表2： 表2 初始化后的数据 当天天气 温度 湿度 季节 明天天气 1 25 50 1 1 2 21 48 1 2 2 18 70 1 3 1 28 41 2 1 3 8 65 3 2 1 18 43 2 1 2 24 56 4 1 3 18 76 4 2 3 31 61 2 1 2 6 43 3 3 1 15 55 4 2 3 4 58 3 3          其中，对于“当天天气”属性，数字{1，2，3}分别表示{晴，阴，雨}；对于“季节”属性{1，2，3，4}分别表示{春天、夏天、冬天、秋天}；对于类标签“明天天气”，数字{1，2，3}分别表示{晴、阴、雨}。 代码如下所示：          static double[][] allData;                              //存储进行训练的数据 　　　 static List<String>[] featureValues;                    //离散属性对应的离散值 featureValues是链表数组，数组的长度为属性的个数，数组的每个元素为该属性的离散值链表。 （2）两个类：节点类和分裂信息 a）节点类Node 该类表示一个节点，属性包括节点选择的分裂属性、节点的输出类、孩子节点、深度等。注意，与ID3中相比，新增了两个属性：leafWrong和leafNode_Count分别表示叶子节点的总分类误差和叶子节点的个数，主要是为了方便剪枝。 b）分裂信息类，该类存储节点进行分裂的信息，包括各个子节点的行坐标、子节点各个类的数目、该节点分裂的属性、属性的类型等。 主方法findBestSplit(Node node,List<int> nums,int[] isUsed)，该方法对节点进行分裂 其中： node表示即将进行分裂的节点； nums表示节点数据的行坐标列表； isUsed表示到该节点位置所有属性的使用情况； findBestSplit的这个方法主要有以下几个组成部分： 1）节点分裂停止的判定 节点分裂条件如上文所述，源代码如下： 2）寻找最优的分裂属性 寻找最优的分裂属性需要计算每一个分裂属性分裂后的信息增益率，计算公式上文已给出，其中熵的计算代码如下： 3）进行分裂，同时对子节点进行迭代处理 其实就是递归的工程，对每一个子节点执行findBestSplit方法进行分裂。 findBestSplit源代码： （4）剪枝 悲观剪枝方法（PEP）：   总结：       要记住，C4.5是分类树最终要的算法，算法的思想其实很简单，但是分类的准确性高。可以说C4.5是ID3的升级版和强化版，解决了ID3未能解决的问题。要重点记住以下几个方面：       1.C4.5是采用信息增益率选择分裂的属性，解决了ID3选择属性时的偏向性问题；       2.C4.5能够对连续数据进行处理，采用一刀切的方式将连续型的数据切成两份，在选择切割点的时候使用信息增益作为择优的条件；       3.C4.5采用悲观剪枝的策略，一定程度上降低了过拟合的影响。   决策树系列（五）——CART CART，又名分类回归树，是在ID3的基础上进行优化的决策树，学习CART记住以下几个关键点： （1）CART既能是分类树，又能是分类树； （2）当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据； （3）CART是一棵二叉树。 接下来将以一个实际的例子对CART进行介绍： 表1 原始数据表 看电视时间 婚姻情况 职业 年龄 3 未婚 学生 12 4 未婚 学生 18 2 已婚 老师 26 5 已婚 上班族 47 2.5 已婚 上班族 36 3.5 未婚 老师 29 4 已婚 学生 21 从以下的思路理解CART： 分类树？回归树？       分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。       CART既能是分类树，又能是决策树，如上表所示，如果我们想预测一个人是否已婚，那么构建的CART将是分类树；如果想预测一个人的年龄，那么构建的将是回归树。 分类树和回归树是怎么做决策的？假设我们构建了两棵决策树分别预测用户是否已婚和实际的年龄，如图1和图2所示：                         　　　　　　　　　　　　　　图1 预测婚姻情况决策树                                               图2 预测年龄的决策树        图1表示一棵分类树，其叶子节点的输出结果为一个实际的类别，在这个例子里是婚姻的情况（已婚或者未婚），选择叶子节点中数量占比最大的类别作为输出的类别；        图2是一棵回归树，预测用户的实际年龄，是一个具体的输出值。怎样得到这个输出值？一般情况下选择使用中值、平均值或者众数进行表示，图2使用节点年龄数据的平均值作为输出值。 CART如何选择分裂的属性？       分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。 GINI值的计算公式：       节点越不纯，GINI值越大。以二分类为例，如果节点的所有数据只有一个类别，则 ，如果两类数量相同，则 。 回归方差计算公式： 方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。       因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案。即最小化（分类树）： 或者（回归树）： CART如何分裂成一棵二叉树？      节点的分裂分为两种情况，连续型的数据和离散型的数据。      CART对连续型属性的处理与C4.5差不多，通过最小化分裂后的GINI值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看C4.5。      对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。      以属性“职业”为例，一共有三个离散值，“学生”、“老师”、“上班族”。该属性有三种划分的方案，分别为{“学生”}、{“老师”、“上班族”}，{“老师”}、{“学生”、“上班族”}，{“上班族”}、{“学生”、“老师”}，分别计算三种划分方案的子节点GINI值或者样本方差，选择最优的划分方法，如下图所示： 第一种划分方法：{“学生”}、{“老师”、“上班族”} 预测是否已婚（分类）：                      预测年龄（回归）：        　　　　    第二种划分方法：{“老师”}、{“学生”、“上班族”}   预测是否已婚（分类）：                      预测年龄（回归）：       　　　　   第三种划分方法：{“上班族”}、{“学生”、“老师”}  预测是否已婚（分类）：                      预测年龄（回归）：         　　　　 综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，则选择{“老师”}、{“学生”、“上班族”}的划分方法。   如何剪枝？       CART采用CCP（代价复杂度）剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。 可描述如下： 令决策树的非叶子节点为。 a）计算所有非叶子节点的表面误差率增益值  b）选择表面误差率增益值最小的非叶子节点（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）。 c）对进行剪枝 表面误差率增益值的计算公式： 其中： 表示叶子节点的误差代价， ， 为节点的错误率， 为节点数据量的占比； 表示子树的误差代价， ， 为子节点i的错误率， 表示节点i的数据节点占比； 表示子树节点个数。 算例： 下图是其中一颗子树，设决策树的总数据量为40。 该子树的表面误差率增益值可以计算如下：   求出该子树的表面错误覆盖率为 ，只要求出其他子树的表面误差率增益值就可以对决策树进行剪枝。   程序实际以