之前写过决策树的一篇blog：http://blog.csdn.net/ice110956/article/details/10049149
这几天看数据挖掘导论发掘一些新的东西，记录下来。

过拟合问题

这是之前blog http://blog.csdn.net/ice110956/article/details/14002791引用Ng的一般误差与经验误差的关系。

可以看出，一般误差正比于VC维，反比于训练集大小（说法不太严格）。

过拟合就是第二项太大导致一般误差太大。

导论上关于一般误差的比喻比较好，引用一下：

假设关于球赛，有个评论员，随机猜测结果，也就是正确率为0.5。那么在10场比赛中至少猜对8场的概率为

很小。

但是，如果有50个这种评论员，那么其中有一个能至少猜中8场的概率是：

那么可以这么说，50个人中，至少有一个可以假装是很好的评论员。

同样的道理，当决策树划分到很小集合时，这些剩下的训练样本不同之处是很随机的，并且受噪音影响很大。也就是，我们这时做的任意决策，都带有随机猜测的性质。

虽然这个时候，我们认为决策得到训练误差很小，就像上面计算的90%的准确率，但是这也是随机猜测中取较好结果的假象而已。

真实的准确率还是随机猜测的结果。

简单说：越往细分，决策越没有概括性，趋向于随机猜测。训练准确率高，只是假象而已。

剪枝

决策树有几种剪枝法：

1.预剪枝：设定阈值

当划分到一定数量时，结束划分，取较多的一类样本标签作为此节点标签

2.后剪枝：整合节点

在决策树建立完成后，再整合节点，多个节点合并（小节点融合）；常用节点与不常用节点合并（测试时较常访问的节点）

后剪枝一般比预剪枝有更好的效果，不过会更复杂，以及增加了计算复杂度。

纯度计算的几种方法

信息熵：ID3的计算方法

这二类情况下，三种纯度计算方法图形如下

可以看出，这三种方法的效果基本一致。实验也证明，这三种方法都有相似的结果。