Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes

This paper examines specific classes of conventional decision tables (DTs) that are closed under operations of attribute (column) removal and decision modifications assigned to rows. For DTs belonging to any of these closed classes (CCs), we investigate a greedy algorithm that constructs a deterministic decision tree. We demonstrate that the number of steps performed by this algorithm is limited by twice the number of rows in the table. Furthermore, we compare the behavior of two functions. The first function describes the increase in the minimum complexity of a deterministic decision tree for a DT from the CC in the worst-case scenario, in relation to the complexity of the set of attributes associated with columns of the table. The second function characterizes the worst-case complexity growth of the deterministic decision tree constructed by the greedy algorithm for a DT from the CC, considering the growth of complexity of the set of attributes associated with columns of the table. We divide the entire collection of pairs consisting of a bounded complexity measure (BCM) and a CC into three subsets. For each subset, we establish lower and upper bounds for the second function based on the first function.