A binary complete decision table with many-valued decisions is a table with n attributes and 2^(n) pairwise distinct rows filled with numbers from the set{0,1}.Each row of this table is labeled with a nonempty finite ...A binary complete decision table with many-valued decisions is a table with n attributes and 2^(n) pairwise distinct rows filled with numbers from the set{0,1}.Each row of this table is labeled with a nonempty finite set of decisions.For a given row of the table,the task is to find a decision from the set of decisions attached to the row.Such tables are generalizations of Boolean functions.They can also be viewed as representations of various problems related to systems of decision rules.In this paper,we consider three types of classes of binary complete decision tables with many-valued decisions,closed with respect to removal of columns and changing of decisions.For tables from these classes,we study the relationships between the minimum weighted depth of deterministic,nondeterministic,and(for one type of classes)strongly nondeterministic decision trees and the total weight of attributes attached to columns.Note that nondeterministic decision trees and strongly nondeterministic decision trees for decision tables can be interpreted as a way of representing the two types of systems of decision rules for these tables.展开更多
We consider various tasks of recognizing properties of DRSs(Decision Rule Systems)in this paper.As solution algorithms,DDTs(Deterministic Decision Trees)and NDTs(Nondeterministic Decision Trees)are used.An NDT can be ...We consider various tasks of recognizing properties of DRSs(Decision Rule Systems)in this paper.As solution algorithms,DDTs(Deterministic Decision Trees)and NDTs(Nondeterministic Decision Trees)are used.An NDT can be considered as a representation of a DRS that satisfies the conditions of the considered task and covers all potential inputs.It has been shown that the minimum depth of a DDT solving the task does not exceed the square of the minimum depth of an NDT.The growth of the minimum number of nodes in DDTs and NDTs can be exponential with the size of the original DRSs.There-fore,in the general case,it is better to simulate the behavior of the DT(Deci-sion Tree)on the given tuple of feature values rather than building the entire tree.We propose a greedy algorithm for such modeling and study its efficiency for a class of tasks of recognizing properties of DRSs.The obtained results may be of interest for data analysis in which both DRSs and DTs are intensively studied.In particular,these results make one think about the possibilities of transforming DRSs into DTs.展开更多
基金supported by King Abdullah University of Science and Technology(KAUST).
文摘A binary complete decision table with many-valued decisions is a table with n attributes and 2^(n) pairwise distinct rows filled with numbers from the set{0,1}.Each row of this table is labeled with a nonempty finite set of decisions.For a given row of the table,the task is to find a decision from the set of decisions attached to the row.Such tables are generalizations of Boolean functions.They can also be viewed as representations of various problems related to systems of decision rules.In this paper,we consider three types of classes of binary complete decision tables with many-valued decisions,closed with respect to removal of columns and changing of decisions.For tables from these classes,we study the relationships between the minimum weighted depth of deterministic,nondeterministic,and(for one type of classes)strongly nondeterministic decision trees and the total weight of attributes attached to columns.Note that nondeterministic decision trees and strongly nondeterministic decision trees for decision tables can be interpreted as a way of representing the two types of systems of decision rules for these tables.
基金supported by King Abdullah University of Science and Technology(KAUST).
文摘We consider various tasks of recognizing properties of DRSs(Decision Rule Systems)in this paper.As solution algorithms,DDTs(Deterministic Decision Trees)and NDTs(Nondeterministic Decision Trees)are used.An NDT can be considered as a representation of a DRS that satisfies the conditions of the considered task and covers all potential inputs.It has been shown that the minimum depth of a DDT solving the task does not exceed the square of the minimum depth of an NDT.The growth of the minimum number of nodes in DDTs and NDTs can be exponential with the size of the original DRSs.There-fore,in the general case,it is better to simulate the behavior of the DT(Deci-sion Tree)on the given tuple of feature values rather than building the entire tree.We propose a greedy algorithm for such modeling and study its efficiency for a class of tasks of recognizing properties of DRSs.The obtained results may be of interest for data analysis in which both DRSs and DTs are intensively studied.In particular,these results make one think about the possibilities of transforming DRSs into DTs.
