Spectral Clustering

Spectral Clustering V/s Conventional Clustering

Spectral Clustering is versatile, allowing us to cluster both graphical and non-graphical data. It makes no assumptions about the clusters' shape. K-Means and other clustering approaches presume that the points assigned to a cluster are spherical around the cluster center. This is a broad assumption that may or may not be accurate. In such instances, Spectral Clustering can assist in the creation of more distinct clusters. Due to dimension reduction, it may correctly cluster observations that belong to the same cluster but are further apart than observations in other clusters.

In Spectral Clustering, the data points should be connected but not necessarily have convex borders, unlike traditional clustering approaches, which cluster data points based on compactness. Although eigenvalues and eigenvectors must be computed, and Clustering must be performed on these vectors, it is computationally expensive for large datasets. Furthermore, as the size of the dataset grows larger, the complexity rises, and the accuracy falls.

Steps in Spectral Clustering

Constructing a similarity network, projecting data into a lower-dimensional space, and grouping the data are the three primary phases in spectral Clustering.

Similarity Network

The goal of spectral Clustering is to divide the data inputs into several groups such that points in the same group are similar and points in different groups are different. If we don't have any more information than the similarities between data points, we can express the data in a similarity graph G = (V, E). A data point xi is represented by each vertex vi in this network. If the similarity sij between the matching data points xi and xj is positive or more than a given threshold, two vertices are connected, and the edge is weighted by sij. The clustering problem may now be restated using the similarity graph: we want to identify a graph partition where the edges between various groups have very low weights (which suggests that points in different clusters are dissimilar). The edges within a group have large weights (which means that points within the same cluster are similar).

Epsilon-Neighborhood Graph: All points with pairwise distances less than epsilon are connected here. Weighting the edges would not add more information to the graph because the distances between all connected points are basically of the same scale (at most epsilon). As a result, the epsilon-neighborhood graph is sometimes considered an unweighted graph. If we choose an excellent parameter ε, we obtain well-defined clusters at the algorithm's output.

K-Nearest Neighbor Graph: The purpose is to link vertex vi to vertex vj if vj is one of vi's k-nearest neighbors. However, because the neighborhood relationship is not symmetric, this definition results in a directed graph. This graph can be made undirected in two ways. The first method is to ignore the edge directions, connecting vi and vj with an undirected edge if vi is one of the vj's k-nearest neighbors or vj is one of vi's k-nearest neighbors. The graph that results is known as the k-nearest neighbor graph. If both vi and vj are among the k-nearest neighbors of vj and vj is among the k-nearest neighbors of vj. If both vi and vj are among the k-nearest neighbors of vj and vj is among the k-nearest neighbors of vi, the second option is to connect them. The graph that results is known as the mutual k-nearest neighbor graph. After connecting the appropriate vertices, we weigh the edges based on the similarity of their ends in both circumstances.

Fully Connected Graph: Each point in this graph is connected to every other point by an undirected edge-weighted by the distance between the two points. Because this method is used to model local neighborhood relationships, the distance is usually calculated using the Gaussian similarity measure.

Projecting the Data onto Lower Dimensional Data

This step is taken to account for the potential that members of the same cluster may be separated by a large distance in the dimensional space. As a result, the dimensional space is reduced, and those points are closer in the reduced dimensional space, allowing a typical clustering technique to cluster them together. The Graph Laplacian Matrix is used to do this.

The Laplacian matrix is calculated by:

                                                                     L=D-A

Where,

L=Laplacian Matrix.

D=Degree Matrix.

A=Affinity matrix.

For mathematical efficiency, this Matrix is then normalized. To minimize the dimensions, the eigenvalues and eigenvectors must first be determined. If there are k clusters, the first eigenvalues and their eigenvectors are taken and stacked into a matrix, with the eigenvectors serving as columns. So to calculate the Laplacian matrix, we need to know about the degree matrix, affinity matrix, distance matrix(adjacency matrix), eigenvalues, and eigenvectors.

Adjacency List

The graph can be represented as an Adjacency Matrix, where the nodes are represented by the row and column indices. The entries are the presence or absence of an edge between the nodes (i.e., if the entry in row 0 and column 1 is 1, it would indicate that node 0 is connected to node 1).

