基本概念

决策树是一种基本的分类与回归，我们可以把决策树看成一个if-then规则；通过对数据集中属性进行判断，从而将数据打上对应的标签；这也是有监督学习的一种

流程

收集数据
整理数据，将数据按照一定的规则整理、排版
分析数据，构造决策树使用简单数据集，检查决策树是否符合预期
训练算法，使用你准备的数据集中的一部分数据，进行训练，构造出决策树数据结构
测试算法
使用算法

构造数据集

def creatDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'], 
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
    return dataSet, labels

信息熵计算

def calcShannonEnt(dataset):
    numEntires=len(dataset) #数据集的大小
    labelCount={}             #统计每一种分类对应的数目
    for featVec in dataset:
        currentLabel=featVec[-1] #分类标签
        if currentLabel not in labelCount:
            labelCount[currentLabel] = 0
        labelCount[currentLabel]+=1
    shannonEnt=0.0 
    for key in labelCount:
        prob=float(labelCount[key])/numEntires #计算权重使用float函数产生小数
        shannonEnt-=prob*log(prob,2)
    return shannonEnt

寻找最优特征

遍历每一个属性
找到每一个属性对应值的子集D1、D2、D3
计算每个属性下的信息增益
找到当前数据集下，最优的分类属性

'''
找到对应的特征为value的行，将这个属性清除作为下一个子集D1
'''
def splitDataSet(dataSet,axis,value):
    reDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reduceFeatVec=featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            reDataSet.append(reduceFeatVec)
    return reDataSet

'''
找到当前数据集下，最优的分类属性
'''
def chooseBestFeatureToSplit(dataset):
    numfeatures=len(dataset[0])-1       ##准备遍历每一个属性
    baseEntropy=calcShannonEnt(dataset) ##初始信息熵
    bestInfoGain=0.0                     ##最大信息增益
    bestFeature=-1                        ##记录最优属性下标    
    for i in range(numfeatures):
        featList=[examp[i] for examp in dataset] #获得单个属性的所有值
        uniqVals=set(featList)     #去重，基于属性值分为子集D1、D2、D3
        newEntrop=0.0           #每种属性对应的信息熵
        for value in  uniqVals:
            subsDataSet=splitDataSet(dataset,i,value)
            prob=len(subsDataSet)/float(len(dataset)) #子集占数据集权重
            newEntrop+=prob*calcShannonEnt(subsDataSet) #将子集信息熵累加
        inforGain=baseEntropy -newEntrop   #信息增益
        if(inforGain>bestInfoGain):
            bestInfoGain=inforGain
            bestFeature=i         #找到最优属性的下标
    return bestFeature

构造决策树

'''
当没有有意义的属性或者所有的属性都用完之后还没分开时，使用数目最多的那一类标签,作为这一类的标签
'''
def majorityCnt(classList):
    classcount={}
    for vote in classList:
        if vote not in classcount.keys():
            classcount[vote]=0
        classcount[vote]+=1
    sortclasscount=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True) #对大小倒序输出
    return sortclasscount[0][0]

'''
构造决策树

'''

def creatTree(dataset,labels,featLabels): #dataset初始数据集 labels属性名称 featLabels决策树找出的分类属性
    classList=[example[-1] for example in dataset]  #获取监督标签
    if classList.count(classList[0])==len(classList): #当数据集中标签相同时，停止分类
        return classList[0]
    if len(dataset[0])==1 or len(labels)==0: #没有可以分类的属性，或者属性都用完之后
        return majorityCnt(classList)
    bestFeat=chooseBestFeatureToSplit(dataset) #获取最优属性
    bestlabel=labels[bestFeat]  ##最优属性的名字
    featLabels.append(bestlabel) ##添加到输出结果中
    myTree={bestlabel:{}}  ##构造树形字典，键为最优属性名字，值为子树
    del(labels[bestFeat])  #从属性名列表中删除，已经找到的
    featValues=[example[bestFeat] for example in dataset]
    uniqueValues=set(featValues)
    for value in uniqueValues:
        myTree[bestlabel][value]=creatTree(splitDataSet(dataset,bestFeat,value),labels,featLabels) #从最优属性的子集D1、D2、D3中再分别得到第二优的属性...
    return myTree
###############################
dataset,labels=creatDataSet()
featLabels=[]
myTree=creatTree(dataset,labels,featLabels)
print(myTree)
print(featLabels)

使用决策树

参考

https://cuijiahua.com/blog/2017/11/ml_2_decision_tree_1.html
https://cuijiahua.com/blog/2017/11/ml_3_decision_tree_2.html