Understanding decision tree concept

Question

I am referring Ehthem Alpaydin, 'Introduction To Machine Learning' book.

Under the chapter 'Decision Trees', I need help with understanding the concept of discriminant and how it is being used in this paragraph:

Each $f_m(x)$ defines a discriminant in the d-dimensional input space dividing it into smaller regions that are further subdivided as we take a path from the root down. $f_m(.)$ is a simple function and when written down as a tree, a complex function is broken down into a series of simple decisions. Different decision tree methods assume different models for $f_m(.)$, and the model class defines the shape of the discriminant and the shape of regions. Each leaf node has an output label, which in the case of classification is the class code and in regression is a numeric value.

Answer 1

In the above image the big square is your $f_m(x)$.

The big square is made up of small partitions. Those partitions are your smaller functions(Partitions) which performs the comparison between your variables and try to find out best possible split.

Here each partition has nearly same labels for classification and nearest numerical values for regression.

The square representation is for 2 dimensions if you want to get for higher dimensions refer the last one with 3 dimensions.

Reference: Elements of Statistical Learning, Basics of Decision trees

Answer 2

Usually, when talking about decision trees, were are referring to the C4.5 algorithm. That is, we build a binary decision tree, where at each node we need to make a decision where we split the data using the rule "variable < value" (if the variable is categorical, you can have an = sign).

How do know what the best split is? Simple, we test all possible combinations of variable and of value, and then choose the split which splits the data in the most egualitarian fashion (closest to 50-50).

How do we know if the data is being well split? We try to minimize metrics such as entropy or maximize metrics such as the Gini coefficient. You want to reduce the original entropy down to zero.

When do you stop? You either stop when you have a single sample in a node or when all samples have the same value. Alternatively, you can define a maximum depth for the decision tree (this is known as pre-pruning) or try to reduce your decision tree afterwards (this is known as post-pruning).

Why are decision trees so fast to create if they test all combinations of variables and values? Well, I lied to you. They don't test all combinations. The metrics used (entropy or gini) can be computed incrementally, so what the algorithms do is to sort the values for each variable, and then incrementally see whether including one more sample improves or reduces the score. But this is a technicality you need not be aware of.

Anything more? You should keep in mind that decision trees do one-ahead optimization. They do not find the global best decision tree. They are myopic. Therefore, if you think two variables are correlated, you should feature engineer a new variable that uses both.

My decision tree is highly variable? Decision trees are know to be very different if the same changes a little bit. This is why people build ensembles of decision trees like random forests by resampling the data to make them stronger. You do lose interpretability: you can no longer draw a decision tree, if you use many of them. See this question for more information on this.

Furthermore, I recommend these resources:

• Visual presentation/animation about decision trees
• Scikit-learn decision trees documentation