Francis R. Bach and Michael I. Jordan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1249
June 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1249.pdf

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},
    Institution = {EECS Department, University of California, Berkeley},
    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