决策树

      分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点和有向边组成，节点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点，这时，每一个子节点对应该特征的一个取值，如此递归的对实例进行测试并分配，直至达到叶节点，最后将实例分到叶节点的类中。下图是一个决策树模型，图中圆和方框分别表示内部节点和叶节点。

      决策树学习的算法通常是一个递归的选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这一过程对应对特征空间的划分，也对应决策树的构建，首先，构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么，构建叶节点，并将这些子集分到所对应的叶节点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如此递归的进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止，最后每个子集被被分到叶节点上，即都有了明确的类，这就生成了一棵决策树。

      决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择，决策树的生成只考虑局部最优，相对的，决策树的剪枝则考虑全局最优。

      特征选择在于选取对训练数据具有分类能力的特征，这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的，经验上扔掉这样的特征对决策树学习的精度影响不大，通常特征选择的准则是信息增益或信息增益比。

      根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正，这是特征选择的另一准则。

      ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归的构建决策树。具体方法是：从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点，再对子结点递归的调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一棵决策树。C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进，C4.5算法在生成的过程中，用信息增益比来选择特征。

      决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象，过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

      CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。CART算法由以下两步组成：1决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。2决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。