<h1 id='0'> 决策树算法梳理 </h1>
<h2 id='1'> 1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度） </h2>

<h3 id='2'> 1.1 熵 （entropy） </h3>

在信息论与概率统计中，熵表示随机变量不确定性的度量。设X是一个取有限个值得离散随机变量，其概率分布为

则随机变量X的熵定义为

若pi等于0，定义0log0=0，熵的单位为比特或者纳特。

<h3 id='3'> 1.2 联合熵 </h3>

举个例子，更容易理解一些，比如天气是晴天还是阴天，和我穿短袖还是长袖这两个事件其可以组成联合信息熵H(X,Y)H(X,Y)，而对于H(x)H(x)就是天气单独一个事件的信息熵，因为两个事件组合起来的信息量肯定是大于单一一个事件的信息量的。

而今天天气和我今天穿衣服这两个随机概率事件并不是独立分布的，所以如果已知今天天气的情况下，我的穿衣与天气的联合信息量/不确定程度是减少了的，也就相当于两者联合信息量已知了今天下雨，那么H(x)H(x)的信息量就应该被减去，得到当前的新联合信息量，也相当于条件信息量。

所以当已知H(x)H(x)这个信息量的时候，联合分布H(X,Y)H(X,Y)剩余的信息量就是条件熵。

Ref：https://blog.csdn.net/gangyin5071/article/details/82228827#5%E8%81%94%E5%90%88%E4%BF%A1%E6%81%AF%E7%86%B5%E5%92%8C%E6%9D%A1%E4%BB%B6%E4%BF%A1%E6%81%AF%E7%86%B5

<h3 id='4'> 1.3 条件熵 (Conditional Entropy) </h3>

H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性定义为X给定条件下Y的条件概率分布的熵对X的数学期望

经验熵和经验条件熵：当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和条件经验熵。

<h3 id='5'> 1.4 信息增益（Information Gain） </h3>

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

from numpy import *
import numpy as np
import pandas as pd
from math import log
import operator
from sklearn.datasets import load_iris


# 计算数据集的香农熵
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
    # 以2为底数计算香农熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt


# 对离散变量划分数据集，取出该特征取值为value的所有样本
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet


# 对连续变量划分数据集，direction规定划分的方向，
# 决定是划分出小于value的数据样本还是大于value的数据样本集
def splitContinuousDataSet(dataSet, axis, value, direction):
    retDataSet = []
    for featVec in dataSet:
        if direction == 0:
            if featVec[axis] > value:
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis + 1:])
                retDataSet.append(reducedFeatVec)
        else:
            if featVec[axis] <= value:
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis + 1:])
                retDataSet.append(reducedFeatVec)
    return retDataSet


# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet, labels):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    bestSplitDict = {}
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        # 对连续型特征进行处理
        if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
            # 产生n-1个候选划分点
            sortfeatList = sorted(featList)
            splitList = []  # 划分点集合
            for j in range(len(sortfeatList) - 1):
                splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)

            bestSplitEntropy = 10000
            slen = len(splitList)
            # 求用第j个候选划分点划分时，得到的信息熵，并记录最佳划分点
            for j in range(slen):
                value = splitList[j]
                newEntropy = 0.0
                subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)  # 大于value的集合
                subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)  # 小于value的集合
                prob0 = len(subDataSet0) / float(len(dataSet))
                newEntropy += prob0 * calcShannonEnt(subDataSet0)
                prob1 = len(subDataSet1) / float(len(dataSet))
                newEntropy += prob1 * calcShannonEnt(subDataSet1)
                if newEntropy < bestSplitEntropy:
                    bestSplitEntropy = newEntropy
                    bestSplit = j
            # 用字典记录当前特征的最佳划分点
            bestSplitDict[labels[i]] = splitList[bestSplit]
            infoGain = baseEntropy - bestSplitEntropy
        # 对离散型特征进行处理
        else:
            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
    # 若当前节点的最佳划分特征为连续特征，则将其以之前记录的划分点为界进行二值化处理
    # 即是否小于等于bestSplitValue
    if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
        bestSplitValue = bestSplitDict[labels[bestFeature]]
        labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
        for i in range(shape(dataSet)[0]):
            if dataSet[i][bestFeature] <= bestSplitValue:
                dataSet[i][bestFeature] = 1
            else:
                dataSet[i][bestFeature] = 0
    return bestFeature


