python学智能算法（八）|决策树

【1】引言

前序学习进程中，已经对KNN邻近算法有了探索，相关文章链接为：

python学智能算法（七）|KNN邻近算法-CSDN博客

但KNN邻近算法有一个特点是：它在分类的时候，不能知晓每个类别内事物的具体面貌，只能获得类别，停留在事物的表面。

为了进一步探索事物的内在特征，就需要学习新的算法。

本篇文章就是在KNN的基础上学习新算法：决策树。

【2】原理分析

在学习决策树执之前，需要先了解香农熵。

本科学控制课，老师讲到香农熵，那时候啥也不懂，以为就是个普通公式，多年以后，看到这三个字难免感慨当年太过幼稚。

【2.1】香农熵

香农熵比较简单，从数学层面上看就是对数求和。

这是香农熵的求解代码：

import numpy as np
from math import log #引入log()函数求对数

# 定义一个嵌套列表
def creatDataset():
    # dataset是一个嵌套列表
    dataset=[
        [1,1,'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']
    ]
    # lables也是一个列表
    labels=['no surfacing','flippers']
    return dataset,labels

# calcShannonEnt是具体的香农熵求解函数
def calcShannonEnt(dataset):
    # numEntries获得了dataset列表的行数
    numEntries=len(dataset)
    # labelcounts是一个空的字典
    labelcounts={}
    # for函数的意义是，对于dataset里面的每一行都会执行循环操作
    for feature in dataset:
        # currentlabel 取到了feature的最后一个元素
        currentlabel=feature[-1]
        # 由于labelcounts是一个空字典，labelcounts.keys()在第一次运行的时候不会指向任何标签，所以会被直接添加
        # currentlabel是每一行dataset的最后一列，也就是最后一个元素
        # if函数实际上进行了同类项合并工作
        if currentlabel not in labelcounts.keys():
            # 给以currentlabel为标签的项目赋值0
            labelcounts[currentlabel]=0
        # 只要currentlabel和labelcounts.keys()存储的元素一致，就给以currentlabel为标签的项目赋值加1
        labelcounts[currentlabel]+=1
    # 定义香农熵的初始值=0
    ShannonEnt=0.0
    # 由于labelcounts是字典，所以可以用key访问字典的项目
    for key in labelcounts:
        # 计算值为浮点数
        # 用key指向的项目对应的数量比上总数
        prob=float(labelcounts[key])/numEntries
        # 香农熵就是频数乘以以2为底的频数的对数，然后还要取负值
        # 取负值是因为，频数小于1，所以对数小于0，一旦取负值就获得了正数
        ShannonEnt-=prob*log(prob,2)
    return ShannonEnt
dataset,labels=creatDataset()
ShannonEnt=calcShannonEnt(dataset)
print('ShannonEnt=',ShannonEnt)

整体代码非常简单，总结起来就是一个公式：

代码中需要注意的是：dataset是一个嵌套列表，labelcounts是一个字典。

【2.2】数据集划分

数据集划分，目的是找出某些关键特征后，将其删除。

# 定义一个嵌套列表
def creatDataset():
    # dataset是一个嵌套列表
    dataset=[
        [1,1,'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']
    ]
    # lables也是一个列表
    labels=['no surfacing','flippers']
    return dataset,labels

# splitdataset把一些列因素直接删除后输出
def splitdataset(dataset, axis, value):
    # 创建一个新的列表
    retdataset = []
    # 对于dataset的每一行
    for featvec in dataset:
        # if第axis列的数据刚好和value相等
        if featvec[axis] == value:
            # reducedfeature先获取索引从第0个到axis-1的元素，一共axis个
            reducedfeatvec = featvec[:axis]
            # reducedfeature继续获取索引从第axis+1开始的所有元素
            # reducedfeature后面再获取从第axis+2个开始一直到最后一个元素
            reducedfeatvec.extend(featvec[axis + 1:])
            # retdataset存储了reducedfeature
            # retdataset中刚好没有位置索引为axis的元素
            # retdataset中刚好没有第axis+1个元素
            retdataset.append(reducedfeatvec)
    return retdataset

