Bird
Raised Fist0

Implement Decision Tree - Information Gain, Recursive Split

CODINGintermediateInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Decision Tree - Information Gain, Recursive Split
Build a decision tree using information gain for splitting.
codingintermediateFreq: highClassical ML Coding
Prerequisites:Decision Trees - Information GainGini Impurity
📝
Problem Statement

Implement a decision tree classifier using information gain for recursive splitting.

I/O Specification
Input:  A 2D NumPy array X of shape (n_samples, n_features) and a 1D NumPy array y of shape (n_samples,).
Output: A decision tree model that can predict the class of new samples.
Example
{
  "input": "X = np.array([[1, 2], [3, 4], [5, 6]]), y = np.array([0, 1, 0])",
  "expected_output": "A tree structure that can classify samples based on the input features."
}
🎯
Interview Angles
  • Understanding of recursive algorithms and base cases.
  • Ability to compute and use information gain for decision making.
  • Handling of edge cases like single element or all same class.
🔵
Naive Approach

Build the decision tree by evaluating all possible splits at each node and choosing the one with the highest information gain. This involves calculating the entropy for each possible split and selecting the best one.

Time complexity is O(n^2 * m * log n) where n is the number of samples, m is the number of features. Space complexity is O(n) for storing the tree.
Why Insufficient
O(n^2 * m * log n) because it evaluates all possible splits at each node, which is computationally expensive for large datasets.
🐍
Naive Code
Python
import numpy as np

class DecisionTreeNaive:
    def __init__(self):
        self.tree = None

    def fit(self, X, y):
        self.tree = self._build_tree(X, y)

    def _build_tree(self, X, y):
        if len(set(y)) == 1:
            return {'label': y[0]}
        best_gain = 0
        best_split = None
        best_sets = None
        current_entropy = self._entropy(y)
        n_features = X.shape[1]
        for feature in range(n_features):
            values = set(X[:, feature])
            for value in values:
                left_indices = X[:, feature] <= value
                right_indices = X[:, feature] > value
                if not any(left_indices) or not any(right_indices):
                    continue
                left_y, right_y = y[left_indices], y[right_indices]
                gain = self._information_gain(current_entropy, left_y, right_y)
                if gain > best_gain:
                    best_gain = gain
                    best_split = (feature, value)
                    best_sets = (left_indices, right_indices)
        if best_gain == 0:
            return {'label': np.bincount(y).argmax()}
        left_tree = self._build_tree(X[best_sets[0]], y[best_sets[0]])
        right_tree = self._build_tree(X[best_sets[1]], y[best_sets[1]])
        return {'feature': best_split[0], 'value': best_split[1], 'left': left_tree, 'right': right_tree}

    def _entropy(self, y):
        counts = np.bincount(y)
        probabilities = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probabilities if p > 0])

    def _information_gain(self, current_entropy, left_y, right_y):
        p = len(left_y) / (len(left_y) + len(right_y))
        return current_entropy - p * self._entropy(left_y) - (1 - p) * self._entropy(right_y)

    def predict(self, X):
        return np.array([self._predict_one(x, self.tree) for x in X])

    def _predict_one(self, x, tree):
        if 'label' in tree:
            return tree['label']
        feature, value = tree['feature'], tree['value']
        branch = tree['left'] if x[feature] <= value else tree['right']
        return self._predict_one(x, branch)

# Driver example
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([0, 1, 0])
dt = DecisionTreeNaive()
dt.fit(X, y)
print(dt.predict(X))
💡
Key Insight
Use a more efficient data structure to store the tree and optimize the split evaluation by caching computations.
🐍
Optimized Code
Python
import numpy as np

class DecisionTreeOptimized:
    def __init__(self):
        self.tree = None

    def fit(self, X, y):
        self.tree = self._build_tree(X, y)

    def _build_tree(self, X, y):
        if len(set(y)) == 1:
            return {'label': y[0]}
        best_gain = 0
        best_split = None
        best_sets = None
        current_entropy = self._entropy(y)
        n_features = X.shape[1]
        for feature in range(n_features):
            values = np.unique(X[:, feature])
            for value in values:
                left_indices = X[:, feature] <= value
                right_indices = X[:, feature] > value
                if not any(left_indices) or not any(right_indices):
                    continue
                left_y, right_y = y[left_indices], y[right_indices]
                gain = self._information_gain(current_entropy, left_y, right_y)
                if gain > best_gain:
                    best_gain = gain
                    best_split = (feature, value)
                    best_sets = (left_indices, right_indices)
        if best_gain == 0:
            return {'label': np.bincount(y).argmax()}
        left_tree = self._build_tree(X[best_sets[0]], y[best_sets[0]])
        right_tree = self._build_tree(X[best_sets[1]], y[best_sets[1]])
        return {'feature': best_split[0], 'value': best_split[1], 'left': left_tree, 'right': right_tree}

    def _entropy(self, y):
        counts = np.bincount(y)
        probabilities = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probabilities if p > 0])

    def _information_gain(self, current_entropy, left_y, right_y):
        p = len(left_y) / (len(left_y) + len(right_y))
        return current_entropy - p * self._entropy(left_y) - (1 - p) * self._entropy(right_y)

    def predict(self, X):
        return np.array([self._predict_one(x, self.tree) for x in X])

    def _predict_one(self, x, tree):
        if 'label' in tree:
            return tree['label']
        feature, value = tree['feature'], tree['value']
        branch = tree['left'] if x[feature] <= value else tree['right']
        return self._predict_one(x, branch)

