python机器学习笔记：深入学习决策树算法原理

　　分类技术（或分类法）是一种根据输入数据建立分类模型的系统方法，分类法的例子包括决策分类法，基于规则的分类法，神经网络，支持向量机和朴素贝叶斯分类法。这些技术都使用一种学习算法（learning algorithm）确定分类模型，该模型能够很好的拟合输入数据中类标号和属性集之间的联系，学习算法得到的模型不仅要很好地拟合输入数据，还要能够正确的预测未知样本的类标号。因此，训练算法的主要目标就是建立具有很好泛化能力模型，即建立能够准确的预测未知样本类标号的模型。

　　那我们首先说一下分类与回归的区别。

回归（regression）

　　回归问题的应用场景（预测的结果是连续的，例如预测明天的温度：23,24,25度等等）

　　所以说回归问题通常是用来预测一个值，如预测房价，未来的天气情况等等，例如一个产品的实际价格为500元，通过回归分析预测值为501元，我们认为这是一个比较好的回归分析。一个比较常见的回归算法是线性回归算法（LR）。另外，回归分析用在神经网络上，其最上层是不需要softmax函数的，而是直接对前一层累加即可。回归是对真实值的一种逼近预测。

分类（classification）

　　分类问题的应用场景（预测的结果是离散的，例如预测明天天气：阴，晴，雨等等）

　　例如判断一幅图片上的动物是一只猫还是一只狗，分类通常是建立在回归之上，分类的最后一层通常要使用softmax函数进行判断其所属类别。分类并没有逼近的概念，最终正确结果只有一个，错误的就是错误的，不会有相近的概念。最常见的分类方法是逻辑回归，或者叫逻辑分类。

如何选择模型呢?（这里借助别人的图来选择分类，回归，聚类，降维）

　　决策数(Decision Tree)在机器学习中也是比较常见的一种算法，属于监督学习中的一种。看字面意思应该也比较容易理解，而作为一个码农，经常不断的敲 if else，其实就已经用到了决策树的思想了，所以相比其他算法比如支持向量机(SVM)或神经网络，似乎决策树感觉“亲切”许多。

决策树算法思想

　　决策树（decision tree）是一个树结构（可以是二叉树或者非二叉树）。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。

　　其中每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放在一个类别。

　　使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

　　举个例子，让我们看一下决策树从根节点开始一步步走到叶子节点：

　　如上图所示，比如小明一家五口人，让我们使用决策树来判断谁喜欢玩电子游戏。一般情况下，在一家人中年龄小的喜欢玩，年龄大的就不那么热爱游戏了，所以我们先做一个判断，年龄是否小于15岁，然后再细分，判断是男孩还是女孩，一般情况下，我们知道男孩比较喜欢玩电子游戏，所以我们再做一个判断，性别是男还是女，最后得到是小明。

　　从这么一个简单的例子，我们可以看出一个决策树的组成，分为三个：根节点；非叶子节点与分支；叶子节点。具体意思如下：

根节点：第一个选择点
非叶子节点与分支：中间过程
叶子节点：最终的决策结果

　　当然我们也发现：一旦构造好了决策树，那么分类或预测任务就很简单了，只需要走一遍即可，但是难点就在于如何构造出来一棵树。构造树需要考虑的问题有很多。

1，决策树学习算法主要由三部分构成

1.1 特征选择

　　特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。

1.2 决策树生成

　　根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。树结构来说，递归结构是最容易理解的方式。

1.3 决策树的剪枝

　　决策树容易过拟合，一般来需要剪枝，缩小树结构规则，缓解过拟合，剪枝技术有预剪枝和后剪枝两种。

预剪枝：边建立决策树边进行剪枝的操作（更实用），预剪枝需要限制深度，叶子节点个数，叶子节点样本数，信息增益量等。
后剪枝：当建立完决策树后来进行剪枝操作，通过一定的衡量标准（叶子节点越多，损失越大）

