In many fields of exploratory data analysis, you will hear the term Spectral Clustering mentioned. Its widespread use comes from the ability it has to adapt to many different types of data, as well as finding ways to group data that may otherwise seem unrelated. Unlike other types of data processing, Spectral Clustering tends to look at the affinity of the data points – how connected they are to one another – rather than their actual location on a graph. This is where the power is in Spectral Clustering, and how we can use it in applications such as image processing and bioinformatics.

The Basic Steps

Spectral Clustering can be broken up into three smaller steps that create our clusters and then allow us to solve relations between related data points. Remember, Spectral Clustering only works if the data points within a certain set are closely related to each other, but are unrelated to other members outside of the chosen set. The steps we take in setting up for Spectral Clustering are:

1. Generate a similarity graph between a number of objects. This is, in essence, our cluster. We can have as little as two clusters or dozens, depending on how disparate the data we’re looking at is. The similarity graph links these objects logically.
2. Calculate the first set of eigenvectors up to a value of k for the Laplacian Matrix generated from our clusters. This allows us to define a feature vector for each individual cluster object.
3. Run a k-means computation on those vectors in order to divide up those clusters into k classes.

Graph Methodology

When it comes to constructing the graphs, we have a pair of methods we can use. The first is the k-Nearest Neighbor (KNN) mapping which associates any particular point with its closest k-related neighbors, where k is an integer value that is related to local data relationships. The second method is called the ε-neighborhood graph which links relations based on the overlap of a ball with radius ε. The radius can be adjusted to fine-tune the relationship, as in the case of cloud storage applications. Generally, k-Nearest Neighbor gives a more connected view of the data than the ε-neighborhood graph. Due to how KNN is calculated, data that would be on different “scales” could theoretically be linked based on their characteristics. Ε-neighbor processing only gives an ear to the physical location of the points and while the radius can be adjusted, it’s unlikely that it would give as deep connectivity as KNN.

Calculating the Eigenvectors and K-Means Computation

Once the clusters are defined, we move on to creation of the Laplacian Matrix. Knowing the Weight Matrix (W) and the Diagonal (degree) matric (D) we can simply construct the Laplacian Matrix, L by the calculation D – W. Once we have L, we can move on to compute the eigenvectors of L. Finally, we apply the k-means algorithm to our clusters. What k-means seeks to accomplish is to separate the data we have into clusters with the nearest mean to the cluster we’re currently dealing with.

Choosing a Legitimate Value for k

If we take the points in our clusters and project them onto a non-linear embedding, then examine the eigenvalues relating to the Laplacian Matrices, we can make an inference as to what value of k we should be using for our processing.

Data Processing and Spectral Clustering

Scientific data can be better processed when it’s represented as clusters. This procedure allows a data set to be generalized using this procedure in order to prepare the data for more complex processing while at the same time offering unique insights into the data through the location and relation of the clusters formed.