欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

决策树--- ID3 & C4.5

程序员文章站 2024-02-26 15:57:46
...

决策树

决策树算法

  • 分类算法是利用训练样本集获得分类函数即分类模型（分类器），从而实现将数据集中的样本划分到各个类中。分类模型通过学习训练样本中的属性集与类别之间的潜在关系，并以此为依据对新样本属于哪一类进行预测。

决策树--- ID3 & C4.5

  • 决策树通过把数据样本分配到某个叶子结点来确定数据集中样本所属的分类
  • 决策树由结点、分支和叶子结点组成
    • 决策结点表示在样本的一个属性上进行的划分
    • 分支表示对于决策结点进行划分的输出
    • 叶结点代表经过分支到达的类
  • 从决策树根结点出发，自顶向下移动，在每个决策结点都会进行次划分，通过划分的结果将样本进行分类，导致不同的分支，最后到达叶子结点，这个过程就是利用决策树进行分类的过程

分支处理

  • 往往使用启发式算法来进行决策树的构造，例如，使用贪婪算法对每个结点构造部分最优决策树
  • 对于一个决策树的构建，最重要的部分就在于其分支处理，即确定在每个决策结点处的分支属性
  • 分支属性的选取即对决策节点上选择哪一个属性来对数据集进行划分，要求每个分支中样本的类别纯度尽可能高，而且不要产生样本数量太少的分支

基本流程

  • 决策树的一般流程
    （1）收集数据：可以用任何方法
    （2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
    （3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
    （4）训练算法：构造树的数据结构
    （5）测试算法：使用经验树计算错误率
    （6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
  • 下面给出西瓜书的基本流程算法
    决策树--- ID3 & C4.5

划分选择

决策树学习的关键是，如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)

西瓜数据集，如下图所示：
决策树--- ID3 & C4.5

信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合DD中的第kk类样本所占的比例为pk(k=1,2,...,∣y∣p_k(k=1,2,...,|y|)，则DD的信息熵定义为Ent(D)=−∑1∣y∣pk∗log2pkEnt(D)=-\sum_1^{|y|}p_k*log_2{p_k}
Ent(D)Ent(D)的值越小，则DD的纯度越高。

假定离散属性aa有VV个可能的取值{a1,a2,...,aV}\{a^1,a^2,...,a^V \},若使用aa来对样本集DD进行划分，则会产生VV个分支结点，其中第vv个分支结点包含了DD中所有在属性aa上取值为ava^v的样本，记为DvD^v。根据上述公式计算出DD的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重∣Dv∣/∣D∣|D^v|/|D|，即样本数越多的分支结点的影响越大，于是可以计算出用属性aa对样本集DD进行划分所获得的“信息增益”(information gain)
Gain(D,a)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv) Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
一般而言，信息增益越大，则意味着使用属性aa来划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在算法流程的第8行选择属性a∗=arg max⁡a∈AGain(D,a)a_*=arg\, \max_{a\in A} Gain(D,a)。著名的ID3决策树学习算法[Quinlan,1986][Quinlan,1986]就是以信息增益为准则来选择划分属性。

下面给出对根结点信息熵的计算ID3.py

# -*- coding: utf-8 -*-
# @Time    : 2020/07/02
# @Author  : AWAYASAWAY
# @File    : tree.py
# @IDE     : PyCharm
from math import log
from decimal import Decimal

def calcShannonEnt(dataSet):
    '''
    计算给定数据集的根节点的香农熵：一般为最后一列
    :param dataSet:
    :return:返回根结点的shannonEnt
    '''
    # 获取数据集dataSet列表的长度
    numEntries = len(dataSet)
    # 新建一个数据字典，用来统计每个标签出现的次数，计算概率
    labelCounts = {}
    for featVec in dataSet:
        # featVec[-1]获取dataSet每行中最后一个数据，作为字典中的key（标签）
        currentLabel = featVec[-1]
        # 以currentLabel作为key加入到labelCounts
        # 如果当前的键值不存在，则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。
        # 键值存在则对应Value+'a',否则为'b'
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    Ent = 0.0
    shannonEnt = 0.0
    for key in labelCounts:
        # 计算正反例样本
        # print('labels：', key)
        # 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度
        prob = float(labelCounts[key]) / numEntries
        # 计算香农熵，以'c'为底求对数
        shannonEnt += -prob * log(prob, 2)
    return shannonEnt


