美文网首页
机器学习实战教程(三):决策树实战篇(a)

机器学习实战教程(三):决策树实战篇(a)

作者: 公子曼步 | 来源:发表于2020-10-21 20:53 被阅读0次

    一、前言

    上篇文章机器学习实战教程(二):决策树基础篇讲述了机器学习决策树的原理,以及如何选择最优特征作为分类特征。本篇文章将在此基础上进行介绍。主要包括:

    决策树构建

    决策树可视化

    使用决策树进行分类预测

    决策树的存储和读取

    sklearn实战之预测隐形眼睛类型

    二、决策树构建

    上篇文章也粗略提到过,构建决策树的算法有很多。篇幅原因,本篇文章只使用ID3算法构建决策树。

    1、ID3算法

    ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子节点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。

    在使用ID3构造决策树之前,我们再分析下数据。

    免费视频教程:www.mlxs.top    

    利用上篇文章求得的结果,由于特征A3(有自己的房子)的信息增益值最大,所以选择特征A3作为根结点的特征。它将训练集D划分为两个子集D1(A3取值为"是")和D2(A3取值为"否")。由于D1只有同一类的样本点,所以它成为一个叶结点,结点的类标记为“是”。

    对D2则需要从特征A1(年龄),A2(有工作)和A4(信贷情况)中选择新的特征,计算各个特征的信息增益:

    免费视频教程:www.mlxs.top    

    根据计算,选择信息增益最大的特征A2(有工作)作为结点的特征。由于A2有两个可能取值,从这一结点引出两个子结点:一个对应"是"(有工作)的子结点,包含3个样本,它们属于同一类,所以这是一个叶结点,类标记为"是";另一个是对应"否"(无工作)的子结点,包含6个样本,它们也属于同一类,所以这也是一个叶结点,类标记为"否"。

    这样就生成了一个决策树,该决策树只用了两个特征(有两个内部结点),生成的决策树如下图所示。

    免费视频教程:www.mlxs.top    

    这样我们就使用ID3算法构建出来了决策树,接下来,让我们看看如何进行代实现。

    2、编写代码构建决策树

    我们使用字典存储决策树的结构,比如上小节我们分析出来的决策树,用字典可以表示为:

    # -*- coding: UTF-8 -*-

    from math import log

    import operator

    """

    函数说明:计算给定数据集的经验熵(香农熵)

    Parameters:

        dataSet - 数据集

    Returns:

        shannonEnt - 经验熵(香农熵)

    Author:

        Jack Cui

    Modify:

        2017-07-24

    """

    def calcShannonEnt(dataSet):

        numEntires = len(dataSet)                        #返回数据集的行数

        labelCounts = {}                                #保存每个标签(Label)出现次数的字典

        for featVec in dataSet:                            #对每组特征向量进行统计

            currentLabel = featVec[-1]                    #提取标签(Label)信息

            if currentLabel not in labelCounts.keys():    #如果标签(Label)没有放入统计次数的字典,添加进去

                labelCounts[currentLabel] = 0

            labelCounts[currentLabel] += 1                #Label计数

        shannonEnt = 0.0                                #经验熵(香农熵)

        for key in labelCounts:                            #计算香农熵

            prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率

            shannonEnt -= prob * log(prob, 2)            #利用公式计算

        return shannonEnt                                #返回经验熵(香农熵)

    """

    函数说明:创建测试数据集

    Parameters:

        无

    Returns:

        dataSet - 数据集

        labels - 特征标签

    Author:

        Jack Cui

    Modify:

        2017-07-20

    """

    def createDataSet():

        dataSet = [[0, 0, 0, 0, 'no'],                        #数据集

                [0, 0, 0, 1, 'no'],

                [0, 1, 0, 1, 'yes'],

                [0, 1, 1, 0, 'yes'],

                [0, 0, 0, 0, 'no'],

                [1, 0, 0, 0, 'no'],

                [1, 0, 0, 1, 'no'],

                [1, 1, 1, 1, 'yes'],

                [1, 0, 1, 2, 'yes'],

                [1, 0, 1, 2, 'yes'],

                [2, 0, 1, 2, 'yes'],

                [2, 0, 1, 1, 'yes'],

                [2, 1, 0, 1, 'yes'],

                [2, 1, 0, 2, 'yes'],

                [2, 0, 0, 0, 'no']]

        labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #特征标签

        return dataSet, labels                            #返回数据集和分类属性

    """

    函数说明:按照给定特征划分数据集

    Parameters:

        dataSet - 待划分的数据集

        axis - 划分数据集的特征

        value - 需要返回的特征的值

    Returns:

        无

    Author:

        Jack Cui

    Modify:

        2017-07-24

    """

    def splitDataSet(dataSet, axis, value):     

        retDataSet = []                                        #创建返回的数据集列表

        for featVec in dataSet:                            #遍历数据集

            if featVec[axis] == value:

                reducedFeatVec = featVec[:axis]                #去掉axis特征

                reducedFeatVec.extend(featVec[axis+1:])    #将符合条件的添加到返回的数据集

                retDataSet.append(reducedFeatVec)

        return retDataSet                                      #返回划分后的数据集

    """

    函数说明:选择最优特征

    Parameters:

        dataSet - 数据集

    Returns:

        bestFeature - 信息增益最大的(最优)特征的索引值

    Author:

        Jack Cui

    Modify:

        2017-07-20

    """

    def chooseBestFeatureToSplit(dataSet):

        numFeatures = len(dataSet[0]) - 1                    #特征数量

        baseEntropy = calcShannonEnt(dataSet)                #计算数据集的香农熵

        bestInfoGain = 0.0                                  #信息增益

        bestFeature = -1                                    #最优特征的索引值

        for i in range(numFeatures):                        #遍历所有特征

            #获取dataSet的第i个所有特征

            featList = [example[i] for example in dataSet]

            uniqueVals = set(featList)                        #创建set集合{},元素不可重复

            newEntropy = 0.0                                  #经验条件熵

            for value in uniqueVals:                        #计算信息增益

                subDataSet = splitDataSet(dataSet, i, value)        #subDataSet划分后的子集

                prob = len(subDataSet) / float(len(dataSet))          #计算子集的概率

                newEntropy += prob * calcShannonEnt(subDataSet)    #根据公式计算经验条件熵

            infoGain = baseEntropy - newEntropy                    #信息增益

            # print("第%d个特征的增益为%.3f" % (i, infoGain))            #打印每个特征的信息增益

            if (infoGain > bestInfoGain):                            #计算信息增益

                bestInfoGain = infoGain                            #更新信息增益,找到最大的信息增益

                bestFeature = i                                    #记录信息增益最大的特征的索引值

        return bestFeature                                            #返回信息增益最大的特征的索引值

    """

    函数说明:统计classList中出现此处最多的元素(类标签)

    Parameters:

        classList - 类标签列表

    Returns:

        sortedClassCount[0][0] - 出现此处最多的元素(类标签)

    Author:

        Jack Cui

    Modify:

        2017-07-24

    """

    def majorityCnt(classList):

        classCount = {}

        for vote in classList:                                        #统计classList中每个元素出现的次数

            if vote not in classCount.keys():classCount[vote] = 0 

            classCount[vote] += 1

        sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序

        return sortedClassCount[0][0]                                #返回classList中出现次数最多的元素

    """

    函数说明:创建决策树

    Parameters:

        dataSet - 训练数据集

        labels - 分类属性标签

        featLabels - 存储选择的最优特征标签

    Returns:

        myTree - 决策树

    Author:

        Jack Cui

    Modify:

        2017-07-25

    """

    def createTree(dataSet, labels, featLabels):

        classList = [example[-1] for example in dataSet]            #取分类标签(是否放贷:yes or no)

        if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分

            return classList[0]

        if len(dataSet[0]) == 1 or len(labels) == 0:                                    #遍历完所有特征时返回出现次数最多的类标签

            return majorityCnt(classList)

        bestFeat = chooseBestFeatureToSplit(dataSet)                #选择最优特征

        bestFeatLabel = labels[bestFeat]                            #最优特征的标签

        featLabels.append(bestFeatLabel)

        myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树

        del(labels[bestFeat])                                        #删除已经使用特征标签

        featValues = [example[bestFeat] for example in dataSet]        #得到训练集中所有最优特征的属性值

        uniqueVals = set(featValues)                                #去掉重复的属性值

        for value in uniqueVals:                                  #遍历特征,创建决策树。       

            subLabels = labels[:]             

            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)

        return myTree

    if __name__ == '__main__':

        dataSet, labels = createDataSet()

        featLabels = []

        myTree = createTree(dataSet, labels, featLabels)

        print(myTree)

    递归创建决策树时,递归有两个终止条件:第一个停止条件是所有的类标签完全相同,则直接返回该类标签;第二个停止条件是使用完了所有特征,仍然不能将数据划分仅包含唯一类别的分组,即决策树构建失败,特征不够用。此时说明数据纬度不够,由于第二个停止条件无法简单地返回唯一的类标签,这里挑选出现数量最多的类别作为返回值。

    运行上述代码,我们可以看到如下结果:

    免费视频教程:www.mlxs.top    

    可见,我们的决策树已经构建完成了。这时候,有的朋友可能会说,这个决策树看着好别扭,虽然这个能看懂,但是如果多点的结点,就不好看了。能直观点吗?完全没有问题,我们可以使用强大的Matplotlib绘制决策树。免费视频教程:www.mlxs.top  

    相关文章

      网友评论

          本文标题:机器学习实战教程(三):决策树实战篇(a)

          本文链接:https://www.haomeiwen.com/subject/edzemktx.html