The GATE Grind

GATE 2024 DA – Question 19

Machine Learning · Unsupervised learning: clustering · 1 mark · Multiple choice

Euclidean distance based $k$-means clustering algorithm was run on a dataset of 100 points with $k = 3$. If the points $\begin{bmatrix}1\\1\end{bmatrix}$ and $\begin{bmatrix}-1\\1\end{bmatrix}$ are both part of cluster 3, then which ONE of the following points is necessarily also part of cluster 3?

  1. $\begin{bmatrix}0\\0\end{bmatrix}$
  2. $\begin{bmatrix}0\\2\end{bmatrix}$
  3. $\begin{bmatrix}2\\0\end{bmatrix}$
  4. $\begin{bmatrix}0\\1\end{bmatrix}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\begin{bmatrix}0\\1\end{bmatrix}$

Explanation

In $k$-means every point goes to its nearest centroid, so each cluster is a convex region (a Voronoi cell). If two points are in cluster 3, every point on the line segment between them is also in cluster 3. The point $(0, 1)$ is the midpoint of $(1, 1)$ and $(-1, 1)$, so it must be in cluster 3. The other points are not on that segment.