决策树分支属性的三种选择方法

决策树算法的核心就是划分属性的选择，按照最优划分属性选择方法的不同可以把决策树算法分为ID3、C4.5和CART算法。本质上来说，决策树的构建过程 就是一个熵减的过程，也就是集合混乱度贬低，纯度变高的过程。要刻画集合的混乱程度，可以使用以下两个公式，这两个公式计算出来的值越小就说明集合的混乱度越低，纯度越高，反之亦反之。记是集合中第种取值的占比：

1. 信息熵

2. 基尼指数

针对某个特定的属性，他可能有很多取值，我们就可以按照样本在这个属性上取值的不同把集合拆分为许多小的集合，对于这些小的集合，我们同样可以使用 上面两个公式去计算它们的混乱程度或，然后加权得到或。根据或就可以找到针对集合的最优划分属性是谁，用第一种思路的就是ID3算法，用第二种思路的就是CART算法。而C4.5算法则是的改进，在其基础上除以一个和子集合大小相关的值消除集合大小的干扰。

话不多说，看一个例子，使用CART(classification and regression tree)算法画出下面这个问题的决策树：

按工作，我们可以把当前集合分为两组，记作，计算它们的混乱度以及使用工作作为划分属性划分后得到节点的平均混乱度：

按房子，我们可以把当前集合分为两组，记作，计算它们的混乱度以及使用工作作为划分属性划分后得到节点的平均混乱度：

按信誉，我们可以把当前集合分为三组，记作，计算它们的混乱度以及使用工作作为划分属性划分后得到节点的平均混乱度：

可以看到对于当前集合使用房子属性划分后的平均混乱度最低，所以选择房子属性作为当前集合的最佳划分属性。得到如下决策树结构：

继续使用上面的方法对得到的新集合进行划分即可，不再赘述了，思想就是这个思想。