Spectral clustering | Laplace matrix

The concept of spectral clustering

The essence of spectrum clustering is to use the similarity between samples , After dimensionality reduction, use clustering algorithm to cluster nodes .
The eigenvalue of the Laplace matrix used is called “ Spectrum ”.

Laplace matrix

① Sample similarity matrix S：
We have n Samples , The similarity between two samples can be obtained by using some similarity measurement method . Such as Gaussian similarity ：
$$S_{i,j}=exp(-\frac{||x_i-x_j|{|}_2^2}{2{\sigma }^2})$$
Get the similarity matrix of the sample , Write it down as S.
② Adjacency matrix A：
For each sample point , take k The nearest neighbor acts as its neighbor node , Construct adjacency matrix A.
That is, if i yes j Of k Close neighbors and j yes i Of k a near neighbor , be $A_{i,j}=S_{i,j}$, otherwise $A_{i,j}=0$
③ Degree matrix D：
D It's a diagonal matrix , The diagonal element is the degree of each node , The rest of the elements are 0.
④ Non standardized Laplace matrix ：
L=D-A
⑤ Standardized Laplace matrix ：
$L_{sym}=D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}$
here $L_{sym}$ There is an important property ： Of Laplace matrix 0 Multiplicity of eigenvalues k Equal to the number of connected components in its corresponding graph .

Steps of spectrum clustering

Input ： Sample set D=(𝑥1,𝑥2,…,𝑥𝑛), Dimension after dimension reduction m, Clustering method , Dimension after clustering y
Output ： Clustering 𝐶(𝑐1,𝑐2,…𝑐y).
　
①~⑤： ditto , Find the standardized Laplace matrix ∈$R_{n\ast n}$
⑥ Find out $L_{sym}$ The eigenvalues of the , Take the smallest m Eigenvalues , Find the corresponding eigenvector , Form a n*m Matrix , That is, the characteristic matrix after dimension reduction , Each line corresponds to a sample point .
⑦ Standardize the matrix
⑧ Cluster the normalized eigenvector matrix （ Such as k-means）