机器学习算法之决策树

一种回归分类算法，每一个内部节点表示对于特征属性的判断，每一个分支就代表对这个特征属性判断的输出，每一个叶节点就是对决策结果的分类。

例：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R1OMNdjt-1663164436430)(./assets/决策树例子.png)]

监督学习的一种

优点：复杂度不高、输出结果容易理解、对中间的缺省不敏感

缺点：可能产生过度匹配问题

特征属性

不同特征对决策的影响大小不同，需要找到决定性的特征，需要对每个特征进行评估、选择，也就是对数据集的划分，一个数据集将被划分为多个数据集。选择特征的方法为：信息增益。

信息增益

选择特征之前和之后数据集发生的变化称为信息增益。

集合信息的度量方式被称为：香农熵（熵）。熵：信息的期望值，集合的无序程度，熵越大越无序。

待分类数据集可能会被分为多个类，则x_i的信息定义为：
$l(x_i)=-log_2p(x_i)$
其中p(x_i)是这个分类的概率

则所有类别的信息期望值（信息熵）：
$H=-\sum_{i=1}^np(x_i)log_2p(x_i)$

第i个特征属性a的信息增益：
$G(a)=H-\sum_{v=1}^V\frac{|D^v|}{|D|}H(D^v)$
$\frac{|D^v|}{|D|}$ 表示分支节点所占比例大小，数据集越大的分支权重越高, $H(D^v)$ 表示在划分出的 $D^v$ 数据集上的信息熵。分支节点纯度越大，则后一项（条件熵，即在选择某一特征作为分类属性下的熵）越小，信息增益越大，目标是最大化信息增益。所以选择信息增益最大的选择的属性。

ID3.5算法

核心思想：在决策树各个节点熵选择最优的信息增益得出特征属性，递归地构建决策树，知道没有特征选择为止。

银行流水例子：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T0nAOUtk-1663164436431)(./assets/银行流水.png)]

from math import  log
def createDataSet():
    '''
    创建数据集
    '''
    dataSet = [[1, 1, 0, 'y'],
               [1, 1, 0, 'y'],
               [1, 0, 0, 'n'],
               [0, 1, 0, 'n'],
               [0, 0, 1, 'n'],
               [1, 0, 1, 'n'],
               [1, 1, 1, 'n']]
    labels = ['Salary', 'Time', 'Bank flow']
    return dataSet,labels

def calcEntropy(dataSet):
    '''
    计算熵
    :param dataSet: 数据集
    :return: 熵值
    '''
    numEntries = len(dataSet)
    labelCounts = {}  # 一个字典，计算y有几个，n有几个
    for line in dataSet:
        currentLabel = line[-1]  # 取这条数据的结果y/n
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    entropy = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries  # y和n的占比
        entropy -= prob * log(prob, 2)  # 计算所有类别的信息期望值 即信息熵
    return entropy


mydata,labels = createDataSet()

entropy = calcEntropy(mydata)

print('熵值为：', entropy)

结果：

熵值为： 0.863120568566631

计算三个特征的信息熵：

def splitDataSet(dataSet,axis,value):
    '''
    划分数据集
    :param dataSet: 按照给定特征划分数据集
    :param axis: 划分数据集的特征
    :param value: 需要返回的特征的值
    :return: 根据选择的特征和特征值分出来的数据集
    '''
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec=featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):
    '''
    计算数据集的熵
    :param dataSet: 数据集
    :return: 最优的特征值的索引
    '''

    # 特征个数
    numFeatures = len(dataSet[0]) - 1
    # 数据集的熵
    baseEntropy = calcEntropy(dataSet)
    # 最优信息增益
    bestInfoGain = 0.0
    # 最优特征的索引值
    bestFeature = -1

    for i in range(numFeatures):
        # 获取数据集的第 i 个所有特征
        featList = [example[i] for example in dataSet]
        #创建 set集合{}，元素不可重复
        uniqueVals = set(featList)
        # 经验条件熵
        newEntropy = 0.0
        #计算信息增益
        for value in uniqueVals:
            # 数据集划分后的子集
            subDataSet = splitDataSet(dataSet, i, value)
            # 计算子集的概率
            prob = len(subDataSet) / float(len(dataSet))
            # 根据公式计算经验条件熵
            newEntropy += prob * calcEntropy((subDataSet))
        # 信息增益
        infoGain = baseEntropy - newEntropy
        # 打印每个特征的信息增益
        print("第%d个特征属性的信息增益为%.3f" % (i, infoGain))

        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

