1.介绍
ID3树与CART树的区别：
ID3算法中，选择的是信息增益来进行特征选择，信息增益大的特征优先选择。而在C4.5中，选择的是信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的缺点。但是无论是ID3还是C4.5，都是基于熵的模型，里面会涉及到大量的对数运算，能不能简化一下？ GINI系数的计算公式：
假设有数据集D，定义GINI指数：
G
I
N
I
(
D
)
=
∑
i
=
1
k
p
k
⋅
(
1
−
p
k
)
=
1
−
∑
i
=
1
k
p
k
2
GINI\left( D \right)=\; \sum_{i=1}^{k}{p_{k}}\cdot \left( 1-p_{k} \right)=1-\sum_{i=1}^{k}{p_{k}}^{2}
GINI(D)=i=1∑kpk⋅(1−pk)=1−i=1∑kpk2 记住上面的公式我们会在后面计算的时候用到简单分析：
从公式中可以看出来，基尼指数的意义是从数据集D中随机抽取两个样本类别标识不一致的概率。基尼指数越小，数据集的纯度越高。相比于信息增益，信息增益比等作为特征选择方法，基尼指数省略了对数计算，运算量比较小，也比较容易理解，所以CART树选择使用基尼系数用来做特征选择。
2.GINI系数计算过程
首先给出一个数据集D，这是一个关于是否出门的数据集，最后一列是决策列，即标签列，我们希望通过前面的一系列特征来决策最终会不会出去玩。下面我们就逐个计算每个特征的GINI系数。从而来决定选用哪个特征来作为第一个分支节点。值得注意的是，Cart树是一个二叉树，所以在计算Gini系数的时候，还要考虑，要以哪个特征值作为切分。这个也是区别于ID3 和C4.5算法的一点。假设我们按顺序计算。
DayOutlookTemp.HumidityWindDecision
1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo
2.1 计算OutLook的Gini系数
首先我们在D数据集中选择出OutLook列的一些数据情况。看下面的表是经过统计得来的：
每个特征值对应的累呗的个数，以及总的个数，我们需要这个。回忆一下计算公式：
G
i
n
i
=
1
−
∑
i
=
1
k
p
k
2
Gini =1-\sum_{i=1}^{k}{p_{k}}^{2}
Gini=1−∑i=1kpk2
OutlookYesNoNumber of instances
Sunny235Overcast404Rain325
开始计算：
G
i
n
i
(
O
u
t
l
o
o
k
=
S
u
n
n
y
)
=
1
−
{
(
2
5
)
2
+
(
3
5
)
2
}
=
0.48
Gini(Outlook =Sunny)=1-\{(\frac{2}{5})^2+(\frac{3}{5})^2 \}=0.48
Gini(Outlook=Sunny)=1−{(52)2+(53)2}=0.48
G
i
n
i
(
O
u
t
l
o
o
k
=
O
v
e
r
C
a
s
t
)
=
1
−
{
(
4
4
)
2
+
(
0
4
)
2
}
=
0
Gini(Outlook =OverCast)=1-\{(\frac{4}{4})^2+(\frac{0}{4})^2 \}=0
Gini(Outlook=OverCast)=1−{(44)2+(40)2}=0
G
i
n
i
(
O
u
t
l
o
o
k
=
R
a
i
n
)
=
1
−
{
(
3
5
)
2
+
(
2
5
)
2
}
=
0.48
Gini(Outlook =Rain)=1-\{(\frac{3}{5})^2+(\frac{2}{5})^2 \}=0.48
Gini(Outlook=Rain)=1−{(53)2+(52)2}=0.48好，现在我们已经计算了每个特征值对应Gini系数了，下面就可以依据这个来计算特征OutLook的Gini系数了，这个过程比较简单了，就是将上面的计算结果，结合数据集中的分量俩进行累加，即可：
G
i
n
i
(
O
u
t
l
o
o
k
)
=
5
14
⋅
G
i
n
i
(
O
u
t
l
o
o
k
=
S
u
n
n
y
)
+
4
14
⋅
G
i
n
i
(
O
u
t
l
o
o
k
=
O
v
e
r
C
a
s
t
)
+
5
14
⋅
G
i
n
i
(
O
u
t
l
o
o
k
=
R
a
i
n
)
=
0.342
Gini(Outlook)=\frac{5}{14}\cdot Gini(Outlook =Sunny)+\frac{4}{14}\cdot Gini(Outlook =OverCast)+\frac{5}{14}\cdot Gini(Outlook =Rain)=0.342
Gini(Outlook)=145⋅Gini(Outlook=Sunny)+144⋅Gini(Outlook=OverCast)+145⋅Gini(Outlook=Rain)=0.342最终计算得到的结果：
G
i
n
i
(
O
u
t
l
o
o
k
)
=
0.342
Gini(Outlook)=0.342
Gini(Outlook)=0.342
2.2 迭代计算
经过上面的计算，我想我已经很清楚的表达了如何计算了，下面简单描述计算过程：
1.遍历所有特征，假如当前选择的特征为OutLook2.遍历OutLook下所有的特征值。3.统计每个特征值的数量，以及对应的每个特征值的分类的个数。Yes = 2,No=34.计算每个特征值的Gini系数。5.加权求和计算该特征的Gini系数。 根据上面的过程依次可以计算出每个特征对应的Gini系数：
G
i
n
i
(
O
u
t
l
o
o
k
)
=
0.342
G
i
n
i
(
T
e
m
p
.
)
=
0.439
G
i
n
i
(
H
u
m
i
d
i
t
y
)
=
0.367
G
i
n
i
(
W
i
n
d
)
=
0.428
Gini(Outlook)=0.342\\ Gini(Temp.)=0.439\\ Gini(Humidity)=0.367\\ Gini(Wind)=0.428\\
Gini(Outlook)=0.342Gini(Temp.)=0.439Gini(Humidity)=0.367Gini(Wind)=0.428此时已经得到了每个特征的Gini系数，下一步就是比较系数然后进行分裂了。
2.3排序后分裂
根据上面已经计算出来的结果，排序就很简单了，不多说。排序后我们选择Gini系数最小的OutLook来进行分裂。分裂过程：
1.选择OutLook这个特征进行分裂。2.我们前面说了Cart树都是二叉树，那么分裂的时候还要继续选择一个分裂点，而不是选择每个分割点。3.根据上面对每个分点的计算结果可以指定OverCast的Gini系数最小为0，因此选择overCast作为切分点。4.将原始的数据集D切分成两个数据子集，迭代计算剩余特征的Gini系数和最佳切分点。5.对后续子集迭代建树，直到满足停止条件。
