基本流程

决策树是一种用于解决分类问题的机器学习方法。

一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果，其他每个节点则对应于一个特征测试。每个节点包含的样本集合根据特征值被划分到子节点中，根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。决策树学习的流程如下所示，这是一个递归过程，函数的输入D为样本集合：

def createTree(D):
 if D中所有样本都属于同一类别C:
   return C 
 if 所有特征都已经使用过了: 
   return D中样本数最多的那种类别
 从还未使用的特征中选择最优划分的特征a
 创建在特征a上的分支节点
 for a 的每一个值 :
   令表示D中在特征a上取值为的样本子集
   分支节点在特征a上取值为的分支 = createTree()
 return 分支节点

划分选择

决策树学习的关键是如何选择最优划分的特征，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，即节点的纯度越来越高。

信息熵

信息熵是度量样本集合纯度最常用的一种指标。假定样本集合D中包含n种类别，其中第k类样本所占的比例为，则D的信息熵定义为：

   

Ent(D)的值越小，则D的纯度越高。

信息增益

假定特征a有V个可能的取值，若使用a来对样本集合D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在特征a上取值为的样本，记为。我们可以根据上式计算出的信息熵，再考虑到不同分支节点所包含的样本数不同，给分支节点赋予权重，即样本数越多的分支节点的影响越大，于是可以计算出用特征a对样本集D进行划分所获得的信息增益：

   

一般而言，信息增益越大，则意味着使用特征a进行划分所获得的纯度提升越大。因此，我们可以用信息增益来进行决策树的划分特征选择，即选择使Gain(D,a)最大化的特征a。

著名的ID3决策树学习算法就是以信息增益为准则来选择划分特征的。