9
$\begingroup$

As I understood, k-NN is a lazy learner algorithm and it doesn't need a training phase. So why do we need to use .fit() with sklearn and what happens when we use it?

$\endgroup$
8
$\begingroup$

On the conceptual level

Fitting a classifier means taking a data set as input, then outputting a classifier, which is chosen from a space of possible classifiers. In many cases, a classifier is identified--that is, distinguished from other possible classifiers--by a set of parameters. The parameters are typically chosen by solving an optimization problem or some other numerical procedure. But, in the case of knn, the classifier is identified by the training data itself. So, at an abstract level, fitting a knn classifier simply requires storing the training set.

On the implementation level

Evaluating a knn classifier on a new data point requires searching for its nearest neighbors in the training set, which can be an expensive operation when the training set is large. As RUser mentioned, there are various tricks to speed up this search, which typically work by creating various data structures based on the training set. The general idea is that some of the computational work needed to classify new points is actually common across points. So, this work can be done ahead of time and then re-used, rather than repeated for each new instance. A knn implementation using these tricks would do this work during the training phase. For example, scikit-learn can construct kd-trees or ball trees during the call to the fit() function.

Choosing $k$ and the distance metric

The number of neighbors $k$ and the distance metric are hyperparameters of knn classifiers. Performance can usually be improved by choosing them to suit the problem. But, the optimal settings aren't usually known ahead of time, and we must search for them during the training procedure. This search amounts to solving an optimization problem, and is similar to hyperparameter tuning for other methods.

$\endgroup$
10
$\begingroup$

You can implement it in a lazy way and it makes a decent exercise when discovering a language. (see per example one of my blog posts). But you can also index the data, to make the prediction (much faster).

If the feature space had a dimension of one, sorting the points according to this feature would help you find the neighbours much faster (using per example dichotomic search). In larger dimension, there is no natural generalization of sorting, but you can index the points using (per example) quadtrees.

Looking at the source, you can see that various methods have been implemented in scikit learn. And there is some research, that keep improving these nearest neighbour queries.

$\endgroup$
5
$\begingroup$

While the points the other answerers made are certainly valid and interesting, I'd like to point out one more thing from a strictly software engineering point-of-view:

To make it consistent with their API

sklearn's Estimators should, among other things, have a fit method that takes one or two array-likes(depending on whether it's a supervised/unsupervised estimator) and a number of implementation-specific details (Source).

So even if knn's fit method were to do absolutely nothing ever, it would likely still exist, because knn is an estimator and sklearn's developers, as well as the code they contribute, expect estimators to have a fit method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.