Bird
Raised Fist0

Implement KNN Classifier - Brute Force and KD-Tree

CODINGintermediateInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement KNN Classifier - Brute Force and KD-Tree
Implement K-Nearest Neighbors using brute force and KD-Tree for efficient querying.
codingintermediateFreq: highClassical ML Coding
Prerequisites:K-Nearest Neighbors
📝
Problem Statement

Implement a K-Nearest Neighbors (KNN) classifier from scratch. Given a training dataset and a query point, predict the class of the query point based on the majority class of its K nearest neighbors.

I/O Specification
Input:  A training dataset X_train (numpy array of shape (n_samples, n_features)), labels y_train (numpy array of shape (n_samples,)), a query point x_query (numpy array of shape (n_features,)), and an integer K.
Output: The predicted class for the query point.
Example
{
  "input": {
    "X_train": [
      [
        1,
        2
      ],
      [
        2,
        3
      ],
      [
        3,
        4
      ]
    ],
    "y_train": [
      0,
      1,
      1
    ],
    "x_query": [
      2.5,
      3.5
    ],
    "K": 2
  },
  "expected_output": 1
}
🎯
Interview Angles
  • Testing understanding of spatial data structures like KD-Trees and their application in reducing search complexity.
  • Evaluating ability to implement distance-based algorithms without relying on libraries like sklearn.
  • Assessing knowledge of handling edge cases in nearest neighbor searches, such as ties and empty datasets.
  • Understanding of computational geometry concepts and their practical applications in machine learning.
🔵
Naive Approach

The brute-force approach involves computing the distance from the query point to every point in the training dataset, sorting these distances, and selecting the K nearest neighbors to determine the majority class.

Time complexity: O(n * d + n log n) - O(n * d) for distance computation and O(n log n) for sorting. Space complexity: O(n) for storing distances.
Why Insufficient
O(n * d + n log n) is inefficient for large datasets because it requires computing distances for all points and sorting them, which becomes impractical as n grows.
🐍
Naive Code
Python
import numpy as np

def knn_brute_force(X_train, y_train, x_query, K):
    distances = np.linalg.norm(X_train - x_query, axis=1)
    nearest_indices = np.argsort(distances)[:K]
    nearest_labels = y_train[nearest_indices]
    unique, counts = np.unique(nearest_labels, return_counts=True)
    return unique[np.argmax(counts)]

# Driver example
X_train = np.array([[1, 2], [2, 3], [3, 4]])
y_train = np.array([0, 1, 1])
x_query = np.array([2.5, 3.5])
K = 2
print(knn_brute_force(X_train, y_train, x_query, K))  # Output: 1
💡
Key Insight
Use a KD-Tree to partition the space and reduce the number of distance computations needed to find the nearest neighbors, making the search more efficient.
🐍
Optimized Code
Python
import numpy as np

class KDTree:
    def __init__(self, data):
        self.data = data
        self.n, self.d = data.shape
        self.tree = self.build_tree(np.arange(self.n), depth=0)

    def build_tree(self, indices, depth):
        if len(indices) == 0:
            return None
        axis = depth % self.d
        sorted_indices = indices[np.argsort(self.data[indices, axis])]
        median_idx = len(sorted_indices) // 2
        return {
            'point': sorted_indices[median_idx],
            'left': self.build_tree(sorted_indices[:median_idx], depth + 1),
            'right': self.build_tree(sorted_indices[median_idx + 1:], depth + 1)
        }

    def query(self, point, K):
        best = []
        self._query(self.tree, point, K, best, 0)
        return [idx for _, idx in sorted(best)]

    def _query(self, node, point, K, best, depth):
        if node is None:
            return
        axis = depth % self.d
        dist = np.linalg.norm(self.data[node['point']] - point)
        if len(best) < K:
            best.append((dist, node['point']))
            best.sort(reverse=True)
        elif dist < best[0][0]:
            best[0] = (dist, node['point'])
            best.sort(reverse=True)
        diff = point[axis] - self.data[node['point'], axis]
        close, away = (node['left'], node['right']) if diff < 0 else (node['right'], node['left'])
        self._query(close, point, K, best, depth + 1)
        if len(best) < K or abs(diff) < best[0][0]:
            self._query(away, point, K, best, depth + 1)


def knn_kd_tree(X_train, y_train, x_query, K):
    tree = KDTree(X_train)
    nearest_indices = tree.query(x_query, K)
    nearest_labels = y_train[nearest_indices]
    unique, counts = np.unique(nearest_labels, return_counts=True)
    return unique[np.argmax(counts)]

