What is Spectral Clustering?

Spectral clustering has emerged as one of the most popular modern clustering algorithms in recent years. It is easy to implement, can be solved efficiently using standard linear algebra software, and frequently outperforms traditional clustering algorithms like the k-means algorithm. At first glance, spectral clustering appears somewhat mysterious, and it is unclear why it works at all and what it does. 

 

What is Spectral Clustering?

 

Spectral Clustering is a developing clustering algorithm that outperforms many traditional clustering algorithms in many cases. It considers each data point to be a graph node, transforming the clustering problem into a graph partitioning problem. A typical implementation includes three basic steps:

 

1. Building the Similarity Graph:

 

This step constructs the Similarity Graph in the form of an adjacency matrix A. The adjacency matrix can be constructed in the following ways: - 

 

• Epsilon-neighborhood Graph: 

 

An epsilon parameter is fixed in advance. Then, each point is linked to all the other points within its epsilon-radius. If all of the distances between any two points are similar in scale, the weights of the edges, i.e. the distance between the two points, are typically not stored because they provide no additional information. As a result, the graph constructed in this case is undirected and unweighted.

 

• K-Closest Neighbors:

 

A fixed parameter k is set in advance. Then, for two vertices u and v, an edge is only directed from u to v if v is one of u's k-nearest neighbors. It is worth noting that this results in the formation of a weighted and directed graph because it is not always the case that for each u having v as one of its k-nearest neighbors, the same is true for v having u as one of its k-nearest neighbors. One of the following approaches is used to make this graph undirected: - 

 

Direct an edge from u to v and from v to u if v is one of the u's k-nearest neighbors OR u is one of the v's, k-nearest neighbors. If v is among u's k-nearest neighbors AND u are among v's k-nearest neighbors, direct an edge from u to v and from v to u.

 

 

2. Projecting the data onto a lower Dimensional Space:

 

This step is performed to account for the possibility that members of the same cluster may be located in a distant location in the given dimensional space. As a result, the dimensional space is reduced, allowing those points to be clustered together using a traditional clustering algorithm because they are closer in the reduced dimensional space. This is accomplished by computing the Graph Laplacian Matrix.

 

3. Clustering the Data:

 

The main step in this process is to cluster the reduced data using any traditional clustering technique, most commonly K-Means Clustering. To begin, each node is assigned a row from the normalized Graph Laplacian Matrix. The data is then clustered using any conventional technique. The node identifier is kept in order to transform the clustering result.

 

Properties:
 

• Assumption-Less: 

Unlike other traditional clustering techniques, this one does not make any assumptions about the data. As a result, this technique can address a broader range of clustering problems.

 

• Ease of implementation and speed:

Because it primarily consists of mathematical computations, this algorithm is easier to implement than other clustering algorithms and also very fast.

 

• It is not scalable: 

Because it requires the construction of matrices as well as the computation of eigenvalues and eigenvectors, which takes time for dense datasets.

 

Also Read | What is Density-based Clustering

 

Approaches to Clustering:

 

Clustering is a popular unsupervised learning technique. The clustering is done in such a way that points in one cluster are similar to each other but less similar to points in other clusters. Thus, it is up to the algorithm to find patterns in the data and group them for us, and we may end up with different clusters depending on the algorithm used.

 

Clustering is a widely used unsupervised algorithm in machine learning to group unlabeled data points by similarity and distance measures as humans. Grouping is known as classification when the data points are labeled. Anomaly detection, image segmentation, search result grouping, market segmentation, and social network analysis are all applications of clustering algorithms. 

 

Clustering is one of the first steps in exploratory data analysis, used to visualize similarity and identify patterns hidden in data points. The goal of clustering is to find similarities within a cluster as well as differences between two clusters.

 

There are two major approaches to Clustering:

 

1. Compactness: 

 

The points are closer together and compact towards the cluster center in compactness. Closeness is calculated using distance as a measure. There are various types of distance metrics in use. Euclidean distance, Manhattan distance, Minkowski distance, and Hamming distance are a few examples. The compactness approach is used by the K-means algorithm. 

 

The points in a cluster are either immediately adjacent (epsilon distance) or connected in connectivity. Even if the distance between them is small, they are not placed in the same cluster. One technique that follows this approach is spectral clustering.

 

2. Connectivity: 

 

Points that are connected or immediately adjacent to each other are grouped together. Even if two points are closer together, if they are not connected, they are not clustered together. This approach is followed by the technique of spectral clustering. 

 

When we need to find general patterns in data and do not have a specific target, we use unsupervised modeling in Machine Learning (ML). We may only have a few independent variables.

 

