[监督学习]决策树

在监督学习中，根据输出是否为概率划分为概率监督学习和非概率监督学习。前面介绍的逻辑回归属于前者，而LDA和支持向量机属于后者，接下来介绍另一种非概率监督学习——决策树。

问题

给定训练集 $D = \{(\boldsymbol{x_1},y_1),(\boldsymbol{x_2},y_2),\cdots,(\boldsymbol{x_N},y_N)\}$D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)} ，其中 $\boldsymbol{x_i} = (x_i^1,x_i^2,\cdots,x_i^n)^T$xi​=(xi1​,xi2​,⋯,xin​)T 为输入的特征向量，$n$n 为特征的个数，$y_i \in \{ 1,2,\cdots,K\}$yi​∈{1,2,⋯,K} 为类的标签，$N$N 为样本的数量。我们学习的目标是根据给定的训练集构成一个决策树模型，使它能够对样本进行正确的分类。

决策树模型

决策树是一个类似于流程图的数结构模型，每一个中间节点表示一个特征或属性，每个叶节点表示一个分类。针对如何选择特征作为中间节点，可以将模型分为两类：基于规则的建树和基于模型的建树。

基于规则的建树就是人为的设计选择特征的规则，例如按照特征出现的先后顺序，这种方法主观性太强；而基于模型的建树是采用信息增益这一度量作为选择特征的参考，为什么选择信息增益呢？信息增益又表示了什么呢？

其实回到特征的选择上，我们无非是想找到一个具有最好分类能力的特征，也就是说按照这个特征将训练集分割成子集，使得各个子集在当前条件下有最好的分类，而信息增益就能够很好地表示这一直觉的准则。

实际上，决策树本质上就是某一特征与结果的相关性。

信息增益

为了便于说明，先给出熵与条件熵的定义。

熵是表示随机变量不确定性的度量。若 $X$X 是一个取有 $n$n 个值的离散随机变量，其概率分布为
$P(X=x_i)=p_i,i=1,2,\cdots,n$P(X=xi​)=pi​,i=1,2,⋯,n
则随机变量 $X$X 的熵定义为
$H(X) = -\sum_{i=1}^n p_i\log p_i$H(X)=−i=1∑n​pi​logpi​
由此发现，熵只依赖于 $X$X 的分布，而与 $X$X 的取值无关，所以也记为 $H(p)$H(p) ，而且熵越大，随机变量的不确定性就越大，从定义可验证熵具有极大值 $0\le H(p) \le \log n$0≤H(p)≤logn 。

设有随机变量 $(X,Y)$(X,Y) ，其联合概率分布为
$P(X=x_i,Y=y_i) = p_{ij},i=1,2,\cdots,n;j=1,2,\cdots,m$P(X=xi​,Y=yi​)=pij​,i=1,2,⋯,n;j=1,2,⋯,m
条件熵 $H(Y|X)$H(Y∣X) 表示在已知随机变量 $X$X 的条件下随机变量 $Y$Y 的不确定性，其定义为
$H(Y|X) = \sum_{i=1}^n p_i H(Y|X=x_i)$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)
$定义(信息增益)：特征A对训练集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D\\的经验条件熵H(D|A)之差，即g(D,A)=H(D)-H(D|A)$定义(信息增益)：特征A对训练集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D∣A)之差，即g(D,A)=H(D)−H(D∣A)

示例

以问题为例，下面根据信息增益来选择决策树中的第一个特征。

首先，由训练集 $D$D 关于标签的概率分布计算出经验熵 $H(D) = - \frac{9}{15}\log \frac{9}{15} - \frac{6}{15}\log \frac{6}{15}$H(D)=−159​log159​−156​log156​ 。然后根据各个特征 $A_1(年龄),A_2(有工作),A_3(有自己的房子),A_4(信贷情况)$A1​(年龄),A2​(有工作),A3​(有自己的房子),A4​(信贷情况) 分别计算信息增益。

