机器学习周报(10.14-10.20)

标签：10.20 剪枝 featValue 10.14 划分周报数据节点决策树

摘要

本周继续学习吴恩达机器学习关于决策树的部分。首先了解了什么是剪枝、为什么要对决策树进行剪枝操作，以及剪枝的两种方法预剪枝和后剪枝并尝试通过Python来简单实现这两种方法。其次了解了什么是多决策树，和如何通过有放回抽样来进行随机森林算法，以及认识到了XGBoost算法。最后学习到了决策树和神经网络各自的优缺点和该在什么时候来使用决策树或神经网络。下周将进入机器学习关于无监督学习、推荐系统和强化学习部分的学习。

Abstract

This week we continue with the Andrew Ng Machine Learning section on decision trees. First, we understand what pruning is, why we should prune decision trees, and the two methods of pruning: pre-pruning and post-pruning, and try to implement these two methods simply through Python. Secondly, they learned what multiple decision trees are, how to perform random forest algorithms with put back sampling, and learned about the XGBoost algorithm. Finally, I learned the advantages and disadvantages of decision trees and neural networks, and when to use decision trees or neural networks. Next week we'll move on to machine learning on unsupervised learning, recommender systems, and reinforcement learning.

1 决策树的剪枝(Decision Tree Pruning)

决策树算法在学习的过程中为了尽可能正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵决策树的分支过多，模型也会很复杂，容易将训练集自身的一些特点当做所有数据都具有的一般性质，导致在遇到没见过的数据集时预测结果会较差，也就是发生“过拟合”。

要解决这个问题，需要对决策树进行剪枝(Pruning)操作。剪枝，顾名思义就是给决策树 "去掉" 一些判断分支，同时在剩下的树结构下仍然能得到不错的结果，从而简化决策树，一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质来防止或减少 "过拟合现象" 的发生，提高决策树的泛化能力。

具体做法：去掉过于细分的叶节点，使其回退到父节点，甚至更高的节点，然后将父节点或更高的叶节点改为新的叶节点。

剪枝的两种方法：

预剪枝(Pre-Pruning)：在决策树构造时就进行剪枝。在决策树构造过程中，对节点进行评估，如果对其划分并不能再验证集中提高准确性，那么该节点就不要继续往下划分。这时就会把当前节点作为叶节点。
后剪枝(Post-Pruning)：在生成决策树之后再剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉该节点，带来的验证集中准确性差别不大或有明显提升，则可以对它进行剪枝，用叶子节点来代填该节点。

注意：决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

1.1 预剪枝(Pre-Pruning)

预剪枝是在划分过程中对树进行剪枝，其基本原理是预先给出一些限制条件，当树达到这个条件时就停止树的生长，或者在划分时先估计当前划分能否为决策树的泛化能力带来提升，如果不能则停止树的生长，以达到剪枝的效果。

预剪枝主要方法有：

限制树深度：相当于限制从根节点到叶子节点用来划分的特征个数
限制叶子节点个数：设置决策树最末端的最大节点数（末端节点即叶子节点）
限制叶子节点样本数：每个节点的最小样本数
限制信息增益量：如果按照某特征进行划分后，信息增益量小于一个阈值，则不进行该特征划分

下面为西瓜的数据集：

色泽	根蒂	敲声	纹理	脐部	触感	好瓜
青绿	蜷缩	浊响	清晰	凹陷	硬滑	是
乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	是
乌黑	蜷缩	浊响	清晰	凹陷	硬滑	是
青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
浅白	蜷缩	浊响	清晰	凹陷	硬滑	是
青绿	稍蜷	浊响	清晰	稍凹	软粘	是
乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
乌黑	稍蜷	浊响	清晰	稍凹	硬滑	是
乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	否
青绿	硬挺	清脆	清晰	平坦	软粘	否
浅白	硬挺	清脆	模糊	平坦	硬滑	否
浅白	蜷缩	浊响	模糊	平坦	软粘	否
青绿	稍蜷	浊响	稍糊	凹陷	硬滑	否
浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
乌黑	稍蜷	浊响	清晰	稍凹	软粘	否
浅白	蜷缩	浊响	模糊	平坦	硬滑	否
青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	否

