Search

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees. [ABSTRACT FROM AUTHOR]

in the paper algorithms are considered which allow to optimize decision trees consecutively againsts relatively different criterions. For decision tables over an arbitrary infinite restricted information system [4], these algorithms have polynomial time complexity. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Presents a study that investigated the time complexity of decision trees which compute values of all observable variables from Bayesian networks (BN). Decision trees for BN; Decomposition of an arbitrary BN with finite variables; Analysis of monotone increasing and monotone decreasing BN.