机器学习实战2 - 决策树

06 Jan 2018 by LelouchHe

决策树(Decision Tree)

chapter03 ID3 chapter09 CART

决策树算法也是一种比较直观的机器学习算法,可以用于分类(classification)或回归(regression).决策树的一个最大的优点是可以显式的总结出数据体现的规则,这样的规则有助于人们更进一步的理解数据.另一个优点是快速,相比于k最近邻每次都需要全部数据,决策树只需要树高最大为属性数目的树形结构即可,小而且快速.

决策树很类似于我们平时做判断的过程,当我们面对众多属性时,我们肯定会逐个属性的进行分析,要不就是基于非常明显的特征,直接得到结论,要不就是逐步的排除不可能的结论,直到最后的结论.具体步骤如下:

1. 挑选一个最优的可以被用来划分的属性
2. 以该属性值将既有数据划分,并构建当前节点的子树,每个子树对应划分好的子数据集
3. 递归的处理每个子树和子数据集

这只是决策树的训练步骤.与k最近邻不同,决策树是需要事先通过训练集训练的(当然,k最近邻其实也要训练,比如前文说的如何寻找k值,就是训练的过程).之后,才能用来进行测试集的测试.使用的具体步骤如下:

1. 取当前节点属性对应的数据的值
2. 根据值,选择对应的子树
3. 递归处理子树,直到到叶子节点,得到最后结论

可以看到,使用的时候,最多经过属性数目次的递归操作,就能得到最后的结果,而且整个数据集的对应的特征,已经被树形结构抽象概括出来了,也就无需数据集参与了.其实这本质上很像基于规则的机器学习,只不过此处的规则,是基于属性值的划分而已.

决策树同样有3个需要注意的问题

如何划分

事实上,决策树的众多算法的区别的重点,就在于此.书上第3章介绍的ID3算法(Iterative Dichotomiser 3)和第9章介绍的CART算法(Classification And Regression Trees),都是从不同的角度看待基于属性划分后的优劣情况,或者用机器学习上的说法,使用的不同的归纳偏置(inductive bias)

• ID3算法: 划分后信息增益(information gain)越高,越好.
• CART算法: 划分后方差越低,越好.

这两种算法,从结果来看,都是试图用贪心的方法,构建一个比较矮的树,所以二者的归纳偏置可以总结为:越矮的树,越好.就和梯度下降(gradient descent)一样,难免陷入局部最优,这个我们另说.

信息增益

ID3使用的信息增益,是一个信息论的常用量,是指信息熵(entropy)的减少.信息熵一般可以理解为信息的混乱程度,具体公式为:

\[E(D) = - \sum _ {i = 1} ^ {n} P(D _ i) \log _ {2} (P(D _ i))\]

其中$P(D _ i)$表示$D _ i$在数据集D中的概率.可以看出,如果数据集D只有1个值,那么$E(D)$为0,可以理解为一点都不混乱,如果数据集D中的每个值的数量都相同,此时$E(D)$为1,可以理解为最混乱

而ID3所做的,就是针对所有的没有被使用过的属性,分别计算对应的信息熵的减少(划分之后的信息熵减去之前的信息熵),即信息增益,最后挑选出信息增益最大的属性,并进行递归划分.可以理解为,我们希望每次的划分,总能将数据集分割成最较为整齐的子数据集.比如现在我们手上有不同颜色不同大小不同形状的积木要进行分类,我们肯定会争取每一步都分成大体上均衡的几部分,从而使下一步的划分更容易.

其实再思考下,这个的本质,不就是二分的本质么?为什么很多情况下,二分总是能最快的得到结果呢?除了算法上的推导外,也可以通过信息熵的角度来理解

闲话一句:这其实也是可以运用到生活中的.看似复杂的问题,在没有头绪的时候,朝着信息熵减少的方向努力,至少不会有太坏的结果的.共勉.

再闲话一句:信息熵的公式非常的有趣,感觉是在一系列既定假设之下,构造出的满足全部条件的公式之一.最近有同事试图判断集合间相似度,使用了一些naive的公式,看了感觉不是很妙.这种的推导,我觉得应该先定义清楚需要满足的假设与性质,然后再在简化计算的基础上,构造合适的公式.一个比较有趣的例子就是知乎上对矩形面积的推导,虽然我不知道这是不是真的,但这个思路我已经看到过很多了,包括数学物理甚至经济学里,都有很多利用.可以好好借鉴下.

方差

