Decision Tree Prediction

mediumFREEDecision TreesMachine Learning 1

Traverse a decision tree to make predictions.

A decision tree is represented as nested dictionaries. Each internal node has:

"feature": index of the feature to check
"threshold": split value
"left": subtree for feature_value <= threshold
"right": subtree for feature_value > threshold

Each leaf node has:

"class": the predicted class label

Given a tree and a list of data points (each a list of feature values), return the predicted class for each point.

Example

Input

tree = {"feature": 0, "threshold": 5, "left": {"class": 0}, "right": {"class": 1}}
X = [[3], [7], [5]]

Output

[0, 1, 0]

Reasoning

Inputs: tree is a single split: its root says "look at feature $0$ and compare it with the threshold $5$ ", with leaf class 0 on the left and leaf class 1 on the right. X holds three points, each with just one feature value: [3], [7], [5].
Point [3]: feature $0$ is $3$ , and $3 \le 5$ , so it falls on the left side and gets class 0.
Point [7]: $7 > 5$ , so it falls on the right side and gets class 1.
Point [5]: $5 \le 5$ holds, so a value exactly equal to the threshold also goes left and gets class 0.
Output: one label per row of X, in the same order: [0, 1, 0].
Notice that the boundary case decides the third answer: with a strict $<$ test, [5] would have been labelled 1. In a deeper tree a point keeps meeting such comparisons until it reaches a node that only carries a class.

Constraints

tree: nested dict with feature/threshold/left/right or class keys
X: 2D list of feature values
Return list of predicted class labels

Learn this in

Decision TreesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

A decision tree is a type of supervised learning algorithm used for both classification and regression tasks. It works by recursively partitioning the data into smaller subsets based on the values of the input features. The tree consists of internal nodes, which represent the features and thresholds used to split the data, and leaf nodes, which represent the predicted class labels. The process of constructing a decision tree involves selecting the best feature and threshold to split the data at each internal node, typically using a measure such as information gain or Gini impurity.

The key concept in traversing a decision tree is to start at the root node and recursively move down the tree, selecting the left or right child node based on whether the feature value is less than or equal to the threshold or greater than the threshold, respectively. This process continues until a leaf node is reached, at which point the predicted class label is returned. Understanding how to represent a decision tree as a nested dictionary and how to traverse the tree is essential to solving this problem.

In the context of this problem, the decision tree is already constructed, and the task is to use the tree to make predictions on a list of data points. This involves writing a function that takes the tree and the data points as input and returns a list of predicted class labels. The function will need to recursively traverse the tree for each data point, using the feature values and thresholds to determine the predicted class label.

Algorithm/Approach

The general approach to solving this problem is to write a recursive function that traverses the decision tree for each data point. The function will take the tree and a data point as input and return the predicted class label. The function will use the feature index and threshold at each internal node to determine whether to move down the left or right subtree, and will return the predicted class label when a leaf node is reached.

Step-by-Step Strategy

To implement the solution, follow these steps:

Define a recursive function that takes the tree and a data point as input
Check if the current node is a leaf node (i.e., it has a "class" key)
If it is a leaf node, return the predicted class label
If it is an internal node, extract the feature index and threshold
Use the feature index and threshold to determine whether to move down the left or right subtree
Recursively call the function on the left or right subtree
Repeat the process until a leaf node is reached

Common Pitfalls

Some common pitfalls to watch out for when implementing this solution include:

Forgetting to handle the base case of the recursion (i.e., when a leaf node is reached)
Incorrectly determining whether to move down the left or right subtree
Failing to handle the case where the feature index or threshold is missing from the tree

Time & Space Complexity

The time complexity of this solution will be $O(n \cdot d)$ , where $n$ is the number of data points and $d$ is the maximum depth of the tree. This is because we need to traverse the tree for each data point, and the maximum number of nodes we need to visit is proportional to the depth of the tree. The space complexity will be $O(d)$ , which is the maximum amount of space we need to store the recursive call stack.

solution.py

Python 3.13

Test results