数据挖掘十大经典算法之 C4.5

ID3 算法

ID3算法，即Iterative Dichotomiser 3，迭代二叉树3代

信息熵(Entropy)

信息熵(Entropy) 表示信息的混乱程度，变量的不确定性越大， 则熵值越大， 一个训练集的信息熵可以表示为：

$$Entropy(S) = - \sum _{i=1}^m P(u_i)\log_2P(u_i)$$

其中 $P(u_i) = \frac{|u_i|}{|S|}$ 表示为样本类别 i 在集合中出现的概率

信息增益(Information gain)

信息增益指的是划分前后熵的变化，可以用下面的公式表示：

$$infoGain(S,A) = Entropy(S) - \sum_{V\in Value(A)}\frac{S_V}{S}Entropy(S_V)$$

其中， A 表示样本的属性， $Value(A)$ 表示属性 A 的所有取值集合， V 是属性 A 的取值之一， $S_V$ 是 S 中 A 的值为 V 的样例集合。

ID3 算法便是每次从剩余属性集合中找出一个属性， 通过这个属性来划分集合使得信息熵增益最大。

C4.5 算法

信息增益率

$$infoGainRatio = \frac{infoGain(V)}{H(V)}$$

$$H(V)= -\sum_j{p(v_j)\log_2 p(v_j)}$$

CART

使用 Gini 基数来评估样本分布

$$Gini(S) = 1 - \sum_{i=1}^m {P_i^2}$$

$$GiniGain(S,A) = Gini(S) - \sum_{V\in Value(A)} \frac{S_V}{S} Gini(S_V)$$

[5]: C4.5决策树