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. (C) 2007 Elsevier B.V. All rights reserved.