How is the threshold parameter practically selected for Scikit learn's decision tree algorithm and how to determine depth of tree?

Question

I am referring to the so-called optimized CART algorithm that is explained on Scikit learn's website: https://scikit-learn.org/stable/modules/tree.html#mathematical-formulation

I would appreciate if anyone can clarify the following:

Referring to section 1.10.7 and 1.10.7.1

1. For each node $m$, a candidate split is $\theta = (j, t_m)$. $j$ is a feature, so it is an integer from $\{1, \ldots, n\}$. I am confused about how $t_m$ is practically selected. Since each $x_i$ is a real $n$-dimensional vector, therefore $t_m$ is a real number. How do we select these real numbers and how many do we select?

Obviously, we can select them more or less randomly. But this is probably not ideal.

So I am thinking Scikit learn probably computes an interval $[\min(x_j), \max(x_j)]$ and sample $t_m$ within this set. But how many? The computational requirement is huge as we increase the number of $t_m$ to search for the best architecture.

Alternatively, since $t_m \in \mathbb{R}$, they could be using an optimization routine to search over $t_m$. But that optimization problem (the impurity/loss function) is probably not convex. So any solution would be suboptimal any ways.

2. How does this algorithm determine the total depth of this tree? That is, the largest number $m$. I noticed there is an undefined $\min_\text{samples}$ parameter. Is this a parameter that the designer set? If so how?

Thanks in advance.

Answer 1

$t_{m}$ is selected following your parameter choice. You can choose random $t$ or you can choose to follow a criterion and use the best split given that criterion. Possible choices for criterion in the algo are gini impurity coefficient and the entropy.
Between the 2, Entropy is going to be more computationally intensive as they calculate logs.

The total depth of the tree is not limited. You can fit a max yourself by using the max_depth parameter, otherwise it stops creating new nodes if the number of samples in the current node is lower than the specified minimum number of elements to split (default of 2 in the algo), or if all the nodes are pure (all elements inside the node have the same output variable).