3.1决策树的构造

3.1.1信息增益

划分数据的原则是：将无序的数据变得有序。
香农熵：定义为信息的期盼值，熵值越高，信息越混乱。
计算所有类别所有可能值包含的信息期望值：H = sum(-p(xi)*log2p(xi)) (1<=i<=n) n为分类的数目。
利用python3计算给定数据集香农熵

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
        # log(x,y)代表以y为底x的对数
        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

测试

import trees
myDat , labels = trees.createDataSet()
print(myDat)
print(trees.calcShannonEnt(myDat))

结果：

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

得到熵值以后，我们可以按照最大增益的方法划分数据集

3.1.2 划分数据集

上一段中，描述了如何去计算香农熵，学习了如何去度量数据集的无序程度，度量划分数据集的熵，以便于判读是否正确地划分了数据集
按照给定的特征划分数据集

def splitDataSet(dataSet,axis,value):
    #传入一个列表
    retDataSet=[]
    #抽取所有符合条件的元素抽取出来
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec=featVec[:axis]#按照axis划分参数集
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

测试结果：

print (myDat)
print(trees.splitDataSet(myDat,0,1))#划分mydata，按照featvec[0] == 1 划分 ；即按照第0(1列)划分出特征为1的
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
[[1, 'yes'], [1, 'yes'], [0, 'no']]

选择做好的数据集划分方式
遍历整个的数据集，循环计算香农熵和splitDataSet()函数，以此找到最好的划分方法

#实现选取特征，划分数据集，计算得出最好的划分数据集的特征
#函数调用的数据要求：必须是由一种列表元素构成的列表每个列表元素都要有相同的数据长度
#数据的最后一列或者每个实例的最后一个元素为当前实例的标签
def chooseBestFeatureToSplit(dataSet):
    numFeatures=len(dataSet[0])-1
    #计算整个数据集的原始香农熵
    baseEntropy=calcshannonEnt(dataSet)
    beatInfoGain=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>beatInfoGain):
            bestInfoGain=infoGain
            bestFeature=i
    return bestFeature

测试结果：

import trees
myDat , labels = trees.createDataSet()
print(trees.chooseBestFeatureToSplit(myDat))
print(myDat)
测试输出：0 #意味着选第0列是最好的划分特征
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
#可以输出myDat来研究一下

3.1.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), reversed=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中
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

测试结果：

import trees
myDat , labels = trees.createDataSet()
myTree = trees.createTree(myDat,labels)
print(myTree)
效果：{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

感谢学长代码的注释能够让我更快的理解
https://blog.csdn.net/qq_33638791/article/details/53324364