Question

决策树原理及算法比较

Answer 1

决策树是什么？

    和线性回归一样是一种模型，内部节点和叶节点。实现分类，内部节点和叶节点通过有向线（分类规      则）连接起来

决策树的目标是什么？

    决策树通过对数据复杂度的计算，建立特征分类标准，确定最佳分类特征。

    表现为“熵”（entropy）和信息增益（information gain），基于决策树思想的三种算法：ID3，C4.5,CART算法，三种算法的信息衡量的指标也不同.

    熵来表示信息的复杂度，熵越大，信息也就越复杂，公式如下：

那些算法能够实现决策树？

    在决策树构建过程中，什么是比较重要的。特征选择（按照熵变计算），算法产生最重要的部分，

决策树中叶节点的分类比较纯，

节点顺序的排列规则：

熵变：

数据的预处理：

改进思路一般有两个1，换算法；2，调参数

做好数据的预处理：

1，做好特征选择；

2，做好数据离散化、异常值处理、缺失填充

分类器：

在决策树中，从根到达任意一个叶节点的之间最长路径的长度，表示对应的算法排序中最坏情况下的比较次数。这样一个比较算法排序中的最坏情况的比较次数就与其决策树的高度相同，同时如果决策树中每种排列以可达叶子的形式出现，那么关于其决策树高度的下界也就是关于比较排序算法运行时间的下界，

ID3算法存在的缺点：

    1，ID3算法在选择根节点和内部节点分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性

    2，当数据为连续性变量的时候，ID3算法就不是一个合理的算法的模型了

C4.5信息增益比率，

     1，在信息增益的基础上除以split-info，是将信息增益改为信息增益比，以解决取值较多的属性的问题，另外它还可以处理连续型属性，其判别标准是θ，

      2，C4.5算法利用增益/熵值，克服了树生长的过程中，总是‘贪婪’选择变量分类多的进行分类

      3，处理来内需型变量，C4.5的分类树的分支就是两条

衡量指标：

（1）信息增益

基于ID3算法的信息增益对于判定连续型变量的时候病不是最优选择，C4.5算法用了信息增益率这个概念。

分类信息类的定义如下：

这个值表示将训练数据集D划分成对应属性A测试的V个输出v个划分产生的信息，信息增益率定义为：

选择最大信息增益率的属性作为分裂属性

Gini指标，CART

表明样本的“纯净度”。Gini系数避免了信息增益产生的问题，

过拟合问题，非常好的泛化能力，有很好的推广能力

Gini系数的计算：

在分类问题中，假设有k个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：

如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的提哦啊见下，集合D的gini指数的定义为：

Gini指数代表特征A不同分组下的数据集D的不确定性，gini指数越大，样本集合的不确定性也就越大，这一点和熵的概念相类似

决策树原理介绍：

第三步：对于每个属性执行划分：

（1）该属性为离散型变量

记样本中的变量分为m中

穷举m种取值分为两类的划分

对上述所有划分计算GINI系数

（2）该属性为连续型变量

将数据集中从小到大划分

按顺序逐一将两个相临值的均值作为分割点

对上述所有划分计算GINI系数

学历的划分使得顺序的划分有个保证，化为连续型变量处理。

决策树的生成算法分为两个步骤：

预剪枝和后剪枝  CCP（cost and complexity）算法：在树变小和变大的的情况有个判断标准。误差率增益值：α值为误差的变化

决策树的终止条件：

      1，某一个节点的分支所覆盖的样本都是同一类的时候

      2，某一个分支覆盖的样本的个数如果小于一个阈值，那么也可以产生叶子节点，从而终止Tree-Growth

确定叶子结点的类：

      1，第一种方式，叶子结点覆盖的样本都属于同一类

      2， 叶子节点覆盖的样本未必是同一类，所占的大多数，那么该叶子节点的类别就是那个占大多数的类