Consistency of spectral clustering

Details Consistency of spectral clustering Consistency of spectral clustering

2008-04-04

arxiv.org/abs/0804.0678v1

Annals of Statistics 2008, Vol. 36, No. 2, 555-586

Mathematics

Statistics Theory

Published in at http://dx.doi.org/10.1214/009053607000000640 the Annals of Statistics (http://www.imstat.org/aos/) by the Inst

Scientific paper

10.1214/009053607000000640

Consistency is a key property of all statistical procedures analyzing randomly sampled data. Surprisingly, despite decades of work, little is known about consistency of most clustering algorithms. In this paper we investigate consistency of the popular family of spectral clustering algorithms, which clusters the data with the help of eigenvectors of graph Laplacian matrices. We develop new methods to establish that, for increasing sample size, those eigenvectors converge to the eigenvectors of certain limit operators. As a result, we can prove that one of the two major classes of spectral clustering (normalized clustering) converges under very general conditions, while the other (unnormalized clustering) is only consistent under strong additional assumptions, which are not always satisfied in real data. We conclude that our analysis provides strong evidence for the superiority of normalized spectral clustering.

Affiliated with

Also associated with

No associations

Rating

Consistency of spectral clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Consistency of spectral clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consistency of spectral clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-190702