决策树算法中基尼指数与信息增益的比较

问题提出

在自己实现决策树算法的时候，发现生成的id3树和cart树一模一样。竟然每个决策节点都选择了同一属性的同一划分。这让我很意外，于是改变了随机种子值，改变训练集的大小，结果发现无一例外它们都是一样的。由此我提出了一个疑问：基尼指数和信息增益是等价的吗？
如果等价，那干嘛还要两个算法？如果不等价，为什么生成的树总是一样的呢？

二者比较

直接取iris数据集中的一部分作为训练集，并指定一个属性作为判断标准。列出一系列对该属性的划分，同时用基尼指数和信息增益作为判断标准进行评价，以此比较两者的区别（此例中训练集大小为100个样本，对0号属性“sepal length”进行划分）

ent为信息增益，gini为基尼指数。同时为了便于观察，引入了$1-gini$1−gini，这样它与ent的意义就更接近：越大越好。
如果说信息增益和基尼指数等价的话，那么对于每一个划分，两者对于它的评价应该是一致的。这并不意味着它们的数值相等，而是指它们的偏序关系是一致的：如果信息增益认为划分A比划分B好，那么基尼指数也能推出划分A比划分B好。简而言之，它们对一组划分的排序应该是完全一致的。
所以我们想找的反例就是信息增益认为划分A比划分B好，但基尼指数却得到相反的结论。
从图中我们可看到，大体上两种标准的趋势是一样的。似乎只要将它们进行y轴上的放缩，就能得到一个不错的拟合。但实际上，如红色箭头标注的那样，两种标准不是完全一致的。信息增益的同时，基尼指数却没有明显提升。可见，它们不是等价的。
但是它们对于最高点，也就是最优划分的判断是一致的。这又引起人的思考，是不是它们只是在局部有细微差别，但是对最优划分却总是一致呢？

进一步寻找反例

经过不断地试探，我找到了一组合适的反例：

属性值	4.4	5.0	5.1	5.1	6.0	6.0	6.1	6.1	6.1	6.3	6.3	6.4	6.5	6.8	6.8	7.7
类别	0	1	0	0	2	1	1	1	2	2	2	2	2	2	2	2

记原始数据集$D\,$D的信息熵为$E_{0}$E0​
现在考虑两个划分：
$Dv_{1}$Dv1​ ：属性值$\le 5.55$≤5.55和$\gt 5.55$>5.55，相应的信息增益记为$E_{1}$E1​，基尼指数为$G_{1}$G1​
$Dv_{2}$Dv2​ ：属性值$\le 6.2$≤6.2和$\gt 6.2$>6.2，相应的信息增益记为$E_{2}$E2​，基尼指数为$G_{2}$G2​
经过计算得到：
$E_{0}=1.41973671$E0​=1.41973671
$E_{1}=0.60845859, \quad G_{1}=0.375$E1​=0.60845859,G1​=0.375
$E_{2}=0.55883437, \quad G_{2}=0.36111111$E2​=0.55883437,G2​=0.36111111
而且$E_{1}$E1​是所有划分中信息增益的最大值，$G_{2}$G2​是所有划分中基尼指数的最小值
这就是我们想要的反例：按信息增益，划分$Dv_{1}$Dv1​优于$Dv_{2}$Dv2​ ，但按基尼指数$Dv_{2}$Dv2​优于$Dv_{1}$Dv1​，同时它们都是划分集里的极值，以此形成的id3树和cart树将会不同

思考

现在，我们已经确定信息增益和基尼指数不是等价的，而且id3树和cart树不一定总是一样的。但我们还需要进一步思考，造成此种现象的原因。
回顾定义：
$Ent(D)=-\sum^{d}_{k=1}p_{k}\log_{2}p_{k}\\ Gini(D)=1-\sum^{d}_{v=1}p_{v}^{2}$Ent(D)=−k=1∑d​pk​log2​pk​Gini(D)=1−v=1∑d​pv2​
信息熵和基尼指数都能反映一个集合的纯度，且集合为单一类别时，两者皆为0；集合中每个元素都取自不同类时，两者都取最大值。
刚才的例子中划分$Dv_{1}$Dv1​ 将集合划分为两个子集$S_{11},S_{12}$S11​,S12​

