1. Doesn't make assumptions about the underlying structure of clusters and is better at finding irregularly shaped clusters
2. Very efficient for sparse data sets.

University of Michigan - Ann Arbor

Spectral Clustering is a clustering algorithm that formulates the building of clusters as a graph partitioning problem and uses the eigenvectors of a similarity matrix to break the data into clusters.

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

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

Advantages of Spectral Clustering

1. Computationally intensive
2. Not immediately apparent how to choose similarity functions or assigning the number of clusters without knowing something about the underlying data structure.
3. Uses K means, so the cluster assignments may not always be stable/the same.

Disadvantages of Spectral Clustering

https://towardsdatascience.com/spectral-clustering-82d3cff3d3b7

Image Reference : Spectral vs K means clustering

As we see, spectral clustering allows us to look at more complex cluster assigments based on more than just proximity.


Spectral Clustering vs K Means Clustering

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 its weighted adjacency matrix $$W$$. Let it have dimensionality $$n 	imes n$$. 3. Build the unnormalized Laplacian $$L$$ ($$n 	imes n$$). 4. If we wish to cluster the data into $$k$$ clusters (user-defined), then we consider the first $$k$$ eigenvectors of the matrix $$L$$. 5. Build an $$n 	imes k$$ matrix with each of the first $$k$$ eigenvectors as its 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-means clustering algorithm to put these distinct $$a_i$$ data points into clusters.

Learn Before

Related