Spectral Clustering: Algorithm
In this post, we are going to discuss the Spectral Clustering Algorithm. In recent times the SC Algorithms are widely used they are simple to implement, can be solved efficiently by standard linear algebra methods, and very often outperforms traditional clustering algorithms such as the k-means algorithm & Hierarchical Clustering. And it has many fundamental advantages.
They are more accurate cause we get more tight clusters. At the first glance, spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does.
Spectral Clustering Algorithm
As its name suggests, this method uses the spectrum (eigenvalues) of the similarity matrix (i.e. Affinity Matrix, Degree Matrix, and Laplacian Matrix) of the data to cluster them and that was to first step to go with the algorithm. The next important aspect of SC is the Laplacian matrix, which is constructed from the similarity matrix.
We assume that our data consists of n “points” x1,…,xn which can be arbitrary objects. We measure their pairwise similarities sij = s(xi, xj ) by some similarity function which is symmetric and non-negative, and we denote the corresponding similarity matrix by S = (sij )i,j=1…n.
Non-normalized Laplacian:
L=D-S
Where S is the similarity matrix and D is a diagonal matrix whose elements are obtained by adding together the elements of all the columns for every row of S.
Input: Similarity matrix S ∈ n×n, number k of clusters to construct.
Construct a similarity graph. Let W be its weighted adjacency matrix.
Compute the unnormalized Laplacian L.
Compute the first k eigenvectors u1,…,uk of L.
Let U ∈ n×k be the matrix containing the vectors u1,…, Uk as columns.
For i = 1,…,n, let Yi ∈ k be the vector corresponding to the i-th row of U.
Cluster the points (Yi)i=1,…,n in k with the k-means algorithm into clusters C1,…, Ck.
Output: Clusters A1,…,Ak with Ai = {j| yj ∈ Ci}.
Normalized Laplacian:
Where I is the Identity Matrix..
Input: Similarity matrix S ∈ n×n, number k of clusters to construct.
Construct a similarity graph by one of the ways described in Section 2. Let W be its weighted adjacency matrix.
Compute the unnormalized Laplacian L.
Compute the first k generalized eigenvectors u1,…,uk of the generalized eigenproblem Lu = λDu.
Let U ∈ n×k be the matrix containing the vectors u1,…,uk as columns.
For i = 1,…,n, let yi ∈ k be the vector corresponding to the i-th row of U.
Cluster the points (yi)i=1,…,n in k with the k-means algorithm into clusters C1,…,Ck.
Output: Clusters A1,…,Ak with Ai = {j| yj ∈ Ci}.
Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)
Input: Similarity matrix S ∈ n×n, number k of clusters to construct.
Construct a similarity graph by one of the ways described in Section 2. Let W be its weighted adjacency matrix.
Compute the normalized Laplacian Lsym.
Compute the first k eigenvectors u1,…,uk of Lsym.
Let U ∈ n×k be the matrix containing the vectors u1,…,uk as columns.
Form the matrix T ∈ n×k from U by normalizing the rows to norm 1, that is set tij = uij/( ” k u2 ik)1/2.
For i = 1,…,n, let yi ∈ k be the vector corresponding to the i-th row of T.
Cluster the points (yi)i=1,…,n with the k-means algorithm into clusters C1,…,Ck.
Output: Clusters A1,…,Ak with Ai = {j| yj ∈
All three algorithms stated above look rather similar, apart from the fact that they use three different graph Laplacians. In all three algorithms, the main trick is to change the representation of the abstract data points xi to points yi ∈ k. It is due to the properties of the graph Laplacians that this change of representation is useful.