The study of the relationships between decision rule systems and decision trees is of considerable interest in computer science. These models are among the most interpretable tools used in knowledge representation, classification, and decision-making. In this paper, we consider classes of decision rule systems that are closed under the operations of attribute and rule removal. The motivation for this study is to understand how the structural properties of decision rule systems affect the complexity of decision trees constructed for solving the problems related to the system. For an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum depth of deterministic and nondeterministic decision trees that solve the problem of the existence of realizable rules in a decision rule system on the number of different attributes in this system. In particular, we consider the problem of deciding whether a realizable rule exists for a given tuple and analyze the worst-case tree depth required to solve this problem. We prove that these functions are either bounded from above by a constant or grow linearly. These results extend previous theoretical findings and may be useful for building efficient interpretable models in practice.

Decision rule systems and decision trees are frequently used in computer science as interpretable models. Understanding their complexity in terms of attribute costs is crucial when decisions must be made with minimum resource usage. Our result shows a tight bound on how much more expensive a deterministic model can be, which can impact rule-based system design in cost-sensitive environments. This paper discusses various problems related to recognizing properties of decision rule systems using deterministic and nonde-terministic decision trees as solution algorithms. Importantly, a nondeterministic decision tree can be interpreted as a representation of a system of decision rules that are true for a given problem and cover all possible inputs. The paper shows that the minimum weighted depth of a deterministic decision tree solving a problem is bounded above by the square of the minimum weighted depth of a nondeterministic decision tree. This result, in particular, encourages consideration of the possibility of transforming decision rule systems into decision trees.

In this paper, classes of decision tables with many-valued decisions (also known as multi-labeled decision tables) closed with respect to deletion of attributes (columns) and change of decisions are considered. For tables from these classes, the dependence of the minimum complexity of regular decision trees on the minimum complexity of oblivious decision trees, in which the order of queries on attribute values is predetermined, is studied. It is proved that the function describing this dependence is either bounded from above by a constant or grows as a logarithm, or grows almost linearly. This result is valid for the so-called bounded complexity measures, including the depth and weighted depth of decision trees. Motivation of this work constitutes in analyzing growth in the worst-case of the minimum complexity of a regular decision tree for a decision table from a closed class with the growth of the minimum complexity of an oblivious decision tree for this decision table. It is also shown that the minimum complexity of an oblivious tree for a decision table is equal to the minimum complexity of a reduct for this table. This finding can be useful for applications related to oblivious decision trees.

The subject of the paper concerns the problem of deriving decision rules from distributed data. The paper examines issues of learning general and inner decision rules from a set of decision trees. Inner rules refer to the routes within decision trees from the root to leaf nodes , while general rules are arbitrary rules derived from attributes found in the set of decision trees. The paper illustrates that the optimization of general decision rules is NP-hard problem, so the authors propose heuristics H 1 and H 2 for this issue. Taking into account induction and optimization of inner decision rules an algorithm A is employed. Additionally, an approach based on global optimization relative to length, support, and sequential optimization is proposed. The presented algorithms were studied considering two perspectives (i) knowledge discovery from data and (ii) knowledge representation. In the first case, it is possible to discover patterns from the data and verify the induced model, in the second case, it is possible to represent knowledge in a comprehensible and explainable way. These elements are important in an era of heterogeneous, distributed data sources . Experiments were carried out on selected datasets from UCI ML and Kaggle repositories. In order to create a distributed data structure, an approach based on reducts induced by a genetic algorithm was employed. Obtained results show that there are cases where the global rule-based classifiers built in the framework of optimization of inner decision rules perform better in terms of accuracy than that of local models induced directly from subtables. In the case of algorithms H 1 and H 2 , the low complexity of models based on decision rules induced from a set of decision trees is noted.

