Compressible Infinite Information Systems

Article type: Research Article

Authors: Moshkov, Mikhail Ju.

Affiliations: Faculty of Computing Mathematics and Cybernetics of Nizhny Novgorod State University, 23, Gagarina Av., Nizhny Novgorod, 603950, Russia

Abstract: We investigate infinite information systems. Such systems are widely used in pattern recognition, data mining, discrete optimization, computational geometry. An information system is called compressible relatively to a given weight function if for each problem over the information system with sufficiently large weight (i.e., total weight of attributes in the problem description) there exists a decision tree (i) solving this problem and (ii) having the weighted depth less than the problem weight. In the paper all pairs (information system, weight function) such that the information system is compressible relatively to the weight function are described. For each such pair the behavior of Shannon type function is investigated characterizing the growth in the worst case of the minimal weighted depth of decision trees with the growth of problem weight.

Keywords: information system, decision tree, weighted depth

Journal: Fundamenta Informaticae, vol. 55, no. 1, pp. 51-61, 2003