决策树--ID3算法
决策树–ID3算法
概念
（1）信息熵
E n t r o p y ( x ) = − ∑ i N c l a s s P ( x i ) l o g 2 P ( x i ) Entropy(x) = -\sum_{i}^{N_{class}}P(x_i)log_2 P(x_i) Entropy(x)=−i∑NclassP(xi)log2P(xi)
假设只有2个类别（N=2），$ P(x_i) 在【 0 ， 1 】之间， 在【0，1】之间， 在【0，1】之间，log_2 P(x_i) $ 小于0，因此Entropy(x) 大于0；
当两类别概率分别0.5，0.5的时候（样本均匀）信息熵最大，此时纯度最低；当分别为1，0的时候信息熵最小，此时纯度最高；
因此，信息熵表示不确定性（混乱程度），纯度最低的时候混乱性最大。
息增益指的就是划分可以带来纯度的提高，信息熵的下降。
（2）信息增益
决策树划分需要往数据纯度提高的方向进行才能正确识别样本，即信息熵变小的方向，假设划分前的信息熵为 S S S，根据特征 T T T划分后的信息熵为 S T S_{T} ST，则 S T S_{T} ST的值应该最小，即 S − S T S-S_{T} S−ST的值（信息增益）应该最大；
即信息增益最大的时候划分的数据越纯；
信息增益的计算公式为：
G a i n ( S , T ) = E n t r o p y ( S ) − ∑ v ∈ T ∣ S v ∣ ∣ S ∣ E n t r o p y ( ∣ S v ∣ ) Gain(S, T) = Entropy(S) -\sum_{v\in T }^{} \frac{|S_v|}{|S|} Entropy(|S_v|) Gain(S,T)=Entropy(S)−v∈T∑∣S∣∣Sv∣Entropy(∣Sv∣)
其中， v v v为特征 T T T的取值，当 v v v为特征 T 1 T_1 T1时，一共有样本数目为 ∣ S v ∣ |S_v| ∣Sv∣，该集合的信息熵为 E n t r o p y ( ∣ S v ∣ ) Entropy(|S_v|) Entropy(∣Sv∣)