1. 基本内容
2. 划分选择
3. 剪枝处理
4. 连续与缺失值
5. 多变量决策树

1. 基本内容

决策树通常有三个步骤：特征选择、决策树生成、决策树的修建。
决策树是一种十分常用的分类方法，需要监管学习，监管学习就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

• 创建一个决策树的主要问题在于：
  1.决策树中每个节点在哪个维度的特征上面进行划分？
  2.被选中的维度的特征具体在哪个值上进行划分？

参考：
知乎：决策树算法的Python实现——黄耀鹏、YJanggo视频信息熵是什么？ - 知乎 (zhihu.com)

YouTube：statquest

2. 划分选择

2.1 信息增益——决策树ID3训练算法

• 熵：一种食物的不确定性叫做熵。
• 信息：消除不确定性的事物；调整概率；排除干扰；确定情况
  信息熵计算公式.png
  其中

2.2 增益率——决策树C4.5训练算法

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响。C4.5算法使用增益率替代信息增益来选择最优划分属性。
使用方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.3 基尼指数——决策树CART训练算法

基尼系数是信息增益准则的一种近似，具有计算简单的特点。
基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
注意： Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

基尼系数公式.png

参考资料：（一）《机器学习》（周志华）第4章 决策树 笔记 理论及实现——“西瓜树” - 君以沫 - 博客园 (cnblogs.com)

3. 剪枝处理

3.1 预剪枝

3.2 后剪枝

4. 连续与缺失值

4.1 连续值处理

4.2 缺失值处理

5. 多变量决策树

#! /usr/bin/python
#coding=utf-8
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','flippers']#两个特征项（不能浮出水面是否可以生存，脚蹼）
    return dataSet,labels
'''
dataSet：样本集合
'''
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   #当前标签每出现一次，则当前标签对应的计数器+1
    shannonEnt = 0.0 #初始熵为0
    for key in labelCounts:#对于标签计数器的每个标签
        prob = float(labelCounts[key]) / numEntries #出现的概率=当前的标签计数/总的数据个数
        shannonEnt -= prob*log(prob,2)  #根据熵的计算公式，当前熵=负的（所有的概率*log概率）之和，这里的log以2为底
    return shannonEnt #返回信息熵
'''
dataSet：样本集合
axis：特征项
value： 特征值
'''
def splitDataSet(dataSet, axis, value):
    retDataSet = [] #初始化返回的子样本集合
    
    for featVec in dataSet: #对于数据集的每一行，即每一个数据特征项
        if featVec[axis] == value: #如果指定的特征项数值=给定的数值
            reducedFeatVec = featVec[:] #复制当前数据点的特征值
            reducedFeatVec.remove(reducedFeatVec[axis]) # 去除指定的特征项
            retDataSet.append(reducedFeatVec) #添加到返回的样本集合中去
    return retDataSet #返回的子样本集合
'''
dataSet：样本集合
'''
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1   #获取样本的特征项个数
    baseEntropy = calcShannonEnt(dataSet)   #计算总的样本集合的熵
    bestInfoGain = 0.0;     #初始化最大信息增益值为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 #返回最优划分特征所在的列数
 
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),reverse=True)
    return sortedClassCount[0][0]
'''
dataSet：样本集合
labels： 特征项
'''
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])   #删除list中此特征项
    featValues = [example[bestFeat] for example in dataSet] #将所有样本在该特征项下的值取出来
    uniqueVals = set(featValues)    #去重
    for value in uniqueVals:    #对于不同的特征值
        subLabels = labels[:]   #复制标签
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels) #递归创建决策树，使用划分后的子样本集合和子标签
    return myTree   #返回决策树，决策树的key为最优划分特征，值为key为特征值，value为对应的子样本决策树。
myDat,labels=createDataSet()
myTree = createTree(myDat,labels)
print myTree