In this research paper, we examine classes of decision tables that are closed under attribute (column) removal and changing of decisions associated with rows.For decision tables belonging to these closed classes, we investigate lower bounds on the minimum cardinality of reducts.Reducts are minimal sets of attributes that allow us to determine the decision attached to a given row.We assume that the number of rows in the decision tables from the closed class is not limited by a constant.We divide the set of these closed classes into two families.In one family, the minimum cardinality of reducts for decision tables is bounded by standard lower bounds of the form Ω(log cl(T )), where cl(T ) represents the number of decision classes in the table T .In the other family, these lower bounds can be significantly tightened to the form Ω(cl(T ) 1/q ) for some natural number q.

Extensive research has been conducted on rough set theory, specifically focusing on the study of decision trees (DTs) and decision rule systems (DRSs). This theory addresses several important questions, including the relationship between DTs and DRSs, the tradeoff between time and space for DTs, and the tradeoff for DRSs.The objective of this paper is to investigate infinite binary information systems (ISs), each consisting of an infinite set (universe) and an infinite set of two-valued functions (features) defined on the universe. We examine the concept of a task within an IS, which is described by a finite number of features and a mapping that assigns a decision to each combination of feature values. Our analysis focuses on deterministic and nondeterministic DTs (DDTs and NDTs) as algorithms for task-solving, with the restriction that only features from the task description are used.NDTs serve as representations of DRSs and can sometimes have lower space complexity compared to the original DRSs. We study the time and space complexity of DTs, specifically examining the depth and the number of nodes in these trees. The obtained results allow us to classify the set of all ISs into three families, enabling the identification of nontrivial relationships between DDTs and DRSs represented by NDTs. For each family, we investigate the tradeoff between time and space for both DDTs and NDTs.

Decision rules belong to known forms of knowledge representation. Among popular measures of their quality length and support can be distinguished. Shorter rules are easier to understand and interpret. Support allows to present patterns hidden in the data. Nowadays, data mining tasks are oriented toward extracting knowledge from data in both distributed and centralized forms. Learning decision rules from a decision tree is a relatively simple task. However, the challenge arises when decision rules are induced from a set of decision trees. Moreover, in the case of distributed data, the decision trees may be constructed independently on different sources, and merging them into a unified set requires resolving conflicts and inconsistencies. In this paper, decision rules are constructed from distributed data based on decision trees induced using the randomly chosen attributes as the splitting criterion. The aim of the study is to compare the quality of two algorithms for constructing rules which are true for a maximum number of trees. The comparison was made based on three factors: the number of trees for which the rule is true, their length and support. Based on performed experiments it was possible to see that the number of true rules for the maximum number of decision trees from the set is greater for algorithm A than for heuristics H. This algorithm allows the induction of shorter rules with greater support compared to heuristic H. However, it should be also noted that the rules induced by heuristic H are often true for a larger number of trees than the rules constructed by algorithm A. Thus, both algorithms can be applied to distributed data.

In this paper, we assume that a dispersed data is represented by a finite set S of decision tables with equal sets of attributes. We discuss one of the possible ways to the study decision trees common to all tables from the set S : building a decision table for which the set of decision trees coincides with the set of decision trees common to all tables from S . We show when we can build such a decision table and how to build it in a polynomial time. If we have such a table, we can apply to it various decision tree learning algorithms. We extend the considered approach to the study of decision rules and test (reducts) common to all tables from S .

Association rules are popular form for knowledge discovery domain. They are used for finding interesting relationships and patterns hidden in large data sets and in the area of associative classification, where usually rules with one item in the right-hand side are considered. There are many different approaches and algorithms for mining association rules. One of the most popular group are methods which are based on mining frequent itemsets, usually applied for data in transaction format. Such data can be transformed to binary information system which corresponds to matrix data format. Technological development means that we are dealing with an increasing amount of data that can be heterogeneous, taking into account their format and location. In this paper, we assume that dispersed data is represented by a finite set S of information systems with equal sets of attributes. We discuss one of the possible ways to the study association rules common to all information systems from the set S: building a joint information system for which the set of true association rules that are realizable for a given row r and have given attribute f on the right-hand side coincides with the set of association rules that are true for all information systems from S, are realizable for the row r, and have the attribute f on the right-hand side. We show how to build a joint information system in a polynomial time. When we build such an information system, we can apply to it various association rule learning algorithms.