CART则是比较直接的使用方差.方差是指数据集结果偏离均值的程度,也在一定程度上反应了该数据集混乱的程度.如果仔细计算一下,方差和上文的信息增益,应该大体上的方向是类似的,只不过方差计算的更快.具体公式为:

\[V(D) = \sum _ {i = 1} ^ {n} V(D _ i)\]

在实际操作中,就是要针对所有没有被使用过的属性,分别计算划分后的方差,然后选择划分后方差总和最小的那个属性,来进行递归的划分.与信息增益这个相对值不同,方差是个绝对值,并不需要同当前进行比较.

思考

这两种算法其实大同小异,都是针对单属性的划分.我的想法是,有没有基于多属性的划分.当然,多属性的划分,可以看作多次单属性划分,但有的时候,也不一定全都是这样.比如我们平日里在做某些事情时,我们不一定是精确的根据某些特征来进行判断,有的时候仅仅是多个特征组成的某些模式(pattern),但单看这些特征的话,则没有类似的功能.

我的想法是给划分增加更多的上下文信息,也许是多属性,也许是其他什么,从感觉上讲,可能会有提升的空间.

如何结束

如何结束包括2个子问题

在哪里结束

在哪里结束表示的是递归划分结束的条件,一个直接的条件就是没法划分下去了,比如没有多余属性或者信息增益/方差没法变化了(通常就是该数据集的结果都是一样的了)

另一个稍微有些优化的则是由用户设定阈值,当信息增益或方差变化达不到阈值时,提前结束递归.个人感觉虽然这样的处理并不能让树的构建快多少,但这种思路,很像我们后面要提到的减枝(prune)

用什么结束

这就和具体使用树的目的有些关系了.

• 分类: 叶子节点应该保留的是当前数据集中较多的结果的值
• 回归: 针对CART,叶子节点可以保留当前数据集的线性回归的权值(weighted value / ws)

思考

个人看来,这个问题是很实现相关的了.只要能从最后叶子节点的信息中,得到我们的最终结果,就可以了,并没有规定只能存什么或者不能存什么.这在多种机器学习算法结合的时候,尤为关键.

比如我们在大的方向上是使用决策树的,但结束条件上我们设定了很大的阈值,或者识别某种模式,然后在叶子节点利用其它的算法,对满足决策树路径条件的数据,进一步的处理分析.这样做也是完全没有问题的.

在学习机器学习的时候,最忌讳生搬硬套.虽然我们有很多现成的工具和平台,但结合具体数据和场景分析,并主动使用这些机器学习工具,还是非常必要的

如何避免过度拟合

相比于k最近邻,决策树的参数就比较多了,每一个分支都可以看作一个参数.参数多就容易引起过度拟合,也就是过度的拟合了训练集,包括真正的数据模式与训练集自身的噪声,导致在测试,或真正使用的时候,存在很大的偏差.过度拟合其实就是要砍参数.

对于决策树来说,就是减少分支,合并节点

• 前减枝: 在树构建好之前,进行减枝.比如上文”在哪里结束”提到的设定阈值,可以提前结束从而减少分支数目.前减枝效果不好,因为有些方法很靠分析和经验,一旦决策错误,相当于把正确的树直接砍掉了,后面再怎么补,都是无济于事的.
• 后减枝: 在树构建好之后,进行减枝.递归的判断某个分支是否需要合并.此时不能使用训练集来判断,而是要用单独的测试集.判断的标准大部分时候是上文提到的划分标准,也可以是新的标准

其实,避免过度拟合,一个重要的方法就是划分训练集和测试集,并且在训练过程中,定期的用测试集来判断错误率.Ng提到用plot的方法,可以很直观的看到训练集错误率和测试集错误率的关系,从而了解算法过度拟合的状态

总结

优点

• 符合常识
• 可以总结出可读的规律
• 一旦训练完成,不需要原始数据

缺点

• 有过度拟合的危险
• 需要数据集的正确性较高,一旦有错误,很容易把正确的树砍掉

思考

决策树最大的优点是能提取出可读的规律来.一旦构建成功,我们可以通过树结构本身,更深刻的理解原有的数据.这是很多其他算法所不能的,比如k最近邻,逻辑回归,神经网络等.

树形结构本身又是规则的一部分,因此也可以看作是简单版本的基于规则的系统.基于规则的系统还有很多,听说有很多专家系统就是基于规则实现的,有很多也是以决策树的形式,在很多领域取得了很大的成功.有机会的话,需要好好研究类似的东西