Inappropriateness of the criterion of k-way normalized cuts for deciding the number of clusters
Spectral clustering is a completely different algorithm from other existing clustering algorithms in that it relies on a linear algebraic approach including spectral decomposition. Normalized Cuts is a representative algorithm of spectral clustering. It incorporates a criterion for deciding the number k of clusters to partition. This paper shows that the criterion is not appropriate for deciding k. We showed this by proving that the optimal bipartition (that is, when k=2) becomes the optimal clustering. Namely, based on the criterion, the evaluation becomes better when k is small. We also show that the criterion is inappropriate for comparing approximate solutions with various k . Especially we prove that a bipartition which surpasses the best given approximate solution H  k  can be constructed from H  k  within the time complexity at most O ( k  3 ) , where k  is the number of clusters contained in H  k  . Based on these two reasons, the Normalized Cuts Criterion is not appropriate for deciding k. An alternative criterion is necessary.
number of clusters clustering spectral clustering cluster validation