This paper deals with computation trees over an arbitrary structure consisting of a set along with collections of functions and predicates that are defined on it. It is devoted to the comparative analysis of three parameters of problems with n input variables over this structure: the complexity of a problem description, the minimum complexity of a computation tree solving this problem deterministically, and the minimum complexity of a computation tree solving this problem nondeterministically. Rough classification of relationships among these parameters is considered and all possible seven types of these relations are enumerated. The changes of relation types with the growth of the number n of input variables are studied.

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments.

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued non-constant functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should determine values of these attributes. As algorithms for problem solving, we study decision trees that use arbitrary attributes from the considered infinite set of attributes and solve the problem based on 1-consequences. In such a tree, we take into account consequences each of which follows from one equation of the kind “attribute = value” obtained during the decision tree work and ignore consequences that can be derived only from at least two equations. As time complexity, we study the depth of decision trees. We prove that in the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees based on 1-consequences grows either as a logarithm or linearly.

In this paper, we study decisions trees for decision tables with multiple decisions as a means for knowledge representation. To this end, we consider three methods to design decision trees and evaluate the number of nodes, and local and global misclassification rates of constructed trees. The considered methods are based on a dynamic programming algorithm for bi-objective optimization of decision trees. The goal of this study is to construct trees with reasonable number of nodes and at the same time reasonable accuracy. Previously, it was mentioned that the consideration of only the global misclassification rate of the decision tree is not enough and it is necessary to study also the local misclassification rate. The reason is that even if the global misclassification rate related to the whole tree is enough small, the local misclassification rate related to the terminal nodes of the tree can be too big. One of the considered methods allows us to construct the decision trees with moderate number of nodes as well as moderate global and local misclassification rates. These decision trees can be used for the knowledge representation.

In this paper, we present results of experimental studies related to the existence of totally optimal decision trees (which are optimal relative to two or more cost functions simultaneously) for nine decision tables from the UCI Machine Learning Repository. Such trees can be useful when we consider decision trees as algorithms for problem solving or as a way for knowledge representation. For cost functions, we use depth, average depth, and number of nodes. We study not only exact but also approximate decision trees based on five uncertainty measures: entropy, Gini index, misclassification error, relative misclassification error, and number of unordered pairs of rows with different decisions. To investigate the existence of totally optimal trees, we use an extension of dynamic programming that allows us to make multi-stage optimization of decision trees relative to a sequence of cost functions. Experimental results show that totally optimal decision trees exist in many cases. The behavior of graphs that describe how the number of decision tables with totally optimal decision trees depends on their accuracy is mainly irregular. However, one can observe some trends, in particular, an upward trend when accuracy is decreasing.

In this paper, seven greedy heuristics for construction of association rules are compared from the point of view of the length and coverage of constructed rules. The obtained rules are compared also with optimal ones constructed by dynamic programming algorithms. The average relative difference between length of rules constructed by the best heuristic and minimum length of rules is at most 4%. The same situation is with coverage.

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. The association rule set is optimized in two stages, first for minimum cardinality and then for minimum length of rules. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of rule set based on the information obtained during algorithm work as well as obtained results for length.

Decision tree is a widely used technique to discover patterns from consistent data set.But if the data set is inconsistent, where there are groups of examples (objects) with equal values of conditional attributes but different decisions (values of the decision attribute), then to discover the essential patterns or knowledge from the data set is challenging.We consider three approaches (generalized, most common and many-valued decision) to handle such inconsistency.We created different greedy algorithms using various types of impurity and uncertainty measures to construct decision trees.We compared the three approaches based on the decision tree properties of the depth, average depth and number of nodes.Based on the result of the comparison, we choose to work with the many-valued decision approach.Now to determine which greedy algorithms are efficient, we compared them based on the optimization and classification results.It was found that some greedy algorithms (Mult_ws_entSort, and Mult_ws_entML) are good for both optimization and classification.

