今天以周志华老师的西瓜为例，复盘一下三种决策树算法。
文章目录
信息增益（ID3算法）信息增益比率（C4.5算法）基尼指数（CART算法）数据：
信息增益（ID3算法）
信息熵表示信息的混乱程度，熵越大数据越混乱。分类的目的是为了使同一类别的数据尽可能“纯净”，因此追求尽量小的信息熵。
信息增益表示分类前后信息熵的差值。分类前信息熵是定值，分类后信息熵越小，信息增益越大。因此我们追求尽量大的信息增益值。
entropy(D)表示未分类时数据D的信息熵:
entropy(D)=−∑i=1kp(ci)log2p(ci)entropy(D)=-\sum_{i=1}^k p(c_i)log_2p(c_i)entropy(D)=−i=1∑kp(ci)log2p(ci)
其中，cic_ici表示样本的分类变量取i的概率。
entropy(D,A)表示按照属性A分类后数据D的信息熵：
entropy(D,A)=∑i=1m∣Di∣∣D∣entropy(Di)entropy(D,A)=\sum_{i=1}^m\frac{|D_i|}{|D|}entropy(D_i)entropy(D,A)=i=1∑m∣D∣∣Di∣entropy(Di)
其中，∣Di∣∣D∣\frac{|D_i|}{|D|}∣D∣∣Di∣表示样本的描述变量A取DiD_iDi的概率。
信息增益即信息熵的差值:
gain(D,A)=entropy(D)−entropy(D,A)gain(D,A)=entropy(D)-entropy(D,A)gain(D,A)=entropy(D)−entropy(D,A)
以西瓜为例，分类变量为是否为好瓜，描述变量为前面6个属性。
entropy(D)=−817log2817−917log2917=0.998entropy(D)=-\frac{8}{17}log_2\frac{8}{17}-\frac{9}{17}log_2\frac{9}{17}=0.998entropy(D)=−178log2178−179log2179=0.998
entropy(D,色泽)=−617entropy(青绿)−617entropy(乌黑)−517entropy(浅白)=−617[−36log236−36log236]−617[−46log246−26log226]−517[−15log215−45log245]=0.889\begin{aligned} entropy(D,色泽)&=-\frac{6}{17}entropy(青绿)-\frac{6}{17}entropy(乌黑)-\frac{5}{17}entropy(浅白)\\[2ex] &=-\frac{6}{17}[-\frac{3}{6}log_2\frac{3}{6}-\frac{3}{6}log_2\frac{3}{6}]-\frac{6}{17}[-\frac{4}{6}log_2\frac{4}{6}-\frac{2}{6}log_2\frac{2}{6}]-\frac{5}{17}[-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2{4}{5}]\\[2ex] &=0.889 \end{aligned}entropy(D,色泽)=−176entropy(青绿)−176entropy(乌黑)−175entropy(浅白)=−176[−63log263−63log263]−176[−64log264−62log262]−175[−51log251−54log245]=0.889
gain(D,色泽)=entropy(D)−entropy(D,色泽)=0.109gain(D,色泽)=entropy(D)-entropy(D,色泽)=0.109gain(D,色泽)=entropy(D)−entropy(D,色泽)=0.109
同理，计算其他属性的信息增益，最终得出“纹理”的信息增益最大，因此选择它作为分裂属性。
信息增益比率（C4.5算法）
由信息熵的计算公式可以看出，信息增益有一个先天缺陷：更倾向于选取分类个数多的属性。若有一个分类变量，对每一个样本都取不同值，那么每个样本为一个类别，每个类别的信息熵都是0，信息熵最小，但显然是不合理的。因此，提出信息增益比率进行调整。
gain_ratio(D,A)=gain(D,A)splitInfo(D,A)gain\_ratio(D,A)=\frac{gain(D,A)}{splitInfo(D,A)}gain_ratio(D,A)=splitInfo(D,A)gain(D,A)
spliInfo(D,A)=−∑i=1m∣Di∣∣D∣log2(∣Di∣∣D∣)spliInfo(D,A)=-\sum_{i=1}^m\frac{|D_i|}{|D|}log_2(\frac{|D_i|}{|D|})spliInfo(D,A)=−i=1∑m∣D∣∣Di∣log2(∣D∣∣Di∣)
信息增益比率即信息增益除以一个“分类信息熵”，这个分母其实就是把描述变量A当做分类变量时计算得出的信息熵值。可以看出，类别越多，分类信息熵越大。
还是以西瓜为例：
spliInfo(D,色泽)=−617log2617−617log2617−517log2517=0.613spliInfo(D,色泽)=-\frac{6}{17}log_2\frac{6}{17}-\frac{6}{17}log_2\frac{6}{17}-\frac{5}{17}log_2\frac{5}{17}=0.613spliInfo(D,色泽)=−176log2176−176log2176−175log2175=0.613
gain_ratio=0.1090.613=0.178gain\_ratio=\frac{0.109}{0.613}=0.178gain_ratio=0.6130.109=0.178
类似的可以计算出其他属性的信息增益比率。
需要注意的是，增益率对类别数量少的属性有所偏好，因此，C4.5算法并不直接选择增益率最大的属性进行分裂，而是先选出信息增益高于平均水平的属性，在从这些属性中选择信息增益率最高的，其实就是对两种方法的缺点进行了一下权衡。
基尼指数（CART算法）
值得一提的是，CART算法要求决策树为二叉树，当分类变量大于2个的时候，将一个类别视为一类，其余类别视为另一类，计算基尼指数选取最优的划分方法。
基尼指数表示随机抽取两个样本，分类变量值不一致的概率，概率越大表示纯度越低。因此，追求的基尼指数越小越好。
Gini(D)=∑i=1kpk(1−pk)=1−∑i−1kpk2Gini(D)=\sum_{i=1}^kp_k(1-p_k)=1-\sum_{i-1}^kp_k^2Gini(D)=i=1∑kpk(1−pk)=1−i−1∑kpk2
按照描述变量A进行分类后，基尼指数为：
Gini(D,A)=∑i=1m∣Di∣∣D∣Gini(Di)Gini(D,A)=\sum_{i=1}^m\frac{|D_i|}{|D|}Gini(D_i)Gini(D,A)=i=1∑m∣D∣∣Di∣Gini(Di)
再看西瓜的例子：
以色泽分类后，基尼指数
Gini(D,色泽)=617Gini(青绿)+617Gini(乌黑)+517(浅白)=617[1−(36)2−(36)2]+617[1−(46)2−(26)2]+517[1−(15)2−(45)2]\begin{aligned} Gini(D,色泽)&=\frac{6}{17}Gini(青绿)+\frac{6}{17}Gini(乌黑)+\frac{5}{17}(浅白)\\[2ex] &=\frac{6}{17}[1-(\frac{3}{6})^2-(\frac{3}{6})^2]+\frac{6}{17}[1-(\frac{4}{6})^2-(\frac{2}{6})^2]+\frac{5}{17}[1-(\frac{1}{5})^2-(\frac{4}{5})^2] \end{aligned}Gini(D,色泽)=176Gini(青绿)+176Gini(乌黑)+175(浅白)=176[1−(63)2−(63)2]+176[1−(64)2−(62)2]+175[1−(51)2−(54)2]
同理算出其他属性的GIni指数，选取最小的作为分类属性即可。
手动复盘，如有错误，敬请指正。
