In the paper, we study a greedy algorithm for construction of approximate 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 nd a decision from the set attached to this row. We use an uncertainty measure which is the number of boundary subtables. We present also experimental results for data sets from UCI Machine Learning Repository for proposed approach and approach based on generalized decision.
In the paper, we study decision trees for decision tables with many-valued
decisions. We can meet such tables when we work with experimental or statistical
data. In such data sets, we often have groups of rows with equal values of
conditional attributes but, probably, di erent values of the decision attribute. In
this case, instead of a group of rows, we can consider one row given by values
of conditional attributes, and we attach to this row a set of decisions: either all
decisions for rows from the group, or k the most frequent decisions for rows from
the group [
In the rough sets theory [
In our approach, we study a problem of nding of an arbitrary decision or
one of the most frequent decisions from the set of decisions. Proposed approach
was considered in [
Decision tables with many-valued decisions can be considered as decision
tables with an incomplete information because we don't know which decision
should be chosen from the set of decisions. However, an incomplete information
can be interpreted also in situations where instead of a single value of conditional
attribute we have a subset of values of the attribute domain or missing values
of attributes. Z. Pawlak [
In this paper, we present a greedy algorithm for construction of decision trees
for decision tables with many-valued decisions. Theoretical results connected
with a greedy algorithm for construction of approximate decision trees were
presented in [
We present an upper bound on the number of steps of the considered algorithm. From this bound it follows that, for an arbitrary natural t, the greedy algorithm has polynomial time complexity on tables which have at most t decisions in each set of decisions attached to rows.
In this paper, we consider only binary decision tables with many-valued decisions. However, the obtained results can be extended to the decision tables lled by numbers from the set f0; : : : ; k 1g, where k 3. One of the aims of this paper is to make some comparative study relative to depth and average depth of decision trees for proposed approach and approach based on generalized decision. We present experimental results for data sets from UCI ML Repository.
This paper consists of six sections. Section 2, contains main notions. In Sect. 3, we present a theorem for decision tables with at most t decisions in each set of decisions attached to rows. In Sect. 4, we study a greedy algorithm for -decision tree construction. Section 5 contains experimental results, Sect. 6 { conclusions.
In this section, we consider de nitions of notions corresponding to decision tables with many-valued decisions.
A (binary) decision table with many-valued decisions is a rectangular table T lled by numbers from the set f0; 1g. Columns of this table are labeled with attributes f1; : : : ; fn. Rows of the table are pairwise di erent, and each row is labeled with a nonempty nite set of natural numbers (set of decisions). Note that each (binary) decision table with one-valued decisions can be interpreted also as a decision table with many-valued decisions. In such table, each row is labeled with a set of decisions which has one element.
We will say that T is a degenerate table if either T has no rows, or the intersection of sets of decisions attached to rows of T is nonempty.
A decision which belongs to the maximum number of sets of decisions attached to rows in T is called the most common decision for T . If we have more than one such decisions we choose the minimum one. If T is empty then 1 is the most common decision for T .
A table obtained from T by removal of some rows is called a subtable of T . A subtable T 0 of T is called a boundary subtable if T 0 is not degenerate but each proper subtable of T 0 is degenerate. We denote by B(T ) the number of boundary subtables of the table T . It is clear that T is a degenerate table if and only if B(T ) = 0. The value B(T ) will be interpreted as uncertainty of T . An example of boundary subtables for decision table T0 with many-valued decisions can be found in Fig. 1.
f1 f2 f3 d r1 0 0 0 f1g T0 = rr23 01 10 11 ff11;; 23gg r4 1 1 0 f2; 3g r5 0 0 1 f2g
In the case of generalized decision approach we consider sets of decisions attached to rows of the table T0 as values of the decision attribute (see Fig. 2). The number of boundary subtables for such approach is equal to 10. Each boundary subtable of the table T0 has 2 rows (see Theorem 1).
Let fi1 ; : : : ; fim 2 ff1; : : : ; fng and 1; : : : ; m 2 f0; 1g. We denote by
T (fi1 ; 1) : : : (fim ; m) the subtable of the table T which consists of all rows that at the intersection with columns fi1 ; : : : ; fim have numbers 1; : : : ; m respectively.
nite tree with root in which each terminal node is labeled with a decision (a natural number), and each nonterminal node is labeled node. These edges are labeled with 0 and 1 respectively. with an attribute from the set ff1; : : : ; fng. Two edges start in each nonterminal Let
be a decision tree over T and v be a node of . We attach to the node v a subtable T (v) of the table T . If v is the root of then T (v) = T .
Otherwise, let nodes and edges in the path from the root to v be labeled with attributes fi1 ; : : : ; fim and numbers
subtable T (fi1 ; 1) : : : (fim ; m) of the table T .
It is clear that for any row r of T there exists exactly one terminal node v in such that r belongs to T (v). The decision attached to v will be considered as the result of the work of
on the row r.
Let be a real number such that 0 < 1. We will say that is an -decision tree for T if for any terminal node v of , the inequality B(T (v))
B(T ) holds, and the node v is labeled with the most common decision for T (v). An example of an exact decision tree constructed for the table T0 can be found in Fig. 3, a 0.25-decision tree constructed for the table T0 can be found in Fig. 5. 0 + 3 f1 0 + 1
Q1 sQ f3
Q1 sQ
2 length of a path from the root to a terminal node. We denote by h (T ) the minimum depth of an
-decision tree for the table T . We denote by l( ) a total path length for an arbitrary row
of the table T . It is a length of the path from the root to a terminal node of which accepts . An average depth of is equal to the total path length divided by N (T ) { the number of rows in decision table T . 3
We denote by T ab(t), where t is a natural number, the set of decision tables with
many-valued decisions such that each row in the table has at most t decisions.
Theorem 1. [
Therefore, for tables from T ab(t), there exists a polynomial algorithm for the computation of parameter B(T ). For example, for any decision table T with onevalued decisions (really, for any table from T ab(1)) the equality B(T ) = P (T ) holds where P (T ) is the number of unordered pairs of rows of T with di erent decisions. 4
To construct an -decision tree for T , we rst need to construct all boundary subtables of decision table T and to compute the value of B(T ).
Let be a real number such that 0 < 1. Let T have n columns labeled with attributes f1; : : : ; fn. We now describe an algorithm U which for a given decision table with many-valued decisions constructs an -decision tree U (T ) for the table T .
{ Step 1. Construct a tree consisting of a single node labeled with the table T and proceed to the second step. { Suppose t 1 steps have been already made. The tree obtained at the step t will be denoted by G. { Step (t + 1). If no one node of the tree G is labeled with a table then we denote by U (T ) the tree G. The work of the algorithm U is completed. { Otherwise, we choose a node v in the tree G which is labeled with a subtable of the table T . Let the node v be labeled with the table T 0.
If B(T 0) B(T ) then instead of T 0 we mark the node v with the most common decision for T 0 and proceed to the step (t + 2).
Let B(T 0) > B(T ). Then for i = 1; : : : ; n, we compute the value
Q(fi) = maxfB(T 0(fi; 0)); B(T 0(fi; 1))g: Instead of T 0 we mark the node v with the attribute fi0 where i0 is the minimum i for which Q(fi) has the minimum value. For each 2 f0; 1g, we add to the tree G the node v( ), mark this node with the subtable T 0(fi0 ; ), draw the edge from v to v( ), and mark this edge with . Proceed to the step (t + 2). d
1 a 0.25-decision tree, for decision table T0. All boundary subtables of the decision
The table T0 is not degenerate, so for i 2 f1; 2; 3g, we compute the value of Q(fi): Q(f1) = maxf1; 0g = 1, Q(f2) = maxf2; 0g = 2, Q(f3) = maxf1; 1g = 1. We choose the attribute f1 as a root of the 0.25-decision tree (see Fig. 4).
B(T (f1; 0)) = 1 and B(T (f1; 1)) = 0, so B(T (f1; 0)) 0:25
to 0.25-decision tree the most common decision for the subtable T (f1; 1), and the most common decision for the subtable T (f1; 0). The result of the algorithm U0:25 work for the table T0 is a 0.25-decision tree depicted in Fig. 5. 1 = 3 f1
Q0 sQ
1
Now, we present an upper bound on the number of steps of algorithm U .
Theorem 2. [
makes at most 2N (T ) + 1 steps where N (T ) is the number of rows in T .
From this theorem it follows that for any natural t the algorithm U has a polynomial time complexity on the set T ab(t). Theorem 3. For any real , 0 < table with many-valued decisions T
< 1, and for any nondegenerate decision
h(U (T )) < h0(T ) ln
In this section, we present experimental results. First, we show how we
constructed decision tables with many{valued decisions based on data sets from
UCI Machine Learning Repository. We consider a number of decision tables
from UCI Machine Learning Repository [
RowsAttr
To obtain rows which are labeled with sets containing more than one decision we removed from decision tables more conditional attributes. The information about such decision tables can be found in Table 1. This table contains name of initial table, number of rows (column \Rows"), number of attributes (column \Attr"), spectrum of this table (column \Spectrum"), and names of removed attributes (column \Removed attributes"). Spectrum of decision table with manyvalued decisions is a sequence #1, #2,. . . , where #i, i = 1; 2; : : :, is the number of rows labeled with sets of decision with the cardinality equal to i.
Table 2 presents the depth of -decision trees constructed by the algorithm U , for 2 f0; 0:001; 0:01; 0:2; 0:5g.
Table 3 presents the average depth of -decision trees constructed by the algorithm U , for 2 f0; 0:001; 0:01; 0:2; 0:5g.
Based on results presented in Table 2 and Table 3 we can see that depth and average depth of -decision tree are decreasing when is increasing, till = 0:5. The biggest value of depth of exact decision tree we can observe for decision table \kr-vs-kp-5" and \kr-vs-kp-4". However, if we consider 0.1-decision tree for such decision tables, the depth is equal to 2.
To make some comparative study we also present results of experiments connected with depth and average depth of -decision trees for approach based on generalized decision.
For decision tables described in Table 1 and 2 f0; 0:001; 0:01; 0:2; 0:5g we constructed -decision trees by the greedy algorithm. Table 4 presents depth of constructed -decision trees, Table 5 { the average depth of constructed decision trees, for approach based on generalized decision. the generalized decision. Each input of this table is equal to the value of the depth of an -decision tree for the generalized decision approach divided by the value of the depth of an -decision tree for the proposed approach.
Table 7, based on results from Tables 3 and 5, presents comparison of the average depth of -decision trees for proposed approach and approach based on generalized decision. Each input of this table is equal to the value of average depth of -decision tree for generalized decision approach divided by the value of average depth of -decision tree for proposed approach.
The di erence relative to depth and average depth of -decision trees is noticeable for small values of (see Table 6 and Table 7). In case of 2 f0:2; 0:5g values of depth and average depth of -decision trees are almost the same. However, for Table 6, for decision table \nursery-4", for = 0:0 and = 0:01, the depth of -decision tree for proposed approach is 2 times shorter than for generalized decision approach. We can also nd decision table (\breast-cancer-1" and = 0:1) where the depth of -decision tree for proposed approach is longer (50%) than the depth of -decision tree for generalized decision approach. Similar situation according to comparison of average depth, we can observe in Table 7. We presented the algorithm U , 0 < 1, for construction of -decision trees, for decision tables with many-valued decisions. We showed that for an arbitrary natural t, the considered algorithm has polynomial time complexity on tables which have at most t decisions in each set of decisions attached to rows. Based on results presented in Sect. 5, we can observe that greedy algorithm U constructs, for decision tables with many-valued decisions, -decision trees with relatively short depth.
Based on results connected with comparison we can see that the depth and average depth of -decision trees constructed in the framework of our approach (one decision from the set of decisions attached to row) is usually less than the depth and average depth of -decision trees constructed in the framework of generalized decision approach (all decisions from the set of decisions attached to row). So, if it is enough to nd only one decision, our approach can be used. However, it is necessary to nd simpler uncertainty measures for greedy algorithm since the work with boundary subtables is too complicated.