2.2.2　CART分类决策树的原理

CART算法可以生成分类决策树和回归决策树。我们首先介绍CART分类决策树的算法流程，然后给出一个决策树生成实例。

2.2.2.1　CART分类决策树的算法流程

1. 输入

输入为训练数据集D和停止计算的条件。其中，训练数据集D包含多条记录，每个记录由多个属性构成。每个属性的数据类型均为离散的，例如二值类型、标称值或枚举值类型等。停止计算的条件可以是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或没有更多特征属性等。

2. 输出

输出为CART分类树。

3. CART分类决策树的生成流程

CART算法从根节点开始，用训练集递归地建立CART分类决策树。

1）设训练数据集为D，计算数据集现有的所有属性特征对该训练集的基尼增益。对每一个属性特征F，对其所有可能取值的每个值f，根据D中的样本实例对F=f的测试为“是”或“否”，将数据集D分割成D₁和D₂两个子集，利用基尼增益公式计算F=f时的基尼增益。假设有N_F个属性特征，对于每一个属性特征i，可能取值数量为N_i，则总共需要计算的基尼不纯度次数为2+1，基尼增益或基尼指数的计算次数为。

2）在所有可能的属性特征F以及它们所有可能的切分点f_i中，选择基尼增益最大的特征及其对应的切分点作为最优切分点，依据该最优切分点切割，生成两个子节点，左子节点为D₁，右子节点为D₂。

3）对两个子节点递归调用步骤1~2，直至满足停止条件。

4）生成一棵完整的二叉CART分类决策树。

4. CART分类决策树的优化

使用决策树模型拟合数据时容易产生过拟合，解决办法是对决策树进行剪枝处理。决策树剪枝有两种思路：预剪枝（pre-pruning）和后剪枝（post-pruning）。

5. CART分类决策树模型的使用

决策树算法是一种通过对历史样本数据进行测算实现对新数据的分类和预测的算法。整个决策过程从根节点开始，从上到下进行，根据数据的分类在每个决策节点给出不同的结果。使用决策树的过程和人眼比对的过程类似：先比对根节点，根据比对结果走向决策树的不同子节点；再在子节点处进行比对，直到比对到叶子节点，即得到结果。对生成的CART分类决策树做预测的时候，如果测试集里的某个样本A落到了某个叶子节点，且该叶子节点里存在多个类别的训练样本，则概率最大的训练样本是样本A的类别。

2.2.2.2　CART分类决策树的生成实例

下面以天气与是否打网球的数据集为例，具体介绍CART分类决策树的生成过程。是否打网球的影响因素有天气、温度、湿度和风力，共有如表2.2所示的14条记录。

表2.2　天气与是否打网球的数据（PlayTennis数据集）

首先确定根属性特征，计算原始样本数据集的基尼不纯度：

G=1-（9/14）2-（5/14）2≈1-0.413-0.128=0.459

我们考虑第一个属性特征：天气。它是一个标称值类型，包含3个枚举值，即晴朗、阴天和下雨。统计该属性特征取不同值时的样本数量，如表2.3所示。

表2.3　天气数据

根据表2.3可以得到：

G（Outlook=Sunny）=1-（2/5）2-（3/5）2=1-0.16-0.36=0.48

G（Outlook≠Sunny）=1-（7/9）2-（2/9）2≈1-0.61-0.05=0.34

G（Outlook=Overcast）=1-（4/4）2-（0/4）2=0

G（Outlook≠Overcast）=1-（5/10）2-（5/10）2=0.5

G（Outlook=Rain）=1-（3/5）2-（2/5）2=1-0.36-0.16=0.48

G（Outlook≠Rain）=1-（6/9）2-（3/9）2≈1-0.44-0.11=0.45

这样，原始的样本数据集会被划分为两个子集合。那么，具体采用天气的哪一个值作为分割点呢?如果采用Outlook=Sunny，则产生的基尼增益和基尼指数为

GG（Outlook=Sunny）=G-5/14×G（Outlook=Sunny）-9/14×G（Outlook≠Sunny）

=0.459-5/14×0.48-9/14×0.34≈0.459-0.171-0.219=0.069

GI（Outlook=Sunny）=0.39

如果采用Outlook=Overcast，则产生的基尼增益和基尼指数为

GG（Outlook=Overcast）=G-4/14×G（Outlook=Overcast）

-10/14×（1-G（Outlook=Overcast））

=0.459-4/14×0-10/14×0.5≈0.102

GI（Outlook=Overcast）=0.357

如果采用Outlook=Rain，则产生的基尼增益和基尼指数为

GG（Outlook=Rain）=G-5/14×G（Outlook=Rain）-9/14×（1-G（Outlook=Rain））

=0.459-5/14×0.48-9/14×0.45≈0.459-0.171-0.288=0

GI（Outlook=Rain）=0.459

那么，从基尼增益或基尼指数的角度看，选择的分割值为Overcast，基尼增益为0.102，基尼指数为0.357。

类似地，我们考虑第二个属性特征：温度。它也是一个标称值类型，有3个取值，分别为热、温和以及凉爽。统计该属性特征取不同值时的样本记录数量，如表2.4所示。

表2.4　温度数据

