导读
通常决策树一共有三种实现方法，分别是ID3、C4.5和CART（Classification And Regression Tree，即分类回归树），回顾决策树的基本知识，其构建过程主要有下述三个重要的问题：
-
数据是怎么分裂的（ID3、C4.5、CART）
-
如何选择分类的属性（哪个属性作为根节点，哪个属性作为子节点）
-
什么时候停止分裂（剪枝）
有个构成决策树的方法后，可以用多棵决策树一起做判断，此时有两种方法，Bagging（代表例子有随机森林）和Boosting（代表例子有GBDT梯度提升决策树，Adaboost以及XGBoost），下面分别介绍实现决策树的三种方法。
方法一：ID3
先看一个例子，给定14天的气象数据（指标包括outlook，temperature，humidity，windy），并已知这些天气决定是否打球（play，yes or no）。例如下面表格中的第一个例子，如果给出新一天的气象指标数据：晴天（outlook = sunny）、凉爽（temperature = cool）、湿度大（humidity = high）、没有风（windy = False），则不回去打球（play = no）。
| outlook | temperature | humidity | windy | play |
|---|---|---|---|---|
| sunny | hot | high | FALSE | no |
| sunny | hot | high | TRUE | no |
| overcast | hot | high | FALSE | yes |
| rainy | mild | high | FALSE | yes |
| rainy | cool | normal | FALSE | yes |
| rainy | cool | normal | TRUE | no |
| overcast | cool | normal | TRUE | yes |
| sunny | mild | high | FALSE | no |
| sunny | cool | normal | FALSE | yes |
| rainy | mild | normal | FALSE | yes |
| sunny | mild | normal | TRUE | yes |
| overcast | mild | high | TRUE | yes |
| overcast | hot | normal | FALSE | yes |
| rainy | mild | high | TRUE | no |
用决策树来预测：
决策树的形式类似于“如果天气怎么样，去玩；否则，怎么着怎么着”的树形分叉。那么问题是用哪个属性（即变量，如天气、温度、湿度和风力）最适合充当这颗树的根节点，在它上面没有其他节点，其他的属性都是它的后续节点。
那么借用上面所述的能够衡量一个属性区分以上数据样本的能力的“信息增益”（Information Gain）理论，即选分裂前总的信息 - 分裂后总的信息之差最大的节点。
如果一个属性的信息增益量越大，这个属性作为一棵树的根节点就能使这棵树更简洁，比如说一棵树可以这么读成，如果风力弱，就去玩；风力强，再按天气、温度等分情况讨论，此时用风力作为这棵树的根节点就很有价值。如果说，风力弱，再又天气晴朗，就去玩；如果风力强，再又怎么怎么分情况讨论，这棵树相比就不够简洁了。
计算信息增益
计算信息增益的方法有很多，我们选用熵来计算信息增益，回顾一下熵的定义式：
E
n
t
r
o
p
y
(
S
)
=
E
n
t
r
o
p
y
(
p
1
,
p
2
,
…
,
p
m
)
=
−
∑
i
=
1
m
p
i
l
o
g
2
p
i
(1)
Entropy(S) = Entropy(p_{1},p_{2},\dots,p_{m}) = -\sum_{i=1}^{m}p_{i}log_{2}p_{i} \tag{1}
Entropy(S)=Entropy(p1,p2,…,pm)=−i=1∑mpilog2pi(1)
熵越小代表样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱
首先计算分裂前系统的熵，最终判断的类别是“是否出去玩”。取值为yes的记录有9个，取值为no的有5个，即说这个样本里有9个正例，5 个负例，记为
S
(
9
+
,
5
−
)
S(9+,5-)
S(9+,5−)，S是样本的意思(Sample)。那么
P
(
c
1
)
=
9
/
14
P(c1) = 9/14
P(c1)=9/14，
P
(
c
2
)
=
5
/
14
P(c2) = 5/14
P(c2)=5/14，系统的熵为：
E
n
t
r
o
p
y
(
S
)
=
−
9
14
×
l
o
g
2
9
14
−
5
14
×
l
o
g
2
5
14
=
−
0.94
Entropy(S)= -\frac{9}{14} \times log_2\frac{9}{14} - \frac{5}{14} \times log_2 \frac{5}{14} = -0.94
Entropy(S)=−149×log2149−145×log2145=−0.94
下面计算以某个属性为根节点进行分裂后的熵，即条件熵。分别以Wind、Humidity、Outlook和Temperature作为根节点计算分裂后系统的熵，先计算以Wind为节点的条件熵，Wind有两种取值，当为Weak时：记录有8条，其中正例6个，负例2个；同样，取值为Strong的记录6个，正例负例个3个。利用
(
1
)
(1)
(1)式我们可以计算相应的熵为：
E
n
t
r
o
p
y
(
W
e
a
k
)
=
−
(
6
/
8
)
×
l
o
g
(
6
/
8
)
−
(
2
/
8
)
×
l
o
g
(
2
/
8
)
=
−
0.811
E
n
t
r
o
p
y
(
S
t
r
o
n
g
)
=
−
(
3
/
6
)
×
l
o
g
(
3
/
6
)
−
(
3
/
6
)
×
l
o
g
(
3
/
6
)
=
−
1.0
Entropy(Weak)=-(6/8) \times log(6/8)-(2/8) \times log(2/8)=-0.811 \\ Entropy(Strong)=-(3/6) \times log(3/6)-(3/6) \times log(3/6)=-1.0
Entropy(Weak)=−(6/8)×log(6/8)−(2/8)×log(2/8)=−0.811Entropy(Strong)=−(3/6)×log(3/6)−(3/6)×log(3/6)=−1.0
则分裂后系统的条件熵为：
E
n
t
r
o
p
y
(
S
∣
W
i
n
d
)
=
8
14
×
E
n
t
r
o
p
y
(
W
e
a
k
)
+
6
14
×
E
n
t
r
o
p
y
(
S
t
r
o
n
g
)
=
−
0.89
Entropy(S | Wind) = \frac{8}{14} \times Entropy(Weak) + \frac{6}{14} \times Entropy(Strong) = -0.89
Entropy(S∣Wind)=148×Entropy(Weak)+146×Entropy(Strong)=−0.89
现在就可以计算出以Wind为节点的信息增益了：
G
a
i
n
(
W
i
n
d
)
=
E
n
t
r
o
p
y
(
S
)
−
E
n
t
r
o
p
y
(
S
∣
W
i
n
d
)
=
−
0.94
−
(
−
0.89
)
=
−
0.048
Gain(Wind)=Entropy(S)-Entropy(S | Wind)=-0.94-(-0.89)=-0.048
Gain(Wind)=Entropy(S)−Entropy(S∣Wind)=−0.94−(−0.89)=−0.048
计算以Wind为节点分裂后的属性技巧在于要乘上各自取值所占的比例，例如
8
/
14
8/14
8/14是属性Wind取值为Weak的个数占总记录的比例，同样
6
/
14
6/14
6/14是其取值为Strong的记录个数与总记录数之比。
同理，如果以Humidity作为根节点的条件熵以及信息增益为：
E
n
t
r
o
p
y
(
H
i
g
h
)
=
0.985
;
E
n
t
r
o
p
y
(
N
o
r
m
a
l
)
=
0.592
,
G
a
i
n
(
S
∣
H
u
m
i
d
i
t
y
)
=
0.940
−
(
7
/
14
)
×
E
n
t
r
o
p
y
(
H
i
g
h
)
−
(
7
/
14
)
×
E
n
t
r
o
p
y
(
N
o
r
m
a
l
)
=
0.151
Entropy(High)=0.985;\quad Entropy(Normal)=0.592, \\ Gain(S|Humidity)=0.940-(7/14) \times Entropy(High)-(7/14) \times Entropy(Normal)=0.151
Entropy(High)=0.985;Entropy(Normal)=0.592,Gain(S∣Humidity)=0.940−(7/14)×Entropy(High)−(7/14)×Entropy(Normal)=0.151
以Outlook作为根节点的条件熵以及信息增益为：
E
n
t
r
o
p
y
(
S
u
n
n
y
)
=
0.971
;
E
n
t
r
o
p
y
(
O
v
e
r
c
a
s
t
)
=
0.0
;
E
n
t
r
o
p
y
(
R
a
i
n
)
=
0.971
G
a
i
n
(
S
∣
O
u
t
l
o
o
k
)
=
0.940
−
(
5
/
14
)
×
E
n
t
r
o
p
y
(
S
u
n
n
y
)
−
(
4
/
14
)
×
E
n
t
r
o
p
y
(
O
v
e
r
c
a
s
t
)
−
(
5
/
14
)
×
E
n
t
r
o
p
y
(
R
a
i
n
)
=
0.247
Entropy(Sunny)=0.971;\quad Entropy(Overcast)=0.0;\quad Entropy(Rain)=0.971 \\ Gain(S|Outlook)=0.940-(5/14) \times Entropy(Sunny)-(4/14) \times Entropy(Overcast)-(5/14) \times Entropy(Rain)=0.247
Entropy(Sunny)=0.971;Entropy(Overcast)=0.0;Entropy(Rain)=0.971Gain(S∣Outlook)=0.940−(5/14)×Entropy(Sunny)−(4/14)×Entropy(Overcast)−(5/14)×Entropy(Rain)=0.247
以Temperature作为根节点的条件熵以及信息增益为：
E
n
t
r
o
p
y
(
C
o
o
l
)
=
0.811
;
E
n
t
r
o
p
y
(
H
o
t
)
=
1.0
;
E
n
t
r
o
p
y
(
M
i
l
d
)
=
0.918
G
a
i
n
(
S
∣
T
e
m
p
e
r
a
t
u
r
e
)
=
0.940
−
(
4
/
14
)
×
E
n
t
r
o
p
y
(
C
o
o
l
)
−
(
4
/
14
)
×
E
n
t
r
o
p
y
(
H
o
t
)
−
(
6
/
14
)
×
E
n
t
r
o
p
y
(
M
i
l
d
)
=
0.029
Entropy(Cool)=0.811;\quad Entropy(Hot)=1.0;\quad Entropy(Mild)=0.918 \\ Gain(S|Temperature)=0.940-(4/14) \times Entropy(Cool)-(4/14) \times Entropy(Hot)-(6/14) \times Entropy(Mild)=0.029
Entropy(Cool)=0.811;Entropy(Hot)=1.0;Entropy(Mild)=0.918Gain(S∣Temperature)=0.940−(4/14)×Entropy(Cool)−(4/14)×Entropy(Hot)−(6/14)×Entropy(Mild)=0.029
这样我们就得到了以上四个属性相应的信息增益值：
G
a
i
n
(
S
∣
W
i
n
d
)
=
0.048
G
a
i
n
(
S
∣
H
u
m
i
d
i
t
y
)
=
0.151
G
a
i
n
(
S
∣
O
u
t
l
o
o
k
)
=
0.247
G
a
i
n
(
S
∣
T
e
m
p
e
r
a
t
u
r
e
)
=
0.029
Gain(S|Wind)=0.048 \\ Gain(S|Humidity)=0.151 \\ Gain(S|Outlook)=0.247 \\ Gain(S|Temperature)=0.029
Gain(S∣Wind)=0.048Gain(S∣Humidity)=0.151Gain(S∣Outlook)=0.247Gain(S∣Temperature)=0.029
最后按照信息增益最大的原则选Outlook为根节点。子节点重复上面的步骤，最终树的结构如下图：
ID3算法优点与不足
ID3优点是理论清晰、方法简单、学习能力较强，但也存在一些缺点：
- 只能处理分类属性的数据，不能处理连续的数据；
- 对噪声敏感；
- ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准，信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
方法二：C4.5
因为ID3在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率gain ratio的方式来选择属性。
信
息
增
益
率
=
信
息
增
益
(
G
a
i
n
)
/
属
性
熵
(
S
p
l
i
t
I
n
f
o
r
m
a
t
i
o
n
)
信息增益率 = 信息增益(Gain) / 属性熵(SplitInformation)
信息增益率=信息增益(Gain)/属性熵(SplitInformation)
当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于C4.5算法来说，属性熵也会变大，所以整体的信息增益率并不大。
信息增益率的具体定义如下：
G
a
i
n
R
a
t
i
o
(
S
,
A
)
=
G
a
i
n
(
S
,
A
)
S
p
l
i
t
I
n
f
o
r
m
a
t
i
o
n
(
S
,
A
)
GainRatio(S,A) = \frac{Gain(S,A)}{SplitInformation(S,A)}
GainRatio(S,A)=SplitInformation(S,A)Gain(S,A)
其中，分裂信息SplitInformation被定义为（分裂信息用来衡量属性分裂数据的广度和均匀）：
S
p
l
i
t
I
n
f
o
r
m
a
t
i
o
n
(
S
,
A
)
≡
−
∑
i
=
1
c
∣
S
i
∣
∣
S
∣
l
o
g
2
∣
S
i
∣
∣
S
∣
SplitInformation(S,A) \equiv -\sum_{i=1}^{c}\frac{|S_{i}|}{|S|} log_{2} \frac{|S_{i}|}{|S|}
SplitInformation(S,A)≡−i=1∑c∣S∣∣Si∣log2∣S∣∣Si∣
信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）
例子
下面以ID3相同的weather数据集（全部为分类属性）为例，分析C4.5构建决策树的详细过程。
数据集weather具有属性“outlook，temperature，humidity，wind”，每个属性的取值分别为：
o
u
t
l
o
o
k
=
{
s
u
n
n
y
,
o
v
e
r
c
a
s
t
,
r
a
i
n
}
outlook=\{sunny,overcast,rain\}
outlook={sunny,overcast,rain}，
t
e
m
p
e
r
a
t
u
r
e
=
{
h
o
t
,
m
i
l
d
,
c
o
o
l
}
temperature=\{hot,mild,cool\}
temperature={hot,mild,cool}，
h
u
m
i
d
i
t
y
=
{
h
i
g
h
,
n
o
r
m
a
l
}
humidity=\{high,normal\}
humidity={high,normal}，
w
i
n
d
=
{
w
e
a
k
,
s
t
r
o
n
g
}
wind=\{weak,strong\}
wind={weak,strong},
C4.5对weather数据集建立决策树的过程如下：
1.由上一部分知所有属性划分数据集S所得的信息增益分别如下：
G
a
i
n
(
S
∣
o
u
t
l
o
o
k
)
=
0.246
;
G
a
i
n
(
S
∣
t
e
m
p
e
r
a
t
u
r
e
)
=
0.029
;
G
a
i
n
(
S
∣
h
u
m
i
d
i
t
y
)
=
0.152
;
G
a
i
n
(
S
∣
w
i
n
d
)
=
0.049
Gain(S|outlook)= 0.246; \\ Gain(S|temperature)= 0.029; \\ Gain(S|humidity)= 0.152; \\ Gain(S|wind)= 0.049
Gain(S∣outlook)=0.246;Gain(S∣temperature)=0.029;Gain(S∣humidity)=0.152;Gain(S∣wind)=0.049
2.计算各属性的分裂信息和信息增益率：
对wind属性，取值为weak的样本有8条，取值为strong的样本有6条，则
S
p
l
i
t
E
w
i
n
d
=
−
8
14
l
o
g
2
8
14
−
6
14
l
o
g
2
6
14
=
0.985
G
a
i
n
R
a
t
i
o
w
i
n
d
=
G
a
i
n
w
i
n
d
S
p
l
i
t
E
w
i
n
d
=
0.049
0.985
=
0.0497
SplitE_{wind} = -\frac{8}{14} log_{2} \frac{8}{14} - \frac{6}{14} log_{2} \frac{6}{14} = 0.985 \\ GainRatio_{wind} = \frac{Gain_{wind}}{SplitE_{wind}} = \frac{0.049}{0.985} = 0.0497
SplitEwind=−148log2148−146log2146=0.985GainRatiowind=SplitEwindGainwind=0.9850.049=0.0497
对outlook属性，取值为overcast的样本有4条，取值为rain的样本有5条，取值为sunny的样本有5条，则
S
p
l
i
t
E
o
u
t
l
o
o
k
=
−
5
14
l
o
g
2
5
14
−
4
14
l
o
g
2
4
14
−
5
14
l
o
g
2
5
14
=
1.576
G
a
i
n
R
a
t
i
o
o
u
t
l
o
o
k
=
G
a
i
n
o
u
t
l
o
o
k
S
p
l
i
t
E
o
u
t
l
o
o
k
=
0.44
SplitE_{outlook} = -\frac{5}{14} log_{2} \frac{5}{14} - \frac{4}{14} log_{2} \frac{4}{14} - \frac{5}{14} log_{2} \frac{5}{14} = 1.576 \\ GainRatio_{outlook} = \frac{Gain_{outlook}}{SplitE_{outlook}} = 0.44
SplitEoutlook=−145log2145−144log2144−145log2145=1.576GainRatiooutlook=SplitEoutlookGainoutlook=0.44
对temperature属性，取值为cool的样本有4条，取值为hot的样本有4条，取值为mild的有6条，则
S
p
l
i
t
E
t
e
m
p
e
r
a
t
u
r
e
=
−
4
14
l
o
g
2
4
14
−
4
14
l
o
g
2
4
14
−
6
14
l
o
g
2
6
14
=
1.556
G
a
i
n
R
a
t
i
o
t
e
m
p
e
r
a
t
u
r
e
=
G
a
i
n
t
e
m
p
e
r
a
t
u
r
e
S
p
l
i
t
E
t
e
m
p
e
r
a
t
u
r
e
=
0.029
1.556
=
0.019
SplitE_{temperature} = -\frac{4}{14} log_{2} \frac{4}{14} - \frac{4}{14} log_{2} \frac{4}{14} - \frac{6}{14} log_{2} \frac{6}{14} = 1.556 \\ GainRatio_{temperature} = \frac{Gain_{temperature}}{SplitE_{temperature}} = \frac{0.029}{1.556} = 0.019
SplitEtemperature=−144log2144−144log2144−146log2146=1.556GainRatiotemperature=SplitEtemperatureGaintemperature=1.5560.029=0.019
对humidity属性，取值为high的样本有7条，取值为normal的样本有7条，则
S
p
l
i
t
E
h
u
m
i
d
i
t
y
=
−
7
14
l
o
g
2
7
14
−
7
14
l
o
g
2
7
14
=
1
G
a
i
n
R
a
t
i
o
h
u
m
i
d
i
t
y
=
G
a
i
n
h
u
m
i
d
i
t
y
S
p
l
i
t
E
h
u
m
i
d
i
t
y
=
0.152
1
=
0.152
SplitE_{humidity} = -\frac{7}{14} log_{2} \frac{7}{14} - \frac{7}{14} log_{2} \frac{7}{14} = 1 \\ GainRatio_{humidity} = \frac{Gain_{humidity}}{SplitE_{humidity}} = \frac{0.152}{1} = 0.152
SplitEhumidity=−147log2147−147log2147=1GainRatiohumidity=SplitEhumidityGainhumidity=10.152=0.152
可以看出，outlook属性的信息增益率是最大的，所以选择outlook属性作为决策树的根节点，产生3个分支，往后计算依次类推，最终得到整棵决策树。
剪枝
剪枝一般分两种方法：先剪枝和后剪枝。
先剪枝方法中通过提前停止树的构造（比如决定在某个节点不再分裂或划分训练元组的子集）而对树剪枝。一旦停止，这个节点就变成树叶，该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法，比如（1）当决策树达到一定的高度就停止决策树的生长；（2）到达此节点的实例具有相同的特征向量，而不必一定属于同一类，也可以停止生长（3）到达此节点的实例个数小于某个阈值的时候也可以停止树的生长，不足之处是不能处理那些数据量比较小的特殊情况（4）计算每次扩展对系统性能的增益，如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题，也就是说在相同的标准下，也许当前扩展不能满足要求，但更进一步扩展又能满足要求。这样会过早停止决策树的生长。
另一种C4.5更常用的方法是后剪枝，它由完全成长的树剪去子树而形成。通过删除节点的分枝并用树叶来替换它。悲观剪枝法就是其中的一种，它通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。
C4.5算法的优点与不足
优点：
- 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy），也就是熵的变化值，而C4.5用的是信息增益率。
- 在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟合overfitting。
- 对非离散数据也能处理；C4.5 选择
具有最高信息增益的划分所对应的阈值- 能够处理缺失值；即用不含缺失值的样本计算出来的信息增益率乘以它们在总样本中占的比例
缺点：信息增益比偏向取值较少的特征
原因： 当特征取值较少时分裂信息值SplitInformation(S,A)较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
CART（分类回归树）
CART算法的认识
CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法本质是生成结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：
- 将样本递归划分进行建树过程
- 用验证数据进行剪枝
CART算法的原理
上面说到了CART算法分为两个过程，其中第一个过程进行递归建立二叉树，那么它是如何进行划分的 ？
设 x 1 , x 2 , … , x n x_{1},x_{2},\dots,x_{n} x1,x2,…,xn代表单个样本的 n n n个属性， y y y表示所属类别。CART算法通过递归的方式将维的空间划分为不重叠的矩形。划分步骤大致如下
（1）选一个自变量，再选取的一个值，把维空间划分为两部分，一部分的所有点都满足，另一部分的所有点都满足，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。
（2）递归处理，将上面得到的两部分按步骤（1）重新选取一个属性继续划分，直到把整个维空间都划分完。
在划分时候有一个问题，它是按照什么标准来划分的 ？ 对于一个变量属性来说，它的划分点是一对连续变量属性值的中点。假设个样本的集合一个属性有个连续的值，那么则会有个分裂点，每个分裂点为相邻两个连续值的均值。每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用Gini系数，基尼系数越小，代表数据集的纯度越高。假设一个样本共有类，那么一个节点的Gini不纯度可定义为
G
i
n
i
(
p
)
=
∑
k
=
1
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
K
p
k
2
,
(
其
中
∑
k
=
1
K
p
k
=
1
)
Gini(p) =\sum_{k=1}^{K} p_{k}(1-p_{k}) = 1 - \sum_{k=1}^{K} p_{k}^{2}, (其中\sum_{k=1}^{K} p_{k}=1 )
Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2,(其中k=1∑Kpk=1)
其中
p
k
p_{k}
pk表示属于类的概率，当
G
i
n
i
(
A
)
=
0
Gini(A)=0
Gini(A)=0时，所有样本属于同类，所有类在节点中以等概率出现时，
G
i
n
i
(
A
)
Gini(A)
Gini(A)最大化，此时有
G
i
n
i
(
A
)
=
C
(
C
−
1
)
/
2
Gini(A) = C(C-1)/2
Gini(A)=C(C−1)/2。
有了上述理论基础，实际的递归划分过程是这样的：如果当前节点的所有样本都不属于同一类或者只剩下一个样本时，那么此节点为非叶子节点，所以会尝试样本的每个属性以及每个属性对应的分裂点，尝试找到杂质变量最大的一个划分，该属性划分的子树即为最优分支。
CART算法举例
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 晴天 | 高 | 低 | 否 | 打篮球 |
| 晴天 | 高 | 低 | 是 | 打篮球 |
| 晴天 | 中 | 低 | 否 | 打篮球 |
| 晴天 | 中 | 中 | 否 | 打篮球 |
| 晴天 | 中 | 低 | 是 | 打篮球 |
| 小雨 | 低 | 高 | 否 | 不打篮球 |
| 小雨 | 低 | 高 | 是 | 不打篮球 |
| 小雨 | 中 | 高 | 否 | 不打篮球 |
| 阴天 | 低 | 高 | 否 | 不打篮球 |
| 阴天 | 中 | 高 | 否 | 打篮球 |
| 阴天 | 中 | 低 | 是 | 打篮球 |
若以 { 晴 天 } \{晴天\} {晴天}、 { 小 雨 , 阴 天 } \{小雨,阴天\} {小雨,阴天}为分裂节点：
D1
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 晴天 | 高 | 低 | 否 | 打篮球 |
| 晴天 | 高 | 低 | 是 | 打篮球 |
| 晴天 | 中 | 低 | 否 | 打篮球 |
| 晴天 | 中 | 中 | 否 | 打篮球 |
| 晴天 | 中 | 低 | 是 | 打篮球 |
G i n i ( D 1 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( 5 / 5 ) 2 = 0 Gini(D1) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - (5/5)^{2} = 0 Gini(D1)=1−∑i=1ipi2=1−(5/5)2=0
D2
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 小雨 | 低 | 高 | 否 | 不打篮球 |
| 小雨 | 低 | 高 | 是 | 不打篮球 |
| 小雨 | 中 | 高 | 否 | 不打篮球 |
| 阴天 | 低 | 高 | 否 | 不打篮球 |
| 阴天 | 中 | 高 | 否 | 打篮球 |
| 阴天 | 中 | 低 | 是 | 打篮球 |
G i n i ( D 2 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( ( 4 / 6 ) 2 + ( 2 / 6 ) 2 ) = 0.44 Gini(D2) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - ((4/6)^{2} + (2/6)^{2}) = 0.44 Gini(D2)=1−∑i=1ipi2=1−((4/6)2+(2/6)2)=0.44
故以
{
晴
天
}
\{晴天\}
{晴天}、
{
小
雨
,
阴
天
}
\{小雨,阴天\}
{小雨,阴天}为分裂节点总的基尼系数为：
G
i
n
i
_
i
n
d
e
x
(
D
,
w
e
a
t
h
e
r
)
=
∑
i
=
1
i
∣
D
i
∣
∣
D
∣
G
i
n
i
(
D
i
)
=
5
11
G
i
n
i
(
D
1
)
+
6
11
G
i
n
i
(
D
2
)
=
0.2
Gini\_index(D,weather) = \sum_{i=1}^{i}\frac{|D^{i}|}{|D|}Gini(D^{i}) = \frac{5}{11}Gini(D1) + \frac{6}{11}Gini(D2) = 0.2
Gini_index(D,weather)=i=1∑i∣D∣∣Di∣Gini(Di)=115Gini(D1)+116Gini(D2)=0.2
若以 { 小 雨 } \{小雨\} {小雨}、 { 晴 天 , 阴 天 } \{晴天,阴天\} {晴天,阴天}为分裂节点：
D1
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 小雨 | 低 | 高 | 否 | 不打篮球 |
| 小雨 | 低 | 高 | 是 | 不打篮球 |
| 小雨 | 中 | 高 | 否 | 不打篮球 |
G i n i ( D 1 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( 3 / 3 ) 2 = 0 Gini(D1) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - (3/3)^{2} = 0 Gini(D1)=1−∑i=1ipi2=1−(3/3)2=0
D2
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 晴天 | 高 | 低 | 否 | 打篮球 |
| 晴天 | 高 | 低 | 是 | 打篮球 |
| 晴天 | 中 | 低 | 否 | 打篮球 |
| 晴天 | 中 | 中 | 否 | 打篮球 |
| 晴天 | 中 | 低 | 是 | 打篮球 |
| 阴天 | 低 | 高 | 否 | 不打篮球 |
| 阴天 | 中 | 高 | 否 | 打篮球 |
| 阴天 | 中 | 低 | 是 | 打篮球 |
G i n i ( D 2 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( ( 7 / 8 ) 2 + ( 1 / 8 ) 2 ) = 0.22 Gini(D2) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - ((7/8)^{2} + (1/8)^{2}) = 0.22 Gini(D2)=1−∑i=1ipi2=1−((7/8)2+(1/8)2)=0.22
故以
{
小
雨
}
\{小雨\}
{小雨}、
{
晴
天
,
阴
天
}
\{晴天,阴天\}
{晴天,阴天}为分裂节点总的基尼系数为：
G
i
n
i
_
i
n
d
e
x
(
D
,
w
e
a
t
h
e
r
)
=
∑
i
=
1
i
∣
D
i
∣
∣
D
∣
G
i
n
i
(
D
i
)
=
3
11
G
i
n
i
(
D
1
)
+
8
11
G
i
n
i
(
D
2
)
=
0.16
Gini\_index(D,weather) = \sum_{i=1}^{i}\frac{|D^{i}|}{|D|}Gini(D^{i}) = \frac{3}{11}Gini(D1) + \frac{8}{11}Gini(D2) = 0.16
Gini_index(D,weather)=i=1∑i∣D∣∣Di∣Gini(Di)=113Gini(D1)+118Gini(D2)=0.16
若以 { 阴 天 } \{阴天\} {阴天}、 { 晴 天 , 小 雨 } \{晴天,小雨\} {晴天,小雨}为分裂节点：
D1
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 阴天 | 低 | 高 | 否 | 不打篮球 |
| 阴天 | 中 | 高 | 否 | 打篮球 |
| 阴天 | 中 | 低 | 是 | 打篮球 |
G i n i ( D 1 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( ( 1 / 3 ) 2 + ( 2 / 3 ) 2 ) = 0.44 Gini(D1) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - ((1/3)^{2} + (2/3)^{2}) = 0.44 Gini(D1)=1−∑i=1ipi2=1−((1/3)2+(2/3)2)=0.44
D2
| 天气 | 温度 | 湿度 | 刮风 | 是否打篮球 |
|---|---|---|---|---|
| 晴天 | 高 | 低 | 否 | 打篮球 |
| 晴天 | 高 | 低 | 是 | 打篮球 |
| 晴天 | 中 | 低 | 否 | 打篮球 |
| 晴天 | 中 | 中 | 否 | 打篮球 |
| 晴天 | 中 | 低 | 是 | 打篮球 |
| 小雨 | 低 | 高 | 否 | 不打篮球 |
| 小雨 | 低 | 高 | 是 | 不打篮球 |
| 小雨 | 中 | 高 | 否 | 不打篮球 |
G i n i ( D 2 ) = 1 − ∑ i = 1 i p i 2 = 1 − ( ( 5 / 8 ) 2 + ( 3 / 8 ) 2 ) = 0.47 Gini(D2) = 1 - \sum_{i=1}^{i} p_{i}^{2} = 1 - ((5/8)^{2} + (3/8)^{2}) = 0.47 Gini(D2)=1−∑i=1ipi2=1−((5/8)2+(3/8)2)=0.47
故以
{
小
雨
}
\{小雨\}
{小雨}、
{
晴
天
,
阴
天
}
\{晴天,阴天\}
{晴天,阴天}为分裂节点总的基尼系数为：
G
i
n
i
_
i
n
d
e
x
(
D
,
w
e
a
t
h
e
r
)
=
∑
i
=
1
i
∣
D
i
∣
∣
D
∣
G
i
n
i
(
D
i
)
=
3
11
G
i
n
i
(
D
1
)
+
8
11
G
i
n
i
(
D
2
)
=
0.46
Gini\_index(D,weather) = \sum_{i=1}^{i}\frac{|D^{i}|}{|D|}Gini(D^{i}) = \frac{3}{11}Gini(D1) + \frac{8}{11}Gini(D2) = 0.46
Gini_index(D,weather)=i=1∑i∣D∣∣Di∣Gini(Di)=113Gini(D1)+118Gini(D2)=0.46
通过比较三种分裂方法最终得到的基尼系数，发现
{
小
雨
}
、
{
晴
天
,
阴
天
}
\{小雨\}、\{晴天,阴天\}
{小雨}、{晴天,阴天}的划分方法，基尼指数最小，即分裂后纯度最高。所以若我们以天气属性作为划分，那么就选择
{
小
雨
}
、
{
晴
天
,
阴
天
}
\{小雨\}、\{晴天,阴天\}
{小雨}、{晴天,阴天}的分类。
建树完成后就进行第二步了，即根据验证数据进行剪枝。在CART树的建树过程中，可能存在Overfitting，许多分支中反映的是数据中的异常，这样的决策树对分类的准确性不高，那么需要检测并减去这些不可靠的分支。决策
树常用的剪枝有事前剪枝和事后剪枝，CART算法采用事后剪枝，具体方法为代价复杂性剪枝法。
CART算法优点与不足
优点：基尼指数的计算方法，由于没有使用对数，所以运算会比对数运算要快。