This question was partially answered on Are decision trees sensitive to translations in feature space?, but no references were provided for "Gini impurity and entropy measures are translation invariant".
I couldn't find material relating to this topic, so does anyone know either:
a) Why Gini is translation invariant, or
b) Why the results of a decision tree would be otherwise insensitive to translations (e.g. log) in the feature space?
Thanks.
$\begingroup$
$\endgroup$
asked Dec 30, 2017 at 15:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
It depends on what algorithm is being used to build the tree. CART trees are invariant to scale changes so a log transform should not change the resulting tree. However, the values of the split rules will be changed to the log scale.
The reason for this is because the splitting process sorts each feature (numeric) and then checks midpoints between successive observations for impurity improvement based on splits at the interval point. The maximum across observations and features is chosen for that node and the process continues. This means that if you rescale any feature(s) as long as the relative ordering of feature values is maintained-which a log transform will maintain-the tree will be the same but the split values will be log-transformed.
answered Dec 30, 2017 at 16:29
-
$\begingroup$ Yes, thanks, I was referring to trees grown via CART. Do you have any information as to why CART trees are invariant to scale/ non-linear transformations? $\endgroup$ Commented Dec 30, 2017 at 17:12
-
$\begingroup$ @DataAnalyticsAnalyst will add a description of why CART trees are invariant to scale changes to my answer. $\endgroup$ Commented Dec 30, 2017 at 17:15
-
$\begingroup$ Wouldn’t the only issues here be with in machine precision? That is, taking the log of a very small number could aid in sorting; I’m thinking similar to how we always take the log of the likelihood in maximum likelihood estimation. $\endgroup$ Commented Dec 30, 2017 at 18:33
-
$\begingroup$ @Mark White -> Not sure how taking a log transform would aid in sorting. Assuming all observations are positive the log transform preserves the ordering. Most sorting algorithms use a binary comparison with a partial ordering so the numeric magnitudes are (usually) not relevant. What did you have in mind? $\endgroup$ Commented Dec 31, 2017 at 21:09
-
1$\begingroup$ Note that there are also tree induction algorithms that do not only rely on tests of binary splits at midpoints but also on tests of linear associations (e.g., the CTree algoirthm with default settings). Consequently, such algorithms are invariant against linear transformations but not nonlinear transformations (like logs). $\endgroup$ Commented Jan 7, 2018 at 20:34