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

《机器学习实战》第一部分 分类 第3章 决策树

程序员文章站 2022-05-01 14:26:01
...

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

在构造决策树时,第一个需要解决的问题就是,如何确定出哪个特征在划分数据分类是起决定性作用,或者说使用哪个特征分类能实现最好的分类效果。这样,为了找到决定性的特征,划分最好的结果,我们就需要评估每个特征。当找到最优特征后,依此特征,数据集就被划分为几个数据子集,这些数据自己会分布在该决策点的所有分支中。此时,如果某个分支下的数据属于同一类型,则该分支下的数据分类已经完成,无需进行下一步的数据集分类;如果分支下的数据子集内数据不属于同一类型,那么就要重复划分该数据集的过程,按照划分原始数据集相同的原则,确定出该数据子集中的最优特征,继续对数据子集进行分类,直到所有的特征已经遍历完成,或者所有叶结点分支下的数据具有相同的分类。

相关公式:
香农熵(entropy),简称熵,用来定量表示信息的聚合程度,是信息的期望值。
《机器学习实战》第一部分 分类 第3章 决策树
信息增益指的是划分数据集前后信息发生的变化。
《机器学习实战》第一部分 分类 第3章 决策树

问题描述:
海洋生物数据:
《机器学习实战》第一部分 分类 第3章 决策树
有两个特征:不浮出水面是否可以生存,是否有脚蹼,标签是鱼类和非鱼类,现在我们需要建立一个决策树分类器,根据这个分类器对其它动物进行预测,预测的准确性暂且不讨论。

数据离散化:
《机器学习实战》第一部分 分类 第3章 决策树

python代码实现:

1、创建数据集

def createDataSet():
    """
    创建测试数据集
    :return:
    """
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    feature = ['no surfacing','flippers']
    return dataSet, feature

2、计算给定数据集的熵

def calcShannonEnt(dataSet):
    """
    计算香农熵
    :param dataSet: 数据集
    :return: 香农熵
    """
    # 得到数据集的数据行数
    numEntries = len(dataSet)
    # 创建一个空字典
    featureCounts = {}
    for featVec in dataSet:
        # 获取每行最后一个数值,作为键值
        currentFeature = featVec[-1]
        # 如果当前键值不存在,则将键值添加进字典,键值对应的数值为0,意思是出现零次
        if currentFeature not in featureCounts.keys():
            featureCounts[currentFeature] = 0
        # 当前键值数值加1,代表出现次数多一次
        featureCounts[currentFeature] += 1
    # 定义香农熵
    shannonEnt = 0.0
    for key in featureCounts:
        # 键值出现概率
        prob = float(featureCounts[key]) / numEntries
        # 以2为底求对数
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

3、划分数据集

def splitDataSet(dataSet, axis, value):
    """
    划分数据集
    :param dataSet: 待划分的数据集
    :param axis:  每行特征的下标
    :param value: 对应的特征值
    :return:
    """
    # 创建一个空列表
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            # extend 在列表末尾追加另一个序列中的多个值
            reducedFeatVec.extend(featVec[axis+1:])
            # append 在列表末尾添加新对象
            retDataSet.append(reducedFeatVec)
    return retDataSet

4、遍历整个数据集,切分数据,求熵,找到最佳的特征划分方式

def chooseBestFeatureToSplit(dataSet):
    """
    遍历整个数据集,切分数据,求熵,找到最佳的特征划分方式
    :param dataSet:
    :return:
    """
    # 特征数量,去掉最后的标签
    numFeatures = len(dataSet[0]) -1
    # 计算整个数据集的原始熵
    baseEntropy = calcShannonEnt(dataSet)
    # 定义最佳信息增益
    bestInfoGain = 0.0
    # 定义最佳特征索引
    bestFeature = -1
    for i in range(numFeatures):
        # 取dataSet的第i行的第i列
        featList = [example[i] for example in dataSet]
        # 列表转集合去重
        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
        # 比较信息增益,得到最大值
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
     # 返回最佳特征的索引值
    return bestFeature

5、得到每列特征不同值的次数,返回出现次数最多的标签

def majorityCnt(classList):
    """
    得到每列特征不同值的次数,返回出现次数最多的标签
    :param classList:
    :return:
    """
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] +=1
    # sorted()函数对所有可迭代的对象进行排序操作
    # operator.itemgetter() 指定可迭代对象中的一个元素来进行排序
    # reverse=True表示降序
    sortedClassConnt = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassConnt[0][0]

6、递归的构建决策树(主函数)

def createTree(dataSet, featureSet):
    """
    主函数:递归的构建决策树
    :param dataSet: 数据集
    :param feature: 特征列
    :return:
    """
    # 深复制
    feature = copy.deepcopy(featureSet)
    # 提取数据集最后一列数据
    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)
    # 得到最佳特征名
    bestFeatFeature = feature[bestFeat]
    # 使用字典类型存储树的信息
    myTree = {bestFeatFeature:{}}
    # 从特征列表中删除最佳特征的列
    del(feature[bestFeat])
    # 得到最佳特征值对应的数据集中的那一列数据组成列表
    featValues = [example[bestFeat] for example in dataSet]
    # 唯一化
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 复制,开一块新内存
        subFeature = feature[:]
        # 递归
        myTree[bestFeatFeature][value] = createTree(splitDataSet(dataSet, bestFeat, value), subFeature)
    return myTree

7、测试算法

def classify(inputTree, feature, testVec):
    """
    测试算法
    :param inputTree: 构建好的决策树
    :param feature: 特征列
    :param testVec: 测试实例
    :return:
    """
    # 找到树的第一个分类特征,或者说根节点
    firstStr = list(inputTree.keys())[0]
    # 从树中得到该分类特征的分支
    secondDict = inputTree[firstStr]
    # 得到对应的索引
    featIndex = feature.index(firstStr)
    for key in secondDict.keys():
        # 测试集的第0个特征值等于第key个子节点
        if testVec[featIndex] == key:
            # 判断该子节点是否为字典类型
            if type(secondDict[key]).__name__ == 'dict':
                # 子节点为字典类型,则从该分支树开始继续遍历分类
                classFeature = classify(secondDict[key], feature, testVec)
            else:
                # 子节点不是字典类型,则返回节点取值,就是分类结果
                classFeature = secondDict[key]
    return classFeature

8、存取决策树

def storeTree(inputTree, filename):
    """
    pickle模块序列化决策树对象,保存在磁盘中
    :param inputTree:
    :param filename:
    :return:
    """
    # 创建一个可以'写'的文本文件,二进制方式写入
    fw = open(filename, 'wb+')
    # 将决策树写入文件
    pickle.dump(inputTree, fw)
    # 关闭
    fw.close()

def grabTree(filename):
    """
    读取决策树
    :param filename:
    :return:
    """
    # 二进制形式读出数据
    fr = open(filename, 'rb+')
    return pickle.load(fr)

最终的决策树结构:{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}
图形展示如下:
《机器学习实战》第一部分 分类 第3章 决策树