定义
决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。
例如有人给我们介绍新的对象的时候,我们就要一个个特点去判断,于是这种判断的过程就可以画成一棵树,例如根据特点依次判断:
如上,决策的形式以树的形式进行示意和编码,就形成了决策树。
结构
显然,决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点。
- 根节点:包含数据集中的所有数据的集合
- 内部节点:每个内部节点为一个判断条件,并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果,内部节点对应的数据的集合别分到两个或多个子节点中。
- 叶节点:叶节点为最终的类别,被包含在该叶节点的数据属于该类别。
简而言之,决策树是一个利用树的模型进行决策的多分类模型,简单有效,易于理解。
伪代码
决策树算法的伪代码(参照了python语法)如下图所示:
# D = {(x1,y1)、(x2,y2)......(xm,yn)} 是数据集
# A = {a1、a2、a3.} 是划分节点的属性集
# 节点node有两个主要属性:content代表该节点需要分类的训练集,type代表叶节点的决策类型
def generateTree(D,A):
newNode = 空 #生成新的节点
# 如果当前数据集都为一个种类,则设为一个叶节点并返回
if D 中数据皆属于类别 C:
newNode.content = D
newNode.type = C
return
# 如果已经没有属性了或者数据集在剩余属性中表现相同(属性无法区分)
if A = 空集 or D中数据在A中取值相同:
newNode.content = D
newNode.type = D中最多的类
return
#从A中选取最优的属性a
a=selectBestPorperty(A)
#为a的每一个取值生成一个节点,递归进行处理
for a的每一个取值 res[i]:
生成新的分支节点 node[i]
D[i] = D中取值为res[i]的数据
node[i].content = D[i]
if node[i].content == null:
node[i].type = D中最多的类
else:
generateTree(D[i],A - {a})
return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
划分选择
可以看到,在伪代码中,大部分步骤都是简单而明确的,而最重要的步骤在于从A中选取最优的属性a,可以说,属性选择的质量,决定了决策树的预测准确度。这很容易理解,例如我们看一个学生聪明与否可以看他的成绩,但是如果依靠他的身高预测他是否聪明,显然得不到好的结果。
一般的原则是,希望通过不断划分节点,使得一个分支节点包含的数据尽可能的属于同一个类别,即“纯度“越来越高。
这里列出三种常用的准则。
信息增益准则
我们先对一个节点的纯度进行定义,我们将其称之为信息熵:
Ent(D)=−∑k=1|γ|pklog(pk)
Ent(D)=−∑k=1|γ|pklog(pk)
其中pkpk代表当前节点D的数据中第k类样本所占的比例。
观察该信息熵的定义,有以下几个特点:
由于pkpk都属于[0,1],Ent(D)必定为正值,值越大说明纯度越低
Ent(D)在k=1,p1p1=1时取值最小值0,在k=|γ|k=|γ| pk=1|γ|pk=1|γ|时取值最大值log|γ|2log2|γ|
信息熵是一个节点的固有性质,和该节点选取什么属性进行下一步的划分无关
在定义了信息熵之后,对信息增益进行定义,假设选取属性a有V个取值,{a1a2......aV}{a1a2......aV},按照决策树的规则,D将被划分为V个不同的节点数据集,DvDv代表其中第v个节点:
Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)
Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)
观察该式,有以下几点说明:
第一线Ent(D)是确定的,和选取的属性a无关,我们可以将之看为定值
|Dv||D||Dv||D|表示分支节点所占的比例大小,显然数据集越大的分支节点权重越高
分支节点整体纯度越大,则后一项越小,信息增益Gain变得越大,所以我们的目标是如何最大化信息增益
由此,我们得到了一种选择划分属性的方法,计算以每个属性进行划分子节点得到的信息增益,选择其中最大的作为选择的属性。
信息增益率准则
信息增益原则对于每个分支节点,都会乘以其权重,也就是说,由于权重之和为1,所以分支节点分的越多,即每个节点数据越小,纯度可能越高。这样会导致信息熵准则偏爱那些取值数目较多的属性。
为了解决该问题,这里引入了信息增益率,定义如下:
Gainratio(D,a)=Gain(D,a)IV(a)
Gainratio(D,a)=Gain(D,a)IV(a)
IV(a)=∑v=1V|Dv||D|log|Dv||D|2
IV(a)=∑v=1V|Dv||D|log2|Dv||D|
相当于引入了修正项IV(a),它是对于属性a的固有值。
需要注意的是,信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题,可以先找出信息增益在平均值以上的属性,在从中选择信息增益率最高的。
基尼指数准则
在CART决策树中,使用基尼指数来选择属性,首先定义数据集D的基尼值:
Gini(D)=∑k=1|γ|∑k1!=kpkpk1=1−∑k=1|γ|p2k
Gini(D)=∑k=1|γ|∑k1!=kpkpk1=1−∑k=1|γ|pk2
形象的说,基尼值代表了从D中随机选择两个样本,其类别不一致的概率。
有了基尼值后,可以在此基础上定义基尼指数:
Giniindex(D,a)=∑v=1V|Dv||D|Gini(Dv)
Giniindex(D,a)=∑v=1V|Dv||D|Gini(Dv)
其中DvDv的含义和之前相同,可以看出基尼指数越小,说明纯度越高,我们可以通过选择基尼指数小的属性来划分子节点。
剪枝
剪枝是应该决策树过拟合的一种重要方法,主要分为以下两种:
预剪枝:该策略就是在对一个节点进行划分前进行估计,如果不能提升决策树泛化精度,就停止划分,将当前节点设置为叶节点。那么怎么测量泛化精度,就是留出一部分训练数据当做测试集,每次划分前比较划分前后的测试集预测精度。
优点:降低了过拟合风险,降低了训练所需的时间。
缺点:预剪枝是一种贪心操作,可能有些划分暂时无法提升精度,但是后续划分可以提升精度。故产生了欠拟合的风险。
后剪枝:该策略是首先正常建立一个决策树,然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序,依次对内部节点进行剪枝,如果将某以内部节点为根的子树换成一个叶节点,可以提高泛化性能,就进行剪枝。
优先:降低过拟合风险,降低欠拟合风险,决策树效果提升比预剪枝强
缺点:时间开销大得多
特殊值处理
连续值处理
在之前进行选择属性的时候,我们仅仅讨论了属性值为离散值的情况,例如身高分为“极高、高、较高、中等、较矮”五个选项,但是如果数据集中身高为连续值,例如140-210cm,我们该如何处理呢?
这里可以采用二分的思想,将连续值化为离散值。由于我们的数据集是有限的,即使是连续值,属性a在数据集中也只出现了有限个确定的值,记为(a1,a2,a3......an)(a1,a2,a3......an),且a1<a2<a3......<ana1<a2<a3......<an。
取n个值的中点,令
t1=a1+a22,t2=a2+a32......tn−1=an−1+an2
t1=a1+a22,t2=a2+a32......tn−1=an−1+an2
我们得到了n-1个中点,(t1,t2......tn−1)(t1,t2......tn−1),任取一个值titi可以将数据集D分为两个,D+D+表示D中大于titi的数据,D−D−表示D中小于titi的数据集合,这样,我们便可以同离散值一样进行处理了。
接下来的问题是,选取哪一个t呢?显然在信息增益准则下,应该选择使得信息增益最大的t:
Gain(D,a)=maxtGain(D,a,t)=maxtEnt(D)−∑λ∈{+,−}|Dλ||D|Ent(Dλt)
Gain(D,a)=maxtGain(D,a,t)=maxtEnt(D)−∑λ∈{+,−}|Dλ||D|Ent(Dtλ)
经过稍加改造的信息增益公式就可以选择最好的t来进行划分。
缺失值处理
缺失值处理较为复杂,设计到较多的公式,在这里给出链接,读者可以参考阅读
缺失值处理详解
其主要思想是
在选择属性时,仅使用不缺失该属性的数据来计算信息增益,最后乘以一个代表缺失数据比例的比例系数
在对某个属性进行划分子节点时,对于不缺失该属性的数据正常划分,对于缺失该属性的数据,按不同的权重划分进行每个子节点
多变量决策树
实际上大部分机器学习的分类算法,都是将一个具有n个属性的数据,看成一个在n维空间的一个点,分类的过程就是在n维空间或者更高维度空间中找到超平面,将这些点进行划分。
而普通的决策树算法有一个特点,由于它每个节点的划分条件都是单独的,明确的,所以决策树的决策边界是平行于空间的坐标轴的。如下图所示:
这对其拟合特性有一定的影响,当数据比较复杂时,需要较多的属性才能得到较好的划分,而多变量决策树就可以解决该问题。
在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器。 如下图所示:
原文:https://blog.csdn.net/bravery_again/article/details/81104914
相关推荐
数据挖掘十大算法之决策树详解数据挖掘十大算法之决策树详解
决策树 信息熵(Entropy) 什么是决策树 决策树的构建过程 决策树分割属性选择 决策树量化纯度 决策树量化纯度 信息增益率计算方式 决策树的停止条件 决策树算法效果评估 决策树生成算法 ID3算法 ID3...
关于决策树算法解释较为清晰明了的PPT与代码,非常适合小白入门,以及作为面试的准备,有助于快速提升机器学习基础算法
机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3)算法及案例.docx机器学习--决策树(ID3...
决策树源文件,实例,内容详解,word文档
决策树和随机森林详解,决策树和随机森林详解,决策树和随机森林详解,决策树和随机森林详解,决策树和随机森林详解
决策树具体详解移步:http://blog.csdn.net/adiaixin123456/article/details/50573849 项目的目录结构分为四个文件夹algorithm,common,data,test (1)algorithm为算法,包括DecisionTree(决策树生成算法)、...
本章介绍另一种分类算法——决策树,用它预测NBA篮球赛的获胜球队。比起其他算法,决策树有很多优点,其中最主要的一个优点是决策过程是机器和人都能看懂的,我们使用机器学习到的模型就能完成预测任务。正如我们将...
使用Python实现用于判断西瓜好坏的决策树程序。 程序详解:https://blog.csdn.net/weixin_40973138/article/details/117999991?spm=1001.2014.3001.5501
决策树与集成算法详解,文章后面还有实战源码(也有详解) 下面是决策树优点 1. 决策树易于理解和解释,可以可视化分析,容易提取出规则; 2. 可以进行回归和分类 3. 比较适合处理有缺失属性的样本; 4. 能够处理不...
决策树,源代码,注释和详解,内附加说明,id3,CD_4型决策树
除了绘制树部分代码有借鉴,其他代码都是自己亲手完成,历时2天时间,过程稍微痛苦,当看到运行结果出现在...由于更喜欢C++编程,所以使用python类来完成~~~~,个人感觉面向对象更容易和更适合实现生成决策树的软件系统
主要介绍了Python决策树和随机森林算法,集合实例形式详细分析了决策树和随机森林算法的概念、原理及Python相关实现技巧与注意事项,需要的朋友可以参考下
决策树分类与上一篇博客k近邻分类的最大的区别就在于,k近邻是没有训练过程的,而决策树是通过对训练数据进行分析,从而构造决策树,通过决策树来对测试数据进行分类,同样是属于监督学习的范畴。决策树的结果类似如...
主要介绍了Python机器学习算法库scikit-learn学习之决策树实现方法,结合实例形式分析了决策树算法的原理及使用sklearn库实现决策树的相关操作技巧,需要的朋友可以参考下
本文实例讲述了Python机器学习之决策树算法。分享给大家供大家参考,具体如下: 决策树学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树。决策树...
李航统计学习第二版思维导图-决策树xmind格式,可以编辑。决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析...
决策树之CART(分类回归树)详解,具体内容如下 1、CART分类回归树简介 CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量。如果待预测分类是离散型数据,则CART生成分类决策树;如果待...
主要介绍了决策树剪枝算法的python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下