四、划分选择
1、属性划分选择
构造决策树的关键是如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
常用属性划分的准则：
（1）ID3：信息增益
（2）C4.5：增益率
（3）CART：基尼指数
直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征
纯度越高意味着从这个子集中取得某个类别的样本的确定性越高，不确定性越低。
三种决策树算法ID3，C4.5 ,Cart的区别在于划分属性准则的不同。
2、信息增益
（1）信息熵
1948年，香农提出了“信息熵”(information entropy)的概念，解决了信息的量化度量问题。信息熵 是度量样本集合“纯度”最常用的一种指标。假定当前样本集合 D 中第 k 类样本所占的比例为pk，则D的信息熵定义为：
信息熵越大，信息不确定性越大，纯度越低。
（2）信息增益
信息增益：在划分数据集之前之后信息发生的变化。按照属性的特征值划分数据集，计算信息增益，获得信息增益最高的属性就是最好的选择。
计算数据集D关于属性a的信息增益，首先计算数据集D的信息熵，然后按照属性a的属性值划分成若干个子集，计算各个子集的信息熵，然后将各个子集熵进行加权，权值定义为子集样本个数对总数的占比。要想获得最大的信息增益，那么划分后的信息熵要尽量小，熵越小，数据的纯度越高，信息的不确定性越小。
举例：
（1）求信息熵：
（2）求信息增益：
以属性“色泽”为例，其对应的3个数据子集分别为：
D1(色泽=青绿)，D2(色泽=乌黑)，D3(色泽=浅白)
子集D1包含的编号为{1，4，6，10，13，17}的6个样例，其中正例占 P1 = 3/6 ，反例占 P2 = 3/6 ；D2、D3同理，3个结点的信息熵为：
属性“色泽”的信息增益为：
类似的其他的信息增益为：
显然，属性“纹理”的信息增益最大，其被选为划分属性：
对每个分支结点作进一步划分，最终得到决策树：
3、信息增益率
信息增益：对可取值数目较多的属性有所偏好（有明显弱点，例如：考虑将“编号”作为一个属性），这里引入一个新的度量——增益率。
增益率：
其中
属性 a 的可能取值数目越多 (即 V 越大)，则 IV(a) 的值（属性固有值）通常就越大。
每一个样本的编号是不同的，这时按照编号属性进行划分时，每个子集的样本只有一个，所有子集的信息熵为0，则划分后的信息熵0，该属性的信息增益是最大的，但这种划分不具备泛化能力，为了减少这种不利影响，著名的决策树算法C4.5不知用信息增益，而是用增益率。
增益率对于可能取值数目较少的属性有所偏好，因此C4.5不直接采用信息率最大的属性作为候选划分属性，而是使用一个启发式：
启发式： 先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的。
举例：
以色泽为例，
D1(色泽=青绿)={1,4,6,10,13,17}6个样例（3正，3负）
D2(色泽=乌黑)={2,3,7,8,9,15}6个样例（4正，2负）
D3(色泽=浅白)={5,11,12,14,16}5个样例（1正，4负）
信息增益率为：
4、基尼指数
CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可用基尼值来度量：
反映了从 D 中随机抽取两个样例，其类别标记不一致的概率。Gini(D) 越小，数据集 D 的纯度越高
属性 a 的基尼指数：
在候选属性集合中，选取那个使划分后基尼指数最小的属性。
在Cart决策树中，采用基尼指数作为划分属性的准则，它定义为任意两个不相同的类别的概率的乘积之和，pk表示从数据集D抽取第k个类别的概率，可以用D中第k个类别的样本占样本总数的比例进行估计。
举例：
以色泽为例，
D1(色泽=青绿)={1,4,6,10,13,17}6个样例，3个正例，3个反例
D2(色泽=乌黑)={2,3,7,8,9,15}6个样例，4个正例，2个反例
D3(色泽=浅白)={5,11,12,14,16}5个样例，1个正例，4个反例
求色泽的基尼指数：