# 特征若已经划分完，节点下的样本还没有统一取值，则需要进行投票
def majorityCnt(classList):
    classCount = {}

    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
            classCount[vote] += 1
    return max(classCount)


# 主程序，递归产生决策树
def createTree(dataSet, labels, data_full, labels_full):
    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, labels) #获取选取的特征下标
    bestFeatLabel = labels[bestFeat]  # 下标容易变，但标签不容易变
    myTree = {bestFeatLabel: {}}  # 树根root
    featValues = [example[bestFeat] for example in dataSet]  #该标签下的所有值
    uniqueVals = set(featValues)    #将值去重

    if type(dataSet[0][bestFeat]).__name__ == 'str':  # 若第一行是标签则更新当前的标签信息
        currentlabel = labels_full.index(labels[bestFeat])
        featValuesFull = [example[currentlabel] for example in data_full]
        uniqueValsFull = set(featValuesFull)

    del (labels[bestFeat])  #删除label中的改特征名
    # 针对bestFeat的每个取值，划分出一个子树。
    for value in uniqueVals:
        subLabels = labels[:]
        if type(dataSet[0][bestFeat]).__name__ == 'str':
            uniqueValsFull.remove(value)
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, data_full,
                                                  labels_full)
    if type(dataSet[0][bestFeat]).__name__ == 'str':
        for value in uniqueValsFull:
            myTree[bestFeatLabel][value] = majorityCnt(classList)
    return myTree


import matplotlib.pyplot as plt

decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")


# 计算树的叶子节点数量
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]  # python3中 'dict_keys' 返回的是dict_keys对象，支持iterable但不支持indexable  需要手动list
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:
            numLeafs += 1
    return numLeafs


# 计算树的最大深度
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:
            thisDepth = 1
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth


# 画节点
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction',
                            va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)


# 画箭头上的文字
def plotMidText(cntrPt, parentPt, txtString):
    lens = len(txtString)
    xMid = (parentPt[0] + cntrPt[0]) / 2.0 - lens * 0.002
    yMid = (parentPt[1] + cntrPt[1]) / 2.0
    createPlot.ax1.text(xMid, yMid, txtString)


def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]
    cntrPt = (plotTree.x0ff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.y0ff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    plotTree.y0ff = plotTree.y0ff - 1.0 / plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            plotTree(secondDict[key], cntrPt, str(key))
        else:
            plotTree.x0ff = plotTree.x0ff + 1.0 / plotTree.totalW
            plotNode(secondDict[key], (plotTree.x0ff, plotTree.y0ff), cntrPt, leafNode)
            plotMidText((plotTree.x0ff, plotTree.y0ff), cntrPt, str(key))
    plotTree.y0ff = plotTree.y0ff + 1.0 / plotTree.totalD


def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.x0ff = -0.5 / plotTree.totalW
    plotTree.y0ff = 1.0
    plotTree(inTree, (0.5, 1.0), '')
    plt.show()


# 输入三个变量（决策树，属性特征标签，测试的数据）
def classify(inputTree, featLables, testVec):
    firstStr = list(inputTree.keys())[0]  # 获取树的第一个特征属性
    secondDict = inputTree[firstStr]  # 树的分支，子集合Dict
    featIndex = featLables.index(firstStr)  # 获取决策树第一层在featLables中的位置
    preLabel =[]
    for test in testVec:
        for key in secondDict.keys():
            if test[featIndex] == key:
                if type(secondDict[key]).__name__ == 'dict':
                    classLabel = classify(secondDict[key], featLables, testVec)
                else:
                    classLabel = secondDict[key]
    return classLabel


from sklearn.model_selection import train_test_split

if __name__ == '__main__':
    dataSet = load_iris()
    x_train, x_test, y_trian, y_test = train_test_split(dataSet.data, dataSet.target, test_size=0.2)
    data = np.c_[x_train, y_trian].tolist()
    data_full = data[:]
    labels = ["Calyx length", "calyx width", "petal length", "petal width"]
    labels_full = labels[:]
    myTree = createTree(data, labels, data_full, labels_full)

    createPlot(myTree)
    # classify(myTree,labels, x_test)
# 参考：https://blog.csdn.net/wzmsltw/article/details/51039928
# 参考：https://blog.csdn.net/shenxiaoming77/article/details/51602976

于是我们可以应用信息增益准则来选择特征，信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。对数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

信息增益比：

from numpy import *
import numpy as np
import pandas as pd
from math import log
import operator
from sklearn.datasets import load_iris


# 计算数据集的香农熵
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
    # 以2为底数计算香农熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt


# 对离散变量划分数据集，取出该特征取值为value的所有样本
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet


# 对连续变量划分数据集，direction规定划分的方向，
# 决定是划分出小于value的数据样本还是大于value的数据样本集
def splitContinuousDataSet(dataSet, axis, value, direction):
    retDataSet = []
    for featVec in dataSet:
        if direction == 0:
            if featVec[axis] > value:
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis + 1:])
                retDataSet.append(reducedFeatVec)
        else:
            if featVec[axis] <= value:
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis + 1:])
                retDataSet.append(reducedFeatVec)
    return retDataSet


# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet, labels):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    bestSplitDict = {}
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        # 对连续型特征进行处理
        if type(featList[0]).__name__ == 'float' or type(featList[0]).__name__ == 'int':
            # 产生n-1个候选划分点
            sortfeatList = sorted(featList)
            splitList = []  # 划分点集合
            for j in range(len(sortfeatList) - 1):
                splitList.append((sortfeatList[j] + sortfeatList[j + 1]) / 2.0)

            bestSplitEntropy = 10000

            featureEntropy = 0.0  # 训练数据集关于特征的商H_A(D)
            slen = len(splitList)
            # 求用第j个候选划分点划分时，得到的信息熵，并记录最佳划分点
            for j in range(slen):
                value = splitList[j]
                newEntropy = 0.0
                subDataSet0 = splitContinuousDataSet(dataSet, i, value, 0)  # 大于value的集合
                subDataSet1 = splitContinuousDataSet(dataSet, i, value, 1)  # 小于value的集合
                prob0 = len(subDataSet0) / float(len(dataSet))
                newEntropy += prob0 * calcShannonEnt(subDataSet0)
                prob1 = len(subDataSet1) / float(len(dataSet))
                newEntropy += prob1 * calcShannonEnt(subDataSet1)

                if newEntropy < bestSplitEntropy:
                    bestSplitEntropy = newEntropy
                    bestSplit = j
                    featureEntropy = -1.0*(prob0 * log(prob0, 2)+prob1 * log(prob1, 2))  # 计算
            # 用字典记录当前特征的最佳划分点
            bestSplitDict[labels[i]] = splitList[bestSplit]
            infoGain = baseEntropy - bestSplitEntropy  # 信息增益
            infoGain = infoGain / float(featureEntropy) # 信息增益比

        # 对离散型特征进行处理
        else:
            uniqueVals = set(featList)
            newEntropy = 0.0
            featureEntropy = 0.0  # 训练数据集关于特征的商H_A(D)
            # 计算该特征下每种划分的信息熵
            for value in uniqueVals:
                subDataSet = splitDataSet(dataSet, i, value)
                prob = len(subDataSet) / float(len(dataSet))
                newEntropy += prob * calcShannonEnt(subDataSet)
                featureEntropy -= prob * log(prob, 2)
            infoGain = baseEntropy - newEntropy  # 信息增益
            infoGain = infoGain / float(featureEntropy)  #信息增益比

        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    # 若当前节点的最佳划分特征为连续特征，则将其以之前记录的划分点为界进行二值化处理
    # 即是否小于等于bestSplitValue
    if type(dataSet[0][bestFeature]).__name__ == 'float' or type(dataSet[0][bestFeature]).__name__ == 'int':
        bestSplitValue = bestSplitDict[labels[bestFeature]]
        labels[bestFeature] = labels[bestFeature] + '<=' + str(bestSplitValue)
        for i in range(shape(dataSet)[0]):
            if dataSet[i][bestFeature] <= bestSplitValue:
                dataSet[i][bestFeature] = 1
            else:
                dataSet[i][bestFeature] = 0
    return bestFeature


