决策树的理解与应用
决策树🌲是一种基本的分类和回归的方法【以前总是下意识以为决策树只能用于分类，事实上还可以用于回归】。在分类问题中，决策树基于特征对实例进行分类，这个分类过程可以认为是if-then的规则集合，也可以认为是特征空间与类空间上的条件概率分布。
NOTE:
if—then规则集合具有一个重要的特征：互斥且完备，即每个实例都被一条路径或者一条规则所覆盖，而且只能被一条路径或一条规则所覆盖
优点 ：简单易理解、分类速度快
过程 ：利用损失函数最小化原则对训练集进行建模，再利用建立好的模型进行分类。决策树的学习算法通常是递归地选择最优特征，并根据特征对训练集进行分割，最终形成从【根结点->叶子结点】的树模型， 但是这样生成的树可以容易发生过拟合，所以需要自底向上修剪✋
决策树学习包括三个步骤：特征选择、决策树生成、决策树修剪
1.当特征数量较多时，在学习之前先进行特征选择
2.决策树生成对应局部最优
3.决策树修剪对应全局最优
目标 ：选择一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
通常，特征选择的准则是 信息增益或者信息增益比
先介绍基本概念：
决策树的生成过程仅考虑到对训练数据集分类的准确性，这样生成的树模型容易出现过拟合且构建的树过于复杂，所以有必要对其进行剪枝。
剪枝 ：从已生成的树上裁掉一些子树或者叶结点，并将其根结点或者父结点作为新的叶结点，从而简化分类树模型。 剪枝往往是通过极小化决策树的整体损失函数来实现的
定义损失函数 ：
设树 的叶结点个数为 , 是树的叶结点，该叶结点有 个样本点，其中 类的样本点有 ，其中 是叶子结点 的经验熵， 为参数，决策树学习的损失函数为：
其中
所以最终的损失函数表示为：
公式解释： 是表示模型对训练集的预测误差，即模型与训练集的拟合程度， 表示模型的复杂度，叶子节点数越大模型越复杂， 是调节参数，控制模型的拟合和复杂程度。
当 确定时，选择损失函数最小的模型，这里定义的损失函数其实等价于正则化的极大似然估计。
算法：
INPUT: 生成算法产生的整个树 ，参数
OUPUT: 修剪后的子树
1.计算每个结点的经验熵
2.递归地从树的叶结点向上回缩
回缩前后整体树的损失函数比较，如果回缩前的损失函数大于回缩后，进行剪枝。
3.重复2，直到不能继续为止，得到损失函数最小的子树
后期加入
总结：决策树是一种简单快速的分类算法，本文不仅把熵相关的概念给整理了一遍，文中信息增益和信息增益比也可以用于其他模型的特征选择，而最后剪枝部分提到的决策树的损失函数是我之前在专门写的《详述机器学习中的损失函数》博客中没有提到的，这里也是一个补充。
