We connect all nodes in the graph that are at most  $\epsilon$  'distance' away from each other

$\epsilon$ neighbourhood graph

We connect nodes to their k nearest neighbours. However there are times when this relation is NOT symmetric i.e. A's kth nearest neighbour is B, but A is B's k+1th nearest neighbour. This causes the graph to be directed which is a problem. 
This can be dealt with in two ways described in the child nodes.

K nearest neighbours graph

We connect all nodes that have a non zero similarity value ($s_{i,j}$) in the similarity matrix and weigh their edges by the value of $s_{i,j}$ .

Fully connected graph

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

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

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

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

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

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

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.

Learn Before

Related

Learn After