定义
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。
使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
算法步骤
在数据挖掘中决策树训练是一个常用的方法。目标是创建一个模型来预测样本的目标值。
一棵树的训练过程为：根据一个指标，分裂训练集为几个子集。这个过程不断的在产生的子集里重复递归进行，即递归分割。当一个训练子集的类标都相同时递归停止。这种决策树的自顶向下归纳 (TDITD) 是 贪心算法的一种, 也是目前为止最为常用的一种训练方法，但不是唯一的方法。
常用算法
ID3
ID3算法是最基本的模型，简单实用，但是在某些场合下也有缺陷。
这个算法的思想是：在每次分裂的时候，贪心选择信息增益最大的属性，作为本次分裂属性。
那么什么是增益最大呢？
首先它定义了一个公式来表示熵增益，然后算出每个属性所对应的熵增益，挑出最大的那个，然后用对应的属性作为分裂属性，接着，对各个子集，进行类似操纵。
存在的问题
ID3在选择的时候容易选择一些比较容易分纯净的属性做分裂，尤其在具有像ID值这样的属性，因为每个ID都对应一个类别，所以分的很纯净。但是这对于结果是毫无意义的。
C4.5
C4.5 在 ID3 的基础上，抛弃了比较熵增益，转而比较增益率。
增益率引入了一个分裂熵，来表示属性分裂的熵，分的越多就越混乱，熵越大。
最后得出增益率 = 熵增益 / 分裂熵。
这样子就抑制了ID3算法的缺陷。
注意点
停止条件
决策树的构建过程是一个递归的过程，所以需要确定停止条件，否则过程将不会结束。一种最直观的方式是当每个子节点只有一种类型的记录时停止，但是这样往往会使得树的节点过多，导致过拟合问题（Overfitting）。另一种可行的方法是当前节点中的记录数低于一个最小的阀值，那么就停止分割，将max(P(i))对应的分类作为当前叶节点的分类。
过度拟合
- 噪音数据：训练数据中存在噪音数据，决策树的某些节点有噪音数据作为分割标准，导致决策树无法代表真实数据。
- 缺少代表性数据：训练数据没有包含所有具有代表性的数据，导致某一类数据无法很好的匹配。
- 多重比较
属性用完了怎么办
在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用光了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。
优化方案
修剪枝叶
前置裁剪：在构建决策树的过程时，提前停止。那么，会将切分节点的条件设置的很苛刻，导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。
后置裁剪：决策树构建好后，然后才开始裁剪。采用两种方法：1）用单一叶节点代替整个子树，叶节点的分类采用子树中最主要的分类；2）将一棵子树完全替代另外一棵子树。后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪了，导致有点浪费。
K-Fold Cross Validation
首先计算出整体的决策树T，叶节点个数记作N，设i属于[1,N]。对每个i，使用K-Fold Validataion方法计算决策树，并裁剪到i个节点，计算错误率，最后求出平均错误率。（意思是说对每一个可能的i，都做K次，然后取K次的平均错误率。）这样可以用具有最小错误率对应的i作为最终决策树的大小，对原始决策树进行裁剪，得到最优决策树。
Random Forest
Random Forest是用训练数据随机的计算出许多决策树，形成了一个森林。然后用这个森林对未知数据进行预测，选取投票最多的分类。
优缺点
优点
-
易于理解和解释，人们很容易理解决策树的意义。
-
只需很少的数据准备，其他技术往往需要数据归一化。
- 即可以处理数值型数据也可以处理类别型数据。其他技术往往只能处理一种数据类型。例如关联规则只能处理类别型的而神经网络只能处理数值型的数据。
-
使用白箱模型.。输出结果容易通过模型的结构来解释。而神经网络是黑箱模型，很难解释输出的结果。
-
可以通过测试集来验证模型的性能 。可以考虑模型的稳定性。
-
强健控制. 对噪声处理有好的强健性。
- 可以很好的处理大规模数据 。
缺点
- 只能采用启发式搜索算法（例如 贪心算法）来达到局部最优，但却没办法得到全局最优。
- 决策树创建的过度复杂会导致无法很好的预测训练集之外的数据。这称作过拟合。剪枝机制可以避免这种问题。
- 有些问题决策树没办法很好的解决,例如 异或问题。