|
|
|
M.Ju. Moshkov and I.V. Chikalov
Bounds on average weighted depth of decision trees
Research Institute for Applied Mathematics and Cybernetics of Nizhni Novgorod State
University 10, Uljanova St., Nizhni Novgorod, 603005, Russia
Faculty of Calculating Mathematics and Cybernetics of Nizhni Novgorod State University, 23,
Gagarina Av., Nizhni Novgorod, 603600, Russia
Email:
moshkov@unn.ac.ruUpper and lower bounds on minimal average weighted depth and minimal average depth of decision trees over arbitrary information systems are considered. In proofs methods of test theory and rough set theory are used.
Deterministic and nondeterministic decision trees for rough computing
Research Institute for Applied Mathematics and Cybernetics of Nizhni Novgorod State University 10, Uljanova St., Nizhni Novgorod, 603005, Russia
Email:
moshkov@unn.ac.ruIn the paper, infinite information systems are considered which are used in pattern recognition, discrete optimization, computational geometry. Depth and size of deterministic and nondeterministic decision trees over such information systems are studied. Two classes of infinite information systems are investigated. Systems from these classes are best from the point of view of time complexity and space complexity of deterministic as well as nondeterministic decision trees. In proofs methods of test theory [1] and rough set theory [6, 9] are used.
M.Ju. Moshkov and I.V. Chikalov
On algorithm for constructing of decision trees with minimal depth
Research Institute for Applied Mathematics and Cybernetics of Nizhni Novgorod State
University 10, Uljanova St., Nizhni Novgorod, 603005, Russia
Faculty of Calculating Mathematics and Cybernetics of Nizhni Novgorod State University, 23,
Gagarina Av., Nizhni Novgorod, 603600, Russia
Email:
moshkov@unn.ac.ruAn algorithm is considered which for a given decision table constructs a decision tree with minimal depth. The class of all information systems (finite and infinite) is described for which this algorithm has polynomial time complexity depending on the number of columns (attributes) in decision tables.
Decision trees for regular language word recognition
Research Institute for Applied Mathematics and Cybernetics of Nizhni Novgorod State University 10, Uljanova St., Nizhni Novgorod, 603005, Russia
Email:
moshkov@unn.ac.ruIn this paper the problem of recognition of words with fixed length from a regular language is considered. The word under consideration can be interpreted as a description of certain screen image in the following way: the $i$-th letter of the word encodes the color of the $i$-th screen cell. In this case a decision tree which recognizes some words may be interpreted as an algorithm for the recognition of images which are defined by considered words. The classification of all regular languages depending on the growth of minimal depth of decision trees for language word recognition with the growth of the word length is obtained. In proofs methods of test theory and rough set theory are used.
|
|
|