How to find the optimal number of clusters for spectral clustering using similarity matrix in scikit learn

Question

What is the best way of finding out the optimal number of clusters, given that I just have a similarity matrix? Is it possible to do it all in Scikit-learn without any extra implementation?

My suggestion? PCA it!

Please correct, Thank you!

Answer 1

For methods that are specific to spectral clustering, one straightforward way is to look at the eigenvalues of the graph Laplacian and chose the K corresponding to the maximum drop-off. In R, this is implemented in the CRAN ‘Spectrum’ package https://cran.r-project.org/web/packages/Spectrum/index.html.

In the Zelnik-Manor et al (2005) paper the authors discuss this and a more sophisticated method that involves rotating the eigenvectors and minimising a cost function using gradient descent for each K. Then K is the one with the lowest cost. You would have to read the paper to get more details.

See: Zelnik-Manor, Lihi, and Pietro Perona. "Self-tuning spectral clustering." Advances in neural information processing systems. 2005.

There is another school of thought that says we should examine the distribution of the individual eigenvectors when deciding K. Eigenvectors that are less unimodal contain more information. An example of this is the multimodality gap method we came up with, but there are several similar methods which are popular in image analysis.

Christopher R John, David Watson, Michael R Barnes, Costantino Pitzalis, Myles J Lewis, Spectrum: fast density-aware spectral clustering for single and multi-omic data, Bioinformatics, btz704.

See this paper for a nice example.

Alshammari, Mashaan, and Masahiro Takatsuka. "Approximate spectral clustering with eigenvector selection and self-tuned k." Pattern Recognition Letters 122 (2019): 31-37.

Answer 2

Well, if you want to know the optimal number of clusters, one of the most common methods is the Elbow Curve method.

Basically what you have to do is to look at the graph where X is the number of clusters and Y is your WCSS (Within Cluster Sum of Squares). Since I cannot write formulas here because I'm new or attach images, the WCSS is further discussed here: https://discuss.analyticsvidhya.com/t/what-is-within-cluster-sum-of-squares-by-cluster-in-k-means/2706/2

Now that you've figured out what WCSS is visually, you'll see that the WCSS is high at the beginning and you'll notice it drop substantially and then after a while, it will still drop but there won't be any substantial change. That point where the last big drop is, that's the optimal number of clusters. That's how you choose the optimal number of clusters while using the Elbow Method. You can simply use sklearn's library for clustering.

Refer to this for other techniques: http://www.sthda.com/english/articles/29-cluster-validation-essentials/96-determining-the-optimal-number-of-clusters-3-must-know-methods/

Hope this helped!