Python3.0 实现决策树算法

决策树的一般流程

检测数据集中的每个子项是否属于同一个分类 

if so return 类标签

Else 

    寻找划分数据集的最好特征

    划分数据集

   创建分支 节点

from math import log
import operator



#生成样本数据集
def createDataSet():
    dataSet = [[1,1,'yes'],
               [1,1,'yes'],
               [1,0,'no'],
               [0,1,'no'],
               [0,1,'no']]
    labels = ['no surfacing','flipper']
    return dataSet,labels

# 计算香农熵 香农 大神必须要膜拜啊，信息界的根目录人物啊
#  no surfacing 指的是 不浮出水面能否生存 1 标识 是 0 指的是否
# flipper 指的是是否有脚
#  yes  no指的是否是鱼类
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) # 用上面的createDataSet dataSet 这个值就是5
    #定义标签字典
    labelCounts = {}

    # 为所有可能的分类创建字典
    for featVec in dataSet:
        currentLabel = featVec[-1]  #这个-1指的是去取最后一个维度 对应数据dataSet 这里取的是yes和no
        if currentLabel not in labelCounts.keys():
            # 如果当前分类标签不在 标签字典中
            labelCounts[currentLabel] = 0
        # 其他情况 分类标签分类加1
        labelCounts[currentLabel] += 1
    #定义香农熵 以2为底数求对数
    shannonEnt = 0.0
    for key in labelCounts:
        #计算 yes 或者No 出现的概率
        pro = float(labelCounts[key])/numEntries
        # 计算香农熵
        shannonEnt -= pro*log(pro,2)
    return shannonEnt

#dataSet是待划分的数据集， 划分数据集的特征 axis 特征的返回值value
#最后是创建了一个新的列表对象
def splitDataSet(dataSet, axis , value):
    # 创建新list对象
    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):
    # len(dataSet[0]）是计算这一行有多少列，即有多少个特征值
    numFeatures = len(dataSet[0])-1 # -1 是最后一个特征值就不要记录在内了，算baseEntrop的时候已经算了最后一个特征值yes no
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        #创建唯一的分类标签列表 也就是说提取dataSet每一行第i个值 就提取dat
        featList = [example[i] for example in dataSet]
        # 取出有几种特征值
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            #创建特征值的子数据集
            subDataSet = splitDataSet(dataSet,i, value)
            #计算该特征值数据对总数在数据对总数出现的概率
            pro = len(subDataSet)/float(len(dataSet))
            #计算分割出来的子集香农熵
            newEntropy += pro*calcShannonEnt(subDataSet)
        #计算信息增益 得到最好的特征值 这个理论是这样的g(D,A) = H(D)-H(D/A）
        infoGain = baseEntropy-newEntropy
        #取出最大的信息增益，此时特征值最大
        if(infoGain >bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

'''
#构建决策树是根据特征值的消耗来计算的，如果后面的特征值已经全部用完了
但是还没有分出结果，这个时候就需要使用多数表决方式计算节点分类
最后返回最大的分类
'''
def majorityCnt(classList):
    # 分类的字典
    classCount = {}
    for vote in range(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):
    # 获取数据样本每组最后一组的特征值 这里是yes,no
    classList = [example[-1] for example in dataSet]
    # 如果说这个classList 全部都是 yes 或者全部是no 那肯定子返回yes 或者no
    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:{}}
    # 删除labels中的一特征值
    del(labels[bestFeat])
    #找到特征值那一列
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # labels列表的赋值
        subLabels = labels[:]
        myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree




dataSet,lables = createDataSet()
shannonEnt= calcShannonEnt(dataSet)
my = createTree(dataSet,lables)
print(my)