def createDataset():
    '''
    创建数据：西瓜书 76 页
    数据类型：不限定
    :dataSet:西瓜数据集
    :return:dataSet, label
    '''
    dataSet = [
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'],
        ['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'],
        ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'],
        ['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
        ['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'],
        ['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
        ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']
    ]
    labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']
    return dataSet, labels


def splitDataSet(dataSet, axis, value):
    '''
    按照给定特征划分数据集
    :param dataSet:
    :param axis:
    :param value:
    :return:
    '''
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            # reduceFeatVec 为新生的空list
            reduceFeatVec = featVec[:axis]
            # extend只是扩展长度
            reduceFeatVec.extend(featVec[axis + 1:])
            # append添加列表
            retDataSet.append(reduceFeatVec)
    return retDataSet


def chooseBestFeature2Split(dataSet):
    '''
    选择最好的数据集划分方式
    :param dataSet:
    :return:
    '''
    # 提取特属性集合的长度
    numFeatures = len(dataSet[0]) - 1
    # 根结点的香农熵/整个数据集的原始香农熵
    baseEntropy = calcShannonEnt(dataSet)
    print('整个数据集的原始香农熵 %.3f' % baseEntropy)
    # 特征 i 拥有最好的信息增益
    bestInfoGain = 0.0
    bestFeature = -1
    featInfoGain = []
    for i in range(numFeatures):
        # 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素,放入列表featList中
        # 提取所有的属性值
        featList = [example[i] for example in dataSet]
        # print(featList)
        # 删除重复的属性值,创建唯一的分类标签列表
        uniqueVals = listDeduplication(featList)
        # uniqueVals = set(featList)
        newEntropy = 0.0
        # 计算每种划分方式的信息熵
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        infoGain = float(Decimal(infoGain).quantize(Decimal('0.000')))
        featInfoGain.append((infoGain))
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i

    return featInfoGain, bestFeature, bestInfoGain


def listDeduplication(x):
    '''
    List去重
    :param x: list
    :return: list
    '''
    return list(dict.fromkeys(x))


if __name__ == '__main__':
    dataSet, labels = createDataset()
    featInfoGain, bestFeature, bestInfoGain = chooseBestFeature2Split(dataSet)

    print('各个属性的信息增益')
    d = dict(zip(labels[:-1], featInfoGain))
    for key, value in d.items():
        print(key, '=', value)
    print(labels[bestFeature], '的信息增益最大= %.3f'% bestInfoGain)



整个数据集的原始香农熵 0.998
各个属性的信息增益
色泽 = 0.108
根蒂 = 0.143
敲声 = 0.141
纹理 = 0.381
脐部 = 0.289
触感 = 0.006
纹理 的信息增益最大= 0.381

增益率

但是当每个分支结点仅包含一个样本时，这些分支结点的纯度已达到最大（如，编号列）。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效的预测。

实际上，信息增益准则对可能取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5C4.5决策树算法[Quinlan,1993][Quinlan,1993]不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优的划分属性，增益率定义为:
GainRation(D,a)=Gain(D,a)IV(a) GainRation(D,a) = \frac{Gain(D,a)}{IV(a)}
其中
IV(a)=−∑v=1V∣Dv∣∣D∣log⁡2∣Dv∣∣D∣ IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2{\frac{|D^v|}{|D|}}
称为aa的“固有值”(intrinsicvalue)[Quinlan,1993].(intrinsic value)[Quinlan, 1993]. 属性aa的可能取值数目越多(即VV越大)，则IV(a)IV(a)的值通常会很大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式[Quinlan,1993]:[Quinlan, 1993]: 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

下面给出的计算C4.5.py

#-*- coding: utf-8 -*-
# @Time    : 2020/7/2 16:24
# @Author  : AWAYASAWAY
# @File    : C4.5.py
# @IDE     : PyCharm

from math import log
from decimal import Decimal

def calcShannonEnt(dataSet):
    '''
    计算给定数据集的根节点的香农熵：一般为最后一列
    :param dataSet:
    :return:返回根结点的shannonEnt
    '''
    # 获取数据集dataSet列表的长度
    numEntries = len(dataSet)
    # 新建一个数据字典，用来统计每个标签出现的次数，计算概率
    labelCounts = {}
    for featVec in dataSet:
        # featVec[-1]获取dataSet每行中最后一个数据，作为字典中的key（标签）
        currentLabel = featVec[-1]
        # 以currentLabel作为key加入到labelCounts
        # 如果当前的键值不存在，则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。
        # 键值存在则对应Value+'a',否则为'b'
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    Ent = 0.0
    shannonEnt = 0.0
    for key in labelCounts:
        # 计算正反例样本
        # print('labels：', key)
        # 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度
        prob = float(labelCounts[key]) / numEntries
        # 计算香农熵
        shannonEnt += -prob * log(prob, 2)
    return shannonEnt


def createDataset():
    '''
    创建数据：西瓜书 76 页
    数据类型：不限定
    :dataSet:西瓜数据集
    :return:dataSet, label
    '''
    dataSet = [
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'],
        ['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'],
        ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'],
        ['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
        ['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'],
        ['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
        ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否']
    ]
    labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜']
    return dataSet, labels


def splitDataSet(dataSet, axis, value):
    '''
    按照给定特征划分数据集
    :param dataSet:
    :param axis:
    :param value:
    :return:
    '''
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            # reduceFeatVec 为新生的空list
            reduceFeatVec = featVec[:axis]
            # extend只是扩展长度
            reduceFeatVec.extend(featVec[axis + 1:])
            # append添加列表
            retDataSet.append(reduceFeatVec)
    return retDataSet


def chooseBestFeature2Split(dataSet):
    '''
    选择最好的数据集划分方式
    :param dataSet:
    :return:
    '''
    # 提取特属性集合的长度
    numFeatures = len(dataSet[0]) - 1
    # 根结点的香农熵/整个数据集的原始香农熵
    baseEntropy = calcShannonEnt(dataSet)
    print('整个数据集的原始香农熵 %.3f' % baseEntropy)
    # 特征 i 拥有最好的信息增益
    bestInfoGain = 0.0
    bestGainRatio = 0.0
    bestFeature = -1
    featInfoGain = []
    featGainRatio = []
    for i in range(numFeatures):
        # 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素,放入列表featList中
        # 提取所有的属性值
        featList = [example[i] for example in dataSet]
        # print(featList)
        # 删除重复的属性值,创建唯一的分类标签列表
        #uniqueVals = listDeduplication(featList)
        uniqueVals = set(featList)
        newEntropy = 0.0
        intrinsicValue = 0.0
        # 计算每种划分方式的信息熵
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            intrinsicValue += -prob * log(prob, 2)
            newEntropy += prob * calcShannonEnt(subDataSet)
        # 计算每个属性的信息增益，添加到列表featInfoGain

        print('固有值：IV(a)=%.3f' % intrinsicValue)
        infoGain = baseEntropy - newEntropy
        infoGain = float(Decimal(infoGain).quantize(Decimal('0.000')))
        featInfoGain.append((infoGain))
        # 计算每个属性的信息增益率，添加到列表featGainRatio
        gainRatio = infoGain / intrinsicValue
        gainRatio = float(Decimal(gainRatio).quantize(Decimal('0.000')))
        featGainRatio.append(gainRatio)
        if gainRatio > bestGainRatio:
            bestGainRatio = gainRatio
            bestFeature = i

    return featInfoGain, featGainRatio, bestFeature, bestInfoGain, bestGainRatio, newEntropy


def listDeduplication(x):
    '''
    set函数就可以
    :param x: list
    :return: list
    '''
    return list(dict.fromkeys(x))


if __name__ == '__main__':
    dataSet, labels = createDataset()
    # 输出
    featInfoGain, \
    featGainRatio, \
    bestFeature,\
    bestInfoGain,\
    bestGainRatio,\
    newEntropy = chooseBestFeature2Split(dataSet)

    print('各个属性的信息增益')
    d = dict(zip(labels[:-1], featInfoGain))
    for key, value in d.items():
        print(key, '=', value)
    print('各个属性的信息增益率')
    c = dict(zip(labels[:-1], featGainRatio))
    for key, value in c.items():
        print(key, '=', value)
    print(labels[bestFeature], '的信息增益率最大= %.3f'% bestGainRatio)

计算结果如下：

整个数据集的原始香农熵 0.998
固有值：IV(a)=1.580
固有值：IV(a)=1.402
固有值：IV(a)=1.333
固有值：IV(a)=1.447
固有值：IV(a)=1.549
固有值：IV(a)=0.874
各个属性的信息增益
色泽 = 0.108
根蒂 = 0.143
敲声 = 0.141
纹理 = 0.381
脐部 = 0.289
触感 = 0.006
各个属性的信息增益率
色泽 = 0.068
根蒂 = 0.102
敲声 = 0.106
纹理 = 0.263
脐部 = 0.187
触感 = 0.007
纹理 的信息增益率最大= 0.263
):
相关标签： 决策树 python

上一篇： 实现Java线程的取值并返回的方法

下一篇： 分享CentOS下MySQL最新版本5.6.13源码安装过程

推荐阅读