Fork me on GitHub

机器学习-决策树

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

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

决策树算法的特点

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

样例

姓名 年龄 长相 工资 写代码 类别
A 不会 不见
B 年轻 一般 中等
C 年轻 不会 不见
D 年轻 一般
E 年轻 一般 不会 不见

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

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

ID3-最大信息增益

熵是一种信息的度量方式,表示信息的混乱程度,也就是说:信息越有序,信息熵越低。例如:火柴有序放在火柴盒里,熵值很低,相反,熵值很高。假设样本空间D中的的概率分布为:

  • $C_{i}$为样本集合D中属于第$i$类标签的样本子集
  • $|C_{i}|$表示该子集的样本个数
  • $|D_{i}|$表示整个样本集的个数

数据集$D$的熵为

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

在样例中,包含去见的2人,不去见的为3人,总共为5人,因此可以得到数据集$D$的熵为:



为了决定创建决策树时使用哪个特征,这个时候就要针对不同的特征计算该特征的信息熵,由此引入条件熵,其计算公式为:

  • $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$包含两个值=[年龄:老, 年龄:年轻],其中年龄老的会见的在整个样本中的人数为1,其中人数0,不见的人数为1;年龄年轻的在整个样本的人数为4,其中会见的人数为2,不见的人数为2。由此分析,求得特征$A1$对应的条件熵


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

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

数据集的熵减去特征的条件熵

算法流程

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

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

  • 根据特征$A_{i}$,求解特征对应的条件熵$H(D|A_{i})$,及信息增益$g(D,A_{i})$

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

不足

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

C4.5-信息增益率

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

信息增益率

定义如下

式子中的$H_{A}(D)$如下所示

求得信息增益之后,将信息增益与数据集关于特征$A$的取值的熵作比,得到信息增益率。


对于示例,继续条件熵的计算,$H_{A_{1}}(D)$表示数据集关于年龄这个特征的,对于年龄这个特征,在整个样本空间内有4个年轻的去见,一个年老的不去见,因此该特征的熵为:



取值较多的特征对应的信息增益较大,但是对应的特征的取值的熵也较大,一定程度上对取值较多的特征进行了惩罚和抑制。

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}$,则概率分布的基尼指数为

对于二分类问题,如果样本属于第1个类的概率为$p$,则概率分布的基尼指数可以表示为

假设存在$K$个类,则数据集$D$的基尼指数为:

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

  • $|C_{k}|$为样本集合$D$中属于第$k$类标签的样本子集的样本数量,$K$是类的个数

特征$A$的$Gini$指数为:

每次选择$Gini$指数最小的特征及其对应的切分点进行分类

如果样本$D$根据特征$A$是否取某一可能值$a$被分割成$D_{1}$和$D_{2}$两部分,则$D_{1}={(x,y)\in D|A=a}$并且$D_{2}=D-D_{1}$则在特征条件$A$的条件下,集合$D$的基尼指数可以定义为:

基尼指数值越大,对应的样本的不确定性越大,与熵相似,因此选择最小的基尼指数作为划分标准。


同样是上面的例子,计算特征$A_{1}$对应的基尼指数,当$A_{1}$中的特征为年轻时,会将样本集一分为2,一部分为年轻,对应4人;一部分为年老,对应1人,基于此进行该特征值下的基尼指数的计算

同理,可以得到

依次可以得到不同特征值取值下的$Gini$指数,并选择最小的$Gini$指数作为特征进行决策树创建。


CART回归-最小平方差损失

给定训练数据集

对于决策树的核心问题是:如何选择划分点?如何决定节点的输出值?

对于上面的分类树使用的是信息论中的评价指标,信息增益,信息增益率,基尼指数;而对于回归树使用的是启发式的方法。假设数据中存在$n​$个特征,每个特征有$s_{i}(i \in (1,n))​$个取值,选择第j个变量$x^{(j)}​$和它的取值s作为切分变量和切分点并将整个数据集划分为两个数据空间

如上图所示,每个节点将数据空间划分为两个部分,划分点的选择基于最小平方差损失。遍历所有的特征,并尝试该特征的所有取值对空间进行划分,直到特征j的取值s使的损失函数最小,对于CART回归树使用最小平方差损失,具体的求解方式为

式中的$c_m=ave(y_i|x_i \in R_m)​$

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

假设输入空间被划分为M个单元$R_2,R_2,R_3,R_m​$,那么每个区域的输出值就是该区域内所有点$y​$值的平均值$c_m=ave(y_i|x_i \in R_m)​$,也就是

总结

决策树算法名称 算法特点
ID3 只用于分类
只处理离散数据
偏向样本较多的特征
泛化能力较差,容易过拟合
对于缺失值比较敏感
节点下生成多叉分支,特征在层间不会复用
通过剪枝权衡数的准确性和泛化能力
C4.5 只用于分类
可以处理离散和连续数据
添加取值较多的特征惩罚
泛化能力相较ID3较好
节点下生成多叉分支,特征在层间不会复用
通过剪枝权衡数的准确性和泛化能力
CART 用于分类和回归
可以处理离散和连续数据
回归使用最小平方差,分类使用最小基尼指数
每个节点产生两个分支,最后形成一个二叉树,特征层间复用
利用全部数据发现所有可能的树结构

参考文献

-------------本文结束知识分享,方便你我-------------

本文标题:机器学习-决策树

文章作者:ShiXiaofeng

发布时间:2018年11月09日 - 17:18

最后更新:2019年01月25日 - 16:07

原始链接:http://xiaofengshi.com/2018/11/09/机器学习-决策树/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%