# K-Nearest Neighbours algorithm explanation needed

I need some explanation for K-Nearest Neighbors algorithm.

1. Why is the training process needed in KNN algorithm? In regression models the training process means to find optimum parameters for a selected function. Does the training in KNN mean that the similarity distances are calculated between training datapoints? Why is it good for a later prediction phase?

2. Are similarity distances also calculated between training and testing datapoints? If so then why is it necessary at all that before that the distances between training datapoints were calculated?

3. If the following code is executed then what does it exactly do? Does it mean that distances between training datapoints are calculated?

neigh = KNeighborsClassifier(n_neighbors = k).fit(x_train, y_train)

4. If the following code is executed then what does it exactly do? The manual says that class labels for each data sample are returned. But how is it done? Does it mean that distances between training and testing datapoints are first calculated? If not then how can we find neighbors for "unseen datapoints" at all? We need to know distances.

yhat = neigh.predict(x_test)

K Nearest Neighbors is a Classification Algorithm. Just as with every classification algorithm is important that the algorithm doesn't "remember" the answers and that the answer it gets can be generalized to all the population, not just learned from the database.

1. Why is the training process needed in KNN algorithm? In regression model the training process means to find optimum parameters for a selected function. Does the training in KNN mean that the similarity distances are calculated between TRAINING datapoints? Why is it good for a later prediction phase?

The traininig process is needed in KNN because (as I stated before), we want to avoid it from learning-the-database, the famous "overfitting".

As you stated, in a regression the training is for finding the optimum parameters, here too, but the idea of "parameters" slightly changes: Here the parameters are the selected points (individuals) and of course, the $$k$$, separating in train/test allows the model to be more general when the test data is unknown.

Yes, it means the KNN calculates distance only in the training set. When the optimum parameters are found in the training set, the results in the test set are better, more general.

Are similarity distances also calculated between TRAINING and TESTING datapoints? If so then why is it necessary at all that before that the distances between TRAINING datapoints were calculated?

The new datapoints (the ones from the TEST dataset) do not participate in a recalculation of KNN, the way the new points decide if they are blue or red is determined by the points which were calculated before (TRAIN dataset), by measuring which color the k nearest neighbors (of the new point) have.

For the new green point, with $$k=3$$, two were blue and one red, the new color is likely to be blue (and is assigned blue).

3. If the following code is executed then what does it exactly do? Does it mean that distances between TRAINING datapoints are calculated?

neigh = KNeighborsClassifier(n_neighbors = k).fit(x_train, y_train)


No, a more thoughful explanation would be that they are "memorized" in certain position and certain y_value. The calculation of distances is done when fitting TEST data.

4. If the following code is executed then what does it exactly do? The manual says that class labels for each data sample are returned. But how is it done? Does it mean that distances between TRAINING and TESTING datapoints are first calculated? If not then how can we find neighbours for "unseen datapoints" at all? We need to know distances.

yhat = neigh.predict(x_test)


As was explained in another point, the former code (fit) did not calculate distances, the code memorized the points. In the predict code, distances between x_train and x_test are computed, and for every member of x_test, the k nearest neighbors (from x_train) are found, and they vote to retrieve a class for this new datapoint (in x_test).

In the image, when $$k=3$$, they vote 2-1 to say that the green point (new one) is blue.

• How is pre-calculated fast-indexed structure useful in predicting testing data? Isn't it so that indexed training data gives information only for that how far are the datapoints in training dataset? It means that when predicting labels for testing data then all distances between training and testing data needs to be calculated anyway. If similarity is calculated between test point against ALL train points then what's the benefit if we know how far are the datapoints in training dataset? – Tauno Apr 26 '19 at 13:13