Is Decision Tree Obsolete in Its Original Form? A Burning Debate

Decision tree is a binary tree that recursively splits the dataset until we are left with the pure leaf nodes which defines the decision i.e. the data with only one type of class. In decision tree there are two kinds of nodes: decision nodes and leaf nodes. The former one contains a condition to split the data and the latter one helps us to decide the class of a new data point. Since, decision tree internally is a bunch of nested if-else statements and we still consider it as a Machine learning approach because there are many possible splitting conditions which need to learn which feature to take and the corresponding correct threshold values to optimally split the data. The goal of a decision tree model is to get the pure leaf nodes and for that the model iteratively splits the data until all the nodes are processed. This is the theoretical approach about the working of decision tree [1].

Mathematically, it can be processed using information theory. More precisely the model will choose the split that maximizes the information gain. To calculate the information gain we first need to understand the information contained in a state. Imagine we are predicting the class of randomly picked points. Only half of time we will be correct, i.e. the state has the highest uncertainty or impurity. The way to quantify this is to use the entropy, i.e. if the entropy value is highest then we are uncertain about the randomly picked points and then it needs more bits to describe its state. The entropy can be calculated as (1):

Entropy $=\sum-p_{i} \log p_{i}$     (1)

Here, $p_{i}$ is the probability of class $i$.

The highest possible value of entropy for a binary class is 1 and the lowest value for the entropy is 0 (pure node). To find the information gain corresponding to a split we need to subtract the combined entropy of child node from the entropy of parent nodes as shown below (2):

$I G=E_{(\text {parent })}-\sum w_{i} E_{(\text {child })_{i}}$     (2)

Here, $w_{i}$ is the relative size of the child node with respect to the parent node. In reality the node compares the every possible split and takes the one with the maximum information gain. So, the model traverses through every possible feature and feature value to search for the best feature and the corresponding threshold. Thus, we can point out with this that decision tree is a greedy algorithm where it selects the best split that maximizes information gain. It does not backtrack and change a previous split and this doesn’t guarantee that we will get most optimal set of splits but greedy search makes our training a lot faster and it works really good despite of its simplicity [2].

Since all the decision tree inducers more or less follow the same procedure to construct the decision tree from a given set of data. The major goal is to optimize the output results which can be done by improving the accuracy measure and by reducing the error content. Furthermore, it is not only to increase the accuracy measure but it also depends on the time and space complexity of the algorithm and the number of rules generated in optimizing the overall results. This may include the pruning factors of the algorithm as well. Thus, finding out the best optimized algorithm is a quite hard task as we don’t have to check the accuracy measure only but other factors are also taken into consideration [5]. The other factors include recall, sensitivity, specificity, Cohen kappa, F-measure etc. These factors are basically used for information retrieval and are used to evaluate the performance in determining the strength of an algorithm. In the field of data sciences these statistical factors specifically allow us to visualize the performance of an algorithm. Some of these machine learning measures are calculated in this study and are shown in below table (Table 2).

It has been proposed that finding the minimal decision tree from the training set is NP-hard and constructing the minimal decision tree from the expected set of outcomes is NP-complete. Furthermore, it has been proposed that finding the optimal decision tree is also a NP-hard problem.

Optimal decision tree construction is only feasible for small task where smaller set of data is present or where smaller problems are taken into account. Thus, constructing a decision tree using above mentioned decision tree inducers may not be sufficient for optimizing the performance alone.

3.1 Potentials with decision tree inducers

• Since it is self-explanatory that decision trees are easy to track i.e. the smaller the tree is the more it is easy to follow. At different levels of complex decision regions like high dimensional space the combination of smaller and simpler decision regions can be used to approximate the overall complexity [5].
• Unnecessary assumptions can be reduced when tree classifiers are used in place of single stage classifiers. This can help in increasing the efficiency of the decision tree inducers used [6].
• One of the major problems of high-dimensionality distributions in case of multivariate analysis can be reduced using any of the decision tree inducer by using a smaller number of features at different internal node at each level without affecting the overall performance [7].
• In discriminating among the classes only one subset of features is used in case of single-stage classifier which is chosen by a globally optimal criterion (GBC). Whereas, in case of any decision tree inducer subsets of features can be used at different levels of a tree thereby, improving the performance over single-stage classifier [7].

3.2 Problems with decision tree inducers

• Overlapping is one of the major drawbacks in decision tree inducers when the size of the data is large i.e. the number of classes are very large and this may have an effect on the space and time complexity of the algorithm.
• Accumulation of errors at each level of the large decision trees can reduce the performance and efficiency. Thus, it may also reduce the overall accuracy of the decision tree [8].
• Due to the large size of the decision tree, the overall design of the tree may effect on the performance of the decision tree inducer. Thus, it is very important on the overall designing of the decision tree [8].
• Many Decision tree inducers usually work on discrete values, they usually follow the greedy approach, and this may lead to the over-sensitivity to the training set of data and irrelevant data (noise) [9].
• Since there are many advantages of simple decision tree inducers but there are many disadvantages as well which needs to be rectified. To overcome the problems many-upgraded version are introduced which are readily used now a day. Some of these upgraded versions are illustrated in section 5.

