决策树---信息增益_决策树信息增益

一、什么事信息增益？

划分数据集的之前之后信息发生的变化称为信息增益，知道如何计算信息增益，就可以计算每个特征值划分数据集获得的信息增益，获取信息增益最高的特征就是最好的选择。

通俗来说就是信息选择的特征。

信息熵：表示随机变量的不确定性。
条件熵：在一个条件下，随机变量的不确定性。
信息增益：熵 - 条件熵。表示在一个条件下，信息不确定性减少的程度。
举例：
X(明天下雨)是一个随机变量，X的熵1
Y(明天阴天)也是随机变量，在阴天情况下下雨的信息熵假设为0.3（此处需要知道其联合概率分布或是通过数据估计）即是条件熵。
信息增益=X的熵-Y条件下X的熵=0.7。
在获得阴天这个信息后，下雨信息不确定性减少了0.7，不确定减少了很多，所以信息增益大。也就是说，阴天（即特征）这个信息对明天下午这一推断来说非常重要。

熵定义为信息的期望值，即计算所有类别所有可能包含的信息期望值，通过以下公式得到。其中n是分类的数目。p(i)为该分类的概率

这次实验采取的样本（共100条，这只是一部分）

二、决策树的构造

代码都写入trees.py

引入

# 决策树
# 数据可视化
import matplotlib.lines as mlines
import matplotlib.pyplot as plt
import matplotlib as mpl
from numpy import *
import operator
from math import log
# 代码功能：计算香农熵
#我们要用到对数函数，所以我们需要引入math模块中定义好的log函数（对数函数）
import trees
import treePlotter
1
2
3
4
5
6
7
8
9
10
11
12

1.信息增益

计算给定数据集的香农熵

def calcShannonEnt(dataSet):#传入数据集
# 在这里dataSet是一个链表形式的的数据集
    countDataSet = len(dataSet)                      #我们计算出这个数据集中的数据个数
    labelCounts={}                                   #构建字典，用键值对的关系我们表示出 我们数据集中的类别还有对应的关系
    for featVec in dataSet:                          #通过for循环，我们每次取出一个数据集，如featVec=[1,1,'yes']
        currentLabel=featVec[-1]                     #取出最后一列 也就是类别的那一类，比如说‘yes’或者是‘no’
        if currentLabel not in labelCounts.keys():   #若不在字典中
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0                                 #计算香农熵， 根据公式
    for key in labelCounts:
        prob = float(labelCounts[key])/countDataSet  #类别标签的频率=概率
        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'],
             [0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],
             [1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],
             [0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],
             [1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],
             [0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],
             [1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],
             [0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],
             [1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],
             [0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes'],
             [1, 1, 'yes'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 0, 'no'],[0, 1, 'no'],
             [0, 1, 'no'],[1, 1, 'yes'],[1, 1, 'yes'],[0, 1, 'no'],[0, 1, 'no'],
             [1, 1, 'yes'], [1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],
             [0, 0, 'no'],[0, 1, 'no'],[0, 1, 'no'],[0, 0, 'no'],[1, 1, 'yes']]
    labels = ['movie','bloody']
    return dataSet,labels

if __name__ == '__main__':
    myDat, labels = trees.createDataSet()
    print(myDat)
    print(calcShannonEnt(myDat))
    # 熵越大，混合数据越多
    myDat[0][-1] = 'maybe'
    print(myDat)
    print(calcShannonEnt(myDat))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

结果

2.划分数据集

（1）按照给定特征划分数据集

def splitDataSet(dataSet, axis, value):     #axis是dataSet数据集下要进行特征划分的列号例如outlook是0列，value是该列下某个特征值，0列中的sunny
    retDataSet = []                         #创建新的list对象
    for featVec in dataSet:                 #遍历数据集，并抽取按axis的当前value特征进划分的数据集(不包括axis列的值)
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

