Francis R. Bach and Michael I. Jordan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1249

2003

Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.

---

BibTeX citation:

@techreport{Bach:CSD-03-1249,
    Author= {Bach, Francis R. and Jordan, Michael I.},
    Title= {Learning Spectral Clustering},
    Year= {2003},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5549.html},
    Number= {UCB/CSD-03-1249},
    Abstract= {Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.},
}

EndNote citation:

%0 Report
%A Bach, Francis R. 
%A Jordan, Michael I. 
%T Learning Spectral Clustering
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1249
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5549.html
%F Bach:CSD-03-1249