机器学习之决策树（Decision Tree）模型

机器学习之决策树

• 1、决策树模型介绍
• 2、决策树数学原理
• 3、算法及Python实现
• 4、小结

1、决策树模型介绍

定义：（决策树） 分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子节点对应着改特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

2、决策树数学原理

特征选择过程在于选取对于训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比。
在信息论和概率统计中，熵（entropy）是表示随机变量不确定性的变量，设X是一个取有限个值的离散随机变量，其概率分布为

P(X=xi)=pi,i=1,2,⋯,n$P(X=x_i)=p_i,i=1,2,\cdots ,n$
则随机变量X的熵的定义为
H(X)=−∑ni=1pilogpi$H(X)=-\sum _{i=1}^n{p}_{i}log{p}_i$
当随机变量只取两个值，例如1,0时，即X的分布为
P(X=1)=p,P(X=0)=1−p,0≤p≤1$P(X=1)=p,P(X=0)=1-p,0\le p\le 1$
熵为
H(p)=−plog2p−(1−p)log2(1−p)$H(p)=-plo{g}_{2}p-(1-p)lo{g}_2(1-p)$
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性
H(Y|X)=∑ni=1piH(Y|X=xi)$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$
这里，pi=P(X=xi),i=1,2,⋯,n.$p_i=P(X=x_i),i=1,2,\cdots ,n.$
信息增益：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件D的经验条件熵H(D|A)之差，即
g(D,A)=H(D)−H(D|A)$g(D,A)=H(D)-H(D|A)$

3、决策树生成算法及Python实现

（ID3算法）
输入：训练数据集D，特征集A，阀值ε$\epsilon$；
输出：决策树T。
（1）若D中所有实例属于同一类Ck$C_k$，则T为单结点树，并将类Ck$C_k$作为该结点的类标记，返回T；
（2）若A=∅$\mathrm{\varnothing }$，则T为单结点树，并将D中实例数最大的类Ck$C_k$作为该结点的类标记，返回T
（3）否则，按照上面公式计算A中各特征对D的信息增益，选择信息增益最大的特征Ag$A_g$；
（4）如果Ag$A_g$的信息增益小于阀值ε$\epsilon$，则置T为单结点树，并将D中实例数量最大的类Ck$C_k$作为该结点的类标记，返回T；
（5）否则，对Ag$A_g$的每一个可能值ai$a_i$，依Ag=ai$A_g=a_i$将D分割为若干非空自己Di$D_i$，将Di$D_i$中实例数量最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
（6）对第i个子结点，以Di$D_i$为训练集，以A-{Ag$A_g$}为特征集，递归地调用步(1)~步(5)，得到子树Ti$T_i$，返回Ti$T_i$.

下面是Python实现代码

from math import log
import operator
#定义计算熵函数
def calcShannonEnt(dataSet):
    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)
    return shannonEnt
#根据相应的特征索引获取数据
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 majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    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]
    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
def classify(inputTree, featLabels,testVec):
    firstStr = list(inputTree.keys())[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    for key in secondDict.keys():
        if tstVec[featIndex] == key:
            if type(secondDict[key]).__name__=='dict':
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

以下为绘制树形图的代码

#Matplotlib注解绘制树形图
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):
    createPlot.ax1.annotate(nodeTxt,xy=parentPt,xycoords="axes fraction",xytext=centerPt,textcoords="axes fraction",va="center",ha="center",bbox=nodeType,arrowprops=arrow_args)
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:
            numLeafs += 1
    return numLeafs
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(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
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)
def plotTree(myTree,parentPt,nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(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()

下面使用决策树预测隐形眼镜类型（所用数据集下载地址lenses.txt）

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

构造的决策树如下图所示

4、小结

ID3算法主要是利用熵来判定每个特征对分类的效果，决策树可以转换成一个if-then规则的集合，还有其他的决策树构造算法，最流行的是C4.5和CART，后面我会介绍。