if __name__ == '__main__':
    myDat, labels = trees.createDataSet()
    # 给定特征划分数据集
    print(splitDataSet(myDat, 0, 0))
    print(splitDataSet(myDat, 0, 1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结果

（2）①选择最好的数据集划分（信息增益）

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1               #获取当前数据集的特征个数，最后一列是分类标签
    baseEntropy = calcShannonEnt(dataSet)           #计算当前数据集的信息熵
    bestInfoGain = 0.0; bestFeature = -1            #初始化最优信息增益和最优的特征
    for i in range(numFeatures):                    #遍历每个特征iterate over all the features
        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                              #返回特征下标

if __name__ == '__main__':
   # 选择最好数据集特征划分
    myDat, labels = trees.createDataSet()
    print(chooseBestFeatureToSplit(myDat))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果

②选择最好的数据集划分（基尼指数）

#基尼指数
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1               #获取当前数据集的特征个数，最后一列是分类标签
    bestGini = 999999.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        gini = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            subProb = len(splitDataSet(subDataSet, -1, 'N')) / float(len(subDataSet))
            gini += prob * (1.0 - pow(subProb, 2) - pow(1 - subProb, 2))
        if (gini < bestGini):
            bestGini = gini
            bestFeature = i
    return bestFeature                              #返回特征下标
  if __name__ == '__main__':
    # 选择最好数据集特征划分
    myDat,labels=trees.createDataSet()
    print(chooseBestFeatureToSplit(myDat))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果

说明含否决定的因素最大，即不是电影就决对不是恐怖电影，没有血腥场景也决对不是恐怖电影。

3.递归构建决策树

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), 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:                        #遍历完所有的特征时，仍然不能将数据集划分成仅包含唯一类别的分组 dataSet
        return majorityCnt(classList)               #由于无法简单的返回唯一的类标签，这里就返回出现次数最多的类别作为返回值
    bestFeat = chooseBestFeatureToSplit(dataSet)    #获取最好的分类特征索引
    bestFeatLabel = labels[bestFeat]                #获取该特征的名字
    # 这里直接使用字典变量来存储树信息，这对于绘制树形图很重要。
    myTree = {bestFeatLabel:{}}                     #当前数据集选取最好的特征存储在bestFeat中
    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
    
if __name__ == '__main__':
    # 创建树
    myDat, labels = trees.createDataSet()
    myTree = createTree(myDat, labels)
    print(myTree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

结果

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

函数写入treePlotter.py。主函数写在trees.py

引入

import matplotlib.pyplot as plt
import pickle
1
2

1.Matplotlib注解

使用文本注解绘制树节点

#绘制树形图
#首先定义文本框和箭头的格式：
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 createPlot():
    fig=plt.figure(1,facecolor='white')                 #创建一个新图形，白色
    fig.clf()                                           #清空绘图区
    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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.构造注解树

（1）获取叶节点的数目和树的层数

#获取叶子节点个数
def getNumLeafs(myTree):                                #获取叶节点数目
    numLeafs = 0                                        #叶节点数初始化为0
    # firstStr = myTree.keys()[0]                       #python3.6以上版本这么改
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]
    secondDict = myTree[firstStr]                       #第一个key对应的value为其子树
    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                                        #最大树高初始化为0
    # firstStr = myTree.keys()[0]                         #第一个节点为树的第一个键值 #需要转化为列表才能按下标访问
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]
    secondDict = myTree[firstStr]                       #第一个key对应的value为其子树
    for key in secondDict.keys():                       #对子树的每个孩子节点
        if type(secondDict[key]).__name__ =='dict':     #如果当前子节点仍有子树
            thisDepth = 1+ getTreeDepth(secondDict[key])
        else:                                           #否则说明是叶节点
            thisDepth = 1                               #当前树高为1
        if thisDepth > maxDepth : maxDepth = thisDepth  #如果当前树高大于最大树高则更新最大树高
    return maxDepth