# 创建预剪枝决策树
def createTreePrePruning(dataTrain, labelTrain, dataTest, labelTest, names, method='id3'):
    trainData = np.asarray(dataTrain)
    labelTrain = np.asarray(labelTrain)
    testData = np.asarray(dataTest)
    labelTest = np.asarray(labelTest)
    names = np.asarray(names)
    # 如果结果为单一结果
    if len(set(labelTrain)) == 1:
        return labelTrain[0]
        # 如果没有待分类特征
    elif trainData.size == 0:
        return voteLabel(labelTrain)
    # 其他情况则选取特征
    bestFeat, bestEnt = bestFeature(dataTrain, labelTrain, method=method)
    # 取特征名称
    bestFeatName = names[bestFeat]
    # 从特征名称列表删除已取得特征名称
    names = np.delete(names, [bestFeat])
    # 根据最优特征进行分割
    dataTrainSet, labelTrainSet = splitFeatureData(dataTrain, labelTrain, bestFeat)

    # 预剪枝评估
    # 划分前的分类标签
    labelTrainLabelPre = voteLabel(labelTrain)
    labelTrainRatioPre = equalNums(labelTrain, labelTrainLabelPre) / labelTrain.size
    # 划分后的精度计算
    if dataTest is not None:
        dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, bestFeat)
        # 划分前的测试标签正确比例
        labelTestRatioPre = equalNums(labelTest, labelTrainLabelPre) / labelTest.size
        # 划分后 每个特征值的分类标签正确的数量
        labelTrainEqNumPost = 0
        for val in labelTrainSet.keys():
            labelTrainEqNumPost += equalNums(labelTestSet.get(val), voteLabel(labelTrainSet.get(val))) + 0.0
        # 划分后 正确的比例
        labelTestRatioPost = labelTrainEqNumPost / labelTest.size

    # 如果没有评估数据 但划分前的精度等于最小值0.5 则继续划分
    if dataTest is None and labelTrainRatioPre == 0.5:
        decisionTree = {bestFeatName: {}}
        for featValue in dataTrainSet.keys():
            decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue),
                                                                         labelTrainSet.get(featValue)
                                                                         , None, None, names, method)
    elif dataTest is None:
        return labelTrainLabelPre
    # 如果划分后的精度相比划分前的精度下降, 则直接作为叶子节点返回
    elif labelTestRatioPost < labelTestRatioPre:
        return labelTrainLabelPre
    else:
        # 根据选取的特征名称创建树节点
        decisionTree = {bestFeatName: {}}
        # 对最优特征的每个特征值所分的数据子集进行计算
        for featValue in dataTrainSet.keys():
            decisionTree[bestFeatName][featValue] = createTreePrePruning(dataTrainSet.get(featValue),
                                                                         labelTrainSet.get(featValue)
                                                                         , dataTestSet.get(featValue),
                                                                         labelTestSet.get(featValue)
                                                                         , names, method)
    return decisionTree

# 将西瓜数据集分割为测试集和训练集
xgData, xgLabel, xgName = createDataXG20()
xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest = splitXgData20(xgData, xgLabel)
# 生成预剪枝前的树
xgTreeTrain = createTree(xgDataTrain, xgLabelTrain, xgName, method='id3')
print("预剪枝前的树")
createPlot(xgTreeTrain)
# 生成预剪枝的树
xgTreePrePruning = createTreePrePruning(xgDataTrain, xgLabelTrain, xgDataTest, xgLabelTest, xgName, method='id3')
print("预剪枝的树")
createPlot(xgTreePrePruning)

预剪枝前的树：

在进行根节点划分时，得到信息增益最佳的特征“脐部”，然后对“脐部”进行划分前后的验证集精度对比，得到划分前精度为42.9%，划分后精度为71.4%，划分后精度提升则允许进行划分。

在“色泽”节点划分时，对“色泽”进行划分前后的验证集精度对比，得到划分前精度为71.4%，划分后精度为57.1%，划分后精度下降，则禁止划分。

在“根蒂”节点划分时，对“根蒂”进行划分前后的验证集精度对比，得到划分前精度为71.4%，划分后精度为71.4%，划分后精度不变，也禁止划分。

得到预剪枝的树：

预剪枝可以有效减少决策树的训练时间和测试时间开销，降低过拟合风险，减少训练时间和空间复杂度，但可能会因过早停止划分而欠拟合，错过一些有价值的划分。

