统计学习方法笔记（五）：决策树

定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成。节点有内部节点（内部节点表示一个特征或属性，叶节点表示一个类）和叶节点组成

学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型

决策树的路径或者说其对应的if-then规则集合具有一个重要的性质：互斥并且完备（每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。）

决策树的学习

决策树学习的本质是从训练数据集中归纳出一组分类规则其损失函数通常是正则化的极大似然函数，学习问题变成了在损失函数意义下选择最优决策树的问题，这是NP完全问题，所以现实中学习算法通常采用启发式方法，近似求解这一最优问题决策树学习的3个步骤：特征选择、决策树的生成、决策树的修剪

特征选择

特征选择问题 特征选择是决定用哪个特征来划分特征空间

选择的特征要能够一下子就能够将集合划分开（如一下子分成了9：1），目的是尽量避免选择一些让集合划分为55开的特征，也即是选择信息增益最大的特征，即选择不确定性减少最多的特征。

计算信息增益算法

决策树的生成

ID3算法：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归的调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。相当于用极大似然法进行概率模型的选择。（由于只有树的生成，该算法生成的树容易过拟合）

C4.5算法：和ID3算法相似，只改成了用信息增益比来选择特征

决策树的剪枝

过拟合的原因在于学习时过多地考虑了如何提高训练数据的正确分类，从而构建出过于复杂的决策树。

回归树

决策树思想不仅能够应用于分类问题，还能够应用于回归拟合问题

总结