How does the decision tree implicitly do feature selection?

Question

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?

Answer 1

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.

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.