数据挖掘

决策树之ID3与C4.5

笔者最近开始学习李航的《统计学习方法》，将以前零散学习的数据挖掘/机器学习算法系统整理一遍，而决策树则可以说是一个入门级的内容了。

李航将机器学习方法等价为：模型+策略+算法，笔者认为这个总结十分受用，便于拆解一些经典的算法逐步理解。这种自上而下将任务拆解的方法则很合适工程类人士学习。

根据李航给出的框架，首先将决策树分解为：

1
2
3
模型：决策树，归根结底就是一个条件概率分布函数。
策略：选择模型的准则，在决策树中则为决策树的损失函数。
算法：求解决策树的算法，在此是生成决策树的算法。

决策树学习的三个步骤：特征选择、决策树生成、决策树剪枝。

模型

在此语境下，模型即是决策树。分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

策略

在生成决策树时是不需要损失函数的，但是不经过剪枝的决策树会有过于复杂以及过拟合的情况，而剪枝在某种程度上解决该问题，于是便在生成决策树后进行一个剪枝的操作，而剪枝所用的损失函数：

其中，表示决策树叶子节点个数，表示叶子节点下有个样本，其中第类样本点个。参数影响惩罚力度，越大则对叶子节点数量越敏感，此时算法倾向于选择叶子节点少的决策树。

算法

生成一颗决策树核心的问题是，如何选取特征作为分裂当前节点的依据？ID3使用信息增益作为特征选择的依据，C4.5则采用信息增益比。

经验熵与条件经验熵（点击展开细节） 在信息论与概率统计中，`熵（Entropy）`是表示随机变量不确定性的度量。设X是一个取有限值的`离散随机变量`，其概率分布为：

则随机变量X的熵定义为：

当时，定义。

设有随机变量，其联合概率分布为：

条件熵表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵（Conditional Entropy），定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

其中，。

当熵和条件熵中的概率由数据估计（尤其是极大似然估计）得到时，所对应的熵与条件熵分别成为经验熵（Empirical Entropy）和经验条件熵（Empirical Conditional Entropy）。

ID3采用的信息增益公式：

其中D为训练数据集，A为特征。

也被称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据中类与特征的互信息。

根据信息增益准则的特征选择方法：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择最大值者为当前节点分裂的依据。

具体的特征增益算法：

  1. 计算数据集D中的经验熵：
  2. 计算特征A对数据集D的经验条件熵：
  3. 计算信息增益：

ID3的信息增益存在一个缺点，易偏向选择取值较多的特征。而C4.5与ID3的不同之处是划分训练数据集的特征的方法不同，C4.5使用信息增益比(information gain ratio)矫正信息增益存在的问题：

其中，n是特征A的取值个数。

按照李航介绍机器学习的方法模型+策略+算法，已经把两个经典的决策树的算法在较为高层的角度讲述了，然而到落实为代码仍需要更为详细的伪代码来讲述。

ID3的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
输入： 训练数据集D，特征集A，阈值e
输出： 决策树T
    if D中所有实例属于同一类C[k] then
        return new TreeNode(class = C[k])
    if A为空集 then
        找出D中实例数最多的类C
        return new TreeNode(class = C)
    classes = D中各类的统计数
    entropy_d = Entropy(classes)
    for k in 1..A.length
        cnt = 0
        stats_ak = 统计A[k]的取值情况
        entropy_ak[k] = 0
        for val in A[k]
            for c in 1..classes.length
                stats_ak[k][val][c] = 统计取值A[k]=vak,时D[c]的取值情况
        entropy_ak[k] = Entropy(stats_ak[k], entropy_d)
    gain_ak = gain(entropy_d, entropy_ak)
    从gain_ak获得最大取值时的k
    if gain_ak[k] < e then
        找出D中实例数最多的类C
        return new TreeNode(class = C)
    for val in A[k]
        通过val作为识别，将A[k]=val时的实例归到新数据集D_sub[val]
        A_new[val] = A[k]=val并且去掉A[k]特征后的特征集
        T_sub[i] = 递归生成子节点algo(D_sub[val], A_new[val], e)
    return new TreeNode(child = T_sub)

C4.5则是更对计算entropy_ak时的公式小更改，笔者认为给出的伪代码已经很细节了。很久之前用Ruby写过ID3的第一版，虽然之前打算重写，但是发现要学习的东西太多，所以重写计算暂时延后，先把没有学到的经典算法实现了再回头做这里。