k-nearest neighbours, k-means and clustering

In short: k-NN classifies a point by its k nearest neighbours. k-means splits data without labels into k groups (clusters) by searching for centres.

In more detail: Both work with distances in feature space. Features must therefore be scaled to a similar magnitude beforehand.

In detail

• k-NN: no training, just storing. For a new point find the k nearest known points and take the most frequent class. Simple, slow with lots of data.
• k-means: choose random centres → assign each point to the nearest centre → recompute centres → repeat until stable. You must specify k.
• DBSCAN: finds dense regions, detects outliers, the number need not be specified.
• Hierarchical clustering: builds a merge tree (dendrogram).
• Use: customer segments, image compression (colour palette), document groups, recommendations.
• Distance measures: Euclidean, Manhattan, cosine (for text embeddings, see Embedding (vector representation)).
• Curse of dimensionality: in very many dimensions all distances become similar.

See also: Principal component analysis (PCA), Kinds of learning: supervised, unsupervised, reinforcement