Draw the decision boundaries of S1 and S2 when k=1.

Consider a binary classification problem with two real valued features X1 and 32. Figures 1 and 2 illustrate two different training sets S1 and S2. White circles indicate the positively-labeled examples, whereas black squares indicate the negatively-labeled examples. To classify a new instance point, we will use (unweighted) k-Nearest Neighbors with Euclidean distance and different k values. Thus the label for a new point will be predicted by the majority class (i.e., positive or negative) among the k closest examples around the query point. 6 5.5 4 5 1 3.5 4.5 1 4 3 3.5 2.5 X2 3 o X2 2 2.5 1 2 1.5 1.5 1 1 O 0.5 0.5 11 0 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 X1 X1 Figure 1: The training set S Figure 2: The training set S2