算法之决策树分类

决策树（Decision Tree）是一种被广泛使用的分类算法，在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。

在实际应用中，对于探测式的知识发现，决策树更加适用。

一、算法定义

决策树是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

一个决策树包含三种类型的节点：

1. 决策节点：通常用矩形框来表示
2. 机会节点：通常用圆圈来表示
3. 终结点：通常用三角形来表示

(x, y) = (x1, x2, x3…, xk, y)

相关的变量 Y 表示我们尝试去理解，分类或者更一般化的结果。 其他的变量x1, x2, x3 等则是帮助我们达到目的的变量。

二、算法思想

决策树算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。

构造决策树的依据（特征选择）：

信息熵增益，如果经过某个选定的属性进行数据划分后的信息熵下降最多，则这个划分属性是最优选择。

信息增益，集合信息的度量方式称为香农熵，或者简称熵。

熵定义为信息的期望值

如果待分类的事物可能划分在多个类之中，则符号x_i的信息定义为： 

l(x_i)=−log2p(x_i)l(x_i)=−log2p(x_i)

其中，p(x_i)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，通过下式得到： 

H(D)=−Σⁿp(x_i)log2p(x_i)

其中，n为分类数目，熵越大，随机变量的不确定性就越大。

 当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。

在理解信息增益之前，要明确——条件熵

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望： 

H(Y|X)=∑ⁿp_iH(Y|X=x_i)

其中，p_i=P(X=x_i)

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0

信息增益：信息增益是相对于特征而言的。

所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g(D,A)=H(D)−H(D|A)

一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小。

使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

信息增益比：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比：

gR(D,A)=g(D,A)/H(D)

三、算法实现

从数据集构造决策树算法的工作原理如下：

得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

决策树生成算法递归地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

构建决策树的算法有很多，比如C4.5、ID3和CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。由于特征数目并不是每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题。目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。