• 温度
• 起风
• 下雨
• 湿度

1 0 0 1 1
1 0 1 1 0
0 1 0 0 0
1 1 0 0 1
1 0 0 0 1
1 1 0 0 1

# 信息熵与决策树的构造

## 信息熵的计算公式

$$E(P) = E(-log P_i) = -\sum_{i=1}^{n} P_i logP_i$$

出去玩 为例，首先根据公式计算出去玩的概率，从表格可知，一共6个样本数据，0出现了2次，1出现了4次，分别求两者的概率：
$P_1 = \frac{4}{2 + 4} = \frac{4}{6}$
$P_2 = \frac{2}{2 + 4} = \frac{2}{6}$
$E(o) = -\sum_{i=1}^{n} P_i logP_i = -(\frac{4}{6} log_2 \frac{4}{6}) -(\frac{2}{6} log_2 \frac{2}{6}) ≈ 0.918$

## 利用信息熵构造决策树

ID3算法是一种贪心算法，以信息熵的下降速度作为选取测试属性的标准，即在每个节点选取还尚未被用来划分的，具有最高信息增益的属性作为划分标准，然后递归这个过程，直到生成的决策树能完美分类训练样例。可以说，ID3算法的核心其实就是信息增益的计算

$$Gain(P_1,P_2) = E(P_1) - E(P_2)$$

$Gain(o,t) = 0.918 - 0.809 = 0.109​$
$Gain(o,w) = 0.918 - 0.459 = 0.459​$
$Gain(o,r) = 0.918 - 0.602 = 0.316​$
$Gain(o,h) = 0.918 - 0.874 = 0.044​$

# 相关术语与名词

## 节点杂质（node impurity）

In simple terms, let’s say you are trying to predict whether you will go out or not based on weather parameters.

If it is raining you will definitely not go. So all observations at this point are ‘No’ i.e. pure node

While if is is not raining you will check weather temperature is below 20 C then “yes” else “no”. This node is impure node.

You can measure this impurity based on metric of your choice. Thus deciding how you split the variables (concept from decision trees https://www.youtube.com/watch?v=Zze7SKuz9QQ)

You can choose your impurity measure based on requirement as Peter has suggested.

## 基尼不纯度（Gini Impurity）

$$I_G(f)=\sum_{i=1}^mf_i(1-f_i)=\sum_{i=1}^mf_i-\sum_{i=1}^mf_i^2=1-\sum_{i=1}^mf_i^2​$$

1. 显然基尼不纯度越小，纯度越高，集合的有序程度越高，分类的效果越好；
2. 基尼不纯度为 0 时，表示集合类别一致；
3. 基尼不纯度最高（纯度最低）时,$f_1=f_2=\ldots =f_m=\frac1m$,$I_G(f)=1-(\frac1m)^2\times m=1-\frac1m$

0%