# Is there a relation between the number of classes and the total number of splits there need to be computed in binary classification trees?

I'm trying to understand the mechanism behind decision trees training better. Suppose it is binary splitting only, and Gini-index is used as the impurity function. The explanatory variable X is first ordered. In the worst case the maximum number of splits to consider would be $$\mathrm{n}-1$$. Sample data:

X y
4 A
7 A
8 A
9 A
11 B
15 B
16 C
17 A
22 B
31 C

Since optimal splits can only occur on segment borders, this would reduce the maximum number of splits to consider to only 5 for the data above, regardless of how many classes in y. Segments: {4,7,8,9}, {11,15}, {16}, {17}, {22}, {31}, thus only 5 splits $$X < 10, X<15.5, X<16.5, X<19.5$$ and $$X < 26.5$$ are considered.

Is my understanding correct? Or does the number of classes also in some way have a relationship with the number of total splits to consider?

Cheers.

• Keep in mind that the sample size needed to get a reliable tree is astronomical. Sep 26 at 12:30

Number of classes puts a lower bound on the number of splits (i.e. $$c-1$$ if there are $$c$$ classes), but there is no strong relation between the number of splits and the number of classes. It mostly depends on the feature distribution.

For example, in your case, there is only one feature and if you had only two classes with the following allocation, you'd need more splits:

X y
4 A
7 B
8 A
9 B
11 A
15 B
16 A
17 B
22 A
31 B