一.简介

决策树是一种基于树结构来进行决策的分类算法，我们希望从给定的训练数据集学得一个模型（即决策树），用该模型对新样本分类。决策树可以非常直观展现分类的过程和结果，一旦模型构建成功，对新样本的分类效率也相当高。

最经典的决策树算法有ID3、C4.5、CART，其中ID3算法是最早被提出的，它可以处理离散属性样本的分类，C4.5和CART算法则可以处理更加复杂的分类问题，本文重点介绍ID3算法

二.基于买西瓜这个场景建立模型

1.引入例子

举个例子：夏天买西瓜时，我一般先选瓜皮有光泽的（新鲜），再拍一拍选声音清脆的（成熟），这样挑出来的好瓜的可能就比较大了。那么我挑西瓜的决策树是这样的

那么我们是如何挑选最优划分的属性的呢

通过学习我们可以得知

2.利用信息增益选择最优划分属性

样本有多个属性，该先选哪个样本来划分数据集呢？

原则是随着划分不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一分类，即“纯度”越来越高。先来学习一下“信息熵”和“信息增益”。

下面引入两个概念

信息熵（information entropy）
样本集合D中第k类样本所占的比例（k=1,2,...,|Y|），|Y|为样本分类的个数，则D的信息熵为：

Ent(D)的值越小，则D的纯度越高。直观理解一下：假设样本集合有2个分类，每类样本的比例为1/2，Ent(D)=1；只有一个分类，Ent（D）= 0，显然后者比前者的纯度高。

在西瓜样本集中，共有17个样本，其中正样本8个，负样本9个，样本集的信息熵为：

信息增益（information gain）
使用属性a对样本集D进行划分所获得的“信息增益”的计算方法是，用样本集的总信息熵减去属性a的每个分支的信息熵与权重（该分支的样本数除以总样本数）的乘积，通常，信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。因此，优先选择信息增益最大的属性来划分。设属性a有V个可能的取值，则属性a的信息增益为：

西瓜样本集中，以属性“色泽”为例，它有3个取值{青绿、乌黑、浅白}，对应的子集（色泽=青绿）中有6个样本，其中正负样本各3个，（色泽=乌黑）中有6个样本，正样本4个，负样本2个，（色泽=浅白）中有5个样本，正样本1个，负样本4个。

​

就像这样我们计算另外几个属性的信息增益，选择信息增益最大的属性作为根节点来进行划分，然后再对每个分支做进一步划分。

现在我们来实现下这第一步

3.代码实现计算信息增益选择划分。

#导入数据以及相关包
import pandas as pd
import numpy as np
from collections import Counter
from math import log2
fr = open(r'D:\baidu\watermalon.txt',encoding="utf-8")
listWm = [inst.strip().split(' ') for inst in fr.readlines()]
print(listWm)

看到数据如下

根据之前所学的算下信息熵

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
    for key in labelCounts:  # 计算信息熵
        prob = float(labelCounts[key]) / numEntries
        shannonEnt = shannonEnt - prob * log(prob, 2)
    return shannonEnt
print(calcShannonEnt(listWm))

先定义一个划分数据集的函数

# 划分数据集，axis:按第几个属性划分，value:要返回的子集对应的属性值
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    featVec = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

再通过计算当前属性的信息增益选择最恰当的划分的属性

# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 属性的个数
    baseEntropy = calcShannonEnt(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 * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):  # 选择信息增益最大的属性
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
print(chooseBestFeatureToSplit(listWm))

输出为三，即最先应该选择序号为三的那一列属性作为分割

4.递归构建决策树

通常一棵决策树包含一个根节点、若干个分支节点和若干个叶子节点，叶子节点对应决策结果（如好瓜或坏瓜），根节点和分支节点对应一个属性测试（如色泽=？），每个结点包含的样本集合根据属性测试的结果划分到子节点中。

在上一节中，我们对整个训练集选择的最优划分属性就是根节点，第一次划分后，数据被向下传递到树分支的下一个节点，再这个节点我们可以再次划分数据，构建决策树是一个递归的过程，而递归结束的条件是：所有属性都被遍历完，或者每个分支下的所有样本都属于同一类。

还有一种情况就是当划分到一个节点，该节点对应的属性取值都相同，而样本的类别却不同，这时就把当前节点标记为叶节点，并将其类别设为所含样本较多的类别。例如：当划分到某一分支时，节点中有3个样本，其最优划分属性为色泽，而色泽的取值只有一个“浅白”，3个样本中有2个好瓜，这时我们就把这个节点标记为叶节点“好瓜”。

import operator  # 此行加在文件顶部
 