# 特征若已经划分完，节点下的样本还没有统一取值，则需要进行投票
def majorityCnt(classList):
    classCount = {}

    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
            classCount[vote] += 1
    return max(classCount)


# 主程序，递归产生决策树
def createTree(dataSet, labels, data_full, labels_full):
    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, labels)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel: {}}
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)

    if type(dataSet[0][bestFeat]).__name__ == 'str':  # 若第一行是标签则跟新当前的标签信息
        currentlabel = labels_full.index(labels[bestFeat])
        featValuesFull = [example[currentlabel] for example in data_full]
        uniqueValsFull = set(featValuesFull)

    del (labels[bestFeat])
    # 针对bestFeat的每个取值，划分出一个子树。
    for value in uniqueVals:
        subLabels = labels[:]
        if type(dataSet[0][bestFeat]).__name__ == 'str':
            uniqueValsFull.remove(value)
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, data_full,
                                                  labels_full)
    if type(dataSet[0][bestFeat]).__name__ == 'str':
        for value in uniqueValsFull:
            myTree[bestFeatLabel][value] = majorityCnt(classList)
    return myTree


import matplotlib.pyplot as plt

decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")


# 计算树的叶子节点数量
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]  # python3中 'dict_keys' 返回的是dict_keys对象，支持iterable但不支持indexable  需要手动list
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:
            numLeafs += 1
    return numLeafs


# 计算树的最大深度
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:
            thisDepth = 1
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth


# 画节点
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction',
                            va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)


# 画箭头上的文字
def plotMidText(cntrPt, parentPt, txtString):
    lens = len(txtString)
    xMid = (parentPt[0] + cntrPt[0]) / 2.0 - lens * 0.002
    yMid = (parentPt[1] + cntrPt[1]) / 2.0
    createPlot.ax1.text(xMid, yMid, txtString)


