Machine Learning Techniques Lecture 9: Decision Tree | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 9: Decision Tree


 
 

内容:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 


 
 

上一讲:

Adaptive Boosting 演算法,透过调整每一笔资料的权重的方式来得到不一样的hypothesis,同时在计算过程中决定每一个hypothesis的权重,然后用linear 的方式合起来,这样的方式被证明可以让分类结果变得比较好。

 
 

这一讲:

Decision Tree

 
 


 
 

我们先来看看 aggregation model:就是可以通过很多的g合起来变成大G来提升效果。这包括两种主要的面向。

Blending:我们已经得到了一些小g,可以透过uniform/non-uniform/conditional的方式把他们合起来,这三种情况下的blending的做法叫做 averaging/linear/stacking。

Learning:我们并不知道有哪些小g,需要边学习小g,边把他们合起来,同样可以透过uniform/non-uniform/conditional 的方式把他们合起来,这三种情况下的blending的做法叫做 Bagging/Adaboost/Decision Tree。

 
 

Decision Tree 就是补完这张表格,在不同情况下使用不同的小g,而且是边学习边合起来使用。这个方法的起源非常早,都比机器学习这个名词的出现还早,其做法就是模仿的人类的认知决策过程。

 
 


 
 

什么叫做Decision Tree?

 
 

这里是一个例子:你到底要不要下班后打开线上课程学习?

首先看是否下班早,早回则看一下是否有约会,晚回则看一下是否是作业的deadline,再确定会不会打开线上课程。

 
 

我们怎么来表达这个hypothesis?

 
 

小g:叶子节点,最后的决定;q:非叶子节点,条件,每一个都是比较简单的判断;所有的合起来就是G。

就是模仿人类的决策过程。

 
 


 
 

Decision Tree 也可以看作是:

每一个非叶子节点产生的每一个分支,都是一颗子树。b代表的就是分支,G_c就是在c的情况下的子树。

把一颗大大的树拆成几棵小树,递归定义。

 
 


 
 

在讲算法之前,先告诉大家一下有关Decision Tree的Disclaimers

 
 

优点:描述了整个做决定的过程,人很好理解,具有可解释性;非常简单;计算效率高。

缺点:基本没有什么理论保证,专注于流程设计;怎么去设计分支很难;通常没有什么比较具有代表性的好坏的算法。

 
 


 
 

练习

 
 


 
 

上面的黄色框表示的是递归公式表示的Decision Tree,够过这个公式可以把其演算法写出来:

输入是所有的资料,目标是产生一个树(G),过程中我们需要知道的是怎么产生分支(g)。

  1. 先看怎么做分支
  2. 根据分支分块
  3. 每一个分块用来学出小小的树,看是否要停下,不停下的话每棵小树再继续上面三步
  4. 所有的小树合起来就是G

 
 

一共包括四个决定:要分几支,怎么做分支,什么时候要停下开始组合G,叶子节点的结果是什么。对于每一个具体的Decision Tree演算法,都是对上面的四个决定做了独特的设计。

 
 


 
 

今天要给大家介绍的演算法: Classification & Regression Tree (C&RT)

 
 

  1. 每次一刀切成两份,就是分成两支(binary tree);
  2. 最后回传的g是constant,叶子就是一个常数,常数是由当前叶子范围内的Ein是最小的;

 
 


 
 

  1. 利用decision stump来切两半,也就是说只看一个feature,并通过这个feature把资料分成两半。

    切开后怎么样是最好呢?purifying:看切开后得到的资料看起来比较纯(y近似),用切开后两边会最纯的情况作为这次的切分。也就是说切开后纯度越来越高。

 
 


 
 

怎么衡量纯度?

可以看切开后要回传的常数是否够好来描述纯度,也就是用Ein来衡量。一般使用的时候classification的时候Gini比较常用,regression的时候regression error比较常用来衡量纯度。

 
 


 
 

  1. 所有的y都一样的话会被迫停下来,完全的纯,回传常数;

    所有的x都一样的话也会被迫停下来,完全没有下刀的情况;

    长到被迫停下来的树叫做fully-grown tree

 
 


 
 

练习

 
 


 
 

把 C&RT 做的四项选择写入到 decision tree 的算法里面就得到了 C&RT 的算法描述。上面的橙色,红色,绿色,蓝色对应的就是四个决定。

这种算法的一大好处就是处理multi-class classification和binary classification一样简单。

 
 


 
 

按照上面讲的 fully-grown tree 的切割方式来切的话,一定会得到Ein=0的树。但是这样是会比较不妙,会有overfit。

 
 

我们需要一些regularizer的机制来控制复杂度来放置overfit。

 
 

Pruned Decision Tree:

一种方式是控制树叶的数量,也就是不让切特别多刀,树叶的数目和切的刀数相关。

所以做法可以是把所有的树都做出来,看看每棵树的Ein是多少,算算其复杂度是多少,然后用lamda平衡一下,我们不要只选择切的很深的Ein很小的树。

这件事情不那么好做,我们要考虑遍历所有的可能的树的结构不现实。

 
 

实际上的做法:

首先得到一颗完全长成的树,然后尝试着去合并一次两片叶子,做所有的情况,找出只合并两片叶子Ein最小的树G_1。再从这摘掉一片叶子的树出发在同上面的方法再去摘一片叶子,得到最好的摘掉两片叶子的树G_2。以此类推得到G_n。

我们接下来就是在这些摘掉x片叶子最好的树里面做选择,找到一个平衡的最佳解,就是去确定lamda,方法是validation。

 
 


 
 

C&RT 还有一些其他的特征:

 
 

【类别支持】

  1. 输入部分不一定是数字,可能是类别,例如病人的症状等,会影响怎么去做切割。

这时候需要用 Decision Subset 来做切割:可以穷举类别,人为定义左右或者大小来做。

 
 


 
 

对于人来说:

例如我使用体重来区分人群,但是有个人进来忘了称体重,怎么办?可能是去马上去量体重;可能通过目测身高估体重,所以可以改通过身高区分。

 
 

【支持特征丢失的资料】

  1. 对于特征丢失的资料,怎么用我们的Decision Tree来处理呢?

训练的时候会为每个特征找一些替代品,通过替代品做切割得到的结果要和原来的方式类似,替代品是训练的时候就已经学习好了的。

 
 


 
 

练习

 
 


 
 

一个例子

 
 


 
 

确定下刀,两边各自组成树,合起来就是大树。

 
 


 
 

第二刀

 
 


 
 

第三刀

 
 


 
 

第四刀

 
 


 
 

区域都纯洁了

 
 


 
 

回传叶子节点的类型

 
 


 
 

递归上一层

 
 


 
 

再上一层

 
 


 
 

回到大树

 
 


 
 

和Adaboost对比:Adaboost每一刀一定是贯穿整个区域,但是decision Tree就不一定,因此相对来说比较有效率。

 
 


 
 

复杂的例子

 
 


 
 

C&RT 算法的好处:

  1. 人看得懂的决策方式
  2. 可以容易的处理多类别分类
  3. 可以容易的处理类别输入
  4. 可以支持测试资料的特征残缺
  5. 训练测试都很有效率

几乎没有其他的模型有这么多的好处,因此也是一种常用的方法。

 
 

实际上还有 C4.5 这种 decision tree 算法,自己可以去看一下做了哪些特殊决定得到的。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 

下一讲:

至此讲完了Aggregation的基本模型,下一讲进入一个更高的境界,开始把已有的aggregation方法混起来用,叫做Aggregation of Aggregation。


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags