人群决策树算法

① 决策树CART算法优点和缺点

CART的全称是分类和回归树，既可以做分类算法，也可以做回归。
决策树的优缺点：
优点：

1.可以生成可以理解的规则。
2.计算量相对来说不是很大。
3.可以处理连续和种类字段。
4.决策树可以清晰的显示哪些字段比较重要
缺点：

1. 对连续性的字段比较难预测。
2.对有时间顺序的数据，需要很多预处理的工作。
3.当类别太多时，错误可能就会增加的比较快。
4.一般的算法分类的时候，只是根据一个字段来分类。

② 决策树计算公式

决策树计算公式公式：H(X)=–∑P(x)log[P(x)]H(x)：表示熵 P(x)：表示x事件发生的概率。

决策树法的具体计算过程：

①绘制决策树图形，按上述要求由左向右顺序展开。

②计算每个结点的期望值，计算公式为：

状态结点的期望值=Σ（损益值×概率值）×经营年限

③剪枝，即进行方案的选优。

方案净效果=该方案状态结点的期望值-该方案投资额

③ 决策树方法的基本思想是什么

决策树的基本思想
决策树算法是最早的机器学习算法之一。
算法框架
1.决策树主函数
各种决策树的主函数都大同小异，本质上是一个递归函数。该函数的主要功能是按照某种规则生长出决策树的各个分支节点，并根据终止条件结束算法。一般来讲，主函数需要完成如下几个功能。
（1）输入需要分类的数据集和类别标签
（2）根据某种分类规则得到最优的划分特征，并创建特征的划分节点--计算最优特征子函数
（3）按照该特征的每个取值划分数据集为若干部分--划分数据集子函数
（4）根据划分子函数的计算结果构建出新的节点，作为树生长出的新分支
（5）检验是否符合递归的终止条件
（6）将划分的新节点包含的数据集和类别标签作为输入，递归执行上述步骤。
2.计算最优特征子函数
计算最优特征子函数是除主函数外最重要的函数。每种决策树之所以不同，一般都是因为最优特征选择的标准上有所差异，不同的标准导致不同类型的决策树。如：ID3的最优特征选择标准是信息增益、C4.5是信息增益率、CART是节点方差的大小等。
在算法逻辑上，一般选择最优特征需要遍历整个数据集，评估每个特征，找到最优的那一个特征返回。
3.划分数据集函数
划分数据集函数的主要功能是分隔数据集，有的需要删除某个特征轴所在的数据列，返回剩余的数据集；有的干脆将数据集一分为二。
4.分类器
所有的机器学习算法都要勇于分类或回归预测。决策树的分类器就是通过遍历整个决策树，使测试集数据找到决策树中叶子节点对应的类别标签。这个标签就是返回的结果。

④ 决策树的原理及算法

决策树基本上就是把我们以前的经验总结出来。我给你准备了一个打篮球的训练集。如果我们要出门打篮球，一般会根据“天气”、“温度”、“湿度”、“刮风”这几个条件来判断，最后得到结果：去打篮球？还是不去？

上面这个图就是一棵典型的决策树。我们在做决策树的时候，会经历两个阶段：构造和剪枝。

构造就是生成一棵完整的决策树。简单来说，构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
叶节点：就是树最底部的节点，也就是决策结果。

剪枝就是给决策树瘦身，防止过拟合。分为“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Pruning）。

预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。

后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。

1是欠拟合，3是过拟合，都会导致分类错误。

造成过拟合的原因之一就是因为训练集中样本量较小。如果决策树选择的属性过多，构造出来的决策树一定能够“完美”地把训练集中的样本分类，但是这样就会把训练集中一些数据的特点当成所有数据的特点，但这个特点不一定是全部数据的特点，这就使得这个决策树在真实的数据分类中出现错误，也就是模型的“泛化能力”差。

p(i|t) 代表了节点 t 为分类 i 的概率，其中 log2 为取以 2 为底的对数。这里我们不是来介绍公式的，而是说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。

公式中 D 是父亲节点，Di 是子节点，Gain(D,a) 中的 a 作为 D 节点的属性选择。

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，C4.5 选择具有最高信息增益的划分所对应的阈值。

针对数据集不完整的情况，C4.5 也可以进行处理。

暂无

请你用下面的例子来模拟下决策树的流程，假设好苹果的数据如下，请用 ID3 算法来给出好苹果的决策树。

“红”的信息增益为：1“大”的信息增益为：0
因此选择“红”的作为根节点，“大”没有用，剪枝。

数据分析实战45讲.17 丨决策树（上）：要不要去打篮球？决策树来告诉你

⑤ 决策树原理及算法比较

决策树是什么？

    和线性回归一样是一种模型，内部节点和叶节点。实现分类，内部节点和叶节点通过有向线（分类规      则）连接起来

决策树的目标是什么？

    决策树通过对数据复杂度的计算，建立特征分类标准，确定最佳分类特征。

    表现为“熵”（entropy）和信息增益（information gain），基于决策树思想的三种算法：ID3，C4.5,CART算法，三种算法的信息衡量的指标也不同.

    熵来表示信息的复杂度，熵越大，信息也就越复杂，公式如下：

