Minimization of decision tree depth for multi-label decision tables

In this paper, we consider multi-label decision tables that have a set of decisions attached to each row. Our goal is to find one decision from the set of decisions for each row by using decision tree as our tool. Considering our target to minimize the depth of the decision tree, we devised various kinds of greedy algorithms as well as dynamic programming algorithm. When we compare with the optimal result obtained from dynamic programming algorithm, we found some greedy algorithms produces results which are close to the optimal result for the minimization of depth of decision trees.

I. Introduction

In usual decision tables, we found that each object is labeled with a single decision, but here we consider decision tables where each object is associated with a set of decisions. It arises when we study, e.g., problem of semantic annotation of images, music categorization into emotions, text categorization [1] etc. The problem under consideration is that we choose an arbitrary decision from the set of decisions for each object. To solve such problem, we used decision tree as our tool.