Classification of Infinite Information Systems Depending on Complexity of Decision Trees and Decision Rule Systems

• Autorzy: Moshkov M.Ju.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

decision tree; decision rule; time complexity; space complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 54, nr 4
• Strony: 345--368
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Moshkov M.Ju.

• Faculty of Computing Mathematics and Cybernetics of Nizhni Novgorod State University, 23, Gagarina Av., Nizhni Novgorod, 603950, Russia,

Bibliografia

• 1] Chegis, I. A., Yablonskii, S. V.: Logical methods of electric circuit control, Trudy MIAN SSSR, 51, 1958, 270–360 (in Russian).
• [2] Moshkov, M. Ju.: Conditional tests, in: Problemy Kybernetiki, 40 (S. V. Yablonskii, Ed.), Nauka Publishers, Moscow, 1983, 131–170 (in Russian).
• [3] Moshkov, M. Ju.: Unimprovable upper bounds on time complexity of decision trees, Fundamenta Informaticae, 31, 1997, 157–184.
• [4] Moshkov, M. Ju.: On time complexity of decision trees, in: Rough Sets in Knowledge Discovery 1. Methodology and Applications (L. Polkowski, A. Skowron, Eds.), Phisica-Verlag, Heidelberg,1998, 160–191.
• [5] Moshkov, M. Ju.: Deterministic and nondeterministic decision trees for rough computing, Fundamenta Informaticae, 41, 2000, 301–311 368 M. Ju. Moshkov / Classification of Infinite Information Systems.
• [6] Moshkov, M. Ju.: Classification of infinite information systems, Proc. Rough Sets and Current Trends in Computing (W. Ziarko, Y. Y. Yao, Eds.) LNCS 2005, Springer-Verlag, Berlin, 2001.
• [7] Moshkov, M. Ju.: Classification of infinite check systems depending on complexity of decision trees and decision rule systems, Proc. 11th Interstates Workshop on Design and Complexity of Control Systems, Nizhny Novgorod, Russia, 2000 (in Russian).
• [8] Pawlak, Z.: Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, Boston, London, 1991.
• [9] Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems, in: Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory (R. Slowinski, Ed.),Kluwer Academic Publishers, Dordrecht, Boston, London, 1992, 331–362.