What are the main similiarities between K-means and K-nearest neighbours? I know that k-means is unsupervised and is used for clustering etc and that k-NN is supervised. These two are different. But I wanted to know if there any similiarities between the two?
 A: Both methods have k in the name, but this is completely incidental. K refers to something different for each method (the number of clusters in k-means vs. the number of neighbors in KNN). They're used for completely different purposes, but there are some connections between them.
Both methods involve computing distances in input space and assigning data points to a set of nearest 'prototype points'. But, they differ in this respect because 1) In KNN, the prototypes are training points. In k-means, the prototypes are cluster centroids, which are not restricted to be data points themselves. 2) In KNN, the training points are simply memorized and held fixed. In k-means, cluster centroids are learned by updating their values during training (which also changes the assignment of data points to centroids). 3) In k-means, data points are assigned to a single centroid (the nearest). In KNN, data points are assigned to the k nearest training points.
Once k-means has been trained, new points can be assigned to the existing clusters by simply finding the nearest centroid. This procedure is identical to a KNN classifier with k=1, where the training set consists of the cluster centroids and the labels consist of the cluster ids. Both k-means and KNN (with k=1) induce a Voronoi partition on input space. Each Voronoi cell consists of the set of points that would be assigned to the corresponding centroid or training point. But, this isn't true for KNN with k>1.
Along similar lines, we can draw an analogy between k-means and KNN regression as follows. Say we have a set of data points $X$ and a set of prototype points $P$. Given any data point $x$, we can find the nearest prototype and output it:
$$f(x) = \arg \min_{p \in P} \|x - p\|^2$$
Note that $f$ is equivalent to KNN regression (with k=1) using $P$ as both training inputs and outputs--that is, we're predicting points from themselves. Now, we want to find the set of prototypes that minimizes the squared prediction error on $X$:
$$\min_P \sum_{i=1}^n \|x_i - f(x_i)\|^2$$
This is equivalent to the k-means problem of minimizing the sum of within-cluster variance (clustering $X$ with centroids $P$). Therefore, it's possible to think of k-means as optimizing the training set of a nearest neighbor regression model for predicting points from themselves.
This perspective makes sense in the context of vector quantization, where the purpose is typically data compression (this is another application of k-means, besides clustering). We represent each data point by replacing it with the nearest prototype (prototypes are more properly called 'code vectors' in this application). This gives a compressed representation because prototype ids require fewer bits than the original vectors. We choose the prototypes such that we can reconstruct the original data as well as possible from the compressed representation. The number of prototypes controls the tradeoff between compression and accuracy.
