Bird
Raised Fist0

Implement K-Means Clustering - Lloyd's Algorithm from Scratch

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
K-Means Clustering vs Hierarchical Clustering

For a dataset with 100K samples and a need for quick clustering, would you use K-Means or Hierarchical Clustering? Justify your choice.

📊
Comparison
DimensionK-Means ClusteringHierarchical Clustering
ScalabilityHighLow
InterpretabilityLowHigh
Flexibility in cluster shapesLowHigh
SpeedHighLow
Memory usageLowHigh
✅
Verdict
Default to K-Means for datasets larger than 10,000 samples where speed is crucial and the number of clusters is known. Switch to hierarchical clustering when interpretability and cluster shape flexibility are more important, especially for smaller datasets.
💡
Key Insight
K-Means excels in speed and scalability, while hierarchical clustering provides interpretability and flexibility in cluster shapes.
⚠️
Interview Trap
❌ Wrong: Always use K-Means for clustering because it's faster.
Ignoring the need for interpretability and flexibility in cluster shapes, which hierarchical clustering provides.
✅ Consider the dataset size and the need for understanding cluster relationships. Use K-Means for speed with large datasets and hierarchical clustering for interpretability and flexibility.
K-Means Clustering
"Fast convergence for large datasets with a predefined number of clusters."
Weaknesses
  • Requires the number of clusters (k) to be specified in advance.
  • Sensitive to initial centroid placement, which can lead to suboptimal solutions.
  • Assumes spherical clusters, which may not fit all data distributions.
Ideal When
  • n > 10,000
  • k is known and relatively small (k < 100)
  • Data is well-separated and roughly spherical
  • Low-dimensional data (d < 50)
Google uses K-Means for image compression in its Photos app due to its speed and efficiency with large datasets.
Hierarchical Clustering
"Does not require the number of clusters to be specified in advance and provides a dendrogram for visualizing cluster relationships."
Weaknesses
  • Computationally expensive for large datasets (O(n^3) complexity).
  • Memory-intensive due to storing distance matrices.
  • Less effective for very large datasets due to scalability issues.
Ideal When
  • n < 10,000
  • Need for a dendrogram to understand cluster hierarchy
  • Clusters are not well-separated or are non-spherical
  • Exploratory data analysis where the number of clusters is unknown
Spotify uses hierarchical clustering for playlist generation to understand the relationships between songs and genres.
🐍
K-Means Clustering - Example
▼ Show
Python
import numpy as np

# Randomly initialize centroids
centroids = data[np.random.choice(data.shape[0], k, replace=False)]

# Iterate until convergence
for _ in range(max_iters):
    # Assign clusters
    distances = np.linalg.norm(data[:, np.newaxis] - centroids, axis=2)
    labels = np.argmin(distances, axis=1)
    # Update centroids
    new_centroids = np.array([data[labels == i].mean(axis=0) for i in range(k)])
    if np.all(centroids == new_centroids):
        break
    centroids = new_centroids
🐍
Hierarchical Clustering - Example
▼ Show
Python
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Generate the linkage matrix
Z = linkage(data, 'ward')

# Plot the dendrogram
dendrogram(Z)
plt.show()
✅
Use K-Means Clustering When
  • •n > 10,000
  • •k is known and small (k < 100)
  • •Data is low-dimensional (d < 50)
  • •Quick clustering is required
✅
Use Hierarchical Clustering When
  • •n < 10,000
  • •Exploratory analysis with unknown k
  • •Need for visualizing cluster hierarchy
  • •Clusters are non-spherical
↳
Nuances
  • For very large datasets, K-Means can be initialized with a subset of data to improve speed without significant loss in accuracy.
  • Hierarchical clustering can be used to determine the number of clusters for K-Means by analyzing the dendrogram.
  • K-Means may converge to a local minimum, so multiple runs with different initializations can improve results.

Practice

(1/5)
1. What is the time complexity of computing a confusion matrix for a binary classification problem with n predictions?
easy
A. O(n^2)
B. O(n log n)
C. O(n)
D. O(1)

Solution

  1. Step 1: Analyze the operation

    Computing a confusion matrix involves iterating over predictions once.

  2. Step 2: Determine complexity

    Each prediction is checked once, leading to O(n) complexity.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Confusion matrix computation is linear in predictions. [OK]
Hint: Confusion matrix computation is linear in predictions. [OK]
Common Mistakes:
2. What is the time complexity of updating the embeddings for a single word pair in the Skip-Gram model with negative sampling?
easy
A. O(k)
B. O(vocab_size)
C. O(n)
D. O(1)

Solution

  1. Step 1: Identify the operations involved

    Updating embeddings involves computing gradients and updating weights for the target word and k negative samples.

  2. Step 2: Determine the complexity

    Each update involves a constant number of operations per sample, leading to O(k) complexity where k is the number of negative samples.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Complexity is O(k) due to k negative samples [OK]
Hint: Complexity is O(k) due to k negative samples [OK]
Common Mistakes:
3. 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:
4. You need to apply non-max suppression on a batch of images. Which approach is most efficient?
medium
A. Apply non-max suppression independently on each image.
B. Concatenate all boxes from all images and apply non-max suppression once.
C. Apply non-max suppression on the image with the highest number of boxes only.
D. Apply non-max suppression on images with scores above a certain threshold.

Solution

  1. Step 1: Consider independence of images

    Each image's boxes are independent, so process them separately.

  2. Step 2: Evaluate efficiency

    Concatenating boxes would mix unrelated data, and focusing on one image or thresholding scores misses other valid boxes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Process each image independently [OK]
Hint: Process each image independently [OK]
Common Mistakes:
5. How would you modify the Mini-Batch SGD with Momentum to handle sparse data more efficiently?
medium
A. Increase the learning rate to speed up convergence.
B. Use a sparse matrix library for gradient storage.
C. Apply L2 regularization to reduce overfitting.
D. Implement lazy updates to avoid unnecessary computations.

Solution

  1. Step 1: Identify the challenge with sparse data

    Sparse data often leads to many zero gradients, making full updates inefficient.

  2. Step 2: Choose the appropriate modification

    Lazy updates only update non-zero elements, reducing unnecessary computations and improving efficiency.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Use lazy updates for sparse data efficiency [OK]
Hint: Use lazy updates for sparse data efficiency [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