0

决策树——ID3和C4.5

前言

本文介绍的是决策树算法,涉及的算法内容是ID3和C4.5,CART算法在决策树(2)中会介绍,本文的知识点是李航博士《统计学习》第5章和周志华老师的《机器学习》的知识总结,文末会给出ID3算法的Python版本的代码,改代码修改自Peter Harrington的《机器学习实战》,仅供学习参考。文章的内容编排如下:

  1. 决策树简介
  2. 决策树的特征选择
  3. 决策树生成
    1. ID3算法
    2. C4.5算法
  4. 决策树剪枝
  5. ID3算法的Python代码
  6. 总结

决策树简介

决策树(Decision Tree)是一种基本的分类与回归算法,而本文要讨论的ID3和C4.5算法是分类算法,在决策树(2)中讨论的CART算法是一种分类和回归都适用的算法。决策树模型是一种树形模型,在分类问题中,表示基于特征对实例进行分类的过程,可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树的主要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测时,对新数据,利用决策树模型进行分类。决策树学习算法通常包括以下步骤:

  1. 特征选择
  2. 决策树生成
  3. 决策树剪枝

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

决策树学习

决策树学习过程,假设给定训练数据集

\[
D={(x_1, y_1), (x_2, y_2), …,(x_n, y_n)}
\]

其中,$x_i=(x_i^{(1)}, x_i^{(2)}, …, x_i^{(n)})^T$为输入实例(特征向量),$n$为特征的个数,$y_i \epsilon \{1, 2, …, K\}$为类标记,$i=1,2, …, N$,$N$为样本容量。算法学习的目标是根据给定的训练数据集构建一个决策树模型,使得它能够对实例进行正确分类。

决策树的学习本质上是从训练数据中归纳出一组分类规则,决策树学习算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得各个子数据集有一个很好的分类过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。

用决策树进行分类,先从根结点开始,从实例中对根节点对应的特征的值进行测试,根据测试结果把实例分配到其子结点;然后从实例中对子节点对应的特征的值进行测试,一次递归,直到叶结点。最后叶结点表示的类就是实例的类。下图是泰坦尼克号幸存者条件的决策树,从决策树的中可以了解中从泰坦尼克号中生还的人具备的一些条件。

cart_tree_titanic_survivors

决策树的特征选择

在介绍特征选择之前举个例子,假如你注册了一个婚恋网站的账号,打算找个女朋友,然后你填写了一些个人资料,然后你打算找一个约会对象进行线下约会,婚恋网站一般会根据你的收入,年龄,地域,个人爱好为你推荐你可能喜欢的女孩子。每个人都有择偶标准的吧,比如,你找女朋友最看重的是外貌,比如脸长得一定要像徐若瑄的,然后再是身高一定要160-170的,体重一定要45kg的,家里一定要是广州本地的,一定要是会讲粤语的,然后年收入一定要是20万以上的等等。其实,有没有发现,你无形中就为自己建立了一棵决策树。而这棵决策树中,最重要的指标是女孩的外貌,其次是身高体重,再次是是否是本地人,以及会不会说粤语,最后是年收入。

假设婚恋网站每天都给你推荐100个女孩,然后你就在100女孩中真的就找到了1个长得很像徐若瑄的,而且其他的条件都很符合的。这个时候你给她发了一个约会邀请,或者给这个女孩打了一个喜欢的标签。因此,对你而言,你找到了一个适合和你约会的女孩子,而对婚恋网站而言,通过用户行为,网站也会学习到用户的喜好,慢慢给用户推荐合适的女孩子,这当然是后话。

回到特征选择的问题,特征选择的目的在于选取对训练数据具有分类能力的特征。这样可以提高决策树的学习效率。特征选择是决定用哪个特征来划分特征空间。

直观上,如果一个特征具有更好的分类能力(比如上文择偶条件中的外貌),或者说按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有很好的分类,那么就应选择这个特征。因此,信息增益(information gain)和信息增益比(information gain ratio)就能够很好地表示这一直观准则。

信息增益

在介绍信息增益之前,先得介绍熵(entropy),在信息论和概率论中,熵(entropy)是表示随机变量不确定性的度量。$X$是一个取有限个值的离散型随机变量,其概率分布为

\[
P(X=x_i)=p_i, i=1,2, …, n
\]

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

\[
H(X)=-\sum_{i=1}^{n}{p_i{\log{p_i}}}
\]

在上式中,如果$p_i=0$,则定义$0\log{0}=0$。由定义可知,熵只依赖于$X$的分布,而与$X$的取值无关,因此,也可将$X$的熵记作$H(P)$,即