根据表2.4可以得到：

G（Temperature=Hot）=1-（2/4）2-（2/4）2=0.5

G（Temperature≠Hot）=1-（7/10）2-（3/10）2=1-0.49-0.09=0.42

G（Temperature=Cool）=1-（3/4）2-（1/4）2=1-0.5625-0.0625=0.375

G（Temperature≠Cool）=1-（6/10）2-（4/10）2=1-0.36-0.16=0.48

G（Temperature=Mild）=1-（4/6）2-（2/6）2≈1-0.444-0.111=0.445

G（Temperature≠Mild）=1-（5/8）2-（3/8）2≈1-0.391-0.111=0.445

如果Temperature=Hot，则产生的基尼增益和基尼指数为

GG（Temperature=Hot）=G-4/14×G（Temperature=Hot）-10/14×G（Temperature≠Hot）

=0.459-4/14×0.5-10/14×0.42≈0.459-0.143-0.3=0.016

GI（Temperature=Hot）=0.443

如果Temperature=Cool，则产生的基尼增益和基尼指数为

GG（Temperature=Cool）=G-4/14×G（Temperature=Cool）-10/14×G（Temperature≠Cool）

=0.459-4/14×0.375-10/14×0.48≈0.459-0.107-0.343=0.009

GI（Temperature=Cool）=0.45

如果Temperature=Mild，则产生的基尼增益和基尼指数为

GG（Temperature=Mild）=G-6/14×G（Temperature=Mild）-8/14×G（Temperature≠Mild）

=0.459-6/14×0.445-8/14×0.445≈0.459-0.445=0.014

GI（Temperature=Mild）=0.445

那么，从基尼增益或基尼指数的角度看，选择的分割值为Hot，基尼增益为0.016，基尼指数为0.443。

类似地，我们考虑第三个属性特征：湿度。它也是一个二值类型，有2个取值，分别为高和正常。统计该属性特征取不同值时的样本记录数量，如表2.5所示。

表2.5　湿度数据

根据表2.5可以得到：

G（Humidity=High）=1-（3/7）2-（4/7）2≈1-0.184-0.327=0.489

G（Humidity=Normal）=1-（6/7）2-（1/7）2≈1-0.735-0.02=0.245

G（Humidity≠High）=G（Humidity=Normal）=0.244

G（Humidity≠Normal）=G（Humidity=High）=0.489

如果Humidity=High，则产生的基尼增益和基尼指数为

GG（Humidity=High）=G-7/14×G（Humidity=High）-7/14×G（Humidity≠High）

≈0.459-0.245-0.122=0.092

GI（Humidity=High）=0.367

如果Humidity=Normal，则产生的基尼增益和基尼指数为

GG（Humidity=Normal）=G-7/14×G（Humidity=Normal）-7/14×G（Humidity≠Normal）

≈0.459-0.122-0.245=0.092

GI（Humidity=Normal）=0.367

那么，从基尼增益或基尼指数的角度看，选择的分割值为High或Normal，基尼增益为0.092，基尼指数为0.367。

同样，我们考虑第四个属性特征：风力。它也是一个二值类型，有2个取值，分别为弱和强。统计该属性特征取不同值时的样本记录数量，如表2.6所示。

表2.6　风力数据

根据表2.6可以得到：

G（Wind=Weak）=1-（6/8）2-（2/8）2=1-0.5625-0.062=0.375

G（Wind=Strong）=1-（3/6）2-（3/6）2=1-0.25-0.25=0.5

G（Wind≠Weak）=G（Wind=Strong）=0.5

G（Wind≠Strong）=G（Wind=Weak）=0.375

如果Wind=Weak，则产生的基尼增益和基尼指数为

GG（Wind=Weak）=G-8/14×G（Wind=Weak）-6/14×G（Wind≠Weak）

=0.459-8/14×0.375-6/14×0.5≈0.459-0.214-0.214=0.031

GI（Wind=Weak）=0.428

如果Wind=Strong，则产生的基尼增益和基尼指数为

GG（Wind=Strong）=G-6/14×G（Wind=Strong）-8/14×G（Wind≠Strong）

=0.459-6/14×0.5-8/14×0.375≈0.459-0.214-0.214=0.031

GI（Wind=Strong）=0.428

那么，从基尼增益或基尼指数的角度看，选择的分割值为Weak或Strong，基尼增益为0.031，基尼指数为0.428。

最后，我们根据每个属性特征的基尼增益或基尼指数，就可以决定决策树的根节点。从表2.7中可以看出，选择天气属性时，基尼增益是最大的。因此天气被选择为决策树的根节点，且分割点为Overcast。

表2.7　各个属性特征的基尼增益、基尼指数与分割点表

这样，原样本数据集被分割成两个子集：子集D₁（表2.8）为Outlook=Overcast，子集D₂（表2.9）为Outlook≠Overcast。

表2.8　子集D₁：Outlook=Overcast

表2.9　子集D₂：Outlook≠Overcast

接下来考虑子集D₁，由于该子集中所有样本都是打网球，因此，该子集直接生成叶子节点。对于子集D₂，可以继续上述过程，选择合适的属性特征及其分割点，生成后续的子节点，这里就不再介绍了。