机器学习-决策树

决策树是机器学习中非常容易理解机模型，是最基础最常见的有监督学习模型，被用于分类或者回归，由于树结构与销售、教育、医疗诊断场景决策过程相似，因此在该领域应用广泛。

决策树的生成包括三个部分：特征选择，构造树，树剪枝

决策树算法的特点

1
2
3

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。

样例

这是一个典型的是否进行约会的样例，数据中包含A-E五个人，包含年龄，长相，工资，会写代码五个属性，通过这五个属性来确定是否进行约会。整个数据集中包含特征为$A$=[年龄，长相，工资，写代码]=$$[A1,A2,A3,A4]$$

对于构建决策树过程中的第一步：特征选择，目前存在三种特征选择的启发函数：最大信息增益，信息增益比，基尼指数。接下来的几个计算实例都是使用这个样例。

ID3-最大信息增益

熵

熵是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。假设样本空间D中的的概率分布为：
$$p_i=\frac{\mathrm{\mid }{C}_i\mathrm{\mid }}{D}$$

• $C_i$为样本集合D中属于第$i$类标签的样本子集
• $\mathrm{\mid }{C}_i\mathrm{\mid }$表示该子集的样本个数
• $\mathrm{\mid }{D}_i\mathrm{\mid }$表示整个样本集的个数

数据集$D$的熵为
$$H(D)=-\sum _{i=1}^n{p}_{i}lo{g}_2{p}_i$$

• 一定要注意前面的负号
• $n$表示标签数
• 指数可以使用以$2$位底或以$e$为底

在样例中，包含去见的2人，不去见的为3人，总共为5人，因此可以得到数据集$D$的熵为：
$$H(D)=-(\frac{3}{5}\ast lo{g}_2\frac{3}{5}+\frac{2}{5}\ast lo{g}_2\frac{2}{5})=0.971$$

• $D_i$表示$D$中特征$A$取第$i$个值的样本子集
• $D_{ik}$表示$D_i$中属于第k类的样本子集
• 存在等式关系$D_i={\sum }_{k=1}^k{D}_{ik}$和$D={\sum }_{i=1}^n{D}_i$

计算$A1$的条件熵，$A1$包含两个值$$[A11,A12]$$=[年龄:老, 年龄:年轻]，其中年龄老的会见的在整个样本中的人数为1，其中人数0，不见的人数为1；年龄年轻的在整个样本的人数为4，其中会见的人数为2，不见的人数为2。由此分析，求得特征$A1$对应的条件熵

$$\begin{array}{cccc}& {\displaystyle \begin{array}{rl}{\displaystyle H(D\mathrm{\mid }{A}_1)}& {\displaystyle =-\sum _{i=1}^n\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}(\sum _{k=1}^k\frac{\mathrm{\mid }{D}_{ik}\mathrm{\mid }}{\mathrm{\mid }{D}_i\mathrm{\mid }}lo{g}_2\frac{\mathrm{\mid }{D}_{ik}\mathrm{\mid }}{\mathrm{\mid }{D}_i\mathrm{\mid }})}\\ {\displaystyle }& {\displaystyle =-(\frac{1}{5}H(D_1)+\frac{4}{5}H(D_2))}\\ {\displaystyle }& {\displaystyle =-[\frac{1}{5}\ast (-0)+\frac{4}{5}(-\frac{2}{4}lo{g}_2\frac{2}{4}-\frac{2}{4}lo{g}_2\frac{2}{4})]}\\ {\displaystyle }& {\displaystyle =0.8}\end{array}}& & \end{array}$$

由此可以得到所有特征对应的条件熵。

在ID3算法，使用的是启发函数为信息增益，所谓信息增益是针对样本内的特征而言的，对于不同的特征，使用样本集的熵与特征的条件熵的差作为该特征的信息增益。因此信息增益的定义如下

数据集的熵减去特征的条件熵
$$g(D,A)=H(D)-H(D\mathrm{\mid }A)$$

算法流程

• 给定样本集$D$以及提取存在的特征$A$

• 根据整个样本集$D$以及标签计算$H(D)$

• 根据特征$A_i$，求解特征对应的条件熵$H(D\mathrm{\mid }{A}_i)$，及信息增益$g(D,A_i)$

