对于一个如果,当存在其它的如果对训练例子的拟合比它差,但其实在实例的整个分布(也就是包括训练集合以外的实例)上表现的却更好时,我们说这个如果过度拟合训练例子。
这样的情况发生的一种可能原因是训练例子含有随机错误或噪声。
其实,当训练数据没有噪声时,过度拟合也有可能发生,这样的情况下,非常可能出现巧合的规律性。
有几种途径用来避免决策树学习中的过度拟合。
它们可被分为两类:
a) 及早停止增长树法,在ID3 算法完美分类训练数据之前停止增长树;
b) 后修剪法,即同意树过度拟合数据,然后对这个树后修剪。
一个常见的做法是错误率减少修剪：考虑将树上的每个结点作为修剪的候选对象。修剪一个结点由下面步骤组成:删除以此结点为根的子树;使它成为叶子结点;把和该结点关联的训练例子的最常见分类赋给它。
仅当修剪后的树对于验证集合的性能不差于原来的树时才删除该结点。这样便使由于训练集合的巧合规律性而增加的结点非常可能被删除,由于相同的巧合不大会发生在验证集合中。反复地修剪结点,每次总是选取它的删除能够最大提高决策树在验证集合上的精度的结点。继续修剪结点直到进一步的修剪是有害的。
2. 合并连续值属性
把连续值属性的值域切割为离散的区间集合。其实本质还是处理离散值、仅仅是将连续值划分为离散值。
3. 属性选择的其它度量标准
信息增益度量存在一个内在偏置,它偏袒具有较多值的属性。举一个极端的例子,考虑属性Date,它有大量的可能值(比如March 4,1979)。要是我们把这个属性加到数据中,它会在全部属性中有最大的信息增益。
这是由于单独Date就能够全然预測训练数据的目标属性。
于是这个属性会被选作树的根结点的决策属性并形成一棵深度为一级但却非常宽的树,这棵树能够理想地分类训练数据。当然,这个决策树对于后来数据的性能会相当差,由于虽然它完美地切割了训练数据,但它不是一个好的预測器(predicator)。
属性Date出了什么问题了呢?
简单地讲,是由于它太多的可能值必定把训练例子切割成非常小的空间。因此,相对训练例子,它会有非常高的信息增益,虽然对于未见实例它是一个非常差的目标函数预測器。
避免这个不足的一种方法是用其它度量,而不是信息增益,来选择决策属性。关于选取其它度量属性度量标准、參见參考资料。
4. 处理缺少属性值的训练例子
在某些情况下,可供使用的数据可能缺少某些属性的值。
比如,在医学领域我们希望依据多项化验指标预測患者的结果,然而可能仅有部分患者具有验血结果。在这样的情况下,常常须要依据此属性值已知的其它实例,来预计这个缺少的属性值。
处理缺少属性值的一种策略是赋给它结点n 的训练例子中该属性的最常见值。
还有一种策略是能够赋给它结点n 的被分类为c(x)的训练例子中该属性的最常见值。
5. 处理代价不同的属性
在某些学习任务中,实例的属性可能与代价相关。
比如,在学习分类疾病时我们可能以这些属性来描写叙述患者:体温、活组织切片检查、脉搏、血液化验结果等。这些属性在代价方面区别非常大,不论是所需的费用还是患者要承受的不适。对于这样的任务,我们将优先选择尽可能使用低代价属性的决策树,仅当须要产生可靠的分类时才依赖高代价属性。
考虑代价的相关算法參见參考资料。
參考资料：
1<<机器学习>> Tom M. Mitchell
2<<CS229--Machine Learning>> Andrew Ng
课程翻译：
讲义下载：
?course=MachineLearning
<完>
-------------------------------------------------------------------------------------
黑夜路人。一个关注开源技术、乐于学习、喜欢分享的程序猿
博客：
微博：heiyeluren
微信：heiyeluren2012
想获取很多其它IT开源技术相关信息，欢迎关注微信！
微信二维码扫描高速关注本号码：