2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Data Science Officer Dec 30 '17 at 17:12
  • $\begingroup$ @DataAnalyticsAnalyst will add a description of why CART trees are invariant to scale changes to my answer. $\endgroup$ – Lucas Roberts Dec 30 '17 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$ – Mark White Dec 30 '17 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$ – Lucas Roberts Dec 31 '17 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$ – Achim Zeileis Jan 7 '18 at 20:34

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.