数据表和决策树

数据表：有属性和结果。我们按照属性来划分决策树。

递归过程：

划分的结果如下。

怎么求当前最优划分属性？

希望分支包含的样本尽可能属于同一类别，即信息的「纯度」够高。

香农：「信息熵」，概念描述信源的不确定性，也是度量集合的纯度最常用的指标。

信息量

「信息量」：衡量不确定性的大小，需要满足：

• 不会是负数；
• 是概率的单调递减函数；
• 两个独立符号产生的不确定性应该为二者不确定性之和 $f(p_1 p_2) = f(p_1) +f(p_2)$ 。

因而取信息量为概率的负对数 $f(p) = \log \frac 1 p = -\log p$ 。

信息熵

度量集合划分方法的纯度。假如集合 $D$ 有 $N$ 类结果样本，每类样本分别占比为 $p_i, i \in \{1, 2, \cdots N\}$ 。那么 $D$ 的信息熵定义为信息量的期望：

$$ Ent(D) = -\sum_{i=1}^{N} p_i \log p_i $$

比如一个样本集合中有 3 个好瓜， 5 个坏瓜，那么信息熵为：

$$

• \left(\frac 38 \log \frac 38 + \frac 58 \log \frac 58\right) $$

二分类任务的 $N =2$ 。