2，决策实例一

　　决策树表示如下（借用周志华老师西瓜书的图）

　　假如我现在告诉你，我买了一个西瓜，它的特点是纹理是清晰，根蒂是硬挺的瓜，你来给我判断一下是好瓜还是坏瓜，恰好，你构建了一颗决策树，告诉他，没问题，我马上告诉你是好瓜，还是坏瓜？

　　判断步骤如下：

　　根据纹理特征，已知是清晰，那么走下面这条路，红色标记：

　　好了，现在到了第二层，这个时候，由决策树的图，我们可以看到，我们需要知道根蒂的特征是什么了？对是硬挺，于是我们继续走，如下蓝色的图：

　　此时，我们到达叶子结点了，根据上面总结的点，可知，叶子结点代表一种类别，我们从如上决策树中可以知道，这是一个坏瓜！！

　　所以根据上面的例子，非常直观容易的得到了一个实例的类别判断，只要你告诉我各个特征的具体值，决策树的判定过程就相当于树中从跟节点到某一个叶子节点的遍历，每一步如何遍历是由数据各个特征的具体特征属性决定。

　　好了，可能有人要问了，说了这么多，给你训练数据，你的决策树是怎么构建的呢？没有树，谈何遍历，谈何分类？

　　于是构建决策树也就成了最重要的工作！！

　　比如，给我下面的训练数据，我们如何构建出决策树？

　　我们可以从上面的决策树看出，每一次子结点的产生，是由于我在当前层数选择了不同的特征来作为我的分裂因素造成的，比如下面红色三角形表示选择的特征：

　　每一层选择了指定的特征之后，我们就可以继续由该特征的不同属性值进行划分，依次一直到叶子节点。

　　看起来一切很顺利，但是，细心地小伙伴可能会问了，为什么在第一次选择特征分裂的时候，不选择触感呢？而是选择纹理，比如如下：

　　不换成抽干，或者是其他特征呢？为什么选择的是纹理，这是以什么标准来选择特征的？这个问题先留着，让我们再看一个例子

3，决策实例二

　　一天，老师问了个问题，只根据头发和声音怎么判断一位同学的性别。
　　为了解决这个问题，同学们马上简单的统计了8位同学的相关特征，数据如下：

机智的同学A想了想，先根据头发判断，若判断不出，再根据声音判断，于是画了一幅图，如下：
同学A
　　于是，一个简单、直观的决策树就这么出来了。头发长、声音粗就是男生；头发长、声音细就是女生；头发短、声音粗是男生；头发短、声音细是女生。
　　
　　这时又蹦出个同学B，想先根据声音判断，然后再根据头发来判断，如是大手一挥也画了个决策树：
同学B
　　同学B的决策树：首先判断声音，声音细，就是女生；声音粗、头发长是男生；声音粗、头发长是女生。

　　那么问题来了：同学A和同学B谁的决策树好些？计算机做决策树的时候，面对多个特征，该如何选哪个特征为最佳的划分特征？下面我们就要说一下决策树的特征选择了。

4，决策树的特征选择

　　划分数据集的大原则是：将无序的数据变得更加有序。
　　我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。于是我们这么想，如果我们能测量数据的复杂度，对比按不同特征分类后的数据复杂度，若按某一特征分类后复杂度减少的更多，那么这个特征即为最佳分类特征。

　　我们的目标是：通过一种衡量标准来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当做根节点，以此类推。而衡量标准就是：熵
　　Claude Shannon 定义了熵（entropy）和信息增益(information gain)。下面先介绍一下概念：

5，信息论基础知识

5.1 熵（entropy）

　　在信息论与概率论中，熵（entropy）用于表示“随机变量不确定性的度量”

　　（解释一下：说白了就是物体内部的混乱程度，比如杂货市场里面什么都有，那肯定乱，而专卖店里面只卖一个牌子，那就稳定了）

