> For the complete documentation index, see [llms.txt](https://book.zimmem.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://book.zimmem.com/shu-ju-chu-li/default-2/c4.5.md).

# 数据挖掘十大经典算法之 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决策树](http://www.cnblogs.com/zhangchaoyang/articles/2842490.html)