决策树算法

决策树

决策树算法是一个自顶向下的树(可以是二叉树，也可以是多叉树)。算法原理简单，易解释，分类性能较好。决策树是一种强大的、非概率的方法。

 

决策树非叶节点划分规则:

1.信息增益最大的先分，通俗来讲就是针对于因变量区分度最大的标签

2.离散变量采用是或不是的方法

3.连续变量采用>=或<=的方法

 

分枝策略:

分类树:信息熵

回归树:最小均方差

 

主要参数

 

最大深度:max depth

最大分区数:maxBins

 

ID3和C4.5

ID3根据信息增益去划分，计算通过比较信息熵的方法来划分。但是实际情况中会有这么一点比如说一个唯一键，像这种情况使用ID3的划分其实是无意义的。所以引入了C4.5。C4.5使用的是信息增益率的概念。所以不会出现这个问题。

 

ID3的缺点:

1.用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性

2.不能处理连续属性

 

C4.5的改进：

1.用信息增益比来选择属性

2.在决策树的构造过程中对树进行剪枝

3.对非离散数据也能处理

4.能够对不完整数据进行处理

 

C4.5采用悲观剪枝

 

CART

CART（Classification And Regression Trees，分类回归树）算法，CART是一个独立于其他经典决策树算法的算法，所以导致CART相对来说较为复杂。因为它不仅仅可以作为分类树，还可以作为回归树。采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

 

理解:记住这个定义，基尼不纯度表示在样本集合中一个随机选中的样本被分错的概率。互斥事件概率求和，独立事件概率求积。

举个例子:

 

 

ps:CART算法的决策树一定是二叉树

剪枝

剪枝的过程就是对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否会小于某个指定的阈值。如果确实如此，则这些叶节点会被合并成一个单一的节点，合并后的新节点包含了所有可能的结果值。

决策树的剪枝是因为防止过拟合。决策树常用的剪枝有事前剪枝和事后剪枝。

CART算法采用事后剪枝。

事前剪枝和事后剪枝都是基于给定的阈值来判断是否剪枝，区别在于在结点形成前，还是形成后。事前剪枝可能会导致过分简化的树，而较低的阈值可能使得树的简化太少。

悲观剪枝:有点复杂，主要就是一个叶子节点的元祖个数为K，其中分类错误的个数为J，通过J/K表示不能可信地估计错误率。

 

Sklearn

sklearn.tree.DecisionTreeClassifier

criterion = "entroy"是ID3算法,"gini"是gini系数

sklearn.tree.DecisionTreeRegressor

criterion = "MSE"(均方差),"MAE"(均绝对误差)

共有的参数

min_impurity_decrease(事后剪枝)和min_impurity_split(事前剪枝)

 

参考

https://blog.csdn.net/ACdreamers/article/details/44664481

https://juejin.im/entry/5adfe8696fb9a07aab298378

决策树（ID3、C4.5、CART、随机森林:https://blog.csdn.net/gumpeng/article/details/51397737

ID3 C4.5 CART决策树原理及sklearn实现:https://blog.csdn.net/jingjishisi/article/details/79379847