决策树算法
原来一直以为自己对决策树算法很了解了,今天有人问起的时候才发现原来一知半解。醒悟过来特作记录。
由于公式实在是太难敲了,所以下文基本没有公式,见谅。
一、简介
相对于其他机器学习算法来说,决策树是一种很简单的算法,它遵循‘分而治之’的策略,迭代的产生分类or回归结果。它的内容主要有三点:
(1)特征选择
特征选择在于选取对数据具有分类能力的特征,其间细节其实很多,比如特征选择的方法以及的它们的缺点、连续特征与离散特征的不同等。
A.特征选择的方法
1)信息增益---------ID3算法
ID3算法计算每个特征的信息增益,增益越大,这个特征的分辨性越好。但是这种方法有个问题,那就是它偏向于取值较多的特征(比如一些ID类特征,user_id,shop_id等等),这样训练出来的决策树缺乏泛化能力,要么将这些特征删除,要么改用其他算法
2)信息增益比------C4.5算法
C4.5算法采取信息增益比来选择特征,增益比越大,这个特征的分辨性越好。其实就是求出信息增益后再除以根据相应特征计算出的一个数,来减弱上文提到的信息增益偏向于取值较多的特征的缺点。但这个时候又带来了另一个问题,它偏向于取值较少的特征。因此C4.5算法并不是直接直接选择增益比最大的特征,而是采用了一个启发式的方法:先从候选特征中找出信息增益高于平均水平的特征,再从中找出增益比最大的特征。
3)基尼指数-----CART算法
其实真正使用的决策树最多的还是CART算法,它使用基尼指数(gini)来选择特征,选择gini最小的特征来划分。
B. 划分点的确定(连续特征与离散特征)
如果特征是离散的,那么很好办,直接计算上面三种指标的一种,那个特征好就选哪一个,借用机器学习一书的图进行说明:
特征都是离散的(比如纹理取值只有清晰、稍糊、模糊),如果选定了纹理这个特征直接划分就ok。
但是如果特征是连续,那么就不能这么办了,因为连续特征取值无穷多(就算你在训练集中当做离散值划分了,那么测试集来一个新的取值,那怎么办,不是抓瞎了)。这个时候,一般采用简单的二分法,比如 连续特征取值为{a,b,c,d,e.....},那就可以取划分点dot1=(a+b)/2,dot2=(b+c)/2.......把>=dot的当做一部分,把<dot的当做一部分(相当于划分为两个离散值了),然后再算指标。
(2)决策树的生成
不论是ID3还是C4.5还是CART,在每次决策树生长的之前都是先选择特征,在确定划分点,然后进行树的生长。但是这其中还是有一些注意点:
- 离散特征在树的生长过程只使用一次,后面就不再使用这个特征了,但连续特征可以多次使用
- 虽然机器学习一书说决策树可以处理缺失值,但实际这必须自己编程实现,python里面的决策树不能有缺失值,必须提前预处理
(3)决策树的剪枝
实际上,决策树很容易过拟合,所以会对他进行剪枝。常见的剪枝算法有两种,即‘预剪枝’和‘后剪枝’,使用剪枝算法是必须留一部分数据作为验证数据(留一法)。
预剪枝就是在决策树生成过程中对每个节点的划分进行预估计(就是到这儿停了作为叶子好呢还是继续长好),这就需要验证集进行确认。预剪枝算法本质上禁止节点继续生长,有欠拟合的风险。
后剪枝是在树长好后在剪枝,看将这个节点生成的子树去掉好呢还是不去掉好。相对于预剪枝来说,后剪枝时间开销大的多,但效果更好。
还是用机器学习书中图说明一下:分别是剪枝前、预剪枝、后剪枝
二、小结
(1)三种决策树算法的比较
(2)决策树算法的优点:
- 简单直观,生成的决策树很直观。
- 基本不需要预处理,不需要提前归一化。
- 使用决策树预测的代价是O()。 m为样本数。
- 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
- 可以处理多维度输出的分类问题。
- 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释
- 可以交叉验证的剪枝来选择模型,从而提高泛化能力。
(3)决策树算法的缺点:
- 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
- 决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
- 寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
- 有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
- 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。