1.2 后剪枝(Post-Pruning)

后剪枝是在决策树完全生成后进行的。它自底向上地对非叶节点进行考察，如果将该节点对应的子树替换为叶节点能够带来泛化性能的提升，则将该子树替换为叶节点。

后剪枝通常保留更多的分支，泛化性能往往优于预剪枝，但训练时间开销较大。

# 后剪枝 训练完成后决策节点进行替换评估  这里可以直接对xgTreeTrain进行操作
def treePostPruning(labeledTree, dataTest, labelTest, names):
    newTree = labeledTree.copy()
    dataTest = np.asarray(dataTest)
    labelTest = np.asarray(labelTest)
    names = np.asarray(names)
    # 取决策节点的名称 即特征的名称
    featName = list(labeledTree.keys())[0]
    # print("\n当前节点：" + featName)
    # 取特征的列
    featCol = np.argwhere(names == featName)[0][0]
    names = np.delete(names, [featCol])
    # print("当前节点划分的数据维度：" + str(names))
    # print("当前节点划分的数据：" )
    # print(dataTest)
    # print(labelTest)
    # 该特征下所有值的字典
    newTree[featName] = labeledTree[featName].copy()
    featValueDict = newTree[featName]
    featPreLabel = featValueDict.pop("_vpdl")
    # print("当前节点预划分标签：" + featPreLabel)
    # 是否为子树的标记
    subTreeFlag = 0
    # 分割测试数据 如果有数据 则进行测试或递归调用  np的array我不知道怎么判断是否None, 用is None是错的
    dataFlag = 1 if sum(dataTest.shape) > 0 else 0
    if dataFlag == 1:
        # print("当前节点有划分数据！")
        dataTestSet, labelTestSet = splitFeatureData(dataTest, labelTest, featCol)
    for featValue in featValueDict.keys():
        # print("当前节点属性 {0} 的子节点：{1}".format(featValue ,str(featValueDict[featValue])))
        if dataFlag == 1 and type(featValueDict[featValue]) == dict:
            subTreeFlag = 1
            # 如果是子树则递归
            newTree[featName][featValue] = treePostPruning(featValueDict[featValue], dataTestSet.get(featValue),
                                                           labelTestSet.get(featValue), names)
            # 如果递归后为叶子 则后续进行评估
            if type(featValueDict[featValue]) != dict:
                subTreeFlag = 0

                # 如果没有数据  则转换子树
        if dataFlag == 0 and type(featValueDict[featValue]) == dict:
            subTreeFlag = 1
            # print("当前节点无划分数据！直接转换树："+str(featValueDict[featValue]))
            newTree[featName][featValue] = convertTree(featValueDict[featValue])
            # print("转换结果：" + str(convertTree(featValueDict[featValue])))
    # 如果全为叶子节点， 评估需要划分前的标签，这里思考两种方法，
    #     一是，不改变原来的训练函数，评估时使用训练数据对划分前的节点标签重新打标
    #     二是，改进训练函数，在训练的同时为每个节点增加划分前的标签，这样可以保证评估时只使用测试数据，避免再次使用大量的训练数据
    #     这里考虑第二种方法 写新的函数 createTreeWithLabel，当然也可以修改createTree来添加参数实现
    if subTreeFlag == 0:
        ratioPreDivision = equalNums(labelTest, featPreLabel) / labelTest.size
        equalNum = 0
        for val in labelTestSet.keys():
            equalNum += equalNums(labelTestSet[val], featValueDict[val])
        ratioAfterDivision = equalNum / labelTest.size
        # print("当前节点预划分标签的准确率：" + str(ratioPreDivision))
        # print("当前节点划分后的准确率：" + str(ratioAfterDivision))
        # 如果划分后的测试数据准确率低于划分前的，则划分无效，进行剪枝，即使节点等于预划分标签
        # 注意这里取的是小于，如果有需要 也可以取 小于等于
        if ratioAfterDivision < ratioPreDivision:
            newTree = featPreLabel
    return newTree

后剪枝前的树：

通过对原分支“色泽”对比剪枝前后的验证集精度，发现剪枝前精度为57.1%，剪枝后为71.4%，剪枝后精度提升，则对此分支进行剪枝操作。

同样对原分支“纹理”对比剪枝前后的验证集精度，发现剪枝前精度为42.9%，剪枝后为57.1%，剪枝后精度提升，则对此分支进行剪枝操作。

