机器学习 决策树

算法原理

决策树模型是一种描述对实例进行分类的树形结构。其由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性（features），叶结点表示一个类（labels）。
用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。
决策树模型可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。

决策树场景

信息熵

熵（entropy）：熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。信息论（information theory）中的熵（香农熵）：是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。信息增益（information gain）：在划分数据集前后信息发生的变化称为信息增益。

如何构造一个决策树？
我们使用 createBranch() 方法，如下所示：

def createBranch():
‘’’
此处运用了迭代的思想。
‘’’
检测数据集中的所有数据的分类标签是否相同:
If so return 类标签
Else:
寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
划分数据集
创建分支节点
for 每个划分的子集
调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
return 分支节点

项目案例1：判定鱼类和非鱼类

项目概述

根据以下两个特征，将动物分成两类：鱼类和非鱼类。

1. 不浮出水面是否可以生存
2. 是否有脚蹼

开发流程

Step1: 收集数据

Step2: 准备数据

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

Step3: 分析数据
可以使用任何方法，构造树完成之后，我们可以将树画出来。
计算给定数据集的香农熵的函数如下：

from math import log

def calcShannonEnt(dataSet):
    '''
    概率计算就是计算数据出现的频率
    第一步：统计总体数据数
    第二步：求出每个标签出现次数，这里需要用到字典的映射关系
    第三步：遍历求出香农熵

    熵越高，则混合额数据也就越多，数据的混乱程度也就越高
    :param dataSet:
    :return: shannonEnt
    '''
    numEntries = len(dataSet)       #计算数据集中实例总数
    labelCounts = {}        #创建一个字典 键值为数据标签
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0       #没有这个标签就拓展字典并将当前键值加入字典
        labelCounts[currentLabel] += 1      #统计键值出现的次数
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries       #计算对应标签出现的概率
        shannonEnt -= prob * log(prob,2)        #log后为底数
    return shannonEnt

按照给定特征划分数据集
将指定特征的特征值等于 value 的行剩下列作为子数据集。

def splitDataSet(dataSet,axis,value):
    '''

    :param dataSet:数据集
    :param axis: 列（特征所对应的列）
    :param value: 需要返回的特征的值
    :return: index列为value的数据集【数据分离后要删除index列】
    '''
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

选择最好的数据集划分方式：

def chooseBestFeatureToSplit(dataSet):
    """
    chooseBestFeatureToSplit(选择最好的特征)
    Args:
        dataSet 数据集
    Returns:
        bestFeature 最优的特征列
    """
    # 求第一行有多少列的 Feature, 最后一列是label列
    numFeatures = len(dataSet[0]) - 1
    # 数据集的原始信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # 最优的信息增益值, 和最优的Featurn编号
    bestInfoGain, bestFeature = 0.0, -1
    # iterate over all the features
    for i in range(numFeatures):
        # 获取对应的feature下的所有数据
        featList = [example[i] for example in dataSet]
        # 获取剔重后的集合，使用set对list数据进行去重
        uniqueVals = set(featList)
        # 创建一个临时的信息熵
        newEntropy = 0.0
        # 遍历某一列的value集合，计算该列的信息熵
        # 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 计算概率
            prob = len(subDataSet) / float(len(dataSet))
            # 计算条件熵
            newEntropy += prob * calcShannonEnt(subDataSet)
        # gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值
        # 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。
        infoGain = baseEntropy - newEntropy
        print('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy)
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

Step4: 训练算法
构造树的数据结构，创建树的函数代码如下：

import operator

def majorityCnt(classList):
    """
    majorityCnt(选择出现次数最多的一个结果)
    Args:
        classList label列的集合
    Returns:
        bestFeature 最优的特征列
    """
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    # 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
    # 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
    # count() 函数是统计括号中的值在list中出现的次数
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
    # 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 选择最优的列，得到最优列对应的label含义
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
    # 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
    del (labels[bestFeat])
    # 取出最优列，然后它的branch做分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

储存决策树：

def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'wb')
    pickle.dump(inputTree, fw)
    fw.close()


def loadTree(filename):
    import pickle
    fr = open(filename, 'rb')
    return pickle.load(fr)

代码测试

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    tree = createTree(dataSet, labels)
    print(tree)

# infoGain= 0.4199730940219749 bestFeature= 0 0.9709505944546686 0.5509775004326937
# infoGain= 0.17095059445466854 bestFeature= 1 0.9709505944546686 0.8
# infoGain= 0.9182958340544896 bestFeature= 0 0.9182958340544896 0.0
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

    storeTree(tree, 'classifierStorage.pkl')
    tree = loadTree('classifierStorage.pkl')
    print(tree)

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

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

def classify(inputTree, featLabels, testVec):
    """
    classify(给输入的节点，进行分类)
    Args:
        inputTree  决策树模型
        featLabels Feature标签对应的名称
        testVec    测试输入的数据
    Returns:
        classLabel 分类的结果值，需要映射label才能知道名称
    """
    # 获取tree的根节点对于的key值
    firstStr = list(inputTree.keys())[0]
    # 通过key得到根节点对应的value
    secondDict = inputTree[firstStr]
    # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firstStr)
    # 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    print('+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat)
    # 判断分枝是否结束: 判断valueOfFeat是否是dict类型
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else:
        classLabel = valueOfFeat
    return classLabel

Step6: 使用算法

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    labelsCopy = labels[:]
    inputTree = createTree(dataSet, labels)
    result = classify(inputTree, labelsCopy, [1, 0])
    print(result)

# +++ no surfacing xxx {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}} --- 1 >>> {'flippers': {0: 'no', 1: 'yes'}}
# +++ flippers xxx {0: 'no', 1: 'yes'} --- 0 >>> no
# no