决策树--ID3算法

决策树–ID3算法

概念

（1）信息熵

$$Entropy(x)=-\sum _i^{N_{class}}P(x_i)lo{g}_{2}P(x_i)$$

假设只有2个类别（N=2），$ P(x_i) $在【0，1】之间，$log_2 P(x_i) $ 小于0，因此Entropy(x) 大于0；
当两类别概率分别0.5，0.5的时候（样本均匀）信息熵最大，此时纯度最低；当分别为1，0的时候信息熵最小，此时纯度最高；
因此，信息熵表示不确定性（混乱程度），纯度最低的时候混乱性最大。

息增益指的就是划分可以带来纯度的提高，信息熵的下降。

（2）信息增益

决策树划分需要往数据纯度提高的方向进行才能正确识别样本，即信息熵变小的方向，假设划分前的信息熵为$S$，根据特征$T$划分后的信息熵为$S_T$，则$S_T$的值应该最小，即$S-S_T$的值（信息增益）应该最大；
即信息增益最大的时候划分的数据越纯；
信息增益的计算公式为：
$$Gain(S,T)=Entropy(S)-\sum _{v\in T}\frac{|S_v|}{|S|}Entropy(|S_v|)$$
其中，$v$为特征$T$的取值，当$v$为特征$T_1$时，一共有样本数目为$|S_v|$，该集合的信息熵为$Entropy(|S_v|)$