06061121
06061121
5月前 · 2 人阅读

01 决策树定义

之前我们学习了两种分类方法:
K近邻(KNN)
朴素贝叶斯(Naive Bayes)

今天我们来学习另一种分类方法——决策树

在开始学习之前,先提出一个问题:

这三种分类方法的区别是什么呢?分别适用什么场景呢?

好了,带着疑问,我们开始学习决策树~

决策树是什么?

它是一种基本的分类与回归的方法,可以认为是if-then规则的集合,决策树分类时,将某结点的实例强行分到条件概率大的那一类中去。

下面我们主要啊解释分类决策树,回归决策树在CART算法中有提及,篇幅限制,本文暂不做讲解。

它的优点是,模型具有可读性,分类速度快。

决策树定义

决策树由结点、有向边组成,结点分为内部结点和叶结点,顾名思义,内部节点就是特征或属性,叶结点就是决策树的末端,表示一个类,决策树大概长成这样:

我们用决策树分类时,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到子结点,这时每个子结点对应着分类特征的一个值,如此递归地对实例进行测试并分配,直到达到叶结点,最后将实例分到叶结点的类中。

02 决策树学习

在01节的末尾,我们概述了决策树的构建过程,这一节我们更进一步讲解决策树的学习过程。

目标:根据给定的训练数据集,构建一个决策树模型,使它能够对实例进行正确的分类。

本质:从训练数据集归纳出一组分类规则,由训练数据集估计条件概论模型,从而对训练集有很好的拟合,对未知数据有很好的预测。

步骤:

  1. 特征选择
  2. 决策树的生成
  3. 决策树的剪枝

学习过程
可以概括为,递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类。

具体步骤如下:

  1. 构建根结点,所有训练数据都放在根结点
  2. 选择一个最优特征,按照此特征将训练数据集分割成子集,使各子集有一个在当前条件下最好的分类
  3. 若子集已经能被正确分类,该结点变为叶结点;否则继续对这些结点选择最优特征,分类,如此递归下去
  4. 每个子集都被分到叶结点上,决策树生成
  5. step1~4可能对训练数据有很好的分类能力,但对未知数据的预测能力较弱(过拟合),于是需要对决策树进行修剪
  6. 去掉过于细分的叶结点,回退到父结点甚至更高的结点,然后将父结点或更高结点改为新的叶结点

常用算法:
ID3
C4.5
CART

03 学习步骤详解

决策树学习过程分为三个步骤:特征选择、决策树生成、决策树剪枝。

下面我们详细讲解每个步骤的算法和原理,介绍ID3算法和C4.5算法。由于篇幅限制,CART算法在本文暂不做讲解。

1. 特征选择

目的:选取对训练数据具有分类能力的特征,从而提高决策树学习效率

准则:
信息增益 (information gain)
信息增益比 (information gain ratio)

信息增益是什么?
定义为,集合D的经验熵H(D)与特征A给定的条件下D的经验条件熵H(D|A)之差

g(D,A) = H(D) - H(D|A)

其中,H(D), H(D|A)定义如下,

在热力学中,熵表示物质的混乱程度,在这里,我们可以这样理解信息增益:表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。信息增益越大,特征的分类能力越强。

如何选择最优特征
我们现在知道信息增益越大,特征的分类能力越强。有了信息增益这个工具,我们自然而然可以选择最优特征了——选择信息增益最大的特征。

再提一句,以信息增益作为划分选择数据集的特征,可能存在偏向于选择取值较多的特征的问题。因此产生了信息增益比这个度量,它规避了信息增益的问题,定义为:信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比。

2. 决策树的生成

算法核心:在决策树各个结点上应用信息增益准则(ID3算法)或信息增益比准则(C4.5算法)选择特征,递归地构建决策树。

过程:从根结点开始,对结点计算所有可能特征的信息增益(比),选择增益(比)最大的特征作为结点特征,由该特征的不同取值建立子结点,再对子结点递归地调用以上方法,构建决策树,直到所有特征的信息增益均很小或没有特征可以选择为止。

ID3算法

C4.5算法

3. 决策树的剪枝

决策树的生成算法(ID3, C4.5),因为过多地考虑提高对训练数据的正确分类,容易产生过拟合。

于是人们想出一个办法解决过拟合的问题:正则化(控制树的复杂度),及决策树的剪枝。

剪枝是将已生成的树进行简化的过程:从已生成的树上裁掉一些子树或叶结点,并将根结点或父结点作为新的叶结点,从而简化分类树模型。

原理:通过极小化决策树整体的损失函数或代价函数来实现。

决策树的损失函数
设树T的叶结点有|T|个,t是树T的叶结点,该叶结点有Nt个样本点,其中k类样本点Ntk个,Ht(T)为叶结点t上的经验熵,那么有:

决策树学习的损失函数

叶结点t的经验熵

决策树损失函数公式

其中:

  • C(T)——模型对训练数据的预测误差(即模型与训练数据的拟合程度)
  • |T|——模型的复杂度(即叶结点个数)
  • alpha——>=0,控制模型拟合程度和复杂度
    • 较大的alpha促使选择较简单的模型(树)
    • 较小的alpha促使选择较复杂的模型(树)
    • alpha=0表示只考虑模型与训练数据的拟合程度,不考虑过拟合

剪枝算法

4. 生成和剪枝算法的区别

决策树生成:只考虑通过提高信息增益(比)对训练数据进行更好地拟合,容易产生过拟合,相当于用极大似然估计进行模型选择。

决策树剪枝:还考虑减小模型复杂度|T|,从而减小过拟合,更好地对未知数据进行预测,相当于用正则化极大似然估计进行模型选择。

04 总结

今天我们学习了除KNN,Naive Bayes分类方法之外的另一种分类方法:决策树。

决策树可以用于分类和回归,我们主要学习了分类树。

我们给出了决策树的定义、学习过程以及过程详解,介绍了ID3、C4.5、剪枝三种算法。

其中,由于篇幅限制,CART算法(分类与回归数算法)没有介绍。

下期我们将学习逻辑回归,敬请期待~

收藏 0
决策树 结点 增益 分类 特征 算法
评论 ( 0 )