最后得到后剪枝的树：

在实际应用中，选择预剪枝还是后剪枝取决于具体问题。预剪枝由于其贪心本质，可能会错过一些有益的分支，导致欠拟合。而后剪枝虽然能够保留更多的分支，但计算开销较大。通常，后剪枝的泛化性能优于预剪枝，但需要更多的计算资源。

2 集成树(Tree Ensembles)

2.1 多决策树(Multiple Decision Trees)

在单一决策树中，改变一个示例时，根节点划分的特征也改变了，同时左右子树集合也发生了变化，说明单一决策树对数据中的微小变化非常敏感：

使用多决策树可以使算法不那么敏感或更健壮。可以构建三个决策树的集合：

每一个都可能是一种合理的方法来分类，然后只要在新的例子上运行这三棵树，最终选择这三棵树中的大多数预测的情况，从而得到较为正确的预测情况。

2.2 有放回抽样(Sampling with Replacement)

有放回的抽样是每一次抽取之后放回，然后再进行下一轮的抽取，例如四个筹码颜色分别为红、黄、绿和蓝，则有放回的抽样可能情况有：

等等......

将有放回抽样运用于构建树的集合，可以构建多个与最初的训练集略有不同的随机训练集，例如：

可以看出，这个训练集并不包含所有十个原始训练示例。

2.3 随机森林算法(Random Forest Algorithm)

随机森林(Random Forest)是一种集成学习方法，通过构建多个决策树并将它们的预测结果结合起来，来提高模型的准确性和稳定性。每个决策树都是通过对训练数据进行有放回抽样和特征随机选择而构建的。

得到一个大小为 $eq?m$ 的训练集，循环 $eq?N$ 次下面操作：

使用带有替换的采样来创建大小为 $eq?m$ 的新训练集
在这个数据集上训练决策树

将它们的预测结果结合起来，得到最终的预测结果，提高了模型的准确性和稳定性。

事实证明，将树的数量设置的很多并不会降低效果，但是当树的数量超过一个临界点时，最终会得到收益递减的效果。这种集成树的创建方法也叫做袋状决策(Bagged decision tree)。

实际上有一个对袋装决策的修改，从而能使其变为随机森林。关键思想是，即使采用这种带有替换的采样过程，很多时候依然会获得同样的根节点，以及非常相似的根节点附近的节点。

因此，为了避免这种情况的发生，我们需要更加随机一点。通常的做法是在每个节点上选择一个特征进行切割，方法是假设总共有 $eq?n$ 个特征，每次选取特征时随机选取 $eq?k$ ( $eq?k%3Cn$ )个特征的随机子集，再从 $eq?k$ 个随机子集中选取一个最大增益特征作为该节点的分类特征。这种方法有效的原因是它允许决策树出现更多的情况的可能。

2.4 XGBoost(eXtreme Gradient Boosting)

XGBoost（eXtreme Gradient Boosting）是一种高效且强大的基于决策树和样本的决策树算法，用于解决回归和分类问题。它是梯度提升树（Gradient Boosting Tree）方法的扩展，通过结合多棵决策树进行集成学习，具有极强的预测能力。XGBoost的工作原理为：

得到一个大小为 $eq?m$ 的训练集，循环 $eq?N$ 次下面操作：

使用带有替换的采样来创建大小为 $eq?m$ 的新训练集（但是不是以相等的概率( $eq?%5Cfrac%7B1%7D%7Bm%7D$ )从所有的样本中进行选择，而是使其更有可能选择之前训练过的树错误分类的样本在新的数据集上训练一个决策树）
在这个数据集上训练决策树

构建决策树时，我们从数据集中抽取m个来创建新的数据集，但是与之前不同的是，我们要改变抽到每个元素的概率，让它更有可能抽到在之前已经创建的决策树中分类错误的例子：

XGBoost有以下特点：

增强树的开源实现；
快速、高效的实现；
很好的选择了默认拆分标准和何时停止拆分的标准；
内置了正则化，防止过度拟合；
是一种高竞争性的算法；
为不同的数据使用不同的方法，对数据集大小要求不高。

可以导入XGBoost库并且初始化分类器：

from xgboost import XGBClassifier

model = XGBClassifier()
model.fit(X_Train, y_train)
y_pred = model.predict(X_test)

