spectral clustering

A clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size. method that uses the eigenvectors of a matrix derived from a similarity graph over the data. Points become nodes of a graph whose edges are weighted by similarity (for example a Gaussian kernel or k-nearest-neighbor connections); the graph Laplacian, usually normalized, is formed; the eigenvectorseigenvector, n.: A special direction for a transformation: anything pointing that way stays on its line, only longer, shorter or reversed; the amount of stretch is the eigenvalue. Together they reveal the main axes along which data or a system varies. belonging to its k smallest eigenvalues give each point a new k-dimensional representation; and k-meansk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat. is run on those coordinates. The procedure is a continuous relaxation of finding a minimum normalized cut, a partition that severs as little edge weight as possible while keeping the groups balanced. Spectral clustering can recover non-convex shapes, such as concentric rings, that defeat k-means, and it links clustering to graph partitioning and manifold learning. Its costs are building the similarity graph and computing the eigendecomposition, roughly cubic in the number of points unless sparse or approximate solvers are used, and it is sensitive to the scale chosen for the similarity function.

K-means split the two interlocking crescents down the middle, while spectral clustering separated them cleanly.