Spectral Clustering

COMPUTATIONAL STATISTICS

1. SPECTRAL CLUSTERING Prepared By Ms.W.Ancy Breen,A.P /CSE SRMIST

2. SPECTRAL CLUSTERING Spectral Clustering  is a growing clustering algorithm which has performed better than many traditional clustering algorithms in many cases. It treats each data point as a graph-node and thus transforms the clustering problem into a graph-partitioning problem. Spectral clustering is a popular unsupervised machine learning algorithm which often outperforms other approaches. Why spectral clustring ? Strength of spectral clustering Makes no assumptions on the shapes of clusters,can handled sprials,etc . EM or the like require an iterative process to find local minima and multiple restarts. Purpose of spectral clustering Spectral clustering is a technique with roots in graph theory, where the approach is used to identify communities of nodes in a graph based on the edges connecting them. The method is flexible and allows us to cluster non graph data as well.

3. Process of spectral clustering Construct a similarity graph( eg:KNN graph)for all the data points. Embed data points in a low-dimensional space(spectral embedding),in which the clusters are more obvious,with the use of the eigen vectors of the graph Laplacian . A classical clustering algorithm( eg:k -means)is applied to partition the embedding.

4. Three Basic Stages: 1)Pre-processing Construct a matrix representation of the graph. 2) Decomposition Compute eigen values and eigen vectors of the matrix . Map each point to a lower-dimensional representation based on one or more eigen vectors. 3)Grouping Assign points to two or more clusters, based on the new representation.

5. Matrix Representations of a Graph

6. Eigen Value and Eigen Vector of Graphs

7. Eigen Value and Eigen Vector of Graphs

8. Bipartitioning Via Spectral Methods