Affinity Matrix(A)

An Affinity Matrix is identical to an Adjacency Matrix, except that the value for a pair of points represents how similar they are. If two locations are incredibly distinct, the affinity should be zero. The association could be one of the identical points. The affinity functions as the weights for the edges on our graph in this way.

Degree Matrix(D)

A Degree Matrix is a diagonal matrix in which the number of edges connecting to a diagonal node (i.e., values) determines its degree. The degree of the nodes can alternatively be calculated by adding the total of each row in the adjacency matrix.

Laplacian Matrix(L)

This is yet another visualization of the graph/data points, emphasizing the lovely qualities of Spectral Clustering. We subtract the Adjacency Matrix from the Degree Matrix (L = D – A) yields one such representation.

Clustering the Data

The majority of this procedure entails clustering the reduced data using any classic clustering technique, most commonly K-Means Clustering. First, a row of the normalized Graph Laplacian Matrix is assigned to each node. The data is then grouped using any standard method. The node identifier is kept while transforming the clustering result.

Properties:

Assumption Less: Unlike other classic clustering algorithms, this clustering technique makes no assumptions about the data. So, this technique can be used to solve a broader range of clustering problems.

Ease of implementation and speed:  K-means clustering algorithm is more straightforward to develop than other clustering algorithms. It is also swift because it is based mainly on mathematical computations.

Not-Scalable: It is time-consuming for dense datasets since it requires the construction of matrices and the computing of eigenvalues and eigenvectors.

Pros and Cons of Spectral Clustering

Spectral Clustering aids in the resolution of two fundamental clustering issues: the shape of the cluster and locating the cluster centroid. The K-means method presupposes that clusters are spherical or circular and within a k-radius of the cluster center. In K means determining the cluster centroid takes a lot of iterations. Clusters in the spectrum do not have a definite shape or pattern. Points that are far apart but connected belong to the same cluster, while points closer together but not connected may belong to distinct clusters. This suggests that the algorithm could work with all shapes and sizes of data. 

Compared to other techniques, it is computationally fast for sparse datasets with several thousand data points. To work with, you don't need the actual dataset. Distance or Clustering may be costly to compute for large datasets since eigenvalues and eigenvectors must be calculated first, followed by Clustering. The algorithms, on the other hand, strive to save money. Before beginning the operation, the number of clusters (k) must be determined.

FAQs

1. When it comes to spectral Clustering, how do you choose K?
   The value of k that maximizes the eigengap is commonly used to determine the number of clusters k. (difference between consecutive eigenvalues). The wider this eigengap, the closer the ideal case's eigenvectors are, and hence the better spectral Clustering works.
    
2. What is the purpose of spectral Clustering?
   Although spectral Clustering is a graph theory technique, it is used to identify communities of vertices in a graph based on the edges that connect them. This approach is adaptable, allowing us to cluster non-graph and graph data, both with and without the original data.
    
3. What makes spectral Clustering superior to k-means?
   Spectral Clustering is more computationally expensive for large datasets than K-Means since it requires eigendecomposition (low-dimensional space). Depending on the type of centroids initialization, the outcomes of both clustering methods may differ.
    
4. Is spectral Clustering a straight line?
   Due to its ease of implementation and promising performance in many graph-based clustering applications, spectral Clustering has grown in popularity. Standard linear algebra software can solve it quickly, and it frequently outperforms classic techniques like the k-means algorithm.

Key Takeaways

Let us brief the article.
We've studied the theory and implementation of spectral Clustering for both graphs and arbitrary data. When your data doesn't satisfy the requirements of other typical algorithms, spectral Clustering provides a flexible approach for locating clusters.
We started by making a graph out of our data points. The graph's edges represent the commonalities between the points. The Graph Laplacian's eigenvalues can then be used to determine the optimal number of clusters, and the eigenvectors can be used to determine the actual cluster labels.

Want to dig deeper into data science. Well, we have a perfect guiding partner for you.

I hope you all like this article.
Happy Learning Ninjas!