《机器学习实战》笔记之三——决策树的构造

第三章 决策树的构造

• 决策树简介
• 在数据集中度量一致性
• 使用递归构造决策树
• 使用Matplotlib绘制树形图

决策树主要优势：数据形式非常容易理解。

优点：

计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征。

缺点：

可能会产生过度匹配问题，即过拟合问题。

例子：

长方形：判断模块

椭圆形：终止模块

左右箭头：分支

3.1 决策树的构造

构造决策树：

步骤：选取起决定性左右的特征作为根节点，根据根节点特征的几个类别的值划分原始数据集为几个数据子集，如是否包含"曲棍球"这个特征，以其为根节点后，划分训练数据集为包含"曲棍球"这个训练数据集，和不包含。分别在两个子训练数据集上，再选取其他特征，不必再考虑这个特征。直到在训练子集全为一类。

如果所有的数据都是包含"曲棍球"，那么是否包含"曲棍球"这个特征是最好的特征了，因为这个特征能够很好的将数据全部分为一类，算法结束，否则算法需要继续寻找最好的特征。为此需要用上信息论里面的熵(entropy)的概念，并用基于熵的ID3算法划分数据。

伪代码函数createBranch():

Figure3-1: createBranch()函数

信息增益

划分数据集的最大原则: 将无序的数据变得更加有序。

信息增益(information gain): 在划分数据集之前之后信息发生的变化

熵(entropy): 信息的期望值，或者集合信息的度量方式。

信息定义：

如果待分类的事务可能划分在多个分类之中，则xi的信息定义为：

其中，p(xi)是选择该分类的概率。

信息期望值：

其中，n是分类的数目。

理解熵：

1. 若数据都为一类，那么H=-1*log2(1)=0，不用任何信息就能区分这个数据。
2. 如有一枚正反两面硬币，分为正面或者反面的概率都为0.5, H= -0.5log2(0.5) - 0.5log2(0.5) = 1, 需要一个单位比特信息区分是否是正面或者反面，也即0或者1。
3. 熵，代表信息的混乱度信息。其基本作用就是消除人们对事物的不确定性。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。
4. 具体地可参考《信息论》。
   

计算给定数据集的熵：

# -*- coding: utf-8 -*-
"""
Created on Thu Sep  3 22:59:01 2015

@author: shifeng
"""

from math import log

def calcShnnonEnt(dataSet):
    numEntries  = len(dataSet)       #数据集需要是每行一个训练样本，并且最后一列为训练labels
    labelCounts = {}
    for featVec in dataSet:
        currentLabel  = featVec[-1]                                      #对每个样本来说，取其label，即某行最后一个值
#        if currentLabel not in labelCounts.keys():
#            labelCounts[currentLabel] = 0
#        labelCounts[currentLabel] += 1
        labelCounts[currentLabel] = labelCounts.get(currentLabel, 0)+1   #此处就体现了字典的get()函数的威力，代替上面三行
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries   #选择该分类的概率值
        shannonEnt -= prob*log(prob, 2)             #计算信息熵的期望值
    return shannonEnt        
        
    
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
#myDat,labels = trees.createDataSet()

Figure3-2: 计算熵的函数测试

划分类标: 3个yes, 2个no, H=-0.6log2(0.6)-0.4log2(0.4) = 0.97 < 1, 需要一枚重量不均匀的硬币即可区分。而增加了一个类标maybe, 变成: 1个yes, 1个maybe, 3个no, H=-0.2log2(0.2)-0.2log2(0.2)-0.6log2(0.6)=1.37<2, 至少需要2枚硬币区分，增加一个类标，不确定性增加了，变得更“混乱”了。

划分数据集

按照给定特征划分数据集：

def splitDataSet(dataSet, axis, value):
    '''
    axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
    value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
    '''
    retDataSet = []             #需要新创建一个列表变量，因列表的参数是按照引用方式传递的
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

Figure3-3: 划分数据子集测试

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

def chooseBestFeatureToSplit(dataSet):
    '''
    数据集格式：
    1.由列表元素组成的列表，并且所有列元素都要具有相同数据长度。
    2.数据最后一列为label.
    如同createDataSet()中dataSet变量的数据集
    '''
    numFeatures = len(dataSet[0]) -1             #特征的个数，随便第一个实例的长度，去掉最后一个标签。
    baseEntropy = calcShnnonEnt(dataSet)
    bestInfoGain = 0.0                          #定义基尼指数
    bestFeature  = -1
    for i in range(numFeatures):                #对第i个特征处理，
        featList   = [example[i] for example in dataSet]
        uniqueVals = set(featList)              #第i个特征的属性值全放在集合里面，第0个特征有属性值0或者1，
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet  = splitDataSet(dataSet, i, value)        #对第i个特征，其值为value划分数据
            prob        = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcShnnonEnt(subDataSet)         #调用计算熵的公式。
        infoGain = baseEntropy - newEntropy                      #计算基尼指数。利用基尼指数得到熵最低的特征。
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature  = i
    return bestFeature

Figure3-4: 选择最好的特征

计算选择第0个特征作为划分特征：

Figure3-5: 计算最好的选择特征

递归构建决策树