5.1 Random Forest (RF)

Random forest is considered as the most popular supervised machine learning algorithm which is capable of implementing both classification and regression tasks. It is an ensemble method that is used to train the different decision trees in a parallel manner with bootstrapping which is followed by the aggregation. This process is called as Bagging in which number of different decision trees are trained in different subsets and for the final decision it aggregates the individual decisions from the different individual decision trees and consequently it shows good generalization. Implementation of RF classifier on a dataset that has four features (A1, A2, A3, and A4) and two classes (Z = Y and N). RF classifier is an ensemble method that trains several decision trees in parallel with bootstrapping followed by aggregation as shown in Figure 5. Each tree is trained on different subsets of training sample and features [11].

5.png

Figure 5. Random Forest Model

The major advantage of using random forests over decision tree approach is that it can handle the missing values and maintains the accuracy for missing data. It also handles the large set of data with higher dimensionalities without over-fitting the model. i.e. it inclines to outrange most of the other classification methods with respect to the accuracy without over-fitting [11].

Thus, if the number of trees increases the overfitting problem will reduce and thus converges the generalization error. In other words, reducing the number of analytical variables can results in weakening of each individual tree of the model, which leads to reduce the correlation between the trees and improve the accuracy of the model. Therefore, it is necessary to choose a large number of trees and to minimize the generalization error by optimizing the number of predictive variables [11].

In building the random forest, time and space complexity play a major role in its performance. Initially, before building a random forest, we have to define the number of sub-trees a random forest contains, and this can be denoted as "$n$-tree", where $n$ defines the total number of sub-trees. We further need to take care of the number of variables we want to sample at each node, and it can be denoted by "$m$-try", where "$m$" denotes the number of variables or attributes.

Thus, in order to build one tree with "m-try" variable, the complexity would be:

$\mathrm{O}(\operatorname{mtry} * \mathrm{n} \log (\mathrm{n}))$

Furthermore, if the number of sub-trees be "n-tree", then the complexity would be:

$\mathrm{O}($ ntree $*$ mtry $* \operatorname{nlog}(\mathrm{n}))$

where $\mathrm{n} \log (\mathrm{n})$ is assumed as the depth of the tree and is treated as the worst case complexity scenario.

5.2 Distributed Decision Trees (DDT)

In practice, amongst the diverse situations for classification involving the large sets of data including big datasets where the volume of data is huge to manage and evaluate. In such situations a distributed implementations are carried out, i.e. the concept of distributed decision trees are implemented where a particular number of decision trees are generated based on the number of partitions carried out in the input data [12]. Suppose if there are n number of partitions in the input data then it will result in the n number of sub trees and the overall prediction and the classification are carried out on the basis of voting i.e. the individual performances or predictions of the sub trees are recorded and the final prediction and classification is calculated based on these individual performances by implementing the concept of voting technique [12], .i.e. Number of Decision Trees (Models) = n, Where n is the number of splits/partitions.

16.png

Figure 6. Distributed Decision Tree Model

The graphical representation of the Distributed Decision Tree model is shown in Figure 6.

In distributed decision trees the prediction of one sub tree is independent on other sub trees, i.e. all the sub trees predict individually and then voting technique is applied in which the majority of the decisions will be chosen as the final output for the prediction. Suppose if there are 1000 entries present in the original dataset and the data is split into 5 partitions i.e. 5 decision trees will be created and if the target attribute is binary classified [0,1] and every decision tree either predicts 0 or 1. Then the final output will be the majority count of 0 or 1 from all the sub trees [13].

5.2.1 Steps for implementing distributed decision tree

The distributed decision tree follows a simple approach in its implementation process. In order to implement the distributed decision tree on a particular set of data, it needs to be divided into a certain number of partitions based on a particular attribute. Suppose the data used in this paper originally contained the station_ID as one of its attributes. The station_ID contains discrete values of three stations (42044, 42027, and 42026) [11], and these three stations belong to the three different regions (south zone, north zone, and central zone) of the UT of the Jammu and Kashmir region of India. Thus, we have three subsets of original data, and in order to check the individual performances of these subsets, we need the concept of distributed decision trees. A voting classifier was used to validate the prediction's final output value. A voting classifier declares the majority value of "Yes" or "No" as the final output of the prediction class. Suppose two of the subsets arrive with a decision of yes, and one subset arrives with a decision of no. Then, the final output value for the prediction class will be the majority one, i.e., yes.

5.3 Model Trees (MT)

Model tree is another decision tree extension algorithm where a step wise implementation is carried out to construct a tree. This step wise implementation follows a two level approach where at first level any simple decision tree inducer (C4.5) is used for the construction of decision tree and latter at second level model tree functions are used at the leaf nodes [13].