# 通过排序返回出现次数最多的类别
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]
 
 
# 递归构建决策树
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])  # 已经选择的特征不再参与分类
    featValues = [example[bestFeat] for example in dataSet]
    uniqueValue = set(featValues)  # 该属性所有可能取值，也就是节点的分支
    for value in uniqueValue:  # 对每个分支，递归构建树
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(
            splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

最后使用数据测试一下算法，。因为生成的树是中文表示的，因此使用json.dumps(）方法来打印结果。如果是不含中文，直接print即可。

# -*- coding: cp936 -*-
import trees
import json
 
fr = open(r'C:\Python27\py\DecisionTree\watermalon.txt')
 
listWm = [inst.strip().split('\t') for inst in fr.readlines()]
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
Trees = trees.createTree(listWm, labels)
 
print json.dumps(Trees, encoding="cp936", ensure_ascii=False)

结果如下

{"纹理": {"模糊": "否", "清晰": {"根蒂": {"稍蜷": {"色泽": {"乌黑": {"触感": {"软粘": "否", "硬滑": "是"}}, "青绿": "是"}}, "蜷缩": "是", "硬挺": "否"}}, "稍糊": {"触感": {"软粘": "是", "硬滑": "否"}}}}

5.使用Matplotlib绘制决策树

字典形式的决策树仍然不易理解，下面我们利用Matplotlib库的annotate（注释）模块绘制决策树，就可以很直观的看出决策树的结构

# -*- coding: cp936 -*-
import matplotlib.pyplot as plt
 
# 设置决策节点和叶节点的边框形状、边距和透明度，以及箭头的形状
decisionNode = dict(boxstyle="square,pad=0.5", fc="0.9")
leafNode = dict(boxstyle="round4, pad=0.5", fc="0.9")
arrow_args = dict(arrowstyle="<-", connectionstyle="arc3", shrinkA=0,
                  shrinkB=16)
 
 
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(unicode(nodeTxt, 'cp936'), xy=parentPt,
                            xycoords='axes fraction',
                            xytext=centerPt, textcoords='axes fraction',
                            va="top", ha="center", bbox=nodeType,
                            arrowprops=arrow_args)
 
 
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = myTree.keys()[0]
    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 = 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 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, unicode(txtString, 'cp936'))
 
 
def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = myTree.keys()[0]
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW,
              plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    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
            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
 
 
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.xOff = -0.5 / plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree, (0.5, 1.0), '')
    plt.show()
# -*- coding: cp936 -*-
import trees
import treePlotter
import json
 
fr = open(r'C:\Python27\py\DecisionTree\watermalon.txt')
 
listWm = [inst.strip().split('\t') for inst in fr.readlines()]
labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
Trees = trees.createTree(listWm, labels)
 
print json.dumps(Trees, encoding="cp936", ensure_ascii=False)
 
treePlotter.createPlot(Trees)

三、ID3、C4.5和CART的算法代码实现(使用Sklearn)

1.导入相关库

#导入相关库
import pandas as pd
import graphviz 
from sklearn.model_selection import train_test_split
from sklearn import tree

f = open('watermelon2.csv','r')
data = pd.read_csv(f)

x = data[["色泽","根蒂","敲声","纹理","脐部","触感"]].copy()
y = data['好瓜'].copy()
print(data)

特征函数数值化，决策树学习，最后将得到的决策树绘出

#将特征值数值化
x = x.copy()
for i in ["色泽","根蒂","敲声","纹理","脐部","触感"]:
    for j in range(len(x)):
        if(x[i][j] == "青绿" or x[i][j] == "蜷缩" or data[i][j] == "浊响" \
           or x[i][j] == "清晰" or x[i][j] == "凹陷" or x[i][j] == "硬滑"):
            x[i][j] = 1
        elif(x[i][j] == "乌黑" or x[i][j] == "稍蜷" or data[i][j] == "沉闷" \
           or x[i][j] == "稍糊" or x[i][j] == "稍凹" or x[i][j] == "软粘"):
            x[i][j] = 2
        else:
            x[i][j] = 3
            
y = y.copy()
for i in range(len(y)):
    if(y[i] == "是"):
        y[i] = int(1)
    else:
        y[i] = int(-1) 
#需要将数据x，y转化好格式，数据框dataframe，否则格式报错
x = pd.DataFrame(x).astype(int)
y = pd.DataFrame(y).astype(int)
print(x)
print(y)
x_train, x_test, y_train, y_test = train_test_split(x,y,test_size=0.2)
print(x_train)
#决策树学习
clf = tree.DecisionTreeClassifier(criterion="entropy")                    #实例化 
clf = clf.fit(x_train, y_train) 
score = clf.score(x_test, y_test)
print(score)

