决策树

决策树是一类常见的机器学习方法，其是基于“树”的结构进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

以西瓜好坏的机器学习任务构建决策树如下图。

一般地，一棵决策树包括一个根节点、若干个内部节点和若干个叶结点；叶结点对应于决策结果，其余结点对应于一个属性测试。从根结点到每个叶结点的路径对应了一个判定测试序列。

以下是决策树学习基本算法

显然，决策树是一种递归过程。我们可从中得知，具有三种情形导致递归返回：（1）当前节点包含的样本全属于同一类别，无需划分 （2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分 （3）当前结点包含的样本集合为空，不能划分

划分选择

“信息熵”是度量样本集合纯度（决策树的分支结点所包含的样本尽可能属于同一类别）最常用的一种指标。

假定当前样本集合D中第k类样本所占的比例为pk（k=1,2,3.....|y|），则D的信息熵定义为

并且，Ent（D）的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为a^v的样本，记为D^v。然后算出D^v的信息熵，给分支结点赋予权重，即样本数越多的分支结点的影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”。

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，在算法第8行选择属性著名的ID3决策树算法就是以信息增益为准则来选择划分属性的。

增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法使用了“增益率”来选择最优划分属性。增益率定义为

其中

称为属性a的“固有值”；属性a的可能取值数目越多（即V越大），则IV（a）的值通常也越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。