Answers.Body: <p>Consider a dataset <span class="math-container">$S \in \mathbb{R}^{N \times (M + 1)}$</span> with <span class="math-container">$N$</span> observations (or examples), where each observation <span class="math-container">$S_i \in \mathbb{R}^{M + 1}$</span> is composed of <span class="math-container">$M$</span> elements, one value for each of the <span class="math-container">$M$</span> features (or independent variables), <span class="math-container">$f_1, \dots f_M$</span>, and the corresponding target value <span class="math-container">$t_i$</span>. </p>
  
  <p>A <a href="https://en.wikipedia.org/wiki/Decision_tree_learning" rel="nofollow noreferrer">decision tree algorithm (DTA)</a>, such as the <a href="https://en.wikipedia.org/wiki/ID3_algorithm" rel="nofollow noreferrer">ID3 algorithm</a>, constructs a tree, such that each internal node of this tree corresponds to one of the <span class="math-container">$M$</span> 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).</p>
  
  <p>For example, let's assume that the features and the target are binary, so each <span class="math-container">$f_k$</span> can take on only one of two possible values, <span class="math-container">$f_{k} \in \{0, 1\}, \forall k$</span>, and <span class="math-container">$t_i \in \{0, 1\}$</span> (where the index <span class="math-container">$i$</span> correspond to the <span class="math-container">$i$</span>th observation, while the index <span class="math-container">$k$</span> correspond to the <span class="math-container">$k$</span>th column or feature of <span class="math-container">$S$</span>). In this case, a DTA first chooses (based on some metric, for example, the <a href="https://en.wikipedia.org/wiki/Information_gain_in_decision_trees" rel="nofollow noreferrer">information gain</a>) one of the <span class="math-container">$M$</span> features, for example, <span class="math-container">$f_j$</span>, to associate it with the root node of the tree. Let's call this root node <span class="math-container">$f_j$</span>. Then <span class="math-container">$f_j$</span> will have two branches, one for each of the binary values of <span class="math-container">$f_j$</span>. If <span class="math-container">$f_j$</span> were a ternary variable, then the node corresponding to <span class="math-container">$f_j$</span> 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 <span class="math-container">$S$</span> 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.</p>
  
  <p>The following diagram represents a final decision tree built by a DTA.</p>
  
  <p><a href="https://i.sstatic.net/tmrRW.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tmrRW.png" alt="enter image description here"></a></p>
  
  <p>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 <em>yes</em>, 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 <span class="math-container">$[0, 1]$</span>). The shape of the tree depends on the dataset and DTA algorithm. Therefore, different datasets and algorithms might result in different decision trees.</p>
  
  <p>So, yes, you can view a decision tree algorithm as a feature selection or, more precisely, feature <em>splitting</em> algorithm. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T21:00:09.590Z
Answers.Text: You are very good at explaining things, i have read a lot of literature but could not find a explanation that was this clear!
Answers.UserDisplayName: jennifer ruurs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T21:27:08.360Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T17:35:41.533Z
Answers.LastActivityDate: 2019-11-25T18:51:00.740Z
Answers.LastEditDate: 2019-11-25T18:51:00.740Z
Answers.UserDisplayName: nbro
Body: <p>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.</p>
  
  <p>What does he mean with this and how does this work?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-24T00:47:45.563Z
Comments.Text: Hi Jennifer! Do you know how a decision tree is created? Have you ever looked at the details of a decision tree learning algorithm?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-24T03:01:18.613Z
Comments.Text: @nbro Yes, I think this is due to usage of the information gain criteria is that correct?
Comments.UserDisplayName: jennifer ruurs
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-24T22:25:50.500Z
Comments.Text: @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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-25T05:32:04.670Z
Comments.Text: @nbro thank you, so Gini impurity and variance reduction are implicitly also feature selection criteria?
Comments.UserDisplayName: jennifer ruurs
Tags: <machine-learning><decision-trees><feature-selection>
Title: How does the decision tree implicitly do feature selection?
UserDisplayName: jennifer ruurs
ThreadText: # How does the decision tree implicitly do feature selection?
  
  (Asked by: username_0 on 2019-11-23)
  
  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?
  
  **Tags:** machine-learning, decision-trees, feature-selection
  > **Comments:**
  > **username_1**: Hi Jennifer! Do you know how a decision tree is created? Have you ever looked at the details of a decision tree learning algorithm?  
  > **username_0**: @nbro Yes, I think this is due to usage of the information gain criteria is that correct?  
  > **username_1**: @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.  
  > **username_0**: @nbro thank you, so Gini impurity and variance reduction are implicitly also feature selection criteria?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-25. Score: 3 | Accepted answer
  
  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)](https://en.wikipedia.org/wiki/Decision_tree_learning), such as the [ID3 algorithm](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Information_gain_in_decision_trees)) 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](https://i.sstatic.net/tmrRW.png)](https://i.sstatic.net/tmrRW.png)
  
  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.
  
  > **Comments:**
  > **username_0**: You are very good at explaining things, i have read a lot of literature but could not find a explanation that was this clear!  
  > **username_1**: @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.  
  
  ---
  
  