Why Does Tree and Ensemble based Algorithm don't need feature scaling?

Question

Recently, I've been interested in Data analysis.
So I researched about how to do machine-learning project and do it by myself.
I learned that scaling is important in handling features.
So I scaled every features while using Tree model like Decision Tree or LightGBM.
Then, the result when I scaled had worse result.
I searched on the Internet, but all I earned is that Tree and Ensemble algorithm are not sensitive to variance of the data.
I also bought a book "Hands-on Machine-learning" by O'Relly But I couldn't get enough explanation.
Can I get more detailed explanation for this?

Answer 1

Though I don't know the exact notations and equations, the answer has to do with the Big O Notation for the algorithms.

Big O notation is a way of expressing the theoretical worse time for an algorithm to complete over extremely large data sets. For example, a simple loop that goes over every item in a one dimensional array of size n has a O(n) run time - which is to say that it will always run at the proportional time per size of the array no matter what.

Say you have a 2 dimensional array of X,Y coords and you are going to loop across every potential combination of x/y locations, where x is size n and y is size m, your Big O would be O(mn)

and so on. Big O is used to compare the relative speed of different algorithms in abstraction, so that you can try to determine which one is better to use.

If you grab O(n) over the different potential sizes of n, you end up with a straight 45 degree line on your graph.

As you get into more complex algorithms you can end up with O(n^2) or O(log n) or even more complex. -- generally though most algorithms fall into either O(n), O(n^(some exponent)), O(log n) or O(sqrt(n)) - there are obviously others but generally most fall into this with some form of co-efficient in front or after that modifies where they are on the graph. If you graph each one of those curves you'll see which ones are better for extremely large data sets very quickly

It would entirely depend on how well your algorithm is coded, but it might look something like this: (don't trust me on this math, i tried to start doing it and then just googled it.)

Fitting a decision tree of depth ‘m’:

• Naïve analysis: 2m-1 trees -> O(2m-1 n d log(n)).
• each object appearing only once at a given depth: O(m n d log n)

and a Log n graph ... well pretty much doesn't change at all even with sufficiently large numbers of n, does it?

so it doesn't matter how big your data set is, these algorithms are very efficient in what they do, but also do not scale because of the nature of a log curve on a graph (the worst increase in performance for +1 n is at the very beginning, then it levels off with only extremely minor increases to time with more and more n)

Answer 2

Do not confuse trees and ensembles (which may be consist from models, that need to be scaled). Trees do not need to scale features, because at each node, the entire set of observations is divided by the value of one of the features: relatively speaking, to the left everything is less than a certain value, and to the right - more. What difference then, what scale is chosen?