Identifying intervals for hierarchical clustering using the Gershgorin circle theorem

• Upper bounds on eigenvalues determine intervals for the ideal number of clusters.
• Upper bounds on eigenvalues obtained by the Gershgorin circle theorem.
• No need to perform computationally intensive eigen-decomposition to determine k.
• Provide a hierarchical clustering algorithm that uses the proposed intervals.

In this paper we present a novel method for unraveling the hierarchical clusters in a given dataset using the Gershgorin circle theorem. The Gershgorin circle theorem provides upper bounds on the eigenvalues of the normalized Laplacian matrix. This can be utilized to determine the ideal range for the number of clusters (k) at different levels of hierarchy in a given dataset. The obtained intervals help to reduce the search space for identifying the ideal value of k at each level. Another advantage is that we don’t need to perform the computationally expensive eigen-decomposition step to obtain the eigenvalues and eigenvectors. The intervals provided for k can be considered as input for any spectral clustering method which uses a normalized Laplacian matrix. We show the effectiveness of the method in combination with a spectral clustering method to generate hierarchical clusters for several synthetic and real world datasets.