Bird
Raised Fist0

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

CODINGintermediateInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
▶
Execution Trace
Step 1/4
Initial Centroids

Centroids initialized at C1(2,3) and C2(8,7)

🎯 Choosing initial centroids can affect convergence speed and final clusters.
centroids = np.array([[2, 3], [8, 7]])
Data Point Assignment

P1(1,2) assigned to C1, P4(8,8) assigned to C2 based on distance

🎯 Distance metric (e.g., Euclidean) is crucial for assignment.
for point in data_points:
  distances = np.linalg.norm(point - centroids, axis=1)
  cluster = np.argmin(distances)
Centroid Update

New centroid C1 calculated as mean of P1, P2, P3

🎯 Centroid update step involves averaging assigned points.
for i in range(k):
  points = [data_points[j] for j in range(len(data_points)) if assignments[j] == i]
  centroids[i] = np.mean(points, axis=0)
Convergence Check

Centroids unchanged after iteration 2, algorithm converges

🎯 Convergence is reached when centroids no longer change.
if np.all(centroids == old_centroids):
  break
📊
Diagram
Diagram
┌──────────────────────────────────────────────────────────────┐
│ Initial Centroids: C1(2,3), C2(8,7)                         │
│                                                              │
│ Iteration 1:                                                 │
│   Data Points: P1(1,2), P2(2,3), P3(3,4), P4(8,8), P5(9,7)  │
│   Assignments: P1→C1, P2→C1, P3→C1, P4→C2, P5→C2            │
│   New Centroids: C1(2,3), C2(8.5,7.5)                       │
│                                                              │
│ Iteration 2:                                                 │
│   Assignments: P1→C1, P2→C1, P3→C1, P4→C2, P5→C2            │
│   New Centroids: C1(2,3), C2(8.5,7.5)                       │
│                                                              │
│ Convergence: Centroids unchanged                            │
└──────────────────────────────────────────────────────────────┘
Labels
  • Initial Centroids: Starting points for clusters
  • Data Points: Points to be clustered
  • Assignments: Data points assigned to nearest centroid
  • New Centroids: Updated positions of centroids
  • Convergence: No change in centroids
🔑
Key Moments
▲
Q: Why is the choice of initial centroids important?
A: Initial centroids can affect the speed of convergence and the quality of the final clusters.
Q: What role does the distance metric play in K-Means?
A: The distance metric determines how data points are assigned to clusters, affecting the clustering outcome.
Q: How do we know when the K-Means algorithm has converged?
A: The algorithm converges when the centroids no longer change between iterations.
Trace Summary

This visual trace document explains the K-Means clustering algorithm using Lloyd's method. It illustrates the iterative process of assigning data points to the nearest centroid, updating centroids based on the mean of assigned points, and checking for convergence when centroids stabilize. Key insights include the importance of initial centroid selection, the role of the distance metric in point assignment, and the convergence criteria. Understanding these steps is crucial for implementing K-Means effectively and optimizing its performance.

Primary Focus

✓ K-Means Clustering algorithm implementation

Practice

(1/5)
1. 
import numpy as np

def entropy(y):
    unique, counts = np.unique(y, return_counts=True)
    probabilities = counts / counts.sum()
    return -np.sum(probabilities * np.log2(probabilities))

labels = np.array([1, 1, 0, 0, 1])
print(entropy(labels))
What does this code output?
easy
A. 1.0
B. 0.9709505944546686
C. 0.5
D. 0.9182958340544896

Solution

  1. Step 1: Calculate probabilities

    For labels [1, 1, 0, 0, 1], probabilities are [0.4, 0.6].

  2. Step 2: Calculate entropy

    Entropy = -[0.4*log2(0.4) + 0.6*log2(0.6)] = 0.9709505944546686.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Entropy formula: -Σ(p*log2(p)) [OK]
Hint: Entropy formula: -Σ(p*log2(p)) [OK]
Common Mistakes:
2. What is the time complexity of calculating the entropy for a dataset with n samples?
easy
A. O(log n)
B. O(n log n)
C. O(n^2)
D. O(n)

Solution

  1. Step 1: Analyze entropy calculation

    Entropy calculation involves counting occurrences and computing probabilities, both O(n).

  2. Step 2: Eliminate wrong options

    O(n^2) and O(n log n) are incorrect as they overestimate the operations needed.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Entropy calculation is linear in n [OK]
Hint: Entropy calculation is linear in n [OK]
Common Mistakes:
3. 
import numpy as np

def ndcg_at_k(r, k):
    dcg_max = dcg_at_k(sorted(r, reverse=True), k)
    if not dcg_max:
        return 0.
    return dcg_at_k(r, k) / dcg_max

relevance_scores = [3, 2, 3, 0, 1, 2]
k = 3
print(ndcg_at_k(relevance_scores, k))
The output is unexpectedly low. What is the most likely cause?
medium
A. The k value is too low.
B. The DCG is calculated incorrectly.
C. The relevance scores are not normalized.
D. The ideal DCG is not calculated correctly.

Solution

  1. Step 1: Check Ideal DCG Calculation

    The ideal DCG should be calculated using the sorted relevance scores.

  2. Step 2: Identify the Error

    If the ideal DCG is not calculated correctly, the NDCG will be incorrect.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Check ideal DCG calculation. [OK]
Hint: Check ideal DCG calculation. [OK]
Common Mistakes:
4. In the following learned positional encoding implementation, the model is not learning as expected. What is the most likely cause?
import torch
import torch.nn as nn

class LearnedPositionalEncoding(nn.Module):
    def __init__(self, max_len, d_model):
        super().__init__()
        self.positional_encoding = nn.Parameter(torch.zeros(max_len, d_model))

    def forward(self, x):
        return x + self.positional_encoding[:x.size(1), :]

model = LearnedPositionalEncoding(100, 512)
optimizer = torch.optim.Adam(model.parameters(), lr=0.001)
medium
A. The positional encoding is not initialized properly.
B. The learning rate is too low.
C. The optimizer is not suitable for this task.
D. The positional encoding is not being updated.

Solution

  1. Step 1: Identify the initialization issue

    The positional encoding is initialized to zeros, which may not provide a useful starting point for learning.

  2. Step 2: Eliminate wrong options

    The learning rate is too low. is incorrect because the learning rate is standard. The optimizer is not suitable for this task. is incorrect because Adam is generally suitable. The positional encoding is not being updated. is incorrect because the parameter is part of the model and should be updated.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check initialization of learned parameters. [OK]
Hint: Check initialization of learned parameters. [OK]
Common Mistakes:
5. How can you optimize the numerical gradient computation for a large neural network?
hard
A. Use a smaller step size to reduce computation time.
B. Parallelize the gradient computation across multiple cores.
C. Increase the batch size during training.
D. Use a higher learning rate to speed up convergence.

Solution

  1. Step 1: Identify optimization strategies for numerical gradient computation

    Parallelizing the computation can significantly reduce time for large networks.

  2. Step 2: Eliminate ineffective strategies

    Options A, C, and D do not directly optimize the gradient computation process.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Parallelize for large networks. [OK]
Hint: Parallelize for large networks. [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