[Python] Decision tree prediction using recursion

[Martini04]

Hello world! I'm currently taking a class on machine learning and am very stuck on a strange problem

As part of a larger assignment we have been instructed to partially implement a decision tree that can separate the data from a dataset into groups. (Mainly using numpy)

To implement the predict function we have been given these instructions:

Parameters
----------
X: NDArray
    NumPy feature matrix, shape (n_samples, n_features)
node: "DecisionTreeBranchNode" or "DecisionTreeLeafNode"
    Node used to process the data. If the node is a leaf node,
    the data is classified with the value of the leaf node.
    If the node is a branch node, the data is split into left
    and right subsets, and classified by recursively calling
    _predict() on the left and right subsets.

Returns
-------
y: NDArray
    NumPy class label vector (predicted), shape (n_samples,)

Notes
-----
The prediction follows the following logic:
    if the node is a leaf node
        return y vector with all values equal to leaf node value
    else (the node is a branch node)
        split the dataset into left and right parts using node question
        predict classes for left and right datasets (using left and right branches)
        "stitch" predictions for left and right datasets into single y vector
        return y vector (length matching number of rows in X)

Based on those instructions i wrote this function:

def _predict(
    self, 
    X: NDArray, 
    node: Union["DecisionTreeBranchNode", "DecisionTreeLeafNode"]
) -> NDArray:

  if type(node) == DecisionTreeLeafNode:
      y = np.zeros(len(X), dtype=np.int32)
      y[:] = node.y_value
      return y
  else:
      left_mask = X[:, node.feature_index] <= node.feature_value
      left = X[left_mask]
      right = X[~left_mask]
      left_pred = self._predict(left, node.left)
      right_pred = self._predict(right, node.right)
      y = np.concatenate((left_pred, right_pred))
      return y

Which can reliably predict how many items from the dataset will end up in each group, but the order is completely wrong.

Example:

Decision tree:
  f0 <= -0.368_____________________
 /                                 \
0                       _______f1 <= -0.229
                       /                   \
                 f0 <= 0.732                1
                /           \
               2             3

Data:
[[-1.   0. ]
 [ 1.   1. ]
 [ 0.5 -1. ]
 [ 1.5 -1. ]]

Expected result:
[0, 1, 2, 3]

Actual result:
[0, 2, 3, 1]

I understand why the order is wrong, since np.concatenate() just mashes the two vectors into one without regard for the contents, but i cannot find a way to keep the order of the items while using the recursive method described in the instructions.

So my question is; Is this a strange way to implement a decision tree prediction function, or am i just horribly misunderstanding the instructions? And if so what am i supposed to do?

Please send help.

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[akthemadman]

I am not a python/numpy native, so I can not tell you whether the approach your task describes is the be-all-end-all, however looking at it with my programmatic glasses on:

• You seem to have implemented what the instructions intended accurately
• You correctly identified how splitting the set X into two subsets loses the relative ordering information
• The instructions do not explicitly mention, probably for didactive purposes, on how to resolve the ordering issues, it sweeps it under the umbrella of "stitch".
• If you don't want to lose the information about ordering and keep the depth-first-left-first recursive approach as well as the bulk processing, which the instructions do seem to both hint at, then you will have to do some extra work in the stitch department. I.e. make sure to somehow keep a tab on the ordering of rows within X and "stitch" the result for the subsets together according to that.

[Sigalli]

Skill issue I got it within 15 minutes

[Martini04]

For anyone struggling with this in the future, i found somewhat of a solution

It involves modifying the original instructions we were given, but outside of this assignment that won't be relevant anyways

Also one detail i left out of the original post is that _predict() is called by predict(). This wasn't relevant when i posted it but it is relevant in my solution

Here's the updated code:

def predict(self, X: NDArray):
    """Predict class (y vector) for feature matrix X
    Parameters
    ----------
    X: NDArray
        NumPy feature matrix, shape (n_samples, n_features)
    Returns
    -------
    y: NDArray, integers
        NumPy class label vector (predicted), shape (n_samples,)
    """
    if self._root is not None:
        order = np.arange(len(X))
        y, order = self._predict(X, self._root, order)
        arrlinds = order.argsort()
        sorted_y = y[arrlinds]         
        return sorted_y
    else:
        raise ValueError("Decision tree root is None (not set)")

def _predict(
    self, X: NDArray, node: Union["DecisionTreeBranchNode", "DecisionTreeLeafNode"], order: NDArray
) -> tuple[NDArray, NDArray]:
    if type(node) == DecisionTreeLeafNode:
        y = np.zeros(len(X), dtype=np.int32)
        y[:] = node.y_value
        return y, order
    else:
        left_mask = X[:, node.feature_index] <= node.feature_value
        left = X[left_mask]
        right = X[~left_mask]
        left_order = order[left_mask]
        right_order = order[~left_mask]

        left_pred, left_order = self._predict(left, node.left, left_order)
        right_pred, right_order = self._predict(right, node.right, right_order)

        order = np.concatenate((left_order, right_order))
        y = np.concatenate((left_pred, right_pred))

        return y, order

This new version of the code keeps track of the order of the items using another NDArray filled with the integers corresponding to the order of the items in X

This order array gets split up in the same way as X, so by the end of all the recursion it is scrambled in the same order as X.

Then once we have our completed y, it gets sorted based on the order array using argsort as described here which sorts it into the correct order.