Scholarlink

In this chapter, we consider six problems of transforming decision rule systems into decision trees. For each problem, we study unimprovable upper and lower bounds on the minimum depth of decision trees obtained from decision rule systems, depending on various parameters of these systems. We study the complexity of constructing entire decision trees from decision rule systems and discuss the possibility of describing the computational path in this tree for a given input rather than constructing the entire decision tree. For each problem, we study two algorithms that are based on node covers for the hypergraphs corresponding to decision rule systems and a completely greedy algorithm for describing the computation paths. We also consider dynamic programming algorithm that, given decision rule systems, returns the minimum depth of decision trees for these systems.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Six Problems of Transformation: Depth of Decision Trees

  • 章节

  • 发表日期：

    2026年

查看全文
  • Kerven Durdymyradov,
  • Mikhail Moshkov,
  • Azimkhon Ostonov

摘要

In this chapter, we consider six problems of transforming decision rule systems into decision trees. For each problem, we study unimprovable upper and lower bounds on the minimum depth of decision trees obtained from decision rule systems, depending on various parameters of these systems. We study the complexity of constructing entire decision trees from decision rule systems and discuss the possibility of describing the computational path in this tree for a given input rather than constructing the entire decision tree. For each problem, we study two algorithms that are based on node covers for the hypergraphs corresponding to decision rule systems and a completely greedy algorithm for describing the computation paths. We also consider dynamic programming algorithm that, given decision rule systems, returns the minimum depth of decision trees for these systems.