工作原理：得到原始数据集，基于最好的属性值划分数据集，第一次划分后，再次划分数据。因此可以递归处理数据集。

递归结束的条件：划分数据集所有属性，或者每个分支下的所有实例都具有相同的分类。

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们通常采用多数表决的方法决定该叶子节点的分类。

<span style="font-size:14px;">def splitDataSet(dataSet, axis, value):
    '''
    axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
    value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
    '''
    retDataSet = []             #需要新创建一个列表变量，因列表的参数是按照引用方式传递的
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)</span>

子功能模块构建好了后，将其组合起来，以得到我们需要的结果：树

<span style="font-size:14px;"># -*- coding: utf-8 -*-
"""
Created on Thu Sep  3 22:59:01 2015

@author: shifeng
"""
import operator
from math import log

def calcShnnonEnt(dataSet):
    numEntries  = len(dataSet)       #数据集需要是每行一个训练样本，并且最后一列为训练labels
    labelCounts = {}
    for featVec in dataSet:
        currentLabel  = featVec[-1]                                      #对每个样本来说，取其label，即某行最后一个值
#        if currentLabel not in labelCounts.keys():
#            labelCounts[currentLabel] = 0
#        labelCounts[currentLabel] += 1
        labelCounts[currentLabel] = labelCounts.get(currentLabel, 0)+1   #此处就体现了字典的get()函数的威力，代替上面三行
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries   #选择该分类的概率值
        shannonEnt -= prob*log(prob, 2)             #计算信息熵的期望值
    return shannonEnt        
        
    
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
#myDat,labels = trees.createDataSet()
    
def splitDataSet(dataSet, axis, value):
    '''
    axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
    value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
    '''
    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):
    '''
    数据集格式：
    1.由列表元素组成的列表，并且所有列元素都要具有相同数据长度。
    2.数据最后一列为label.
    如同createDataSet()中dataSet变量的数据集
    '''
    numFeatures = len(dataSet[0]) -1             #特征的个数，随便第一个实例的长度，去掉最后一个标签。
    baseEntropy = calcShnnonEnt(dataSet)
    bestInfoGain = 0.0                          #定义基尼指数
    bestFeature  = -1
    for i in range(numFeatures):                #对第i个特征处理，
        featList   = [example[i] for example in dataSet]
        uniqueVals = set(featList)              #第i个特征的属性值全放在集合里面，第0个特征有属性值0或者1，
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet  = splitDataSet(dataSet, i, value)        #对第i个特征，其值为value划分数据
            prob        = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcShnnonEnt(subDataSet)         #调用计算熵的公式。
        infoGain = baseEntropy - newEntropy                      #计算基尼指数。利用基尼指数得到熵最低的特征。
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature  = i
    return bestFeature
    
def majorityCnt(classList):             #classList为类标例表
    classCount = {}
    for vote in classList:
        classCount[vote] = classCount.get(vote,0)+1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
    
def createTree(dataSet, labels):                            #labels  = ["no surfacing","flippers"],其值为特征名
    classList = [example[-1] for example in dataSet]            #取dataSet每个实例的最后一个元素，也即label
    if classList.count(classList[0]) == len(classList):         #类别完全相同则停止划分，取第一个就行了，第一个的个数等于所有的个数
        return classList[0]
    if len(dataSet[0]) == 1:                                #遍历完所有特征时，返回label出现次数最多的
        return majorityCnt(classList)
    bestFeat      = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]                        #labels列表中包含了具体的属性值
    myTree        = {bestFeatLabel:{}}                      #关键所在
    del(labels[bestFeat])                                   #类标的某个特征被选择了后，就不必再考虑了
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        #递归调用createTree()函数，并且将返回的tree插入到myTree字典中，
        #利用最好的特征划分的子集作为新的dataSet传入到createTree()函数中。
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree    
        </span>

Figure3-6: 分类结果

由于我们需要得到一颗决策树，用字典这种数据结构再好不过，字典嵌套构成树的整个结构，如果字典的属性值为类标签，那么子节点就是叶子节点，如果字典的属性值为字典，那么子节点是另一个判断节点。

另外，多数表决的方法在多数情况下卤主也不确定是否好，还需继续探究。

3.2 在python中使用Matplotlib注解绘制树形图

这部分跟机器学习相关性不大，主要是熟悉python可视化包Matplotlib画图的功能，方便展示给他人。有兴趣可参考教材。

3.3 测试和存储分类器

这部分有个比较有用的是关于决策树的存储，用到了pickle模块序列化对象。

3.4 示例：使用决策树预测隐形眼睛类型

目标：通过决策树预测患者需要佩戴的隐形眼睛类型。

隐形眼睛数据集：

Figure3-7: lenses data

测试结果：

Figure3-8: lenses数据测试结果

3.5 小结

这里主要是采用ID3算法划分数据集，用递归的方法将数据集转化为决策树，并可用pickle模块存储决策树的结构。

ID3算法无法处理直接数值型数据，需要将其化为标量型数值。

决策树最大的缺点在于过拟合问题。在构建树的时候，其能够完全匹配实验数据，但是这并不是我们想要的，为此，可以删掉一些只增加了很少信息的节点，将其并入到其他叶子节点中，或者裁剪一些分支。具体决策树的很多问题也待整理。