关于封闭类常规决策表的确定性和非确定性决策树的复杂性

On Complexity of Deterministic and Nondeterministic Decision Trees for Conventional Decision Tables from Closed Classes.

作者信息

Ostonov Azimkhon, Moshkov Mikhail

机构信息

Computer, Electrical and Mathematical Sciences & Engineering Division and Computational Bioscience Research Center, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia.

出版信息

Entropy (Basel). 2023 Oct 3;25(10):1411. doi: 10.3390/e25101411.

DOI:10.3390/e25101411

PMID:37895532

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC10606725/

Abstract

In this paper, we consider classes of conventional decision tables closed relative to the removal of attributes (columns) and changing decisions assigned to rows. For tables from an arbitrary closed class, we study the dependence of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We also study the dependence of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. Note that a nondeterministic decision tree can be interpreted as a set of true decision rules that covers all rows of the table.

摘要

在本文中，我们考虑相对于属性（列）的删除以及分配给行的决策的改变而封闭的常规决策表类。对于来自任意封闭类的表，我们研究确定性和非确定性决策树的最小复杂度对附加到列的属性集的复杂度的依赖性。我们还研究确定性决策树的最小复杂度对非确定性决策树的最小复杂度的依赖性。请注意，非确定性决策树可以解释为覆盖表中所有行的一组真决策规则。