决策树学习：过度拟合、噪声与属性选择

"这篇资料主要讨论了决策树学习过程中遇到的过度拟合和噪声问题，以及如何处理这些问题。文中提到了决策树的构建原理、如何处理连续和离散属性、应对噪声数据的方法，并介绍了基本的决策树算法和选择根属性的策略。" 在机器学习领域，决策树是一种广泛使用的分类和回归模型。它通过一系列特征测试来做出预测，构建出类似流程图的结构，即树状结构。每个内部节点代表一个特征测试，每个分支代表一个测试结果，而叶节点则给出最终的预测类别或数值。 过度拟合是指模型在训练数据上表现良好，但在未见过的新数据上表现差的情况。在决策树学习中，过度拟合可能由分类或属性噪声引起。当训练数据中存在噪声，例如错误标记的实例或者属性值的不确定性，决策树可能会过于复杂，试图捕捉这些噪声，而不是真正的模式。例如，一个本来应该是正类的实例被错误地标记为负类（<<medium, green, circle>, +> 实际上是 -）。这种情况下，决策树可能会在决策路径上为这个噪声实例创建额外的分支，导致树过于复杂。 为了处理噪声，决策树算法需要具备一定的鲁棒性。一种策略是在叶节点分配主要的分类，即使该叶节点包含多种分类的样本。例如，如果一个叶节点既有红色圆形的正类样本，也有红色圆形的负类样本（<<big, red, circle>, -> 实际上为 +），那么该叶节点可能会被标记为正类，因为这是主要的分类。 此外，属性不完备可能导致样本冲突。当某个属性值缺失或者不足以判断分类时，决策树可能无法正确地将实例分到某个特定的类别，从而产生冲突。处理这种情况的一种方法是使用缺省值或者根据其他已知属性来推断缺失值。 决策树学习的基本算法通常采用自顶向下的递归方式。算法首先检查所有样本是否属于同一类别，若是，则创建一个对应该类别的叶节点。如果属性为空，就返回最常见的分类作为叶节点。否则，算法会选择一个最优属性作为当前节点的测试，然后对每个属性值创建子节点，并递归地构建子树。 选取根属性时，算法的目标是找到能最大程度地减少数据集混乱度的属性。常用的一种度量是信息增益（Information Gain），它基于熵的概念。熵是衡量样本集合纯度的一个指标，越纯的集合熵越低。对于二分类问题，熵计算基于正负样本的比例；对于多分类问题，熵则考虑所有类别的比例。选择信息增益最大的属性作为分割点，有助于创建更“纯净”的子集，从而降低整体的熵。 决策树学习需要平衡模型的复杂性和泛化能力，避免过度拟合，同时处理噪声和属性缺失的问题，通过有效的属性选择策略来优化决策树的结构。