Search

In the paper, some generalizations of the notions of reduct and test (superreduct) are considered. The accuracy of greedy algorithm for construction of partial test is investigated. A lower bound on the minimal cardinality of partial reducts based on an information on greedy algorithm work is studied. Results of an experiment with greedy algorithm are described. [ABSTRACT FROM AUTHOR]

For any fixed natural k, there exists a polynomial in time algorithm which for a given decision table T and given k conditional attributes recognizes if there exist a decision reduct of T containing these k attributes. [ABSTRACT FROM AUTHOR]

In this paper greedy algorithms with weights for construction of partial tests (partial superreducts) and partial decision rules are considered. Lower bounds on minimal weight of partial reducts and partial decision rules based on information about greedy algorithm work are obtained. Keywords: Partial reducts, partial decision rules, weights, greedy algorithms. [ABSTRACT FROM AUTHOR]

For problems over arbitrary information system we study the relationships among the complexity of a problem description, the minimal complexity of a decision tree solving this problem deterministically, and the minimal complexity of a decision tree solving this problem nondeterministically. We consider the local approach to investigation of decision trees where only attributes from a problem description are used for construction of decision trees solving this problem. Keywords: Decision tree, rough set theory, complexity. [ABSTRACT FROM AUTHOR]

In the paper algorithms are considered which allow to consecutively optimize decision trees for decision tables with many-valued decisions relatively different complexity measures such as number of nodes, weighted depth, average weighted depth, etc. For decision tables over an arbitrary infinite restricted information system [5] these algorithms have (at least for the three mentioned measures) polynomial time complexity depending on the length of table description. For decision tables over one of such information systems experimental results of decision tree optimization are described. Keywords: Decision trees, complexity measures, optimization. [ABSTRACT FROM AUTHOR]

The research monograph is devoted to the study of bounds on time complexity in the worst case of decision trees and algorithms for decision tree construction. The monograph is organized in four parts. In the first part (Sects. 1 and 2) results of the monograph are discussed in context of rough set theory and decision tree theory. In the second part (Sect. 3) some tools for decision tree investigation based on the notion of decision table are described. In the third part (Sects. 4-6) general results about time complexity of decision trees over arbitrary (finite and infinite) information systems are considered. The fourth part (Sects. 7-11) contains a collection of mathematical results on decision trees in areas of rough set theory and decision tree theory applications such as discrete optimization, analysis of acyclic programs, pattern recognition, fault diagnosis and probabilistic reasoning. Keywords: decision tree, rough set theory, test theory, time complexity [ABSTRACT FROM AUTHOR]

In the paper a totally polynomial algorithm for construction of the set of irreducible partial covers for the major part of set cover problems is considered. Keywords: Irreducible partial cover, totally polynomial algorithm. [ABSTRACT FROM AUTHOR]

In the paper a greedy algorithm for construction of partial tests is considered. Bounds on minimal cardinality of partial reducts are obtained. Results of experiments with software implementation of the greedy algorithm are described. Keywords: partial cover, partial test, partial reduct, greedy algorithm. [ABSTRACT FROM AUTHOR]