GATE 2024 DA Q.63: solution and answer

GATE 2024 · DAQ.63 · 2 marks · NAT

Given the two-dimensional dataset consisting of 5 data points from two classes (circles and squares) and assume that the Euclidean distance is used to measure the distance between two points. The minimum odd value of $k$ in $k$ -nearest neighbor algorithm for which the diamond ( $◊$ ) shaped data point is assigned the label square is ______.

GATE 2024 DA question 63: A 2D grid plot with x-axis and y-axis both marked 1, 2, 3. — Figure from the GATE 2024 DA paper. It is part of the question.

Answer and solution

ANSWER

The minimum odd value of $k$ is $5$ .

Official answer: 5Source: Official answer key, GATE 2024 DA (IISc Bengaluru)

Read the points off the plot: circles at $(1, 1)$ and $(1, 2)$ ; squares at $(2, 3)$ , $(3, 3)$ and $(3, 2)$ ; the query (diamond) is at $(2, 1)$ .
Euclidean distances from $(2, 1)$ : to $(1, 1)$ it is $1^{2} + 0^{2} = 1$ ; to $(1, 2)$ it is $1 + 1 = 2$ ; to $(3, 2)$ it is $1 + 1 = 2$ ; to $(2, 3)$ it is $0 + 4 = 2$ ; to $(3, 3)$ it is $1 + 4 = 5$ .
Order by distance: circle $(1, 1)$ at $1$ ; circle $(1, 2)$ and square $(3, 2)$ tied at $2 \approx 1.41$ ; square $(2, 3)$ at $2$ ; square $(3, 3)$ at $\approx 2.24$ .
$k = 1$ : the single nearest point is the circle at $(1, 1)$ , so the label is circle.
$k = 3$ : the three nearest points are $(1, 1)$ , $(1, 2)$ and $(3, 2)$ . The tie at $2$ is fully included, because both tied points fall inside the three, so there is no cut-off ambiguity. That gives 2 circles and 1 square, so the majority is circle.
$k = 5$ : all five points vote, giving 2 circles and 3 squares, so the majority is square.
The odd values $k = 1$ and $k = 3$ both give circle, and $k = 5$ gives square, so the minimum odd $k$ that assigns the label square is $5$ .

KEY IDEA

In $k$ -NN, rank all training points by Euclidean distance from the query and take a majority vote among the $k$ nearest. Compute the distances once, then test each odd $k$ in turn.

WATCH OUT FOR

Counting only the two squares nearest to the query, or assuming that the square at $(3, 2)$ is farther than the circle at $(1, 2)$ . These two are tied at $2$ , so at $k = 3$ both are included, and the circles still win 2 to 1. With 5 points in total, the only way for squares to win a majority is to use all of them.

From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 4 Logistic, k-NN, naive Bayes questions, with notes

GATE 2024 DA Q.63: solution and answer

Answer and solution

More Logistic, k-NN, naive Bayes questions