　　在决策树的算法中，熵是一个非常非常重要的概念，一件事发生的概率越小，我们说它蕴含的信息量越大，比如：我们听到女人怀孕了，是不是不奇怪，但是某天听到那个男人怀孕了，是不是？？？？

　　所以下面我们说一下信息量熵的定义。

　　设X是一个有限状态的离散型随机变量，其概率分布为：

　　则随机变量X的熵定义为：

　　其中 n代表X的 n 种不同的离散取值，而 pi代表了X取值为 i 的概率，log是以2为底的对数。

　　注意这里，为什么对熵定义取负号呢？首先，既然Pi是概率分布，那么pi的取值范围肯定在（0， 1）之间，而log的底数肯定是大于1的，所以是下面红色的log曲线，而在x属于0到1之间，y是负数，取个负号则熵就成为正的了。

　　熵越大，则随机变量的不确定性越大。

　　当随机变量只有0和1两种取值的时候，假设P（X=1）=p，则有：

　　从而有：

　　从而可知，当p=0.5时，熵取值最大，随机变量不确定性最大。如图：

5.2 条件熵（conditional entropy）

　　随机变量X给定的条件下，Y的条件概率分布的熵对X的数学期望，其数学推导如下：

　　随机变量Y的条件熵H（Y|X）定义为：

　　其中：

　　条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。注意一下，条件熵中X也是一个变量，意思是在一个变量X的条件下（变量X的每个值都会取到），另一个变量Y的熵对X的期望。

5.3 信息增益（information gain）

　　信息增益表示的是：得知特征X的信息而使得类Y的信息的不确定性减少的程度。简单说，就是当我们用另一个变量X对原变量Y分类后，原变量Y的不确定性就会减少了（即熵值减少）。而熵就是不确定性，不确定程度减少了多少其实就是信息增益，这就是信息增益的由来。

　　所以信息增益的具体定义如下：

　　特征A对训练数据集D的信息增益g(D，A）定义为集合D的经验熵H（D）与特征A给定条件下D的经验条件熵H（D/A）之差，即：

　　一般地，熵H(Y)与条件熵H(Y|X)之差成为互信息（mutual information）。

　　根据信息增益准则而进行特征选择的方法是：对训练数据集D，计算其每个特征的信息增益，并比他们大小，从而选择信息增益最大的特征。

　　假设训练数据集为D，样本容量为|D|，由k个类别C_k，|C_k|为类别C_k的样本个数，某一特征A由n个不同的取值a1,a2,a3,…..an。根据特征A的取值可将数据集D划分为n个子集D1，D2…..D_n，|D_i|为D_i的样本个数，并记子集Di中属于类C_k，的样本的集合为D_ik，|D_ik|为D_ik的样本个数。

　　则信息增益的算法如下：

输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)

（1）计算数据集D的经验熵H(D)。

（2）计算特征A对数据集D的经验条件H（D|A）

（3）计算信息增益

5.4 信息增益比（information gain ratio）

　　以信息增益作为特征选择准则，会存在偏向于选择取值较多的特征的问题，可以采用信息增益比对这个问题进行校正。

　　特征A对训练数据集D的信息增益比定义为其信息增益与训练集D关于特征A的值的熵之比，即：

其中：

6，计算实例二的信息增益

　　我们下面接着案例二来继续，首先计算未分类前的熵，总共有8位同学，男生3位，女生5位。

熵（总）=-3/8*log2(3/8)-5/8*log2(5/8)=0.9544

　　接着分别计算同学A和同学B分类后信息熵。
　　同学A首先按头发分类，分类后的结果为：长头发中有1男3女。短头发中有2男2女。

熵（同学A长发）=-1/4*log2(1/4)-3/4*log2(3/4)=0.8113
熵（同学A短发）=-2/4*log2(2/4)-2/4*log2(2/4)=1
熵（同学A）=4/8*0.8113+4/8*1=0.9057

