机器学习小组-决策树

基本概念

决策树是一种常见的机器学习算法，它是类似流程图的结构，其中每个内部节点表示一个测试功能，即类似做出决策的过程（动作），每个叶节点都表示一个类标签，即在计算所有特征之后做出的决定（结果）。
决策树表示给定特征条件下，类的条件概率分布，这个条件概率分布表示在特征空间的划分上，将特征空间根据各个特征值不断进行划分，就将特征空间分为了多个不相交的单元，在每个单元定义了一个类的概率分布，这样，这条由根节点到达叶节点的路径就成了一个条件概率分布。决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好地拟合，而且对未知数据有很好地预测，既有很好的泛化能力。
决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
决策树通常有三个步骤：
特征选择
决策树的生成
决策树的修剪
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。决策树生成和决策树剪枝是个相对的过程，决策树生成旨在得到对于当前子数据集最好的分类效果(局部最优)，而决策树剪枝则是考虑全局最优，增强泛化能力。

特征选择

信息熵表示随机变量的不确定度。对于一组数据来说，越随机、不确定性越高，信息熵越大；不确定性越低，信息熵越小。


在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择。信息增益就是：以某特征划分数据集前后的熵的差值。

在使用增益信息比时，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
基尼系数（Gini），也被称为基尼不纯度，表示在样本集合中一个随机选中的样本被分错的概率。Gini系数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，基尼指数集合越不纯。即：基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率，有如下公式：

修剪

决策树非常容易产生过拟合，实际所有非参数学习算法，都非常容易产生过拟合。
因此，对于决策树的构建还需要最后一步，即决策树的修剪。两个目的：降低复杂度，解决过拟合。
决策树的修剪，也就是剪枝操作，主要分为两种：
预剪枝（Pre-Pruning）
后剪枝（Post-Pruning）
预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
后剪枝是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树完全替换为叶节点能带来决策树繁花性的提升，则将该子树替换为叶节点。