用于回归：

from xgboost import XGBRegressor

model = XGBRegressor()
model.fit(X_train, Y_train)
y_pred = model.predict(X_test)

3 什么时候使用决策树(When to Use Decision Trees)

对比决策树和神经网络，各自的优缺点如下：

决策树和集成树：

能够很好地处理表格（结构化）数据
不建议用于非结构化数据（例如图像、音频、文本）
快
一次只能训练一个决策树
小的决策树可能是人类可以解释的

神经网络：

可以很好地处理所有类型的数据，包括表格（结构化）数据和非结构化数据
可能比决策树慢
适用于迁移学习
当构建一个由多个模型一起工作的系统时，将多个神经网络串在一起可能会更容易

4 无监督学习、推荐系统和强化学习(Unsupervised Learning, Recommender systems and Reinforcement Learning)

无监督学习(Unsupervised Learning)：在没有标签的数据里，根据聚类或一定的模型得到数据之间的关系，发现潜在的一些结构的一种训练方式，包括：

聚类学习(Clustering)：是按照某个特定标准（如距离）把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。
异常检测(Anomaly detection)：是寻找不符合预期行为的数据模式，用于识别与大多数样本不同的罕见或异常数据点。常见的方法包括基于统计的方法、基于聚类的方法和基于生成模型的方法等。

推荐系统(Recommender systems)：一种基于用户行为和偏好，自动向用户推荐可能感兴趣的物品（如商品、电影、音乐等）的技术。它们在现代互联网应用中扮演着至关重要的角色，为用户提供个性化的体验，同时也帮助平台提升用户粘性和销售额。常见的算法有协同过滤(Collaborative Filtering)、基于内容的推荐(Content-Based Recommendation)以及混合推荐(Hybrid Recommendation)，它们分别利用用户的行为数据、物品的属性特征和两者结合的方式来生成个性化的建议。

强化学习(Reinforcement Learning)：用于描述和解决智能体(agent)在环境中通过尝试和错误来学习行为策略。智能体通过与环境进行交互，根据奖励信号来调整其行为策略，以达到最大化累积奖励的目标。强化学习包括以下几个关键要素：

状态(State)：智能体观察到的环境状况。
行动(Action)：智能体可以执行的操作。
奖励(Reward)：对智能体行动结果的反馈，鼓励或惩罚。
策略(Policy)：决定智能体何时及采取何种行动的规则。

总结

通过本周的学习，了解到了决策树的剪枝是通过降低决策树的复杂度来避免过拟合的过程，为了防止决策树在学习的过程中不停地对结点进行划分，导致决策树的分支过多，造成过拟合现象，所以可通过剪枝来防止或减少过拟合现象。决策树剪枝的方法有预剪枝和后剪枝，预剪枝是在决策树构造时就进行剪枝，后剪枝是在生成决策树之后再剪枝，两者各有优缺点。

其次，了解了多决策树是由多个决策树组成并协同工作的一种模型。然后学习到随机森林算法是通过构建多个决策树并将它们的预测结果结合起来，来提高模型的准确性和稳定性。每个决策树都是通过对训练数据进行有放回抽样和特征随机选择而构建的。还有XGBoost算法是一种高效且强大的基于决策树和样本的决策树算法，用于解决回归和分类问题。

最后通过对比决策树和神经网络得到各自的优缺点，然后判断该在什么情况下使用决策树或神经网络。决策树能够很好地处理表格（结构化）数据，而神经网络可以很好地处理所有类型的数据，包括表格（结构化）数据和非结构化数据，但是会比决策树处理地慢。

下周将开始进入机器学习关于无监督学习、推荐系统和强化学习部分的学习。无监督学习是在没有明确标注（标签）的情况下对数据进行分析和建模，包括聚类学习和异常检测等。推荐系统是一种基于用户行为和偏好，自动向用户推荐可能感兴趣的物品（如商品、电影、音乐等）的技术，包括协同过滤、基于内容的推荐以及混合推荐等。强化学习是用于描述和解决智能体(agent)在环境中通过尝试和错误来学习行为策略，包括状态、行动、奖励、策略等这几个关键要素。

标签：10.20,剪枝,featValue,10.14,划分,周报,数据,节点,决策树
From： https://blog.csdn.net/qq_60040306/article/details/142869073