决策树

决策树（decision tree）又称为判定树，是运用于分类的一种树结构，其中：
>
1.每个内部节点代表对某一属性的一次测试。
2.每条边代表一个测试结果。
3.叶节点代表某个类或类的分布。

决策过程需要从根节点开始，测试集中的数据与决策树中的特征节点进行比较，并按照比较结果选择下一比较分支，直到叶子节点作为最终的决策结果。

实现决策树的核心就是选择属性判断节点，有很多标准，对应的就是不同的算法，最著名的有三个：ID3，C4.5和CART。在介绍之前，先了解一些预备知识。

预备知识

信息是个抽象概念。人们常说信息很多，或者信息较少，但很难说清楚信息到底有多少。1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。

热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。

一条信息的信息量大小和不确定性有直接的关系。如果信息的不确定性越大，熵的值也就越大。设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：

$$Info(D)=-\sum_{i=1}^{m} p_i log_{2}p_i$$

其中，D为所有事件集合，p为发生概率，m为特征总数。

一般用比特（bit）来衡量信息的多少。当然，如果log不是以2为底，则使用的是其他的单位。

即信息获取量（information gain），原有信息熵与属性划分后信息熵的差值，具体计算法如下：

$$gain(A)=Info(D)-Info_A(D)$$

其中，第二项为将训练元组D按属性A进行划分：

$$Info_A(D)=\sum_{j=1}^{v} \frac{|D_j|}{|D|} Info(D_j)$$

ID3算法实际上就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。

ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。

C4.5算法首先定义了“分裂信息”，其定义可以表示成：

$$split\underline{} Info_A(D)=\sum_{j=1}^{v} \frac{|D_j|}{|D|} log_2(\frac{|D_j|}{|D|})$$

增益率被定义为：

$$gain\underline{} ratio(A)=\frac{gain}{split\underline{} Info(A)}$$

C4.5选择具有最大增益率的属性作为分裂属性。

在实际构造决策树时，通常要进行剪枝，主要是为了避免overfitting。剪枝有两种：

1.先剪枝：在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。
2.后剪枝：先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

1.优点：直观、便于理解，小规模数据集有效。
2.缺点：处理连续变量时效果不好；类别较多时，错误增加较多；可规模性一般。

在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用完了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，一般采取“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。

关于决策树的概念先介绍这么多，具体实例和应用，会有后续文章讲解。