决策树

本周学了一种非要重要也非常基础的核心分类算法——决策树。下面对决策树算法做一个总结：）

决策树（decision tree）是一种基本的分类与回归方法。这里主要总结用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤：特征选择、决策树的生成和决策的修建。生成决策树后就可以根据它来进行分类了。这些决策树的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。（其实这几种算法的主要区别就在于采用什么方式选择最合适的属性作为分裂准则，也叫属性选择度量），这里介绍的是基础的ID3算法，采用的是信息增益最大的属性进行分裂。

选择根属性，就好比下面一堆数据，构成的决策树

决策树
这里看起来挺正常，但是如果给我们一堆数据，我们怎么知道根属性需要从“年龄”这里字段来进行分裂呢？这就牵涉到一个信息增益的问题，也就是我希望我选择的这个属性可以获得最大信息增益，也就是根据这个属性分出来的两个子树中纯度比较好，这么说吧，我选择了“年龄”字段，如果年龄过大的直接就Pass了，这就说明这个属性很给力，仅凭这一点就可以判断是否需要去见面。那么这个最大信息增益需要怎么来度量呢？就需要使用一个叫做香农信息熵的概念。
香农是信息论的奠基人，大牛，学会信息论和数字信号处理的都知道。信息熵的计算采用如下公式：
信息熵
pi是D中任意属性元组属于类Ci的概率，并用|Ci|/|D|来估计。具体来说，如果数据集中有5个人愿意见面，有5个人不想见面，那么总人数就是10个人，这里的pi就等于5/10=0.5，信息熵就等于-0.5log0.5+(-0.5log0.5)。注意：这里是根据最终分类结果来计算的总的信息熵。
下面计算属性“年龄”带来的信息熵：

其中，|Dj|/|D|充当权重值，在这里就是年龄属性的权重，假设年龄大于35岁的有4个人，小于等于35岁的有6个人，先看年龄大于35岁的4个人，这里|Dj|/|D|=4/10=0.4，Info(Dj)就是在年龄35以上这些人里面有多少人获得了见面机会的，显然机会为零，因此Info(Dj)=0；继续来看年龄小于等于35岁的6个人，假设有3个人获得见面机会，那么|Dj|/|D|=6/10=0.6,pj=3/6=0.5,所以Info(Dj)=0+(-0.5log0.5)=0.5，因此最终“年龄”属性的信息增益是0.60.5=0.3。
属性“年龄”的信息增益就是：Gain(年龄)=Info-Info(年龄)=1-0.3=0.7
同样可以求得其他几个属性的信息增益，选择信息增益最大的属性作为分裂的属性，这就是ID3算法。

项目案例和实际代码编写

根据以下 2 个特征，将动物分成两类：鱼类和非鱼类。
特征：
不浮出水面是否可以生存
是否有脚蹼

1.选择根属性（也就是分裂的属性）

首先，我们需要把数据读入到一个数据集中去：

from math import log

original_labels = []

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

其实，根据我们上面的算法思路计算数据集的整体信息熵，这里可以进行测试一下

def calcShannonEnt(dataSet):
    # 求list的长度，表示计算参与训练的数据量
    numEntries = len(dataSet)
    # 计算分类标签label出现的次数
    labelCounts = {}

    for featVec in dataSet:
        # 每行的最后一列元素就是分类标签
        currentLabel = featVec[-1]
        # 更新标签的计数
        labelCounts[currentLabel] = labelCounts.get(currentLabel,0)+1

    # 根据标签的占比求出香农熵
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # 计算香农熵，以2为底，求对数
        shannonEnt -= prob*log(prob,2)
    return shannonEnt

dataSet,labels = createDataSet()
shannonEnt = calcShannonEnt(dataSet)
print("shannonEnt = %s"%shannonEnt)

得到：shannonEnt = 0.9709505944546686，也就是这个数据集的整体信息熵为0.97*****
获取数据子集，也就是某一属性等于某一个具体值时的数据子集，计算某一属性的信息熵时需要用到：

'''将dataSet数据集分开，遍历dataSet的行，当index列的值等于value时，把这行数据划分进我们新的数据集中，同时要把index列的元素去掉'''
def splitDataSet(dataSet,index,value):
    retDataSet = []
    for featVect in dataSet:
        if(featVect[index]==value):
            reducedFeatVect = featVect[:index]
            reducedFeatVect.extend(featVect[index+1:]) # 其实这里就是去掉了index列的数据，并把这一行单独留下来放到新的数据集中去了
            retDataSet.append(reducedFeatVect)
            #retDataSet.append(featVect) # 其实这里这样就可以了，没必要非要把比较的index列去掉
    return retDataSet