那些算法能够实现决策树？

    在决策树构建过程中，什么是比较重要的。特征选择（按照熵变计算），算法产生最重要的部分，

决策树中叶节点的分类比较纯，

节点顺序的排列规则：

熵变：

数据的预处理：

改进思路一般有两个1，换算法；2，调参数

做好数据的预处理：

1，做好特征选择；

2，做好数据离散化、异常值处理、缺失填充

分类器：

在决策树中，从根到达任意一个叶节点的之间最长路径的长度，表示对应的算法排序中最坏情况下的比较次数。这样一个比较算法排序中的最坏情况的比较次数就与其决策树的高度相同，同时如果决策树中每种排列以可达叶子的形式出现，那么关于其决策树高度的下界也就是关于比较排序算法运行时间的下界，

ID3算法存在的缺点：

    1，ID3算法在选择根节点和内部节点分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性

    2，当数据为连续性变量的时候，ID3算法就不是一个合理的算法的模型了

C4.5信息增益比率，

     1，在信息增益的基础上除以split-info，是将信息增益改为信息增益比，以解决取值较多的属性的问题，另外它还可以处理连续型属性，其判别标准是θ，

      2，C4.5算法利用增益/熵值，克服了树生长的过程中，总是‘贪婪’选择变量分类多的进行分类

      3，处理来内需型变量，C4.5的分类树的分支就是两条

衡量指标：

（1）信息增益

基于ID3算法的信息增益对于判定连续型变量的时候病不是最优选择，C4.5算法用了信息增益率这个概念。

分类信息类的定义如下：

这个值表示将训练数据集D划分成对应属性A测试的V个输出v个划分产生的信息，信息增益率定义为：

选择最大信息增益率的属性作为分裂属性

Gini指标，CART

表明样本的“纯净度”。Gini系数避免了信息增益产生的问题，

过拟合问题，非常好的泛化能力，有很好的推广能力

Gini系数的计算：

在分类问题中，假设有k个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：

如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的提哦啊见下，集合D的gini指数的定义为：

Gini指数代表特征A不同分组下的数据集D的不确定性，gini指数越大，样本集合的不确定性也就越大，这一点和熵的概念相类似

决策树原理介绍：

第三步：对于每个属性执行划分：

（1）该属性为离散型变量

记样本中的变量分为m中

穷举m种取值分为两类的划分

对上述所有划分计算GINI系数

（2）该属性为连续型变量

将数据集中从小到大划分

按顺序逐一将两个相临值的均值作为分割点

对上述所有划分计算GINI系数

学历的划分使得顺序的划分有个保证，化为连续型变量处理。

决策树的生成算法分为两个步骤：

预剪枝和后剪枝  CCP（cost and complexity）算法：在树变小和变大的的情况有个判断标准。误差率增益值：α值为误差的变化

决策树的终止条件：

      1，某一个节点的分支所覆盖的样本都是同一类的时候

      2，某一个分支覆盖的样本的个数如果小于一个阈值，那么也可以产生叶子节点，从而终止Tree-Growth

确定叶子结点的类：

      1，第一种方式，叶子结点覆盖的样本都属于同一类

      2， 叶子节点覆盖的样本未必是同一类，所占的大多数，那么该叶子节点的类别就是那个占大多数的类

⑥ 决策树法分为那几个步骤

1、特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中，每个样本的属性可能有很多个，不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征，也就是分类能力较强的特征。在特征选择中通常使用的准则是：信息增益。

2、决策树生成

选择好特征后，就从根节点触发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点使用相同的方式生成新的子节点，直到信息增益很小或者没有特征可以选择为止。

3、决策树剪枝

剪枝的主要目的是对抗“过拟合”，通过主动去掉部分分支来降低过拟合的风险。

【简介】

决策树是一种解决分类问题的算法，决策树算法采用树形结构，使用层层推理来实现最终的分类。

⑦ 决策树之ID3算法及其Python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益
??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。
??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。
??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。
??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。
??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。
??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。
4. ID3算法
??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。
ID3算法流程：
(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。
(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。
(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。
(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。
??A、待分裂节点的所有样本同属于一类。
??B、训练样本集中所有样本均完成分类。
??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。
ID3算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

⑧ 5.10 决策树与ID3算法

https://blog.csdn.net/dorisi_h_n_q/article/details/82787295

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。决策过程是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树的关键步骤是分裂属性。就是在某节点处按某一特征属性的不同划分构造不同的分支，目标是让各个分裂子集尽可能地“纯”。即让一个分裂子集中待分类项属于同一类别。

简而言之，决策树的划分原则就是：将无序的数据变得更加有序

分裂属性分为三种不同的情况 ：

构造决策树的关键性内容是进行属性选择度量，属性选择度量（找一种计算方式来衡量怎么划分更划算）是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

此概念最早起源于物理学，是用来度量一个热力学系统的无序程度。
而在信息学里面，熵是对不确定性的度量。
在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为：

在划分数据集之前之后信息发生的变化称为信息增益。
知道如何计算信息增益，就可计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

条件熵 表示在已知随机变量的条件下随机变量的不确定性，随机变量X给定的条件下随机变量Y的条
件熵(conditional entropy) ，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

根据上面公式，我们假设将训练集D按属性A进行划分，则A对D划分的期望信息为

则信息增益为如下两者的差值

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

步骤：1. 对当前样本集合，计算所有属性的信息增益；

是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。ID3算法是对CLS算法的改进，主要是摒弃了属性选择的随机性。

基于ID3算法的改进，主要包括：使用信息增益比替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择
的另一个标准。
特征对训练数据集的信息增益比定义为其信息增益gR( D,A) 与训练数据集的经验熵g(D,A)之比 ：

gR(D,A) = g(D,A) / H(D)

sklearn的决策树模型就是一个CART树。是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此，CART算法生成的决策树是结构简洁的二叉树。
分类回归树算法(Classification and Regression Trees,简称CART算法)是一种基于二分递归分割技术的算法。该算法是将当前的样本集，分为两个样本子集，这样做就使得每一个非叶子节点最多只有两个分支。因此，使用CART
算法所建立的决策树是一棵二叉树，树的结构简单，与其它决策树算法相比，由该算法生成的决策树模型分类规则较少。

CART分类算法的基本思想是：对训练样本集进行递归划分自变量空间，并依次建立决策树模型，然后采用验证数据的方法进行树枝修剪，从而得到一颗符合要求的决策树分类模型。

CART分类算法和C4.5算法一样既可以处理离散型数据，也可以处理连续型数据。CART分类算法是根据基尼(gini)系
数来选择测试属性，gini系数的值越小，划分效果越好。设样本集合为T，则T的gini系数值可由下式计算：

CART算法优点：除了具有一般决策树的高准确性、高效性、模式简单等特点外，还具有一些自身的特点。
如，CART算法对目标变量和预测变量在概率分布上没有要求，这样就避免了因目标变量与预测变量概率分布的不同造成的结果；CART算法能够处理空缺值，这样就避免了因空缺值造成的偏差；CART算法能够处理孤立的叶子结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响；CART算法使用的是二元分支，能够充分地运用数据集中的全部数据，进而发现全部树的结构；比其它模型更容易理解，从模型中得到的规则能获得非常直观的解释。

CART算法缺点：CART算法是一种大容量样本集挖掘算法，当样本集比较小时不够稳定；要求被选择的属性只能产生两个子结点，当类别过多时，错误可能增加得比较快。

sklearn.tree.DecisionTreeClassifier

1.安装graphviz.msi ， 一路next即可

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

按照好友密度划分的信息增益：

按照是否使用真实头像H划分的信息增益

**所以，按先按好友密度划分的信息增益比按真实头像划分的大。应先按好友密度划分。

⑨ 常见决策树分类算法都有哪些

在机器学习中，有一个体系叫做决策树，决策树能够解决很多问题。在决策树中，也有很多需要我们去学习的算法，要知道，在决策树中，每一个算法都是实用的算法，所以了解决策树中的算法对我们是有很大的帮助的。在这篇文章中我们就给大家介绍一下关于决策树分类的算法，希望能够帮助大家更好地去理解决策树。
1.C4.5算法
C4.5算法就是基于ID3算法的改进，这种算法主要包括的内容就是使用信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进行处理；使用k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性等内容，这种算法是一个十分使用的算法。
2.CLS算法
CLS算法就是最原始的决策树分类算法，基本流程是，从一棵空数出发，不断的从决策表选取属性加入数的生长过程中，直到决策树可以满足分类要求为止。CLS算法存在的主要问题是在新增属性选取时有很大的随机性。
3.ID3算法
ID3算法就是对CLS算法的最大改进是摒弃了属性选择的随机性，利用信息熵的下降速度作为属性选择的度量。ID3是一种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能力强、分类速度快适合大规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗干扰能力差。
3.1.ID3算法的优缺点
ID3算法的优点就是方法简单、计算量小、理论清晰、学习能力较强、比较适用于处理规模较大的学习问题。缺点就是倾向于选择那些属性取值比较多的属性，在实际的应用中往往取值比较多的属性对分类没有太大价值、不能对连续属性进行处理、对噪声数据比较敏感、需计算每一个属性的信息增益值、计算代价较高。
3.2.ID3算法的核心思想
根据样本子集属性取值的信息增益值的大小来选择决策属性，并根据该属性的不同取值生成决策树的分支，再对子集进行递归调用该方法，当所有子集的数据都只包含于同一个类别时结束。最后，根据生成的决策树模型，对新的、未知类别的数据对象进行分类。
在这篇文章中我们给大家介绍了决策树分类算法的具体内容，包括有很多种算法。从中我们不难发现决策树的算法都是经过不不断的改造趋于成熟的。所以说，机器学习的发展在某种程度上就是由于这些算法的进步而来的。

⑩ 决策树的算法

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。