signed

QiShunwang

“诚信为本、客户至上”

决策树算法笔记

2021/4/26 14:16:11   来源:

决策树 很重要的一个概念是信息熵,这一点统计学习方法书上记录的很清楚了,就不在此记录了,记录一下几个方法大致的pipeline以及优缺点。

 

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归的构建决策树。

流程如下:1. 看是否符合单一类的特征,如果不用在分类了,那就是一个叶子结点;

2. 对于集合中所有的类算信息增益,选择信息增益最大的特征作为结点分类区别;

3. 如果该结点的信息增益小于阈值\varepsilon,则返回。

4. 将类别最多的一类作为标记,构建子节点。

5. 重复1-4的过程。

 

C4.5算法和ID3算法类似,但是用信息增益比来选择特征,取代了信息增益,因为在使用信息增益作为划分训练数据集的特征时,存在偏向于选择取值较多的特征的问题。

 

在决策树上,可以用结点数量来表示结点复杂度,来做一个约束复杂度。

决策树的剪枝,就是通过优化损失函数(包括模型复杂度),因为决策树在建立的时候,是不考虑模型复杂度,只考虑信息增益。

剪枝过程:

1.计算每个结点的经验熵;

2.从叶子结点往上回缩,计算损失函数值,如果缩回之后的损失函数较低,则进行剪枝。

 

cart算法:只记录分类树的过程。

分类树的生成过程:1.找切分点。

2.对于每一个特征:

    2.1 对于每一个切分点:

        计算其的基尼指数,选择基尼指数最小的切分点作为这一特征的切分点。

   2.2 对于这一轮特征的选择,选择所有特征中基尼指数最小的那一个作为切分的特征。

  2.3 停止条件:结点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值(样本基本属于同一类),或者没有更多特征。

 

cart树剪枝的过程:

1. 自下而上地对各内部结点 计算g(t),损失函数与总树的差值/结点的数量。

2. 每一次对于最小g(t)值的结点进行剪枝,

3.重复1-2的过程,最后根据 \alpha 的大小区间进行分类,分出n+1 个树,取最小的损失函数值的树为 最优子树。