For example, The C4.5 builds a decision tree based on top-down, recursive and “divide and conquer” approach. It constructs the decision tree based on the information gain theory concept in which the splitting attribute which has the highest information gain ratio will be chosen as the splitting node parameter. The information gain can be defined as the reduction in the entropy after the dataset is divided on an attribute. In the next step the regression at each leaf node is applied which can result in the pruning of the original decision tree inducer (C4.5). Pruning of trees at interior nodes are then replaced by the regression plane instead of a constant value which can also results in the rules generated by the LMT. This is usually done when the branches of the tree are not useful in the later stages. The main advantage of this step is that it reduces the level of complexity of the classifier without affecting the overall performance of the original tree. There are two primary strategies for pruning:

1) With reduced error pruning in which the most popular class replace the nodes and starting at leaves. This approach is used to simplify the data and increasing speed. M5 model tree follows a greedy approach for minimization of errors at each internal node in which Standard deviation reduction is calculated one node at a time and is given by (3):

$S D R=\frac{S D(T)-\sum S D\left(T_{i}\right)\left|T_{i}\right|}{|T|}$     (3)

Pruning of trees at interior nodes are then replaced by the regression plane instead of a constant value which can also results in the rules generated by the M5 Model tree. This is usually done when the branches of the tree are not useful in the later stages. The main advantage of this step is that it reduces the level of complexity of the classifier without affecting the overall performance of the original tree.

2) With cost computing pruning (CCP) where it is used to define the cost-complexity measure of the tree [13, 14]. Logistic model tree (LMT) follows cost-complexity pruning approach in order to reduce the variance of the model and with this, it will have better performance on different types of data. This can be computed as (4):

CCP $=\frac{\operatorname{err}(\operatorname{prune}(T, t), S)-\operatorname{err}(T, S)}{\mid \text { leaves }(T)|-| \text { leaves }(\operatorname{prune}(T, t)) \mid}$     (4)

where, $\operatorname{err}(T, S)$ is the error rate of tree T over dataset $S$, and ( $\operatorname{prune}(T, t), S)$ is the tree obtained by pruning the sub trees $t$ after the regression is applied on the tree $T$.

The basic methodology of Model trees is shown in below Figure 7.

7.png

Figure 7. Model Tree

Model trees can predict a numeric value like an ordinary regression tree works, that is defined over a permanent number of numeric or nominal parameters but distinctly model trees construct a piecewise or Hamiltonian linear estimations to the target function [15]. Thus, the resultant model tree constructs a tree with the logistic or linear regression functions at the leaf nodes. The principal advantage of using this machine learning methodology is that it acts as a white box learning model where each and every step is defined by the mathematical expression that shows the dependencies between the attributes. Furthermore, model trees can perform feature selection implicitly, data preparation becomes an easy process i.e. less effort needs to be taken while performing data preparation [16-27], and it can handle missing values also.

In this approach the experimental evaluation of some decision tree inducers and decision tree extensors has been carried out on the geographical data of Kashmir province. For the simulation study an open source data Analytics tool called KNIME, has been used. The experiment was carried out on the 70-30 ratio in which 70% was used as the training set and 30% was used for testing purposes. The dataset consists of 4 independent continuous parameters which includes minimum and maximum temperatures, Humidity at two different intervals and one dependent variable rainfall with continuous values [19].

Table 2. Accuracy statistics

In order to check the performances of both DT inducers and DT extensors individual implementation has been carried out on same set of data. It was observed that all the algorithms show more or less same performance but Model trees shows better performance as compared to other algorithms [20].

Table 2 shows the individual performances of the various algorithms (Both Inducers and Extensors) used in predicting the rainfall of Kashmir province.

We can confirm from the above table that the number of rules in LMT are only 10 with an accuracy of 87.23%. But this doesn’t define that LMT always produces better results than any traditional decision tree inducers [21-25]. The performance measure of any algorithm depends on the type of data on which the work has been carried out [26]. In this study, although the accuracy has been increased in logistic model tree but internally the working of logistic model tree is totally dependent on methodology of basic decision tree inducer (ID3, C4.5 etc.). So, it is very tough to say that decision tree in its original form has lost its applicability or capability.

Performance of an algorithm be it Decision Tree, or its modifications/ up-gradations is primarily specific to dataset and no algorithm can be generalized. The applicability of an algorithm is primarily dependent on the type of the dataset used. Thus, in this study we conclude that dataset determine the applicability and audibility of an algorithm in generation and accordingly same is applicable to decision tree. Thus, the question about the obsoleteness of the decision tree is answered and its applicability in today’s machine learning world is as relevant as its successors.

Since all the experiments were performed on only historical geographical dataset of Kashmir province, now there are two aspects to this; i.e., 1) does the same theory hold for other datasets (like academic datasets, agricultural datasets, medical datasets etc.) or not? 2) The geographical datasets of other regions like Shimla, where the temperature remains more or less same as in Kashmir province or Rajasthan, where the temperature is too hot, does it hold the same here also? This remains a question, which will be carried as a future work for this study.