机器学习数据挖掘自主学习心得5——决策树和回归树
讲了一上午，中间只休息了一次，也只是简单介绍完了lasso，nn-garrotte还有LARS算法，以及在group
首先要讲的东西，是所谓的回归树。之前在我的博文中有介绍过决策树，大多是用来分类的。选择分类属性的标准是信息增益最大，涉及到熵这个概念。而在做回归树的时候，我们希望和回归这个东西多一点联系，因此选择变量的标准我们用残差平方和。熟悉通常意义的回归分析的人，一定知道回归分析的最小二乘解就是最小化残差平方和的。在决策树的根部，所有的样本都在这里，此时树还没有生长，这棵树的残差平方和就是回归的残差平方和。然后选择一个变量也就是一个属性，这个变量使得通过这个进行分类后的两部分的分别的残差平方和的和最小。然后在分叉的两个节点处，再利用这样的准则，选择之后的分类属性。一直这样下去，直到生成一颗完整的树。（生成完整树的标准，即算法何时停止在之前的博文中有介绍，这里也不赘述）。
生成了一个完整的树，也会遇到问题。问题一是这棵树对于非训练样本可能预测并不准确，问题二就是训练样本可能有错误的树，那么训练出来的树就也不正确。为了解决这个问题，我们引入一个解决方法，cross-validation。这里只介绍其中一个比较可爱的策略。也就是先把样本分两半，然后拿一半去生成一颗树，用另一半去剪枝。然后再拿另一半在已经被剪过的树上继续生成树，然后用之前的一半减枝。然后再调换，再往复，直到这棵树的大小不再变化了。
那么剪树枝的原理又是什么，什么样的树枝该被剪掉呢？准则也很简答，比如我们剪掉一枝（带两个树叶和它们的母体枝），那么这棵树就变了，我们用训练样本来评估这棵树，如果训练样本在这棵被减的树中得到的残差平方和缩小了，那么剪树枝就有效，就该剪，否则就不剪。
至此，我们构建了一棵回归树，就如回归分析一样，做回归的目的是为了预测。那么回归树用来预测的时候也会遇到和回归模型预测方面同样的许多不确定性。也就是这棵树对于新入选的样本估计或许并不那么准确，比如说，如果样本的响应变了，整个树就会变。那么我们就要估计当样本变化时候，这棵树变动的差异。这种估计，目前十分流行的是Efron提出的bootstrap，通过重新抽样，来估计无差，这种方法的原理很简单，但是实用性非常大。
以上是我今天坐公交车看论文的一些体会心得，论文其实是我从卡耐基梅陇的网站上下载的决策树与回归树的讲义。讲义中是用R语言实现决策树的，函数名字就叫tree。关于bootstrap，还有cross-validation这两种策略，我想在实际工作中肯定应用的非常广泛，下一篇博文主要讲谢邦昌那本书中关于决策树的部分，然后介绍一下spss如何实现决策树。今天就先到这里，做点腹部运动，看着我这圈肉就心烦意乱。
ps：之前有师弟和我讨论数学建模的事情，我建议他们先学点基本的算法，我深刻体会到，有了这些算法，解决问题的手段变的非常多。而且我们的很多聪明的统计学家也提出了很多策略，bootstrap和cross-validation都是很好的策略。应该读点这方面的资料。Efron介绍bootstrap和jackknife的书我去年印了，为了写个小型作业报告，简单了解了一下，其实还是值得细看的。另外，Efron就是我之前博文中LARS算法的提出者，这位stanford的统计学家，可谓是当今模型届的泰斗。榜样榜样啊.
转载请注明：数据分析 » 机器学习数据挖掘自主学习心得5——决策树和回归树
