决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。
例如有人给我们介绍新的对象的时候,我们就要一个个特点去判断,于是这种判断的过程就可以画成一棵树,例如根据特点依次判断:
如上,决策的形式以树的形式进行示意和编码,就形成了决策树。
显然,决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点。
简而言之,决策树是一个利用树的模型进行决策的多分类模型,简单有效,易于理解。
决策树算法的伪代码(参照了python语法)如下图所示:
1# D = {(x1,y1)、(x2,y2)......(xm,yn)} 是数据集
2# A = {a1、a2、a3.} 是划分节点的属性集
3# 节点node有两个主要属性:content代表该节点需要分类的训练集,type代表叶节点的决策类型
4def generateTree(D,A):
5 newNode = 空 #生成新的节点
6 # 如果当前数据集都为一个种类,则设为一个叶节点并返回
7 if D 中数据皆属于类别 C:
8 newNode.content = D
9 newNode.type = C
10 return
11 # 如果已经没有属性了或者数据集在剩余属性中表现相同(属性无法区分)
12 if A = 空集 or D中数据在A中取值相同:
13 newNode.content = D
14 newNode.type = D中最多的类
15 return
16 #从A中选取最优的属性a
17 a=selectBestPorperty(A)
18 #为a的每一个取值生成一个节点,递归进行处理
19 for a的每一个取值 res[i]:
20 生成新的分支节点 node[i]
21 D[i] = D中取值为res[i]的数据
22 node[i].content = D[i]
23 if node[i].content == null:
24 node[i].type = D中最多的类
25 else:
26 generateTree(D[i],A - {a})
27 return
可以看到,在伪代码中,大部分步骤都是简单而明确的,而最重要的步骤在于从A中选取最优的属性a,可以说,属性选择的质量,决定了决策树的预测准确度。这很容易理解,例如我们看一个学生聪明与否可以看他的成绩,但是如果依靠他的身高预测他是否聪明,显然得不到好的结果。
一般的原则是,希望通过不断划分节点,使得一个分支节点包含的数据尽可能的属于同一个类别,即“纯度“越来越高。
这里列出三种常用的准则。
我们先对一个节点的纯度进行定义,我们将其称之为信息熵:
其中
代表当前节点D的数据中第k类样本所占的比例。
观察该信息熵的定义,有以下几个特点:
都属于[0,1],Ent(D)必定为正值,值越大说明纯度越低
时取值最大值
在定义了信息熵之后,对信息增益进行定义,假设选取属性a有V个取值,
,按照决策树的规则,D将被划分为V个不同的节点数据集,
代表其中第v个节点:
观察该式,有以下几点说明:
表示分支节点所占的比例大小,显然数据集越大的分支节点权重越高
由此,我们得到了一种选择划分属性的方法,计算以每个属性进行划分子节点得到的信息增益,选择其中最大的作为选择的属性。
信息增益原则对于每个分支节点,都会乘以其权重,也就是说,由于权重之和为1,所以分支节点分的越多,即每个节点数据越小,纯度可能越高。这样会导致信息熵准则偏爱那些取值数目较多的属性。
为了解决该问题,这里引入了信息增益率,定义如下:
相当于引入了修正项IV(a),它是对于属性a的固有值。
需要注意的是,信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题,可以先找出信息增益在平均值以上的属性,在从中选择信息增益率最高的。
在CART决策树中,使用基尼指数来选择属性,首先定义数据集D的基尼值:
形象的说,基尼值代表了从D中随机选择两个样本,其类别不一致的概率。
有了基尼值后,可以在此基础上定义基尼指数:
其的含义和之前相同,可以看出基尼指数越小,说明纯度越高,我们可以通过选择基尼指数小的属性来划分子节点。
剪枝是应该决策树过拟合的一种重要方法,主要分为以下两种:
在之前进行选择属性的时候,我们仅仅讨论了属性值为离散值的情况,例如身高分为“极高、高、较高、中等、较矮”五个选项,但是如果数据集中身高为连续值,例如140-210cm,我们该如何处理呢?
这里可以采用二分的思想,将连续值化为离散值。由于我们的数据集是有限的,即使是连续值,属性a在数据集中也只出现了有限个确定的值,记为
,且
。
取n个值的中点,令
我们得到了n-1个中点,
,任取一个值
可以将数据集D分为两个,
表示D中大的数据,
表示D中小的数据集合,这样,我们便可以同离散值一样进行处理了。
接下来的问题是,选取哪一个t呢?显然在信息增益准则下,应该选择使得信息增益最大的t:
经过稍加改造的信息增益公式就可以选择最好的t来进行划分。
缺失值处理较为复杂,设计到较多的公式,在这里给出链接,读者可以参考阅读
https://blog.csdn.net/u012328159/article/details/79413610
其主要思想是
实际上大部分机器学习的分类算法,都是将一个具有n个属性的数据,看成一个在n维空间的一个点,分类的过程就是在n维空间或者更高维度空间中找到超平面,将这些点进行划分。
而普通的决策树算法有一个特点,由于它每个节点的划分条件都是单独的,明确的,所以决策树的决策边界是平行于空间的坐标轴的。如下图所示:
这对其拟合特性有一定的影响,当数据比较复杂时,需要较多的属性才能得到较好的划分,而多变量决策树就可以解决该问题。
在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器。 如下图所示:
多变量决策树较复杂,如果想进一步了解,可以阅读这个领域的论文。
作者:陈浩然,欢迎阅读她的博客:chrer.com,她的机器学习系列笔记:
北大才女总结:机器学习的概念、历史和未来
北大才女笔记:这样学习线性回归和梯度下降(上篇)
北大陈浩然笔记:特征缩放和泛化能力(下篇)
logistics判别与线性模型中的4个问题
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!