Spectral ClusteringIt is a clustering method based on graph theory. It divides a weighted undirected graph into two or more optimal subgraphs. The subgraphs are similar internally and far apart to achieve clustering. Its essence is to transform the clustering problem into the optimal partitioning problem of the graph. It is a point-to-point clustering algorithm.

Compared with traditional clustering algorithms, spectral clustering has the ability to cluster samples in arbitrary shape spaces and converge to the global optimal solution. The algorithm defines an affinity matrix based on the given samples, which is used to describe the similarity of paired data points, and calculates the eigenvalues and eigenvectors of the matrix, and selects appropriate eigenvectors to cluster different data points. Spectral clustering algorithms were initially used in computer vision, VLSI design and other fields, and were not used in machine learning until 2005.

Characteristics of spectral clustering

Spectral clustering is a widely used clustering algorithm. It has stronger adaptability to data distribution than the K-Means algorithm and has excellent clustering effect. At the same time, the clustering calculation amount is smaller and the implementation is not complicated.

Spectral clustering method

Clustering is to divide samples into two or K parts reasonably. From the perspective of graph theory, the clustering problem is equivalent to the graph segmentation problem.

Given a graph G = (V, E), where the vertex set V represents each sample and the weighted edges represent the similarity between each sample, the purpose of spectral clustering is to find a reasonable partitioning method so that the edge weights connecting the subgraphs after partitioning are as low as possible, and the weights of the edges within the same subgraph are as high as possible.

Sub-word: clustering

Related words: graph theory