ID3 决策树算法存在的问题
ID3 决策树算法在特征选择时存在什么问题呢？
我们来举个例子：数据集 A 存在一个非常稀疏的特征 ID 列，我们知道 ID 是唯一不重复的，种类自然就会非常庞大。
这个时候，如果我们使用 ID 去切分数据集，那切分到最后，每个样本都会被分配到单独的样子结点上，每个样子结点的数据只有一样，不确定性为 0 ，熵值也为 0 。
那这样是不是就说名 ID 这个特征非常好呢？根据 ID 就能预测标签？当然不是，实际上 ID 这个特征毫无意义。
小鱼这里拿 ID 举例，只是个极端的例子。但足以说明，对于类似 ID 这样数据种类非常多，分布非常稀疏的特征来说，ID3 决策树算法通过信息增益来选取结点特征是远远不够的。
为了解决 ID3 决策树算法的问题，我们引入了信息增益率，计算信息增益时，考虑特征分布的自身熵。
C4.5 决策树算法 - 信息增益率
C4.5 决策树算法使用信息增益率来衡量特征节点的分类能力。所谓信息增益率就是在信息增益的基础上除以该特征自身的熵值计算而来。
为什么要除以特征自身的熵值呢？我们举个例子：还是刚才的 ID 特征，ID 特征切分完数据后的熵值为 0 ，原始数据集的熵值为 G，特征 ID 的熵值为 -n*(1/n)*log(1/n) = -log(1/n) 其中 n 为数据集样本的个数。因此，特征 ID 的熵 G2 是一个非常庞大的数值。
使用 ID 节点切分数据集之后，得到的信息增益为：G - 0 = G，信息增益非常大，分类效果堪称完美。但如果使用信息增益率去衡量，则：(G - 0)/G2，其中 G2 一定是远远大于 G 的，因为很显然标签的混乱层度远低于 ID 列的混乱层度。
因此，我们求得的信息增益率就是一个非常小的值了，这个时候就可以发现 ID 这个特征分类效果非常差。也因此 C4.5 算法很好地解决了 ID3 算法对稀疏特征衡量的不足。
CART 决策树算法 - GINI 系数
GINI 系数和熵的衡量标准类似，只是计算方式不同。GINI 系数的公式为：
当概率 P 为 0 或者 1 时，此时没有不确定性。其中概率为 1 时，GINI系数为 0 ，概率为 0 时，GINI 系数也为 0 。
总结：随机变量的不确定性越小，熵值越小，GINI 系数越小。