# Driver example
X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([0, 1, 0])
dt = DecisionTreeOptimized()
dt.fit(X, y)
print(dt.predict(X))
🔍
Line-by-Line
if len(set(y)) == 1:
Base case: if all labels are the same, return a leaf node with that label.
best_gain = 0
Initialize the best information gain to zero for comparison.
values = np.unique(X[:, feature])
Get unique values for the current feature to evaluate potential splits.
if not any(left_indices) or not any(right_indices):
Skip splits that don't divide the data.
gain = self._information_gain(current_entropy, left_y, right_y)
Calculate information gain for the current split.
if best_gain == 0:
If no gain is found, return a leaf node with the most common label.
return {'feature': best_split[0], 'value': best_split[1], 'left': left_tree, 'right': right_tree}
Store the best split and recursively build left and right subtrees.
⚡
Complexity
Time complexity is O(n * m * log n) due to sorting and evaluating splits. Space complexity is O(n) for storing the tree.
Output
[0 1 0]
🔲
Edge Cases
Single Element
The tree should return the label of the single element.
if len(set(y)) == 1:
All Same Class
The tree should return a single node with that class.
if len(set(y)) == 1:
⚠️
Common Mistakes
Not handling the base case correctly in recursion.
Symptom: Infinite recursion or incorrect tree structure.
Incorrectly calculating information gain due to entropy errors.
Symptom: Suboptimal splits leading to poor model accuracy.
Failing to handle datasets where all features have the same value.
Symptom: No split found, returning an incorrect leaf node.

Practice

(1/5)
1. 
import numpy as np

data = np.array([1, 2, 3, 4, 5])
mean = np.mean(data)
std = np.std(data)

standardized_data = (data - mean) / std
print(standardized_data)
What does the code output?
easy
A. An array with values [0, 1, 2, 3, 4]
B. An array with values [0, 0.5, 1, 1.5, 2]
C. An array with values [-1.41, -0.71, 0, 0.71, 1.41]
D. An array with values [-2, -1, 0, 1, 2]

Solution

  1. Step 1: Understand Standardization

    Standardization transforms data to have a mean of 0 and a standard deviation of 1.

  2. Step 2: Calculate the Output

    The standardized values are calculated as (data - mean) / std, resulting in [-1.41, -0.71, 0, 0.71, 1.41].

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Standardization centers data around 0. [OK]
Hint: Standardization centers data around 0. [OK]
Common Mistakes:
2. In a scenario where training time is critical, which approach is better for implementing early stopping?
medium
A. Use a small patience value to stop early.
B. Use a large patience value to ensure stability.
C. Monitor training loss instead of validation loss.
D. Disable early stopping to avoid interruptions.

Solution

  1. Step 1: Consider training time constraints

    In time-critical scenarios, stopping early can save resources.

  2. Step 2: Choose the appropriate patience value

    A small patience value allows for quicker termination if no improvement is seen, aligning with the need to save time.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Small patience saves time in critical scenarios. [OK]
Hint: Small patience saves time in critical scenarios. [OK]
Common Mistakes:
3. In your implementation of K-Means, the algorithm is not converging. What is the most likely cause?
medium
A. The dataset is too small.
B. The number of clusters is too large.
C. The initial centroids are poorly chosen.
D. The distance metric is incorrect.

Solution

  1. Step 1: Identify convergence issues

    Poorly chosen initial centroids can lead to non-convergence as they may not represent the data well.

  2. Step 2: Eliminate wrong options

    The number of clusters is too large. is incorrect because a large number of clusters doesn't prevent convergence. The dataset is too small. is incorrect as a small dataset doesn't inherently cause non-convergence. The distance metric is incorrect. is incorrect if the metric is consistent.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Check initial centroids for convergence issues. [OK]
Hint: Check initial centroids for convergence issues. [OK]
Common Mistakes:
4. How can you optimize the following logistic regression implementation for faster computation?
import numpy as np

# Initialize weights
weights = np.zeros((m, 1))

# Training loop
for epoch in range(epochs):
    # Compute predictions
    predictions = 1 / (1 + np.exp(-np.dot(X, weights)))
    
    # Compute gradient
    gradient = np.dot(X.T, (predictions - y)) / n
    
    # Update weights
    weights -= learning_rate * gradient
hard
A. Use a sparse matrix representation for X.
B. Use a smaller learning rate to ensure stability.
C. Vectorize the gradient computation to avoid loops.
D. Precompute the sigmoid function for all possible inputs.

Solution

  1. Step 1: Identify bottlenecks

    Matrix operations can be slow if X is dense and large.

  2. Step 2: Optimize matrix operations

    Using a sparse matrix representation for X reduces memory usage and speeds up computations.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sparse matrices optimize large, sparse datasets [OK]
Hint: Sparse matrices optimize large, sparse datasets [OK]
Common Mistakes:
5. How can the calculation of precision, recall, and F1-score be optimized for a large confusion matrix?
hard
A. Use a more efficient data structure than a matrix.
B. Pre-compute and store results for common confusion matrices.
C. Use parallel processing to compute metrics for each class.
D. Approximate metrics using a subset of the data.

Solution

  1. Step 1: Identify bottlenecks

    Calculating metrics for each class can be parallelized.

  2. Step 2: Choose the best optimization strategy

    Parallel processing allows simultaneous computation, reducing time complexity.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Parallelize class-wise computations. [OK]
Hint: Parallelize class-wise computations. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard