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

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

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.

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

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.

University of Michigan - Ann Arbor

- K-means clustering
- Hierarchical clustering

Method of clustering in unsupervised statistical learning

K-Means Clustering is a form of unsupervised learning that aims to identify distinct categories in data by segmenting the data by Euclidean Distance into 'k' number of clusters.

K-Means Clustering

Method of clustering that seeks to build a hierarchy of clusters. 

Starts by treating each observation as separate cluster. Then it will repeated execute the following two steps: 

1. Identify the two clusters closest together
2. Merge the two most similar clusters 


The iterative process continues until all clusters are merged together

Hierarchical Clustering  

Some decisions must be made before performing K-means and hierarchical clustering. With these methods there is no single right answer and any solution that exposes some interesting aspects of the data should be considered.

Practical Issues in Clustering

Below is a video reference for both k-means and hierarchical clustering. It provides an easy introduction to both clustering methods and their algorithms.

[Luis Serrano]. (2019, January 27). Clustering: K-means and Hierarchical [Video File]. Retrieved from [www.youtube.com/watch?v=QXOkPvFM6NU](https://www.youtube.com/watch?v=QXOkPvFM6NU) 

Clustering: K-means and Hierarchical (Reference)

There are various applications for both k-means and hierarchical clustering using real life data. Some of these include:
- Genetics and evolutionary biology:
Genomes holds a lot of information about a species. That information can be clustered to understand how species have evolved over time
- Recommender systems:
Users can be clustered based on the similarity of their interests
- Social networks:
Demographics, behavior, and other factors can be clustered to target certain groups of users with specific types of information (echo chamber)

Applications of Clustering

Spectral Clustering

A Gaussian mixture model (GMM) is a unsupervised learning model which states that all generated data points are derived from a mixture of a finite Gaussian distributions that has no known parameters. The parameters for Gaussian mixture models are derived from an iterative expectation-maximization algorithm. 

Gaussian Mixture Model (GMM) Clustering 

- Density based spatial clustering of applications with noise 
- Don’t need to specify # of clusters 
- Relatively efficient 
 -Identifies likely noise points 
- Parameters:
       - Neighbor count parameter: min_samples
       - Neighborhood radius parameter: eps 
- Core point: point that lie in more dense region 
- For a given data point, if there are min_sample other data points that lie within a distance of eps, that given data point is labelled as a core sample 
- All core samples with a distance of eps units apart are put in the same cluster 
- Noise: points that don’t belong in any cluster 
- Boundary point: points within a distance of eps units from core points but not core points themselves

Learn Before

Related

Learn After