def retrieveTree(i):
    listodfTrees=[{'no movie':{0:'no',1:{'bloody':{0:'no',1:'yes'}}}},
                  {'no movie':{0:'no',1:{'bloody':{0:{'head':{0:'no',1:'yes'}},1:'no'}}}}
                  ]
    return listodfTrees[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

main函数在trees.py执行

if __name__ == '__main__':
 	treePlotter.retrieveTree(1)
    myTree = treePlotter.retrieveTree(0)
    print(treePlotter.getNumLeafs(myTree))
    print(treePlotter.getTreeDepth(myTree))
1
2
3
4
5

结果

（2）plotTree函数

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#减少y偏移
    for key in secondDict.keys():                       #对当前树的每个子树
        if type(secondDict[key])==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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

main函数在trees.py执行

if __name__ == '__main__':
   # 打印树
    myTree = treePlotter.retrieveTree(0)
    print(treePlotter.createPlot(myTree))
1
2
3
4

结果

main函数在trees.py执行

if __name__ == '__main__':
 #打印树
    myTree = treePlotter.retrieveTree(0)
    myTree['no movie'][3]='maybe'
    myTree
    {'no movie':{0:'no',1:{'bloody':{0:'no',1:'yes'}},3:
        'maybe'}}
    print(treePlotter.createPlot(myTree))
1
2
3
4
5
6
7
8

结果

四.测试与储存分类器

1.使用决策树执行分类

使用决策树的分类函数

def classify(inputTree, featLabels, testVec):        #递归函数，从决策树根节点起不断向下在输入向量中找到对应特征，直到得出结果
    firstStr = list(inputTree.keys())[0]             #当前树的根节点标签字符
    secondDict = inputTree[firstStr]                 #根节点的子树
    #将标签字符串转换为索引
    featIndex = featLabels.index(firstStr)           #当前判断的特征在特征向量中的下标
    for key in secondDict.keys():                    #对此特征下对应的各个分类方向
        if testVec[featIndex]==key:                  #找到测试向量对应的那个方向
            if type(secondDict[key])==dict:          #如果下面还有分类
                classLabel = classify(secondDict[key], featLabels, testVec) #对其之后对应的分类继续递归调用此函数
            else:
                classLabel = secondDict[key]         #若已到叶节点则判断结束，classLabel返回给上层调用
    return classLabel
1
2
3
4
5
6
7
8
9
10
11
12

main函数在trees.py执行

if __name__ == '__main__':
 #测试
    # 测试
    myDat,labels=trees.createDataSet()
    myTree = createTree(myDat, labels)
    # treePlotter.createPlot(myTree)
    myDat, labels = trees.createDataSet()
    print("[1,0]", treePlotter.classify(myTree, labels, [1, 0]))
    print("[1,1]", treePlotter.classify(myTree, labels, [1, 1]))
    print("[0,1]", treePlotter.classify(myTree, labels, [0, 1]))
    print("[0,0]", treePlotter.classify(myTree, labels, [0, 0]))
1
2
3
4
5
6
7
8
9
10
11

结果

2.决策树的存储

使用pickle模块存储决策树

# 决策树的存储
def storeTree(inputTree, filename):
		# 这里二进制写入
		# fw=open(filename,'w')
		fw = open(filename, 'wb')
		# dump函数将决策树写入文件中
		pickle.dump(inputTree, fw)
		# 写完成后关闭文件
		fw.close()

	# 取决策树
def grabTree(filename):
		import pickle
		# 采用二进制读取
		# fr=open(filename)
		fr = open(filename, 'rb')
		return pickle.load(fr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

main函数在trees.py执行

if __name__ == '__main__':
myDat, labels = trees.createDataSet()
    myTree = createTree(myDat, labels)
    treePlotter.storeTree(myTree, 'movie.txt')
    treePlotter.grabTree('movie.txt')
    {'no movie': {0: 'no', 1: {'bloody': {0: 'no', 1: 'yes'}}}}
1
2
3
4
5
6

结果（自己会在目录下生成一个.txt文件，至于为什么是乱码，我也没整明白，试了百度的方法也没用，要是有小可爱知道滴我一声哈）