概述
决策树(Decision Tree)是一种非参数的有监督学习方法,它是一种树形结构,所以叫决策树。它能够从一系列有特征和标签的数据中总结出决策规则,并用树状图的结构来呈现这些规则,以解决分类和回归问题。决策树算法容易理解,适用各种数据,在解决各种问题时都有良好表现,尤其是以树模型为核心的各种集成算法,在各个行业和领域都有广泛的应用。
决策树的核心有三种算法:
ID3:ID3 是最早提出的决策树算法,他就是利用信息增益来选择特征的。
C4.5:他是 ID3 的改进版,他不是直接使用信息增益,而是引入“信息增益比”指标作为特征的选择依据。
CART:这种算法即可以用于分类,也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。
ID3算法是本教程的重点要讲的内容,其余两种算法将会后续推出。
数据集
下面举个例子,会使用ID3算法帮助我们判断今天的天气适不适合出去打球。
进行判断之前,需要历史天气数据和打球活动数据,以下为历史数据集S。
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D1 | 晴朗 | 热 | 湿 | 弱 | 否 |
D2 | 晴朗 | 热 | 湿 | 强 | 否 |
D3 | 大雨 | 热 | 湿 | 弱 | 是 |
D4 | 小雨 | 中等 | 湿 | 弱 | 是 |
D5 | 小雨 | 凉爽 | 正常 | 弱 | 是 |
D6 | 小雨 | 凉爽 | 正常 | 强 | 否 |
D7 | 大雨 | 凉爽 | 正常 | 强 | 是 |
D8 | 晴朗 | 中等 | 湿 | 弱 | 否 |
D9 | 晴朗 | 凉爽 | 正常 | 弱 | 是 |
D10 | 小雨 | 中等 | 正常 | 弱 | 是 |
D11 | 晴朗 | 中等 | 正常 | 强 | 是 |
D12 | 大雨 | 中等 | 湿 | 强 | 是 |
D13 | 大雨 | 热 | 正常 | 弱 | 是 |
D14 | 小雨 | 中等 | 湿 | 强 | 否 |
ID3算法
ID3算法会选择当前信息增益最大的特征作为树中新的节点。计算过程如下:
步骤1
假设S
为完整的数据集,数据标签(数据类别)共有n
个类别,分别为C1,...,Cn
。Si
对应Ci
类别下数据子集,因此,数据集S
的信息熵计算如下:
\]
其中,pi
是数据样本为Ci
的概率,因此:
\]
|Si|
是类别Ci在数据集S中的数据数量,|S|
是数据集S中的数据数量。
步骤2
假设特征A
有k
种不同的取值,根据特征A
,一定条件下的数据集S可以分为k个子集{S1,...,Sk}
,因此,数据集S的信息熵可以按照如下方式计算:
\]
步骤3
假设数据集S根据特征A不同的取值分为众多子集,则信息增益的计算为:
\]
计算数据集中每一个特征的信息增益,如Gain(S,B), Gain(S,C)
等,选取信息增益最大的特征作为树中新的节点。
计算信息增益
天气的各个属性如上图所示,它们所有可能的值如下所示:
- 天气:晴朗、小雨、大雨
- 气温:热、中等、凉爽
- 湿度:正常、湿
- 风力:弱、强
同时,S中有14天的历史天气和活动数据,其中,打球的有9天,不打球的5天,因此数据集S的熵可以计算为:
\]
现在我们开始计算每一列的信息增益。
对于天气列,有晴朗
、小雨
、大雨
三种情况,根据三种情况划分对应的数据子集。
当天气为晴朗
时,涉及到的数据如下:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D1 | 晴朗 | 热 | 湿 | 弱 | 否 |
D2 | 晴朗 | 热 | 湿 | 强 | 否 |
D8 | 晴朗 | 中等 | 湿 | 弱 | 否 |
D9 | 晴朗 | 凉爽 | 正常 | 弱 | 是 |
D11 | 晴朗 | 中等 | 正常 | 强 | 是 |
此时有5天的数据,出去打球的有2天,不打球的有3天,因此熵值为:
\]
当天气为小雨
时,涉及到的数据如下:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D4 | 小雨 | 中等 | 湿 | 弱 | 是 |
D5 | 小雨 | 凉爽 | 正常 | 弱 | 是 |
D6 | 小雨 | 凉爽 | 正常 | 强 | 否 |
D10 | 小雨 | 中等 | 正常 | 弱 | 是 |
D14 | 小雨 | 中等 | 湿 | 强 | 否 |
此时有5天的数据,出去打球的有3天,不打球的有2天,因此熵值为:
\]
当天气为大雨
时间,涉及到的数据如下:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D3 | 大雨 | 热 | 湿 | 弱 | 是 |
D7 | 大雨 | 凉爽 | 正常 | 强 | 是 |
D12 | 大雨 | 中等 | 湿 | 强 | 是 |
D13 | 大雨 | 热 | 正常 | 弱 | 是 |
此时有4天的数据,出去打球的有4天,不打球的有0天,因此熵值为:
\]
熵值为0,所有数据(标签)都处在同一类,决策树在该分支上停止生长。
由此可以计算天气
这一列的信息熵:
Entropy(S_{天气})&=\frac{5}{14}\times Entropy(S_{晴朗})+\frac{5}{14}\times Entropy(S_{小雨})+\frac{4}{14}\times Entropy(S_{大雨})\\
&=\frac{5}{14}\times 0.971+\frac{5}{14}\times 0.971+0\\
&=0.69
\end{aligned}
\]
其信息增益为:
Gain(S,天气)&=Entropy(S)-Entropy(S_{天气})\\
&=0.94-0.69\\
&=0.25
\end{aligned}
\]
由此可得:
Gain(S,湿度)=Entropy(S_{天气})-Entropy(S_{湿度})=0.15\\
Gain(S,风力)=Entropy(S_{天气})-Entropy(S_{风力})=0.05
\]
信息增益最高的是天气
列,由于当前没有根节点,因此选择该列为根节点。
由上图可以看出,需要进一步划分的为晴天
、小雨
时的情况,因此要分别计算当天气=晴天
以及天气=小雨
时其他列的信息增益。
天气=晴朗
时的数据子集如下:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D1 | 晴朗 | 热 | 湿 | 弱 | 否 |
D2 | 晴朗 | 热 | 湿 | 强 | 否 |
D8 | 晴朗 | 中等 | 湿 | 弱 | 否 |
D9 | 晴朗 | 凉爽 | 正常 | 弱 | 是 |
D11 | 晴朗 | 中等 | 正常 | 强 | 是 |
把它当做一个完整的数据集S,根据上一步的计算其信息熵为0.971
:
分别计算气温
、湿度
、风力
的信息增益,首先计算气温,气温有三种可能出现的情况,即凉爽
、中等
、热
。
当气温=凉爽
时:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D9 | 晴朗 | 凉爽 | 正常 | 弱 | 是 |
此时有1天的数据,出去打球的有1天,不打球的有0天,因此熵值为:
\]
当气温=中等
时:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D8 | 晴朗 | 中等 | 湿 | 弱 | 否 |
D11 | 晴朗 | 中等 | 正常 | 强 | 是 |
此时有2天的数据,出去打球的有1天,不打球的有1天,因此熵值为:
\]
当气温=热
时:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D1 | 晴朗 | 热 | 湿 | 弱 | 否 |
D2 | 晴朗 | 热 | 湿 | 强 | 否 |
此时有2天的数据,出去打球的有0天,不打球的有2天,因此熵值为:
\]
因此天气=晴朗
时,气温
列的信息增益为:
Gain(S_{晴朗},气温)&=Entropy(S_{晴朗})-Entropy(S_{气温}|天气=晴朗)\\
&=Entropy(S_{晴朗})-\frac{1}{5}Entropy(S_{凉爽}|天气=晴朗)-\frac{2}{5}Entropy(S_{中等}|天气=晴朗)\\
&\ \ \ \ -\frac{2}{5}Entropy(S_{热}|天气=晴朗)\\
&=0.971-\frac{1}{5}\times 0-\frac{2}{5}\times 1-\frac{2}{5}\times 0\\
&=0.571
\end{aligned}
\]
同理:
Gain(S_{晴朗},风力)=Entropy(S_{晴朗})-Entropy(S_{风力}|天气=晴朗)=0.019
\]
所以,当天气=晴朗
时,湿度的信息增益最大,本次决策树生长选择湿度
为新的节点。
当湿度=正常
时:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D9 | 晴朗 | 凉爽 | 正常 | 弱 | 是 |
D11 | 晴朗 | 中等 | 正常 | 强 | 是 |
此时有2条数据,其中打球的有2条,不打球的有0条,因此信息熵为0
当湿度=湿
时:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D8 | 晴朗 | 中等 | 湿 | 弱 | 否 |
D1 | 晴朗 | 热 | 湿 | 弱 | 否 |
D2 | 晴朗 | 热 | 湿 | 强 | 否 |
此时有3条数据,其中打球的有0条,不打球的有3条,因此信息熵为0
显然可得,当湿度
不同时,明显分成两类,因此新的决策树如下:
由上可以看出,当`天气=小雨`时不能正确分类,因此当天气为小雨时的数据子集为:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D4 | 小雨 | 中等 | 湿 | 弱 | 是 |
D5 | 小雨 | 凉爽 | 正常 | 弱 | 是 |
D6 | 小雨 | 凉爽 | 正常 | 强 | 否 |
D10 | 小雨 | 中等 | 正常 | 弱 | 是 |
D14 | 小雨 | 中等 | 湿 | 强 | 否 |
此时有5天的数据,出去打球的有3天,不打球的有2天,熵值为0.971。
先看气温,此时有两种情况:中等
、凉爽
,分别划分两种情况各自对应的数据集。
当气温=中等
时,有3次记录,2次打球,1次不打球,因此中等气温时的熵值为:
Entropy(S_{中等}|天气=小雨)&=-[\frac{2}{3}\times\log_{2}{\frac{2}{3}}]-[\frac{1}{3}\times\log_{2}{\frac{1}{3}}]=0.918
\end{aligned}
\]
当气温=凉爽
时,有2次记录,1次打球,1次不打球,因此凉爽气温时的熵值为:
Entropy(S_{凉爽}|天气=小雨)&=-[\frac{1}{2}\times\log_{2}{\frac{1}{2}}]-[\frac{1}{2}\times\log_{2}{\frac{1}{2}}]=1.0
\end{aligned}
\]
因此气温
的信息增益为:
Gain(S_{小雨},气温)&=Entropy(S_{小雨})-Entropy(S_{气温}|天气=小雨)\\
&=Entropy(S_{小雨})-\frac{3}{5}Entropy(S_{中等}|天气=小雨)-\frac{2}{5}Entropy(S_{凉爽}|天气=小雨)\\
&=0.971-\frac{3}{5}\times 0.918-\frac{2}{5}\times 1.0\\
&=0.02
\end{aligned}
\]
同理:
Gain(S_{小雨},湿度)&=Entropy(S_{小雨})-Entropy(S_{湿度}|天气=小雨)\\
&=Entropy(S_{小雨})-\frac{2}{5}Entropy(S_{湿}|天气=小雨)-\frac{3}{5}Entropy(S_{正常}|天气=小雨)\\
&=0.02\\
Gain(S_{小雨},风力)&=Entropy(S_{小雨})-Entropy(S_{风力}|天气=小雨)\\
&=Entropy(S_{小雨})-\frac{2}{5}Entropy(S_{强}|天气=小雨)-\frac{3}{5}Entropy(S_{弱}|天气=小雨)\\
&=0.971
\end{aligned}
\]
因此,当天气=小雨
时,信息增益最大的为风力
,选择该列生长:
当 风力=强
的时候:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D6 | 小雨 | 凉爽 | 正常 | 强 | 否 |
D14 | 小雨 | 中等 | 湿 | 强 | 否 |
标签结果一致,信息熵为0。
当风力=弱
的时候:
天数 | 天气 | 气温 | 湿度 | 风力 | 是否打球 |
---|---|---|---|---|---|
D4 | 小雨 | 中等 | 湿 | 弱 | 是 |
D5 | 小雨 | 凉爽 | 正常 | 弱 | 是 |
D10 | 小雨 | 中等 | 正常 | 弱 | 是 |
标签结果一致,信息熵为0。
引用
[1] Quinlan J R . Induction of Decision Trees[J]. Machine Learning, 1986, 1(1):81-106.
[2] University of FLORIDA.The ID3 Algorithm[EB/OL].https://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm,1997.
[3] Xiaohu W , Lele W , Nianfeng L . An Application of Decision Tree Based on ID3[J]. Physics Procedia, 2012, 25:1017-1021.
[4] Sefik Ilkin Serengil.A Step by Step ID3 Decision Tree Example[EB/OL].https://sefiks.com/2017/11/20/a-step-by-step-id3-decision-tree-example/,2017.
[5] Yaser Sakkaf.Decision Trees: ID3 Algorithm Explained[EB/OL].https://towardsdatascience.com/decision-trees-for-classification-id3-algorithm-explained-89df76e72df1,2020.