[DataAnalysis]数据挖掘导论——决策树详解

Hunt算法

Hunt是许多决策树算法的基础，包括ID3、C4.5和CART。

Hunt：递归地使用属性测试条件直至中所有记录属于同一类。

（1）如果中所有记录都属于同一类，则是叶结点，用标记。

（2）如果中包含属于多个类的记录，则选择一个属性测试条件，将记录划分为较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。 

表示属性测试条件的办法

二元属性、标称属性、序数属性和连续属性

选择最佳划分的度量

一般是根据划分后子女结点不纯性的程度。

不纯性的度量：

补充：

（1）增益率：

为解决熵和Gini指标等不纯性度量趋于有利于具有大量不同值的属性，CART使用二元划分属性，C4.5使用增益率。

模型的过分拟合

分类模型的误差大致分为两种：训练误差和泛化误差。

拟合不足：训练误差与检验误差都很大

过分拟合：训练误差下降但是检验误差上升

过拟合的原因：

（1）噪声导致的过拟合：样本被错误标记。

（2）缺乏代表性样本导致的过分拟合：根据少量训练记录做出分类决策的模型也容易受过分拟合的影响。

结合模型复杂度

奥卡姆剃刀（节俭原则）：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。

悲观误差评估：使用训练误差和模型复杂度罚项的和计算泛化误差

设是结点分类的训练记录数，是被误分类的记录数。决策树的悲观误差估计可用下式计算：

其中：是决策树的叶结点数，决策树的总训练误差，是训练记录数，是每个结点对应的罚项。

最小描述长度原则：

另一种结合模型复杂度的方法是基于称作最小描述长度（mininum description length，MDL）原则的信息论方法。

使用确认集：不再使用训练集估计泛化误差，而是把原始的训练数据集分为两个较小的子集，一个子集用于训练，另一个子集用于估计泛化误差。

处理决策树归纳中的过分拟合

介绍在决策树归纳上避免过分拟合的策略

先剪枝（提前终于规则）：

在这种方法中，树增长算法在产生完全拟合整个训练数据集的完全增长的决策树之前就停止决策树的生长。具体实现方式可以当观察到的不纯性度量的增益低于某个确定的阈值时就停止扩展叶结点。这种方法的优点在于避免产生过分拟合训练数据的过于复杂的子树。但是阈值的选取是一个比较复杂的问题。

后剪枝：

初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自底向上的方式修剪完全增长然后修剪。

修剪有两种做法：

（1）用新的叶子节点替换子树，该叶结点的类标号由子树下记录中的多数类决定。子树替换

（2）用子树中最常使用的分支代替子树。当模型不能再改进时终止剪枝步骤。子树提升

评估分类器的性能

1、训练集和测试集方法

2、交叉验证

每个记录用于训练的次数相同，并且恰好检验一次。

3、自助法bootstrap

训练记录采用有放回抽样