目录

决策树公式

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：决策树

5. 信息增益举例

机器学习笔记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 \\
\]

按不同字段分割,计算结果如下：
机器学习笔记5：决策树

决策树特征的重要性

计算决策树特征重要性的步骤：

假设数据有M个特征,使用信息熵来决定每一个分叉的情况：

  1. 初始化一个数组A[],长度为M,所有的值都为0.
  2. 遍历树的每一个节点:
  • 假设某一个分叉点是基于第m个(0<=m<=M)特征来分叉的;
  • 假设这一节点分叉造成的信息熵减小值为e;
  • 假设训练数据中通过这个分叉的数据个数为d;
  • 令A[m]+=d*e;
  1. 假设数组A[]中所有的值求和为S,将数值A[]中的每个元素除以S
  2. 最终数组A[]中第m个元素的值就是数据中第m个特征的重要性.
  • 注意:决策树的特征重要性是取决于特定数据集的,即使同一棵树,换了一个数据集,特征重要性也会改变.

随机森林

集成学习

同时训练多个决策树,预测的时候,综合考虑多个结果预测.例如取多个结果的均值,众数

随机性体现在两点：

  1. 从原来的数据集随机(带放回)取一个子集作为森林中某一个决策树的训练数据集
  2. 每一次选择分叉的特征时,限定为在随机选择的特征的子集中寻找一个特征

有两个优势：

  • 消除了决策树容易过拟合的缺点
  • 减小了预测的variance:预测值不会因为训练数据的小变化而剧烈变化