人工智能中文网
  • 主页
  • 线代考研视频
  • 线性代数
  • Python机器学习与算法
  • 大数据与机器学习
  • Python基础入门教程
  • 人工智能中文网
    教程目录
    阅读:

    决策树算法原理及Python实现(超详细)

    < 上一篇:支持向量机算法 下一篇:CART分类树算法 >
    决策树(Decision Tree)算法是一类常用的机器学习算法,在分类问题中,决策树算法通过样本中某一维属性的值,将样本划分到不同的类别中。以二分类为例,二分类的数据集如下表所示。

    表 1 数据集
    是否用鳃呼吸 有无鱼籍 是否为鱼
    鲨鱼
    鲫鱼
    河蚌
    海豚

    在表 1 中,有 5 个样本,样本中的属性为“是否用鳃呼吸”和“有无鱼鳍”,通过对样本的学习,如“鲸鲨”,可以利用学习到的决策树模型对于一个新的样本,正确地做出决策,即判断其是否为鱼。

    决策树算法是基于树形结构来进行决策的。如对于表 1 所示的数据,首先通过属性“是否用鳃呼吸”判断样本是否为鱼,如图 2 所示。


    图 2 通过属性“是否用鳃呼吸”划分数据

    从图 2 中可以看出,通过属性“是否用鳃呼吸”,已经将一部分样本区分开,即不用鳃呼吸的不是鱼,接下来对剩下的样本利用第二维属性“有无鱼鳍”进行划分,如图 3 所示。


    图 3 通过属性“有无鱼鳍”继续划分数据

    在图 3 中,通过属性“有无鱼鳍”对剩余的样本继续划分,得到了最终的决策,从图 3 中可以看出,不用鳃呼吸的不是鱼,用鳃呼吸但是没有鱼鳍的也不是鱼,用鳃呼吸同时有鱼鳍的是鱼。对于一个新的样本“鲸鲨”,其样本属性为 {用鳃呼吸,有鱼鳍},符合上述对鱼的判断,因此,认为鲸鲨为鱼。

    选择最佳划分的标准

    对于表 1 中所示的数据,其中每个样本包含了两个特征,分别为是否用鳃呼吸和有无鱼鳍,对于这两维特征,选择划分数据集的特征的时候存在一定的顺序,如图 2 中,首先选择的是“是否用鳃呼吸”,选择的依据是这一维特征对数据的划分更具有区分性,在决策树算法中,通常有这些标准:信息增益(Information Gain)增益率(Gain Ratio)基尼指数(Gini Index)

    熵(Entropy)是度量样本集合纯度最常用的一种指标,对于包含 m 个训练样本的数据集 D:{(X(1),y(1)),…,(X(m),y(m))},在数据集 D 中,第 k 类的样本所占的比例为 pk ,则数据集 D 的信息熵为:


     
    其中,K 表示的是数据集 D 中类别的个数。对于表 1 所示的数据集,其信息熵为:


     
    当把样本按照特征 A 的值 a 划分成两个独立的子数据集 D1 和 D2 时,此时整个数据集 D 的熵为两个独立数据集 D1 的熵和 D2 的熵的加权和,即:


     
    其中,D1 表示的是数据集 D1 中的样本的个数,D2 表示的是数据集 D2 中的样本的个数。对于表 1 所示的数据集,将样本按照特征“是否用鳃呼吸”划分成两个独立的子数据集,如图 2 所示,此时,数据集 D 的信息熵为:


     
    由上述的划分可以看出,在划分后数据集 D 的信息熵减小了,对于给定的数据集,划分前后信息熵的减少量称为信息增益(Information Gain),即:


    其中 |Dp| 表示的是属于第 p 类的样本的个数。信息熵表示的数据集中的不纯度,信息熵较小表明数据集纯度提升了。在选择数据集划分的标准时,通常选择能够使得信息增益最大的划分。ID3 决策树算法就是利用信息增益作为划分数据集的一种方法。

    增益率(Gain Ratio)是可以作为选择最优划分属性的方法,增益率的计算方法为:


     
    其中,IV(A) 被称为特征 A 的“固有值(Intrinsic Value)”,即:


     
    在著名的 C4.5 决策树算法中就是利用增益率作为划分数据集的方法。

    基尼指数(Gini Index)也可以选择最优的划分属性,对于数据集 D,假设有 K 个分类,则样本属于第 k 个类的概率为 pk ,则此概率分布的基尼指数为:


    对于数据集 D,其基尼指数为:


    其中,|Ck| 表示数据集 D 中,属于类别 k 的样本的个数。若此时根据特征 A 将数据集 D 划分成独立的两个数据集 D1 和 D2,此时的基尼指数为:


    在如表 1 所示的数据集 D 中,其基尼指数为:


    利用特征“是否用鳃呼吸”将数据集 D 划分成独立的两个数据集 D1 和 D2 后,其基尼指数为:



    在 CART 决策树算法中利用 Gini 指数作为划分数据集的方法。

    现在,让我们一起利用 Python 实现上述的 Gini 指数的计算过程,Gini 指数的具体计算方法如下程序所示:
    def cal_gini_index(data):
        '''计算给定数据集的Gini指数
        input: data (list):数据集、
        output: gini (float) :Gini 指数
        '''
        total_sample = len (data) # 样本的总个数
        if len(data)==0:
            return 0
        label_counts = label_uniq_cnt (data)#统计数据集中不同标签的个数
        #计算数据集的Gini指数
        gini = 0
        for label in label_counts:
            gini = gini + pow(label_counts[label],2)
        gini = 1 - float(gini) / pow(total_sample, 2)
        return gini
    该程序中:
    • 函数 cal_gini_index 用于计算数据集 data 的 Gini 指数,在计算 Gini 指数的过程中,需要判断数据集中类别标签的个数;
    • label_uniq_cnt 函数用于计算数据集 data 中不同的类别标签的个数,此函数的具体实现如下所示:
    def label_uniq_cnt(data):
        '''统计数据集中不同的类标签label的个数
        input: data (list):原始数据集
        output: label_uniq_cnt (int):样本中的标签的个数
        '''
        label_uniq_cnt = {}
        for x in data:
            label = x[len(x) - 1] #取得每一个样本的类标签label
            if label not in label_uniq_cnt:
                label_uniq_cnt[label] = 0
            label_uniq_cnt[label] = label_uniq_cnt[label] + 1
        return label_uniq_cnt
    • 函数 label_uniq_cnt 用于统计数据集 data 中不同标签的个数,并将统计结果存储到字典 label_uniq_cnt 中。

    通过统计不同类别标签的个数,并根据上述的计算方法计算当前的数据集 data 中的 Gini 指数(如程序中所示)。在计算 Gini 指数的过程中,需要用到 pow 函数,因此,在程序开始前,我们需要导入 pow:
    from math import pow

    停止划分的标准

    在按照特征对上述的数据进行划分的过程中,需要设置划分的终止条件,通常在算法的过程中,设置划分终止条件的方法主要有:
    • 结点中的样本数小于给定阀值;
    • 样本集的基尼指数小于给定阀值(样本基本属于同一类);
    • 没有更多特征;

    在图 3 所示的最终的划分中,当叶子节点中的所有样本属于同一个类别时,停止划分。
    < 上一篇:支持向量机算法 下一篇:CART分类树算法 >