决策树
序
本次记录一下决策树的相关概念以及思想，后面博客再贴上具体的算法原理
一句话介绍
决策树是一种基本的分类与回归的判别式模式，在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if then的规则集合，也可以认为是定义在特征空间与类空间上的条件概率分布。决策树的生长过程均可看作是一个贪心的过程。
分类
下图是常见决策树模型的相关分类以及其分支的内容。
算法思想
决策树是一个树形结构（二叉或非二叉）
其每一个非叶子节点表示一个特征属性上的样本划分，每个分支代表这个特征属性在某个值域上的输出，而每个叶子节点存放一个类别。
使用决策树进行决策的过程就是从根节点出发，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
总的来说，可以概括为以下几点：
决策树模型核心：
1）具有节点和有向边
2）节点分为内部节点和叶子节点两种
3）内部节点表示一个特征的一种取值，叶节点表示一个类
决策树学习流程：（递归建树的过程）
1）特征选择
2）决策树生成
3）决策树修剪
决策树与条件概率分布
决策树通过对样本的划分，将特征空间划分为不想交的单元，并且在每个单元根据多数类而定义一个类的概率分布就构成了一个条件概率分布。决策树中的一条路径决定了特征空间中的一个划分区域，该区域的条件概率分布可表示为P(Y/X)。
换句话说，决策树就是通过训练数据集来估计条件概率模型，基于特征空间划分的类的条件概率有无穷多个，我们选择的条件概率模型应该是对训练集和测试集都能拟合较好的那一个。
决策树学习过程
- 本质
决策树的学习本质上是从训练集中归纳出一组分类规则而已，这些得到的规则对应的是由训练数据所估计的条件概率模型，我们最终通过极小化损失函数得到在训练集和测试集上拟合较好的条件概率模型。 - 决策树学习包含：
特征选择、决策树递归生成、决策树剪枝 - 决策树生成
开始，构建根节点，将所有训练集数据都放在根节点，选择一个最优的特征，按照这一特征将训练集分割成子集，使得各个子集有一个在当前条件下最好的分类，如果这些子集已经能够被基本正确分类，那么就构建叶子节点并将这些子集分到所对应的叶节点中去，如果还有子集不能被正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如此递归下去，直至所有训练数据子集被基本正确分类。 - 剪枝
生成决策树考虑的是局部最优，剪枝的过程考虑的全局最优。
特征选择
特征选择是决定用哪个特征来划分特征空间，特征选择的目的是选取对训练数据具有分类能力的特征，这样可以提高决策树的学习效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称该特征没有分类能力，经验熵丢掉这样的特征对决策树的分类精度不会有什么影响。
案例解释
摘自西瓜书中一图：
- 为何第一次不选择其他特征作为第一个节点呢？
决策树的关键步骤在于属性分裂，而对属性进行分裂的意思是在某节点处，按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能纯，纯是指让一个分裂子集中待分类项属于同一类别。 - 特征选择的依据？
根据上面的介绍，引入了ID3和C4.5方法来进行特征选择，这俩算法也是进行纯度度量的依据
