一、相关概念

1.什么是决策树

       决策树是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。

2.决策树构造步骤

       (1)特征选择：这是构造决策树的关键步骤，目的是选择将元组最好地划分成不同类的属性。通常采用信息增益、信息增益比、基尼指数等指标来度量特征的重要性和纯度。目标是使得每个子节点尽可能地纯净，即包含尽可能多的相同类别的实例

        (2)切分数据集：选择最优特征后，将数据集根据该特征的不同取值切分成多个子集。这个过程将数据集根据特征划分为不同的分支，每个分支对应于特征的一个取值，该分支上的数据集包含了特征取值与该分支对应的所有实例。

        (3)递归构建决策树：对于每个子集，重复上述步骤，选择最优特征、切分数据集，直到满足终止条件。终止条件可能包括子集中所有样本都属于同一类别，或者没有更多特征可供选择等。

        (4)剪枝：由于决策树可能存在过拟合问题，为了提高其泛化能力，需要对决策树进行剪枝操作。剪枝过程有预剪枝和后剪枝两种策略，目的是去除那些可能导致过拟合的分支。

3.常用算法

(1)ID3算法：

        ID3算法是一种贪心算法，用于构造决策树。它起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准。ID3算法的核心思想是通过计算每个属性的信息增益来选择最佳的划分属性。信息增益表示了给定属性条件下，数据集的不确定性减少的程度。在每个节点，算法选择尚未被用来划分的具有最高信息增益的属性作为划分标准，然后递归地在每个子节点上应用同样的过程，直到生成的决策树能够完美分类训练样例或满足其他停止条件。

(2)C4.5算法：

       C4.5算法是对ID3算法的一个扩展，由Ross Quinlan开发。C4.5算法同样使用信息增益作为选择划分属性的标准，但在处理连续特征、缺失值和剪枝等方面进行了优化。C4.5能够处理具有连续值的属性，通过离散化处理来选择最佳的划分点。此外，C4.5还引入了剪枝策略，通过删除一些可能导致过拟合的分支来提高决策树的泛化能力。C4.5算法的目标是通过学习找到一个从属性值到类别的映射关系，用于对新的未知类别的实体进行分类。

(3)CART算法：

       CART算法，全称Classification and Regression Trees，即分类与回归树算法。它既可用于分类问题，也可用于回归问题。CART算法使用基尼指数作为选择划分属性的标准。在分类问题中，CART算法根据特征值将数据集划分为多个子集，通过选择一个最佳划分特征和划分阈值来构建决策树。在回归问题中，CART算法同样根据特征值划分数据集，但构建的是回归树。CART算法生成的决策树是结构简洁的二叉树，每个非叶子节点都有两个分支。

4.信息增益和基尼指数

信息增益和基尼指数都是评估数据集划分纯度和选择最佳特征的重要指标，它们各自具有不同的特点和适用场景，在决策树的构建过程中发挥着关键作用。

       （1）信息增益：表示数据集中某个特征的信息使得类的不确定性减少的程度。在机器学习中，每个特征可以看作是一个信息源，每个特征值对应一个信息。特征对训练数据集的信息增益，定义为集合的熵与特征给定条件下集合的条件熵之差。通过计算信息增益，我们可以衡量每个特征对于分类模型的贡献程度，并选择最佳的特征进行数据集的划分。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号xi的信息定义为：

(其中p(xi)是选择该分类的概率)

为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值,通过下式可得：

(其中n为分类数目)

       （2）基尼指数：也称为基尼不纯度，表示在样本集合中一个随机选中的样本被分错的概率。基尼指数越小，表示集合中被选中的样本被分错的概率越小，即集合的纯度越高。在构建决策树时，基尼指数可以帮助我们确定最佳的特征和特征值来分割数据集，从而构建出高效准确的分类模型。

直观来说，Gini（D）反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini（D）越小，则数据集D的纯度越高。

属性a的基尼指数定义为：

二、ID3和CART算法构造决策树

1.ID3算法

创建数据集及标签

def createDataSet():
    dataSet = [
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
        ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
        ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
        ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
        ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
    ]
    features = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
    return dataSet,features

计算给定数据集的熵：利用字典进行数量统计并计算熵 

def calShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
            labelCounts[currentLabel] += 1
        else:
            labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2)
    return shannonEnt

按照给定的特征划分数据集：返回划分后的数据集的结果

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

选择最好的数据集的划分方式并输出每个特征的熵和信息增益