信息增益（同学A）=熵（总）-熵（同学A）=0.9544-0.9057=0.0487
　　同理，按同学B的方法，首先按声音特征来分，分类后的结果为：声音粗中有3男3女。声音细中有0男2女。

熵（同学B声音粗）=-3/6*log2(3/6)-3/6*log2(3/6)=1
熵（同学B声音粗）=-2/2*log2(2/2)=0
熵（同学B）=6/8*1+2/8*0=0.75

信息增益（同学B）=熵（总）-熵（同学A）=0.9544-0.75=0.2087

　　按同学B的方法，先按声音特征分类，信息增益更大，区分样本的能力更强，更具有代表性。
以上就是决策树ID3算法的核心思想。

　　代码如下：

from math import log
import operator

# 计算数据的熵（entropy）
def calcShannonRnt(dataSet):
    # 数据条数，计算数据集中实例的总数
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        # 每行数据的最后一个类别（也就是标签）
        currentLable = featVec[-1]
        if currentLable not in labelCounts.keys():
            labelCounts[currentLable] = 0
        # 统计有多少个类以及每个类的数量
        labelCounts[currentLable]  += 1
    shannonEnt = 0.0
    for key in labelCounts:
        # 计算单个类的熵值
        prob = float(labelCounts[key]) / numEntries
        # 累加每个类的熵值
        shannonEnt -= prob * log(prob , 2)
    return shannonEnt

