4
$\begingroup$

From basic theory I know that knn is a supervised algorithm while for example k-means is an unsupervised algorithm.

However, at Sklearn there are is an implementation of KNN for unsupervised learning (http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.NearestNeighbors.html#sklearn.neighbors.NearestNeighbors).

What is exactly this unsupervised version of knn at SkLearn?

Is this a knn algorithm?

  • If yes how it is unsupervised since by definition knn is supervised?
  • If no what is it then?
Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The unsupervised version simply implements different algorithms to find the nearest neighbor(s) for each sample.

The kNN algorithm consists of two steps:

  1. Compute and store the k nearest neighbors for each sample in the training set ("training")
  2. For an unlabeled sample, retrieve the k nearest neighbors from dataset and predict label through majority vote / interpolation (or similar) among k nearest neighbors ("prediction/querying")

The unsupervised version is basically only step 1, the training phase of the kNN algorithm.

(This is useful because if your dataset is large, a pairwise comparison for all samples (algorithm='brute') is often infeasible. Therefore two alternative algorithms for the training stage are implemented that make use of previous comparisons to reduce the number of distance calculations. See the documentation here.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanksfor the answer @oW (upvote). "The unsupervised version simply implements different algorithms to find the nearest neighbor(s) for each sample.", by different you mean different than knn or different the one to each other? Also, my main question is: is this a knn algorithm? If yes how it is unsupervised since by definition knn is supervised? If no what is it then? $\endgroup$
    – Universalis0
    Commented Jul 5, 2018 at 22:07
  • $\begingroup$ Thanks for the updated answer! Then how diffirent is this unsupervised version of knn to kmeans which is essentialy again about neighbors in an unsupervised way? (I am going to look it up in more detail but if you can come up effortlessly with a concise answer then it is even better) $\endgroup$
    – Universalis0
    Commented Jul 5, 2018 at 23:15
  • $\begingroup$ kMeans is for clustering, the unsupervised kNN is just that... a way to find nearest neighbors in a dataset... what you do with that calculation is up to you. $\endgroup$
    – oW_
    Commented Jul 5, 2018 at 23:18
  • $\begingroup$ Ok, perhaps I am missing something. But essentially clustering (in kmeans) is done exactly by identifying "neighbors" (at least to a centroid which may be or may not be an actual data) for each cluster. What is its difference then to unsupervised knn? Is it that the unsupervised knn is identifying neighbors between the actual data points whereas kmeans is identifying neighbors to centroids (which may not be actual data points)? $\endgroup$
    – Universalis0
    Commented Jul 5, 2018 at 23:26
  • $\begingroup$ also k in kMeans refers to the number of clusters not the number of neighbors. in kMeans you only need to compute the distance from the data points to the centroid not to other data points. you don't really care about "neighbors" $\endgroup$
    – oW_
    Commented Jul 6, 2018 at 15:24
2
$\begingroup$

The confusion comes from the way Sklearn designed their code.

Short answer

The "unsupervised" version you mention is not a K-Nearest Neighbour algorithm (which is implemented here). In its description, it only reads:

"Unsupervised learner for implementing neighbour searches."

This learner is actually used by KNNClassifier in order to perform neighbour searches efficiently. Sklearn made it as a separate learner because other algorithms such as KMeans also need to perform neighbour searches.

Long answer

There exist many algorithms which require neighbour searches. KNN and K-Means being some of the famous ones. As a design choice, Sklearn decided to implement the neighbour search part as its own "learner".

To find a nearest-neighbour, you can obviously compute all pairwise distances but it might not be very efficient. This is why there exist smarter ways which use specific data structures like a KD-Tree or a Ball-Tree (Ball trees typically perform better than KD-Trees on high dimensional data by the way).

If you fit the unsupervised NearestNeighbors model, you will store the data in a data structure based on the value you set for the algorithm argument. And you can then use this unsupervised learner's kneighbors in a model which require neighbour searches.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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