Compressible Infinite Information Systems

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

Abstrakty

EN

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.

Słowa kluczowe

EN

information systems; decision tree; weighted depth

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 55, nr 1
• Strony: 51--61
• Opis fizyczny: Biibliogr. 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.: Decision Trees. Theory and Applications, Nizhny Novgorod University Publishers, Nizhny Novgorod, 1994 (in Russian).
• [4] Moshkov, M. Ju.: Unimprovable upper bounds on time complexity of decision trees, Fundamenta Informaticae, 31, 1997, 157-184.
• [5] 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.
• [6] Moshkov, M. Ju.: On compressible information systems, Proc. Rough Sets and Current Trends in Computing (J. J. Alpigini, J. F. Peters, A. Skowron, N. Zhong, Eds.), LNCS 2475, Springer-Verlag, Berlin, 2002.
• [7] Moshkov, M. Ju.: Classification of infinite information systems depending on complexity of decision trees and decision rule systems (submitted to Fundamenta Informaticae), 54, 2003, 345-368.
• [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