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

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!

• How does PCA reveal information about the optimal number of clusters? Could you elaborate? Oct 23, 2017 at 9:33
• Sure! The number of components that explain let's say 80% of the variance, could be the optimal number of clusters. If this makes sense then the problem is that, I did not find anywhere in scikit-learn documentation that PCA accepts similarity matrices as input :P Any ideas? Oct 25, 2017 at 7:53
• An overview of the indices used to select the better cluster solution stats.stackexchange.com/a/358937/3277 Dec 9, 2018 at 10:27
• It doesn't make sense to use PCA in the way you suggested because a linear (sub)space with a given dimensionality could contain any number of clusters. Jan 24, 2019 at 11:30

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.

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!

• The elbow method isn't specific for spectral clustering and was debunked in the GAP-statistic paper years ago, see: Tibshirani, Robert, Guenther Walther, and Trevor Hastie. "Estimating the number of clusters in a data set via the gap statistic." Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63.2 (2001): 411-423. Jul 1, 2018 at 6:58