1. $A_1$A1​ 特征对训练集 $D$D 的信息增益 $g(D,A_1)$g(D,A1​)
   $\begin{aligned} g(D,A_1) &= H(D) - H(D|A_1) \\ & = H(D)- \sum_{i=1}^3 p_i H(D|A_1=x_i) \\ & = H(D) - [P(A_1 = 青年)H(D|A_1 = 青年) + P(A_1 = 中年)H(D|A_1 = 中年) + P(A_1 = 老年)H(D|A_1 = 老年)] \\ &= H(D)- [\frac{5}{15}H(D|A_1 = 青年)+\frac{5}{15}H(D|A_1 = 中年)+\frac{5}{15}H(D|A_1 = 老年)] \\ &= H(D) - [\frac{5}{15}(-\frac{3}{5}\log \frac{3}{5}- \frac{2}{5}\log \frac{2}{5}) + \frac{5}{15}(-\frac{2}{5}\log \frac{2}{5}- \frac{3}{5}\log \frac{3}{5}) + \frac{5}{15}(-\frac{4}{5}\log \frac{4}{5}- \frac{1}{5}\log \frac{1}{5})]\\ &= 0.083 \end{aligned}$g(D,A1​)​=H(D)−H(D∣A1​)=H(D)−i=1∑3​pi​H(D∣A1​=xi​)=H(D)−[P(A1​=青年)H(D∣A1​=青年)+P(A1​=中年)H(D∣A1​=中年)+P(A1​=老年)H(D∣A1​=老年)]=H(D)−[155​H(D∣A1​=青年)+155​H(D∣A1​=中年)+155​H(D∣A1​=老年)]=H(D)−[155​(−53​log53​−52​log52​)+155​(−52​log52​−53​log53​)+155​(−54​log54​−51​log51​)]=0.083​

2. $A_2$A2​ 特征对训练集 $D$D 的信息增益 $g(D,A_2)$g(D,A2​)

$\begin{aligned} g(D,A_2) &= H(D) - H(D|A_2) \\ &= H(D) - \sum_{i=1}^2 p_i H(D|A_2 = x_i)\\ &= H(D)- [P(A_2 = 是)H(D|A_2=是)+P(A_2 = 否)H(D|A_2=否)] \\ &= H(D) - [\frac{5}{15}H(D|A_2=是) + \frac{10}{15}H(D|A_2=否)] \\ &= H(D)- [\frac{5}{15}(-0\log 0 - 1 \log 1) + \frac{10}{15}(-\frac{6}{10}\log \frac{6}{10} - \frac{4}{10} \log \frac{4}{10})] \\ &= 0.324 \end{aligned}$g(D,A2​)​=H(D)−H(D∣A2​)=H(D)−i=1∑2​pi​H(D∣A2​=xi​)=H(D)−[P(A2​=是)H(D∣A2​=是)+P(A2​=否)H(D∣A2​=否)]=H(D)−[155​H(D∣A2​=是)+1510​H(D∣A2​=否)]=H(D)−[155​(−0log0−1log1)+1510​(−106​log106​−104​log104​)]=0.324​

3. $A_3$A3​ 特征对训练集 $D$D 的信息增益 $g(D,A_3)$g(D,A3​)

$\begin{aligned} g(D,A_3) &= H(D) - H(D|A_3)\\ &= H(D) - \sum_{i=1}^2 p_iH(D|A_3=x_i) \\ &= H(D) - [P(A_3=是)H(D|A_3=是)+P(A_3=否)H(D|A_3=否)]\\ &= H(D) - [\frac{6}{15}(-0\log 0-1\log1)+\frac{9}{15}(-\frac{6}{9} \log \frac{6}{9} - \frac{3}{9}\log \frac{3}{9})] \\ &= 0.420 \end{aligned}$g(D,A3​)​=H(D)−H(D∣A3​)=H(D)−i=1∑2​pi​H(D∣A3​=xi​)=H(D)−[P(A3​=是)H(D∣A3​=是)+P(A3​=否)H(D∣A3​=否)]=H(D)−[156​(−0log0−1log1)+159​(−96​log96​−93​log93​)]=0.420​

4. $A_4$A4​ 特征对训练集 $D$D 的信息增益 $g(D,A_4)$g(D,A4​)

$\begin{aligned} g(D,A_4) &= H(D) - H(D|A_4)\\ &= H(D) - \sum_{i=1}^3 p_iH(D|A_4=x_i) \\ &= H(D) - [P(A_4=非常好)H(D|A_4=非常好)+P(A_4=好)H(D|A_4=好)+P(A_4=一般)H(D|A_4=一般)]\\ &= H(D) - [\frac{4}{15}(-0\log 0-1\log1)+\frac{6}{15}(-\frac{2}{6} \log \frac{2}{6} - \frac{4}{6}\log \frac{4}{6}) + \frac{5}{15}(-\frac{4}{5} \log \frac{4}{5} - \frac{1}{5}\log \frac{1}{5})] \\ &= 0.363 \end{aligned}$g(D,A4​)​=H(D)−H(D∣A4​)=H(D)−i=1∑3​pi​H(D∣A4​=xi​)=H(D)−[P(A4​=非常好)H(D∣A4​=非常好)+P(A4​=好)H(D∣A4​=好)+P(A4​=一般)H(D∣A4​=一般)]=H(D)−[154​(−0log0−1log1)+156​(−62​log62​−64​log64​)+155​(−54​log54​−51​log51​)]=0.363​

通过比较各个特征的信息增益，可以发现第一个节点的最优特征是 $A_3(有自己的房子)$A3​(有自己的房子) 。

ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构成决策树，直至所有的特征的信息增益均很小或没有特征可以选择为止。