# 创建数据集
def createDataSet():
    dataSet = [[\'Long\', \'Think\', \'male\'],
               [\'Short\', \'Think\', \'male\'],
               [\'Short\', \'Think\', \'male\'],
               [\'Long\', \'Thin\', \'female\'],
               [\'Short\', \'Thin\', \'female\'],
               [\'Short\', \'Think\', \'female\'],
               [\'Long\', \'Think\', \'female\'],
               [\'Long\', \'Think\', \'female\']]
    labels = [\'hair\', \'voice\']
    return dataSet,labels

# 按照给定特征划分数据集
def splitDataSet(dataSet,axis,value):
    \'\'\'

    :param dataSet: 待划分的数据集
    :param axis: 划分数据集的特征
    :param value: 特征的返回值
    :return:
    \'\'\'
    retDataSet = []
    for featVec in dataSet:
        # 如果发现符合要求的特征，将其添加到新创建的列表中
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)

    return retDataSet

# 选择最好的数据集划分方式
def chooseBestFeatureTpSplit(dataSet):
    \'\'\'
        此函数中调用的数据满足以下要求
        1，数据必须是一种由列表元素组成的列表，而且所有列表元素都要具有相同的数据长度
        2，数据的最后一列或者实例的最后一个元素是当前实例的类别标签
    :param dataSet:
    :return:
    \'\'\'
    numFeatures = len(dataSet[0]) - 1
    # 原始的熵
    baseEntropy = calcShannonRnt(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 * calcShannonRnt(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.items(),
                              key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

# 创建树的函数代码
def createTree(dataSet,labels):
    \'\'\'

        :param dataSet:  输入的数据集
        :param labels:  标签列表（包含了数据集中所有特征的标签）
        :return:
        \'\'\'
    # classList 包含了数据集中所有类的标签
    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 = chooseBestFeatureTpSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    # 字典myTree存储了树的所有信息，这对于后面绘制树形图很重要
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    # 得到列表包含的所有属性值
    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

if __name__ == \'__main__\':
    myData,labels = createDataSet()
    print(myData)
    print(labels)
    
    myTree = createTree(myData,labels)
    print(myTree)
    
\'\'\'
[[\'Long\', \'Think\', \'male\'], [\'Short\', \'Think\', \'male\'], [\'Short\', \'Think\', \'male\'], [\'Long\', \'Thin\', \'female\'], [\'Short\', \'Thin\', \'female\'], [\'Short\', \'Think\', \'female\'], [\'Long\', \'Think\', \'female\'], [\'Long\', \'Think\', \'female\']]
[\'hair\', \'voice\']
{\'voice\': {\'Think\': {\'hair\': {\'Long\': \'female\', \'Short\': \'male\'}}, \'Thin\': \'female\'}}
\'\'\'

　　这个结果的意思是：首先按声音分类，声音细为女生；然后再按头发分类：声音粗，头发短为男生；声音粗，头发长为女生。
　　这个结果也正是同学B的结果。

　　使用Python中Matplotlib绘图如下（可以看出与B同学的结果一模一样）：

　　画图的代码如下：

import matplotlib.pyplot as plt

# 定义文本框和箭头格式（树节点格式的常量）
decisionNode = dict(boxstyle=\'sawtooth\',fc=\'0.8\')
leafNode = dict(boxstyle=\'round4\',fc=\'0.8\')
arrows_args = dict(arrowstyle=\'<-\')

# 绘制带箭头的注解
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=arrows_args)


# 在父子节点间填充文本信息
def plotMidText(cntrPt,parentPt,txtString):
    xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0]
    yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]
    createPlot.ax1.text(xMid,yMid,txtString, va="center", ha="center", rotation=30)

def plotTree(myTree,parentPt,nodeTxt):
    # 求出宽和高
    numLeafs = getNumLeafs(myData)
    depth = getTreeDepth(myData)
    firstStides = list(myTree.keys())
    firstStr = firstStides[0]
    # 按照叶子结点个数划分x轴
    cntrPt = (plotTree.xOff + (0.1 + float(numLeafs)) /2.0/plotTree.totalW,plotTree.yOff)
    plotMidText(cntrPt,parentPt,nodeTxt)
    plotNode(firstStr,cntrPt,parentPt,decisionNode)
    secondDict = myTree[firstStr]
    # y方向上的摆放位置 自上而下绘制，因此递减y值
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__  == \'dict\':
            plotTree(secondDict[key],cntrPt,str(key))
        else:
            plotTree.xOff = plotTree.xOff + 1.0 / plotTree.totalW  # x方向计算结点坐标
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)  # 绘制
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))  # 添加文本信息
    plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD  # 下次重新调用时恢复y

def myTree():
    treeData = {\'voice\': {\'Think\': {\'hair\': {\'Long\': \'female\', \'Short\': \'male\'}}, \'Thin\': \'female\'}}
    return treeData

# 获取叶子节点的数目
def getNumLeafs(myTree):
    # 初始化结点数
    numLeafs = 0
    firstSides = list(myTree.keys())
    # 找到输入的第一个元素，第一个关键词为划分数据集类别的标签
    firstStr = firstSides[0]
    secondDect = myTree[firstStr]
    for key in secondDect.keys():
        # 测试节点的数据类型是否为字典
        if type(secondDect[key]).__name__ == \'dict\':
            numLeafs += getNumLeafs(secondDect[key])
        else:
            numLeafs +=1
    return numLeafs

# 获取树的层数
def getTreeDepth(myTree):
    maxDepth = 0
    firstSides = list(myTree.keys())
    firstStr = firstSides[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 createPlot(inTree):
    # 创建一个新图形并清空绘图区
    fig = plt.figure(1,facecolor=\'white\')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)  # no ticks
    # createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5 / plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree, (0.5, 1.0), \'\')
    plt.show()


if __name__ == \'__main__\':
    myData  = myTree()
    myData[\'voice\'][3] = \'maybe\'
    print(myData)
    # LeafNum = getNumLeafs(myData)
    # TreeDepth = getTreeDepth(myData)
    # print(LeafNum)
    # print(TreeDepth)
    createPlot(myData)

　　补充说明：判定分类结束的依据是，若按某特征分类后出现了最终类（男或女），则判定分类结束。使用这种方法，在数据比较大，特征比较多的情况下，很容易造成过拟合，于是需进行决策树枝剪，一般枝剪方法是当按某一特征分类后的熵小于设定值时，停止分类。

决策树的生成算法介绍

　　划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

　　决策树的生成算法由很多变形，这里简单说一下几种经典的实现算法：ID3算法，C4.5算法和CART算法。这些算法的主要区别在于分类结点熵特征选择的选取标准不同，下面了解一下算法的具体实现过程。

一：ID3算法

　　ID3算法所采用的度量标准就是我们前面提到的“信息增益”。当属性a的信息增益最大时，则意味着用a属性划分，其所获得的“纯度”提升最大，我们所要做的，就是找到信息增益最大的属性。

　　ID3算法的核心是在决策树的各个节点上应用信息增益准则进行特征选择，具体的做法是：

从根节点上开始，对结点计算所有可能特征的信息增益，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值构建子节点；
对于子节点递归的调用以上方法，构建决策树；
直到所有特征的信息增益均很小或者没有特征可选择的时候为止。

　　ID3算法具体的算法过程如下：

　　输入的是 m 个样本，样本输出集合为D，每个样本有 n 个离散特征，特征集合为A，输出为决策树 T。

1，初始化信息增益的阈值€
2，判断样本是否为同一类输出 Di，如果是则返回单节点树T，标记类别为Di
3，判断特征是否为空，如果是则返回单节点树T，标记类别为样本值红输出类别D实例数最多的类别
4，计算A 中的各个特征（一共 n 个）对输出D的信息增益，选择信息增益最大的特征 Ag
5，如果Ag的信息增益小于阈值€，则返回单节点树T，标记类别为样本中输出类别D实例树最多的类别
6，否则，按特征Ag 的不同取值 Agi 将对应的样本输出D分成不同的类别 Di，每个类别产生一个子节点。对应特征为 Agi，返回增加了节点的数 T
7，对于所有的子节点，令 D= Di，A=A-{Ag} 递归调用 2~6 步，得到子树Ti并返回

　　ID3算法存在的缺点：

　　1. ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性，在有些情况下这类属性可能不会提供太多有价值的信息。
　　2. ID3算法只能对描述属性为离散型属性的数据集构造决策树。

　　3. ID3算法对于缺失值的情况没做考虑。

　　4.没有考虑过拟合的问题。

1.1 信息增益（Info-Gain）和信息增益比（Gain-ratio）的关系和差异

　　参考文献：https://www.zhihu.com/question/22928442

　　对于缺点一，我们知道当信息增益偏向于选择取值较多的特征，则容易过拟合。如何理解呢？就是说什么叫取值越多会导致信息增益越大？这里使用案例（天气预报数据集）：

　　在这个例子中，最后一列是否出去玩，这里作为我们所要预测的标记值（label），而前四列就是我们需要借助的数据，每一列都是一个特征（feature）。对于这四种划分方式，那么问题就是谁来当根节点呢？

　　下面我们对四个特征逐一分析，

　　我们使用信息增益来算。初始状态下，label列总共为 14列，有9个yes和5个no，所以label列初始信息熵为：

　　假设我们先划分 outlook 这一列，分为sunny ， rain， overcast 三类，计算过程在后面代码里面，这里直接粘贴结果：

　　根据数值统计，Outlook取值分别为sunny ， rain， overcast 三类的概率分别为5/14 5/14 4/14考虑到每个类别下对应的label不同，可以计算划分后的信息比：

　　信息增益：系统的熵值由原来的0.940 下降到0.693，增益为 0.247。

　　我们可以用同样的方式来计算其他特征的信息增益，那么我们选择最大的就可以了，相当于我们遍历了一遍特征，找出根节点，然后继续找其余的特征的根节点。

　　在ID3算法中，信息增益（Info-Gain）越大，划分越好，决策树算法本质上就是找出每一列的最佳划分以及不同列划分的先后顺序以及排布。

　　回到题中的问题，C4.5 中使用信息增益率（Gain-ration），ID3算法使用信息增益（Info-Gain），二者有何区别？

　　根据上面的例子，Info-Gain在面对类别较少的离散数据时效果较好，上面的 Outlook，temperature等数据都是离散数据，而且每个类别都要一定数量的样本，这种情况下使用ID3与C4.5的区别并不大。但如果面对连续的数据（如体重，身高，年龄，距离等），或者每列数据没有明显的类别之分（最极端的例子就是该列的数据都是独一无二），在这种情况下，我们分析信息增益（Info-Gain）的效果：

　　根据公式：

　　E（S）为初始 label 列的熵，并未发生变换，则 IGain(S, A)的大小取决于 E(A)的大小，E(A)越小，IGain(S, A)越大，而根据前文例子：

　　若某一列数据没有重复，ID3算法倾向于把每个数据自成一类，此时：

　　注意这里E(Sv)的计算（值为什么等于1 ，熵为什么等于0）：

　　（这里我太蠢了，混淆了概念，我们这里其实计算的是某一划分下对应的右边label列的熵，最容易理解的例子就是上面我们算的基于天气的划分中overcast的计算，如果n行分为n类，则右边label列只对应一个元素，那么熵为0。我还将E(Sv)写出来找原因。看来这个例子真的是个好例子，我真的。。。。）

　　这样E(A) 为最小，IGain(S,A)最大，程序会倾向于选择这种划分，这种划分效果极差。

　　所以为了解决这个问题，引入了信息增益率（Gain-ratio）的概念，计算方式如下：

　　这里Info为划分行为带来的信息，信息增益率如下计算：

　　这样就能减轻了划分行为本身的影响。

　　所以为了改进决策树，又提出了C4.5算法和CART算法。

　　注意：这里还有一个坑！就是在计算特征的每个取值下的熵的时候，需要估计每个类别k的概率，我们使直接用频率去近似的概率。

　　这个我觉得有必要引出来说一下（个人拙见）：根据大数定理，只有当样本数足够多的时候，频率才可以准确的近似概率。也就是说，样本数越少，对概率的估计结果的方差就会越大（想象一下做抛硬币实验来近似正面向上的概率，如果只抛两次，那么得到的正面向上的概率可能会非常离谱，而如果抛一万次，不论何时何地几乎总能得到近似0.5的概率）。而方差大概会导致什么结果呢？显然就会导致该取值下的类别错估计为非均匀分布，而非均匀分布，不就是导致该取值下的熵更小。

　　所以说，ID3决策树，或者说信息增益（条件熵）并不是说一定会偏向取值多的特征，而是数据集的不充分以及客观存在的大数定理导致取值多的特征在计算条件熵时容易估计出偏小的条件熵。如果数据集足够大，均分到某特征的每个取值的样本足够多，那么这时信息增益是没有偏向性的。

　　计算熵的小公式如下：

from math import log

# 初始熵值
Entropy_base = -(9 / 14) * log(9 / 14, 2) - (5 / 14) * log(5 / 14, 2)
# outlook=sunny
Entropy_Outlook_sunny = -(2 / 5) * log(2 / 5, 2) - (3 / 5) * log(3 / 5, 2)
# outlook=overcost
Entropy_Outlook_overcost = -(4 / 4) * log(4 / 4, 2)
# outlook=rainy
Entropy_Outlook_rainy = -(3 / 5) * log(3 / 5, 2) - (2 / 5) * log(2 / 5, 2)
print(Entropy_Outlook_sunny, Entropy_Outlook_overcost, Entropy_Outlook_rainy)
# 0.9709505944546686 -0.0 0.9709505944546686
Entropy_Outlook = (5 / 14) * Entropy_Outlook_sunny + (4 / 14) * Entropy_Outlook_overcost + (
        5 / 14) * Entropy_Outlook_rainy
print(\'Entropy_Outlook:\', Entropy_Outlook)
Entropy_test = -(1 / 2) * log(1 / 2, 2) - (1 / 2) * log(1 / 2, 2)
Entropy_test1 = -(1 / 3) * log(1 / 3, 2) - (1 / 3) * log(1 / 3, 2) - (1 / 3) * log(1 / 3, 2)
Entropy_test2 = -(1 / 4) * log(1 / 4, 2) - (1 / 4) * log(1 / 4, 2) - (1 / 4) * log(1 / 4, 2) - (1 / 4) * log(1 / 4, 2)
print(Entropy_test, Entropy_test1, Entropy_test2)
# 1.0     1.584962500721156     2.0

　　ID3算法代码实践博文：请点击我

二：C4.5算法

　　ID3算法的作者昆兰基于上面的不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢？那是因为决策树当时太火爆了，它的ID3一出来，别人二次创新，很快就占了ID4，ID5，所以他另辟蹊径，取名C4.5 算法，后来的进化版为C4.5算法。

　　C4.5算法与ID3算法的区别主要是在于它在生产决策树的过程中，使用信息增益比来进行特征选择。

　　实际上，信息增益准则对于可取值数目较多的属性会有所偏好，为了减少这种偏好可能带来的不利影响，C4.5决策树算法不直接使用信息增益，而是使用“信息增益率”来选择最优划分属性，信息增益率定义为：

　　其中，分子为信息增益，分母为属性X的熵。

　　需要注意的是，增益率准则对可取值数目较少的属性有所偏好。所以一般这样选取划分属性：先从候选属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。

　　虽然C4.5 改善了ID3算法的几个问题，仍然有优化的空间。

1，由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要有两种：一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
2，C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3，C3.5算法只能用于分类，如果将决策树用于回归的话，可以扩大它的使用范围。
4，C4.5算法由于使用了熵模型，里面有大量的耗时的对数运算，如果是连续纸还有大量的排序运算。如果能够加以模型简化可以减少运算强度但不牺牲太多准确性的话，那就更好了。

三：CART算法

　　分类与回归树（classification and regression tree,CART）与C4.5算法一样，由ID3算法演化而来。CART假设决策树是一个二叉树，它通过递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。

　　上面所说的C4.5的几个缺点在CART树里面加以改进。所以如果不考虑集成学习的话，在普通的决策树算法里，CART算法就是比较优的算法了。sklearn的决策树使用的也是CART算法。

　　CART算法中，对于回归树，采用的是平方误差最小化准则；对于分类树，采用基尼指数最小化准则。

平方误差最小化

　　假设已将输入空间划分为M个单元R1，R2……Rm，并且在每个单元Rm上有一个固定的输出值Cm，于是回归树可以表示为：

　　当输入空间的划分确定时，可以用平方误差来表示回归树对于训练数据的预测误差。

基尼指数

　　分类问题中，假设有K个类别，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：

　　CART算法代码实践博文：请点击我

决策树的优缺点分析

优点：

易于理解和解释，甚至比线性回归更直观；
与人类做决策思考的思维习惯契合；
模型可以通过树的形式进行可视化展示；
可以直接处理非数值型数据，不需要进行哑变量的转换，甚至可以直接处理含有缺失值的数据；

缺点：

对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
决策分类的因素取决于更多变量的复杂组合时；
模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同

完整代码及其数据，请移步小编的GitHub

　　传送门：请点击我

　　如果点击有误：https://github.com/LeBron-Jian/MachineLearningNote

参考：
– Machine Learning in Action
– 统计学习方法

https://zhuanlan.zhihu.com/p/26703300

https://www.cnblogs.com/pinard/p/6050306.html

本文链接：https://www.cnblogs.com/wj-1314/p/9428494.html