基于多臂赌博机的决策树优化.pdfVIP

基于多臂赌博机的决策树优化

HasibulKarimShantoUmmeAymanKoana

DepartmentofIndustrialandProductionEngineeringDepartmentofComputerScience

BangladeshUniversityofEngineeringandTechnologyYorkUniversity

Dhaka,BangladeshOntario,Canada

hasibsourov36@ummekona@yorku.ca

ShadikurRahman

DepartmentofComputerScience

YorkUniversity

Ontario,Canada

shadikur@yorku.ca

本

译

中

1摘要—决策树如果没有适当的约束，很容易变得过于复杂过拟合。这种过拟合的问题主要发生在当树变得过于复

v并且容易过拟合，捕捉到噪声而非可泛化的模式。为了解决这个杂，并开始捕捉数据集中的噪音而非通用模式时[5]。

7

5问题，剪枝操作是优化决策树的关键部分，因为它不仅降低了树

剪枝决策树是一种创新的方法，可以减轻过拟合的

9的复杂性，还减少了生成过拟合模型的概率。传统的剪枝技术如

5成本-复杂度剪枝（CCP）和减少误差剪枝（REP）大多基于贪影响并提高模型的泛化能力[6]。通过有策略地移除对

0

.婪方法，专注于在剪枝节点时即时性能提升。然而，这可能会导模型预测性能贡献最小的分支，剪枝不仅优化了决策

8

0致长期泛化能力降低，在引入未见过的数据样本时削弱了树模型树，还提高了其鲁棒性。现有的决策树剪枝方法有几种，

5的鲁棒性，特别是在使用小且复杂的训练数据集时更为明显。为例如减少错误剪枝（REP）和成本复杂度剪枝（CCP）。

2

:了解决这一挑战，我们提出了一种基于多臂老虎机（MAB）的

vREP通过对验证集上的性能进行迭代去除分支来简化

i剪枝方法，这是一种基于强化学习（RL）的技术，能够动态地

x剪枝以生成具有更好泛化的最优决策树。我们的提议假设剪枝过决策树的复杂性，而CCP则使用惩罚项在平衡模型的

r

a程是一个探索-利用问题，使用MAB算法根据每次剪枝操作的复杂性和准确性的同时对树进行剪枝。虽然这些方法有

反馈来寻找最佳分支节点进行剪枝。在多个基准数据集上的实验效，但它们严重依赖基于启发式标准或计算昂贵的交叉

评估表明，我们提出的这种方法比传统方法有更好的预测性能。验证程序。这些特征限制了它们的可扩展性，特别是在

这表明利用MAB以动态和概率的方式对决策树进行剪枝有可实际应用中。

能优化基于决策树的模型。

剪枝决策树需要在不影响模型预测性能的情况下

IndexTerms—决策树剪枝，优化，多臂赌博机，强化学习。

找到当前最佳的分支节点进行剪枝，因此可以将其设计

I.介绍为一个顺序决策问题。强化学习等方法在这个类型的决

根据少数研究[1]和[2]，大多数在机器学习（ML）策任务中显示出巨大的潜力。研究[7]和[8]已经证明其

中使用的算法的主要缺点是缺乏透明度。随着机器学习在优化顺序决策任务中的有效性。在各种RL框架中，

被应用于各个领域以提高效率，用户更倾向于那些能够多臂赌博机非常简单且易于使用。它基于迭代反馈以动