We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row.The size of the decision tree can be small as well as very large.We study here different greedy as well as dynamic programming algorithms to minimize the size of the decision trees.When we compare the optimal result from dynamic programming algorithm, we found some greedy algorithms produce results which are close to the optimal result for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference).

Knowledge representation and extraction are very important tasks in data mining. In this work, we proposed a variety of rule-based greedy algorithms that able to obtain knowledge contained in a given dataset as a series of inhibitory rules containing an expression “attribute ≠ value” on the right-hand side. The main goal of this paper is to determine based on rule characteristics, rule length and coverage, whether the proposed rule heuristics are statistically significantly different or not; if so, we aim to identify the best performing rule heuristics for minimization of rule length and maximization of rule coverage. Friedman test with Nemenyi post-hoc are used to compare the greedy algorithms statistically against each other for length and coverage. The experiments are carried out on real datasets from UCI Machine Learning Repository. For leading heuristics, the constructed rules are compared with optimal ones obtained based on dynamic programming approach. The results seem to be promising for the best heuristics: the average relative difference between length (coverage) of constructed and optimal rules is at most 2.27% (7%, respectively). Furthermore, the quality of classifiers based on sets of inhibitory rules constructed by the considered heuristics are compared against each other, and the results show that the three best heuristics from the point of view classification accuracy coincides with the three well-performed heuristics from the point of view of rule length minimization.

The paper is devoted to the analysis of greedy algorithms for the minimization of average depth of decision trees for decision tables such that each row is labeled with a set of decisions. The goal is to find one decision from the set of decisions. When we compare with the optimal result obtained from dynamic programming algorithm, we found some greedy algorithms produces results which are close to the optimal result for the minimization of average depth of decision trees.

The paper describes a new tool for study relationships between length and coverage of exact decision rules. This tool is based on dynamic programming approach. We also present results of experiments with decision tables from UCI Machine Learning Repository.

This paper presents a new tool for the study of relationships between the total path length or the average depth and the number of misclassifications for decision trees. In addition to algorithm, the paper also presents the results of experiments with datasets from UCI ML Repository [9] and datasets representing Boolean functions with 10 variables.

In this work, we consider so-called nonredundant inhibitory rules, containing an expression “attribute:F value” on the right- hand side, for which the number of misclassifications is at most a threshold γ. We study a dynamic programming approach for description of the considered set of rules. This approach allows also the optimization of nonredundant inhibitory rules relative to the length and coverage. The aim of this paper is to investigate an additional possibility of optimization relative to the number of misclassifications. The results of experiments with decision tables from the UCI Machine Learning Repository show this additional optimization achieves a fewer misclassifications. Thus, the proposed optimization procedure is promising.

In this paper, we present three approaches for construction of decision rules for decision tables with many-valued decisions. We construct decision rules directly for rows of decision table, based on paths in decision tree, and based on attributes contained in a test (super-reduct). Experimental results for the data sets taken from UCI Machine Learning Repository, contain comparison of the maximum and the average length of rules for the mentioned approaches.

In this paper, we present the empirical results for relationships between time (depth) and space (number of nodes) complexity of decision trees computing monotone Boolean functions, with at most five variables. We use Dagger (a tool for optimization of decision trees and decision rules) to conduct experiments. We show that, for each monotone Boolean function with at most five variables, there exists a totally optimal decision tree which is optimal with respect to both depth and number of nodes.

We describe new heuristics to construct decision rules for decision tables with many-valued decisions from the point of view of length and coverage which are enough good. We use statistical test to find leaders among the heuristics. After that, we compare our results with optimal result obtained by dynamic programming algorithms. The average percentage of relative difference between length (coverage) of constructed and optimal rules is at most 6.89% (15.89%, respectively) for leaders which seems to be a promising result.

