决策树的python实现详解——《机器学习实战》

时间：2022-05-09 23:52:10

一、简介

（1）本章主要使用字典来存储决策树，但字典的可读性太低。后面将用matplotlib将其形象化。

优点：计算复杂度不高、输出结果易于理解、对中间值的缺失不敏感、可以处理不相关特征数据

缺点：可能会产生过度匹配问题

（2）#创建决策树的伪代码函数createBranch()如下：
检查数据集中的每个子项是否属于同一个分类
if so return 类标签；
else
    寻找划分数据集的最好特征
    划分数据集
    创建分支结点
        for 每个划分的子集
            调用createBranch并增加返回结果到分支结点中
    return 分支结点

二、构造决策树

一步一步将上述伪代码转为Python代码

1 划分数据集

划分数据集的原则是：将无序的数据变得更加有序。在这里，用“信息增益（information gain）”来衡量数据的有序程度。信息增益越大，则数据变得更有序。

数据假定为:决策树的python实现详解——《机器学习实战》

第一列为feature1,第二列为feature2,第三列为label

信息增益=原始数据集的熵之和-新数据集的熵之和

那么什么是熵（entropy）呢？（这边只介绍公式，具体内容大家有兴趣的自行了解）熵来源于信息论之父克劳德·香农。对于指定label的数据集，其熵的计算公式为：  

           e=-pi*log(2,pi)

其中，pi表示该label（"yes","no"或“maybe”）的数量占总样本数量的比例。

如果我们要计算整个数据集的熵，则：

H=-（p1*log(2,p1）+p2*log(2,p2)+...+pn*log(2,pn))

其中，pn为第n个label占总数的比。

（1）计算给定数据集的香农熵

#计算给定数据集的香农熵
from math import log
def calcShannonEnt(dataSet):
    numEntries=len(dataSet)
    labelCounts={}    #定义一个统计label的字典，每个Label都能且只能被存放1次
    #统计各个label的数量,放在字典里
    for featVec in dataSet:
        currentLabel=featVec[-1]    #取最后一列（label列）
        if currentLabel not in labelCounts.keys():  #如果取出的这个label不在字典里，就在下面加入labelCounts中，并将其次数初始化为0
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1      #为当前取出的label的次数加1
    shannonEnt=0.0
    #遍历每个label,分别计算每个label对应的熵并累加起来
    for key in labelCounts:   
        prop=float(labelCounts[key])/numEntries
        shannonEnt-=prop*log(prop,2)
    return shannonEnt

（2）上一步实现了对某一特定数据集熵的计算，现在来学习怎样按照给定的feature划分出一个新的数据集。

#按照给定特征划分数据集
#axis:划分数据集的特征值的维度（哪个feature）
#value:维度axis上的返回值（0,1或者3）
def splitDataSet(dataSet,axis,value):
    retDataSet=[]    #创建返回的list
    #遍历dataSet中的每个样本
    for featVec in dataSet:
        if featVec[axis]==value:
            #抽取：将符合要求的值去掉axis列数据（去除该feature）后添加到retDataSet集上
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])   #extend:把一个序列（sequence）的内容添加到列表中
            retDataSet.append(reducedFeatVec)         #append:向列表中添加一个对象
    return retDataSet

（3）现在，我们学会了计算指定数据集的香农熵和按照指定feature划分数据集。现在，将这两个结合起来，我们就知道怎么选择最好的数据集划分方式了：

#选择最好的数据集划分方式
#返回可获得最大信息增益的那个feature的维度
def chooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1    #计算feature的数量（减1：减去最后一列标签）
    baseEntropy=calcShannonEnt(dataSet)    #计算了数据集的原始香农熵
    bestInfoGain=0.0    #初始化最佳的信息增益位0.0
    bestFeature=-1      #初始化最好的feature的维度为-1
    #遍历每列feature
    for i in range(numFeatures):
        featList=[example[i] for example in dataSet]    #遍历dataSet的每一行，取其第i个feature（第i列）上的属性值放在featList上
        uniqueVals=set(featList)    #set():创建featList上“无序不重复”的元素集
        newEntropy=0.0
        #遍历i列feature中的所有可能属性值(不重复）
        #计算第i列feature的信息增益
        for value in uniqueVals:
            #计算i列所有划分方式的信息熵之和
            subDataSet=splitDataSet(dataSet,i,value)
            prob=len(subDataSet)/float(len(dataSet))
            newEntropy+=prob*calcShannonEnt(subDataSet)
        #计算信息增益
        infoGain=baseEntropy-newEntropy
        #比较所有特征中的信息增益，如果当前信息增益大于bestInfoGain,则更新这个bestInfoGain
        if(infoGain>bestInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature

2 递归构造决策树

回顾第一部分，我们已经学习了从数据集构建决策树算法所需要的子功能模块：将原始数据集基于最好的feature划分。第一次划分后，数据集将被分散传递到树分支的子节点，在这个节点上，我们可以再次划分数据（当feature不止1个时）。因此，我们可以采用递归的原则处理数据集。

递归结束的条件是：①每个分支下的所有的所有实例都具有相同的分类；②程序遍历完所有划分数据集的feature

第二个结束条件使得算法可以终止。但是如果程序遍历完所有feature后，某些feature中的属性对应的label仍不是唯一的，此时我们需要决定如何定义该叶子节点。

（1）在这种情况下，通常采用“多数表决”的方法决定该叶子节点的分类：

#多数表决:返回出现频率最高的那个标签
def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys:
            classCount[vote]=0
        classCount[vote]+=1
    #按照classCount中value值从大到小排列
    sortedClassCount=sorted(classCount.items(),
                            key=operator.itemgetter(1),    #获取对象第1个域的值（第0个域：key,第1个域：value）
                            reverse=True)
    return sortedClassCount[0][0]

（2）现在，可以真正地构建树了（一棵存储在字典中的树）

#feature:feature的名称 
def createTree(dataSet,feature):
    classList=[example[-1] for example in dataSet]  #取出dataSet的label集
    #若classList中所有的标签都和classList[0]的一致（类别完全相同），则停止继续划分
    if classList.count(classList[0])==len(classList):
        return classList[0]
    #若使用完了所有特征，仍不能将数据集划分成仅包含唯一label的分组
    #则返回出现次数最多的类别作为标签
    if len(dataSet[0])==1:
        return majorityCnt(classList)
    bestFeat=chooseBestFeatureToSplit(dataSet)     #找出最适合划分数据集的feature的维度
    bestFeatFeature=feature[bestFeat]          #找出对应的feature名称
    myTree={bestFeatFeature:{}}           #决策树的key为当前的bestFeatFeature
    del(feature[bestFeat])        #删除当前这列feature           
    featValues=[example[bestFeat] for example in dataSet]   #遍历这列feature的每个属性值，取出放在featValues上
    uniqueVals=set(featValues)   #创建featValues上的无序不重复元素集
    #遍历当前feature上的每个属性
    for value in uniqueVals:
        subFeature=feature[:]
        #对每个属性的子节点调用createTree进行下一步划分
        myTree[bestFeatFeature][value]=createTree(splitDataSet(dataSet,bestFeat,value),subFeature)
    return myTree


                                   


标签：

相关文章