构建决策树的思想:

需要解决的第一个问题就是当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。那么如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内

第一步:数据集的确定

海洋生物数据

从该图，可以看到有5个海洋动物，特征包括:不浮出水面是否可以生存，以及是否有脚蹼。标签呢，就是判断这些动物是否是鱼类，即label:鱼类和非鱼类

def createDataSet():
    dataSet = [
              [1, 1, 'yes'],
              [1, 1, 'yes'],
              [1, 0, 'no'],
              [0, 1, 'no'],
              [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

第二步:信息增益和香农熵

现在有了数据和标签，怎么判断哪种特征在划分数据分类时起决定性作用，这里采用ID3算法划分数据集。这里不得不提的一个概念就是信息增益，(PS:不用感到头大，这种专业一般的字眼确实让人看着就烦)只要知道信息增益的意思就可以啦，信息增益呢就是说在划分数据集之前之后信息发生的变化。如果知道如何计算信息增益，就可以计算每个特征值划分数据集获得的信息增益，这样获得信息增益最高的特征就是最好的选择，所有我们必须学习如何计算信息增益。和信息增益息息相关的就是熵(PS:更头疼的词，不管它是干嘛的，只要只要它对我们的作用就可以了)，熵就是信息的期望值(PS:是不是没有那么神秘了)

信息定义

信息期望值

import numpy as np
# 程序清单3-1 计算给定数据集的香农熵
from math import log

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)#计算行数，即数据集的总数
    labelCounts = {}#定义一个字典
    for featVec in dataSet:
        currentLabel = featVec[-1]#最后一列是键的值
        if currentLabel not in labelCounts.keys():#如果当前的标签不在我们定义的字典中
            labelCounts[currentLabel] = 0#标签字典值为0，即当前键值不存在
        labelCounts[currentLabel] += 1#否则，标签字典值加1，加入字典中
    shannonEnt = 0.0
    for key in labelCounts:#字典的值的遍历方式
        prob = float(labelCounts[key]) / numEntries#某分类的概率p(xi)
        shannonEnt -= prob * log(prob, 2)#计算熵的公式
    return shannonEnt

我相信有一半的代码大家是看得懂的，只是for循环中的东西有点抽象(PS:我和你们的感觉是一样的，所有我决定单独拎出来输出一下看看到底是什么难为住我了)，我们单独输出一下currentLabel，然后再输出labelCounts.keys()还有labelCounts[currentLabel]就可以了

测试代码

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)#计算行数，即数据集的总数
    labelCounts = {}#定义一个字典
    for featVec in dataSet:
        currentLabel = featVec[-1]#最后一列是标签即结果是鱼或者不是鱼
        print(currentLabel)#
        if currentLabel not in labelCounts.keys():#如果当前字典的值不在我们定义的字典中，则加入
            labelCounts[currentLabel] = 0#标签字典值为0，即当前键值不存在
        labelCounts[currentLabel] += 1#否则，标签字典值加1，加入字典中
    print(labelCounts.keys())
    print(labelCounts[currentLabel])
    shannonEnt = 0.0
    for key in labelCounts:#字典的值的遍历方式
        prob = float(labelCounts[key]) / numEntries#某分类的概率
        shannonEnt -= prob * log(prob, 2)#计算熵的公式
    return shannonEnt
myDat, labels = createDataSet()
print(calcShannonEnt(myDat))#计算信息熵

测试输出

yes
yes
no
no
no
dict_keys(['yes', 'no'])
3
0.9709505944546686

可以看出currentLabel即对应的就是是否是鱼的标签，if语句就是把yes和no选出来并记录yes和no的个数。所以labelCounts.keys()就是dict_keys(['yes', 'no'])，然后就是labelCounts[yes]=3,labelCounts[no]=2,然后就是计算概率和熵，搞定！！！

第三步:划分数据集

#按照给定特征划分数据集,三个参数:待划分的数据集，划分数据集的特征，特征的返回值
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis] 
            reducedFeatVec.extend(featVec[axis + 1 : ])
            retDataSet.append(reducedFeatVec)
    return retDataSet 

测试代码

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis] 
            print(reducedFeatVec)
            reducedFeatVec.extend(featVec[axis + 1 : ])
            print(reducedFeatVec)
            retDataSet.append(reducedFeatVec)
            print(reducedFeatVec)
    return retDataSet 
myDat, labels = createDataSet()
print(myDat)
print(splitDataSet(myDat, 1, 1))

输出

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

OK,这里涉及到几个小的知识点
1,python list的:使用

测试用例

list = [1, 1, 'yes']
print(list[:1])
print(list[2:])

测试

[1]
['yes']

说明list的:使用时半包状态，即不包括当前位置的数值
2,python extend()和append()

测试用例

list = [1, 1, 'yes']
list.extend([3])
print(list)
list.append([5,6,7])
print(list)

输出

[1, 1, 'yes', 3]
[1, 1, 'yes', 3, [5, 6, 7]]

OK，单独一个特征的划分我们都会了，现在让我们遍历整个数据集，循环计算香农熵和splitDataSet()函数，找出最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1#dataSet[0]第一行[1, 1, 'yes']
    baseEntropy = calcShannonEnt(dataSet)#计算香农熵
    bestInfoGain = 0.0; bestFeature = -1
    for i in np.arange(numFeatures):#遍历数据中所有特征
        featList = [example[i] for example in dataSet]#按列存入数据
        print(featList)
        uniqueVals = set(featList)#set集合{}去掉重复元素
        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