• 选择最大的信息增益对应的特征作为当前节点的划分标准

不足

使用增大信息增益作为节点的划分规则，由于信息增益反应的是数据不确定性减小的程度，所以对于取值较多的特征，这就意味着该特征的确定性越高，对应的条件熵也就越低，信息增益越大。因此使用最大信息增益偏向取值较多的特征。

C4.5-信息增益率

为了改进使用最大信息增益偏向取值较多的特征这一个不足，引入了信息增益率。

信息增益率

定义如下
$$g_g(D,A)=\frac{g(D,A)}{H_A(D)}$$
式子中的$H_A(D)$如下所示

$$H_A(D)=-\sum _{i=1}^n\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}lo{g}_2\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}$$
求得信息增益之后，将信息增益与数据集关于特征$A$的取值的熵作比，得到信息增益率。

对于示例，继续条件熵的计算，$H_{A_1}(D)$表示数据集关于年龄这个特征的，对于年龄这个特征，在整个样本空间内有4个年轻的去见，一个年老的不去见，因此该特征的熵为：
$$H_{A_1}(D)=-\frac{1}{5}lo{g}_2\frac{1}{5}-\frac{4}{5}lo{g}_2\frac{4}{5}=0.722$$

C4.5算法流程

1
2
3
4
5
6
7
8

输入：数据集D，特征集A,类别集C,阈值thresh
输出：决策树T
if any(D) in Ci: T为单节点树，ci作为该节点的类，返回T；
elif A is None: T为单节点树，D中实例数最大的类别Ci作为该节点的类，返回T；
elif Ai=max(cal_info_gain_ratio(A)) 
	if Ai<thresh: T为单节点树，D中实例数最大的类别Ci作为该节点的类，返回T
	else：计算Ai总每个可能只ai，使用Ai=ai将D划分若干非空Di，将Di中实例最多的类别Ci作为标记构建子节点，有节点及子节点构成的数T，返回Ti；
对节点i，以Di为训练集，以A-Ai为特征集，递归上述步数得到子树Ti

CART

CART-classification and regression tree分类回归树

该算法即可用于回归又可以用于分类。构建树时使用特征的取值对样本空间进行二值划分，不仅可以处理离散数据同时可以处理连续数据。

CART分类-Gini指数

与信息熵相似，信息熵描述的是数据的混乱程度，基尼指数描述的是数据的纯度，基尼指数越小，对应的信息纯度越高。分类决策树使用基尼指数进行最优特征的选择，同时决定改特征的最优二值切分点。

Gini定义

分类问题中，假设存在$K$个类，样本点属于$k$的概率为$p_k$，则概率分布的基尼指数为
$$\begin{array}{rllll}& {\displaystyle Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)}& {\displaystyle =1-\sum _{k=1}^K{p}_k^2}& & \\ & {\displaystyle }& {\displaystyle where{p}_k=\frac{\mathrm{\mid }{C}_k\mathrm{\mid }}{D}}& & \end{array}$$
对于二分类问题，如果样本属于第1个类的概率为$p$，则概率分布的基尼指数可以表示为
$$\begin{array}{cccc}& {\displaystyle Gini(p)=2p(1-p)}& & \end{array}$$
假设存在$K$个类，则数据集$D$的基尼指数为：
$$Gini(D)=1-\sum _{k=1}^K(\frac{\mathrm{\mid }{C}_k\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}{)}^2$$

• 公式内的符号定义与熵的公式中的含义相应。

• $\mathrm{\mid }{C}_k\mathrm{\mid }$为样本集合$D$中属于第$k$类标签的样本子集的样本数量，$K$是类的个数

特征$A$的$Gini$指数为：
$$Gini(D\mathrm{\mid }A)=\sum _{k=1}^K\frac{\mathrm{\mid }{D}_k\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}Gini(D_k)$$
每次选择$Gini$指数最小的特征及其对应的切分点进行分类

如果样本$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，则$D_1=(x,y)\in D\mathrm{\mid }A=a$并且$D_2=D-D_1$则在特征条件$A$的条件下，集合$D$的基尼指数可以定义为：
$$Gini(D\mathrm{\mid }A)=\frac{\mathrm{\mid }{D}_1\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}Gini(D_1)+\frac{\mathrm{\mid }{D}_2\mathrm{\mid }}{\mathrm{\mid }D\mathrm{\mid }}Gini(D_2)$$
基尼指数值越大，对应的样本的不确定性越大，与熵相似，因此选择最小的基尼指数作为划分标准。

