Python 决策树的构造

　　上一节我们学习knn，kNN的最大缺点就是无法给出数据的内在含义，而使用决策树处理分类问题，优势就在于数据形式非常容易理解。

　　决策树的算法有很多，有CART、ID3和C4.5等，其中ID3和C4.5都是基于信息熵的，也是我们今天的学习内容，主要是根据通过信息熵划分数据集，再进入递归构造决策树的过程。

1. 信息熵

　　熵最初被用在热力学方面的，由热力学第二定律，熵是用来对一个系统可以达到的状态数的一个度量，能达到的状态数越多熵越大。香农1948年的一篇论文《A Mathematical Theory of Communication》提出了信息熵的概念，此后信息论也被作为一门单独的学科。

　　信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么他出现的各种情况也就越多。信息熵越小，说明信息量越小。

　　对于信息的定义，可以这样理解，如果待分类的事务划分在多个分类之中，则符号x_i的信息定义为

　　　　I(x_i) = -log₂p(x_i) 其中p(x_i) 是选择该分类的概率

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

　　　　 Python 决策树的构造，其中n是分类的数目

2. 计算信息熵

　　这里有个小例子，通过2个特征：不浮出水面是否可以生存，是否有脚蹼，来判断是否属于鱼类。其中‘1’表示是，‘0’表示否

不浮出水面是否可以生存	是否有脚蹼	属于鱼类
1	1	1
1	1	1
1	0	0
0	1	0
0	1	0

　　使用python实现简单计算信息熵，程序如下：

#-*- coding:utf-8 -*-
from math import log

#创建简单数据集

def creatDataset():

    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):

    numEntries = len(dataSet)

    labelCounts = {}

    for vec in dataSet:

        currentLabel = vec[-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 

#简单测试

myDat,labels = creatDataset()

print myDat

print calcShannonEnt(myDat)

　　测试结果如下：

[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

0.970950594455

　　得到熵之后，我们就可以按照获取最大信息熵的方法来划分数据集。

3. 划分数据集

　　划分的方法是：对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。

　　定义函数splitDataset(dataSet,axis,value)来将数据划分，其中axis表示划分数据集的特征（比如说"是否有脚蹼"），value表示特征的值（“有脚蹼”还是“无脚蹼”）　

#按照给定的特征划分数据集

def splitDataset(dataSet,axis,value):

    retDataset = []     #符合特征的数据

    for vec in dataSet:

        if vec[axis] == value:       #数据特征符合要求

            reducedVec = vec[:axis]  #提取该数据的剩余特征

            reducedVec.extend(vec[axis+1:])   #将两列表合成一个列表

            reDataset.append(reducedVec)

    return reDataset

　　接下里，我们需遍历整个数据集，循环计算香农熵和splitDataset（）函数，找到最好的特征划分方式。

　　思路：计算原始信息熵，然后对每个特征值（去重）划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和，期望是找到最好的信息增益，也即是熵的减少量最大，最后返回最好特征划分的索引值。

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

def chooseBestFeatureToSplit(dataSet):

    numFeatures = len(dataSet[0]) - 1     #特征数

    baseEntropy = calcShannonEnt(dataSet) #计算原始熵

    bestInfoGain = 0.0

    bestFeature = -1

    for i in xrange(numFeatures):

        featList = [eg[i] for eg 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

4. 递归构造决策树

秒客网

Python 决策树的构造

相关文章