Classification of Infinite Information Systems Depending on Complexity of Decision Trees and Decision Rule 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: In this paper, infinite information systems used in pattern recognition, data mining, discrete optimization, and computational geometry are investigated. Time and space complexity of decision trees and complete decision rule systems are studied. A partition of the set of all infinite information systems into two classes is considered. Information systems from the first class are close to the best from the point of view of time and space complexity of decision trees and decision rule systems. Decision trees and decision rule systems for information systems from the second class have in the worst case large time or space complexity.

Keywords: decision trees, decision rule systems, time complexity, space complexity

Journal: Fundamenta Informaticae, vol. 54, no. 4, pp. 345-368, 2003