目录
决策树公式
1.信息熵
\[ H(X)=-\sum_{i=1}^{n}P(X=i)log_{2}P(X=i) \]
2.条件熵
\[ H(X|Y)=-\sum_{v\in values(Y)}P(Y=v)H(X|Y=v) \\ H(X|Y=v)=-\sum_{i=1}^{n}P(X=i|Y=v)log_{2}P(X=i|y=v) \]
3.信息增益
\[ I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X) \]
我们通常会选择信息增益最大的作为分割特征。
4. 信息熵举例
5. 信息增益举例
决策树举例
表格
| Outlook | Temperature | Humidity | Windy | PlayGoIf? |
|---|---|---|---|---|
| sunny | 85 | 85 | FALSE | no |
| sunny | 80 | 90 | TRUE | no |
| overcast | 83 | 86 | FALSE | yes |
| rainy | 70 | 96 | FALSE | yes |
| rainy | 68 | 80 | FALSE | yes |
| rainy | 65 | 70 | TRUE | no |
| overcast | 64 | 65 | TRUE | yes |
| sunny | 72 | 95 | FALSE | no |
| sunny | 69 | 70 | FALSE | yes |
| rainy | 75 | 80 | FALSE | yes |
| sunny | 75 | 70 | TRUE | yes |
| overcast | 72 | 90 | TRUE | yes |
| overcast | 81 | 75 | FALSE | yes |
| rainy | 71 | 95 | TRUE | no |
预设
将Temperature按如下规格分为三类：
HOT:[80-90)
Middle:[70,80)
Cool:[60,70)
(很显然这里的温度用的不是摄氏度)
将湿度按如下规格分为两类：
High：>=85
Normal: <85
手动计算
选择Play Golf为父节点,那么
| PlayGoIf? | Frequency | P | Entropy |
|---|---|---|---|
| Yes | 5 | 0.36 | -0.531 |
| No | 9 | 0.64 | -0.410 |
| 14 | 0.940 |
其中,比如Yes的概率,就是根据上面的公式算出来的:
\[ E(Yes)=0.36\times log_{2}{0.36}\approx -0.531 \\ E(No)=0.64\times log_{2}{0.64}\approx -0.410 \\ H(X)=-E(Yes)-E(No)=0.940 \\ \]
按不同字段分割,计算结果如下：
决策树特征的重要性
计算决策树特征重要性的步骤：
假设数据有M个特征,使用信息熵来决定每一个分叉的情况：
- 初始化一个数组A[],长度为M,所有的值都为0.
- 遍历树的每一个节点:
- 假设某一个分叉点是基于第m个(0<=m<=M)特征来分叉的;
- 假设这一节点分叉造成的信息熵减小值为e;
- 假设训练数据中通过这个分叉的数据个数为d;
- 令A[m]+=d*e;
- 假设数组A[]中所有的值求和为S,将数值A[]中的每个元素除以S
- 最终数组A[]中第m个元素的值就是数据中第m个特征的重要性.
- 注意:决策树的特征重要性是取决于特定数据集的,即使同一棵树,换了一个数据集,特征重要性也会改变.
随机森林
集成学习
同时训练多个决策树,预测的时候,综合考虑多个结果预测.例如取多个结果的均值,众数
随机性体现在两点：
- 从原来的数据集随机(带放回)取一个子集作为森林中某一个决策树的训练数据集
- 每一次选择分叉的特征时,限定为在随机选择的特征的子集中寻找一个特征
有两个优势：
- 消除了决策树容易过拟合的缺点
- 减小了预测的variance:预测值不会因为训练数据的小变化而剧烈变化