决策树(decision tree)是一种多功能的机器学习算法，它可以实现分类和回归任务，同时也是随机森林的重要组成部分，本篇博客主要讨论用于分类的决策树。

分类型决策树是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内结点表示一个特征，叶子结点表示一个类别。

原理

决策树在建模过程中使用信息增益准则选择特征，给定训练集$D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性。而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性，它们的差即信息增益，表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。显然，对于数据集$D$而言，信息增益依赖于特征，不同的特征具有不同的信息增益，信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集$D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益大的特征。

ID3算法

设训练数据集为$D$，$|D|$表示其样本容量，即样本个数。设有$K$个类$C_k，k=1,2,…,K$，$|C_k|$为属于$C_k$的样本个数，$\sum_{k=1}^{K}|C_k|=|D|$。设特征$A$有$n$个不同的取值${a_1,a_2,…,a_n}$，根据特征$A$的取值将$D$划分为n个子集$D_1,D_2,…,D_n$，$|D_i|$为$D_i$的样本个数，$\sum_{k=1}^{n}|D_i|=|D|$。记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$，记$D_{ik}=D_i \cap C_k$，$|D_{ik}|$为$D_{ik}$的样本个数。

ID3算法如下

输入：训练数据集$D$，特征集$A$，阈值$\epsilon$
输出：决策树$T$

若$D$中所有实例属于同一类别$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；
若$A=\emptyset$，则$T$为单点树，将$D$中实例数最多的类$C_k$作为该结点的类标记，返回$T$；
否则，如下计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$
1. 计算数据集$D$的经验熵
  $$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$
2. 计算特征集$A$对数据集$D$的经验条件熵
  $$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=\sum_{i=1}^{n}[\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log_2\frac{|D_{ik}|}{|D_{i}|}]$$
3. 计算信息增益
  $$g(D,A)=H(D) - H(D|A)$$
如果$A_g$小于阈值$\epsilon$，则置$T$为单点树，将$D$中实例数最多的类$C_k$作为该结点的类标记，返回$T$；
否则，对$A_g$的每一个值$a_i$，按照$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例最大的类作为标记，构建子结点，由结点和子结点构成树$T$，返回$T$
对第$i$个子结点，以$D_i$为训练集，以$A_i-{A_g}$为特征集，递归地调用步骤1-5，得到子树$T_i$，返回$T_i$

C4.5算法

C4.5算法和ID3算法类似，C4.5算法对ID3算法进行了改进，在生成模型的过程中采用信息增益比来选择特征。

示例

以贷款申请数据为例讲解决策树的生成过程，采用ID3算法。

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

计算经验熵$H(D)$
$$H(D)=-\frac{6}{15}log_2\frac{6}{15}-\frac{9}{15}log_2\frac{9}{15}=0.971$$
计算各特征对数据集$D$的信息增益
- 年龄
  $$
  \begin{split}
  g(D,A_1)&=H(D) - [\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)+\frac{5}{15}H(D_3)]\\
  &= 0.971 - {\frac{5}{15}[-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}]+
  \frac{5}{15}[-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}]+
  \frac{5}{15}[-\frac{4}{5}log_2\frac{4}{5}-\frac{1}{5}log_2\frac{1}{5}]}\\
  &=0.971-0.888\\
  &=0.083
  \end{split}
  $$
- 有工作
  $$
  \begin{split}
  g(D,A_2)&=H(D) - [\frac{5}{15}H(D_1)+\frac{10}{15}H(D_2)]\\
  &= 0.971 - {\frac{5}{15} \times 0+
  \frac{10}{15}[-\frac{6}{10}log_2\frac{6}{10}-\frac{4}{10}log_2\frac{4}{10}]}\\
  &=0.971-0.647\\
  &=0.324
  \end{split}
  $$
- 有自己的房子
  $$
  \begin{split}
  g(D,A_3)&=H(D) - [\frac{6}{15}H(D_1)+\frac{9}{15}H(D_2)]\\
  &= 0.971 - {\frac{6}{15} \times 0+
  \frac{9}{15}[-\frac{3}{9}log_2\frac{3}{9}-\frac{6}{9}log_2\frac{6}{9}]}\\
  &=0.971-0.551\\
  &=0.420
  \end{split}
  $$
- 信贷情况
  $$
  \begin{split}
  g(D,A_3)&=H(D) - [\frac{5}{15}H(D_1)+\frac{6}{15}H(D_2)+\frac{4}{15}H(D_2)]\\
  &= 0.971 - {\frac{5}{15}[-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2\frac{4}{5}] +
  \frac{6}{15}[-\frac{4}{6}log_2\frac{4}{6}-\frac{2}{6}log_2\frac{2}{6}] +
  \frac{4}{15} \times 0 }\\
  &=0.971-0.608\\
  &=0.363
  \end{split}
  $$
  综上，特征$A_3$（有自己的房子）的信息增益值最大，所以选择$A_3$作为根节点的特征。接下来将数据集$D$划分为两个子集$D_1$($A_3$=是)、$D_2$($A_3$=否)，分别进行下一轮的信息增益筛选。

