# What are the ways to identify a good attribute test while constructing a decision tree?

I'm working through a decision tree by hand to learn it. From my research, I have found the following three ways of determining which variables to split on:

1. Minimum remaining values - The variable with the fewest legal values is chosen
2. Degree heuristic - The variable with the most constraints on remaining values
3. Least Constraining value - The variable that rules out the fewest remaining values in the remaining variables

Do I have these right? What are some other ways of determining the splits?

You might have mixed up CSP (Constrained Satisfaction Problem) search trees and decision trees:

CSP search trees

'Minimum remaining values', 'Degree Heuristic' and 'Least Constraining Value' are used to solve CSPs and not in decision trees (i.e. we are talking symbolic AI here and not a sub-symbolic AI method like decision trees).

However, as far as I know the 'least constraining value' approach is not used to select a variable but after having selected one to choose the order to inspect its values.

So it could go rather like this:

1. Choose a variable applying 'minimum remaining values'
2. If step 1 fails select a variable applying the 'degree heuristic'
3. For the selected variable select its values ordered according to 'least constraining value'


Besides the ones you mentioned you could go the really simple route: just pick 'the next' variable or pick randomly.

Also see section 6.3.1 in 'Artificial Intelligence: A Modern Approach' by Russel and Norvig.

Decision trees

In contrast decision trees are a machine learning method. Here you usually choose the best splits for the tree using a greedy algorithm providing the biggest ad-hoc gain (see below list for how to define 'gain'). Typical criteria for the greedy split are:

Classification

• Information gain (based on entropy)
• Gini score
• Classification error (usually not used when building the tree)

Regression

• Squared error

Also see sections 9.2.2 and 9.2.3 in 'The Elements of statistical learning' by Hastie, Tibshirani and Friedman.