机器学习——决策树

2021/10/28 23:15:50

编程Tag： key 节点 dataset 学习 No 机器决策树 plotTree myTree

本文主要是介绍机器学习——决策树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。

算法结构

  决策树在逻辑上以树的形式存在，包含根节点、内部结点和叶节点。
根节点：包含数据集中的所有数据的集合
        内部节点：每个内部节点为一个判断条件，并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果，对应的数据的集合将分到两个或多个子节点中。
        叶节点：最终的类别。

一般流程

通过任意方法收集数据
数据离散化
检查完成后的构造树是否符合预期
构成树的数据结构
使用经验书计算错误率
使用算法

信息增益

在建立决策树之前，我们需要先学习一个非常重要的概念，那就是信息熵。

一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号xi的信息定义为：

$l(x_{i})=-log_{2}p(x_{i})$

$p(x_{i})$ 为选择该分类的概率

为了计算熵，需要计算所有类别的可能值包含的信息期望值，通过以下公式得到

$H=-\sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})$

n为分类数目，随机数目的不确定性随熵增大而增大

代码实现

from math import log

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet: #the the number of unique elements and their occurance
        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 base 2
    return shannonEnt

划分数据集

分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确的划分了数据集。得到每个特征划分数据集的结果计算出的信息熵后，我们将遍历整个数据集，循环计算香农熵和splitdataset（）函数以找到最好的特征划分方式

代码实现

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 chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1      
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)       
        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

决策树的构建

此时我们已经有了构造决策树算法所需的主要子功能模块，其功能原理为：将原始数据集基于最好的属性值划分，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。在第一次划分后，数据向下传递到分支的下一个节点上，在这个节点我们可以再次划分数据，因此可采用递归的方式处理数据集。

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): 
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]       
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

信息增益率

在信息增益中，若把“编号”也作为一个候选划分属性，则其信息增益一般远大于其他属性。显然，这样的决策树不具有泛化能力，无法对新样本进行有效预测

此时可用信息增益率来解决这类问题

$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

信息增益比 = 惩罚参数 * 信息增益

其中

$IV(a)=-\sum_{v=1}^{V}\frac{\left | D^{v} \right |}{\left | D \right |}log_{2}\frac{\left | D^v \right |}{\left | D \right |}$

称为属性a的“固有值” [Quinlan, 1993]，属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大

信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题，可以先找出信息增益在平均值以上的属性，在从中选择信息增益率最高的。

基尼指数

分类问题中，假设D有K个类，样本点属于第k类的概率为 $p_{k}$ , 则概率分布的基尼值定义为：

$Gini(D)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^{2}$

Gini(D)越小，数据集D的纯度越高；

给定数据集D，属性a的基尼指数定义为：

$Gini_{index}(D,a)=\sum_{v=1}^{V}\frac{\left | D^v \right |}{D}Gini(D^v)$

在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最有划分属性。

用Matplotlib注解绘制树形图

Matplotlib提供了一个注解工具：annotations，可以在数据图形上添加文本工具。
Matplotlib实际上是一套面向对象的绘图库，它所绘制的图表中的每个绘图元素，例如线条Line2D、文字Text、刻度等在内存中都有一个对象与之对应。

import matplotlib.pyplot as plt

decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    # annotate是关于一个数据点的文本  
    # nodeTxt为要显示的文本，centerPt为文本的中心点，箭头所在的点，parentPt为指向文本的点 
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
             xytext=centerPt, textcoords='axes fraction',
             va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )

def createPlot():     
    fig = plt.figure(1,facecolor='white') # 定义一个画布，背景为白色
    fig.clf() # 把画布清空
    # createPlot.ax1为全局变量，绘制图像的句柄，subplot为定义了一个绘图，
    #111表示figure中的图有1行1列，即1个，最后的1代表第一个图 
    # frameon表示是否绘制坐标轴矩形 
    createPlot.ax1 = plt.subplot(111,frameon=False) 
    plotNode('a decision node',(0.5,0.1),(0.1,0.5),decisionNode) 
    plotNode('a leaf node',(0.8,0.1),(0.3,0.8),leafNode) 
    plt.show()

构造注解树

      树在python中用嵌套字典存储
        例：>>> myTree
                {‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}
        绘制一颗完整的树需要技巧，虽然我们有坐标，但是如何放置所有的树节点却是个问题。所以我们需要知道有多少个叶节点来确定x轴长度；还需要知道有多少层来确定y轴的高度。

def getNumLeafs(myTree): #获得叶节点数目
    numLeafs = 0
    firstStr = myTree.keys()[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict': #测试该节点value是否是dict，若不是则该节点为叶节点
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs

def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = myTree.keys()[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth: maxDepth = thisDepth
    return maxDepth

测试中可以用函数retrieveTree()来输出预储存的树信息

def retrieveTree(i):
    listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
                  {'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
                  ]
    return listOfTrees[i]

def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree) 
    depth = getTreeDepth(myTree)
    firstStr = myTree.keys()[0]    
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            plotTree(secondDict[key],cntrPt,str(key))        
        else:  
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD


def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)  
   
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
    plotTree(inTree, (0.5,1.0), '')
    plt.show()

最终实现树的创建