同样是上面的例子，计算特征$A_1$对应的基尼指数，当$A_1$中的特征为年轻时，会将样本集一分为2，一部分为年轻，对应4人；一部分为年老，对应1人，基于此进行该特征值下的基尼指数的计算
$$\begin{array}{cccc}& {\displaystyle \begin{array}{rl}{\displaystyle Gini(D\mathrm{\mid }{A}_1=\text{年轻})}& {\displaystyle =\frac{1}{5}\ast Gini(D_1)+\frac{4}{5}\ast Gini(D_2)}\\ {\displaystyle }& {\displaystyle =\frac{1}{5}\ast [2\ast 1\ast (1-1)]+\frac{4}{5}\ast (2\ast \frac{2}{4}\ast [1-\frac{2}{4})]}\\ {\displaystyle }& {\displaystyle =\frac{2}{5}}\end{array}}& & \end{array}$$
同理，可以得到
$$\begin{array}{cccc}& {\displaystyle \begin{array}{rl}{\displaystyle Gini(D\mathrm{\mid }{A}_1=\text{老})}& {\displaystyle =\frac{1}{5}\ast Gini(D_1)+\frac{4}{5}\ast Gini(D_2)}\\ {\displaystyle }& {\displaystyle =\frac{1}{5}\ast [2\ast 1\ast (1-1)]+\frac{4}{5}\ast (2\ast \frac{2}{4}\ast [1-\frac{2}{4})]}\\ {\displaystyle }& {\displaystyle =\frac{2}{5}}\end{array}}& & \end{array}$$
依次可以得到不同特征值取值下的$Gini$指数，并选择最小的$Gini$指数作为特征进行决策树创建。

CART回归-最小平方差损失

给定训练数据集
$$D=\{(x_1,y_2),(X_2,y_2),\mathrm{.}\mathrm{.}\mathrm{.},(x_N,y_N)\}$$
对于决策树的核心问题是：如何选择划分点?如何决定节点的输出值？

对于上面的分类树使用的是信息论中的评价指标，信息增益，信息增益率，基尼指数；而对于回归树使用的是启发式的方法。假设数据中存在$n\text{}$个特征，每个特征有$s_i(i\in (1,n))\text{}$个取值，选择第j个变量$x^{(j)}\text{}$和它的取值s作为切分变量和切分点并将整个数据集划分为两个数据空间
$$R_j(j,s)=\{x\mathrm{\mid }{x}^{(j)}\le s\}{R}_j(j,s)=\{x\mathrm{\mid }{x}^{(j)}>s\}$$
如上图所示，每个节点将数据空间划分为两个部分，划分点的选择基于最小平方差损失。遍历所有的特征，并尝试该特征的所有取值对空间进行划分，直到特征j的取值s使的损失函数最小，对于CART回归树使用最小平方差损失，具体的求解方式为
$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$
式中的$c_m=ave(y_i\mathrm{\mid }{x}_i\in R_m)\text{}$

遍历所有的变量$j\text{}$，对固定的切分变量$j\text{}$扫描切分点$s\text{}$，选择使得上述公式取值最小的$(j,s)\text{}$

假设输入空间被划分为M个单元$R_2,R_2,R_3,R_m\text{}$，那么每个区域的输出值就是该区域内所有点$y\text{}$值的平均值$c_m=ave(y_i\mathrm{\mid }{x}_i\in R_m)\text{}$，也就是
$$\begin{array}{rllll}& {\displaystyle }& {\displaystyle R_1(j,s)=\{x\mathrm{\mid }{x}^{(j)}\ge s\},R_2(j,s)=\{x\mathrm{\mid }{x}^{(j)}>s\}}& & \\ & {\displaystyle }& {\displaystyle c_m=\frac{1}{N_m}\sum _{x_i\in R_m(i,s)}{y}_i,x\in R_m,m=1,2}& & \end{array}$$

总结

参考文献

• 机器学习实战-决策树