1
$\begingroup$

I was talking with an ex-fellow worker and he told me that the decision tree implicitly applies a feature selection. He told me that the most important feature is higher in the tree because of the usage of information gain criteria.

What does he mean with this and how does this work?

$\endgroup$
  • $\begingroup$ Hi Jennifer! Do you know how a decision tree is created? Have you ever looked at the details of a decision tree learning algorithm? $\endgroup$ – nbro Nov 24 '19 at 0:47
  • $\begingroup$ @nbro Yes, I think this is due to usage of the information gain criteria is that correct? $\endgroup$ – jennifer ruurs Nov 24 '19 at 3:01
  • 1
    $\begingroup$ @jenniferruurs There are different ways of creating decision trees. IG is one metric that can be used to guide the creation of the decision tree (how to split the dataset). There are other metrics, such as Gini impurity or variance reduction. $\endgroup$ – nbro Nov 24 '19 at 22:25
  • $\begingroup$ @nbro thank you, so Gini impurity and variance reduction are implicitly also feature selection criteria? $\endgroup$ – jennifer ruurs Nov 25 '19 at 5:32
2
$\begingroup$

Consider a dataset $S \in \mathbb{R}^{N \times (M + 1)}$ with $N$ observations (or examples), where each observation $S_i \in \mathbb{R}^{M + 1}$ is composed of $M$ elements, one value for each of the $M$ features (or independent variables), $f_1, \dots f_M$, and the corresponding target value $t_i$.

A decision tree algorithm (DTA), such as the ID3 algorithm, constructs a tree, such that each internal node of this tree corresponds to one of the $M$ features, each edge corresponds to one value (or range of values) that such a feature can take on and each leaf node corresponds to a target. There are different ways of building this tree, based on different metrics to choose the features for each internal node and based on whether the problem is classification or regression (so based on whether the targets are classes or numeric values).

For example, let's assume that the features and the target are binary, so each $f_k$ can take on only one of two possible values, $f_{k} \in \{0, 1\}, \forall k$, and $t_i \in \{0, 1\}$ (where the index $i$ correspond to the $i$th observation, while the index $k$ correspond to the $k$th column or feature of $S$). In this case, a DTA first chooses (based on some metric, for example, the information gain) one of the $M$ features, for example, $f_j$, to associate it with the root node of the tree. Let's call this root node $f_j$. Then $f_j$ will have two branches, one for each of the binary values of $f_j$. If $f_j$ were a ternary variable, then the node corresponding to $f_j$ would have three branches, and so on. The DTA recursively chooses one of the remaining features for each node of the child branches. The DTA does this until all features have already been selected. In that case, we will have reached a leaf node, which will correspond to one value of the target variable. When the DTA chooses a feature for a node, all observations of the dataset $S$ that take on the first binary value of that feature will go in the branch corresponding to that value and all other observations will go in the other branch. So, in this way, the DTA splits the dataset based on the features.

The following diagram represents a final decision tree built by a DTA.

enter image description here

You can see that the first feature selected (for the root node) by the DTA is "Is it male?", which is a binary variable. If yes, then, on the left branch, we have another internal node, which corresponds to another feature and, at the same time, to all observations associated with a male. However, on the right branch, we have a leaf node, which corresponds to one value of the target, which, in this case, is a probability (or, equivalently, a numerical value in the range $[0, 1]$). The shape of the tree depends on the dataset and DTA algorithm. Therefore, different datasets and algorithms might result in different decision trees.

So, yes, you can view a decision tree algorithm as a feature selection or, more precisely, feature splitting algorithm.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ You are very good at explaining things, i have read a lot of literature but could not find a explanation that was this clear! $\endgroup$ – jennifer ruurs Nov 25 '19 at 21:00
  • $\begingroup$ @jenniferruurs I'm glad I helped you, but note that I've simplified a little bit the explanation (but, at the same time, I've tried to introduce a rigorous notation to clarify the concepts). It's been a while I've not worked with decision trees. However, if you want to go into the details, you should read about the specific algorithms, like ID3 algorithm. $\endgroup$ – nbro Nov 25 '19 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.