噪声和过拟合

18.3.6 噪声和过拟合

前面我们已经看到如果有两个实例属于不同类别但是描述相同（在属性方面），那么DECISION-TREE-LEARNING算法一定找不到和所有实例都一致的决策树。我们以前提出的解决方法是，当需要确定性的假设时，让每个叶节点报告它的实例集的多数分类，或者利用相关频度报告每种分类的估计概率。不幸的是，这与我们想要的相差甚远。相当可能的是，并且事实上很可能的是，即使缺少了重要的信息，决策树学习算法仍然可以找到一棵满足所有实例的决策树。这是因为决策树可以使用无关的属性（如果有的话），伪造实例之间的区别。

考虑试图预测掷骰子结果的问题。假定实验是用不同的骰子长期进行的，并按照如下的属性描述每个训练实例：

① Day（日）：骰子在哪天掷的（星期一、星期二、星期三、星期四）。

② Month（月份）：骰子在哪个月掷的（一月或二月）。

③ Color（颜色）：骰子的颜色（红色或蓝色）。

既然不存在具有相同描述的两个实例，那么 DECISION-TREE-LEARNING将找到一个完全的假设。属性越多，找到完全假设的可能性越大。而任何一个这样的假设都彻底是伪造的（这些属性其实和掷骰子的结果不相关——译者注）。我们所希望的是DECISION-TREE-LEARNING一旦观察到足够多的实例，它就能够在每次掷骰子时都以接近1/6的概率返回一个唯一的叶节点。

只要存在大规模的可能假设集，那么我们就必须小心谨慎，不要利用产生出的自由在数据中寻找毫无意义的“规律性”。这个问题被称为过拟合。作为一个非常普遍的现象，甚至在目标函数根本不是随机的时候，过拟合也会发生。不仅决策树，每种学习算法都存在过拟合的问题。

对过拟合进行完备的数学处理已经超出了本书的范围。在这里，我们介绍一种被称为决策树剪枝的技术来解决这个问题。剪枝是通过防止递归划分那些不是明显相关的属性来实现的，即使当树中该节点的数据并非均匀分类时。问题是我们如何检测不相关属性？

假设我们用一个不相关的属性来划分实例集合。一般来说，我们可以预期作为结果的子集大致与初始集合中各类别的比例相同。既然如此，信息增益则接近于0[4]。因此，信息增益可以作为发现不相关性的好线索。现在的问题是，为了用一个特定的属性进行划分，我们需要多大的增益？

我们可以利用统计的显著性测试（significance test）来回答这个问题。该测试从假设不存在潜在的模式（即所谓的空假设）开始。然后对实际数据进行分析，以计算它们由于完全缺少模式而造成偏离的程度。如果偏离程度从统计意义上说不太可能（通常意味着5％的概率或更低），那么这被认为是在数据中存在显著模式的好证据。这些概率是根据期望在随机采样中能观察到的偏差量的标准分布而计算得到的。

在这种情况下，空假设就是：属性是无关的，而且因此对于一个无限大样本的信息增益是 0。我们需要计算在空假设下，一个大小为v的样本展现出可观察到的、与正例和反例的期望分布相偏离的概率。我们可以通过把每个子集中的正例和反例的实际数目，即 pi和 ni，与所期望的数目pˆi和niˆ 相比较来度量这个偏差，假定确实是不相关的：

总偏离可用下式方便地度量：

在空假设下，D值的分布服从v−1个自由度的χ2（chi-squared——常读作“卡方”——译者注）分布。属性确实是不相关的概率则可以通过标准χ2 表或是统计软件进行计算。习题 18.11 要求你对DECISION-TREE-LEARNING做适当的改动，以实现这种形式的剪枝，即χ2剪枝。

有了剪枝技术，噪声则可以被容忍：分类错误可以导致预测误差的线性增长，而实例描述中的错误有渐近的影响，当树缩减为更小的集合时，误差更大。当数据中包含大量的噪声时，经过剪枝构造的树表现出的性能显著好于没有经过剪枝构造的树。经过剪枝的树经常比较小，并因此更容易理解。

交叉验证是减少过拟合的另外一种技术。它可以用于任何学习算法，而不仅是决策树学习。其基本思想是估计每个假设对未知数据进行预测的准确程度。具体实现是预留部分已知数据，然后利用它们测试从其余已知数据中归纳出的假设的预测性能。k-次交叉验证则是进行 k 次实验，每次预留不同的1 / k的数据用来检测，并对结果进行平均。常用的k值是5或10。极端情况是k=n，即逐一删除（leave-one-out）交叉验证。交叉验证可以与任意的建树方法（包括剪枝）相结合，以选择一棵预测能力好的树。为了避免窥视，我们必须用一个新的测试集来度量它的性能。