def choosebest(dataSet):
    numFeatures = len(dataSet[0])-1
    baseEntropy = calShannonEnt(dataSet)
    #print(baseEntropy)
    bestinfo = 0.0; beatFeature = -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 * calShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        print("第", i + 1, "个特征的信息熵为:", newEntropy)
        print("第", i + 1, "个特征的信息增益为:", infoGain)
        if(infoGain > bestinfo):
            bestinfo = infoGain
            beatFeature = i
    return beatFeature

绘制决策树

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.key():
            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 = choosebest(dataSet)
    bestFeatLabel = labels[bestFeat]
    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

运行结果：

2.CART算法构造决策树

创建数据集和特征

def createDataSet():
    dataSet = [
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],
        ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],
        ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],
        ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],
        ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],
        ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']
    ]
    features = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
    numList = []  # [3, 3, 3, 3, 3, 2]
    for i in range(len(features)):
        numList.append(len(featureDic[features[i]]))
    newDataSet = np.array(dataSet)
    # 得到训练数据集
    trainIndex = [0, 1, 2, 3, 5, 6, 9, 13, 14, 15, 16]
    trainDataSet = newDataSet[trainIndex]
    # 得到剪枝数据集
    pruneIndex = [4, 7, 8, 10, 11, 12]
    pruneDataSet = newDataSet[pruneIndex]
 
    return np.array(dataSet), trainDataSet, pruneDataSet, features

计算基尼指数

def calGini(dataArr):
    numEntries = dataArr.shape[0] #shape [0] 表示行数,即数据集样本总数
    classArr = dataArr[:, -1] #表示是好瓜还是坏瓜
    uniqueClass = list(set(classArr))
    Gini = 1.0
    for c in uniqueClass:
        Gini -= (len(dataArr[dataArr[:, -1] == c]) / float(numEntries)) ** 2
    return Gini

划分数据集

def splitDataSet(dataSet, ax, value):
    return np.delete(dataSet[dataSet[:, ax] == value], ax, axis=1)

计算给定的数据集的在属性ax上的基尼指数

def calSplitGin(dataSet, ax, labels):
    newGini = 0.0  # 划分完数据后的基尼指数
    # 对每一种属性
    for j in featureDic[ax]:
        axIndex = labels.index(ax)
        subDataSet = splitDataSet(dataSet, axIndex, j)
        prob = len(subDataSet) / float(len(dataSet))
        if prob != 0:  
            newGini += prob * calGini(subDataSet)
    return newGini

根据基尼指数得到最好的分类特征

def chooseBestSplit(dataSet, labelList):
    bestGain = 1
    bestFeature = -1
    n = dataSet.shape[1]
    # 对每一个特征
    for i in range(n - 1):
        newGini = calSplitGin(dataSet, labelList[i], labelList)
        print(f"{labelList[i]}   {newGini}")
        if newGini < bestGain:
            bestFeature = i
            bestGain = newGini
    return bestFeature

构造决策树

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount:
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(),
                              key=operator.itemgetter(1),
                              reverse=True)
    return sortedClassCount[0][0]
 
def createTree(dataSet, labels):
    classList = dataSet[:, -1]
    # 如果基尼指数为0，即D中样本全属于同一类别，返回
    if calGini(dataSet) == 0:
        return dataSet[0][-1]
    # 属性值为空，只剩下类标签
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 得到增益最大划分的属性、值
    bestFeatIndex = chooseBestSplit(dataSet, labels)  # bestFeat 是最优划分属性的坐标
    bestFeatLabel = labels[bestFeatIndex]
    myTree = {bestFeatLabel: {}}  # 创建字典，即树的节点。
    labelsCopy = labels[:]
    del (labelsCopy[bestFeatIndex])
    uniqueVals = featureDic[bestFeatLabel]  # 最好的特征的类别列表
    for value in uniqueVals: 
        subLabels = labelsCopy[:]
        subDataSet = splitDataSet(dataSet, bestFeatIndex, value)
        if len(subDataSet) != 0:
            myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels)
        else:
            myTree[bestFeatLabel][value] = majorityCnt(classList)
    return myTree

运行结果：

 

         由以上的运行结果可知，ID3算法以信息增益为指标计算出的最好的特征为第四个特征，即：“纹理”；而CART算法以基尼指数为指标计算出的最好的特征为第五个特征，即“脐部”。因为两个算法计算出的最优的特征不同，因此所构造出的决策树也不同。

         所以可以得出，不同的构造决策树的算法，以不同的指标作为标准所计算出的最优特征会不同，因而构造出的决策树也会有所不同。