测试

myDat, labels = createDataSet()
print(chooseBestFeatureToSplit(myDat))

输出

[1, 1, 1, 0, 0]
[1, 1, 0, 1, 1]
0

代码运行结果告诉我们，第0个特征是最好的用于划分数据集的特征

递归构建决策树

目前我们已经得到原始数据集，并实现基于最好的属性值划分数据集。但是由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。故采用递归的原则处理数据集
那么递归结束的条件是:程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类
现在还有一个问题就是即使数据集处理了所有属性，类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类

# 如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，
# 在这种情况下，我们通常会采用 多数表决的方法决定该叶子节点的分类
def majorityCnt(classList):
    classCount = {}#定义一个字典
    for vote in classList:
        if vote not in classCount.keys():#存储字典中的不同值并计算不同值的个数
            classCount[vote] = 0
        classCount[vote] += 1
    
    newvalue = -1
    for key in classCount:#找出最大值
        if newvalue < classCount[key]:
            newkey = key
            newvalue = classCount[key]
    return newkey

# 程序清单 3-4 创建树的函数代码
def createTree(dataSet, labels): # 两个输入参数-- 数据集， 标签列表
    classList = [example[-1] for example in dataSet]#把标签保存到classList中
    if classList.count(classList[0]) == len(classList):
        return classList[0]   # 如果类别完全相同则停止继续划分
    
    if len(dataSet[0]) == 1:  # 遍历完所有特征时返回出现次数最多的类别
        return majorityCnt(classList) 
    #字典类型存储树
    bestFeat = chooseBestFeatureToSplit(dataSet)#找出最好的用于划分的特征
    bestFeatLabel = labels[bestFeat]#'no surfacing
    myTree = {bestFeatLabel:{}}#用来存储树信息
    del(labels[bestFeat])
    
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]  # 这行代码复制了类标签，并将其存储在新列表变量subLabels中
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) # 字典的嵌套
    return myTree

测试代码

myDat, labels = createDataSet()
myTree = createTree(myDat, labels)
print(myTree)

输出

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

变量myTreee包含了很多代表数结构的嵌套字典，从左边开始，第一个关键字no surfacing是第一个划分数据集的特征名称，该关键字的值也是另一个数据字典。第二个关键字是no surfacing特征划分的数据集，这些关键字的值是no surfacing节点的子节点。这些值可能是类标签，也可能是另一个数据字典。如果值是类标签，则该子节点是叶子节点；如果是另一个数据字典，则子节点是一个判断节点，这种格式结构不断重复就构成了整棵树

测试算法:使用决策树执行分类

依靠训练数据构造了决策树之后，可以将它用于实际数据的分类，在执行数据分类时需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子节点；最后将测试数据定义为叶子节点所属的类型

# 程序清单3-8 使用决策树的分类函数
def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0]#字典中的键
    print(inputTree.keys(),44)
    print(firstStr)
    secondDict = inputTree[firstStr]#no surfacing对应的值
    featIndex = featLabels.index(firstStr)#在featLabels中索引到no surfacing的位置
    print('1 ',featIndex)
    for key in secondDict.keys():#
        if testVec[featIndex] == key:#若我们测试的值和树的值一样，说明找到对的位置
            if isinstance(secondDict[key], dict):#若该值是字典类型，继续找
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:#不然就找到了
                classLabel = secondDict[key]
    return classLabel

测试代码

# 程序清单3-8 使用决策树的分类函数
def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0]#字典中的键
    #print(inputTree.keys())
    #print(firstStr)
    secondDict = inputTree[firstStr]#no surfacing对应的值
    featIndex = featLabels.index(firstStr)#在featLabels中索引到no surfacing的位置
    #print('1 ',featIndex)
    for key in secondDict.keys():#
        if testVec[featIndex] == key:#若我们测试的值和树的值一样，说明找到对的位置
            if isinstance(secondDict[key], dict):#若该值是字典类型，继续找
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:#不然就找到了
                classLabel = secondDict[key]
    return classLabel

中间注释的代码可以拿去测试

测试代码

myDat, labels = createDataSet()
print(labels)
print(myTree)
print(classify(myTree, labels, [1, 1]))

输出

['no surfacing', 'flippers']
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
yes

使用算法:决策树的存储

我们使用python模块pickle序列化对象，就可以在磁盘上保存并在需要的时候读取出来。

# 程序清单 3-9 使用pickle模块存储决策树
import pickle
def storeTree(inputTree, filename):
    fw = open(filename, 'wb')
    pickle.dump(inputTree, fw)#存储
    fw.close()
    
def grabTree(filename):
    fr = open(filename, 'rb')
    return pickle.load(fr)#读取

测试数据

myDat, labels = createDataSet()
#print(labels)
myTree = createTree(myDat, labels)

storeTree(myTree, r'保存路径XXX\a.txt')#先存储

print(grabTree(r'保存路径XXX\a.txt'))#后读取

输出

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

使用决策树预测隐形眼镜类型

数据集样本类型

fr = open(lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
# print(lenses)
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = createTree(lenses, lensesLabels)
print(lensesTree)

输出

{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'young': 'hard', 'presbyopic': 'no lenses'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'young': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}}}}}}}

源码
scikit-learn决策树算法讲解
scikit-learn官网介绍决策树算法