关于决策树的更多——CART

上篇讲了ID3的后继C4.5，这篇讲讲有略大不同的（Classification and Regreession Tree，分类回归树）。它的特点是二分递归，产生真正的二叉树（这才是真正的Dichotomiser.。。。。=-=），也就是说无论是连续属性还是有两个值以上的离散属性，CART都只会把它们分成两个分支。

基尼指数
CART不使用熵的思路来衡量属性划分度量，而是使用了基尼指数（Gini Index）。一开始以为这是从经济学上拿来利用的概念，后来看来大概只是两者来自同一思路。维基百科上对CART的这一种度量称为基尼不纯度（Gini Impurity）。
经济学上，基尼系数用来衡量地区的收入不平等程度。在CART中它用来衡量训练集在某属性上的不纯度，定义：

划分连续属性称为二值属性的方法在讲C4.5时已经说过，这里只说如何划分离散属性。对于一个离散属性A，假设其值域为集合, 其幂集包含了它的所有子集。不考虑空集和其本身的情况，一共有个子集，又因为划分时，知道其中一个子集，另一个就是它的补集，划分方案有个，枚举划分方案有随集合大小指数增长的复杂度。
对于枚举出的对离散或是连续值的划分方案，我们计算其基尼系数：

我们选择基尼系数最小的划分方案来将非二值属性二值化，然后通过比较基尼系数，选择最小基尼系数的属性，也即分化程度最小的属性。

选用熵和基尼系数有何不同，我想这样一幅图能给出答案：

两者都在二值属性均分的时候达到最大值，但它们逼近最大值的速度变化不同，但在应用上有何区别上不得知。

代价复杂度
在剪枝问题上CART也是不同的，CART后剪枝使用的是代价复杂度（Cost Complexity）这一概念，对于一棵子树，其代价复杂度是这棵子树的错误率和叶子节点数的函数，有时表示成。类似悲观错误率，比较剪枝前后的代价复杂度，若复杂度变小，则剪去子树。剪枝的方法是自底向上对内部节点进行判断。

决策树的局限
前剪枝和后剪枝的结合使用能减少过拟合的现象，但在数据量大时还是难免防止树过大的情况，我们经常能遇到重复或是复制的问题。
重复（Repetition）即是从根节点开始的一条路径中，连续出现好几个对同一属性进行判断的节点。比如连续属性A的选择度量很大，那么我们经过第一次分裂分成了两个区间后，很有可能接下来的属性选择仍然选择的是A。
复制（Replication）是书中存在重复的子树，例如根据属性A划出两个子树，这两个子树又都按照B属性划分，便有了一毛一样的两个分支。
上面的两种情况在作业中也的确遇到了，也就是我们还没引入熵阈值的时候，树的深度不堪入目，那么可想而知更大的数据集这类问题大概更严重。
CART的一个解决办法是考虑多元划分，基于属性元组，而不是单个属性来划分，相当于构造出了新的属性。虽然教材上没提到，但我想到的一个思路是先将属性用类似机器学习中主成份分析（PCA，Principal Component Analysis，这个算法也是通过美赛第一天想思路时知道的）的方法，将多维的向量在不大量减少其信息值的前提下降维。
教材中提到的另一决策树局限是当数据集大到无法由内存装载的情况，如果只能从存储中分页读取训练集，那么我们无法同时掌握整体数据集的信息。两个思路能帮助解决，一是离散化连续属性，从而减少编码的空间，而是对数据进行抽样，而不利用全部的数据，当然，这就涉及到了抽样的代表性。这两个思路都很容易想到。还有诸如雨林（Rainforest）和树构造自助乐观（BOAT）等更厉害的算法，不过也是to be study了。

分类作为一个经典问题不止决策树一种方法，下一个想看的是贝叶斯分类。