Based on dynamic programming approach we design algorithms for sequential optimization of exact and approximate decision rules relative to the length and coverage [3, 4]. In this paper, we use optimal rules to construct classifiers, and study two questions: (i) which rules are better from the point of view of classification – exact or approximate; and (ii) which order of optimization gives better results of classifier work: length, length+coverage, coverage, or coverage+length. Experimental results show that, on average, classifiers based on exact rules are better than classifiers based on approximate rules, and sequential optimization (length+coverage or coverage+length) is better than the ordinary optimization (length or coverage).

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision fro

In the paper, we study an extension of dynamic programming approach which allows optimization of approximate decision rules relative to the number of misclassifications. We introduce an uncertainty measure J(T) which is a difference between the number of rows in a decision table T and the number of rows with the most common decision for T. For a nonnegative real number γ, we consider γ-decision rules that localize rows in subtables of T with uncertainty at most γ.

This paper is devoted to the study of an extension of dynamic programming approach which allows optimization of partial decision rules relative to the length or coverage. We introduce an uncertainty measure J(T) which is the difference between number

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given r

BACKGROUND: Hydrogen bonds (H-bonds) play a key role in both the formation and stabilization of protein structures. They form and break while a protein deforms, for instance during the transition from a non-functional to a functional state. The intrinsic strength of an individual H-bond has been studied from an energetic viewpoint, but energy alone may not be a very good predictor. METHODS: This paper describes inductive learning methods to train protein-independent probabilistic models of H-bond stability from molecular dynamics (MD) simulation trajectories of various proteins. The training data contains 32 input attributes (predictors) that describe an H-bond and its local environment in a conformation c and the output attribute is the probability that the H-bond will be present in an arbitrary conformation of this protein achievable from c within a time duration Δ. We model dependence of the output variable on the predictors by a regression tree. RESULTS: Several models are built using 6 MD simulation trajectories containing over 4000 distinct H-bonds (millions of occurrences). Experimental results demonstrate that such models can predict H-bond stability quite well. They perform roughly 20% better than models based on H-bond energy alone. In addition, they can accurately identify a large fraction of the least stable H-bonds in a conformation. In most tests, about 80% of the 10% H-bonds predicted as the least stable are actually among the 10% truly least stable. The important attributes identified during the tree construction are consistent with previous findings. CONCLUSIONS: We use inductive learning methods to build protein-independent probabilistic models to study H-bond stability, and demonstrate that the models perform better than H-bond energy alone.

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.

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.

The minimal inhibitory rules for information systems can be used for construction of classifiers. We show that almost all information systems from a certain large class of information systems have relatively short minimal inhibitory rules. However, the number of such rules is not polynomial in the number of attributes and the number of objects. This class consists of all k-valued information systems, k ⩾ 2, with the number of objects polynomial in the number of attributes. Hence, for efficient construction of classifiers some filtration techniques in rule generation are necessary. Another way is to work with lazy classification algorithms based on inhibitory rules.

In 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.

In 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.

An 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.

The paper is devoted to investigation of behavior of global Shannon functions which produce unimprovable upper bounds on time complexity of decision trees over arbitrary information systems.

Upper 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.

We study the relationships between the complexity of a task description and the minimal complexity of deterministic and nondeterministic decision trees solving this task. We investigate decision trees assuming a global approach i.e. arbitrary checks from a given check system can be used for constructing decision trees.

We investigate decision trees for decision tables. We present upper and lower bounds on the minimal decision tree depth. Some bounds are expressed by parameters of decision rule systems constructed for decision tables.

Lower and upper bounds for the depth of decision trees computing Boolean functions are established and Shannon functions of the decision tree depth are determined for closed classes of Boolean functions.

We consider decision trees with questions from an infinite set and time complexity measures. We investigate decidability conditions for two optimization problems for decision trees.