\[
H(P)=-\sum_{i=1}^{n}{p_i{\log{p_i}}}
\]

熵越大,随机变量的不确定性也就越大。

条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性,定义为:

\[
H(Y|X)=-\sum_{i=1}^{n}{p_i{H(Y|X=x_i)}}
\]

这里,$p_i=P(X=x_i)$,$i=1,2, …, n$。

介绍到这里,终于要介绍信息增益了,信息增益表示得到特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。信息增益的公式为:

\[
g(D,A)=H(D)-H(D|A)
\]

根据信息增益准则的特征选择方法是:对训练数据集或子集$D$,计算其每个特征的信息增益,并且比较他们的大小,从中选择信息增益最大的特征。

前面介绍了那么多,这里总结一下信息增益的算法过程

    1. 输入:训练数据集$D$和特征$A$;
    2. 输出:特征$A$对训练数据集$D$的信息增益$g(D,A)$。
        • 计算数据集$D$的经验熵$H(D)=-\sum_{k=1}^{K}\frac{\left|C_k\right|}{\left|D\right|}\log_2\frac{\left|C_k\right|}{\left|D\right|}$,其中$\left | C_k \right |$表示属于类$k$的样本数。
        • 计算特征$A$对数据集$D$的经验条件熵\[
          H(D|A)=\sum_{i=1}^{n}\frac{\left|D_i\right|}{\left|D\right|}H(D_i)=-\sum_{i=1}^{n}\frac{\left|D_i\right|}{\left|D\right|}\sum_{k=1}^{K}\frac{\left|D_{ik}\right|}{\left|D_i\right|}\log_2\frac{\left|D_{ik}\right|}{\left|D_i\right|}
          \]
          其中,这里需要说明的是,在计算条件熵$H(D|A)$时,特征$A$是数据集的所有特征,假设数据集有$4$种特征,分别是$A_1=looks$,$A_2=height$,$A_3=weight$,$A_4=region$,这些特征的取值都是离散值,因此,需要分别计算特征$A_1$,$A_2$,$A_3$,$A_4$的条件熵。回到上面的公式,其中$n$是表示特征$A_x$取值的个数,比如特征$A_1$就有$A_{11}=type_1$,$A_{12}=type_2$,$A_{13}=type_3$,$A_{14}=type_4$4种取值,而$D_i$表示数据集中对特征$A_x$取其第$i$个值的子数据集,如对特征$A_1$,$D_1$表示数据集$D$中特征值$A_1$取$type_1$的子数据集。
        • 计算信息增益$g(D,A)=H(D)-H(D|A)$

信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。信息增益比(information gain ratio)定义为:特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比,即

\[
g_R(D,A)=\frac{g(D,A)}{H_A(D)}
\]

其中,$H_A(D)=-\sum_{i=1}^{n}\frac{\left|D_i\right|}{\left|D\right|}\log_2\frac{\left|D_i\right|}{\left|D\right|}$,$n$是特征$A$取值的个数。

决策树生成

前面已经介绍了决策树特征的选择算法,而特征选择的目的是为了建立决策树。因此,这里介绍ID3算法和C4.5算法。

ID3算法

ID3算法的核心是从特征中利用信息增益选择特征,作为树的一个结点,然后根据该特征的值将数据分成$n$($n$表示该特征取值的个数)份,继而在这$n$个子数据集上递归地构建决策树,直到所有的特征的信息增益均很小或者没有特征可供选择为止。下面给出算法步骤

  1. 输入:训练数据集$D$,特征集$A$,阈值$\epsilon$;
  2. 输出:决策树$T$
    1. 若$D$中所有实属于同一类$C_k$,则$T$为单结点树,并将$C_k$作为该结点的类标记,返回$T$;
    2. 若$A=\emptyset$,则$T$为单结点树,并将$D$中实例数最大的类$C_k$作为该结点的类标记,返回$T$;(说明:当没有特征可以选择时候的一种情况)
    3. 否则,计算$A$中的各个特征对$D$的信息增益,选择信息增益最大的特征$A_g$;
    4. 如果$A_g$的信息增益小于阈值$\epsilon$,则置$T$为单结点树,并将$D$中的实例数最大的类$C_k$作为该结点的类标记,返回$T$;
    5. 否则,对$A_g$的每一个可能的取值$a_i$,依$A_g=a_i$将$D$分割成若干个非空的子集$D_i$,构建子结点,由结点及其子结点构成树$T$,返回$T$;
    6. 对第$i$个子结点,以$D_i$为训练集,以$A-{A_g}$为特征集,递归地调用步1-步5,得到子树$T_i$,返回$T_i$