# 加上Graphviz2.38绝对路径

import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
feature_name = ["色泽","根蒂","敲声","纹理","脐部","触感"]
dot_data = tree.export_graphviz(clf ,feature_names= feature_name,class_names=["好瓜","坏瓜"],filled=True,rounded=True,out_file =None) 
graph = graphviz.Source(dot_data) 

四.C4.5算法

1.C4.5算法简介

C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进：
  （1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性 作为分裂属性的不足；
  （2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
  （3）构造决策树之后进行剪枝操作；
  （4）能够处理具有缺失属性值的训练数据。

2.分裂属性的选择

1. 信息增益率
   分裂属性选择的评判标准是决策树算法之间的根本区别。区别于ID3算法通过信息增益选择分裂属性，C4.5算法通过信息增益率选择分裂属性。
     属性A的“分裂信息”(split information)：

其中，训练数据集S通过属性A的属性值划分为m个子数据集， |Sj|表示第j个子数据集中样本数量， |S|表示划分之前数据集中样本总数量。
  通过属性A分裂之后样本集的信息增益：

通过属性A分裂之后样本集的信息增益率：

通过C4.5算法构造决策树时，信息增益率最大的属性即为当前节点的分裂属性，随着递归计算，被计算的属性的信息增益率会变得越来越小，到后期则选择相对比较大的信息增益率的属性作为分裂属性。

3.C4.5算法优缺点分析

优点：

（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂 属性的不足；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
（3）构造决策树之后进行剪枝操作；
（4）能够处理具有缺失属性值的训练数据。

缺点：

（1）算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
（2）算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。

4.python实现

## 信息增益率
def chooseBestFeatureToSplit_4(dataSet, labels):
    """
    选择最好的数据集划分特征，根据信息增益值来计算
    :param dataSet:
    :return:
    """
    # 得到数据的特征值总数
    numFeatures = len(dataSet[0]) - 1

    # 计算出基础信息熵
    baseEntropy = calcShannonEnt(dataSet)

    # 基础信息增益为0.0
    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=dataSet, axis=i, value=value)

            # 计算出权重
            prob = len(subDataSet) / float(len(dataSet))

            # 计算出当前特征值的熵
            newEntropy += prob * calcShannonEnt(subDataSet)

        # 计算出“信息增益”
        infoGain = baseEntropy - newEntropy
        infoGain = infoGain/newEntropy

        #print('当前特征值为：' + labels[i] + '，对应的信息增益值为：' + str(infoGain)+"i等于"+str(i))

        #如果当前的信息增益比原来的大
        if infoGain > bestInfoGain:
            # 最好的信息增益
            bestInfoGain = infoGain
            # 新的最好的用来划分的特征值
            bestFeature = i

    #print('信息增益最大的特征为：' + labels[bestFeature])
    return bestFeature

五.CART算法

1.CART算法的认识

Classification And Regression Tree，即分类回归树算法，简称CART算法，它是决策树的一种实现，通常决策树主要有三种实现，分别是ID3算法，CART算法和C4.5算法。

CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤

（1）将样本递归划分进行建树过程

（2）用验证数据进行剪枝

2.CART算法的原理

上面说到了CART算法分为两个过程，其中第一个过程进行递归建立二叉树，那么它是如何进行划分的 ？

设x1,x2…xn代表单个样本的n个属性，y表示所属类别。CART算法通过递归的方式将n维的空间划分为不重叠的矩形。划分步骤大致如下

（1）选一个自变量xi，再选取xi的一个值vi，vi把n维空间划分为两部分，一部分的所有点都满足xi<=vi，另一部分的所有点都满足xi>vi，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。

（2）递归处理，将上面得到的两部分按步骤（1）重新选取一个属性继续划分，直到把整个n维空间都划分完。在划分时候有一个问题，它是按照什么标准来划分的 ？ 对于一个变量属性来说，它的划分点是一对连续变量属性值的中点。假设m个样本的集合一个属性有个m连续的值，那么则会有m-1个分裂点，每个分裂点为相邻两个连续值的均值。每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用Gini指标，假设一个样本共有C类，那么一个节点A的Gini不纯度可定义为

3.python借助sklearn实现

只需要将DecisionTreeClassifier函数的参数criterion的值改为gini：

六、总结

决策树其实是通过物体的特征把它进行分类，不同的人有不同的分法，每种方法的结果可能不同，但都有它的道理，但我们要做的就是写出最能满足要求的那种。

学习参考：

https://blog.csdn.net/weixin_46129506/article/details/120987574

https://blog.csdn.net/leaf_zizi/article/details/82848682