mydata,labels = createDataSet()

print("最优的索引值为：", str(chooseBestFeatureToSplit(mydata)))

结果：

第0个特征属性的信息增益为0.170
第1个特征属性的信息增益为0.292
第2个特征属性的信息增益为0.292
最优的索引值为： 1

在计算出第一个最优特征属性后，可以继续使用递归方式计算第二个最优特征属性，直至得出所有可能的决策类别。

构建决策树：

import operator

def majorityCnt(classList):
    '''
    类别数多的类别
    :param classList: 类别
    :return: 返回类别数多的类别
    '''
    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):
    '''
    构建决策树
    :param dataSet: 数据集样本
    :param labels: 特征属性
    :return: 决策树
    '''

    # 决策类别
    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)
    # 返回最优的特征属性
    bestFeature = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeature]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeature])
    # 最优特征值
    featureValues = [example[bestFeature] for example in dataSet]
    uniqueVals = set(featureValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeature, value), subLabels)
    return myTree
mydata,labels = createDataSet()
print(createTree(mydata,labels))

结果：

第0个特征属性的信息增益为0.170
第1个特征属性的信息增益为0.292
第2个特征属性的信息增益为0.292
第0个特征属性的信息增益为0.311
第1个特征属性的信息增益为0.311
第0个特征属性的信息增益为0.918
{'Time': {0: 'n', 1: {'Salary': {0: 'n', 1: {'Bank flow': {0: 'y', 1: 'n'}}}}}}

特征从头选到尾极容易产生过拟合现象，此时需要对模型进行剪枝，使其变得简单，以拥有更好的泛化能力，如果特征很多，也可以在一开始就进行特征选择，只留下有足够分类能力的特征。

ID3算法用信息增益方法作为选择标准，不能剪枝。

C4.5算法用信息增益率来选择节点属性，可以剪枝。

信息增益率：
$G_ratio(a)=\frac{G(a)}{IV(a)}$
$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
可以避免分类水平太多，经验熵减小过快的特征。

决策树的剪枝

决策树的剪枝一般通过极小化决策树整体的损失函数或代价函数来实现。用的是正则化极大似然估计进行模型选择。损失函数定义为模型拟合程度和模型复杂度求和。
$C_\alpha(T)=C(t)+\alpha|T|$
$C(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KD_{tk}log_2\frac{D_{tk}}{D_t}$
树T的叶子节点个数为|T|，t是树T的叶节点，该节点有 $D_t$ 个样本，其中k类的样本有 $N_{tk}$ 个。C(T)表示模型对训练数据的预测误差，|T|表示模型的复杂度，参数 $\alpha$ 控制这两者之间的影响。

剪枝时，当 $\alpha$ 确定时，选择损失函数最小的模型。模型的子树越大，模型的复杂度越高，模型与训练数据的拟合越好。相反，模型的子树越小，模型的复杂度越低，模型与训练数据的拟合越不好。损失函数表示了对两者的平衡。

预剪枝

决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将该结点标记为叶子结点。

优缺点：降低过拟合风险，减少训练和测试时间开销。但“贪心”本质带来欠拟合风险。

后剪枝

先从训练集生产一颗完整的决策树，自底向上地对非叶子结点进行考察，若该结点对应的子树替换为叶子结点能够带来决策树泛化能力的提升，则将该子树替换为叶结点。

模型的子树越小，模型的复杂度越低，模型与训练数据的拟合越不好。损失函数表示了对两者的平衡。

预剪枝

决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将该结点标记为叶子结点。

优缺点：降低过拟合风险，减少训练和测试时间开销。但“贪心”本质带来欠拟合风险。

后剪枝

优缺点：欠拟合风险小，泛化能力优于预剪枝。但训练时间比未剪枝和预剪枝的时间开销大得多。

原文链接：https://blog.csdn.net/lijiahe2000/article/details/126861430