Homogeneous Information Trees

Abstract

By a homogeneous information tree we mean a tree with internal nodes labeled by attributes, edges by values of attributes and terminal nodes by sets of objects. Sets labeling terminal nodes form a partition of the set of objects classified by a homogeneous tree. Homogeneous information trees can be interpreted as models of expert systems, data bases with a menu or tree-structured data bases. The main problem we are dealing with concerns a minimization of a tree with respect to the storage cost. We propose a heuristic polynomial algorithm to construct an optimal tree.