进入子集$D_1$($A_3$=是)，由于该子集中只有一个类别，所以形成叶子结点，结点的标记就是类别。
进入子集$D_2$($A_3$=否)，数据如下
- 计算经验熵
  $$H(D_2)=-\frac{6}{9}log_2\frac{6}{9}-\frac{3}{9}log_2\frac{3}{9}=0.918$$
- 年龄特征信息增益
  $$
  \begin{split}
  g(D_2,A_1)&=H(D) - [\frac{4}{9}H(D_1)+\frac{2}{9}H(D_2)+\frac{3}{9}H(D_3)]\\
  &= 0.971 - {\frac{4}{9}[-\frac{3}{4}log_2\frac{3}{4}-\frac{1}{4}log_2\frac{1}{4}]+
  \frac{2}{9}\times0+
  \frac{3}{9}[-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}]}\\
  &=0.971-0.667\\
  &=0.251
  \end{split}
  $$
- 有工作特征信息增益
$$
\begin{split}
g(D_2,A_2)&=H(D) - [\frac{6}{9}H(D_1)+\frac{3}{9}H(D_2)]\\
&= 0.971 - [\frac{6}{9}\times0+\frac{3}{9} \times 0]\\
&= 0.918-0\\
&=0.918
\end{split}
$$
- 信贷情况特征信息增益
  
  $$
  \begin{split}
  g(D_2,A_4)&=H(D) - [\frac{4}{9}H(D_1)+\frac{4}{9}H(D_2)+\frac{1}{9}H(D_3)]\\
  &= 0.971 - {\frac{4}{9}\times0+
  \frac{4}{9}[-\frac{2}{4}log_2\frac{2}{4}-\frac{2}{4}log_2\frac{2}{4}]+
  \frac{1}{9}\times0}\\
  &=0.918-0.444\\
  &=0.474
  \end{split}
  $$
  综上，特征$A_2$（有工作）的信息增益值最大，所以选择$A_2$作为该结点的特征。接下来将数据集$D_2$划分为两个子集$D_{21}$($A_2$=是)、$D_{22}$($A_2$=否)，分别进行下一轮的信息增益筛选。
进入子集$D_{21}$($A_2$=是)，由于该子集中只有一个类别，所以形成叶子结点，结点的标记就是类别
进入子集$D_{22}$($A_2$=否)，由于该子集中只有一个类别，所以形成叶子结点，结点的标记就是类别

最终产生的决策树模型如下图所示

代码


# coding=utf-8
from math import log
import pygraphviz as pgv


def calcShannonEnt(dataSet):
    # 数据集总条数
    numEntries = len(dataSet)
    labelCount = {}
    # 计算每个类别样本的数量
    for featVec in dataSet:
        currentLabel = featVec[-1]
        labelCount[currentLabel] = labelCount.get(currentLabel, 0) + 1
    shannonEnt = 0.0
    for key in labelCount:
        # 计算每个类别出现的概率
        prob = float(labelCount[key]) / numEntries
        # 计算信息熵
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt


def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        # 挑选第axis个特征的值为value的数据
        if featVec[axis] == value:
            reducedFeature = featVec[:axis]
            reducedFeature.append(featVec[axis + 1:])
            # 注意，此处是extend，不是append
            retDataSet.extend(reducedFeature)
    return retDataSet


def chooseBestFeatureToSplit(dataSet):
    # 特征数量，由于最后一个是标签，所以减1
    numFeatures = len(dataSet[0]) - 1
    # 计算经验熵
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        # 把第i个特征全部挑出
        featList = [example[i] for example in dataSet]
        # 第i个特征有几个不同的特征值
        uniqueVals = set(featList)
        # 条件经验熵
        newEntropy = 0.0
        for value in uniqueVals:
            # 把特征值等于value的数据挑出
            subDataSet = splitDataSet(dataSet, i, value)
            # 计算特征值等于value的数据占总样本的比例
            prob = len(subDataSet) / float(len(dataSet))
            # 计算经验条件熵
            newEntropy += prob * calcShannonEnt(subDataSet)
        # 计算信息增益
        infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature


def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        classCount[vote] = classCount.get(vote, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=lambda item: item[1], reverse=True)
    return sortedClassCount[0][0]


def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel: {}}
    del (labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree


def createDataSet():
    dataSet = [['1', '1', 'yes'],
               ['1', '1', 'yes'],
               ['1', '0', 'no'],
               ['0', '1', 'no'],
               ['0', '1', 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels


def main():
    dataSet, labels = createDataSet()
    tree = createTree(dataSet, labels)
    print tree


if __name__ == '__main__':
    main()

参考

机器学习实战，人民邮电出版社
统计学习方法，清华大学出版社

相关数学概念

信息熵

条件熵

信息增益

信息增益比

原理

ID3算法

C4.5算法

示例

代码

参考