属性值	4.4	5.0	5.1	5.1
类别	0	1	0	0

属性值	6.0	6.0	6.1	6.1	6.1	6.3	6.3	6.4	6.5	6.8	6.8	7.7
类别	2	1	1	1	2	2	2	2	2	2	2	2

$S_{11}$S11​的信息增益、基尼系数分别为$E_{s11}=0.81127812, \quad G_{s11}=0.375$Es11​=0.81127812,Gs11​=0.375
$S_{12}$S12​的信息增益、基尼系数分别为$E_{s12}=0.81127812, \quad G_{s12}=0.375$Es12​=0.81127812,Gs12​=0.375
$E_{1}=E_{0}-\frac{4}{16}E_{s11}-\frac{12}{16}E_{s12}, \quad G_{2}=\frac{4}{16}G_{s11}+\frac{12}{16}G_{s12}$E1​=E0​−164​Es11​−1612​Es12​,G2​=164​Gs11​+1612​Gs12​

划分$Dv_{2}$Dv2​ 将集合划分为两个子集$S_{21},S_{22}$S21​,S22​

属性值	4.4	5.0	5.1	5.1	6.0	6.0	6.1	6.1	6.1
类别	0	1	0	0	2	1	1	1	2

属性值	6.3	6.3	6.4	6.5	6.8	6.8	7.7
类别	2	2	2	2	2	2	2

$S_{22}$S22​只包含一个类，信息熵和基尼系数都为0.
$S_{21}$S21​的信息增益、基尼系数分别为$E_{s21}=1.53049305, \quad G_{s21}=0.64197531$Es21​=1.53049305,Gs21​=0.64197531
$E_{2}=E_{0}-\frac{9}{16}E_{s21}, \quad G_{2}=\frac{9}{16}G_{s21}$E2​=E0​−169​Es21​,G2​=169​Gs21​
从中我们可以看到$E_{s11},\,E_{s12} \lt E_{s21} \quad G_{s11},\,G_{s12} \lt G_{s21}$Es11​,Es12​<Es21​Gs11​,Gs12​<Gs21​
也就是说两种判断方式都认为$S_{11},S_{12}\,$S11​,S12​比$S_{21}\,$S21​更纯，但为什么$E_{1} \gt E_{2}\,$E1​>E2​而$\,G_{1} \gt G_{2}$G1​>G2​呢？
我们注意到$E_{s11}\,$Es11​与$E_{s21}\,$Es21​的差距比$G_{s11}\,$Gs11​与$G_{s21}\,$Gs21​的差距更大，也就是说$S_{21}$S21​的混乱状态在熵中得到了更好的表示，被$\frac{9}{16}$169​削弱之后还能显示出混乱，但基尼系数对$S_{21}$S21​的混乱状态描述得不够充分，被$\frac{9}{16}$169​削弱之后则显示为更优。
我们看看信息熵和基尼系数的最大值：
$Ent(D)=-\sum^{n}_{k=1}\frac{1}{n}\log_{2}{\frac{1}{n}} =\log_{2}{n} \\ Gini(D)=1-\sum^{n}_{v=1}\frac{1}{n^{2}}=\frac{n-1}{n}$Ent(D)=−k=1∑n​n1​log2​n1​=log2​nGini(D)=1−v=1∑n​n21​=nn−1​
这时，我们就可以明显感觉到：当集合越是混乱的时候，基尼系数对这种趋势的表现越不够充分。相比之下，信息熵则更能区分出混乱和更混乱。

结论

1. 信息增益和基尼指数不是等价的
2. 大多数时候它们的区别很小
3. 信息增益对较混乱的集合有很好的表现力，但是基尼指数有所欠缺。另一方面，这也说明较纯的集合，基尼指数可能会区分得更清楚