We insert a mini step between steps 3 and 4 of the algorithm so that instead of calculating the eigenvectors of the unnormalized Laplacian, we calculate the eigenvectors of the generalized eigenproblem
$$Lv = \lambda Dv$$


Normalized Spectral Clustering 1

We calculate the eigenvectors of the matrix generated by :
$$D^\frac{-1}{2} L D^\frac{-1}{2} = I - D^\frac{-1}{2} W D^\frac{-1}{2}$$
Where W is the adjacency matrix (weighted), D is the degree matrix and L is the unnormalized Laplacian.

Normalized Spectral Clustering 2

We just follow the same algorithm and find the eigenvectors of the unnormalized Laplacian.

Unnormalized Spectral Clustering

Normalized spectral clustering is more accurate for prediction in applications like image segmentation, stochastic blockmodels etc. (Role of Normalization in Spectral Clustering for Stochastic Blockmodels, Sarkar, Bickel [2015]). Unnormalized spectral clustering however is less computationally intensive.

Normalized vs Unnormalized Spectral Clustering

1. Normalized Spectral Clustering 1 by Shi and Malik [2000]
2. Normalized Spectral Clustering 2 by Ng, Jordan, Weiss [2002]
3. Unnormalized Spectral Clustering

University of Michigan - Ann Arbor

Algorithm : 
Input : Similarity Matrix and number of clusters k.
1. Represent all data points as nodes in a graph.
2. Build the similarity graph given a similarity matrix. Calculate it's weighted adjacency matrix W.  Let these have the dimentionality n x n.
3. Build the unnormalized Laplacian L (n x n) 
4.  If we wish to cluster the data into k points (user defined), then we consider the first k eigenvectors of the matrix L.
5.  Build an n x k matrix with each of the first k eigenvectors as it's columns. Let us call this matrix M.
6.  Interpret each **ROW** of the matrix M as a separate data point $a_i$ . 
7.  Run the k-mean clustering algorithm to put these distinct $a_i$ data points into clusters.

Spectral Clustering Algorithm

Resources referred to : 
1. [towardsdatascience.com/spectral-clustering-82d3cff3d3b7](https://towardsdatascience.com/spectral-clustering-82d3cff3d3b7)
2. [en.wikipedia.org/wiki/Spectral_clustering](https://en.wikipedia.org/wiki/Spectral_clustering) 

Reference : spectral clustering

Papers and class slides referred to : 
1. [www.cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf](https://www.cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf)
2. [www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf](https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf)
3. [people.cs.pitt.edu/~milos/courses/cs3750-Fall2011/lectures/class17.pdf](https://people.cs.pitt.edu/~milos/courses/cs3750-Fall2011/lectures/class17.pdf)
4. [projecteuclid.org/download/pdfview_1/euclid.aos/1431695635](https://projecteuclid.org/download/pdfview_1/euclid.aos/1431695635) 

Paper References : spectral clustering

The K Means Clustering run on the distinct $a_i$ data points, assigns them to different clusters. The question then arises, how does this allow us to assign cluster assigments to the original data points?

Well, matrix M has dimensionality n x k, i.e. it has n separate points that are classified by the K Means algorithm. Each of these n points is in a one-to-one correspondence with each of the n points in the original similarity matrix i.e. each node of the graph which directly encodes every data point. Thus the assignment of the ith row in M is the same as the cluster assignment of the ith data point.

Thus spectral clustering helps us be more *efficient* with assigning clusters to points of high dimensionality, by mapping them to a lower dimension and *then* running K means on them.

Interpreting output of Spectral Clustering Assignments

Variations of Spectral Clustering Algorithm

Each data point in the matrix denotes the similarity between two data points i.e. $w_{i,j}$ denotes the similarity between points $i$ and $j$ calculated by some specific function. Eg : Gaussian similarity function : 

$$w_{i,j} = exp(- \frac{||x_i - x_j||^2}{2\sigma^2})$$
Here $||$ denotes the L2 norm, and $\sigma$ is just a parameter.
W is symmetric and all $w_{i,j} >= 0$ 


Definition : Adjacency Matrix W

A degree matrix D is a diagonal matrix where

$$d_{i,i} = \Sigma_j w_{i,j}$$
$$d_{i,k} = 0$$
where k != i, $w_{i,j}$ are elements in W, $d_{i,k}$ are elements of D.

Definition : Degree Matrix

The Unnormalized Laplacian is constructed as : 
$$L = D - W$$
Where D is the degree matrix, W is the adjacency matrix, and L is the unnormalized laplacian.

Definition : Unnormalized Laplacian

The first thing we need to do for the algorithm is build a similarity graph from the similarity matrix. There are three types of similarity graphs that can be generated :
1. $\epsilon$ -neighbourhood graph
2. K nearest neighbours graph
3. Fully connected graph

Learn Before

Related

Learn After