Greedy tree construction

As explained in Grokking Machine Learning

A decision-tree construction strategy that selects the locally best feature or split at each node without guaranteeing a globally best tree.

Imagine predicting graduate admission by asking one question at a time. A greedy decision tree chooses the strongest available feature or split at each node, then continues from there. The locally strongest choice may not produce the best complete tree. section 9.5

The strategy works like this:

• Choose the top feature at the current node. section 9.5
• Split the data and repeat the choice within each resulting branch. section 9.5
• Inspect the resulting tree without discarding features absent from it; individually weak features may form a strong combination. section 9.5

Student admissions

In an admissions tree, CGPA becomes the root feature, followed by GRE and TOEFL scores. Statement-of-purpose strength appears later and changes predictions little. A different combination of features might nevertheless be valuable. section 9.5

Figure 9.24 A decision tree of depth 3 trained in the student admissions dataset

Inspect a depth-three admissions tree to see how locally selected features organize the branches. section 9.5

How Grokking Machine Learning covers it

How deep it goes

Explains repeated top-feature selection and stops short of guaranteeing a globally best tree.

Examples

Uses student admissions data with CGPA, GRE, TOEFL, and statement-of-purpose features.

What you can do after

Apply it via Scikit-Learn to fit and inspect an admissions decision tree.

How it connects

Connects decision trees with feature selection and L1 regularization.

liveBookmanning.com

Read Grokking Machine Learning on liveBook Get the book at manning.com

Related concepts

• decision treeused by · A decision tree is a branching structure that represents sequential tests or choices, with paths leading to outcomes, predictions, or actions.
• greedy algorithmkind of · A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.

This explainer was generated by Manning's knowledge graph from the text of Grokking Machine Learning. The section links point to the parts of the book it draws on.