temp = splitDataSet(dataSet,2,'yes')
print(temp)

接下来，分别计算各个属性的信息熵，选择分裂属性

'''选择最好的数据划分方式划分数据'''
def chooseBestFeatureToSplit(dataSet):
    # 一共有多少列属性，最后一列是标签列所以要减掉
    numberOfFeatures = len(dataSet[0])-1
    # 数据集的原始信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # 初始化信息增益和最佳的属性列
    bestInfoGain,bestFeature = 0.0,-1
    # 遍历所有的属性
    for i in range(numberOfFeatures):
        # 获取该属性的所有数据
        featureList = [example[i] for example in dataSet] # 这个写法是遍历数据集中的每一行，把其中的第i个数据取出来组合成一个列表
        featureList = set(featureList) # 属性值去重
        newEntropy = 0.0 # 新的临时的信息熵
        # 根据属性值进行分割数据集
        for value in featureList:
            subData = splitDataSet(dataSet,i,value)
            prob = len(subData)/float(len(dataSet)) # 计算该属性值等于value的数据在总数据集中的比例
            newEntropy += prob*calcShannonEnt(subData) # 计算新的信息熵
        infoGain = baseEntropy - newEntropy # 计算出该属性的信息增益
        if(infoGain>bestInfoGain): # 如果信息增益变大了，就把当前属性作为最好的划分数据，继续遍历
            bestInfoGain = infoGain
            bestFeature = i
    # 返回最好的划分属性
    return bestFeature

bestF = chooseBestFeatureToSplit(dataSet)
print("The best feature is %s"%bestF)

2.构造决策树

有了最好的分裂属性后，我们就可以构建决策树了：

# 创建决策树
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet] # 类别列表，这是一种快速获取某列属性值的方法
    # 第一个停止条件：如果所有标签分类都相同则返回
    if classList.count(classList[0])==len(classList):
        return classList[0]
    # 第二个停止条件：如果数据集只有一列，那么最初出现label最多的一类作为结果返回
    if(len(dataSet[0])==1):
        return majorityCnt(classList)
    # 选择最优的分裂的类
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 获取label的名称
    bestFeatLabel = labels[bestFeat]
    # 初始化树,树采用字典存储
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat]) # 从属性列表中删除这个属性，因为已经分类了，接下来要从剩下的这些属性中进行子树的构建了
    # 取出最优列，然后他的分支做分类，如“年龄”属性取出后，剩下的子树就是>35岁的和<=35岁的
    featValues = [example[bestFeat] for example in dataSet]
    uniqueValues = set(featValues) # 去重
    for value in uniqueValues:
        # 剩余的标签label
        subLabels = labels[:]
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

注意，决策树的物理存储就是一个字典，以键值对形式存储数据。

3.使用决策树进行分类

分类函数

# 使用决策树进行分类
def classify(inputTree,featLabels,testVec):
    # 获取树根节点对于Key的值
    firstStr = list(inputTree.keys())[0]
    # 获取对应的值，其实也是一个字典
    secondDict = inputTree[firstStr]
    # 获取根节点对应在标签中的序号
    featIndex = featLabels.index(firstStr)
    # 获取测试数据集中该标签的值
    key = testVec[featIndex]
    # 获取值，看看有没有子树
    valueOfFeat = secondDict[key]
    print("+++"+firstStr+"xxx"+secondDict+"---"+key+">>>"+valueOfFeat)
    # 如果还有子树就继续往下分类
    if(isinstance(valueOfFeat,dict)):
        classLabel = classify(valueOfFeat,featLabels,testVec)
    # 否则就把标签值作为分类标签
    else:
        classLabel = valueOfFeat
    return classLabel

4.使用决策树进行分类

dataSet,labels = createDataSet()
for label in labels:
    # 这里用到original_labels就是因为labels调用label方法后会被删除，无法在classify方法中使用，因此需要另外使用一个变量保存原始label
    original_labels.append(label) 
inputTree = createTree(dataSet,labels)
print("决策树------->%s"%inputTree)
testVec = [0,0]
lb = classify(inputTree,original_labels,testVec)
print("lb=%s"%lb)

我们可以看到最终输出为：

The best feature is 0
决策树------->{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
lb=no

可以看到决策树，最后就是一个字典。最好的分类就是属性'no surfacing'。[0,0]这个测试向量得到的分类是no，这个也符合我们的常识，一个动物既不能在水下生存也没有脚蹼，那就肯定不是鱼类了。