It is important to note that we use clustering as the unsupervised ML method because supervised ML methods aim to predict the target value based on known independent variables (class, outcome, label, or dependent variable).
 

Also Read | 6 Types of Clustering Algorithms in Machine Learning

 

Steps to Spectral Clustering:

 

Three steps are involved in spectral clustering:

 

• Make a similarity graph.

• Map the data to a low-dimensional space.

• Make clusters

---

Steps to Spectral Clustering 

---

Step 1: Generate a similarity graph:

 

We begin by drawing an undirected graph G = (V, E) with vertex sets V = v1, v2,..., vn = 1, 2,..., n observations from the data. This can be represented by an adjacency matrix, the elements of which are the similarities between each vertex. To accomplish this, we can either compute:

 

• The neighborhood graph:

 

In this graph, we connect all points whose pairwise distances are less than. Because the distances between all connected points are roughly on the same scale (at most), weighting the edges would not add more data to the graph. As a result, the -neighborhood graph is commonly regarded as an unweighted graph.

 

• KNN Graph:

 

 In this case, we use K Nearest Neighbors to connect vertex vi with vertex vj if vj is one of vi's k-nearest neighbors.

 

However, if the nearest neighbors are not symmetric, we may encounter a problem. For example, if vertex vi has vj as the nearest neighbor, vi does not necessarily have to be vj's nearest neighbor. As a result, we get a directed graph, which is problematic because we don't know what similarity between two points means in that case. This graph can be made undirected in two ways.

 

The first method is to simply ignore the edge directions, connecting vi and vj with an undirected edge if vi is among vj's k-nearest neighbors or vj is among vi's k-nearest neighbors. The resulting graph is known as the k-nearest neighbor graph.

 

The second option is to connect vertices vi and vj if both vi and vj are among the k-nearest neighbors of vi. 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 the adjacent points in both cases.

 

• Fully connected graph:

 

 To create this graph, we simply connect all points and weigh all edges by similarity sij. This graph should model the local neighborhood relationships, so similarity functions such as the Gaussian similarity function are used.

 

The parameter here controls the width of the neighborhoods, just like the parameter in the -neighborhood graph.

 

As a result, when we create an adjacency matrix for any of these graphs, Aij 1 indicates that the points are close together and Aij 0 suggests that the points are far apart.

 

Step 2: Map the data to a low-dimensional space:

 

The data points in the same cluster can be as far apart as points in different clusters. Our goal is to transform the space so that when two points are close together, they always belong to the same cluster, and when they are far apart, they belong to different clusters. 

 

Our observations must be projected into a low-dimensional space. We compute the Graph Laplacian for this, which is simply another matrix representation of a graph that can be useful in discovering interesting properties of a graph.

 

The whole point of computing the Graph Laplacian L was to find eigenvalues and eigenvectors for it so that the data points could be embedded in a low-dimensional space. So we can now proceed to find eigenvalues.

 

Step 3 — Create Clusters:

 

In this step, we assign values to each node using the eigenvector corresponding to the second eigenvalue. The second eigenvalue is calculated to be 0.189, and the corresponding eigenvector v2 = [0.41, 0.44, 0.37, -0.4, -0.45, -0.37].

To obtain bipartite clustering (two distinct clusters), we first assign each element of v2 to the nodes in the following order: node1:0.41, node2:0.44,... node 6:-0.37. We then split the nodes so that all nodes with values greater than zero are in one cluster and all other nodes are in the other. Thus, in this case, we have nodes 1, 2, and 3 in one cluster and nodes 4, 5, and 6 in the other.

 

Pros and Cons of Spectral Clustering:

 

Some of the major pros and cons of spectral clustering are discussed below:- 

 

Spectral clustering assists us in overcoming two major clustering problems: the shape of the cluster and determining the cluster centroid. The K-means algorithm generally assumes that the clusters are spherical or round and that they are located within a radius of the cluster centroid. Many iterations are required in K means to determine the cluster centroid. 

 

Clusters in spectra do not have a fixed shape or pattern. Points that are far apart but connected belong to the same cluster, whereas points that are closer together but not connected may belong to different clusters. This implies that the algorithm may be applied to data of various shapes and sizes.

 

It is computationally fast for sparse datasets of several thousand data points when compared to other algorithms. You don't need the actual dataset to get started. Distance or Though it may be costly to compute for large datasets because eigenvalues and eigenvectors must be computed before clustering. However, the algorithms attempt to reduce the cost. Before beginning the procedure, the number of clusters (k) must be determined.

 

People try to get a first impression of their data in every scientific field that deals with empirical data by attempting to identify groups of similar behavior in their data. We demonstrated how the spectral clustering algorithm works by embedding graph vertices into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix.