Exercise 2: Conceptual Understanding of the Nearest Neighbors Learning Paradigm

Foundations of Data Mining:

Final Exam

Exercise 2: Conceptual Understanding of the Nearest Neighbors Learning Paradigm




1. Based on the above information, the output space is

According to the information provided, the output space is Y. It contains the output values Y1,

Y2, Y3, Y4, Y5, which correspond to the input points x1, x2, x3, x4, x5 respectively. The KNN

algorithm is used to classify a new input x based on the output values of the k-nearest points in

the input space X.

Ans is [A} y = {1,2,3,4,5}




2. It is straightforward to determine that fb3NN(x) is

[D] 3




3. The size 2 neighborhood V2(x) of x is given by

The size 2 neighborhood of x, V2(x), is given by the set of points whose distance from x is less

than or equal to the second smallest distance, d(2).

, In this case, since the distances are already sorted in increasing order, the second smallest

distance is 2, so the size 2 neighborhood of x would be V2(x) = {x3, x5}. This means that the

points x3 and x5 are the two nearest neighbors of x, and are included in the size 2 neighborhood.

These two points will be used for the classification of x, by using the similarity measure s(x,xi) =

1/(1+d(x,xi)) and the weighting of the points in the neighborhood simk(x, xi) = X

s(x, xi)


xj∈Vk(x)


s(x, xj )

, if xi is in the k-neighborhood, otherwise it is 0.

Ans is [D] {x3, x5}




4. It is also straightforward to compute w (2) 5 (x),

To compute w(2)5(x) we need to find the weight of the point x5 in the size 2

neighborhood V2(x) of x.

Since x5 is one of the two nearest neighbors to x, it is in the size 2 neighborhood, V2(x) =

{x3, x5}.

Thus, α(2)5(x) = 1.