# Driver example
X_train = np.array([[1, 2], [2, 3], [3, 4]])
y_train = np.array([0, 1, 1])
x_query = np.array([2.5, 3.5])
K = 2
print(knn_kd_tree(X_train, y_train, x_query, K))  # Output: 1
🔍
Line-by-Line
class KDTree:
Defines a KD-Tree class to efficiently partition the data space.
self.tree = self.build_tree(np.arange(self.n), depth=0)
Initializes the KD-Tree by recursively building it from the data indices.
axis = depth % self.d
Determines the axis to split on, cycling through dimensions.
sorted_indices = indices[np.argsort(self.data[indices, axis])]
Sorts indices based on the current axis to find the median.
best.append((dist, node['point']))
Adds the current point to the list of best neighbors if the list is not full.
if len(best) < K or abs(diff) < best[0][0]:
Checks if the opposite branch needs to be searched based on the current best distances.
⚡
Complexity
Time complexity: O(log n) for balanced trees in average case, O(n) in worst case for unbalanced trees. Space complexity: O(n) for storing the tree structure.
Output
1
🔲
Edge Cases
Empty training set
The KD-Tree cannot be built, and querying will return no neighbors.
if len(indices) == 0: return None
Single element training set
The single element is always the nearest neighbor.
if len(best) < K: best.append((dist, node['point']))
All points equidistant
The algorithm will return the first K points encountered.
best.sort(reverse=True)
⚠️
Common Mistakes
Not handling the case where K is larger than the number of training samples.
Symptom: Index out of bounds error or incorrect predictions.
Incorrectly sorting distances in the KD-Tree query function.
Symptom: Returns incorrect nearest neighbors.
Failing to update the best list correctly when a closer neighbor is found.
Symptom: Suboptimal nearest neighbors returned.
Not considering the opposite branch in the KD-Tree when necessary.
Symptom: Misses potential closer neighbors.

Practice

(1/5)
1. What does the following Python code output when applied to an image array img? 
import numpy as np

def flip_image(img):
    return np.flip(img, axis=1)

img = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
flipped_img = flip_image(img)
print(flipped_img)
easy
A. [[3, 2, 1], [6, 5, 4], [9, 8, 7]]
B. [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
C. [[7, 8, 9], [4, 5, 6], [1, 2, 3]]
D. [[9, 8, 7], [6, 5, 4], [3, 2, 1]]

Solution

  1. Step 1: Understand the flip operation

    The np.flip function flips the array along the specified axis. Here, axis=1 means flipping horizontally.

  2. Step 2: Apply the flip to the array

    Flipping horizontally changes the order of elements in each row.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Horizontal flip reverses row elements. [OK]
Hint: Horizontal flip reverses row elements. [OK]
Common Mistakes:
2. What is the time complexity of computing the binary cross-entropy loss for a logistic regression model with n samples and m features?
easy
A. O(1)
B. O(n)
C. O(m)
D. O(nm)

Solution

  1. Step 1: Identify operations involved

    Binary cross-entropy involves computing predictions for each sample, which requires a dot product of weights and features.

  2. Step 2: Calculate complexity

    Each dot product is O(m), and there are n samples, leading to O(nm) complexity.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Dot product per sample, n samples -> O(nm) [OK]
Hint: Dot product per sample, n samples -> O(nm) [OK]
Common Mistakes:
3. In the context of implementing backpropagation using NumPy, which of the following is a correct approach to handle vanishing gradients?
medium
A. Use a smaller learning rate.
B. Switch to a sigmoid activation function.
C. Implement gradient clipping.
D. Increase the number of layers in the network.

Solution

  1. Step 1: Identify vanishing gradient issue

    Vanishing gradients occur when gradients become too small to update weights effectively.

  2. Step 2: Correct approach

    Gradient clipping prevents gradients from becoming too small or too large.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Clip gradients to prevent vanishing [OK]
Hint: Clip gradients to prevent vanishing [OK]
Common Mistakes:
4. How can you optimize the computation of a confusion matrix for a large dataset with millions of predictions?
hard
A. Use a more efficient data structure like a linked list.
B. Use a parallel processing library like Dask.
C. Reduce the number of classes to simplify computation.
D. Use a GPU to accelerate matrix operations.

Solution

  1. Step 1: Identify bottleneck

    Large datasets require efficient computation, often limited by CPU processing.

  2. Step 2: Choose optimization strategy

    Parallel processing with Dask can distribute computation across cores.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Parallel processing speeds up large data tasks. [OK]
Hint: Parallel processing speeds up large data tasks. [OK]
Common Mistakes:
5. Which optimization would most effectively reduce the computational cost of the scaled dot-product attention mechanism for very large input sequences?
hard
A. Use a smaller batch size.
B. Use half-precision floating point operations.
C. Reduce the dimensionality of queries and keys.
D. Implement attention with sparse matrices.

Solution

  1. Step 1: Identify the bottleneck

    Computational cost is high due to dense matrix operations.

  2. Step 2: Choose the best optimization

    Sparse matrices reduce computation by focusing on non-zero elements.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Sparse matrices for large inputs [OK]
Hint: Sparse matrices for large inputs [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