下载掌阅APP，畅读海量书库
立即打开
决策树是数据挖掘的有力工具之一，决策树学习算法是以一组样本数据集（一个样本数据也可以称为实例）为基础的一种归纳学习算法，它着眼于从一组无次序、无规则的样本数据（概念）中推理出决策树表示形式的分类规则。
决策树（Decision Tree）是一种类似于流程图的树结构，其中每个内部节点（非叶节点）表示在属性上的测试，每个分支表示该测试上的一个输出，而每个叶节点存放一个类标号，树的最顶层节点是根节点。决策树生成方式一般情况下都是由上而下的。每次不同的事件或决策都有可能引发至少两个以上的事件，形成不同的结果，这种决策方法用图形表示出来很像一棵树，所以称为决策树。决策树是一种简单且广泛使用的分类器。通过训练数据来构建决策树，可高效地对未知的数据进行分类。
决策树有两大优点：
（1）决策树模型可读性好且具有描述性，有助于进行人工分析。
（2）效率高，决策树只需一次构建就可反复使用，每次预测的最大计算次数不超过决策树的深度。
决策树是树形结构的知识表示，可自动对数据进行分类，可直接转换为分类规则。它能被看作是基于属性的预测模型，树的根节点是整个数据集空间，每个分节点对应一个分裂问题，它是对某个单一变量的测试，该测试将数据集合空间分割成两个或更多数据块，每个叶节点是带有分类结果的数据分割。决策树学习算法主要是针对“以离散型变量作为属性类型进行分类”的学习方法。对于连续性变量，必须离散化才能被学习和分类 [3] 。
决策树与其他分类方法相比具有准确性高和速度快的优点。准确度高主要表现在得出的分类规则的正确率比较高，速度快的优点主要表现在计算量比较小，能够快速地形成分类规则。
基于决策树的决策算法的最大优点是，在学习过程中不需要了解很多背景知识，只从样本数据及提供的信息就能够产生一棵决策树，通过树节点的分叉判别可以使某一分类问题仅与主要的树节点对应的变量属性取值相关，即不需要全部变量取值来判别对应的范类。
基于决策树的决策算法是实用性很好的总结预测算法之一，是一个趋近于非连续型函数值的算法，分类准确率高，方便操作，并且对噪声数据有很好的健壮性，所以成为了应用范围很广且比较受欢迎的数据挖掘算法。决策树在各行各业有着非常多的广泛应用，如在医院的临床决策、人脸检测、故障诊断、故障预警、医疗数据挖掘、案例分析、分类预测的软件系统等方面都有很大的用处。决策树是数据挖掘的有力工具之一。决策树的最佳用途是图解说明如何领会决策与相关事件的相互作用。
决策树的特性是能够直观地体现数据，一般通过简单分析都能理解决策树表达的含义。决策树对于数据要求不是很高，数据的表达形式一般很简单。对于属性的类型是常规型或者是数据型的数据能够同时处理。另外，决策树能够在短时间内对大型的数据源做出有效且可行的分析结果。可以通过静态测试的方法对决策树模型进行测评，并且可以测定模型的可信度。对于某个观察模型，依据它所产生的决策树，能够非常容易地推导出相应的逻辑表达式 [4] 。
决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。
决策树也是最常用的数据挖掘算法之一，它的概念非常简单。决策树算法之所以如此流行，一个很重要的原因就是使用者基本上不用去了解机器学习算法，也不用深究它是如何工作的。直观地看，决策树分类器就像判断模块和终止块组成的流程图，终止块表示分类结果（也就是树的叶子）。判断模块表示对一个特征取值的判断 [5] （该特征有几个值，判断模块就有几个分支）。
如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到了决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树，决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类 [5] 。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。图3-2给出了一个商业上使用决策树的例子。
图3-2 买电脑的决策树
它表示了一个关心电子产品的用户是否会购买电脑，用它可以预测某条记录（某个人）的购买意向。树中包含了三种节点：
（1）根节点（root rode），它没有入边，但有两条或多条出边。
（2）子节点（child node），恰有一条入边和两条或多条出边。
（3）叶节点（Leaf Node ）或终节点（Terminal Node），恰有一条入边，但没有出边。
在决策树中，每个叶节点都赋予一个类标号。非终节点（Non-terminal Rode）（包括根节点和内部节点）包含属性测试条件，用以分开具有不同特性的记录。这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机。每个内部节点（方形框）代表对某个属性的一次检测。每个叶节点（椭圆框）代表一个类：
（买电脑=买）或者（买电脑=不买）
在这个例子中，样本向量为：（年龄，学生，信用评级；买电脑）
被决策数据的格式为：（年龄，学生，信用评级）
输入新的被决策的记录，可以预测该记录隶属于哪个类。
一旦构造了某一棵决策树，对检验记录进行分类就相当容易了。从树的根节点开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该分支或者到达另一个内部节点，使用新的测试条件，或者到达一个叶节点。到达叶节点之后，叶节点的类称号就被赋值给该检验记录。
决策树分类算法应用的完整流程应包含建树和应用。建树是从经验数据中获取知识，进行机器学习，建立模型或者构造分类器，是决策树算法的工作重点，通常又将其分为建树和剪枝两个部分。而应用则比较简单，利用建好的决策树模型分类或者预测新数据即可。
先介绍一下建树。建树就是决策树分类算法建模的主体过程，或者说，建树便是主要规则的产生过程。决策树构建的基本步骤如表3-1所示。
表3-1 决策树构建的基本步骤
决策树的变量有两种：数字型（Numeric）和名称型（Nominal）。
（1）数字型：变量类型是整数或浮点数，如前面例子中的“年龄”。用“＞”“＜”等作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
（2）名称型：类似编程语言中的枚举类型，变量只能从有限的选项中选取。
如何评估分割点的好坏？如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。
树的主体建好后，接下来便是对其剪枝。所谓剪枝，就是在树的主体上删除过多的比较或者直接删除一些不必要的子树，提高树的性能，确保精确度，提高其可理解性。同时，在剪枝过程中还要克服训练样本集的数据噪声，尽可能排除噪声造成的影响。决策树的剪枝一般通过极小化决策树整体的损失函数或代价函数来实现 [6] 。
决策树剪枝常用的方法有两种：预剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。
预剪枝是根据一些原则尽早停止树的增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数等。预剪枝在建立树的过程中决定是否需要继续划分或分裂训练样本来实现提前停止树的构造，一旦决定停止分支，就将当前节点标记为叶节点。这样可以有效减少建立某些子树的计算代价。运用这一策略的代表性算法如PUBLIC [7] 算法。预剪枝的核心问题是，如何事先指定树的最大深度，如果设置的最大深度不恰当，那么将会导致过于限制树的生长，使决策树的表达式规则趋于一般，不能更好地对新数据集进行分类和预测。除了事先限定决策树的最大深度之外，还有另外一个方法来实现预剪枝操作，那就是，采用检验技术对当前节点对应的样本集合进行检验，如果该样本集合的样本数量已小于事先指定的最小允许值，那么停止该节点的继续生长，并将该节点变为叶节点，否则可以继续扩展该节点。
后剪枝是通过在完全生长的树上剪去分支实现的，通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：错误率降低修剪（Reduced-error pruning） [8] 、规则后修剪（Rule post-pruning）、最小错误剪枝（Minimum Error pruning,MEP）和最小描述长度（Minimum Description Length,MDL） [9] 算法等。后剪枝操作是一个边修剪边检验的过程，一般规则标准是，在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树可测试数据的预测精度，并计算出相应的错误率，如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么就剪掉该子树。
决策树分类算法能被普遍应用，是基于其特有的优点。首先，其结构简单，容易理解；其次，适合处理量比较大的数据；再次，计算量较小，运算速度较快；再者，在处理非数值型数据上优势明显；最后，分类准确率比较高。
1）决策树的生成过程
一棵决策树的生成过程主要分为以下3个部分。
（1）特征选择：特征选择是指从训练数据众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同的量化评估标准，从而衍生出不同的决策树算法。
（2）决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分，则决策树停止生长。对于树结构来说，递归结构是最容易理解的方式。
（3）剪枝：决策树容易过拟合，一般都需要剪枝，缩小树结构规模、缓解过拟合。
2）基于信息论的三种决策树算法
划分数据集的最大原则是，使无序的数据变得有序。如果一个训练数据中有10个特征，那么选取哪个特征做划分依据？这就必须采用量化的方法来判断，量化划分方法有多种，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有 ID3、CART和C4.5等算法，其中C4.5和CART两种算法是从ID3算法中衍生而来的。
CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值——分裂值：特征值大于分裂值就走左子树，否则就走右子树。这个分裂值的选取原则是使得划分后子树中的“混乱程度”降低，具体到 C4.5和CART算法则有不同的定义方式。
ID3算法由 Ross Quinlan 发明，建立在“奥卡姆剃刀”的基础上，越是小型的决策树越优于大型的决策树。ID3算法根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征来做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶节点 [10] （例如设置信息增益阈值）。使用信息增益其实有一个缺点，那就是它偏向于具有大量值的属性，就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的。另外 ID3算法不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。
C4.5算法是 ID3算法的一个改进算法，继承了 ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足，在树构造过程中进行剪枝；能够完成对连续属性做离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因为树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须进行多次数据集扫描，故 C4.5算法只适合能够驻留于内存的数据集 [11] 。
CART（Classification And Regression Tree）算法采用的是基尼（Gini）指数（选Gini 指数最小的特征 s）作为分裂标准，同时它也包含后剪枝操作 [12] 。ID3算法和 C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据Gini系数来选择测试属性的决策树算法CART。
3）决策树优缺点
决策树适用于数值型和标称型（离散型数据，变量的结果只在有限目标集中取值），能够读取数据集，提取一些列数据中蕴含的规则。在分类问题中使用决策树模型有很多优点，决策树计算复杂度不高、便于使用、而且高效，决策树可处理具有不相关特征的数据，可很容易地构造出易于理解的规则。决策树模型也有一些缺点，比如处理缺失数据时困难、过度拟合以及忽略数据集中属性之间的相关性等。
下面对ID3、C4.5和CART算法分别进行简单介绍。
1）ID3算法的信息论基础
（1）信息熵。
信息熵：在概率论中，信息熵给出了一种度量不确定性的方式，用来衡量随机变量的不确定性，熵就是信息的期望值。若待分类的事物可能划分在 N 类中，分别是x 1 ,x 2 ,…,x n ，每一种取到的概率分别是p 1 ,p 2 ,…,p n ，那么X的熵就定义为：
从定义中可知：0≤H（X）≤log 2 （n）。
当随机变量只取两个值时，即 X 的分布P（X =1）=p,P（X =0）=1-p,0≤p≤1，则熵为：
熵值越高，则数据混合的种类越高，其蕴含的含义是一个变量可能的变化越多（反而跟变量具体的取值没有任何关系，只和值的种类多少及发生概率有关），它携带的信息量就越大。熵在信息论中是一个非常重要的概念，很多机器学习的算法都会利用这个概念。
（2）条件熵。
假设有随机变量（X,Y），其联合概率分布为：P（X =x i ,Y =y i ）= p ij ,i =1,2,…,n;j= 1,2,…,m。则条件熵H（Y|X）表示在已知随机变量 X 的条件下随机变量 Y 的不确定性，其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望：
若是样本的特征只有两个值（x
1
=0,x
2
=1）对应（出现，不出现），如文本分类中某一个单词的出现与否。那么对于特征二值的情况，用 T 代表特征，用 t 代表 T 出现，
表示该特征不出现。那么：
与前面的公式对比一下，P（t） 就是T出现的概率，
就是T不出现的概率。结合信息熵的计算公式，可得：
特征 T 出现的概率为P（t），只要用出现过 T 的样本数除以总样本数即可；P（C i |t）表示出现 T 的时候，类别C i 出现的概率，只要用出现了 T 并且属于类别C i 的样本数除以出现了T的样本数即可。
（3）信息增益。
信息增益（Information Gain）表示得知特征X的信息后，使得Y的不确定性减少的程度。定义为：
信息增益是针对一个一个的特征而言的，就是看一个特征 X，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息增益。每次选取特征的过程都是通过计算每个特征值划分数据集后的信息增益，然后选取信息增益最高的特征。
对于特征取值为二值的情况，特征 T 给系统带来的信息增益就可以写成系统原本的熵与固定特征T后的条件熵之差：
经过上一轮信息增益计算后，会得到一个特征作为决策树的根节点，该特征有几个取值，根节点就会有几个分支，每一个分支都会产生一个新的数据子集D k ，余下的递归过程就是对每个D k 再重复上述过程，直至子数据集都属于同一类。
在决策树构造过程中可能会出现这种情况：所有特征都作为分裂特征用光了，但子集还不是纯净集（集合内的元素不属于同一类别）。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶节点。
2）ID3算法生成决策树的过程
算法：ID3_DT（S,A,C）。输入：训练集S，特征集A，分类集C。输出：决策规则集。
ID3算法生成决策树的步骤 [13] 如表3-2所示。
表3-2 ID3算法生成决策树的步骤
递归划分停止的条件：
（1）没有条件属性可以继续划分。
（2）给定分支的数据集为空。
（3）数据集属于同一类。
（4）决策树已经达到设置的最大值。
3）ID3算法使用实例
表3-3所示为某学院学生成绩数据库（训练样本集合），训练样本包含4个属性，它们分别为成绩、任课教师、A课程的修习类别、是否修过B课程。样本集合的类别属性为C课程是否合格，该属性有2个取值，即为合格和不合格。
表3-3 某学院学生成绩数据库
从表3-3可以看出，C 课程合格的为4个，C 课程不合格的为6个。所以利用H（X）=plog 2 （p）（1-p）log 2 （1-p）可以计算H（X）：
成绩属性：“＞80”有4个（这4个中 C 课程1个合格，3个不合格），“＜60”有4个（这4个中C课程1个合格，3个不合格），“60～80”有2个（这2个C课程都是合格）。所以利用
可以计算H（成绩）：
利用信息增益式计算成绩的信息增益：
任课教师属性：甲3个（这3个中C课程1个合格，2个不合格），乙3个（这3个中C课程1个合格，2个不合格），丙2个（这2个C课程都是合格），丁2个（这2个C课程都是不合格）。可以计算H（任课教师）：
所以，任课教师的信息增益：
A课程作为哪类课程修习这个属性，作为核心课程的为3个（这3个中C课程1个合格，2个不合格），作为专业选修的为3个（这3个中 C 课程2个合格，1个不合格），作为非限定选修的为4个（这4个中C课程1个合格，3个不合格）。利用下面的式子可以计算H（A的修习类别）：
所以，A的修习类别的信息增益：
是否修过 B 课程这个属性，有修过的4个（这4个中 C 课程1个合格，3个不合格），无修过的6个（这6个中C课程3个合格，3个不合格）。利用以下式子可以计算H（是否修过B）。
所以，是否修过B的信息增益：
从上面对各属性的信息增益计算，并根据 ID3算法选择分裂属性的标准可知，第一个选择的分裂属性为成绩。通过成绩属性的分裂，将样本训练集分为4个分支，其中丙教师任课分支样本全部通过C课程，丁教师任课分支样本全部属于不通过C课程，所以这两枝停止分裂。而甲任课和乙任课的样本还包括合格与不合格两类，并且属性集中还有三个属性，因而需要进一步计算属性的信息增益，进而选择分裂属性。通过计算，并根据ID3算法原理建立的完整决策树如图3-3所示。
图3-3 根据ID3算法对学生数据库建立的决策树
4）ID3算法的优缺点
ID3算法建树过程简单且易懂。但是 ID3存在多值偏向问题，在选择分裂属性时，会优先选择取值较多的属性，而在某一些情况下，这些属性并不是最优属性：首先，对于连续型属性，传统的 ID3算法不能直接进行处理；其次，属性间的关联性不强，但它正是 ID3算法可以在 Hadoop 平台上并行化的前提；再者，ID3算法对噪声数据很敏感；最后，结果会随着训练集规模的不同而不同。
ID3算法并不完美，局限性较强。为了改进其缺陷，Quinlan有针对性地提出了更为完善的 C4.5算法，C4.5算法同样以“信息熵”作为核心，是在 ID3算法基础上的优化改进，同时，也保持了分类准确率高、速度快的特点。
1）基本思想
与ID3算法不同，C4.5算法挑选具有最高信息增益率的属性为测试属性。对样本集T，假设变量 a 有 k 个属性，属性取值a 1 ,a 2 ,…,a k ，对应 a 取值为 a i 的样本个数分别为n i ，若n是样本的总数，则应有n 1 +n 2 +…+n k =n。Quinlan利用属性a的熵值H（X,a）来定义为了获取样本关于属性a的信息所需要付出的代价，即：
信息增益率定义为平均互信息与获取a信息所付出代价的比值，即
信息增益率是单位代价所获得的信息量，是一种相对的信息量不确定性度量。信息增益率作为测试属性的选择标准，选择最大的属性a作为测试属性。
以ID3算法思想为核心，C4.5算法在此基础上重点从以下几个方面进行了改进。
（1）利用信息增益比率作为新的属性判别能力度量，较好地解决了 ID3算法优先选择具有较多值，而不是最优属性可能导致过拟合的现象。
使用信息增益率能解决问题，也会产生一个新的问题：既然是比率，就不能避免分母为0或者非常小（当某个S i 接近S时出现）的情况，出现这种情况的后果就是要么比率非常大，要么就未定义。为了避免这种情况的出现，可以将信息增益率计算分两步来解决：首先计算所有属性的信息增益，忽略掉结果低于平均值的属性，仅对高于平均值的属性进一步计算信息增益率，从中择优选取分裂属性。
（2）缺失数据的处理思路。在面对缺失数据这一点上，C4.5算法针对不一样的情况，采取不一样的解决方法。方法如下：
①若某一属性 x 在计算信息增益或者信息增益率过程中，出现某些样本没有属性 x的情况，C4.5算法的处理方式：一是直接忽略掉这些样本；二是根据缺失样本占总样本的比例，对属性 x 的信息增益或信息增益率进行相应“打折”；三是将属性 x 的一个均值或者最常见的值赋给这些缺失样本；四是总结分析其他未知属性的规律，补全这些缺失样本。
②若属性x已被选为分裂属性，分支过程中出现样本缺失属性x的情况，C4.5算法的处理方式：一是直接忽略这些样本；二是用一个出现频率最高的值或者均值赋给这些样本属性 x；三是直接将这些缺失属性 x 的样本依据规定的比例分配到所有子集中去；四是将所有缺失样本归为一类，全部划分到一个子集中；五是总结分析其他样本，相应地分配一个值给缺失属性x的样本。
③若某个样本缺失了属性 x，又未被分配到子集中去，面对这种情况，C4.5算法的处理方法：一是若存在单独的缺失分支，直接分配到该分支；二是将其直接赋予一个最常见的属性 x 的值，然后进行正常的划分；三是综合分析属性 x 已存在的所有分支，按照一定的概率将其直接分到其中某一类；四是根据其他属性来进行分支处理；五是所有待分类样本在属性 x 节点处都终止分类，然后依据当前 x 节点所覆盖的叶节点类别，为其直接分配一个概率最高的类。
（3）连续属性的处理思路。
面对连续属性的情况，C4.5算法的思路是将连续属性离散化，分成不同的区间段，再进行相应的处理。具体处理过程如下：一是按照一定的顺序排列连续属性；二是选取相邻两个属性值的中点作为潜在划分点，计算其信息增益；三是修正划分点计算后的信息增益；四是在修正后的划分点中作出选择，小于均值的划分点可以直接忽略；五是计算最大信息增益率；六是选择信息增益率最大的划分点作为分裂点。
（4）剪枝策略。
C4.5算法有两种基本剪枝策略：子树替代法和子树上升法。前者的思路是：从树的底部向树根方向，若某个叶节点替代子树后，误差率与原始树很接近，便可用这个叶节点取代整棵子树；后者则是误差率在一定合理范围时，将一棵子树中出现频率最高的子树用以替代整棵子树，使其上升到较高节点处。C4.5算法虽说突破了ID3算法在很多方面的瓶颈，产生的分类规则准确率也比较高、易于理解，但是在核心的思想上还是保持在“信息熵”的范畴，最终仍生成多叉树。同时，其缺点也较为明显：建造树时，训练集要进行多次排序和扫描，所以效率不高。此外，C4.5算法只能处理驻留于内存的数据集，若训练集过大，超过内存容量时，算法便无能为力了。
2）C4.5算法建树过程
算法：C45_DT（A,S）。输入：训练集S，特征集A。输出：决策规则集。
C4.5算法建树步骤 [13] 如表3-4所示。
表3-4 C4.5算法建树步骤
递归划分停止的条件与前面ID3算法停止的条件相同。
3）C4.5 算法的优缺点
与 ID3算法相同，C4.5算法产生的决策规则简单且易懂。此外，C4.5算法可以处理连续属性。但同时 C4.5算法也是内存驻留算法，传统 C4.5算法能处理的数据集规模很小。
CART算法与ID3算法和C4.5算法不同，它生成的是一棵二叉树。它采用的是一种二分递归分割技术，每次都将当前的数据集分为两个互不相交子集，使得所有非叶节点都只有两个分支，因此，它所生成的决策树结构最简单。
1）分裂属性的选择标准
CART 算法分裂属性的选择标准为 Gini 指数，因为 Gini 指数可以用来衡量分割点的优劣程度。CART算法选择具有最小Gini指数的属性为当前数据集的分裂属性。属性具有的Gini指标越小，就表示用该属性划分数据集后，数据越纯，效果越好。
Gini指标分类方法适用于具有连续性或离散性属性的数据集。
设 S 为具有 s 个样本的数据集，所有样本总共包含 m 个不同的类别 C i , i∈{1,2,…,m}，那么Gini指标为：
其中，P i 为样本属性类别C i 的概率。
Gini（S） = 0表示该节点包含的信息量最大；当Gini（S）最大时，表示该节点包含的信息量最小。
根据 CART 算法构造的是一棵二叉树，所以在 CART 算法中是用 Gini 指标进行二元划分的，对于数据集S的任何一个属性A的任何一种取值a，可以将数据集S划分成S 1 和S 2 两个子集，对应属性A,Gini指标的计算式如下：
其中，|S|表示数据集S的个数。当GiniA（S）最小时，属性A就为数据集S的最佳分裂属性，S 1 和S 2 就是按属性A的取值a对数据集S的划分。
2）CART算法建树过程
算法：CART_DT（A,S）。输入：训练集S，特征集A。输出：决策规则集。
CART算法建树步骤 [13] 如表3-5所示。
表3-5 CART算法建树步骤
递归划分停止的条件：
（1）没有剩余的条件属性可以继续划分。
（2）给定分支的数据集为空。
（3）所有数据集属于同一类。
（4）决策树已经达到设置的最大值。
3）CART 算法的优缺点
CART 算法产生的决策树结构简单、容易理解且准确率高。但是同样，它也是内存驻留算法，在单机环境下只能处理小规模的数据。