Decision Tree（决策树）

决策树是一种简单但广泛使用的分类器，它通过训练数据构建决策树，对未知的数据进行分类。决策树的每个内部节点表示在一个属性上的测试，每个分枝代表该测试的一个输出，而每个树叶结点存放着一个类标号。
在决策树算法中。

ID3基于信息增益作为属性选择的度量，
C4.5基于信息增益比作为属性选择的度量，
CART基于基尼指数作为属性选择的度量。

决策树的优缺点

优点
1、不需要任何领域知识或参数假设
2、适合高维数据。
3、简单易于理解。
4、短时间内处理大量数据，得到可行且效果较好的结果。
5、使用可视化模型。
缺点
1、对于各类别样本数量不一致数据，信息增益偏向于那些具有更多数值的特征。
2、易于过拟合。
3、忽略属性之间的相关性。
4、不支持在线学习
5、它们是不稳定的，这意味着数据的微小变化可能导致最优决策树结构的巨大变化。
6、计算可能变得非常复杂，特别是如果许多值不确定和/或许多结果是相关的。

决策树公式

树模型

决策树：从根节点开始一步步走到叶子节点（决策）。
所有的数据最终都会落到叶子节点，即可以应用于分类也可以做回归。

树的组成

根节点：第一个选择点
非叶子节点于分支：中间过程
叶子节点：最终的决策结果

决策树的训练与测试

训练阶段从给定的训练集构造出一颗树，从根节点开始选择最有价值的特征开始切分节点。
测试阶段：根据构造出来的树模型从上到下走一遍。
一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点在于如何构造出一个树。

特征切分

存在的问题：根节点的选择该用那个特征呢？接下来我们要如何划分？
思考：我们的目标应该使根节点就像老大，根节点下面的节点就像老二，老大应该比老二能更好的切分数据。
目标：选择一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的就作为我们的根节点，以此类推确定所有的节点的划分标准。

衡量标准——熵

熵：表示随机变量不确定性的度量（就是一个整体中内部元素的混乱程度，元素种类越多混乱程度越高）
公式：

公式中pi表示第i种情况的概率

熵值熵值与不确定性一般成正比
下图为熵值与概率的关系图：

决策树算法

ID3：信息增益（存在的问题：每个数据都有一个ID特征（1，2，3，…，14），根据该特征分类之后的熵值恒为 0 ，但是实际上根据这个特征分类毫无意义）
C4.5：信息增益率（是ID3的升级，考虑自身熵值）
CART：使用GINI系数来作为衡量标准
GINI系数（基尼系数）：

减枝策略

离散化，
把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200}，{20,50000}，{1,400};
处理后:{3,4}，{2,6}，{1,5};

针对连续值我们可以采用“离散化”的方式减少决策树计算量过大，叶子节点过多的问题。例如一组特征值为60，70，80，90，95，100，120，125，220。直接采用二分将会出现9个节点。如果我们人为分成A（60-80）、B（90-100）、C（120-220），我们只需要分成3类即可。当然要根据特征含义和特定分析条件下选择是否分割数据。
决策树剪枝：为了防止过拟合情况。（决策树过拟合分析很大，理论上可以完全分开数据，使得每个叶子节点只存在一个数据）
剪枝策略：
1、预剪枝（实用）：边建立决策树边进行剪枝操作。方法：限制树的深度，叶子节点的个数，叶子节点包含的样本树，信息增益量等。
2、后剪枝：当建立完决策树后来进行剪枝操作。