C4.5算法

C4.5算法和ID3算法的过程一致,只是C4.5算法使用信息增益比作为选择特征的标准,而ID3是把信息增益作为选择特征的标准。

决策树剪枝

利用决策树算法生成的决策树通常对于训练数据分类很准确,但是对于未知数据却不是很准确,这就是bias和varience的权衡,如果学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,那么生成的决策树通常bias会很低,容易出现过拟合,而varience会很高,因为模型的泛化能力很差。因此,我们需要对已生成的决策树进行简化,将决策树进行简化的过程称为剪枝(pruning),具体地,剪枝就是从树上裁掉一些子树或叶结点,并将其根结点或父结点作为新的叶结点,从而简化决策树。剪枝的本质是在过拟合和欠拟合之间找到一种平衡。

剪枝方法一般由两种,分别是预剪枝和后剪枝,预剪枝是在决策树生成的过程中进行的,是一种贪心算法,容易造成局部最优,但是生成树的过程速度快;而后剪枝是在决策树生成后对树进行剪枝,生成树的速度较慢。这里介绍后剪枝。

决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树$T$的叶结点个数为$\left|T\right|$,$t$是树$T$的叶结点,该结点有$N_t$个样本点,其中$k$类的样本点有$N_{tk}$个,$k=1,2, …, K$,$H_t(T)$为叶结点$t$上的经验熵,$\alpha\geq0$为参数,决策树的损失函数可以定义为
\[
C_\alpha(T)=\sum_{t=1}^{\left|T\right|}N_tH_t(T)+\alpha\left|T\right|
\]
其中经验熵为
\[
H_t(T)=-\sum_{k}^{}\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}
\]
在损失函数中,将其第一项记作
\[
C(T)=\sum_{t=1}^{\left|T\right|}N_tH_t(T)=-\sum_{t=1}^{\left|T\right|}\sum_{k=1}^{K}N_{tk}\log\frac{N_{tk}}{N_t}
\]
因此有
\[
C_\alpha(T)=C(T)+\alpha\left|T\right|
\]
其中,$C(T)$表示模型对训练数据的预测误差,即模型与训练数据的拟合程度,$\left|T\right|$表示模型的复杂度,参数$\alpha\geq0$控制两者之间的影响。较大的$\alpha$促使选择较简单的树,而较小的$\alpha$促使选择较复杂的树。$\alpha=0$意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。

因此,剪枝的目的很明确——当$\alpha$确定时,选择损失函数最小的模型,即损失函数最小的子树。

下面介绍剪枝算法

  1. 输入:生成算法产生的整个树$T$,参数$\alpha$
  2. 输出:修建后的子树$T_\alpha$
    1. 计算每个结点(非叶结点)的经验熵
    2. 递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数分别是$C_\alpha(T_B)$与$C_\alpha(T_A)$,如果$C_\alpha(T_A)\leq{C_\alpha(T_B)}$,则进行剪枝,即将父结点变为新的叶结点。
    3. 返回2,直至不能继续为止,得到损失函数最小的子树$T_\alpha$

ID3算法的Python代码

上面列了那么多公式,作为程序员,学了机器学习,总得拿代码练练手吧,下面的代码是修改自<<机器学习实战>>

代码写的有点乱,但是大家可以顾名思义看懂每个函数的意思,其实分裂数据集的时候对于被分裂的数据集$D_i$,它是没有其父数据集(姑且这么称呼吧)的那个分裂特征的,因此分裂的那个特征的那一列数据其实是被删除了的,子数据集的特征比其直接父数据集是少一个特征的,兄弟数据集的特征是一样的,调用分裂算法时选择的分裂特征是不太可能相同的(这里我说的有点啰嗦,希望读者可以明白)。

总结

其实真的要弄明白机器学习,基本的数学是少不了的,明白机器学习算法公式的推导,了解算法的流程对开发机器学习应用必不可少。目前这是我的第一篇介绍机器学习算法的博客,其实文章的大部分内容也是我对知识的总结,谈不上原创。我相信知识需要总结和分享,将来也将继续分享更多的算法。

引用

  • 李航,<<统计学习方法>>
  • 周志华,<<机器学习>>
  • Peter Harrington,<<机器学习实战>>
  • http://www.patricklamle.com/Tutorials/Decision%20tree%20python/tuto_decision%20tree.html

goingmyway

我是一只野生程序猿,我关注机器学习,神经网络,深度学习,增强学习,人工智能,Python,C/C++,Linux

发表评论

电子邮件地址不会被公开。 必填项已用*标注