def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = list(myTree.keys())[0]
    cntrPt = (plotTree.x0ff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.y0ff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    plotTree.y0ff = plotTree.y0ff - 1.0 / plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            plotTree(secondDict[key], cntrPt, str(key))
        else:
            plotTree.x0ff = plotTree.x0ff + 1.0 / plotTree.totalW
            plotNode(secondDict[key], (plotTree.x0ff, plotTree.y0ff), cntrPt, leafNode)
            plotMidText((plotTree.x0ff, plotTree.y0ff), cntrPt, str(key))
    plotTree.y0ff = plotTree.y0ff + 1.0 / plotTree.totalD


def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.x0ff = -0.5 / plotTree.totalW
    plotTree.y0ff = 1.0
    plotTree(inTree, (0.5, 1.0), '')
    plt.show()


if __name__ == '__main__':
    dataSet = load_iris()

    data = np.c_[dataSet.data, dataSet.target].tolist()
    data_full = data[:]
    labels = ["Calyx length", "calyx width", "petal length", "petal width", "target"]
    labels_full = labels[:]
    myTree = createTree(data, labels, data_full, labels_full)

    createPlot(myTree)

#参考：https://blog.csdn.net/wzmsltw/article/details/51039928
#参考：https://blog.csdn.net/shenxiaoming77/article/details/51602976

<h3 id='6'> 1.5 基尼不纯度 (Gini impurity) </h3>

将来自集合中的某种结果随机应用于集合中某一数据项的预期误差率。

在CART(Classification and Regression Tree)算法中利用基尼不纯度构造二叉决策树。

假设这个数据集里有k种不同标签，第i个标签所占的比重为pi，那么Gini impurity为

基尼不纯度

它描述了一个数据集中标签分布的不纯度，类似于entropy。

<h2 id='7'> 2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景 </h2>

<h3 id='8'> 2.1 ID3算法 原理及应用场景 </h3>

核心思想：以信息增益为度量，选择分裂后信息增益最大的特征进行分裂

遍历所有特征，对于特征A：

1.计算特征A对数据集D的经验条件熵H(D|A)v
2.计算特征A的信息增益：
g(D,A)=H(D) – H(D|A)
3.选择信息增益最大的特征作为当前的分裂特征
4.迭代

ID3优点是理论清晰、方法简单、学习能力较强，但也在应用中存在限制：

（1）只能处理分类属性的数据，不能处理连续的数据；
（2）划分过程会由于子集规模过小而造成统计特征不充分而停止；
（3）ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选
择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。

Ref：https://blog.csdn.net/u010089444/article/details/53241218

<h3 id='9'> 2.2 C4.5 原理及应用场景 </h3>

C4.5算法是ID3算法的改进，区别有：

1. C4.5算法中使用信息增益比率来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息的项来惩罚取值
较多的特征，克服了用信息增益选择属性时偏向选择取值多的属性的不足。
2. 在树构造过程中进行剪枝。合并相邻的无法产生大量信息增益的叶节点，消除过渡匹配问题。
3. C4.5算法既能处理标称型数据，又能连续型数据。能够处理具有缺失属性值的训练数据。

缺点：

1. 算法低效，在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效
2. 内存受限，只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

<h3 id='10'> 2.3 CART中的分类树 原理及应用场景 </h3>

CART（Classification And Regression Tree）算法既可以用于创建分类树，也可以用于创建回归树。CART算法的重要特点包含以下三个方面：

1. 二分(Binary Split)：在每次判断过程中，都是对样本数据进行二分。CART算法是一种二分递归分割技术，把当前样
本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。
由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分
2. 单变量分割(Split Based on One Variable)：每次最优划分都是针对单个变量。
3. 剪枝策略：CART算法的关键点，也是整个Tree-Based算法的关键步骤。剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。
有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够
保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。

如果待预测分类是离散型数据，则CART生成分类决策树。
如果待预测分类是连续性数据，则CART生成回归决策树。

Ref：https://blog.csdn.net/u010089444/article/details/53241218

实例：https://zhuanlan.zhihu.com/p/30155789

<h2 id='11'> 3. CART中的回归树原理（Regression tree） </h2>

实际上，回归树总体流程类似于分类树，分枝时穷举每一个特征的每一个阈值，来寻找最优切分特征j和最优切分点s，衡量的方法是平方误差最小化。
分枝直到达到预设的终止条件(如叶子个数上限)就停止。

当然，处理具体问题时，单一的回归树肯定是不够用的。可以利用集成学习中的boosting框架，对回归树进行改良升级，得到的新模型就是
提升树（Boosting Decision Tree），在进一步，可以得到梯度提升树（Gradient Boosting Decision Tree，GBDT），再进一步可以升级到XGBoost。

Ref：https://juejin.im/post/5a7eb1f06fb9a0636108710a

https://plushunter.github.io/2017/01/15/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97%EF%BC%884%EF%BC%89%EF%BC%9A%E5%86%B3%E7%AD%96%E6%A0%91/

<h2 id='12'> 4. 决策树防止过拟合手段 </h2>

产生过度拟合问题的原因：

样本问题
构建决策树的方法问题

如何解决过度拟合数据问题的发生：

合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树
剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。

剪枝是一个简化过拟合决策树的过程。有两种常用的剪枝方法：

先剪枝（prepruning）：通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类
后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，
该叶子的类标号用该结点子树中最频繁的类标记。后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类
别通过大多数原则(majority class criterion)确定。

<h2 id='13'> 5. 模型评估 </h2>

自助法（bootstrap）：
训练集是对于原数据集的有放回抽样，如果原始数据集N，可以证明，大小为N的自助样本大约包含原数据63.2%的记录。当N充分大的时候，1-（1-1/N）^(N) 概率逼近 1-e^(-1)=0.632。抽样 b 次，产生 b 个bootstrap样本，则，总准确率为（accs为包含所有样本计算的准确率）：

准确度的区间估计：

将分类问题看做二项分布，则有：
令 X 为模型正确分类，p 为准确率，X 服从均值 Np、方差 Np（1-p）的二项分布。acc=X/N为均值 p，方差 p（1-p）/N 的二项分布。acc 的置信区间：

[图片上传失败...(image-2ff48a-1554299342213)]

<h2 id='14'> 6. sklearn参数详解，Python绘制决策树 </h2>

<h3 id='15'> 6.1 sklearn参数详解 </h3>

DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

参数含义：

criterion:string类型，可选（默认为"gini"）

衡量分类的质量。支持的标准有"gini"代表的是Gini impurity(不纯度)与"entropy"代表的是information gain（信息增益）。

splitter:string类型，可选（默认为"best"）

一种用来在节点中选择分类的策略。支持的策略有"best"，选择最好的分类，"random"选择最好的随机分类。

max_features:int,float,string or None 可选（默认为None）

在进行分类时需要考虑的特征数。

1.如果是int，在每次分类是都要考虑max_features个特征。
2.如果是float,那么max_features是一个百分率并且分类时需要考虑的特征数是int(max_features*n_features,其中n_features是训练完成时发特征数)。
3.如果是auto,max_features=sqrt(n_features)
4.如果是sqrt,max_features=sqrt(n_features)
5.如果是log2,max_features=log2(n_features)
6.如果是None，max_features=n_features

注意：至少找到一个样本点有效的被分类时，搜索分类才会停止。

max_depth:int or None,可选（默认为"None"）

表示树的最大深度。如果是"None",则节点会一直扩展直到所有的叶子都是纯的或者所有的叶子节点都包含少于min_samples_split个样本点。忽视max_leaf_nodes是不是为None。

min_samples_split:int,float,可选（默认为2）

区分一个内部节点需要的最少的样本数。
1.如果是int，将其最为最小的样本数。
2.如果是float，min_samples_split是一个百分率并且ceil(min_samples_split*n_samples)是每个分类需要的样本数。ceil是取大于或等于指定表达式的最小整数。

min_samples_leaf:int,float,可选（默认为1）

一个叶节点所需要的最小样本数：
1.如果是int，则其为最小样本数
2.如果是float，则它是一个百分率并且ceil(min_samples_leaf*n_samples)是每个节点所需的样本数。

min_weight_fraction_leaf:float,可选（默认为0）

一个叶节点的输入样本所需要的最小的加权分数。

max_leaf_nodes:int,None 可选（默认为None）

在最优方法中使用max_leaf_nodes构建一个树。最好的节点是在杂质相对减少。如果是None则对叶节点的数目没有限制。如果不是None则不考虑max_depth.

class_weight:dict,list of dicts,“Banlanced” or None,可选（默认为None）

表示在表{class_label:weight}中的类的关联权值。如果没有指定，所有类的权值都为1。对于多输出问题，一列字典的顺序可以与一列y的次序相同。
"balanced"模型使用y的值去自动适应权值，并且是以输入数据中类的频率的反比例。如：n_samples/(n_classes*np.bincount(y))。
对于多输出，每列y的权值都会想乘。
如果sample_weight已经指定了，这些权值将于samples以合适的方法相乘。

random_state:int,RandomState instance or None

如果是int,random_state 是随机数字发生器的种子；如果是RandomState，random_state是随机数字发生器，如果是None，随机数字发生器是np.random使用的RandomState instance.

persort:bool,可选（默认为False）

是否预分类数据以加速训练时最好分类的查找。在有大数据集的决策树中，如果设为true可能会减慢训练的过程。当使用一个小数据集或者一个深度受限的决策树中，可以减速训练的过程。

属性：

feature_importances_ : array of shape = [n_features]

特征重要性。该值越高，该特征越重要。

特征的重要性为该特征导致的评价准则的（标准化的）总减少量。它也被称为基尼的重要性

max_feature_:int

max_features推断值。

n_features_：int

执行fit的时候，特征的数量。

n_outputs_ : int

执行fit的时候，输出的数量。

tree_ : 底层的Tree对象

Ref：官方文档：http://scikit-learn.org/stable/modules/tree.html

<h3 id='16'> 6.2 Python的实现 </h3>

Ref：https://zhuanlan.zhihu.com/p/30744760