The Max-Cut Decision Tree: Improving on the Accuracy and Running Time of Decision Trees
The Max-Cut Decision Tree: Improving on the Accuracy and Running Time of Decision Trees
复制标题
最大割决策树：提高决策树的准确性和运行时间
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Hochbaum
中科院分区：
文献类型：
--
作者：
Jonathan Bodine;D. Hochbaum
决策树是一种广泛使用的分类方法，无论是本身还是作为多种不同集成学习方法的构建块。Max-Cut决策树涉及对分类决策树构建的标准基线模型（准确地说是CART Gini）的新修改。一种修改涉及另一种分裂度量，最大切割，基于最大化属于不同类别和阈值的不同侧的所有观测对之间的距离。另一个修改是从使用主成分分析（PCA）在每个节点本地构造的输入特征的线性组合中选择决策特征。我们的实验表明，这种基于节点的局部PCA与新的分裂修改可以显着提高分类，同时也显着减少计算时间相比，基线决策树。此外，我们的结果是最显着的数据集进行评估时，具有更高的维度，或更多的类;其中，例如数据集CIFAR-100，使49%的准确性提高，同时减少94%的CPU时间。这些引入的修改大大提高了决策树处理困难分类任务的能力。
Decision trees are a widely used method for classification, both by themselves and as the building blocks of multiple different ensemble learning methods. The Max-Cut decision tree involves novel modifications to a standard, baseline model of classification decision tree construction, precisely CART Gini. One modification involves an alternative splitting metric, maximum cut, based on maximizing the distance between all pairs of observations belonging to separate classes and separate sides of the threshold value. The other modification is to select the decision feature from a linear combination of the input features constructed using Principal Component Analysis (PCA) locally at each node. Our experiments show that this node-based localized PCA with the novel splitting modification can dramatically improve classification, while also significantly decreasing computational time compared to the baseline decision tree. Moreover, our results are most significant when evaluated on data sets with higher dimensions, or more classes; which, for the example data set CIFAR-100, enable a 49% improvement in accuracy while reducing CPU time by 94%. These introduced modifications dramatically advance the capabilities of decision trees for difficult classification tasks.