02 决策树 - 初识与构建-阿里云开发者社区

开发者社区> 人工智能> 正文

02 决策树 - 初识与构建

简介:

在讲决策树之前补充了一些基本概念:比特化、信息熵、条件熵,重点理解熵的概念。本章开始正式进入机器学习模型-决策树。
01 决策树 - 数学理论概述

决策树 Decision Tree: 在已知各种情况发生概率的基础上,通过构建决策树来进行分析的一种方式,是一种__运用概率分析的图解法__。

决策树是一个预测模型,代表对象属性和对象值的映射关系;每个叶子节点都代表一种类别;

决策树分为:决策树可用于__有监督__的分类和回归算法,回归用于预测连续值,常用算法:ID3、C4.5、CART等。

一、决策树构建过程

决策树算法的重点是决策树的构造,构造过程是进行属性选择度量,确定各个特征属性之间的树形关系。

构建决策树步骤是分裂属性,分裂属性是指在某个节点按照某一类特征属性的不同划分,构建不同的分支。目的在于:让各个分裂子集尽可能$color{red}{纯}$。即让一个分裂子类中,待分类的项尽可能的属于同一类别。

比如:根据一个人有没有喉结来判断是男是女。
通过“是否有喉结”这一属性分类出的两个子类:“男”,“女” 。这是一个比较$color{red}{纯}$的分类。原来人的分类是男是女不确定性很高,但根据上述分类之后,男和女的分类相当清晰,此时该系统的不稳定性会比较低。

但是:如果根据一个人 “是否带眼镜” 来判断是男是女,显然分类的结果不如根据 “是否有喉结” 进行分类效果好。

此时理解:__构造过程是进行属性选择度量,确定各个特征属性之间的树形关系。__ 这句话的含义是不是就清晰多了。

二、构建步骤如下

1、将所有特征看成一个一个的节点。
2、遍历每个特征的每一种分割方式,找到最好的分割点;将数据划分为不同的子节点,N1、N2、...、Nm,计算划分之后所有子节点的$color{red}{纯度}$信息。
3、对于第2步产生的分割,选择出最优的特征以及最优的划分方式;得出最终的子节点:N1、N2、...、Nm;
4、对于子节点N1、N2、...、Nm分别继续执行2~3步,直到每个最终子节点都足够$color{red}{纯}$。

思考决策树和KD树的区别:
01 KNN算法 - 概述
02 KNN算法 - KD Tree
KD树是一个二叉树,而决策树每一层的叶子节点可以有多个。


步骤分析:现在有若干特征x1、x2、... 、xn

__假设1:__特征x为是否有喉结。
那么对于特征值的划分必然是(0-有,1-没有),特征划分方式只有一种。二叉树。

__假设2:__特征x有三种取值:(0,1,2) 那么分类方式有几种?
第1种:(0,1,2);三个叶子节点。
第2种:属于0类,不属于0类;二叉树。
第3种:属于1类,不属于1类;二叉树。
第4种:属于2类,不属于2类;二叉树。
在这4中分类方式中,我们可以找到一个对系统稳定性最佳的分类方式。

然后对于若干特征x1、x2、... 、xn,我们需要遍历出每一种特征__所有__的分类方式,并找到一个对系统稳定性最佳的分类方式。

再针对上一步已选出的特征x1、x2、... 、xn中的最佳的分类方式,我们再从这n个分类方式中再找到一个最佳的分类方式,做为决策树第一次分裂。这次的分裂是所有选择中最$color{red}{纯}$的分割方式,是整个系统中的最优分割方式。

得到第一个最$color{red}{纯}$的分割方式即生成了第1组子节点,我们还可以继续往下划分,以此类推。

注意:
1、一切划分的标准都是基于目标值Y的,一个理想的算法结果是:每一次分割后的子节点,都更够更好得体现目标值。

2、如果一次分裂将子节点分割得太细,如动物分类,我们不是分割到狗就结束,而是一次细分到狗的每一个品种(金毛、泰迪)。分得太细可能会引起过拟合的问题。

3、针对连续值的划分:确定一个值s作为分裂点,将大于s的值作为一条分支,小于等于s的值作为另一条分支。

三、决策树分割属性的选择

决策树算法是一种 “贪心算法” ,我们只可能考虑到每一次分裂的最优分割情况,但是无法找出全局的最优划分情况。

对于整体数据而言,按照所拥有特征属性进行划分操作,对所有划分操作的结果集$color{red}{纯度}$进行比较,选择$color{red}{纯度}$越高的属性作为当前需要分割的数据集进行分割操作。持续迭代,直到得到最终结果。

决策树是通过$color{red}{纯度}$来选择分割特征属性点的。

PS:在本文中,唯一没有深入解释的术语是$color{red}{纯度}$,文章中统一使用红色标注。$color{red}{纯度}$是非常重要的一个知识点,会在下一章深入描述。本章中,请先充分认识到$color{red}{纯度}$在决策树中的作用和意义。

03 决策树 - 量化纯度、信息增益度、停止条件、评估

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章