决策树

决策树是一个二叉树。当每个叶节点用类别标识（多个叶子可能有相同的标识）时，它可以表示分类树；当每个叶节点被分配了一个常量（所以回归函数是分段常量）时，决策树就成了回归树。决策树是从根结点递归构造的。用所有的训练数据（特征向量和对应的响应）来在根结点处进行分裂。在每个结点处，优化准则（比如最优分裂）是基于一些基本原则来确定的（比如ML中的“纯度purity”原则被用来进行分类，方差之和用来进行回归）。所有的数据根据初始和替代分裂点来划分给左右子结点（就像在预测算法里做的一样）。然后算法回归的继续分裂左右子结点。

在以下情况下算法可能会在某个结点停止：

a) 树的深度达到了指定的最大值

b) 在该结点训练样本的数目少于指定值，比如，没有统计意义上的集合来进一步进行结点分裂了。

c) 在该结点所有的样本属于同一类（或者，如果是回归的话，变化已经非常小了）

d) 跟随机选择相比，能选择到的最好的分裂已经基本没有什么有意义的改进了。

决策树的优点：

a) 计算简单，易于理解；

b) 适应不同的数据类型（包括类别数据，数值数据，未归一化的和混合的数据）；

c) 比较适合处理有缺失属性的样本；

d) 通过分裂的顺序给数据特征赋不同的重要性；

e) 能够处理不相关的特征；

f) 在相对短的时间内能够对大型数据源做出可行且结果良好的结果；

g) 决策树构成了其他算法的基础（如boosting和随机数）。

决策树的缺点：

a) 容易发生过拟合（随即森林可以很大程度上减少过拟合）；

b) 忽略了数据之间的相关性；

c) 对于那些，各类别样本数量不一致的数据，在决策树中，信息增益的结果偏向于那些具有更多数值的特征（只要使用了信息增益，都有这个特点，如RF）