一、决策树

        决策树是最早的机器学习算法之一，起源于对人类某些决策过程的模仿，属于监督学习算法。决策树的优点是易于理解，有些决策树既可以做分类，也可以做回归。在排名前十的数据挖掘算法中有两种是决策树[1]。决策树有许多不同版本，典型版本是最早出现的ID3算法，以及对其改进后形成的C4.5算法，这两种算法可用于分类。对ID3算法改进的另一个分支为“分类和回归树”（Classification AndRegression Trees，CART）算法，可用于分类或回归。CART算法为随机森林和Boosting等重要算法提供了基础。在OpenCV中，决策树实现的是CART算法。

1、决策树的核心问题

        在决策树中，通常将样本向量中的特征称为样本的属性，下文将使用“属性”这一习惯性称呼。决策树通过把样本从根节点排列到某个叶子节点对样本进行分类。根节点是树第一次切分的位置，叶子节点即为样本所属的分类标签。树上的每一个节点都表示了对样本的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。分类样本的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定样本的该属性值对应的树枝向下移动。这一过程在以新节点为根的子树上重复[2]。

        决策树的核心问题是：自顶向下的各个节点应选择何种属性进行切分，才能获得最好的分类器？因此，选择最佳切分属性是决策树的关键所在。

2、最佳切分属性的选择

（1）信息熵

（2）信息增益

（3）信息增益率

（4）基尼系数

（5）均方误差