GATE DS&AI 2024 | Question: 9

Question

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

• A. $\left[\begin{array}{l}0 \\ 0\end{array}\right]$
• B. $\left[\begin{array}{l}0 \\ 2\end{array}\right]$
• C. $\left[\begin{array}{l}2 \\ 0\end{array}\right]$
• D. $\left[\begin{array}{l}0 \\ 1\end{array}\right]$

Answer 1

If points [1, 1] and [-1, 1] are both part of cluster 3 in the k-means clustering algorithm, it implies that they are closer to each other than to the centroids of the other clusters.

Since the clustering is based on Euclidean distance, any point that is closer to points [1, 1] and [-1, 1] than to the centroids of the other clusters will also be part of cluster 3.

Let's examine the given options:

- [0, 0] has a distance of √2 from both [1, 1] and [-1, 1].

- [0, 2] has a distance of √5 from both [1, 1] and [-1, 1].

- [2, 0] has a distance of 2√2 from both [1, 1] and [-1, 1].

- [0, 1] has a distance of 1 from both [1, 1] and [-1, 1].

Among the options, only [0, 1] has the same distance from both [1, 1] and [-1, 1]. Therefore, [0, 1] is necessarily also part of cluster 3.

So, the correct answer is:

D. [0, 1]

Answer 2

Distance between [1, 1] and [-1, 1] = 2.

Consider this distance as diameter of circle. Then, radius = 1.

Any point which has distance ≤ 1 from both the points [1, 1] and [-1, 1] will be in the same cluster.

Since only [0, 1] has distance ≤ 1 from both the points, answer is D. [0, 1].