3.1决策树构造

#3-1计算给定数据集的香农熵
from math import log
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 createDataSet():
    dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    labels = ['no surfacing','flippers']
    return dataSet,labels
#3-2按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):#待划分的数据集、划分数据集的特征、需要返回的特征值
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]  #这一行和下一行整体的功能就是删除这一行
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)#将这些特征值加到新建的list中
    return retDataSet
           

keys()函数：将字典转化为列表函数。创建一个数据字典，它的键值是最后一列的数值。

在第二个函数中，python语言在函数中传递的是列表的引用，在函数内部对列表对象的修改，将会影响该列表对象的整个生存周期。为了消除这个不良影响，我们需要在函数的开始声明一个新列表的对象。

#3-3选择最好的数据集划分方式
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
           

在函数中调用的数据需要满足一定的要求：1.数据必须是一种由列表元素组成的列表，而且所有的列表元素都要具有相同的数据长度。

2.数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。

数据集一旦满足上述要求，我们就可以在函数的第一行判定当前数据集包含多少类别标签。

[example[i] for example in  dataSet]是什么意思？

https://blog.csdn.net/jiangsujiangjiang/article/details/84313227

我的理解：在dataSet中逐行遍历，example[i]中的i就是提取每一个行中第i+1个元素。

set()函数：用来创建集合。创建空集合，必须使用set()而不是{}，{}用于创建空字典。

#挑选次数最多的类别
def majorituCnt(classList):
    classCount = {}
    for vote in classList:
        if vote in classCount.keys():classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
#3-4创建树的函数代码
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:# 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
        return majorituCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#返回的是数字
    bestFeatLabel = labels[bestFeat]
    mytree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]# 取出最优列，然后它的branch做分类
    uniqueVals = set(featValues)#将列表变为元组
    for value in uniqueVals:
        subLabels = labels[:]# 求出剩余的标签label
        mytree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
        # 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
    return  mytree
           

count()函数：计算某个元素在列表中出现的次数

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
           

上面是需要分类的各个类别，下面进行测试：

myDat,labels = createDataSet()
Tree = createTree(myDat,labels)
print(Tree)
           

显示出我们需要的树结构。