决策树修剪

修剪是机器学习和搜索算法中的一种数据压缩技术，它通过删除决策树中非关键和多余的部分来减少对实例的分类。修剪减少了最终分类器的复杂性，从而通过减少过拟合来提高预测精度。

决策树算法中出现的一个问题是最终树的最佳大小。一棵太大的树有可能过度拟合训练数据，对新样本的概括性也很差。

一棵小树可能无法捕捉到关于样本空间的重要结构信息。然而，很难说树形算法何时应该停止，因为无法判断增加一个额外的节点是否会大 大降低误差。这个问题被称为"水平线效应"。

一个常见的策略是增长树，直到每个节点包含少量的实例，然后使用修剪来删除不提供额外信息的节点。

修剪应该减少学习树的大小，而不减少交叉验证集所衡量的预测准确性。有许多树的修剪技术，它们在用于优化性能的测量方面有所不同。

修剪过程可以分为两种类型（前修剪和后修剪）。预修剪程序通过替换归纳算法中的停止（）准则（如xxx值）来防止训练集的完全归纳。树深或信息增益（Attr）>minGain）。

预修剪方法被认为是更有效的，因为它们不诱导整个集合，而是从一开始就保持小树。预修剪方法有一个共同的问题，即水平线效应。这可以理解为停止（）准则对诱导的不希望的过早终止。

后修剪（或只是修剪）是简化树的最常见的方法。

在这里，节点和子树被替换成叶子，以减少复杂性。修剪不仅可以大 大减少尺寸，还可以提高未见对象的分类精度。

可能会出现这样的情况：训练集上的赋值准确度变差，但树的分类属性的准确度总体上会提高。这些程序是根据它们在树中的方法（自上而下或自下而上）来区分的。

自下而上的修剪这些程序从树上的最后一个节点（最低点）开始。循序渐进地向上，他们确定每个单独节点的相关性。如果没有给出分类的相关性，该节点将被删除或被叶子取代。

这种方法的优点是不会丢失相关的子树。这些方法包括减少错误修剪（REP）、最小成本复杂度修剪（MCCP）或最小错误修剪（MEP）。

与自下而上的方法相比，这种方法从树的根部开始。按照下面的结构，进行相关性检查，决定一个节点是否与所有n个项目的分类有关。

通过在内部节点上修剪树，可能会发生整个子树（无论其相关性如何）被放弃的情况。其中一个代表是悲观的错误修剪（PEP），它对未见过的项目带来相当好的结果。

减少错误修剪最简单的修剪形式之一是减少错误修剪。

从叶子开始，每个节点都被替换成其最受欢迎的类别。

如果预测的准确性不受影响，那么就保留这个变化。虽然有些天真，但减少误差的修剪具有简单和快速的优势。

成本复杂度修剪产生了一系列的树{displaystylei-1}中的一个子树，并将其替换为具有在建树算法中选择的值的叶子节点。并用一个叶子节点代替它，其值与建树算法中选择的一样。

被移除的子树的选择如下。定义树T的错误率{displaystyleT}在数据集上的错误率{displaystyleoperatorname{prune}(T,t)}定义了通过修剪得到的树。