dataset, labels = creatDataset()
retdataset = splitdataset(dataset, 0,1)
retdataset1 = splitdataset(dataset, 1,1)
retdataset2 = splitdataset(dataset, 1,0)
print("retdataset:", retdataset)
print("retdataset1:", retdataset1)
print("retdataset2:", retdataset2)

数据集划分只用了一个for循环加if判断就能实现，划分的原理是：对于每一行元素，如果指定列的元素和指定数据相等，就把这个相等的元素挑出去，然后把这行数据剩下的部分添加到一个新的列表里；如果指定列的元素和指定数据不相等，这一行数据会直接略过。

上述代码运行的效果是：

retdataset: [[1, 'yes'], [1, 'yes'], [0, 'no']]
retdataset1: [[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
retdataset2: [[1, 'no']]

【2.3】特征选择

数据集划分后，序言按照制定的特征作为依据，判断这个特征指向的样本对应的香农熵。

要想理解特征选择的意义，需要把前面的香农熵计算和数据集划分子函数都一起写进来：

from math import log  # 引入log()函数求对数

def creatDataset():
    # dataset是一个嵌套列表
    dataset=[
        [1,1,'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']
    ]
    # lables也是一个列表
    labels=['no surfacing','flippers']
    return dataset,labels

# calcShannonEnt是具体的香农熵求解函数
# 实际上calcShannonEnt是dataset最后一列的香农熵
def calcShannonEnt(dataset):
    # numEntries获得了dataset列表的行数
    numEntries = len(dataset)
    # labelcounts是一个空的字典
    labelcounts = {}
    # for函数的意义是，对于dataset里面的每一行都会执行循环操作
    for feature in dataset:
        # currentlabel 取到了feature的最后一个元素
        currentlabel = feature[-1]
        # 由于labelcounts是一个空字典，labelcounts.keys()在第一次运行的时候不会指向任何标签，所以会被直接添加
        # currentlabel是每一行dataset的最后一列，也就是最后一个元素
        # if函数实际上进行了同类项合并工作
        if currentlabel not in labelcounts.keys():
            # 给以currentlabel为标签的项目赋值0
            labelcounts[currentlabel] = 0
        # 只要currentlabel和labelcounts.keys()存储的元素一致，就给以currentlabel为标签的项目赋值加1
        labelcounts[currentlabel] += 1
    # 定义香农熵的初始值=0
    ShannonEnt = 0.0
    # 由于labelcounts是字典，所以可以用key访问字典的项目
    for key in labelcounts:
        # 计算值为浮点数
        # 用key指向的项目对应的数量比上总数
        prob = float(labelcounts[key]) / numEntries
        # 香农熵就是频数乘以以2为底的频数的对数，然后还要取负值
        # 取负值是因为，频数小于1，所以对数小于0，一旦取负值就获得了正数
        ShannonEnt -= prob * log(prob, 2)
    return ShannonEnt

# splitdataset把一些列因素直接删除后输出
def splitdataset(dataset, axis, value):
    # 创建一个新的列表
    retdataset = []
    # 对于dataset的每一行
    for featvec in dataset:
        # if第axis列的数据刚好和value相等
        if featvec[axis] == value:
            # reducedfeature先获取索引从第0个到axis-1的元素，一共axis个
            reducedfeatvec = featvec[:axis]
            # reducedfeature继续获取索引从第axis+1开始的所有元素
            # reducedfeature后面再获取从第axis+2个开始一直到最后一个元素
            reducedfeatvec.extend(featvec[axis + 1:])
            # retdataset存储了reducedfeature
            # retdataset中刚好没有位置索引为axis的元素
            # retdataset中刚好没有第axis+1个元素
            retdataset.append(reducedfeatvec)
    return retdataset

# choosebestfeaturetosplit计算的香农熵对象元素是dataset最后一列对应的元素
def choosebestfeaturetosplit(dataset):
    # 对dataset第0行求长度，获得列数，然后再减去1
    numfeatures = len(dataset[0]) - 1
    # 调用函数calcShannonEnt获得dataset的香农熵
    baseentroy = calcShannonEnt(dataset)
    # 定义一个常数
    bestinfogain = 0.0
    # 定义一个常数
    bestfeature = -1
    # 对于numfeatures中的每一个数
    # numfeatures比dataset的列数少一个
    for i in range(numfeatures):
        # 对于每一行在dataset中的元素，按照列位置索引为i的形式提取
        # 每一行位置索引为i的元素赋值给featlist
        # 这个嵌套列表，因为for的存在，把dataset每一行和位置索引为i的元素赋值给featlist
        # featlist存储的元素数量和dataset的函数一致
        # featlist作为列表没有提前预定义，此处定义这个量和定义如何取值一起出现
        featlist = [example[i] for example in dataset]
        # set是一个内置函数，将featlist这个列表转化为集合
        # 集合具有合并同类项的作用，重复的元素只会保留一个
        uniquevals = set(featlist)
        # 定义一个常数
        newentropy = 0.0
        # 对于uniquevals中的每一个值
        # uniquevals执行过程中，相当于把整个dataset计算获得的uniquevals进行遍历
        # value是uniquevals中的具体元素，也是列位置索引为i的dataset取到的值
        for value in uniquevals:
            # 调用splitdataset对dataset进行子集划分
            # 子集划分的列数和获得uniquevals的列数一致，value是uniquevals的存储值
            # subdataset不会是空值
            subdataset = splitdataset(dataset, i, value)
            # 获取每一个元素的香农熵
            # 需要注意的是，在每一个i的取值范围内，都会执行subdataset操作
            # subdataset是按照列元素进行的集合划分
            # 这个prob实际上是针对列元素展开的，有多少列，就会有多少次prob计算
            # prob实际上代表的是subdataset行数和dataset行数的比例
            prob = len(subdataset) / float(len(dataset))
            # 更新香农熵
            # calcShannonEnt(subdataset)计算了subdataset的最后一列的香农熵
            # newtropy是prob这个比例和对应香农熵的乘积
            newentropy += prob * calcShannonEnt(subdataset)
        # 获得香农熵的变化量
        # baseentroy是dataset的香农熵
        # newtropy是第i列元素为特征进行集合划分之后，对新集合开展的香农熵计算和新集合数量比例的乘积
        infogain = baseentroy - newentropy
        # 如果变化量超过阈值
        if (infogain > bestinfogain):
            # 新变化=变化量
            bestinfogain = infogain
            # 给bestfeature赋值i
            bestfeature = i
    return bestfeature

dataset, labels = creatDataset()
ShannonEnt=calcShannonEnt(dataset)
print('ShannonEnt=',ShannonEnt)
bestfeature=choosebestfeaturetosplit(dataset)
print('bestfeature=',bestfeature)

但在前面理解的基础上，可以先记住两条原则：

1. 香农熵是以一行数据列表的最后一列为计算依据，开展的对数运算；
2. 数据计划分时，会把特征这个依据从一行数据列表中删除。

而为了理解特征选择子函数choosebestfeaturetosplit(dataset)，需要把这个函数分作三部分。

【2.3.1】准备部分

    # 对dataset第0行求长度，获得列数，然后再减去1
    numfeatures = len(dataset[0]) - 1
    # 调用函数calcShannonEnt获得dataset的香农熵
    baseentroy = calcShannonEnt(dataset)
    # 定义一个常数
    bestinfogain = 0.0
    # 定义一个常数
    bestfeature = -1

准备部分获得一些备用值：

numfeatures = len(dataset[0]) - 1，对应的是dataset列表的列数-1；

baseentroy = calcShannonEnt(dataset)，是对dataset计算香农熵；

bestinfogain = 0.0和bestfeature = -1都是直接赋值。

【2.3.2】特征值提取

# 对于numfeatures中的每一个数
    # numfeatures比dataset的列数少一个
    for i in range(numfeatures):
        # 对于每一行在dataset中的元素，按照列位置索引为i的形式提取
        # 每一行位置索引为i的元素赋值给featlist
        # 这个嵌套列表，因为for的存在，把dataset每一行和位置索引为i的元素赋值给featlist
        # featlist存储的元素数量和dataset的函数一致
        # featlist作为列表没有提前预定义，此处定义这个量和定义如何取值一起出现
        featlist = [example[i] for example in dataset]
        # set是一个内置函数，将featlist这个列表转化为集合
        # 集合具有合并同类项的作用，重复的元素只会保留一个
        uniquevals = set(featlist)
        # 定义一个常数
        newentropy = 0.0
        # 对于uniquevals中的每一个值
        # uniquevals执行过程中，相当于把整个dataset计算获得的uniquevals进行遍历
        # value是uniquevals中的具体元素，也是列位置索引为i的dataset取到的值

在特征值提取部分，featlist通过嵌套for循环来提取了特征，然后通过set函数做了合并同类型操作。

featlist本质上是对dataset的列数据进行了提取，然后再合并同类项。

注意newtropy在每列特征值获得后，初始值都是0.0。

【2.3.3】特征值香农熵

        for value in uniquevals:
            # 调用splitdataset对dataset进行子集划分
            # 子集划分的列数和获得uniquevals的列数一致，value是uniquevals的存储值
            # subdataset不会是空值
            subdataset = splitdataset(dataset, i, value)
            # 获取每一个元素的香农熵
            # 需要注意的是，在每一个i的取值范围内，都会执行subdataset操作
            # subdataset是按照列元素进行的集合划分
            # 这个prob实际上是针对列元素展开的，有多少列，就会有多少次prob计算
            # prob实际上代表的是subdataset行数和dataset行数的比例
            prob = len(subdataset) / float(len(dataset))
            # 更新香农熵
            # calcShannonEnt(subdataset)计算了subdataset的最后一列的香农熵
            # newtropy是prob这个比例和对应香农熵的乘积
            newentropy += prob * calcShannonEnt(subdataset)

在获得特征值之后，以每一个特征值为依据，对取得特征值的列进行数据集划分。

也就是在某列取得特征值，这一列的数据就会被提取出来参与数据集划分。

对于每一个特征值对应的数据集，都要依据最后一列元素计算香农熵，然后这个香农熵还要和每个数据集行数占整个dataset行数的比例相乘。实际上，每个数据集的行数就代表了这个特征值在dataset的第i列中出现的次数。

需要注意的是，newentropy需要把第i列获得的所有特征值对应的数据集的香农熵都算一遍再叠加在一起。

【2.3.4】特征值香农熵变化量

# 获得香农熵的变化量
        # baseentroy是dataset的香农熵
        # newtropy是第i列元素为特征进行集合划分之后，对新集合开展的香农熵计算和新集合数量比例的乘积
        infogain = baseentroy - newentropy

这一步相对来说比较简单，用整个数据集dataset的香农熵减去特征值数据集的香农熵，获得一个当前熵增益。

【2.3.5】最佳熵增益

        if (infogain > bestinfogain):
            # 新变化=变化量
            bestinfogain = infogain
            # 给bestfeature赋值i
            bestfeature = i

如果当前熵增益>最佳熵增益，就把当前熵增益赋值给最佳熵增益，记录此时特征值在dataset中的列数。

总体而言，对于最佳列数的选择，是对dataset除最后一列之外的每一列元素都进行特征值选择，再计算香农熵后做出的选择。

当它们偏离dataset香农熵越远，被选中的概率越大。

【2.4】多数表决

def majoritycnt(classlist):
    # classcount是一个空字典
    classcount = {}
    for vote in classlist:
        # classlist是一个外部导入的参数
        # 从if条件来看，classlist也是一个字典
        # 对于classlist字典里的每一个键
        if vote not in classcount.keys():
            # 如果classlist里的键和clssscount里的键不一样
            # classcount字典里的vote键赋值0
            classcount[vote] = 0
        # 如果classlist里的键和clssscount里的键一样
        # classcount字典里的vote键值+1
        classcount[vote] += 1
    # Python 3中字典的iteritems()方法已被items()方法取代
    sortedclasscount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedclasscount[0][0]

对于多数表决部分，相对比较简单，整体上是一个排序的目标。

整个函数的输入参数其实也是列表，需要计算出列表中有多少个键值，然后对键值进行从大到小的排序即可，整个函数只返回最大值。

【2.5】获得决策树

def creattree(dataset, labels):
    # 对dataset中的最后一列取值
    # classlist是一个列元素列表
    classlist = [example[-1] for example in dataset]
    # 修正判断条件的括号
    # classlist.count(classlist[0])获得的是classlist列元素的第一个元素出现的次数
    # len(classlist)是classlist的行数，等于dataset中样本的数量
    if classlist.count(classlist[0]) == len(classlist):
        return classlist[0]
    # dataset[0]代表的是列数，如果列数=1，就直接返回classlist代入majoritycnt()函数的值
    if len(dataset[0]) == 1:
        return majoritycnt(classlist)
    # bestfeat通过choosebestfeaturetosplit(dataset)函数取值
    bestfeat = choosebestfeaturetosplit(dataset)
    # bestfeatlabel通过labels[bestfeat]函数取值
    bestfeatlabel = labels[bestfeat]
    # mytree是一个空字典，字典的键为bestfeatlabel，键值暂时是一个空字典
    mytree = {bestfeatlabel: {}}
    # 从特征标签中删除bestfeature
    del (labels[bestfeat])
    # featvalues的取值是dataset中位置索引为bestfeat的行
    featvalues = [example[bestfeat] for example in dataset]
    # 合并同类项
    uniquevals = set(featvalues)
    # 对于每一项
    for value in uniquevals:
        # sublabels是一个lables的副本
        sublabels = labels[:]
        # 获得决策树
        mytree[bestfeatlabel][value] = creattree(splitdataset(dataset, bestfeat, value), sublabels)
    return mytree

获得决策树的部分相对复杂一些，下一篇文章对整体做结构分析，到时候详细说明。

此时的完整代码为：

import numpy as np
from math import log  # 引入log()函数求对数
import operator

# 定义一个嵌套列表
def creatDataset():
    # dataset是一个嵌套列表
    dataset = [
        [1, 1, 'yes'],
        [1, 1, 'yes'],
        [1, 0, 'no'],
        [0, 1, 'no'],
        [0, 1, 'no']
    ]
    # lables也是一个列表
    labels = ['no surfacing', 'flippers']
    return dataset, labels

# calcShannonEnt是具体的香农熵求解函数
def calcShannonEnt(dataset):
    # numEntries获得了dataset列表的行数
    numEntries = len(dataset)
    # labelcounts是一个空的字典
    labelcounts = {}
    # for函数的意义是，对于dataset里面的每一行都会执行循环操作
    for feature in dataset:
        # currentlabel 取到了feature的最后一个元素
        currentlabel = feature[-1]
        # 由于labelcounts是一个空字典，labelcounts.keys()在第一次运行的时候不会指向任何标签，所以会被直接添加
        # currentlabel是每一行dataset的最后一列，也就是最后一个元素
        # if函数实际上进行了同类项合并工作
        if currentlabel not in labelcounts.keys():
            # 给以currentlabel为标签的项目赋值0
            labelcounts[currentlabel] = 0
        # 只要currentlabel和labelcounts.keys()存储的元素一致，就给以currentlabel为标签的项目赋值加1
        labelcounts[currentlabel] += 1
    # 定义香农熵的初始值=0
    ShannonEnt = 0.0
    # 由于labelcounts是字典，所以可以用key访问字典的项目
    for key in labelcounts:
        # 计算值为浮点数
        # 用key指向的项目对应的数量比上总数
        prob = float(labelcounts[key]) / numEntries
        # 香农熵就是频数乘以以2为底的频数的对数，然后还要取负值
        # 取负值是因为，频数小于1，所以对数小于0，一旦取负值就获得了正数
        ShannonEnt -= prob * log(prob, 2)
    return ShannonEnt

dataset, labels = creatDataset()
ShannonEnt = calcShannonEnt(dataset)
print('ShannonEnt=', ShannonEnt)

# splitdataset把一些列因素直接删除后输出
def splitdataset(dataset, axis, value):
    # 创建一个新的列表
    retdataset = []
    # 对于dataset的每一行
    for featvec in dataset:
        # if第axis列的数据刚好和value相等
        if featvec[axis] == value:
            # reducedfeature先获取索引从第0个到axis-1的元素，一共axis个
            reducedfeatvec = featvec[:axis]
            # reducedfeature继续获取索引从第axis+1开始的所有元素
            # reducedfeature后面再获取从第axis+2个开始一直到最后一个元素
            reducedfeatvec.extend(featvec[axis + 1:])
            # retdataset存储了reducedfeature
            # retdataset中刚好没有位置索引为axis的元素
            retdataset.append(reducedfeatvec)
    return retdataset

def choosebestfeaturetosplit(dataset):
    # 对dataset第0行求长度，获得列数，然后再减去1
    numfeatures = len(dataset[0]) - 1
    # 调用函数calcShannonEnt获得dataset的香农熵
    baseentroy = calcShannonEnt(dataset)
    # 定义一个常数
    bestinfogain = 0.0
    # 定义一个常数
    bestfeature = -1
    # 对于numfeatures中的每一个数
    # numfeatures比dataset的列数少一个
    for i in range(numfeatures):
        # 对于每一个在dataset中的元素，按照位置索引为i的形式提取
        featlist = [example[i] for example in dataset]
        # set是一个内置函数，将featlist这个列表转化为集合
        # 集合具有合并同类项的作用，重复的元素只会保留一个
        uniquevals = set(featlist)
        # 定义一个常数
        newentropy = 0.0
        # 对于uniquevals中的每一个值
        for value in uniquevals:
            # 调用splitdataset进行子集划分
            subdataset = splitdataset(dataset, i, value)
            # 获取每一个元素的香农熵
            prob = len(subdataset) / float(len(dataset))
            # 更新香农熵
            newentropy += prob * calcShannonEnt(subdataset)
        # 获得香农熵的变化量
        infogain = baseentroy - newentropy
        # 如果变化量查过阈值
        if (infogain > bestinfogain):
            # 新变化=变化量
            bestinfogain = infogain
            # 给bestfeature赋值i
            bestfeature = i
    return bestfeature

def majoritycnt(classlist):
    # classcount是一个空字典
    classcount = {}
    for vote in classlist:
        # classlist是一个外部导入的参数
        # 从if条件来看，classlist也是一个字典
        # 对于classlist字典里的每一个键
        if vote not in classcount.keys():
            # 如果classlist里的键和clssscount里的键不一样
            # classcount字典里的vote键赋值0
            classcount[vote] = 0
        # 如果classlist里的键和clssscount里的键一样
        # classcount字典里的vote键值+1
        classcount[vote] += 1
    # Python 3中字典的iteritems()方法已被items()方法取代
    sortedclasscount = sorted(classcount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedclasscount[0][0]

def creattree(dataset, labels):
    # 对dataset中的最后一列取值
    # classlist是一个列元素列表
    classlist = [example[-1] for example in dataset]
    # 修正判断条件的括号
    # classlist.count(classlist[0])获得的是classlist列元素的第一个元素出现的次数
    # len(classlist)是classlist的行数，等于dataset中样本的数量
    if classlist.count(classlist[0]) == len(classlist):
        return classlist[0]
    # dataset[0]代表的是列数，如果列数=1，就直接返回classlist代入majoritycnt()函数的值
    if len(dataset[0]) == 1:
        return majoritycnt(classlist)
    # bestfeat通过choosebestfeaturetosplit(dataset)函数取值
    bestfeat = choosebestfeaturetosplit(dataset)
    # bestfeatlabel通过labels[bestfeat]函数取值
    bestfeatlabel = labels[bestfeat]
    # mytree是一个空字典，字典的键为bestfeatlabel，键值暂时是一个空字典
    mytree = {bestfeatlabel: {}}
    # 从特征标签中删除bestfeature
    del (labels[bestfeat])
    # featvalues的取值是dataset中位置索引为bestfeat的行
    featvalues = [example[bestfeat] for example in dataset]
    # 合并同类项
    uniquevals = set(featvalues)
    # 对于每一项
    for value in uniquevals:
        # sublabels是一个lables的副本
        sublabels = labels[:]
        # 获得决策树
        mytree[bestfeatlabel][value] = creattree(splitdataset(dataset, bestfeat, value), sublabels)
    return mytree

# 测试代码
dataset, labels = creatDataset()
tree = creattree(dataset, labels.copy())
print("决策树:", tree)

【3】总结

学习了决策树的基础知识。